王道考研2021

王道给的代码中，有些用的是c++，但是和c的区别不大，不影响理解。 ElemType e 指e为任意数据类型，如struct,int…

文章目录线性表顺序表定义静态分配动态分配初始化与增加动态数组长度顺序表插入顺序表删除按位查找按值查找结构类型的比较单链表初始化判断是否为空按位查找按值查找求表长度单链表插入按位序删除指定结点删除尾插法建立单链表头插法建立单链表双链表初始化双链表插入双链表删除双链表遍历循环链表循环单链表循环双链表 *静态链表定义基本操作栈顺序栈的定义初始化操作判断栈空进栈出栈读取栈顶元素*共享栈链栈的定义栈在括号匹配中的应用栈在表达式求值中的应用计算逆波兰表达式队列定义与初始化判空入队与判满出队获取队头元素值队列节约空间的定义方式链式队列定义初始化判空入队出队*双端队列特殊矩阵的压缩存储串定义串的链式存储求子串比较定位朴素模式匹配算法KMP算法KMP算法的改进树概念基本概念结点关系描述高度、深度、度有序树和无序树树和森林树的常考性质二叉树概念满二叉树和完全二叉树二叉排序树平衡二叉树常考性质顺序存储定义和初始化顺序存储基本操作与判断链式存储定义/初始化/插入链式存储递归遍历求树的深度（应用）

线性表

在这里插入图片描述

顺序表定义静态分配 #define MaxSize 10typedef struct{ElemType data[MaxSize];int length;}SqList; 动态分配 #define InitSize 10//默认的最大长度typedef struct{int *data;//指示动态分配数组的指针int MaxSize;//顺序表的最大容量int length;//顺序表的当前长度}SeqList; 初始化与增加动态数组长度 //用动态分配定义顺序表void InitList(SeqList &L){//用malloc函数申请一片连续的存储空间L.data=(int *)malloc(InitSize*sizeof(int));L.length=0;//设置长度容易忘L.MaxSize=InitSize;}void IncreaseSize(SeqList &L,int len){//先申请一个比之前大的空间，把原先的数组复制进去，再释放原先的空间int *p=L.data;L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));for(int i=0;i=L.MaxSize)//当前存储空间已满，不能插入return false;for(int j=L.length;j>=i;j--)//将第i个元素及之后的元素后移L.data[j]=L.data[j-1];L.data[i-1]=e;//在位置i处放入eL.length++;//长度加1return true;} 顺序表删除

此处前移，先移动靠前的元素，再移动靠后的元素

//用静态分配定义顺序表bool ListDelete(SqList &L,int i,int &e){if(iL.length)//判断i的范围是否有效return false;e=L.data[i-1];//将被删除的元素赋值给efor(int j=i;jnext==NULL) return true;else return false;} 按位查找 //按位查找，返回第i个元素LNode *GetElem(LinkList L,int i){if(inext;//从第1个结点开始查找数据域为e的结点while(p!=NULL && p->data !=e)p=p->next;return p;//找到后返回该结点指针，否则返回NULL} 求表长度 //求表的长度int Length(LinkList L){//此处不需要间接访问int len = 0;//统计表长LNode *p = L;while(p->next!=NULL){p=p->next;len++;}return len; 单链表插入

综合了按位序+在指定结点后前/后插的代码

//在第i个位置插入元素ebool ListInsert(LinkList &L,int i,ElemType e){if(idata = e;//用结点s保存数据元素e//后插操作s->next=p->next;p->next=s;//将结点s连到p之后//拓展：前插操作s->next=p->next;//修改指针域p->next=s;temp=p->data;//交换数据域部分p->data=s->data;s->data=temp;return true;} 按位序删除 bool ListDelete(LinkList &L,int i,ElemType &e){if(inext == NULL)return false;//第i-1个结点之后已无其他结点LNode *q=p->next;//令q指向被删除结点e = q->data;//用e返回元素的值（不禁联系到js和python的pop方法）p->next=q->next;//将*q结点从链中“断开”free(q);//释放结点的存储空间return true;//删除成功} 指定结点删除

先用后继结点q的数据域覆盖当前结点p的数据域，然后把当前结点的指针域指向下下个结点，删掉q。

