数据结构学习笔记

No.No.PAGE100/100数据结构学习笔记一、绪论数据结构的符号的总称。数据元素：数据的基本单位，一个数据元素可由若干数据项组成。数据项：数据的不可分割的最小单位。数据对象：性质相同的数据元素的集合，是数据的一个子集。对数据的运算。（数据元素都不是孤立存在的）。抽象数据类型（ADT）：特性，用一个三元组表示（D,S,P）。数据类型：是程序设计语言中的一个概念，它是一个值的集合和操作的集合。逻辑结构分为四类结构：集合：结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构：结构中的数据元素之间存在一对一的关系。树型结构：结构中的数据元素之间存在一对多的关系。图状结构（网状结构）：结构中的数据元素之间存在多对多的关系。存储结构系的表示，通常由四种基本的存储方法实现：的逻辑关系，存储密度大。有些操作（如插入、删除）效率较差。链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），且不能折半查找。表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间键字随机存取，不能顺序存取，也不能折半存取。算法算法的基本概念作。算法的特性：有穷性、确定性、可行性、输入、输出。算法的设计目标：正确性，可读性，健壮性，高效率与低存储量需求。算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法的时间复杂度如何计算：找到一个基本操作（最深层循环)分析该基本操作的执行次数x与问题规模n的关系x的数量级就是算法时间复杂度：常用技巧：加法规则：乘法规则：“常对幂指阶”三种复杂度：最坏时间复杂度：考虑输入数据“最坏”的情况。平均时间复杂度：考虑所有输入数据都等概率出现的情况。最好时间复杂度：考虑输入数据“最好”的情况。算法的性能问题只有在n很大时才会暴露出来算法的空间复杂度普通程序：找到所占空间大小与问题规模相关的变量xn的关系x的数量级就是算法空间复杂度递归程序：找到递归调用的深度x与问题规模n的关系x的数量级就是算法空间复杂度二、线性表线性表的定义和操作线性表的基本概念线性表：是具有相同n个数据元素的有限序列。特点：存在唯一的第一个元素。除第一个元素之外，每个元素均只有一个直接前驱。线性表的存储结构：顺序存储结构：顺序表链式存储结构：链表线性表的基本操作InitList(&L)L，并分配内存空间。DestroyList(&L)L占用的内存空间。ListInsert(&L,i,&e)Lie。ListDelete(&L,i,&e)Lie值。LocateElem(L,e)L中查找具有给定元素值的元素。GetElem(L,i)Li个位置的元素的值。Length(L)L的长度，即表中元素的个数。PrintList(L)L的所有元素值。Empty(L)Ltruefalse。操作数据结构的思路：创销、增删改查顺序表顺序表的基本概念顺序表：用顺序存储上。特点：随机访问，即可以在 时间内找到第i个元素。存储密度高，每个节点只存储数据元素。拓展容量不方便（要把数据复制到新的区域）。插入删除操作不方便，需移动大量元素：顺序表的实现静态实现：1#defineMaxSize10//定义最大长度23typedefstruct{4intdata[MaxSize];//使用静态的数组存放数据元素5intlength;//顺序表的当前长度6 7//初始化顺序表voidInitList(SqList&L){L.length=0;//顺序表初始长度为11 }12intmain(){SqListL//声明一个顺序表InitList(L//初始化顺序表return17 }动态实现：1 #defineInitSize10//顺序表的初始长度2typedefstruct{int*data//声明动态分配数组的指针intMaxSize//顺序表的最大容量intlength//顺序表的当前长度8//初始化顺序表voidInitList(SeqList&L){//用malloc函数申请一片连续的存储空间L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=15 }16//增加动态数组的长度voidIncreaseSize(SeqList&L,intlen){int*p=L.data;L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));for(inti=0;i<L.length;i++)L.data[ip[i//将数据复制到新区域L.MaxSizeL.MaxSizelen//顺序表最大长度增加lenfree(p//释放原来的内存空间25 }26intmain(){SeqListL//声明一个顺序表InitList(L//初始化顺序表30 ...IncreaseSize(L,len);return33 }malloc()针。顺序表的基本操作插入：1#defineMaxSize10//定义最大长度23typedefstruct{4intdata[MaxSize];//用静态的数组存放数据元素5intlength;//顺序表的当前长度6 7//在顺序表i位置插入eboolListInsert(SqList&L,inti,inte){if(i1||iL.length+1//判断i的范围是否有效returnfalse;if(L.lengthMaxSize//判断存储空间是否已满returnfalse;for(intjL.lengthjij--//将第i个元素之后的元素后移L.data[j]=L.data[j-1];L.data[i-1e//在位置i处放入eL.length++//长度+1return19 }20intmain(){SqListL;InitList(L);242526

