线性链表课件.ppt

《线性链表课件.ppt》由会员分享，可在线阅读，更多相关《线性链表课件.ppt（457页珍藏版）》请在三一办公上搜索。

1、课程简介,数据结构,深圳大学计算机系 蔡茂国,数据结构课程简介,本课程教材为：数据结构(C语言版)严蔚敏，吴伟民清华大学出版社2004年11月（第28次印刷）,2,主要参考教材,数据结构课程简介,所有课件、作业及实验，均上传至：深圳大学首页 课程中心 输入学生姓名及密码，实现登录 从数据结构课程下下载,3,课件下载,第一章数据结构绪论,数据结构,深圳大学计算机系 蔡茂国,一、数据,5,第一节数据结构,是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据非数值性数据,第章数据结构绪论,二、数据元素（Data Element）,6,第一节数

2、据结构,数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(Data Item)组成（此时数据元素被称为记录）数据元素又称为元素、结点、记录,第章数据结构绪论,三、数据项（Data Item）,7,第一节数据结构,具有独立含义的最小标识单位。,第章数据结构绪论,四、数据对象（Data Object）,8,第一节数据结构,具有相同性质的数据元素的集合。整数数据对象 N=0,1,2,字母字符数据对象 C=A,B,C,F。,第章数据结构绪论,五、结构（Structure）,9,第一节数据结构,结构是元素之间的：空间位置关系相互作用和依赖关系,第章数据结构绪论

3、,五、结构,10,第一节数据结构,四种基本结构集合结构线性结构树形结构图形结构,第章数据结构绪论,1,六、数据结构（Data Structure）,11,第一节数据结构,1.形式定义：某一数据对象的所有数据成员之间的关系。记为：Data_Structure=D,S其中，D 是某一数据对象，S 是该对象中所有数据成员之间的关系的有限集合。,第章数据结构绪论,六、数据结构,12,第一节数据结构,2.线性数据结构举例 L=K,RK=1,2,3,4,5,6R=,第章数据结构绪论,六、数据结构,13,第一节数据结构,3.树形数据结构举例 T=K,RK=1,2,3,4,5,6R=,第章数据结构绪论,六、数

4、据结构,14,第一节数据结构,4.图形数据结构举例 G=K,RK=1,2,3,4,5,6R=(1,2),(1,5),(1,6),(2,3),(2,4),(2,6),(3,4),(4,5),(4,6),(5,6),第章数据结构绪论,七、应用举例,15,第一节数据结构,1.线性数据结构举例数据结构学生选课名单（部分）,第章数据结构绪论,七、应用举例,16,第一节数据结构,2.树形数据结构举例UNIX文件系统结构图（部分）,第章数据结构绪论,七、应用举例,17,第一节数据结构,3.图形数据结构举例深圳城市交通示意图（部分）,第章数据结构绪论,八、数据结构要解决的问题,18,第一节数据结构,如何为应用

5、程序中涉及到各种各样的数据，建立相应的数据结构（表、树或图），并依此实现软件功能从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现,第章数据结构绪论,一、逻辑结构,19,第二节数据的结构,逻辑结构描述数据元素之间的关系线性结构线性表（表，栈，队列，串等）非线性结构树（二叉树，Huffman树，二叉排序树等）图（有向图，无向图等）,第章数据结构绪论,二、物理结构（存储结构）,20,第二节数据的结构,物理结构是数据结构在计算机中的表示（或映象）顺序存储表示（可以用C语言中一维数组表示）链接存储表示（可以用C语言中的指针表示）索引存储表示散列存储表示,第章数据结构绪论,

6、二、物理结构（存储结构）,21,第二节数据的结构,复数存储结构举例,第章数据结构绪论,z1=3.0-2.3i指针或链(地址),z1=3.0-2.3i z2=-0.7+4.8i,顺序存储结构,链式存储结构,一、数据类型,22,第三节数据类型,数据类型是一个值的集合和定义在这个值集上的一组操作的总称如C语言中的整型变量(int)，其值集为某个区间上的整数，定义在其上的操作为+,-,x,/等,第章数据结构绪论,二、原子数据类型和结构数据类型,23,第三节数据类型,1.原子数据类型是不可分解的数据类型如C语言中的整型(int)，实型(float)，字符型(char)，指针类型(*)和空类型(void)