bool DeleteNode(LNode *p){if(p==NULL)return false;LNode *q=p->next;//令q指向*p的后继结点p->data=q->data;//用后继结点的数据域覆盖自己的p->next=q->next;//将*q结点从链中“断开”free(q);//释放后继结点的存储空间return true;} 尾插法建立单链表

王道版：

typedef struct LNode{//定义单链表结点类型ElemType data;//每个结点存放一个数据元素struct LNode *next; //指针指向下一个结点}LNode,*LinkList;LinkList List_TailInsert(LinkList &L){//正向建立单链表int x;//设ElemType为整型L=(LinkList)malloc(sizeof(LNode));//建立头结点L->next=NULL;//初始为空链表LNode *s,*r=L;//s总是指向最新生成的结点，r为表尾指针scanf("%d",&x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode *)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;//r指向新的表尾结点scanf("%d",&x);}r->next=NULL;//尾结点指针置空return L;}

学校版：把数组内的数存入链表

#include #include struct create_list_vi{int* next;int data;}/*create_list_v1:用循环方式建立先进先出链表*headp将指针p所指的整数依次存放到链表的每个节点*/void create_list_v1(struct s_list **headp,int *p){struct s_list *loc_head=NULL,*tail;if(p[0]==0); /*相当于*p==0 */else{loc_head=(struct s_list *)malloc(sizeof(struct s_list));loc_head->data=*p++;/*把数组内的数提取出来，存在链表内*/tail=loc_head;while(*p){/*tail所指结点的指针域指向动态创建的结点*/tail->next=(struct s_list *)malloc(sizeof(struct s_list));tail=tail->next;/*tail指向新创建的结点*/tail->data=*p++;/*向新创建的结点的数据域赋值*/}tail->next=NULL; /*对指针域赋NULL值*/}*headp=loc_head;/*使头指针headp指向新创建的链表*/}void main(void){struct s_list *head=NULL,*p;int s[]={1,2,3,4,5,6,7,8,0}; /*0为结束标记*/create_list_vi(&head,s); /*创建新链表*/print_list(head); /*输出链表结点中的数据*/} 头插法建立单链表

这种方法可以将链表逆置，为常考点

思路：每个新的结点都插在头结点之后

LinkList HeadInsert(LinkList &L){//逆向建立单链表LNode *s;int x;L=(LinkList)malloc(sizeof(LNode));//创建头结点L->next=NULL;//初始为空链表scanf("%d",&x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode *)malloc(sizeof(LNode));//创建新结点s->data=x;s->next=L->next;L->next=s;//将新结点插入表中，L为头指针scanf("%d",&x);}return L;} 双链表初始化 typedef struct DNode{ElemType data;struct DNode *prior,*next;}DNode,*DLinklist;bool InitDLinkList(DLinklist &L){L = (DNode *)malloc(sizeof(DNode));//分配一个头结点if(L==NULL)return false;//内存不足，分配失败L->prior = NULL;//头结点的prior永远指向NULLL->next = NULL;//头结点之后暂时还无结点return true;} 双链表插入

双链表的插入略微比单链表的插入复杂，要明白它插入的过程：

指定位置插入结点的代码（可以结合按位序）：

bool InsertNextDNode(DNode *p,DNode *s){if(p==NULL||s==NULL)return false;//非法参数s->next=p->next;if(p->next!==NULL)//如果p结点有后继节点p->next->prior=s;s->prior=p;//修改指针时要注意顺序p->next=s;} 双链表删除 //删除p结点的后继结点bool DeleteNextDNode(DNode *p){if(p==NULL)return false;DNode *q=p->next;//找到p的后继结点qif(q==NULL)return false;//p没有后继p->next=q->next;if(q->next!=NULL)//q结点不是最后一个结点q->next->prior=p;//释放结点空间free(q);//释放结点空间return true;}//循环释放各个数据结点void DestoryList(DLinklist &L){while(L->next!=NULL)DeleteNextDNode(L);free(L);//释放头结点L=NULL;//头指针指向NULL} 双链表遍历

遍历的目的是对结点p做相应处理，如打印

//后向遍历while(p!=NULL){p=p->next;}//前向遍历while(p!=NULL){p=p->prior;}//前向遍历（跳过头结点）while(p->prior!=NULL){p=p->prior;} 循环链表循环单链表

在初始化时，头指针指向自己（普通单链表指向NULL）

L->next = L;

//判断结点p是否为循环单链表的表尾结点bool isTail(LinkList L,LNode *p){if(p->next==L)return true;elsereturn false;}//判断循环单链表是否为空bool Empty(LinkList L){if(L->next==L)return true;else return false;}

循环链表的好处：很多时候对链表的操作都是在头部或尾部，可以让L指向表尾元素，降低时间复杂度。（暂时没有这部分代码）

循环双链表

在初始化时，头结点的prior和next都指向自己。

L->prior = L;L->next = L;

//判断结点p是否为循环双链表的表尾结点bool isTail(DLinklist L,DNode *p){if(p->next==L)return true;elsereturn false;}//判断循环双链表是否为空bool Empty(DLinklist L){if(L->next == L)return true;else return false;}