2022年数据结构知识点整理 .pdf

《2022年数据结构知识点整理 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构知识点整理 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师推荐精心整理学习必备第一章绪论1.数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构)、这些结构在计算机中的表示及其操作的定义和实现问题。2.逻辑结构：不考虑实现，仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构的逻辑结构。通常说的数据结构即此义。分类：如书目表根据一对一相邻关系形成线性结构、棋盘格局间根据下棋规则(一对多)形成一个树形数据结构，城市间据通路(多对多)形成图状结构，此外还有集合结构(除同属一个集合外，无其它关联)，共四类3.数据结构(数据元素及关系/结构)在计算机中的表示或者说映像称为该数据结构的物理结构或存储结构。4.顺序存储结构：关系采

2、取顺序映像表示，即借助元素在存储器中的位置上的”相邻”关系隐式表示数据元素间具有关系。此时物理结构对应一个数组。优点:可根据起始地址随机访问各元素。缺点:需事先分配一足够大空间，且插入删除结点需移动大量数据。链式存储结构：关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。5.度量指标：算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法

3、的效率。6.时间复杂度：频度函数的增长率基本与函数中“关键项”(去掉低次项和常数项)的增长率相同，故可用“关键项”反映算法效率。假设关键项为f(n)，用 T(n)=O(f(n)表示算法时间增长率与f(n)增长率同阶。称O(f(n)为算法的渐近时间复杂度，简称时间复杂度。f(n)的增长率为f(n+1)/f(n)，如对复杂度为O(n)的算法其运行时间随问题规模增长率为 1+1/n,复杂度为 O(1)的算法时间增长率为1。7.按增长率由小至大的顺序排列下列各函数(2/3)n-2100-2n-n1/2-n-n 2n-n3/2-2n-n!-nn第二章线性表1.顺序表：借助元素在存储器中位置上的”相邻”关

4、系表示数据元素间具有的关系，如此存储的线性表称为顺序表。顺序表优点是实现简单方便，可随机访问各元素；缺点是插入或删除元素时会引起大量的数据元素移动(表尾除外)；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常得不到充分利用。2.线性链表:采用链式存储结构的线性表对应一个链表。结点包含数据域和指针域两部分。链表名指向第一个结点(头指针)，尾结点指针域值为NULL。链表优点是空间利用好,插入删除不移动数据,表头表尾操作快(改进的单链表),位置概念强；缺点是需要顺序访问各元素，位序概念弱。顺序表相关程序：#define LIST_INIT_SIZE 100/#define LI

5、STINCREMENT 10/typedef*ElemType;typedef struct ElemType*elem;/存储空间基址int length;/int listsize;/SqList；SqList La,Lb,Lc;Status InitList_Sq(SqList&L)/构造空线性表L L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)if(L.elem=0)exit(OVERFLOW);L.length=0;/初始化表长为0，“空”表L.listsize=LIST_INIT_SIZE;/初始化存储容量retur

6、n(OK);/InitList_Sq void ListDelete(SqList&L,int i,ElemType&e)/在顺序表L中删除第个元素，用返回其值/i 的合法值是 1，ListLength(L)if(iL.length)return ERROR;/删除位置不合理ElemType*p=&L.elemi-1,*q=L.elem+L.length-1;e=*p;while(pq)*p=*(p+1);+p;/删除位置后元素左移-L.length;return Ok;/ListDelete_Sq Status ListInsert_Sq(SqList&L,int i,ElemType e)

7、/在顺序表L 的第 i 个位置前插入元素e,i 的合法值为1.L.length+1 if(iL.length+1)return ERROR;/插入不合法if(L.length=L.listsize)/表满，增加存储容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)if(!newbase)exit(OVERFLOW);名师推荐精心整理学习必备L.elem=newbase;L.listsize+=LISTINCREMENT;ElemType*q=&L.elemi-1,*p=

8、&L.elemL.length-1;while(p=q)*(p+1)=*p;-p;/插入位置后的元素右移*q=e;+L.length;return OK;/ListInsert_S线性表相关程序：typedef*ElemType;typedef struct LNode ElemType data;/数据域struct LNode*next;/指针域LNode,*LinkList;/默认带头结点,需说明LNode node1;LinkList La；Status GetElem_L(LinkList L,int i,ElemType&e)/L 为带头结点的单链表的头指针。第i 个元素存在时,其