ListInsert(L,3,3);return0;时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：删除：1#defineMaxSize1023typedefstruct{4intdata[MaxSize];5intlength;6 }7//删除顺序表i位置的数据并存入eboolListDelete(SqList&L,inti,int&e){if(i1||iL.length//判断i的范围是否有效returnfalse;eL.data[i-1//将被删除的元素赋值给efor(intjijL.lengthj++//将第i个位置后的元素前移L.data[j-1]=L.data[j];L.length--;return17 }18intmain(){SqListL;InitList(L);inte=-1;if(ListDelete(L,3,e))printf("已删除第3个元素，删除元素值为%d\n"e);25else26printf("位序i不合法，删除失败\n");27return0;28}时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：按位查找：//静态分配的按位查找#defineMaxSize3typedefstruct{ElemTypedata[MaxSize];intlength;89 ElemTypeGetElem(SqListL,inti){10 returnL.data[i-1];11 }1//动态分配的按位查找2#defineInitSize1034typedefstruct{5ElemType*data;6intMaxSize;7intlength;8}SeqList;910ElemTypeGetElem(SeqListL,inti){11returnL.data[i-1];12}时间复杂度：按值查找：1 #defineInitSize2typedefstruct{ElemType*data;intMaxSize;intlength;8//查找第一个元素值为e的元素，并返回其位序intLocateElem(SqListL,ElemTypee){for(inti=0;i<L.length;i++){if(L.data[i]==e)returni+1;//数组下标为i的元素值等于e，返回其位序14 }15 return0//没有查找到16 }在《数据结构》考研初试中，手写代码可以直接用“==”ElemType时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：链表单链表的基本概念单链表：用链式存储针表示。特点：优点：不要求大片连续空间，改变容量方便。缺点：不可随机存取，要耗费一定空间存放指针。两种实现方式：带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。表和非空表的处理需要用不同的代码逻辑。单链表的实现不带头结点的单链表：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//初始化一个空的单链表boolInitList(LinkList&L){LNULL//空表，暂时还没有任何结点return10 }11voidtest(){LinkListL; //声明一个指向单链表的头指针//初始化一个空表InitList(L);16 ...17 }18//判断单链表是否为空boolEmpty(LinkListL){return22 }带头结点的单链表：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//初始化一个单链表（带头结点）boolInitList(LinkList&L){L(LNode*)malloc(sizeof(LNode)); //分配一个头结点if(LNULL) //内存不足，分配失败returnfalse;L->nextNULL; //头结点之后暂时还没有结点return13 }14voidtest(){LinkListL; //声明一个指向单链表的头指针//初始化一个空表InitList(L);19 ...20 }21//判断单链表是否为空boolEmpty(LinkListL){if(L->next==NULL)returntrue;elsereturn28 }单链表的插入按位序插入（带头结点）：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在第i个位置插入元素eboolListInsert(LinkList&L,inti,ElemType8 if(i<1)9 returnFalse;LNode*p; //指针p指向当前扫描到的结点intj=0; //当前p指向的是第几个结点pL; //循环找到第i-1个结点while(p!=NULL&&j<i-1){ //如果i>lenghp最后会等于NULLp=p->next;15 j++;16 }//p值为NULL说明i值不合法if(p==NULL)returnfalse;//在第i-1个结点后插入新结点LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//将结点s连到p后return27 }时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：按位序插入（不带头结点）：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在第i个位置插入元素eboolListInsert(LinkList&L,inti,ElemTypee){//判断i的合法性9 if(i<1)returnfalse;//需要判断插入的位置是否是第1个12if(i==1){13LNode*s=(LNode*)malloc(sizeof(LNode));14s->data=e;15s->next=L;16L=s; //头指针指向新结点17returntrue;18}19//i>1的情况与带头结点一样，唯一区别是j的初始值为120LNode*p; //指针p指向当前扫描到的结点21intj=1; //当前p指向的是第几个结点22p=L;23//循环找到第i-1个结点24while(p!=NULL&&j<i-1){ //如果i>lenghp最后会等于NULL25p=p->next;26j++;27}28//p值为NULL说明i值不合法29if(p==NULL)30returnfalse;31//在第i-1个结点后插入新结点32LNode*s=(LNode*)malloc(sizeof(LNode));33s->data=e;34s->next=p->next;35p->next=s;36returntrue;37}时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：除非特别声明，否则之后的代码都默认为带头结点！指定结点的后插操作：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在结点p后插入元素eboolInsertNextNode(LNode*p,ElemTypee){if(p==NULL){return10 }LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL)returnfalse;s->data=e;s->next=p->next;p->next=s;return18 }19//按位序插入的函数中可以直接调用后插操作boolListInsert(LinkList&L,inti,ElemType22 if(i<1)returnFalse;LNode*p;25//指针p指向当前扫描到的结点26intj=0;27//当前p指向的是第几个结点28p=L;29//循环找到第i-1个结点30while(p!=NULL&&j<i-1){31//如果i>lengh,p最后会等于NULL32p=p->next;33j++;34}35returnInsertNextNode(p,e)36}时间复杂度：指定结点的前插操作：如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对q进行后插操作；如果不传入头指针，可以在指定结点p后插入一个结点s，并交换两个结点所保存的数据，从而变相实现指定结点的前插操作。typedefstructLNode{ElemTypedata;structLNode*next;}LNode,5//在结点p前插入元素eboolInsertPriorNode(LNode*p,ElemTypee){returnfalse;LNode*s=(LNode*)malloc(sizeof(LNode));//内存不足分配失败returnfalse;//将s插入结点p之后s->next=p->next;p->next=s;//交换两个结点中的数据s->data=p->data;p->data=e;return21 }时间复杂度：单链表的删除按位序删除：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,4//删除第i个结点并将其所保存的数据存入eboolListDelete(LinkList&L,inti,ElemType&e){7 if(i<1)returnfalse;LNode*p; //指针p指向当前扫描到的结点intj=0; //当前p指向的是第几个结点p=L;12//循环找到第i-1个结点13while(p!=NULL&&j<i-1){14//如果i>lengh，p和p的后继结点会等于NULL15p=p->next;16j++;17}18if(p==NULL)19returnfalse;20if(p->next==NULL)21returnfalse;22//令q暂时保存被删除的结点23LNode*q=p->next;24e=q->data;25p->next=q->next;26free(q)27returntrue;28}时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：删除指定结点：如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对p进行删除操作；如果不传入头指针，可以把指定结点p的后继结点q删除，并使结点p保存结点q存储的数据，从而变相实现删除指定结点的操作。但是如果指定结点p没有后继结点，这么做会报错。//删除指定结点pboolDeleteNode(LNode*p){if(p==NULL)returnfalse;LNode*qp->next//令q指向p的后继结点//如果p是最后一个结点，则q指向NULL，继续执行就会报错p->data=q->data;p->next=q->next;free(q);return11 }时间复杂度：单链表的查找按位查找：1typedefstructLNode{2ElemTypedata;3structLNode*next;4}LNode,*LinkList;56//查找指定位序i的结点并返回7LNode*GetElem(LinkListL,inti){8if(i<0)9returnNULL;10LNode*p;11intj=0;12131415161718 19

