数据结构知识点总结.ppt

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

1、课堂讲义课堂讲义计算机系列课程之间的联系计算机系列课程之间的联系 课堂讲义课堂讲义数据结构涵盖的内容数据结构涵盖的内容课堂讲义课堂讲义二二.基本概念和术语基本概念和术语1.数据数据数据是用于描述客观事物的数值、字符，以及一切可以数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。范围随着计算机技术的发展而不断发展。2.数据元素数据元素数数据据的的基基本本单单位位是是数数据据元元素素，在在计计算算机机程程序序中中通通常常作作为为一个整体进行考虑和处理。一个整

2、体进行考虑和处理。3.数据项数据项是是数数据据的的不不可可分分割割的的最最小小单单位位，一一个个数数据据元元素素可可由由若若干干个数据项组成。个数据项组成。4.数据对象数据对象性质相同的元素的集合叫做数据对象。性质相同的元素的集合叫做数据对象。课堂讲义课堂讲义5.结点结点数数据据元元素素在在机机内内的的位位串串表表示示，即即数数据据元元素素在在计计算算机机内内的的映象。映象。6.域域/字段字段当当数数据据元元素素由由若若干干个个数数据据项项组组成成时时，位位串串中中对对应应于于各各个个数数据据项项的的子子串串称称为为域域/字字段段，是是数数据据元元素素中中数数据据项项在在计计算算机机中的映象。

3、中的映象。7.信息表信息表计计算算机机程程序序所所作作用用的的一一组组数数据据通通常常称称为为信信息息表表，是是数数据据对象在计算机中的映象。对象在计算机中的映象。课堂讲义课堂讲义8.数据结构数据结构数数据据结结构构指指的的是是数数据据元元素素之之间间的的相相互互关关系系，这这种种关关系系是是抽抽象象的的，即即并并不不涉涉及及数数据据元元素素的的具具体体内内容容。是是数数据据元元素及其相互间的关系的数学描述。素及其相互间的关系的数学描述。9.逻辑结构和存储结构逻辑结构和存储结构(1)逻辑结构逻辑结构数数据据结结构构中中描描述述的的是是数数据据元元素素之之间间的的抽抽象象关关系系(逻逻辑辑关系关

4、系)，称为逻辑结构。，称为逻辑结构。(2)存储结构存储结构/物理结构物理结构数数据据结结构构在在计计算算机机中中的的表表示示（映映象象）称称为为存存储储结结构构/物理结构。物理结构。基本概念和术语基本概念和术语课堂讲义课堂讲义(3)数据元素之间的关系（逻辑结构）在计算机中有数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象两种表示方法：顺序映象(表示表示)和非顺序映象和非顺序映象(表示表示)，从而导致两种不同的存储结构：顺序结构和链式结构。从而导致两种不同的存储结构：顺序结构和链式结构。顺顺序序映映象象（表表示示）的的特特点点是是借借助助数数据据元元素素在在存存储储器器中的相对位

5、置来表示数据元素之间的逻辑关系。中的相对位置来表示数据元素之间的逻辑关系。非非顺顺序序映映象象（表表示示）的的特特点点是是借借助助指指示示数数据据元元素素存存储地址的指针来表示数据元素之间的逻辑关系。储地址的指针来表示数据元素之间的逻辑关系。基本概念和术语基本概念和术语返回课堂讲义课堂讲义四种基本的数据结构四种基本的数据结构1.集合结构集合结构结构中的数据元素之间除了结构中的数据元素之间除了“属于同一个集合属于同一个集合”的关的关系之外，别无其他关系。关系比较松散，可用其他结构来系之外，别无其他关系。关系比较松散，可用其他结构来表示。表示。结构中的数据元素之间存在一个对一个的关系，即结构中的数

6、据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。线性关系，每个元素至多有一个直接前导和后继。2.线性结构线性结构课堂讲义课堂讲义3.树型结构树型结构结构中的数据元素之间存在一个对多个的关系，结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。素相关，而至多与上层的一个元素相关。结构中的数据元素之间存在多个对多个的关系，结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。即任意关系，任何元素之间都可能有关系。4.网状网状/