9、值赋给 e 并返回 OK,否则返回ERROR LNode*p=L-next;/p 指向”第 1 个”结点，int j=1;/j 为指向结点的位序while(p&jnext;+j;if(!p)return ERROR;/第 i 个元素不存在e=p-data;/取第 i 个元素return OK；Status ListInsert_L(LinkList&L,int i,ElemType e)/向链表 L 中第 i 个位置插入e LNode*p=L;int j=0;/*p 始终指向第j 个结点*/while(p&jnext;+j;/寻找第 i-1 个结点if(!p)return ERROR;LNod

10、e*temp;temp=(LNode*)Malloc(sizeof(LNode);if(!temp)exit(OVERFLOW);temp-data=e;temp-next=p-next;p-next=temp;return(OK);/ListInsert_L Status ListDelete_L(LinkList&L,int i,ElemType&e)LNode*p=L,*q;int j=0;/*p 始终指向第j 个结点*/while(p&jnext;+j;/寻找第 i-1 个结点，j 最终为 i-1,除非到表尾p 空if(!p|!p-next)return ERROR;/第 i 个或更前

11、结点不存在q=p-next;e=q-data;p-next=q-next;free(q);return(OK);/ListDelete_L Status CreateList_L(LinkList&L,int n)/逆位序输入n 个元素的值，建立带头结点的单链表L。LNode*p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(int i=1;idata);p-next=L-next;L-next=p;/插入到表头/CreateList_L 相关两表的归并void MergeList_Sq(SqList La,SqList Lb,Sqlist&

12、Lc)/归并非降顺序表La与 Lb构成非降顺序表Lc Lc.listsize=Lc.length=La.length+Lb.length;Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);If(!Lc.elem)exit(OVERFLOW);/存储分配失败ElemType*pa=La.elem,*pb=Lb.elem,*pc=Lc.elem;ElemType*pa_last=La.elem+La.listsize-1;ElemType*pb_last=Lb.elem+La.listsize-1;while(pa=pa_last&pb=

13、pb_last)/归并if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(papa_last)*pc+=*pa+;/插入 La剩余段while(pbpb_last)*pc+=*pb+;/插入 Lb 剩余段/MergeList_Sq Status ListMerge_SortedL 文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4

14、J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T

15、3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:C

16、W2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 H

17、T4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG

18、5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码

19、:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5

20、 HT4J5O7I6J3 ZG5T3S6Z9Q1名师推荐精心整理学习必备(SortedSqList La,SortedSqList Lb,SortedSqList&Lc)/将两个有序顺序表La与 Lb归并为有序顺序表Lc int la_len=ListLength_Sq(La);int lb_len=ListLength_Sq(Lb);int i=1,j=1,k=1;ElemType a,b;InitList_Sq(Lc);while(i=la_len&j=lb_len)/归并GetElem_Sq(La,i,a);GetElem_Sq(Lb,j,b);if(ab)ListInsert_Sq(L

21、c,k+,a);+i;else ListInsert_Sq(Lc,k+,b);+j;while(i=la_len)/插入 La的剩余元素GetElem_Sq(La,i+,a);ListInsert_Sq(Lc,k+,a);while(j=lb_len)/插入 Lb的剩余元素GetElem_Sq(Lb,j+,b);ListInsert_Sq(Lc,k+,b);return OK;/复杂度O(ListLength(La)+ListLength(Lb),因只在表尾插入)3.注意链表中next 指针的应用，如插入，删除等操作各个元素的链接。4.顺序表的就地逆置思路：分别设两个指针p 与 q 指向第一个

22、和最后一个元素，当pq 时*p 与*q 互换，之后+p,-q。单链表的就地逆置思路：令指针 p 指向首元结点,头结点断开,将 p 所指结点插入到表头后,p 后移,直至p 为空 Status ListInverse_Sq(SqList&L)/顺序表就地逆置ElemType*p,*q;ElemType e;p=L.elem;q=L.elem+L.length-1;while(pnext;L-next=NULL;while(p!=NULL)q=p-next;/令 q 指向 p 的后继结点，以便以后 p后移接下来两句将p 所指向节点插入到头结点后p-next=L-next;L-next=p;p=q;/

23、q 后移 return OK;有序顺序表插入Status ListInsert_SortedSq(SqList&L,ElemType e)/在非降顺序表L 中插入元素e,使得 L中各元素仍然非降。注意插入位置据e 求得/思路：从最后一个元素开始，只要它比待插入元素大就后移。条件不成立时退出循环，将e 插入当前位置后即可。顺序表插入操作莫忘表满的处理。只要是顺序表的插入操作就需要判断是否表满，对于链表则无此要求if(L.length=L.listsize)/表满，增加存储容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTIN

24、CREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;/下面从最后一个元素开始，只要大于e就后移，最后插入当前位置后p=L.elem+L.length-1;while(p=L.elem&*pe)*(p+1)=*p;-p;*(p+1)=e;+L.length;/表长加 1 return OK;5.循环链表、双向链表、双向循环链表的特点和基本操作。主要是插入删除的相关指针操作。/-线性表的双向(循环)链表存储结构-typedef struct DuLNode Ele

25、mType data;文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档

26、编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10

27、Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J

28、3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1

29、文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q

30、10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I

31、6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1名师推荐精心整理学习必备struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;Status ListInsert_DuL(DuLinkList&L,int i,ElemTyp

32、e&e)/在带头结点的双向链表L的第 i 个位置插入e,1i表长+1 DuLNode*p=L;int j=0;while(jnext;+j;if(!p)return ERROR;s=(DuLNode*)malloc(sizeof(DuLNode);if(!s)exit(OVERFLOW);s-data=e;s-prior=p;s-next=p-next;/记:注意分析指针改变p-next-prior=s;p-next=s;/次序对结果的影响return OK;另外看下多项式的相关课件，老师复习提纲上有写这方面的代码。第三章栈和队列1.栈(Stack)是定义在线性结构上的抽象数据类型，其操作类似

33、线性表操作，但元素的插入、删除和访问都必须在表的一端进行，为形象起见，称允许操作端为栈顶(Top)，另一端为栈底(base)，注意 Top指向待插入位置。特性:Last In First Out 后进先出/总是访问最近插入的一个/按插入顺序倒着访问。#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef?SElemType;/栈元素类型typedef struct SElemType*base;/栈底指针SElemType*top;/栈顶指针int stacksize;/栈容量SqStack Status InitStack(S

34、qStack&S)/构造空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/存储分配失败S.top=S.base;/空栈S.stacksize=STACK_INIT_SIZE;return(OK);/InitStack 复杂度”O(1)”Status DestroyStack(SqStack&S)/销毁栈 S free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;/复杂度 O(1)Status Cle

35、arStack(SqStack&S)/置 S为空栈S.top=S.base;return OK;/复杂度 O(1)Status Push(SqStack&S,SElemType e)/插入 e 为栈顶元素if(S.top-S.base=S.stacksize)/判断栈满/栈满则应重新分配空间S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=(S.base+S.stacksize);/使得 S.top重新指向栈顶,因 re

36、alloc S.stacksize+=STACKINCREMENT;*S.top+=e;/top 指向待插入位置return(OK);/Push,复杂度 O(1)Status Pop(SqStack&S,SElemType&e)/若栈不空则栈顶元素出栈并用e 带回其值if(S.top=S.base)return ERROR;/判断栈空e=*(-S.top);/栈顶元素为*(S.top-1)return OK;/复杂度 O(1)Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;else return FALSE;int StackLe

37、ngth(SqStack S)return(S.top-S.base);Status GetTop(SqStack S,SElemType&e)if(S.top=S.base)return ERROR;e=*(S.top-1);/注意 top 指向待插入位置return OK;文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z

38、9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5

39、B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5

40、O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S

41、6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2

42、J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4

43、J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T

44、3S6Z9Q1名师推荐精心整理学习必备栈的遍历一直没用到，可以自己找找课件看。2.队列类似线性表和栈,也是定义在线性结构上的ADT,与线性表和栈的区别在于，元素的插入和删除分别在表的两端进行。类似日常生活中排队,允许插入的一端为队尾(rear),允许删除端称队头(front)。特性:First In First Out 先进先出，如操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟。#define*QElemType typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePtr;typedef

45、 struct QueuePtr front;/队头指针QueuePtr rear;/队尾指针 LinkQueue;/链队列Status InitQueue(LinkQueue&Q)/构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;/莫忘！return OK;/时间复杂度O(1)Status DestroyQueue(LinkQueue&Q)/销毁队列Q，此处不同于教材,先清空元素结点，后释放头结点QueuePtr p=Q.front-next

46、;while(p)/依次释放首元素至最后一个元素Q.front-next=p-next;free(p);p=Q.front-next;free(Q.front);Q.front=NULL;Q.rear=NULL;return OK;/去掉下划线部分为置空操作,复杂度 O(n)Status EnQueue(LinkQueue&Q,QElemType e)/插入元素e 为 Q 的新的队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败p-data=e;p-next=NULL;/莫忘！Q.rear-n

47、ext=p;Q.rear=p;return OK;/复杂度 O(1)Status DeQueue(LinkQueue&Q,QElemType&e)/若队列不空，则删除 Q的队头元素，用 e 返回其“值”if(Q.front=Q.rear)return ERROR;/空队列QueuePtr p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;/只 1个结点时改尾指针free(p);return OK;/复杂度 O(1)3.循环队列#define MAXQSIZE 100/最大队列长度typedef stru

48、ct QElemType*base;/动态分配存储空间int front;/头指针,队列不空则指向队列头元素int rear;/尾指针,指向待插入元素位置 SqQueue;Status InitQueue(SqQueue&Q)/构造一个空队列Q Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);/存储分配失败Q.front=Q.rear=0;return OK;/复杂度 O(1)Status DestroyQueue(SqQueue&Q)/销毁队列Q free(Q.base);Q.fro

49、nt=Q.rear=0;return OK;/时间复杂度O(1)，比链队列快Status ClearQueue(SqQueue&Q)/将队列 Q 置空Q.front=Q.rear=0;/只要想等即可return OK;/复杂度 O(1)比链队列快Status EnQueue(SqQueue&Q,QElemType e)/插入元素e 为 Q 的新的队尾元素,无法插入(已满)则返回 ERROR if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;/判断循环队列满的条件Q.baseQ.rear=e;文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T

50、3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:CW2J5B5Q10Z5 HT4J5O7I6J3 ZG5T3S6Z9Q1文档编码:C