p=L;while(p!=NULL&&j<i){p=p->next;j++;}returnp;//封装后的插入操作，在第i个位置插入元素e，可以调用查询操作和后插操作boolListInsert(LinkList&L,inti,ElemType22 if(i<1)returnFalse;//找到第i-1个元素LNode*p=GetElem(L,i-1);//在p结点后插入元素ereturnInsertNextNode(p,28 }时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：按值查找：//查找数据域为e的结点指针，否则返回NULLLNode*LocateElem(LinkListL,ElemTypee){LNode*P=L->next;//从第一个结点开始查找数据域为e的结点while(p!=NULL&&p->data!=e){p=7 }8 return9 }时间复杂度：最好时间复杂度：最坏时间复杂度：平均时间复杂度：计算单链表长度：//计算单链表的长度intLength(LinkListL){intlen=0; //统计表长LNode*p=L;while(p->next!=NULL){p=p->next;len++;8 }9 return10 }时间复杂度：单链表的建立尾插法建立单链表：//使用尾插法建立单链表LLinkListList_TailInsert(LinkList&L){intx; //设ElemType为整型intL(LinkList)malloc(sizeof(LNode)); //建立头结点(初始化空表)LNode*s,*rL; //r为表尾指针scanf("%d"&x); //输入要插入的结点的值7 while(x!=9999){ //输入9999表示结束s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;rs; //r指针指向新的表尾结点12 scanf("%d",&x);13}1413}14r->next=NULL;15returnL;16}时间复杂度：头插法建立单链表：1LinkListList_HeadInsert(LinkList&L){//逆向建立单链表2LNode*s;3intx;4L=(LinkList)malloc(sizeof(LNode));//建立头结点5L->next=NULL;6scanf("%d",&x);//输入要插入的结点的值7while(x!=9999){//输入9999表结束8s=(LNode*)malloc(sizeof(LNode));9s->data=x;10s->next=L->next;11L->next=s;12//将新结点插入表中，L为头指针13scanf("%d",&x);14}15returnL;16}头插法实现链表的逆置：//将链表L中的数据逆置并返回LNode*Inverse(LNode*L){LNode*p,*q;pL->next; //p指针指向第一个结点L->nextNULL; //头结点置空//依次判断p结点中的数据并采用头插法插到L链表中while(p!=8 q=p;p=p->next;q->next=L->next;L->next=12 }13 return14 }具体解释详见\h【数据结构】单链表逆置：头插法图解双链表双链表的定义：点和后继结点。双链表的实现：typedefstructDNode{ //定义双链表结点类型ElemTypedata; //数据域structDNode*prior*next; //前驱和后继指针}DNode,*DLinklist;(带头结点)：typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode,5//初始化双链表boolInitDLinkList(Dlinklist&L){L=(DNode*)malloc(sizeof(DNode));if(L==NULL)returnfalse;L->priorNULL; //头结点的prior指针永远指向NULLL->nextNULL; //头结点之后暂时还没有结点，置空return14 }15voidtestDLinkList(){DLinklistL;InitDLinkList(L);19 ...20 }21//判断双链表是否为空boolEmpty(DLinklistL){if(L->next==NULL)returntrue;elsereturn28 }双链表的后插操作：typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode,5//将结点s插入到结点p之后boolInsertNextDNode(DNode*p,DNode*s){if(p==NULL||s==NULL)returnfalse;s->next=p->next;//判断结点p之后是否有后继结点if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return17 }双链表的前插操作、按位序插入操作都可以转换成后插操作双链表的删除操作：//删除p结点的后继结点boolDeletNextDNode(DNode*p){returnfalse;//找到p的后继结点qDNode*q=p->next;returnfalse;p->next=q->next;if(q->next!=NULL)q->next->prior=p;free(q);return14 }15//销毁一个双链表boolDestoryList(DLinklist&L){//循环释放各个数据结点while(L->next!=NULL){DeletNextDNode(L);free(L);//头指针置空24 }25 }双链表的遍历：//向后遍历while(p!=NULL){//对结点p做相应处理p=5 }6//向前遍历while(p!=NULL){//对结点p做相应处理p=11 }12//跳过头结点的遍历while(p->prior!=NULL){151617

//对结点p做相应处理p=p->prior;双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。循环链表循环链表的定义：指向头结点，整个链表形成一个环。循环单链表的实现：typedefstructLNode{ElemTypedata;structLNode*next;}DNode,5//初始化循环单链表boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));if(L==NULL)returnfalse;//最后一个结点的next指针指向头结点L->next=L;return14 }15//判断循环单链表是否为空boolEmpty(LinkListL){if(L->next==L)returntrue;else2122 23