7、图型结构图型结构返回课堂讲义课堂讲义数据结构的研究对象数据结构的研究对象数据结构的研究对象数据结构的研究对象(研究内容研究内容)1.数据对象的结构形式数据对象的结构形式,各种数据结构的性质各种数据结构的性质(逻辑结构逻辑结构);2.数据对象和数据对象和”关系关系”在计算机中的表示在计算机中的表示(物理结构物理结构/存储结构存储结构);3.数据结构上定义的基本操作数据结构上定义的基本操作(算法算法);4.算法的效率算法的效率;5.数据结构的应用数据结构的应用,如数据分类如数据分类,检索检索.返回课堂讲义课堂讲义数据结构的作用图数据数据结构结构数据关系数据关系数数据据表表示示数数据据类类型型数学数

8、学离散数学离散数学应用数学应用数学硬件硬件存储设备存储设备总体结构总体结构软件软件系统软件系统软件应用软件应用软件算法算法设计设计数据数据运算运算编码编码理论理论数据数据组合组合系统设计系统设计数据存取数据存取课堂讲义课堂讲义2.1算法及其性能评价准则算法及其性能评价准则算法（算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。则）的有限序列，其中每一条指令表示一个或多个操作。算法的特征算法的特征：有穷性、有穷性、确定性、确定性、能行性、能行性、输入、输入、输出输出算法描述：算法描

9、述：自然语言；自然语言；程序设计语言；程序设计语言；类语言类语言*；一、算法、算法的特征和算法描述一、算法、算法的特征和算法描述常用的算法设计方法常用的算法设计方法：递归法（递归法（Recursion）、）、分治法分治法(Divide-andConquer)、贪心法贪心法(Greedy)、动态规划动态规划(DynamicProgramming)、搜索与遍历、搜索与遍历、回溯（回溯（Backtracking）、）、解空间局部搜索解空间局部搜索近似算法近似算法(Approximation)、在线算法（在线算法（On-Line）等）等课堂讲义课堂讲义2.2算法时间复杂性分析方法算法时间复杂性分析方法

