数据结构知识点总结有工大老师多经验编写省公共课一等奖全国赛课获奖课件.pptx

课堂讲义课堂讲义计算机系列课程之间联络计算机系列课程之间联络 第1页课堂讲义课堂讲义数据结构涵盖内容数据结构涵盖内容第2页课堂讲义课堂讲义二二.基本概念和术语基本概念和术语1.数据数据数据是用于描述客观事物数值、字符，以及一切能够输数据是用于描述客观事物数值、字符，以及一切能够输入到计算机中并由计算机程序加以处理符号集合。其范围伴随入到计算机中并由计算机程序加以处理符号集合。其范围伴随计算机技术发展而不停发展。计算机技术发展而不停发展。2.数据元素数据元素数数据据基基本本单单位位是是数数据据元元素素，在在计计算算机机程程序序中中通通常常作作为为一一个整体进行考虑和处理。个整体进行考虑和处理。3.数据项数据项是是数数据据不不可可分分割割最最小小单单位位，一一个个数数据据元元素素可可由由若若干干个个数数据项组成。据项组成。4.数据对象数据对象性质相同元素集合叫做数据对象。性质相同元素集合叫做数据对象。第3页课堂讲义课堂讲义5.结点结点数据元素在机内位串表示，即数据元素在计算机内映象。数据元素在机内位串表示，即数据元素在计算机内映象。6.域域/字段字段当当数数据据元元素素由由若若干干个个数数据据项项组组成成时时，位位串串中中对对应应于于各各个个数数据据项项子子串串称称为为域域/字字段段，是是数数据据元元素素中中数数据据项项在在计计算算机机中中映象。映象。7.信息表信息表计计算算机机程程序序所所作作用用一一组组数数据据通通常常称称为为信信息息表表，是是数数据据对对象在计算机中映象。象在计算机中映象。第4页课堂讲义课堂讲义8.数据结构数据结构数数据据结结构构指指是是数数据据元元素素之之间间相相互互关关系系，这这种种关关系系是是抽抽象象，即即并并不不包包括括数数据据元元素素详详细细内内容容。是是数数据据元元素素及及其其相相互间关系数学描述。互间关系数学描述。9.逻辑结构和存放结构逻辑结构和存放结构(1)逻辑结构逻辑结构数数据据结结构构中中描描述述是是数数据据元元素素之之间间抽抽象象关关系系(逻逻辑辑关关系系)，称为逻辑结构。，称为逻辑结构。(2)存放结构存放结构/物理结构物理结构数数据据结结构构在在计计算算机机中中表表示示（映映象象）称称为为存存放放结结构构/物物理结构。理结构。1.1.1基本概念和术语基本概念和术语第5页课堂讲义课堂讲义(3)数据元素之间关系（逻辑结构）在计算机中有两数据元素之间关系（逻辑结构）在计算机中有两种表示方法：次序映象种表示方法：次序映象(表示表示)和非次序映象和非次序映象(表示表示)，从，从而造成两种不一样存放结构：次序结构和链式结构。而造成两种不一样存放结构：次序结构和链式结构。次次序序映映象象（表表示示）特特点点是是借借助助数数据据元元素素在在存存放放器器中中相对位置来表示数据元素之间逻辑关系。相对位置来表示数据元素之间逻辑关系。非非次次序序映映象象（表表示示）特特点点是是借借助助指指示示数数据据元元素素存存放放地址指针来表示数据元素之间逻辑关系。地址指针来表示数据元素之间逻辑关系。1.1.1基本概念和术语基本概念和术语返回第6页课堂讲义课堂讲义1.1.2四种基本数据结构四种基本数据结构1.集合结构集合结构结构中数据元素之间除了结构中数据元素之间除了“属于同一个集合属于同一个集合”关系之关系之外，别无其它关系。关系比较涣散，可用其它结构来表示。外，别无其它关系。关系比较涣散，可用其它结构来表示。结构中数据元素之间存在一个对一个关系，即线性结构中数据元素之间存在一个对一个关系，即线性关系，每个元素至多有一个直接前导和后继。关系，每个元素至多有一个直接前导和后继。2.线性结构线性结构第7页课堂讲义课堂讲义3.树型结构树型结构结构中数据元素之间存在一个对多个关系，即层结构中数据元素之间存在一个对多个关系，即层次关系，即每一层上元素可能与下层多个元素相关，次关系，即每一层上元素可能与下层多个元素相关，而至多与上层一个元素相关。而至多与上层一个元素相关。结构中数据元素之间存在多个对多个关系，即任结构中数据元素之间存在多个对多个关系，即任意关系，任何元素之间都可能相关系。意关系，任何元素之间都可能相关系。4.网状网状/图型结构图型结构返回第8页课堂讲义课堂讲义1.1.3数据结构研究对象数据结构研究对象数据结构研究对象数据结构研究对象(研究内容研究内容)1.数据对象结构形式数据对象结构形式,各种数据结构性质各种数据结构性质(逻辑结构逻辑结构);2.数据对象和数据对象和”关系关系”在计算机中表示在计算机中表示(物理结构物理结构/存放结构存放结构);3.数据结构上定义基本操作数据结构上定义基本操作(算法算法);4.算法效率算法效率;5.数据结构应用数据结构应用,如数据分类如数据分类,检索检索.返回第9页课堂讲义课堂讲义数据结构作用图数据数据结构结构数据关系数据关系数数据据表表示示数数据据类类型型数学数学离散数学离散数学应用数学应用数学硬件硬件存放设备存放设备总体结构总体结构软件软件系统软件系统软件应用软件应用软件算法算法设计设计数据数据运算运算编码编码理论理论数据数据组合组合系统设计系统设计数据存取数据存取第10页课堂讲义课堂讲义2.1算法及其性能评价准则算法及其性能评价准则算法（算法（Algorithm）：是对特定问题求解步骤一个描述，它是指令（规则）是对特定问题求解步骤一个描述，它是指令（规则）有限序列，其中每一条指令表示一个或多个操作。有限序列，其中每一条指令表示一个或多个操作。算法特征算法特征：有穷性、有穷性、确定性、确定性、能行性、能行性、输入、输入、输出输出算法描述：算法描述：自然语言；自然语言；程序设计语言；程序设计语言；类语言类语言*；一、算法、算法特征和算法描述一、算法、算法特征和算法描述惯用算法设计方法惯用算法设计方法：递归法（递归法（Recursion）、）、分治法分治法(Divide-andConquer)、贪心法贪心法(Greedy)、动态规划动态规划(DynamicProgramming)、搜索与遍历、搜索与遍历、回溯（回溯（Backtracking）、）、解空间局部搜索解空间局部搜索近似算法近似算法(Approximation)、在线算法（在线算法（On-Line）等）等第11页课堂讲义课堂讲义2.2算法时间复杂性分析方法算法时间复杂性分析方法定理定理2.1若若A（n）=amnm+a1n+a0是关于是关于nm次多项式，则次多项式，则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)常量常量阶阶）第13页课堂讲义课堂讲义 for(i=1;i=n;+i)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)线形阶线形阶第14页课堂讲义课堂讲义第三章第三章线性表（线性表（LinerList）第15页课堂讲义课堂讲义知识点：知识点：线性表逻辑结构和各种存放表示方法线性表逻辑结构和各种存放表示方法定义在逻辑结构上各种基本运算（操作）定义在逻辑结构上各种基本运算（操作）在各种存放结构上怎样实现这些基本运算在各种存放结构上怎样实现这些基本运算各种基本运算时间复杂性各种基本运算时间复杂性重点：重点：熟练掌握次序表和单链表上实现各种算法及相关时间复杂性熟练掌握次序表和单链表上实现各种算法及相关时间复杂性分析分析难点：难点：使用本章所学基本知识设计有效算法处理与线性表相关应用问题使用本章所学基本知识设计有效算法处理与线性表相关应用问题第16页课堂讲义课堂讲义3.1抽象数据型线性表抽象数据型线性表 定义定义 线性表是由线性表是由n(n0)n(n0)个相同类型元素组成有序集合。个相同类型元素组成有序集合。记为：记为：(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直接前驱，直接前驱，ai+1为为ai直接后继。直接后继。(位置概念！）位置概念！）线性表是有限，也是有序。线性表是有限，也是有序。第17页课堂讲义课堂讲义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)Previous(p,L),Next(p,L)MakeNull(L)First(L)End(L)数学模型第18页课堂讲义课堂讲义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);第19页课堂讲义课堂讲义3.2线性表实现线性表实现问题：确定数据结构（存放结构）实现型问题：确定数据结构（存放结构）实现型LIST，并在此基础上，并在此基础上实现各个基本操作。实现各个基本操作。存放结构三种方式：存放结构三种方式：连续存放空间（数组）连续存放空间（数组）静态存放静态存放非连续存放空间非连续存放空间指针（链表）指针（链表）动态存放动态存放游标（连续存放空间游标（连续存放空间+动态管理思想）动态管理思想）静态链表静态链表3.2.13.2.1指针和游标指针和游标指针和游标指针和游标指针：地址量，其值为另一存放空间地址；指针：地址量，其值为另一存放空间地址；游标：整型指示量，其值为数组下标，用以表示指定元素游标：整型指示量，其值为数组下标，用以表示指定元素“地址地址”或或“位置位置”（所在数组下标）（所在数组下标）第20页课堂讲义课堂讲义3.2.23.2.2线性表数组实现线性表数组实现线性表数组实现线性表数组实现第第1个元素个元素第第2个元素个元素最终最终1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表数组实现线性表数组实现存放池容量存放池容量第第i个元素个元素1ilast次序表：次序表：把线性表元素逻辑次序依次存放在把线性表元素逻辑次序依次存放在数组连续单元内，再用一个整型量数组连续单元内，再用一个整型量表示最终一个元素所在单元下标。表示最终一个元素所在单元下标。特点：特点：元素之间逻辑关系（相继元素之间逻辑关系（相继/相邻关相邻关系）用物理上相邻关系来表示（用系）用物理上相邻关系来表示（用物理上连续性刻画逻辑上相继性）；物理上连续性刻画逻辑上相继性）；是一个随机存放结构，是一个随机存放结构，也就是能够也就是能够随机存取表中任意元素，其存放位随机存取表中任意元素，其存放位置可由一个简单直观公式来表示。置可由一个简单直观公式来表示。第21页课堂讲义课堂讲义3.2.23.2.2线性表数组实现线性表数组实现线性表数组实现线性表数组实现第第1个元素个元素第第2个元素个元素最终最终1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表数组实现线性表数组实现存放池容量存放池容量第第i个元素个元素1ilast类型定义：#define maxlength 100structLISTelementtypeelementsmaxlength;intlast;位置类型：typedefintposition;线性表 L:LISTL;表示：L.elementsp/L第p个元素L.lastL长度，最终元素位置第22页课堂讲义课堂讲义3.2.23.2.2线性表数组实现线性表数组实现线性表数组实现线性表数组实现操作操作：voidInsert(elementtypex,positionp,LIST&L)positionq;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第23页课堂讲义课堂讲义positionLocate(elementtypex,LISTL)positionq;for(q=1;qL.last)error(“指定元素不存在”);elsereturn(L.elementsp);/时间复杂性：O(1)第第1个元素个元素第第2个元素个元素最终最终1个元素个元素012maxlength-1last表表空单元空单元图图3-1线性表数组实现线性表数组实现存放池容量存放池容量第第i个元素个元素1ilast第24页课堂讲义课堂讲义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;/时间复杂性：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第25页课堂讲义课堂讲义positionEnd(LISTL)return(L.last+1);/O(1)positionFirst(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线性表数组实现线性表数组实现存放池容量存放池容量第第i个元素个元素1ilast第26页课堂讲义课堂讲义3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现结点形式结点形式elementnext结点信息结点信息下一结点地址下一结点地址celltypeLISTheader;positionp,q;a1a2a3anheaderqp单链表：单链表：一个线性表由若干个结点组成，每个结点均含有两个域：一个线性表由若干个结点组成，每个结点均含有两个域：存放元素信息域和存放其后继结点指针域，这么就形成一个存放元素信息域和存放其后继结点指针域，这么就形成一个单向链接式存放结构，简称单向链表或单向线性链表。单向链接式存放结构，简称单向链表或单向线性链表。结构特点结构特点：逻辑次序和物理次序不一定相同；逻辑次序和物理次序不一定相同；元素之间逻辑关系用指针表示；元素之间逻辑关系用指针表示；需要额外空间存放元素之间关需要额外空间存放元素之间关系；系；非随机存放结构非随机存放结构第27页课堂讲义课堂讲义3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现结点形式结点形式elementnext结点信息结点信息下一结点地址下一结点地址celltype类型定义：类型定义：structcelltypeelementtypeelement;celltype*next;/*结点型结点型*/线性表型线性表型typedefcelltype*LIST;位置型位置型typedefcelltype*position;LISTheader;positionp,q;a1a2a3anheaderqpa2:(*p).element;q:(*p).next;a2:pelement;q:pnext;记法记法:第28页课堂讲义课堂讲义操作讨论操作讨论：3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现插入元素插入元素:pa1xheaderqai-1aixpqanxqp(a)表头插入元素(b)中间插入元素(c)表尾插入元素q=newcelltype;qelement=x;qnext=pnext;pnext=q;或或:temp=pnext;pnext=newcelltype;pnextelement=x;pnextnext=temp;讨论表头结点作用讨论表头结点作用第29页课堂讲义课堂讲义操作讨论操作讨论：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)删除表尾元素第30页课堂讲义课堂讲义操作操作：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第31页课堂讲义课堂讲义操作操作：3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现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第32页课堂讲义课堂讲义操作操作：3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现voidDelete(positionp)positionq;if(pnext!=NULL)q=pnext;pnext=qnext;deleteq;/时间复杂性：O(1)positionPrevious(positionp)positionq;if(p=Lnext)error(“不存在前驱元素”)；elseq=L;while(qnext!=p)q=qnext;returnq;/时间复杂性：O(n)Lqa1a2a3an第33页课堂讲义课堂讲义操作操作：3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现positionNext(positionp)positionq;if(pnext=NULL)error(“不存在后继元素”)；elseq=pnext;returnq;/时间复杂性：O(1)positionMakeNull(LIST&L)L=newcelltype;Lnext=NULL;returnL;/时间复杂性：O(1)第34页课堂讲义课堂讲义操作操作：3.2.33.2.3线性表指针实现线性表指针实现线性表指针实现线性表指针实现positionFirst(LISTL)returnL;/时间复杂性：O(1)静态链表静态链表与与动态链表动态链表比较比较比较参数比较参数表容量表容量存取操作存取操作时间时间空间空间链式存放链式存放灵活，易扩充灵活，易扩充次序存取次序存取访问元素费时间访问元素费时间实际长度，节约空间实际长度，节约空间次序存放次序存放固定，不易扩充固定，不易扩充随机存取随机存取插入删除费时间插入删除费时间估算表长度，浪费空间估算表长度，浪费空间举例：遍历线性链表，按照线性表中举例：遍历线性链表，按照线性表中 元素次序，依次访问表中元素次序，依次访问表中 每一个元素，每个元素只能被每一个元素，每个元素只能被 访问一次。访问一次。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;方法二方法二:线性表由线性表由q来来表示表示p=null;w=q;while(w!=null)w=w-next;q-next=p;p=q;q=w;第36页课堂讲义课堂讲义3.2.53.2.5双向链表双向链表双向链表双向链表dcelltype结点形式结点形式elementnext结点信息结点信息后继结点指针后继结点指针previous前驱结点指针前驱结点指针ai-1aiai+1p headerantail双向连表：在单向链表中，对每个结点增加双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点前驱结点。线性表一个域，用一指向该结点前驱结点。线性表这种存放结构称为这种存放结构称为双向链表。双向链表。/*结点类型结点类型*/structdcelltypeelementtypeelement;dcelltype*next,*previous;/*表和位置类型表和位置类型*/typedefdcelltype*DLIST;typedefdcelltype*position;优点：优点：实现双向查找（单链表不易做到）实现双向查找（单链表不易做到）表中位置表中位置i i 能够用指示含有第能够用指示含有第i i 个结点指个结点指针表示。针表示。缺点：空间开销大。缺点：空间开销大。第37页课堂讲义课堂讲义3.2.53.2.5双向链表双向链表双向链表双向链表操作操作：删除位置p元素：voidDelete(positionp,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第38页课堂讲义课堂讲义3.2.63.2.6环形链表环形链表环形链表环形链表单向线性链表单向线性链表双向线性链表双向线性链表单向循环链表单向循环链表双向循环链表双向循环链表对线性链表改进，处理对线性链表改进，处理“单向单向操作操作”问题；改进后链表，能问题；改进后链表，能够从任意位置元素开始，访问够从任意位置元素开始，访问表中每一个元素。表中每一个元素。单向环形链表单向环形链表：在在(不带表头结点不带表头结点)单向链表中，使末尾结点指单向链表中，使末尾结点指针域指向头结点，得到一个环形结构；用指向末尾结点指针标识针域指向头结点，得到一个环形结构；用指向末尾结点指针标识这个表。这个表。存放结构存放结构:与单向链表相同与单向链表相同(略）略）a1a2a3anR左端结点左端结点右端结点右端结点R空表空表第39页课堂讲义课堂讲义操作操作：在表左端插入结点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;a1a2xanRpxpR第40页课堂讲义课堂讲义操作操作：从表左端删除结点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第41页课堂讲义课堂讲义3.2.63.2.6环形链表环形链表环形链表环形链表双向环形链表：双向环形链表：a1aianR 双向环形链表结构与双向连表结构相同，只是将表头元素双向环形链表结构与双向连表结构相同，只是将表头元素空空previousprevious域指向表尾，同时将表尾空域指向表尾，同时将表尾空nextnext域指向表头结点，域指向表头结点，从而形成向前和向后两个环形链表，对链表操作变得愈加灵从而形成向前和向后两个环形链表，对链表操作变得愈加灵活。活。举例：设计算法，将一个单向环形链表反向。头元素变成尾举例：设计算法，将一个单向环形链表反向。头元素变成尾 元素，尾元素变成新头元素，依次类推。元素，尾元素变成新头元素，依次类推。第42页课堂讲义课堂讲义3.2.63.2.6环形链表环形链表环形链表环形链表a1a2a3anRanan-1an-2a1RvoidReverse(LIST&R)positionp,q;q=R;p=Rnext;while(p!=R)s=q;q=p;p=pnext;qnext=s;算法以下：存放结构定义略存放结构定义略第43页课堂讲义课堂讲义3.33.3栈（栈（栈（栈（StackStack）栈是线性表一个特殊形式，是一个限定性数据结构，也就是在对栈是线性表一个特殊形式，是一个限定性数据结构，也就是在对线性表操作加以限制后，形成一个新数据结构。线性表操作加以限制后，形成一个新数据结构。定义：是限定只在表尾进行定义：是限定只在表尾进行插入和删除操作线性表。插入和删除操作线性表。栈又称为后进先出栈又称为后进先出(Last In First Out)(Last In First Out)线性表。线性表。简称简称LIFOLIFO结构。结构。栈举例栈举例a1a2an-1anInsertDeletetopbottom栈底栈顶栈示意图第44页课堂讲义课堂讲义3.33.3栈栈栈栈栈基本栈基本MakeNull(S)操作操作Top(S)Pop(S)Push(x,S)Empty(S)举例：利用栈实现行编辑处理。举例：利用栈实现行编辑处理。设定符号设定符号“#”“#”为擦讫符，用以删为擦讫符，用以删除除“#”“#”前字符；符号前字符；符号“”“”为删为删行符，用以删除当前编辑行。行符，用以删除当前编辑行。原理：原理：普通字符进栈；普通字符进栈；读字符读字符 擦讫符退栈；擦讫符退栈；删行符则清栈删行符则清栈算法：算法：voidLineEdit()STACK；charc;MakeNull(S);c=getchar();while(c!=n)if(c=#)Pop(S);elseif(c=)MakeNull(S);elsePush(c,S);c=getchar();逆序输出栈中全部元素；逆序输出栈中全部元素；第45页课堂讲义课堂讲义3.3.13.3.1栈实现栈实现栈实现栈实现3.33.3栈栈栈栈1、次序存放、次序存放次序栈示意图anaia3a2a1-maxlength-13210top类型定义：类型定义：enumBoolenTRUE,FALSEtypedefstructelementtypeelementsmaxlength;inttop;STACK;STACKS;栈容量：栈容量：maxlength1;栈空：栈空：S.top=0;栈满：栈满：S.top=maxlength1;栈顶元素：栈顶元素：S.elementsS.top;第46页课堂讲义课堂讲义3.3.13.3.1栈实现栈实现栈实现栈实现1、次序存放、次序存放操作：操作：voidMakeNull(STACK&S)S.top=0;BooleanEmpty(STACKS)if(S.topnext=NULL;voidPush(Elementtypex,STACK&S)STACKstk;stk=newnode;stk-val=elm;stk-next=S-next;S-next=stk;第50页课堂讲义课堂讲义 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;第51页课堂讲义课堂讲义 booleanEmpty(STACKS)if(S-next)returnFALSE;elsereturnTRUE;多个栈共用一个存放空间讨论多个栈共用一个存放空间讨论STACKmaxlengthbot1top1bot2top2bot3top3top2botntopn0Maxlength-1botn+1botitopi第52页课堂讲义课堂讲义3.43.4排队或队列（排队或队列（排队或队列（排队或队列（QueueQueue）队列是对线性表插入和删除操作加以限定另一个限队列是对线性表插入和删除操作加以限定另一个限定性数据结构。定性数据结构。定义定义 将线性表插入和删除操作分别限制在表两端进行，将线性表插入和删除操作分别限制在表两端进行，和栈相反，队列是一个先进先出（和栈相反，队列是一个先进先出（First In First OutFirst In First Out，简称，简称 FIFO FIFO 结构）线性表。结构）线性表。a1，a2，a3，an-1，an出队列出队列入队列，入队列，插入，排队插入，排队删除，出队删除，出队队头队头队尾队尾队列示意图队列示意图frontrear操作：操作：MakeNull(Q)、Front(Q)、EnQueue(x,Q)、DeQueue(Q)、Empty(Q)第53页课堂讲义课堂讲义3.43.4队列（队列（队列（队列（QueueQueue）3.4.13.4.1队列指针实现队列指针实现队列指针实现队列指针实现元素元素“型型”：structcelltypeelementtypeelement；celltype*next；队列队列“型型”：structQUEUEcelltype*front；celltype*rear；;a1a2anQ.frontQ.rear队列指针实现示意图第54页课堂讲义课堂讲义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;returnQ.frontnextelement;第55页课堂讲义课堂讲义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=NULL)Q.rear=Q.front;第56页课堂讲义课堂讲义3.4.23.4.2队列数组实现队列数组实现队列数组实现队列数组实现队列队列“型型”：structQUEUEelementtypeelementmaxlength;intfront；intrear；;a1a2a3a4 an Qfrontrearmaxlength右图：队列右图：队列Q状态状态1伴伴随随不不停停有有元元素素出出队队和和进进队队（插插入入和和删删除除），队队列列状状态态由由1变变成成2；此此时时an占占据据队队列列最最终终一一个个位位置置；第第n+1个个元元素素无无法法进进队队,但但实实际际上上，前前 面面 部部 分分 位位 置置 空空 闲闲。“假溢假溢出出“maxlengtha1a2a3a4a5a6 anQfrontrear下列图：队列下列图：队列Q状态状态2第57页课堂讲义课堂讲义3.4.23.4.2队列数组实现队列数组实现队列数组实现队列数组实现 处理假溢出方法有各种；一是经过不停移动元素位置，处理假溢出方法有各种；一是经过不停移动元素位置，每当有元素出队列时，后面元素前移一个位置，使队头元每当有元素出队列时，后面元素前移一个位置，使队头元素一直占据队列第一个位置。素一直占据队列第一个位置。第二种方法是采取循环队列。第二种方法是采取循环队列。Q.rearQ.front01maxlength-1队列队列Q插入元素：插入元素：Q.rear=(Q.rear+1）%maxlength删除元素：删除元素：Q.front=(Q.front+1）%maxlength队空：队空：(Q.rear+1）%maxlength=Q.front队满：队满：(Q.rear+1)%maxlength=Q.front?第58页课堂讲义课堂讲义3.4.23.4.