returnfalse;//判断结点p是否为循环单链表的表尾结点boolisTail(LinkListL,LNode*p){if(p->next==L)returntrue;elsereturn30 }循环双链表的实现：typedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode,5//初始循环双链表boolInitDLinkList(DLinklist&L){L=(DNode*)malloc(sizeof(DNode));if(L==NULL)returnfalse;//头结点的prior指针指向最后一个结点，最后一个结点的next指针指向头结点L->prior=L;L->next=14 }15//判断循环双链表是否为空boolEmpty(DLinklistL){if(L->next==L)returntrue;elsereturn22 }23//判断结点p是否为循环双链表的表尾结点boolisTail(DLinklistL,DNode*p){if(p->next==L)returntrue;elsereturn30 }循环双链表的插入和删除操作：//将结点s插入到结点p之后boolInsertNextDNode(DNode*p,DNode*s){s->next=p->next;//循环双链表不用担心p结点的下一个结点为空p->next->prior=s;s->prior=p;p->next=8 }9//删除p结点的后继结点boolDeletNextDNode(DNode*p){//找到p的后继结点qDNode*q=p->next;//循环双链表不用担心q结点的下一个结点为空p->next=q->next;q->next->prior=p;171819

free(q);returntrue;静态链表静态链表的定义个结点包括了数据元素和下一个结点的数组下标。特点：优点：增、删操作不需要大量移动元素。缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！静态链表的定义：#defineMaxSize10 //静态链表的最大长度structNode{ //静态链表结构类型的定义ElemTypedata; //存储数据元素intnext; //下一个元素的数组下标5 };6//用数组定义多个连续存放的结点voidtestSLinkList(){structNodea[MaxSize]; //数组a作为静态链表每一个数组元素的类型都是structNode10 ...11 }也可以这么定义：#defineMaxSize10 //静态链表的最大长度typedefstruct{ //静态链表结构类型的定义ELemTypedata; //存储数据元素intnext; //下一个元素的数组下标6voidtestSLinkList(){SLinkList9 }第一种是我们更加熟悉的写法，第二种写法则更加侧重于强调a是一个静态链表而非数组。静态链表的注意点：初始化静态链表时，需要把a[0]的next设为-1，并将空闲结点的next设置为某个特殊值，比如-2。按位序查找结点时，从头结点出发挨个往后遍历结点，时间复杂度 。1的结点；③修改新结点的next-1i-1号结点的next为新结点的下标；顺序表和链表的比较逻辑结构：顺序表和链表都属于线性表，都是线性结构。存储结构：顺序表：顺序存储优点：支持随机存取，存储密度高。缺点：大片连续空间分配不方便，改变容量不方便。链表：链式存储优点：离散的小空间分配方便，改变容量方便。缺点：不可随机存取，存储密度低。-创建：顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。静态分配：静态数组，容量不可改变。动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（使用malloc()、free()）。链表：只需要分配一个头结点或者只声明一个头指针。-销毁：Length=0静态分配：静态数组——系统自动回收空间。动态分配：动态数组——需要手动free()。链表：依次删除各个结点free()。-增/删：顺序表：插入/删除元素要将后续元素后移/前移；时间复杂度：，时间开销主要来自于移动元素。链表：插入/删除元素只需要修改指针；时间复杂度：，时间开销主要来自查找目标元素。-查找：顺序表按位查找：按值查找： ，若表内元素有序，可在时间内找到（二分法）链表：按位查找：按值查找：三、栈与队列栈栈的基本概念栈是特殊的线性表：只允许在一端进行插入或删除操作，其逻辑结构与普通线性表相同。（最上面的为顶元素）。（最下面的为空栈：不含任何元素的空表。

底元素）。特点：后进先出（后进栈的元素先出栈）——LIFO（LastInFirstOut）。缺点：栈的大小不可变，解决方法：共享栈。栈的基本操作InitStack(&S)S，分配内存空间。DestroyStack(&S)S所占用的内存空间。Push(&S,x)Sx加入使其成为新的栈顶元素。Pop(&S,&x)S非空，则弹出（删除）x返回。GetTop(S,&x)Sx返回栈顶元素。StackEmpty(S)SStruefalse。栈的顺序存储实现顺序栈的定义：#defineMaxSize10 //定义栈中元素的最大个数typedefstruct{ElemTypedata[MaxSize]; //静态数组存放栈中元素inttop; //栈顶元素6voidtestStack(){SqStackS; //声明一个顺序栈(分配空间9 }顺序栈的初始化：#defineMaxSize10typedefstruct{ElemTypedata[MaxSize];inttop;6//初始化栈voidInitStack(SqStack&S){910 11