10、定理定理2.1若若A（n）=amnm+a1n+a0是关于是关于n的的m次多项式，则次多项式，则A（n）=（nm）*此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关系数和其他低次项无关（1）表示实践复杂性为常数表示实践复杂性为常数常见的时间复杂性及其比较常见的时间复杂性及其比较（1）（n）（n）（n）（nn）（n2）（n3）=(y+1)(y+1)y=y+1;时间时间复复杂杂性性为为O（s=0;f(n)=1;T2(n)=O(f(n)=O(1)常量常量阶阶）课堂讲义课堂讲义 for(i=1;i=n;+i)

11、for(j=1;j=n;+j)+x;s+=x;f(n)=3n2+2n+1;T3(n)=O(f(n)=O(n2)平方阶平方阶 for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;f(n)=2n3+3n2+2n+1;T4(n)=O(f(n)=O(n3)立方阶立方阶for(i=1;i=n;+i)+x;s+=x;f(n)=3n+1;T1(n)=O(f(n)=O(n)线形阶线形阶课堂讲义课堂讲义第三章第三章线性表（线性表（LinerList）课堂讲义课堂讲义知识点：知识点：线性表的逻辑结构和各种存储表示方法线性表的逻辑结构和各种

12、存储表示方法定义在逻辑结构上的各种基本运算（操作）定义在逻辑结构上的各种基本运算（操作）在各种存储结构上如何实现这些基本运算在各种存储结构上如何实现这些基本运算各种基本运算的时间复杂性各种基本运算的时间复杂性重点：重点：熟练掌握顺序表和单链表上实现的各种算法及相关的时间复熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析杂性分析难点：难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题题课堂讲义课堂讲义3.1抽象数据型线性表抽象数据型线性表 定义定义 线性表是由线性表是由n(n0)n(n0)个相同类型的元素组成的

13、有序集合。个相同类型的元素组成的有序集合。记为：记为：(a (a1 1,a,a2 2,a,a3 3,a,ai-1i-1,a,ai i,a,ai+1i+1,a,an n)其中：其中：n为线性表中元素个数，称为线性表的长度；为线性表中元素个数，称为线性表的长度；当当n=0时，为空表，记为（时，为空表，记为（）。）。ai为线性表中的元素，类型定义为为线性表中的元素，类型定义为elementtypea1为表中第为表中第1个元素，无前驱元素；个元素，无前驱元素；an为表中最后一个为表中最后一个元素，无后继元素；对于元素，无后继元素；对于ai-1,ai,ai+1(1in)，称，称ai-1为为ai的直接前驱

14、，的直接前驱，ai+1为为ai的直接后继。的直接后继。(位置概念！）位置概念！）线性表是有限的，也是有序的。线性表是有限的，也是有序的。课堂讲义课堂讲义3.1抽象数据型线性表抽象数据型线性表线性表线性表LIST=(D,R)D=ai|aiElementset,i=1,2,n,n0R=HH=|ai-1,aiD,i=2,n操作：设操作：设L的型为的型为LIST线性表实例，线性表实例，x的型为的型为elementtype的元素的元素实例，实例，p为位置变量。所有操作描述为：为位置变量。所有操作描述为：Insert(x,p,L)Locate(x,L)Retrieve(p,L)Delete(p,L)Pre

15、vious(p,L),Next(p,L)MakeNull(L)First(L)End(L)数学模型课堂讲义课堂讲义3.1抽象数据型线性表抽象数据型线性表举例：设计函数举例：设计函数Deleval（LIST&L,elementtyped)，其功能，其功能为删除为删除L中所有值为中所有值为d的元素。的元素。voidDeleval(LIST&L,elementtyped)positionp;p=First(L);while(p!=Ennd(L)if(same(Retrieve(p,L),d)Delete(p,L);elsep=Next(p,L);课堂讲义课堂讲义3.2线性表的实现线性表的实现问题：确

16、定数据结构（存储结构）实现型问题：确定数据结构（存储结构）实现型LIST，并在此基础上，并在此基础上实现各个基本操作。实现各个基本操作。存储结构的三种方式：存储结构的三种方式：连续的存储空间（数组）连续的存储空间（数组）静态存储静态存储非连续存储空间非连续存储空间指针（链表）指针（链表）动态存储动态存储游标（连续存储空间游标（连续存储空间+动态管理思想）动态管理思想）静态链表静态链表3.2.13.2.1指针和游标指针和游标指针和游标指针和游标指针：地址量，其值为另一存储空间的地址；指针：地址量，其值为另一存储空间的地址；游标：整型指示量，其值为数组的下标，用以表示指定元素游标：整型指示量，其值

17、为数组的下标，用以表示指定元素的的“地址地址”或或“位置位置”（所在的数组下标）（所在的数组下标）课堂讲义课堂讲义3.2.23.2.2线性表的数组实现线性表的数组实现线性表的数组实现线性表的数组实现第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表的数组实现线性表的数组实现存储池容量存储池容量第第i个元素个元素1ilast顺序表：顺序表：把线性表的元素逻辑顺序依次存放把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的型量表示最后一个元素所在单元的下标

18、。下标。特点：特点：元素之间的逻辑关系（相继元素之间的逻辑关系（相继/相邻相邻关系）用物理上的相邻关系来表示关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的（用物理上的连续性刻画逻辑上的相继性）；相继性）；是一种随机存储结构，是一种随机存储结构，也就是可以也就是可以随机存取表中的任意元素，其存储随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表位置可由一个简单直观的公式来表示。示。课堂讲义课堂讲义3.2.23.2.2线性表的数组实现线性表的数组实现线性表的数组实现线性表的数组实现第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last

19、表表空单元空单元图图3-1线性表的数组实现线性表的数组实现存储池容量存储池容量第第i个元素个元素1ilast类型定义：#define maxlength 100structLISTelementtypeelementsmaxlength;intlast;位置类型：typedefintposition;线性表 L:LISTL;表示：L.elementsp/L的第p个元素L.lastL的长度，最后元素的位置课堂讲义课堂讲义3.2.23.2.2线性表的数组实现线性表的数组实现线性表的数组实现线性表的数组实现操作操作：voidInsert(elementtypex,positionp,LIST&L)p

20、ositionq;if(L.last=maxlength1)error(“表满”)；elseif(pL.last+1)|(p=p;q-)L.elementsq+1=L.elementsq;L.last=L.last+1;L.elementsp=x;/时间复杂性：O(n)第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表的数组实现线性表的数组实现存储池容量存储池容量第第i个元个元素素1ilast课堂讲义课堂讲义positionLocate(elementtypex,LISTL)positionq;for(q=1;qL.l

21、ast)error(“指定元素不存在”);elsereturn(L.elementsp);/时间复杂性：O(1)第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表的数组实现线性表的数组实现存储池容量存储池容量第第i个元素个元素1ilast课堂讲义课堂讲义voidDelete(positionp,LIST&L)positionq;if(pL.last)|(p1)error(“指定位置不存在”)；elseL.last=L.last1;for(q=p;q=L.last;q+)L.elementsq=L.elementsq+1

22、;/时间复杂性：O(n)3.2.23.2.2线性表的数组实现线性表的数组实现线性表的数组实现线性表的数组实现positionPrevious(positionp,LISTL)if(pL.last)error(“前驱元素不存在”);elsereturn(p1);/时间复杂性：O(1)第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表的数组实现线性表的数组实现存储池容量存储池容量第第i个元素个元素1ilast课堂讲义课堂讲义positionEnd(LISTL)return(L.last+1);/O(1)positionFi

23、rst(LISTL)return(1);/复杂性：O(1)positionNext(positionp,LISTL)if(p=L.last)error(“前驱元素不存在”);elsereturn(p+1);/时间复杂性：O(1)positionMakeNull(LIST&L)L.last=0;return(L.last+1);/时间复杂性：O(1)3.2.23.2.2线性表的数组实现线性表的数组实现线性表的数组实现线性表的数组实现第第1个元素个元素第第2个元素个元素最后最后1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表的数组实现线性表的数组实现存储池容量存储

24、池容量第第i个元素个元素1ilast课堂讲义课堂讲义3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现结点形式结点形式elementnext结点信息结点信息下一结点地址下一结点地址celltypeLISTheader;positionp,q;a1a2a3anheaderqp单链表：单链表：一个线性表由若干个结点组成，每个结点均含有两个域：一个线性表由若干个结点组成，每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域，这样就形成一个存放元素的信息域和存放其后继结点的指针域，这样就形成一个单向链接式存储结构，简称单向链表或单向线性链表。单向链接式存储结

25、构，简称单向链表或单向线性链表。结构特点结构特点：逻辑次序和物理次序不一定相同；逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示；元素之间的逻辑关系用指针表示；需要额外空间存储元素之间的关需要额外空间存储元素之间的关系；系；非随机存储结构非随机存储结构课堂讲义课堂讲义3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现结点形式结点形式elementnext结点信息结点信息下一结点地址下一结点地址celltype类型定义：类型定义：structcelltypeelementtypeelement;celltype*next;/*结点型结点型*/线性表的型

26、线性表的型typedefcelltype*LIST;位置型位置型typedefcelltype*position;LISTheader;positionp,q;a1a2a3anheaderqpa2:(*p).element;q:(*p).next;a2:pelement;q:pnext;记法记法:课堂讲义课堂讲义操作讨论操作讨论：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现插入元素插入元素:pa1xheaderqai-1aixpqanxqp(a)表头插入元素(b)中间插入元素(c)表尾插入元素q=newcelltype;qelement=x;qnext=

27、pnext;pnext=q;或或:temp=pnext;pnext=newcelltype;pnextelement=x;pnextnext=temp;讨论表头结点的作用讨论表头结点的作用课堂讲义课堂讲义操作讨论操作讨论：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现删除元素删除元素:q=pnext;pnext=qnext;deleteq;或：q=pnext;pnext=pnextnext;deleteq;讨论结点讨论结点ai的位置的位置pa1header(a)删除第一个元素a2qpai-1aipq(b)删除中间元素ai+1anan-1qp(c)删除表尾元

28、素课堂讲义课堂讲义操作操作：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现positionEnd(LISTL)positionq;q=L;while(qnext!=NULL)q=qnext;return(q);/时间复杂性：O(n)voidInsert(elementtypex,positionp)positionq;q=newcelltype;qelement=x;qnext=pnext;pnext=q;/时间复杂性：O(1)Lqa1a2a3an课堂讲义课堂讲义操作操作：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现

29、positionLocate(elementtypex,LISTL)positionp;p=L;while(pnext!=NULL)if(pnextelement=x)returnp;elsep=pnext;returnp;/时间复杂性：O(n)elementtypeRetrieve(positionp)return(pnextelement);/时间复杂性：O(1)Lqa1a2a3an课堂讲义课堂讲义操作操作：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现voidDelete(positionp)positionq;if(pnext!=NULL)q=pn

30、ext;pnext=qnext;deleteq;/时间复杂性：O(1)positionPrevious(positionp)positionq;if(p=Lnext)error(“不存在前驱元素”)；elseq=L;while(qnext!=p)q=qnext;returnq;/时间复杂性：O(n)Lqa1a2a3an课堂讲义课堂讲义操作操作：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现positionNext(positionp)positionq;if(pnext=NULL)error(“不存在后继元素”)；elseq=pnext;returnq;/

31、时间复杂性：O(1)positionMakeNull(LIST&L)L=newcelltype;Lnext=NULL;returnL;/时间复杂性：O(1)课堂讲义课堂讲义操作操作：3.2.33.2.3线性表的指针实现线性表的指针实现线性表的指针实现线性表的指针实现positionFirst(LISTL)returnL;/时间复杂性：O(1)静态链表静态链表与与动态链表的动态链表的比较比较比较参数比较参数表的容量表的容量存取操作存取操作时间时间空间空间链式存储链式存储灵活，易扩充灵活，易扩充顺序存取顺序存取访问元素费时间访问元素费时间实际长度，节省空间实际长度，节省空间顺序存储顺序存储固定，不

32、易扩充固定，不易扩充随机存取随机存取插入删除费时间插入删除费时间估算表长度，浪费空间估算表长度，浪费空间举例：遍历线性链表，按照线性表中举例：遍历线性链表，按照线性表中 元素的顺序，依次访问表中的元素的顺序，依次访问表中的 每一个元素，每个元素只能被每一个元素，每个元素只能被 访问一次。访问一次。voidTravel(LISTL)positionp;p=Lnext;while(p!=NULL)coutnext-next;q=p-next;L-next-next=NULL;while(p!=null)p-next=L-next;L-next=p;p=q;q=q-next;方法二方法二:线性表由线

33、性表由q来来表示表示p=null;w=q;while(w!=null)w=w-next;q-next=p;p=q;q=w;课堂讲义课堂讲义3.2.53.2.5双向链表双向链表双向链表双向链表dcelltype结点形式结点形式elementnext结点信息结点信息后继结点指针后继结点指针previous前驱结点指针前驱结点指针ai-1aiai+1p headerantail双向连表：在单向链表中，对每个结点增加双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为表的这种存储结构称为双向链表。双向链表。/*结点类型结

34、点类型*/structdcelltypeelementtypeelement;dcelltype*next,*previous;/*表和位置的类型表和位置的类型*/typedefdcelltype*DLIST;typedefdcelltype*position;优点：优点：实现双向查找（单链表不易做到）实现双向查找（单链表不易做到）表中的位置表中的位置i i 可以用指示含有第可以用指示含有第i i 个结点个结点的指针表示。的指针表示。缺点：空间开销大。缺点：空间开销大。课堂讲义课堂讲义3.2.53.2.5双向链表双向链表双向链表双向链表操作操作：删除位置p的元素：voidDelete(posi

35、tionp,DLIST&L)if(p-previous!=NULL)ppreviousnext=pnext;if(pnext!=NULL)pnextprevious=pprevious;deletep;voidInsert(elementtypex,positionp,DLIST&L)positionq;q=newdcelltype;qelement=x;ppreviousnext=q;qprevious=pprevious;qnext=p;pprevious=q;ai-1aiai+1p课堂讲义课堂讲义3.2.63.2.6环形链表环形链表环形链表环形链表单向线性链表单向线性链表双向线性链表双向

36、线性链表单向循环链表单向循环链表双向循环链表双向循环链表对线性链表的改进，解决对线性链表的改进，解决“单单向操作向操作”的问题；改进后的链的问题；改进后的链表，能够从任意位置元素开始，表，能够从任意位置元素开始，访问表中的每一个元素。访问表中的每一个元素。单向环形链表单向环形链表：在在(不带表头结点不带表头结点)的单向链表中，使末尾结点的指的单向链表中，使末尾结点的指针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识这个表。这个表。存储结构存储结构:与单向链表相同与单向链表相同(略）略）a1a2a3anR左端结点左端结点右端结点

37、右端结点R空表空表课堂讲义课堂讲义操作操作：在表左端插入结点Insert(x,FIRST(R),R);LInsert(x,R)voidLInsert(elementtypex,LIST&R)celltype*p;p=newcelltype;pelement=x;if(R=NULL)pnext=p;R=p;elsepnext=Rnext;Rnext=p;3.2.63.2.6环形链表环形链表环形链表环形链表在表右端插入结点Insert(x,END(R),R);RInsert(x,R)voidRInsert(elementtypex,LISTR)LInsert(x,R);R=Rnext;a1a2xa

38、nRpxpR课堂讲义课堂讲义操作操作：从表左端删除结点Delete(First(R),R);LDelete(R)voidLDelete(LIST&R)celltype*p;if(R=NULL)error(“空表”);elsep=Rnext;Rnext=pnext;if(p=R)R=NULL;deletep;3.2.63.2.6环形链表环形链表环形链表环形链表xpRpa1a2anR课堂讲义课堂讲义3.2.63.2.6环形链表环形链表环形链表环形链表双向环形链表：双向环形链表：a1aianR 双向环形链表的结构与双向连表结构相同，只是将表头元素双向环形链表的结构与双向连表结构相同，只是将表头元素的

39、空的空previousprevious域指向表尾，同时将表尾的空域指向表尾，同时将表尾的空nextnext域指向表头结点，域指向表头结点，从而形成向前和向后的两个环形链表，对链表的操作变得更加灵从而形成向前和向后的两个环形链表，对链表的操作变得更加灵活。活。举例：设计算法，将一个单向环形链表反向。头元素变成尾举例：设计算法，将一个单向环形链表反向。头元素变成尾 元素，尾元素变成新的头元素，依次类推。元素，尾元素变成新的头元素，依次类推。课堂讲义课堂讲义3.2.63.2.6环形链表环形链表环形链表环形链表a1a2a3anRanan-1an-2a1RvoidReverse(LIST&R)posit

40、ionp,q;q=R;p=Rnext;while(p!=R)s=q;q=p;p=pnext;qnext=s;算法如下：存储结构定义略存储结构定义略课堂讲义课堂讲义3.33.3栈（栈（栈（栈（StackStack）栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。对线性表的操作加以限制后，形成的一种新的数据结构。定义：是限定只在表尾进行定义：是限定只在表尾进行插入和删除操作的线性表。插入和删除操作的线性表。栈又称为后进先出栈又称为后进先出(Last In First Out)(Last

41、 In First Out)的线性表。的线性表。简称简称LIFOLIFO结构。结构。栈举例栈举例a1a2an-1anInsertDeletetopbottom栈底栈顶栈示意图课堂讲义课堂讲义3.33.3栈栈栈栈栈的基本栈的基本MakeNull(S)操作操作Top(S)Pop(S)Push(x,S)Empty(S)举例：利用栈实现行编辑处理。举例：利用栈实现行编辑处理。设定符号设定符号“#”“#”为擦讫符，用以删为擦讫符，用以删除除“#”“#”前的字符；符号前的字符；符号“”“”为删为删行符，用以删除当前编辑行。行符，用以删除当前编辑行。原理：原理：一般字符进栈；一般字符进栈；读字符读字符 擦讫

42、符退栈；擦讫符退栈；删行符则清栈删行符则清栈算法：算法：voidLineEdit()STACK；charc;MakeNull(S);c=getchar();while(c!=n)if(c=#)Pop(S);elseif(c=)MakeNull(S);elsePush(c,S);c=getchar();逆序输出栈中所有元素；逆序输出栈中所有元素；课堂讲义课堂讲义3.3.13.3.1栈的实现栈的实现栈的实现栈的实现3.33.3栈栈栈栈1、顺序存储、顺序存储顺序栈示意图anaia3a2a1-maxlength-13210top类型定义：类型定义：enumBoolenTRUE,FALSEtypedef

43、structelementtypeelementsmaxlength;inttop;STACK;STACKS;栈的容量：栈的容量：maxlength1;栈空：栈空：S.top=0;栈满：栈满：S.top=maxlength1;栈顶元素：栈顶元素：S.elementsS.top;课堂讲义课堂讲义3.3.13.3.1栈的实现栈的实现栈的实现栈的实现1、顺序存储、顺序存储操作：操作：voidMakeNull(STACK&S)S.top=0;BooleanEmpty(STACKS)if(S.topnext=NULL;voidPush(Elementtypex,STACK&S)STACKstk;stk=

44、newnode;stk-val=elm;stk-next=S-next;S-next=stk;课堂讲义课堂讲义 voidPop(STACK&S)STACKstk;if(S-next)stk=S-next;S-next=stk-next;deletestk;ElementtypeTop(STACKS)if(S-next)return(S-next-val);elsereturnNULL;课堂讲义课堂讲义 booleanEmpty(STACKS)if(S-next)returnFALSE;elsereturnTRUE;多个栈共用一个存储空间的讨论多个栈共用一个存储空间的讨论STACKmaxleng

45、thbot1top1bot2top2bot3top3top2botntopn0Maxlength-1botn+1botitopi课堂讲义课堂讲义3.43.4排队或队列（排队或队列（排队或队列（排队或队列（QueueQueue）队列是对线性表的插入和删除操作加以限定的另一种限队列是对线性表的插入和删除操作加以限定的另一种限定性数据结构。定性数据结构。定义定义 将线性表的插入和删除操作分别限制在表的两端进行，将线性表的插入和删除操作分别限制在表的两端进行，和栈相反，队列是一种先进先出（和栈相反，队列是一种先进先出（First In First OutFirst In First Out，简称，简称

46、 FIFO FIFO 结构）的线性表。结构）的线性表。a1，a2，a3，an-1，an出队列出队列入队列，入队列，插入，排队插入，排队删除，出队删除，出队队头队头队尾队尾队列示意图队列示意图frontrear操作：操作：MakeNull(Q)、Front(Q)、EnQueue(x,Q)、DeQueue(Q)、Empty(Q)课堂讲义课堂讲义3.43.4队列（队列（队列（队列（QueueQueue）3.4.13.4.1队列的指针实现队列的指针实现队列的指针实现队列的指针实现元素的元素的“型型”：structcelltypeelementtypeelement；celltype*next；队列的队

47、列的“型型”：structQUEUEcelltype*front；celltype*rear；;a1a2anQ.frontQ.rear队列的指针实现示意图课堂讲义课堂讲义3.4.13.4.1队列的指针实现队列的指针实现队列的指针实现队列的指针实现操作：操作：voidMakeNull(QUEUE&Q)Q.front=newcelltype;Q.frontnext=NULL;Q.rear=Q.front;BooleanEmpty(Q)QUEUE&Q;if(Q.front=Q.rear)returnTRUE;elsereturnFALSE;elementtypeFront(Q)QUEUEQ;retu

48、rnQ.frontnextelement;课堂讲义课堂讲义3.4.13.4.1队列的指针实现队列的指针实现队列的指针实现队列的指针实现voidEnQueue(elementtypex,QUEUE&Q)Q.rearnext=newcelltype;Q.rear=Q.rearnext;Q.rearelement=x;Q.rearnext=NULL;voidDelete(QUEUE&Q)celltype*temp;if(Empty(Q)error(“空队列空队列”);elsetemp=Q.frontnext;Q.frontnext=tempnext;deletetemp;if(Q.frontnext

49、=NULL)Q.rear=Q.front;课堂讲义课堂讲义3.4.23.4.2队列的数组实现队列的数组实现队列的数组实现队列的数组实现队列的队列的“型型”：structQUEUEelementtypeelementmaxlength;intfront；intrear；;a1a2a3a4 an Qfrontrearmaxlength右图：队列右图：队列Q状态状态1随随着着不不断断有有元元素素出出队队和和进进队队（插插入入和和删删除除），队队列列的的状状态态由由1变变成成2；此此时时an占占据据队队列列的的最最后后一一个个位位置置；第第n+1个个元元素素无无法法进进队队,但但实实际际上上，前前 面

50、面 部部 分分 位位 置置 空空 闲闲。“假溢假溢出出“maxlengtha1a2a3a4a5a6 anQfrontrear下图：队列下图：队列Q状态状态2课堂讲义课堂讲义3.4.23.4.2队列的数组实现队列的数组实现队列的数组实现队列的数组实现 解决假溢出的方法有多种；一是通过不断移动元素位置，解决假溢出的方法有多种；一是通过不断移动元素位置，每当有元素出队列时，后面的元素前移一个位置，使队头元每当有元素出队列时，后面的元素前移一个位置，使队头元素始终占据队列的第一个位置。素始终占据队列的第一个位置。第二种方法是采用循环队列。第二种方法是采用循环队列。Q.rearQ.front01maxl