括号匹配问题分析
( ( ( ( ) ) ) )
最后的左括号最先被匹配(LIFO)——可以用栈实现这个特性
( ( ( ) ) ( ) )
每出现一个右括号,就消耗一个左括号(出栈)遇到左括号就入栈,遇到右括号就消耗一个左括号,并且与右括号的大小进行比较
算法实现
代码12345678910111213141516171819202122232425262728293031323334353637383940#define MAXSIZE 10typedef struct{ char data[MAXSIZE]; int top;}SqStack;void InitStack(SqStack &S){ S.top=0;}bool Push(SqStack &S,char x){ S.data[S.top]=x; S.top++; return true;}bool Pop(SqStack &S,char &x){ ...
队列的概念队列(Queue)是指允许在一段插入,另一端删除的线性表
重要术语
队头:允许删除的一端
队尾:允许插入的一端
空队列:队列里没有任何数据元素
特点:先进先出(FIFO)First In First Out
队列的基本操作
队列的顺序实现队列的定义12345#define MAXSIZE 10typedef struct{ int data[MAXSIZE]; int front,rear;//队头指针和队尾指针}SqQueue;
队列的初始化1234void InitQueue(SqQueue &Q){ Q.front=0; Q.rear=0;}
判断队列是否为空1234bool QueueEmpty(SqQueue Q){ if(front==rear)return true; else return false;}
入队12345bool EnQueue(SqQueue &Q,int x){ if((Q.rear+1)%MAXSIZE==Q ...
栈的概念栈(stack)只允许在一端 进行插入或删除操作的线性表。
重要术语
空栈:栈里没有任何数据元素
栈顶:允许插入和删除的一段
栈底:不允许插入和删除的一段
特点:先进后出(LIFO)Last In First Out
栈的基本操作
常考题型合法的出栈顺序n个元素进栈,出栈元素的不同排列的个数为$\frac{1}{n+1}C_{2n}^{n}$
顺序栈顺序栈的定义12345#define MAXSIZE 10typedef struct { int data[MAXSIZE]; int top;}SqStack;
顺序栈的初始化注意:看清楚top是指向栈顶元素还是栈顶元素的后面一个位置
1234void InitStack(SqStack &S){ S.top=-1;//指向栈顶元素 //栈满条件top==MAXSIZE-1}
判断栈空1234bool StackEmpty(SqStack S){ if(S.top==-1)return true; else return fal ...
逻辑结构
都是线性表,都是线性结构
存储结构
顺序表:
采用顺序储存
优点:支持随机存取、存储密度高
缺点:分配连续的大片空间不方便;不方便改变容量大小
链表:
链式储存
优点:离散的小空间分配方便;改变容量方便
缺点:不可随机存取、存储密度低
基本操作创
顺序表:分配一大片连续空间(动态分配、静态分配)
链表:只分配一个头结点
销
顺序表:修改lenth=0,将顺序表标记为一个空表
静态分配:静态数组(自动回收空间)
动态分配:动态数组(malloc、free)(需要手动free)
链表:依次销毁各个结点(free)
增删
顺序表:增/删都需要移动大量数据元素
时间复杂度O(n),主要消耗到移动元素上(若数据元素很大,则移动的时间代价很高)
链表:只需要修改指针
时间复杂度O(n),主要消耗在查找目标元素上
查
顺序表:
按位查找:时间复杂度O(1)
按值查找:时间复杂度O(n)(若顺序表内元素有序,时间复杂度O($\log_{2}{n}$)
链表:
按位查找:时间复杂度O(n)
按值查找:时间复杂度O(n)
项目
顺序 ...
静态链表的定义用数组的方式实现的链表
优点:增删操作不需要移动大量数据
缺点:不能做到随机存取;容量固定
适用场景:
不支持指针的低级语言
数据元素数量固定不变的场景(如操作系统的文件分配表FAT)12345678#define MAXSIZE 100typedef struct Node{ int data; int next;}void TestSLinkList(){ struct Node a[MAXSIZE];}
另一种写法12345678#define MAXSIZE 100typedef struct Node{ int data; int next;}SLinkList[MAXSIZE];void TestSLinkList(){ SLinkList a;}
静态链表的初始化将头结点的next修改为-1,将空结点的next修改为-2
静态链表的查找从头结点开始挨个查找
静态链表的插入插入位序为i的位置
找到空的结点,存入新的数据
找到第i ...
单链表初始化12345678910typedef struct LNode{ int data; struct LNode *next;}LNode,*LinkList;bool InitLinkList(LinkList &L){ L=(LNode*)malloc(sizeof(LNode)); if(L==NULL)return false; L->next=L; return true;}
判断是否为空1234bool Empty(LinkList L){ if(L->next==L)return true; else return false;}
判断结点p是否为最后一个结点1234bool isTail(LinkList L,LNode *p){ if(p->next==L)return true; else return false;}
循环双链表初始化1234567891011typedef struct D ...
双链表的定义1234typedef struct DNode{ int data; struct DNode *prior,*next;}*DLinkList;
双链表的初始化(带头结点)1234567bool InitList(DLinkLIst &L){ DNode L=(DNode*)malloc(sizeof(DNode)); if(L==NULL)return false; L->next=NULL; L->prior=NULL; return true; }
双链表的插入在p结点后插入s结点
12345678910bool InsertNextDNode(DNode *p,DNode *s){ if(p==NULL||s==NULL)return false; s->prior=p; if(p->next!=NULL){ p->next->prior=s; } s-> ...
前言第一次去往live现场,简单地写个repo吧,总体来说这次的体验感很不错,从西安坐十五个小时硬座,在车上艰难地度过了一个晚上,最终到达了上海。从江苏那边开始,窗边的风景就逐渐显示出了长三角地区的繁华。出了上海站后先被火车站和地铁站吓一跳,虽然说是老火车站,但是雀食挺破的…然后就是入住青旅,定的青旅位置不算偏,在杨浦区宁国路,旁边紧挨着地铁站,挺方便的。定的本来是八人间,两天78块,但是青旅八人间人满了,免费升舱六人间,床要自己铺,剩下的5个舍友两天基本没见,床铺挺舒服的,就是个歇脚的地方,也不奢望什么了。
8月22日day1第一天从青旅出来已经一点左右了,当时也不知道先去哪里,就这时群里发来了有人在东京羽田机场见到了ppp一行人,航班大概率是三点降落虹桥t1,所以我们当时直接当机立断去机场接机来接机的人不少,远远看过去就认出来都是来接机的了有一股味儿然后就是一直在等,多等了1个小时才等到中间还接到了意料之外的人,虽然都没认出来,不过当时看到就感觉不像是普通人,挺像那个谁的,所以也录了个视频,后边别人才知道原来是月音瑚奈然后重点来了,就在我放下录像休息的时候,正主出来了,等我拿起手 ...
单链表的概念链式存储结构:用一组任意的存储单元存储线性表的数据元素(可以是连续的,也可以是不连续的)结点(node):存储映像
数据域:存储数据元素信息
指针域: 存储直接后继储存位置存储的信息叫做指针或域
单链表的定义1234typedef struct LNode{ int data; struct LNode *next;}LNode,*LinkList;//LNode强调是结点,LinkList强调是单链表
单链表的初始化不带头结点的单链表1234bool InitList(LinkList &L){ L=NULL; return true;}
带头结点的单链表12345678bool InitList(LinkList &L){ L=(LNode*)malloc(sizeof(LNode)); if(L=NULL){ return false; } L->next=NULL; return true;} ...
顺序表的概念用一组地址连续的存储单元依次存储数据元素的线性表叫做顺序表
特点:逻辑上相邻的数据元素,其物理次序也是相邻的
顺序表的定义静态1234567#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef struct { int data[MAXSIEZE]; int length;}Sqlist;
动态1234567#include<stdio.h>#define INITSIZE 100typedef struct{ int *data; int Maxsize; int length;}Seqlist;
顺序表的初始化静态123456void Initlist(Sqlist &L){ for(int i=0;i<MAXSIZE;i++){ L.data[i]=0; } L.length=0;}
动态1234void In ...