S.top1; //初始化栈顶指针//判断栈是否为空boolStackEmpty(SqStack14 if(S.top==-1)returntrue;elsereturn18 }入栈出栈：1//新元素进栈2boolPush(SqStack&S,ElemTypex){//判断栈是否已满3if(S.top==MaxSize-1)4returnfalse;5S.data[++S.top]=x;6returntrue;7}89//出栈10boolPop(SqStack&x,ElemType&x){//判断栈是否为空11if(S.top==-1)12returnfalse;13x=S.data[S.top--];14returntrue;15}读取栈顶元素：//读栈顶元素boolGetTop(SqStackS,ElemType3 if(S.top==-1)returnfalse;x=S.data[S.top];return7 }共享栈（两个栈共享同一片空间）：12#defineMaxSize10 //定义栈中元素的最大个数typedefstruct{3ElemTypedata[MaxSize];//静态数组存放栈中元素4inttop0;//0号栈栈顶指针5inttop1;//1号栈栈顶指针6}ShStack;78//初始化栈9voidInitSqStack(ShStack&S){10S.top0=-1;11S.top1=MaxSize;12}栈的链式存储实现链栈的定义：1typedefstructLinknode{2ElemTypedata;//数据域3Linknode*next;//指针域4}Linknode,*LiStack;56voidtestStack(){LiStackL; //声明一个链栈8 }链栈的初始化：typedefstructLinknode{ElemTypedata;Linknode*next;}Linknode,5//初始化栈boolInitStack(LiStack&L){L=(Linknode*)malloc(sizeof(Linknode));if(L==NULL)returnfalse;L->next=NULL;return13 }14//判断栈是否为空boolisEmpty(LiStack&L){if(L->next==NULL)returntrue;elsereturn21 }入栈出栈：//新元素入栈boolpushStack(LiStack&L,ElemTypex){Linknode*s=(Linknode*)malloc(sizeof(Linknode));if(s==NULL)returnfalse;s->data=x;//头插法s->next=L->next;L->next=s;return11 }12//出栈boolpopStack(LiStack&L,int&x){//栈空不能出栈if(L->next==NULL)returnfalse;Linknode*s=L->next;x=s->data;L->next=s->next;free(s);return23 }队列队列的基本概念队列是操作受限的线性表：(入队)(出队)。队头：允许删除的一端。队尾：允许插入的一端。空队列：不含任何元素的空表。特点：先进先出（先入队的元素先出队）——FIFO（FirstInFirstOut）。队列的基本操作InitQueue(&Q)Q。DestroyQueue(&Q)Q所占用的内存空间。EnQueue(&Q,x)Qx加入，使之成为新的队尾。DeQueue(&Q,&x)Qx返回。GetHead(Q,&x)Qx。QueueEmpty(Q)Qtrue。队列的顺序存储实现顺序队列的定义：1 #defineMaxSize10; //定义队列中元素的最大个数2typedefstruct{ElemTypedata[MaxSize]; //用静态数组存放队列元素5intfront,rear;//队头指针和队尾指针6}SqQueue;78voidtest{9SqQueueQ;//声明一个队列10}顺序队列的初始化：1 #defineMaxSize2typedefstruct{ElemTypedata[MaxSize];intfront,rear;7//初始化队列voidInitQueue(SqQueue&Q){//初始化时，队头、队尾指针指向0//队尾指针指向的是即将插入数据的数组下标//队头指针指向的是队头元素的数组下标Q.front=Q.rear=14 }15//判断队列是否为空boolQueueEmpty(SqQueueQ){if(Q.front==Q.rear)returntrue;elsereturn22 }入队出队（循环队列）：//新元素入队boolEnQueue(SqQueue&Q,ElemTypex){//如果队列已满直接返回if((Q.rear+1)%MaxSizeQ.front) //牺牲一个单元区分队空和队满returnfalse;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return9 }10//出队boolDeQueue(SqQueue&Q,ElemType&x){//如果队列为空直接返回if(Q.rear==Q.front)returnfalse;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return19 }获得队头元素：//获取队头元素并存入xboolGetHead(SqQueue&Q,ElemType&x){if(Q.rear==Q.front)returnfalse;x=Q.data[Q.front];return7 }注意：