7、等,第章数据结构绪论,二、原子数据类型和结构数据类型,24,第三节数据类型,2.结构数据类型由若干成分（原子类型或结构类型）按某种结构组成的数据类型结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体如数组，由若干分量组成，每个分量可以是整数，也可以是数组（如int A10）,第章数据结构绪论,三、抽象数据类型（Abstract Data Type）,25,第三节数据类型,由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离,第章数据结构绪论,三、抽象数据类型（ADT）,26,第三节数据类型,抽象数据类型

8、（ADT）是一个数学模型以及定义在该模型上的一组操作抽象数据类型=数据结构+定义在此数据结 构上的一组操作,第章数据结构绪论,三、抽象数据类型（ADT表示）,27,第三节数据类型,抽象数据类型可用（D，S，P）三元组表示D是数据对象S是D上的关系集P是对D的基本操作集。,第章数据结构绪论,三、抽象数据类型（ADT定义）,28,第三节数据类型,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作(函数)的定义 ADT 抽象数据类型名,第章数据结构绪论,三、抽象数据类型（ADT定义举例）,29,第三节数据类型,ADT Triplet 数据对象：D=e1,e

9、2,e3|e1,e2,e3ElemSet 数据关系：R=,基本操作：Max(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最大值。Min(T,&e)初始条件：三元组T已存在。操作结果：用e返回T的3个元素中的最小值。ADT Triplet,第章数据结构绪论,三、抽象数据类型（ADT定义实现）,30,第三节数据类型,抽象数据类型可以通过固有数据类型(C语言中已实现的数据类型)来实现抽象数据类型 类 class数据对象 数据成员基本操作 成员函数(方法),第章数据结构绪论,一、算法（Algorithm）,31,第四节算法分析,算法是对特定问题求解步骤的一种描述是一有限长的操

10、作序列,第章数据结构绪论,一、算法（特性）,32,第四节算法分析,有穷性：算法在执行有穷步后能结束确定性：每步定义都是确切、无歧义可行性：每一条运算应足够基本(已验算正确)输入：有0个或多个输入输出：有一个或多个输出,第章数据结构绪论,一、算法（举例）,33,第四节算法分析,例子：选择排序问题：递增排序解决方案：逐个选择最小数据算法框架：for(int i=0;i n-1;i+)/n-1趟从ai检查到an-1，找到最小数;若最小整数在ak,交换ai与ak;,第章数据结构绪论,二、算法设计的要求,34,第四节算法分析,正确性：满足具体问题的需求可读性：便于理解和修改健壮性：当输入数据非法时，也能

11、适当反应效率高：执行时间少空间省：执行中需要的最大存储空间,第章数据结构绪论,三、时间复杂度,35,第四节算法分析,衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度事后统计法：计算算法开始时间与完成时间差值事前统计法：依据算法选用何种策略及问题的规模n，是常用的方法,第章数据结构绪论,三、时间复杂度,36,第四节算法分析,时间复杂度是问题规模n的函数f(n)，即：T(n)=O(f(n)一般地，时间复杂度用算法中最深层循环内的语句中的原操作的重复执行次数表示,第章数据结构绪论,三、时间复杂度,37,第四节算法分析,a.y*=x;b.for(i=1;i=n;i+y*=x;c.for(j=

12、1;j=n;j+for(i=1;i=n;i+y*=x;a,b,c三个算法中，“y*=x;”程序段的时间复杂度分别为O(1),O(n),O(n2)，分别称为常量阶，线性阶，平方阶,第章数据结构绪论,三、时间复杂度,38,第四节算法分析,时间复杂度除常量阶O(1),线性阶O(n),平方阶O(n2)外，还有对数阶O(logn)，排列阶O(n!)，指数阶O(2n)等，是相对于问题规模n的增长率的表示方法指数阶随问题规模增长过快，一般不宜使用,第章数据结构绪论,三、时间复杂度,39,第四节算法分析,如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度如果无法求取平均时间复杂度，则采用最坏情况下的时间

13、复杂度时间复杂度是衡量算法好坏的一个最重要的标准,第章数据结构绪论,四、空间复杂度,40,第四节算法分析,空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：S(n)=O(f(n),第章数据结构绪论,第二章线性表,数据结构,深圳大学计算机系 蔡茂国,一、线性数据结构的特点,42,第一节线性表,在数据元素的非空有限集中、存在惟一的一个被称作“第一个”的数据元素(如“”)、存在惟一的一个被称作“最后一个”的数据元素(如“”)、除第一个元素外，每个数据元素均只有一个前驱、除最后一个元素外，每个数据元素均只有一个后继(next)(如“1”的next是“2”,“2”的next是“3”

14、),第章线性表,二、线性表,43,第一节线性表,线性表是最简单的一类线性数据结构线性表是由n个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系，可以写为：(a1,a2,ai-1,ai,ai+1,an-1,an)其中,ai是表中元素,i表示元素ai的位置,n是表的长度,第章线性表,二、线性表,44,第一节线性表,线性表中的元素具有相同的特性，属于同一数据对象，如：1.26个字母的字母表:(A,B,C,D,Z)2.近期每天的平均温度:(30,28,29,),第章线性表,一、顺序表,45,第二节顺序表,顺序表是线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素,第章线性表,b b

15、+1 b+2 b+3 b+4 b+24 b+25,一、顺序表（元素位置）,46,第二节顺序表,顺序表数据元素的位置：LOC(a i)=LOC(a i-1)+l LOC(a i)=LOC(a1)+(i-1)*l l表示元素占用的内存单元 数,第章线性表,二、顺序表的定义,47,第二节顺序表,采用C语言中动态分配的一维数组表示顺序表,第章线性表,#define LIST_INIT_SIZE 100/线性表存储空间的初始分配量#define LISTINCREMENT 10/线性表存储空间的分配增量Typedef struct ElemType*elem;/存储空间基址intlength;/当前长度

16、int listsize;/当前分配的存储容量(元素数)Sqlist;,三、顺序表的初始化,48,第二节顺序表,创建一个顺序表L,第章线性表,Status InitList_Sq(Sqlist/InitList_Sq,三、顺序表的插入,49,第二节顺序表,顺序表的插入操作是指在顺序表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，即将长度为n的顺序表：(a1,ai-1,ai,an)变成长度为n+1的顺序表：(a1,ai-1,e,ai,an),第章线性表,三、顺序表的插入,50,第二节顺序表,在第3个元素与第4个元素之间插入新元素b需要将最后元素n至第4元素(共7-4+1)都向后移

17、一位置,第章线性表,三、顺序表的插入,51,第二节顺序表,第章线性表,Status ListInsert_Sq(Sqlist/ListInsert_Sq/请注意元素位置数值较元素序号少1,三、顺序表的插入,52,第二节顺序表,在顺序表中插入一个元素，需要向后移动元素个数为：n-i+1平均移动元素数为：n+1 Eis=pi x(n-i+1)i=1,第章线性表,三、顺序表的插入,53,第二节顺序表,当插入位置等概率时，pi=1/(n+1)，因此：n+1 Eis=1/(n+1)x(n-i+1)=n/2 i=1顺序表插入操作的时间复杂度为O(n),第章线性表,四、顺序表的删除,54,第二节顺序表,顺序

18、表的删除操作是指将顺序表的第i个数据元素删除，即将长度为n的顺序表：(a1,ai-1,ai,ai+1,an)变成长度为n-1的顺序表：(a1,ai-1,ai+1,an),第章线性表,四、顺序表的删除,55,第二节顺序表,将第4个元素删除需要将最后元素n至第5元素(共7-4)都向前移一位置,第章线性表,四、顺序表的删除,56,第二节顺序表,第章线性表,Status ListDelete_Sq(Sqlist/ListDelete_Sq,四、顺序表的删除,57,第二节顺序表,在顺序表中删除一个元素，需要向前移动元素个数为：n-i平均移动元素数为：n Edl=qi x(n-i)i=1,第章线性表,四、

19、顺序表的删除,58,第二节顺序表,当插入位置等概率时，qi=1/n，因此：n Edl=1/n x(n-i)=(n-1)/2 i=1顺序表删除操作的时间复杂度为O(n),第章线性表,五、顺序表的优缺点,59,第三节链表,优点：元素可以随机存取元素位置可用一个简单、直观的公式表示并求取缺点：在作插入或删除操作时，需要移动大量元素,第章线性表,一、链表,60,第二节线性链表,链表是线性表的链式存储表示链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系线性表的链式存储表示主要有三种形式：线性链表循环链表双向链表,第章线性表,二、线性链表,61,第二节线性链表,线性链

20、表的元素称为结点(node)结点除包含数据元素信息的数据域外，还包含指示直接后继的指针域每个结点，在需要时动态生成，在删除时释放,第章线性表,二、线性链表,62,第二节线性链表,动态单独生成结点的线性链表也称单链表线性链表可由头指针惟一确定为了操作方便，有时在线性链表的第一个结点之前附设一个头结点，其数据域可以为空，也可以为线性链表的长度信息。,第章线性表,三、线性链表的定义,63,第二节线性链表,定义一个结点typedef struct LNode ElemType data;/数据域struct LNode*next;/后继指针 LNode,*LinkList;,第章线性表,四、找指定元素

21、,64,第二节线性链表,在线性链表中找第i个元素由于线性链表中元素的存储位置具有随机性，因此，只有从头结点开始，顺链一步步查找,第章线性表,四、找指定元素,65,第二节线性链表,Status GetElem_L(LinkList/GetElem_L,第章线性表,四、找指定元素,66,第二节线性链表,算法时间复杂度主要取决于while循环中的语句频度频度与被查找元素在单链表中的位置有关若1in，则频度为i-1，否则为n因此时间复杂度为O(n),第章线性表,五、线性链表的插入,67,第二节线性链表,在线性链表的第i-1元素与第i元素之间插入一个新元素,第章线性表,s-next=p-next;p-n

22、ext=s;,五、线性链表的插入,68,第二节线性链表,Status ListInsert_L(LinkList/ListInsert_L,第章线性表,五、线性链表的插入,69,第二节线性链表,同样，算法时间复杂度主要取决于while循环中的语句频度频度与在线性链表中的元素插入位置有关因此线性链表插入的时间复杂度为O(n),第章线性表,六、线性链表的删除,70,第二节线性链表,将线性链表的第i元素删除,第章线性表,删除前,p-next=p-next-next,六、线性链表的删除,71,第二节线性链表,Status ListDelete_L(LinkList/ListDelete_L,第章线性表

23、,六、线性链表的删除,72,第二节线性链表,同样，算法时间复杂度主要取决于while循环中的语句频度频度与被删除元素在线性链表中的位置有关因此线性链表删除元素的时间复杂度为O(n),第章线性表,七、静态链表,73,第二节线性链表,线性链表也可以采用静态数组实现与顺序表有两点不同：、每个元素包括数据域和指针域、元素的逻辑关系由指针确定,第章线性表,0 1 2 3 4 5 6 7 8 9 10,数据指针,七、静态链表,74,第二节线性链表,与单链表区别：、静态链表暂时不用结点，链成一个备用链表、插入时，从备用链表中申请结点、删除结点时，将结点放入备用链表,第章线性表,一、循环链表,75,第三节循环

24、链表,循环链表是一种特殊的线性链表循环链表中最后一个结点的指针域指向头结点，整个链表形成一个环。,第章线性表,二、查找、插入和删除,76,第三节循环链表,在循环链表中查找指定元素，插入一个结点或删除一个结点的操作与线性链表基本一致差别仅在于算法中的循环条件不是p-next或p是否为空()，而是它们是否等于头指针(L),第章线性表,一、双向链表,77,第四节双向链表,双向链表也是一种特殊的线性链表双向链表中每个结点有两个指针，一个指针指向直接后继(next)，另一个指向直接前驱(prior),第章线性表,二、双向循环链表,78,第四节双向链表,双向循环链表中存在两个环(一个是直接后继环(红)，另

25、一个是直接前驱环(蓝),第章线性表,三、双向链表的定义,79,第四节双向链表,定义一个双向链表的结点Typedef struct DuLNode ElemTypedata;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkList;,第章线性表,对于任何一个中间结点有：p=p-next-priorp=p-prior-next,四、双向链表的插入,80,第四节双向链表,双向链表的插入操作需要改变两个方向的指针,第章线性表,s-next=p;s-prior=p-prior;p-prior-next=s;p-prior=s;,四、双向链表

26、的删除,81,第四节双向链表,双向链表的删除操作需要改变两个方向的指针,第章线性表,L,p-prior-next=p-next;p-next-prior=p-prior;,一、基于空间的比较,82,第五节顺序表与链表的比较,存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度 1,第章线性表,二、基于时间的比较,83,第五节顺序表与链表的比较,存取方式顺序表可以随机存取，也可以顺序存取链表必须顺序存取插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针,

27、第章线性表,三、基于应用的比较,84,第五节顺序表与链表的比较,如果线性表主要是存储大量的数据，并主要用于查找时，采用顺序表较好，如数据库如果线性表存储的数据元素经常需要做插入与删除操作，则采用链表较好，如操作系统中进程控制块(PCB)的管理，内存空间的管理等,第章线性表,第三章栈和队列,数据结构,深圳大学计算机系 蔡茂国,一、栈,86,第一节栈,栈是限定仅在表尾(top)进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top，表尾)，另一端称为栈底(bottom，表头)特点：后进先出(LIFO),第章栈和队列,二、栈的实现,87,第一节栈,栈的存储结构主要有两种：1.顺序栈2.链式

28、栈,第章栈和队列,一、顺序栈,88,第二节顺序栈,顺序栈是栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。,第章栈和队列,二、顺序栈的定义,89,第二节顺表栈,采用C语言中动态分配的一维数组表示顺序表,第章栈和队列,#define STACK_INIT_SIZE 100/栈存储空间的初始分配量#define STACKINCREMENT 10/栈存储空间的分配增量Typedef struct SElemType*base/存储空间基址SElemType*top;/当前长度int stack

29、size;/当前分配的存储容量(元素数)SqStack;,三、顺序栈的特性,90,第二节顺序栈,top=0 或top=base 表示空栈base=NULL表示栈不存在当插入新的栈顶元素时,指针top+1删除栈顶元素时，指针top-1当topstacksize时，栈满，溢出,第章栈和队列,四、顺序栈的主要操作,91,第二节顺序栈,第章栈和队列,ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,3,n 数据关系：R=|ai-1,aiD 基本操作：InitStack(&S)/构造空栈 Push(&S,e)/进栈 Pop(&S,&e)/出栈 GetTop(S,&e)/取栈顶元素值

30、StackEmpty(S)/栈是否为空 ADT Stack,五、创建顺序栈,92,第二节顺序栈,第章栈和队列,Status InitStack(SqStack/InitStack,六、进栈（插入新元素）,93,第二节顺序栈,第章栈和队列,Status Push(SqStack/Push,七、出栈（删除元素）,94,第二节顺序栈,第章栈和队列,Status Pop(SqStack/Pop,八、取栈顶元素,95,第二节顺序栈,第章栈和队列,Status GetTop(SqStack S,SElemType/GetTop,一、数值转换,96,第三节栈的应用举例,将十进制转换为其它进制(d)，其原理为

31、：N=(N/d)*d+N mod d例如：（1348)10=(2504)8，其运算过程如下：N N/8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,第章栈和队列,一、数值转换,97,第三节栈的应用举例,void conversion()InitStack(S);/创建新栈S scanf(“%d”,N);/输入一个十进制数N while(N)Push(S,N%8);/将余数送入栈中 N=N/8;/求整除数 while(!StackEmpty(S)/如果栈不空 Pop(S,e);/将栈中数出栈 printf(%d,e);/conversion,第章栈和队列,二、

32、行编辑程序,98,第三节栈的应用举例,用户输入一行字符允许用户输入出差错，并在发现有误时，可以用退格符“#”及时更正假设从终端接受两行字符：whli#ilr#e（s#*s)实际有效行为：while(*s),第章栈和队列,二、行编辑程序,99,第三节栈的应用举例,对用户输入的一行字符进行处理，直到行结束(“n”)ch=getchar();/从终端输入一个字符while(ch!=n)switch(ch)case#:Pop(S,c);break;/仅当栈非空时退栈default:Push(S,ch);break;/有效字符进栈ch=getchar();/从终端输入一个字符将从栈底到栈顶的栈内字符传送

33、到调用过程的数据区;,第章栈和队列,三、迷宫求解,100,第三节栈的应用举例,迷宫求解一般采用“穷举法”逐一沿顺时针方向查找相邻块（一共四块东(右)、南(下)，西(左)、北(上)）是否可通，即该相邻块既是通道块，且不在当前路径上用一个栈来记录已走过的路径,第章栈和队列,三、迷宫求解,101,第三节栈的应用举例,举例,第章栈和队列,三、迷宫求解（算法）,第三节栈的应用举例,设定当前位置为入口位置do 若当前位置可通，则 将该位置插入栈顶(Push)；若该位置是出口，则结束否则切换当前位置的东邻方块为当前位置；否则 若栈不空则 如果栈顶位置的四周均不可通,则删除栈顶位置(Pop)并重新测试新的栈顶

34、位置如果找到栈顶位置的下一方向未经探索，则将该方向方块设为当前位置while(栈不空)；找不到路径；,第章栈和队列,四、表达式求值,103,第三节栈的应用举例,表达式由操作数、运算符和界限符组成，它们皆称为单词操作数：常数或变量运算符：+,-,*,/等界限符：(,),#(表达式开始及结束符),第章栈和队列,四、表达式求值,104,第三节栈的应用举例,设置两个栈：操作数栈（OPND）运算符栈（OPTR）,第章栈和队列,四、表达式求值,105,第三节栈的应用举例,运算符的优先级关系,第章栈和队列,新运算符,运算符栈顶元素,四、表达式求值（算法）,第三节栈的应用举例,置运算符栈(OPTR)和操作数栈

35、(OPND)为空#插入OPTR栈；取表达式第一个单词；while(单词 或 OPTR栈顶元素不为#)若单词是操作数，则插入OPND栈顶，且取下一个单词否则 OPTR栈顶元素优先级与新运算符优先级关系为：小于，则插入OPTR栈顶，取下一单词等于，则删除OPTR栈顶元素，取下一单词大于，则从OPND栈顶依次取出两个操作数，用从OPTR栈顶取出的元素进行计算，结果插入OPND栈顶,第章栈和队列,从栈顶取出元素，包括取值及删除栈顶元素两个过程,一、队列,107,第四节队列,队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头(f

36、ront)。特点：先进先出(FIFO),第章栈和队列,二、顺序队列,108,第四节队列,顺序队列：采用一组地址连续的存储单元依次存储从队列头到队列尾的元素顺序队列有两个指针：队头指针front和队尾指针rear,第章栈和队列,三、顺序队列的进队和出队原则,109,第四节队列,进队时，新元素按rear指针位置插入，然后队尾指针增一，即 rear=rear+1出队时，将队头指针位置的元素取出，然后队头指针增一，即 front=front+1队头指针始终指向队列头元素队尾指针始终指向队列尾元素的下一个位置,第章栈和队列,四、顺序队列的进队和出队举例,110,第四节队列,第章栈和队列,front,re

37、ar,空队列,front,rear,A,B,C,D进队,front,rear,A退队,front,rear,B退队,front,rear,E,F,G进队,front,rear,H进队,溢出,五、顺序队列存在的问题,111,第四节队列,当队尾指针指向队列存储结构中的最后单元时，如果再继续插入新的元素，则会产生溢出当队列发生溢出时，队列存储结构中可能还存在一些空白位置（已被取走数据的元素）解决办法之一：将队列存储结构首尾相接，形成循环(环形)队列,第章栈和队列,一、循环队列,112,第五节循环队列,循环队列采用一组地址连续的存储单元将整个队列的存储单元首尾相连,第章栈和队列,二、循环队列空与满,1

38、13,第五节循环队列,front=rear，循环队列空(rear+1)%MAXQSIZE=front，循环队列满,第章栈和队列,队列满,三、循环队列定义,114,第五节循环队列,#define MAXQSIZE 100Typedef struct QElemType*base;int front;int rear;SqQueue;,第章栈和队列,三、循环队列插入元素,115,第五节循环队列,Status EnQueue(SqQueue,第章栈和队列,三、循环队列删除元素,116,第五节循环队列,Status DeQueue(SqQueue,第章栈和队列,一、链队列,117,第六节链队列,链队列

39、采用链表存储单元链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。,第章栈和队列,二、链队列指针变化状况,118,第六节链队列,链队列是链表操作的子集,第章栈和队列,第四章串,数据结构,深圳大学计算机系 蔡茂国,一、字符串（string）,120,第一节字符串,字符串是n(0)个字符的有限序列，记作：S=a1a2a3an其中，S 是串名字 a1a2a3an是串值 ai 是串中字符 n 是串的长度(串中字符的个数)例如,S=“Shenzhen University”,第章串,二、字符串术语,121,第一节字符串,空串：不含任何字符的串，串长度=0空格串：仅由一个

40、或多个空格组成的串子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。如：A=Shenzhen University B=University A为主串，B为子串。,第章串,二、字符串术语,122,第一节字符串,位置：字符在序列中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。模式匹配：确定子串在主串中首次出现的位置的运算,第章串,三、字符串与线性表的关系,123,第一节字符串,串的逻辑结构和线性表极为相似，它们都是线性结构串中的每个字符都仅有一个前驱和一个后继,第章串,三、字符串与线性表的关系,12

41、4,第一节字符串,串与线性表又有区别，主要表现为：串的数据对象约定是字符集在线性表的基本操作中，以“单个元素”作为操作对象在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。,第章串,一、定长顺序存储表示,125,第二节串的表示和实现,用一组地址连续的存储单元存储字符序列如C语言中的字符串定义(以“0”为串结束标志)char StrMAXSTRLEN+1;定义了长度为MAXSTRLEN字符存储空间字符串长度可以是小于MAXSTRLEN的任何值（最长串长度有限制，多余部分将被截断）,第章串,二、堆分配存储表示,126,第二节串的表示和实现,在

42、程序执行过程中，动态分配（malloc）一组地址连续的存储单元存储字符序列在C语言中，由malloc()和free()动态分配与回收的存储空间称为堆堆分配存储结构的串既有顺序存储结构的特点，处理方便,操作中对串长又没有限制,更显灵活,第章串,三、链存储表示,127,第二节串的表示和实现,采用链表方式存储串值每个结点中，可以存放一个字符，也可以存放多个字符,第章串,一、求子串位置函数Index(),128,第三节串的匹配算法,子串的定位操作通常称做串的模式匹配算法（穷举法）：从主串的指定位置开始，将主串与模式（要查找的子串）的第一个字符比较，1.若相等，则继续逐个比较后续字符；2.若不等，从主串

43、的下一个字符起再重新和模式的字符比较,第章串,一、求子串位置函数Index(),129,第三节串的匹配算法,Int Index(Sstring S,Sstring T,int pos)/S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构i=pos;j=1;/从第一个位置开始比较while(i T0)return i-T0;/返回与模式第一字符相等else return 0;/匹配不成功/的字符在主串中的序号,第章串,一、求子串位置函数Index(),130,第三节串的匹配算法,在最好的情况下，除比较成功的位置外，其余位置仅需比较一次（模式第一个字符），其时间复杂度为：O(n+m)(

44、n，m分别为主串和模式的长度)但在最坏的情况下，如模式为00000001，主串为0000000000000000000000000000000001,则每次模式的前7个0都要与主串逐一比较，因此，其时间复杂度为：O(n*m),第章串,二、KMP算法,131,第三节串的匹配算法,是index函数的一种改进,由D.E.Knuth(克努特)J.H.Morris(莫里斯)V.R.Pratt(普拉特)发现当一趟匹配过程中出现字符比较不等(失配)时1.不需回溯i指针2.利用已经得到的“部分匹配”的结果3.将模式向右“滑动”尽可能远的一段距离(nextj)后，继续进行比较,第章串,二、KMP算法(举例),1

45、32,第三节串的匹配算法,假设主串ababcabcacbab,模式abcac,改进算法的匹配过程如下 i=3 第一趟匹配 a b a b c a b c a c b a b a b c j=3 i=3-7 第二趟匹配 a b a b c a b c a c b a b a b c a c j=1 i=7-10 第三趟匹配 a b a b c a b c a c b a b a b c a c j=2,第章串,二、KMP算法,133,第三节串的匹配算法,假设主串为s1s2s3sn,模式串为p1p2p3pm若主串中第i个字符与模式串中第j个字符“失配”(si!=pj),需要与模式串中第k(kj)个

46、字符比较,则有以下关系成立：p1p2pk-1=si-k+1si-k+2si-1而已经得到的“部分匹配”结果为：pj-k+1pj-k+2pj-1=si-k+1si-k+2si-1,第章串,二、KMP算法,134,第三节串的匹配算法,从而有下式成立：p1p2pk-1=pj-k+1pj-k+2pj-1上式是只依赖于模式串的关系式上式说明,在主串中第i个字符“失配”时,仅需与模式串中的第k个字符再开始比较（不需要回溯）,第章串,二、KMP算法,135,第三节串的匹配算法,或者换言之,在模式串中第j个字符“失配”时,模式串第k个字符再同主串中对应的失配位置(i)的字符继续进行比较 p1p2pk-1=pj

47、-k+1pj-k+2pj-1k值可以在作串的匹配之前求出一般用next函数求取k值,第章串,二、KMP算法(next函数),136,第三节串的匹配算法,next函数定义为：0当j=1时nextj=maxk|1kj且p1pk-1=pj-k+1pj-11其它情况如k=2,则p1=pj-1(有1个字符相同)除j=2外;k=3,则p1p2=pj-2pj-1(有2个字符相同);,第章串,二、KMP算法(next函数举例),137,第三节串的匹配算法,现有模式串abcac,求其next值,第章串,二、KMP算法(next函数举例),138,第三节串的匹配算法,现有模式串abaabacaca,求其next值

48、,第章串,二、KMP算法(利用next函数),139,第三节串的匹配算法,利用next函数,可写出KMP算法如下：1.令i的初值为pos,j的初值为12.While(i主串长度)且(j模式串长度)(1).若j=0或者si=pj,则i+,j+(2).否则,j=nextj j=0表示第一个字符失配,第章串,二、KMP算法(C语言实现),140,第三节串的匹配算法,Int Index_KMP(Sstring S,Sstring T,int pos)/S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构i=pos;j=1;/从第一个位置开始比较while(i T0)return i-T0;/

49、返回与模式第一字符相等else return 0;/匹配不成功/的字符在主串中的序号,第章串,二、KMP算法(时间复杂度),141,第三节串的匹配算法,Index_KMP()函数的时间复杂度为O(n)为了求模式串的next值,其算法与Index_KMP很相似,其时间复杂度为O(m)因此,KMP算法的时间复杂度为O(n+m),第章串,第六章树与二叉树,数据结构,深圳大学计算机系 蔡茂国,一、树的定义(Tree),143,第一节树的概念与基本术语,树是有n(n0)个结点的有限集合。如果 n=0，称为空树；如果 n0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱)如

50、果 n1，则除根以外的其它结点划分为 m(m0)个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。每个结点都有唯一的直接前驱，但可能有多个后继,第章树与二叉树,一、树的定义(举例),144,第一节树的概念与基本术语,其中：A是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L；T2=C,G；T3=D,H,I,J,M,T1,T2,T3都是根A的子树，且本身也是一棵树,第章树与二叉树,A,只有根结点的树,有13个结点的树,二、树的基本术语,145,第一节树的概念与基本术语,结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的