环队列不能使用Q.rear==Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize==Q.front作为判断队列是否已满的条件。（主流方法）解决方法二：设置size变量记录队列长度。1 #defineMaxSize2typedefstruct{ElemTypedata[MaxSize];intfront,rear;6intsize;7}SqQueue;89//初始化队列10voidInitQueue(SqQueue&Q){11Q.rear=Q.front=0;12Q.size=0;13}1415//判断队列是否为空16boolQueueEmpty(SqQueue0){17if(Q.size==0)18returntrue;19else20returnfalse;21}2223//新元素入队24boolEnQueue(SqQueue&Q,ElemTypex){25if(Q.size==MaxSize)26returnfalse;27Q.size++;28Q.data[Q.rear]=x;29Q.rear=(Q.rear+1)%MaxSize;30returntrue;31}3233//出队34boolDeQueue(SqQueue&Q,ElemType&x){35if(Q.size==0)36returnfalse;37Q.size--;38x=Q.data[Q.front];39Q.front=(Q.front+1)%MaxSize;40returntrue;41}解决方法三tag变量记录队列最近的操作。（tag=0：最近进行的是删除操作；tag=1近进行的是插入操作）1 #defineMaxSize2typedefstruct{ElemTypedata[MaxSize];intfront,rear;inttag;8//初始化队列voidInitQueue(SqQueue&Q){Q.rear=Q.front=0;Q.tag=13 }14//判断队列是否为空boolQueueEmpty(SqQueue0){if(Q.front==Q.rear&&Q.tag==0)returntrue;elsereturn21 }22//新元素入队boolEnQueue(SqQueue&Q,ElemTypex){if(Q.rear==Q.front&&tag==1)returnfalse;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1;return31 }32//出队boolDeQueue(SqQueue&Q,ElemType&x){if(Q.rear==Q.front&&tag==0)returnfalse;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;Q.tag=0;return41 }队列的链式存储实现链队列的定义：//链式队列结点typedefstructLinkNode{ElemTypedata;structLinkNode*next;6//链式队列typedefstruct{//头指针和尾指针LinkNode*front,*rear;}*LinkQueue;链队列的初始化（带头结点）：typedefstructLinkNode{ElemTypedata;structLinkNode*next;5typedefstruct{LinkNode*front,*rear;9//初始化队列voidInitQueue(LinkQueue&Q){//初始化时，front、rear都指向头结点Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=15 }16//判断队列是否为空boolIsEmpty(LinkQueueQ){if(Q.front==Q.rear)returntrue;elsereturn23 }入队出队：//新元素入队voidEnQueue(LinkQueue&Q,ElemTypex){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=8 }9//队头元素出队boolDeQueue(LinkQueue&Q,ElemType&x){if(Q.front==Q.rear)returnfalse;LinkNode*p=Q.front->next;x=p->data;Q.front->next=p->next;//如果p是最后一个结点，则将队头指针也指向NULLif(Q.rear==p)Q.rear=Q.front;free(p);return22 }以上是带头结点的链队列，下面是不带头结点的操作：typedefstructLinkNode{ElemTypedata;structLinkNode*next;5typedefstruct{LinkNode*front,*rear;9//初始化队列voidInitQueue(LinkQueue&Q){12//不带头结点的链队列初始化，头指针和尾指针都指向NULL13Q.front=NULL;14Q.rear=NULL;15}16//判断队列是否为空boolIsEmpty(LinkQueueQ){if(Q.front==NULL)returntrue;elsereturn23 }24//新元素入队voidEnQueue(LinkQueue&Q,ElemTypex){LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;//第一个元素入队时需要特别处理if(Q.front==NULL){Q.front=s;Q.rear=s;}else{Q.rear->next=s;Q.rear=37 }38 }39//队头元素出队boolDeQueue(LinkQueue&Q,ElemType&x){if(Q.front==NULL)returnfalse;LinkNode*s=Q.front;x=s->data;if(Q.front==Q.rear){Q.front=Q.rear=NULL;}else{Q.front=Q.front->next;50 }free(s);return53 }双端队列定义：双端队列是允许从两端插入、两端删除的线性表。如果只使用其中一端的插入、删除操作，则等同于栈。两端插入，一端删除一端插入，两端删除两端插入，一端删除一端插入，两端删除输出受限的双端队列：允许考点：判断输出序列的合法化

的线性表。的线性表。例：数据元素输入序列为1，2，3，4，判断4!=24个输出序列的合法性栈中合法的序列，双端队列中一定也合法栈输入受限的双端队列输出受限的双端队列14个合法() 42134231不合法只有4132和4231不合法栈与队列的应用栈在括号匹配中的应用用栈实现括号匹配：（栈的特性——LIFO）。遇到左括号就入栈。遇到右括号，就“消耗”一个左括号（出栈）。匹配失败情况：扫描到右括号且栈空，则该右括号单身。扫描完所有括号后，栈非空，则该左括号单身。左右括号不匹配。开始开始no栈空？yesno还有未处理的括号？yesa是左括号？yesnoyes栈空？nob与a匹配？yesno结束匹配失败匹配成功弹出栈顶元素b扫描下一个括号aa压入栈顶#defineMaxSize10typedefstruct{chardata[MaxSize];inttop;6voidInitStack(SqStack&S);boolStackEmpty(SqStack&S);boolPush(SqStack&S,charx);boolPop(SqStack&S,char11//判断长度为length的字符串str中的括号是否匹配boolbracketCheck(charstr[],intlength){SqStackS;InitStack(S);//遍历strfor(inti=0;i<length;i++){//扫描到左括号，入栈19 if(str[i]=='('||str[i]=='['||str[i]=='{'){Push(S,str[i]);}else{//扫描到右括号且栈空直接返回if(StackEmpty(S))returnfalse;chartopElem;//用topElem接收栈顶元素Pop(S,topElem);//括号不匹配29 if(str[i]==')'&&topElem!='(')30 returnfalse;31 if(str[i]==']'&&topElem!='[')32 returnfalse;33 if(str[i]=='}'&&topElem!='{')34 returnfalse; }35}36//扫描完毕若栈空则说明字符串str中括号匹配37returnStackEmpty(S);38}栈在表达式求值中的应用转换为前缀或后缀表达式，然后再进行求值。前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。中缀转后缀的手算方法：确定中缀表达式中各个运算符的运算顺序。选择下一个运算符，按照的方式组合成一个新的操作数。如果还有运算符没被处理，就继续执行。例：将 转换为后缀表达式？答：中缀转后缀要遵循“左优先”原则：只要左边的运算符能先计算，就优先计算左边的。后缀表达式的手算方法：例：计算 ?答：后缀表达式的机算方法：从左往右扫描下一个元素，直到处理完所有元素。若扫描到操作数则压入栈，并回到第一步；否则执行第三步。若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步。弹出栈顶元素时，先出栈的是“右操作数”。开始开始结束no还有未处理的元素？yesa是操作数？yesa压入栈顶no弹出两个栈顶元素并执行相应的计算，得到结果bb压入栈顶扫描下一个元素a中缀转前缀的手算方法：确定中缀表达式中各个运算符的运算顺序。选择下一个运算符，按照的方式组合成一个新的操作数。如果还有运算符没被处理，就继续执行第二步。例：将 转为前缀表达式？答： 中缀转前缀遵循“右优先”原则：只要右边的运算符能先计算，就优先算右边的。前缀表达式的计算方法：从右往左扫描下一个元素，直到处理完所有元素。若扫描到操作数则压入栈，并回到第一步；否则执行第三步。若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步。中缀转后缀的机算方法：理各个元素，直到末尾。可能遇到三种情况：遇到操作数：直接加入后缀表达式。遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。遇到运算符：依次弹出栈中优先级“(”或栈空则停止。之后再把当前运算符入栈。1#defineMaxSize402typedefstruct{3chardata[MaxSize];4inttop;5}SqStack;67typedefstruct{8chardata[MaxSize];9intfront,rear;10}SqQueue;1112voidInitStack(SqStack&S);13boolStackEmpty(SqStackS);14boolPush(SqStack&S,charx);15boolPop(SqStack&S,char&x);16voidInitQueue(SqQueue&Q);17boolEnQueue(LQueue&Q,charx);18boolDeQueue(LQueue&Q,char&x);19boolQueueEmpty(SqQueueQ);2021//判断元素ch是否入栈22intJudgeEnStack(SqStack&S,charch){23chartp=S.data[S->top];24//如果ch是a~z则返回-125if(ch>='a'&&ch<='z')26return-1;27//如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回028elseif(ch=='+'&&(tp=='+'||tp=='-'||tp=='*'||tp=='/'))29return0;30elseif(ch=='-'&&(tp=='+'||tp=='-'||tp=='*'||tp=='/'))31return0;32elseif(ch=='*'&&(tp=='*'||tp=='/'))33return0;34elseif(ch=='/'&&(tp=='*'||tp=='/'))35return0;36//如果ch是右括号则返回237elseif(ch==')')38return2;39//其他情况ch入栈，返回140elsereturn1;41}42//中缀表达式转后缀表达式intmain(intargc,charconst*argv[]){SqStackS;SqQueueQ;InitStack(S);InitQueue(Q);charch;printf("请输入表达式，以“#”结束：");scanf("%c",&ch);52 while(ch!='#'){//当栈为空时if(StackEmpty(&S)){//如果输入的是数即a~z56 if(ch>='a'&&ch<='z')EnQueue(Q,ch);//如果输入的是运算符，直接入栈elsePuch(S,ch);}else{//当栈非空时，判断ch是否需要入栈intn=JudgeEnStack(S,ch);//当输入是数字时直接入队65 if(n==-1){EnQueue(Q,ch);}elseif(n==0){//当输入是运算符且运算符优先级不高于栈顶元素时while(1){//取栈顶元素入队chartp;Pop(S,tp);EnQueue(Q,tp);//再次判断是否需要入栈n=JudgeEnStack(S,ch); //当栈头优先级低于输入运算符或者栈头为‘)’时，入栈并跳出循环77 if(n!=0){EnStack(S,ch);break;80 }81 }}elseif(n==2){//当出现‘)’时将()中间的运算符全部出栈入队while(1){chartp;Pop(S,tp);87 if(tp=='(')break;elseEnQueue(Q,tp);91 }}else{//当运算符优先级高于栈顶元素或出现‘(’时直接入栈Push(S,ch);95 }96 }97 scanf("%c",98 }//将最后栈中剩余的运算符出栈入队while(!StackEmpty(S)){chartp;102Pop(S,tp);103EnQueue(Q,tp);104}105//输出队中元素106while(!QueueEmpety(Q)){107printf("%c",DeQueue(Q));108}109return0;110}中缀表达式的机算方法：+后缀表达式的求值（两个算法的结合）初始化两个栈，（操作数栈和运算符栈），若扫描到操作数，压入操作数栈；若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）。栈在递归中的应用函数调用的特点：最后被调用的函数最先执行结束（LIFO）。函数调用时，需要用一个“函数调用栈”存储：调用返回地址实参局部变量递归调用时，函数调用栈可称为“递归工作栈”顶；每退出一层递归，就从栈顶弹出相应信息。缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算。可以自定义栈将递归算法改造成非递归算法。队列的应用树的层次遍历图的广度优先遍历操作系统中多个进程争抢着使用有限的系统资源时，先来先服务算法（FirstComeFirstService）是一种常用策略。特殊矩阵的压缩存储除非题目特别说明，否则数组下标默认从0开始。一维数组的存储：LOC=LOC+i*sizeof(ElemType)(0≤i<10)二维数组的存储：M行N列的二维数组 中，设起始地址为LOC，若按行优先存储，则 的存地址=LOC+(i*N+j)*sizeof(ElemType)M行N列的二维数组 中，设起始地址为LOC，若按列优先存储，则 的存地址=LOC+(j*M+i)*sizeof(ElemType)对称矩阵的压缩存储：若n阶矩阵中任意一个元素 都有 则该矩阵为对称矩阵。对于对称矩阵，只需存储主对角线+下三角区。若按照行优先原则将各元素存入一维数组中，即 存到数组 中，那么有 ，又 故有：若按照列优先存储，有： 三角矩阵的压缩存储：下三角矩阵：除了主对角线和下三角区，其余的元素都相同。上三角矩阵：除了主对角线和上三角区，其余的元素都相同。压缩存储策略：按行优先原则将主对角线+下三角区存入一维数组中，并在最后一个位置存常量。即 存入到数组 中，那么数组 共有 个元素。对于k，有：三对角矩阵的压缩存储：三对角矩阵，又称带状矩阵：当 时，有中，那么。对于三对角矩阵，按行优先原则，只存储带状部分，即 存入到数组中，那么。若已知数组下标k，则 。稀疏矩阵的压缩存储：稀疏矩阵的非零元素远远少于矩阵元素的个数。压缩存储策略：<行，列，值>链式存储：十字链表法四、串串的基本概念串：即字符串（String）是由零个或多个字符组成的有限序列。串的长度：中字符的个数n， 时的串称为空串。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。字符在主串中的位置：字符在串中的序号。串的基本操作StrAssign(&T,chars)Tchars。StrCopy(&T,S)ST。StrEmpty(S)STRUE。StrLength(S)S中元素的个数。ClearString(&S)S清为空串。DestroyString(&S)S销毁（回收存储空间）。Concat(&T,S1,S2)TS1S2SubString(&Sub,S,pos,len)SubSposlen的子串。Index(S,T)STS0。StrCompare(S,T)S>T，则返回值>0S=T，则返回值=0S<T值<0。串的存储实现串的顺序存储（静态数组）：//ch[0]废弃不用，声明int型变量length来存放串的长度#defineMAXLEN3typedefstruct{charch[MAXLEN];intlength;8//串的初始化boolInitString(SString&S){S.length=0;return13 }14//求串的长度intStrLength(SStringS){return18 }19//求主串由位序pos开始len长度的子串存入到串Sub中boolSubString(SString&Sub,SStringS,intpos,intlen){if(pos+len-1>S.length)returnfalse;for(inti=pos;i<pos+len;i++)Sub.ch[i-pos+1]=S.ch[i];Sub.length=len;return28 }29//比较S与T的大小。若S>T，则返回值大于0S=T，则返回值等于0S<T，则返回值小于0intStrCompare(SStringS,SStringT){for(inti=1;i<=S.length&&i<=T.length;i++){if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i]35 }//扫描过的所有字符都相同，则长度长的串更大returnS.length-T.length;38 }39//定位串T在串S中的位置，若无法定位则返回0intIndex(SStringS,SStringT){inti=1,n=StrLength(S),m=StrLength(T);SStringsub; //用于暂存数据while(i<=n-m+1){SubString(sub,S,i,m);46if(StrCompare(sub,T)!=0)47++i;48else49returni;50}51return0;52}535455565758voidtest{SStringS;InitString(S);...}串的顺序存储（动态数组）：1 #defineMAXLEN2typedefstruct{char*ch;intlength;7boolInitString(HString&S){S.ch=(char*)malloc(MAXLEN*sizeof(char));if(S.ch==NULL)returnfalse;S.length=0;return14 }15voidtest{HStringS;InitString(S);19 ...20 }串的链式存储：typedefstructStringNode{charch; //每个结点存1个字符structStringNode*next;}StringNode,*String;上述方式存储密度很低，可以使每个结点存储多个字符。每个结点被称为块，整个链表被称为块链结构。typedefstructStringNode{charch[4]; //每个结点存多个字符structStringNode*next;}StringNode,*String;串的朴素模式匹配串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在主串中的位置。模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串。串的朴素模式匹配算法代码实现：//在主串S中找到与模式串T相同的子串并返回其位序，否则返回0intIndex(SStringS,SStringT){intk=1;4inti=k,j=1;5while(i<=S.length&&j<=T.length){6if(S.ch[i]==T.ch[j]){7++i;++j;8}else{9k++;i=k;j=1;10}11}12if(j>T.length)13returnk;14else15return0;16}时间复杂度：设模式串长度为m，主串长度为n最坏时间复杂度：KPM算法i间开销增加。最坏时间复杂度。串的前缀：包含第一个字符，且不包含最后一个字符的子串。串的后缀：包含最后一个字符，且不包含第一个字符的子串。nextj个字符匹配失败时，将前（1~j-1）个字符组成的串记为S，则：next[j]=S的最长相等前后缀长度+1。特别地，next[1]=0。例：求模式串“abcabd”的next数组。序号j123456模式串abcabdnext[j]011123KPM算法：当子串和模式串不匹配时，ij=next[j]。KMP算法的平均时间复杂度为：。KPM算法代码实现：//获取模式串T的next[]数组voidgetNext(SStringT,int3 inti=1,j=0;4 next[1]=0;5 while(i<T.length){6 if(j==0||T.ch[1]==T.ch[j]){7 ++i;++j;next[i]=j;}elsej=next[j];11 }12 }13//KPM算法，求主串S中模式串T的位序，没有则返回0intIndex_KPM(SStringS,SString16 inti=1,j=1;intnext[T.length+1];getNext(T,next);while(i<=S.length&&j<=T.length){20if(j==0||S.ch[i]==T.ch[j]){21++i;++j;22}else23j=next[j];24}25if(j>T.length)26returni-T.length;27else28return0;29}3031intmain(){32SStringS={"ababcabcd",9};33SStringT={"bcd",3};34printf("%d",Index_KPM(S,T));//输出935}KPMnext数组：1212voidgetNextval(SStringT,intnextvalinti=1,j=0;3nextval[1]=0;4while(i<T.length){5if(j==0||T.ch[i]==T.ch[j]){6++i;++j;7if(T.ch[i]!=T.ch[j])8nextval[i]=j;9else10nextval[i]=nextval[j];11}else12j=nextval[j];13}14}五、树树的概念树的定义和基本术语树是n（n≥0）个结点的有限集合，n0时，称为空树。空树中应满足：有且仅有一个特定的称为根的结点。当n>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm合本身又是一棵树，并且称为根结点的子树。度：树中一个结点的孩子个数称为该结点的度。所有结点的度的最大值