数据结构教学课件（完整版）.ppt

数据结构教学课件（完整版）.ppt

《数据结构教学课件（完整版）.ppt》由会员分享，可在线阅读，更多相关《数据结构教学课件（完整版）.ppt（465页珍藏版）》请在冰点文库上搜索。

,全,册,课,件,延迟符,数据结构全套课件,数据结构,NorthChinaElectricPowerUniversity,DataStructure,第一章绪论,课程简介,基本概念,算法,算法语言的说明,NorthChinaElectricPowerUniversity,开设本课程的必要性以及课程的特点：

1.计算机专业重要的专业基础课之一.,2.需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.,3.实践性较强.,NorthChinaElectricPowerUniversity,课程简介,在计算机发展的初期，计算机主要用于科学计算，因此程序设计者的主要精力集中在程序设计的技巧上，而不重视数据结构。

当时处理一个计算问题的一般步骤为：

具体数值问题数学模型设计算法编程,抽象出,例如：

桥梁结构的应力计算（结构静力分析、线性代数方程）,例如：

全球天气预报（环流模式方程）,例如：

预报人口增长率（微分方程）,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,随着计算机的推广普及，计算机越来越多地应用于非数值领域，使人们逐渐认识到选择一门好的数据结构，从而设计一种好的算法是得到一个好的程序的基础。

算法+数据结构=程序（NiklausWirth）（Algorithm+Datastructure=Program）,程序：

为计算机处理问题编写的一组指令。

算法：

处理问题的策略。

数据结构：

问题的数学模型。

例如：

铺设煤气管道问题,A,B,C,D,I,H,G,E,F,18.2,32.8,44.6,12.1,8.7,56.4,21.3,41.1,67.3,10.5,85.6,98.7,52.5,79.2,A,B,C,D,I,H,G,E,F,32.8,12.1,8.7,21.3,41.1,10.5,79.2,（a）居民区示意图,（b）铺设煤气管道设计图,NorthChinaElectricPowerUniversity,例如：

酒店客房管理系统中的客房分配问题,例人机对奕问题,NorthChinaElectricPowerUniversity,例如：

图书馆的书目检索问题,NorthChinaElectricPowerUniversity,数据结构：

按照某种逻辑结构组织的一组数据，按一定的存储方式将它们映射到计算机的存储器中，并且在这些数据上定义了一个运算的集合，运算的结果保持原来的结构。

NorthChinaElectricPowerUniversity,1.研究数据元素之间的客观联系。

2.研究具有某种逻辑关系的数据在计算机存储器内的存储方式。

3.研究如何在数据的各种结构（逻辑的和物理的）的基础上对数据实施一系列有效的基本操作。

逻辑结构,存储结构,算法,基本概念,数据：

所有能输入到计算机中并为计算机程序处理的对象的集合。

2.数据元素：

数据的基本单位，在程序中作为一个整体加以考虑和处理。

3.数据项：

数据处理的最小单位。

980604,刘晔,女,18,80,10,学号,姓名,性别,年,月,日,组合项,原子项,出生日期,（学生情况）,NorthChinaElectricPowerUniversity,4.数据对象：

性质相同的数据元素的集合。

5.数据的逻辑结构：

对数据元素之间逻辑关系的描述。

它可以用一个数据元素的集合和定义在这个集合上的若干关系来表示。

DataStructure=（D,S）D:

数据元素的集合;S:

D上关系的集合,1）集合：

集合中任何两个结点之间都没有逻辑关系，组织形式松散。

2）线性结构：

元素之间存在着一对一的关系。

依次排列形成一条“锁链”。

NorthChinaElectricPowerUniversity,3）树形结构：

数据元素之间存在着一对多的关系，具有分支、层次特性。

4）图状结构：

数据元素之间存在多对多的关系，元素之间互相缠绕，任何两个元素都可以邻接。

6.数据的存储结构：

数据在计算机中的表示，包括数据元素的表示和关系的表示。

1）顺序存储方式（向量存储）,2）链式存储方式,3）索引存储方式,4）散列存储方式,NorthChinaElectricPowerUniversity,7.数据类型：

一个值的集合和定义在这个值上的一组操作。

8.抽象数据类型：

一个数学模型和定义在这个数学模型的一组操作。

特性,数据抽象：

用ADT描述程序处理的实体时，强调的是其本质的特征，其完成的功能以及和外部的接口。

数据封装：

将实体的外部特性和其内部实现分离，并对外部用户隐藏其内部实现细节。

ADT抽象数据类型名,数据对象：

数据关系：

基本操作：

ADT抽象数据类型名,NorthChinaElectricPowerUniversity,例如:

抽象数据类型复数的定义,ADTComplex数据对象：

D=e1,e2|e1,e2Realset数据关系：

R1=|e1是复数的实数部分、e2是复数的虚数部分基本操作：

InitComplex（v1,v2）DestroyComplex（Z）GetReal（Z,realPart）GetImag（Z,ImagPart）Add（Z1,Z2,Sum）Subtract（Z1,Z2,Difference）Multiply（Z1,Z2,Product）ADTComplex,注：

对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，则可形成不同的抽象数据类型。

NorthChinaElectricPowerUniversity,算法,算法：

解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。

NorthChinaElectricPowerUniversity,算法设计的原则,1.正确性,a.程序中不含语法错误,b.程序对于几组给定的输入数据能得出满足要求的结果,c.程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入能得出满足要求的结果,d.程序对一切合法输入都能得出满足要求的结果,2.可读性：

算法主要是为了人的阅读与交流，其次才是为了计算机执行，因此算法应该易于理解；另外，晦涩难懂的程序易于隐藏较多错误而难于调试,3.健壮性：

当输入的数据非法时，算法应当恰当地做出反应或进行相应的处理，而不是产生莫名其妙的错误输出；并且处理错误的方法不应该是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次进行处理,4.高效率和低存储量需求：

效率：

指算法的执行时间存储量：

算法执行过程中所需的最大存储空间两者都与问题的规模有关,NorthChinaElectricPowerUniversity,算法的复杂性,复杂性：

指实现或运行某一算法所需资源的多少。

时间复杂性,空间复杂性,人工复杂性（指编程、调试等所需的人工）,NorthChinaElectricPowerUniversity,和算法执行时间相关的因素：

1.算法选用的策略,2.问题的规模,3.编写程序的语言,4.编译程序产生的机器代码的质量,5.计算机执行指令的速度,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n来表示），或者说它是问题规模的函数。

算法的时间复杂性：

假如随着问题规模n的增长，算法执行时间的增长率和f（n）的增长率相同，则记作T（n）=O（f（n），称T（n）为算法的时间复杂性。

算法时间复杂性的度量：

任何一个算法都是由一个控制结构和若干原子操作组成,算法的执行时间=原操作（i）的执行次数*原操作（i）的执行时间,因为原操作的执行时间相对问题的规模n而言是个常量，所以算法的执行时间与原操作执行次数之和成正比。

从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。

这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。

NorthChinaElectricPowerUniversity,例如：

k=k+1时间复杂度为O

（1）,例如：

for（i=0;in;i+）k=k+1时间复杂度为O（n）,例如：

for（i=0;in;i+）for（j=0;jn;j+）k=k+1时间复杂度为O（n2）,例如：

for（i=0;in;i+）for（j=0;jn;j+）cij=0;for（k=0;kn;k+）cij=cij+aik*bkj;时间复杂度为O（n3）,NorthChinaElectricPowerUniversity,-n+1-n（n+1）-n2-n2（n+1）-n3,对于足够大的n，存在下述关系：

O（logn）O（n）O（nlogn）O（n2）O（n3）,O（2n）O（3n）O（n!

）,算法的空间复杂性：

假如随着问题规模n的增长，算法执行所需存储量的增长率和g（n）的增长率相同，则记作S（n）=O（g（n），称S（n）为算法的空间复杂性。

算法的存储量：

算法执行过程中所需的最大存储空间。

NorthChinaElectricPowerUniversity,1.采用自然语言来描述,问题：

求两个正整数M与N的最大公因子。

（1）M除以N，将余数送中间变量R；

（2）测试余数R是否等于零？

a）若R等于零，求得的最大公因子为当前N的值,算法到此结束。

b）若R不等于零，将N送入M，将R送N,重复算法的

（1）和

（2）。

NorthChinaElectricPowerUniversity,分类：

1.非形式算法（自然语言算法）,2.流程图语言,3.程序设计语言描述的算法,算法描述语言：

4.伪语言描述的算法,2.采用程序流程图的形式来描述,NorthChinaElectricPowerUniversity,3.采用某种具体程序语言来描述,COMFACTOR（intM,intN）intR;while

（1）R=M%N;if（R=0）returnN;M=N;N=R;,NorthChinaElectricPowerUniversity,来自对C语言的修改，它描述的算法是不能直接在机器上执行的程序过程。

它与标准C的主要区别如下：

局部变量的说明可以省略（但形参表中及函数类型的说明必须保留），重要的变量须在注解中说明其类型和作用。

2.算法写成函数的形式。

函数类型函数名（函数参数表）/算法说明语句序列;/函数名,NorthChinaElectricPowerUniversity,类C语言说明,3.在函数中除了值调用方式之外，增添了C+语言的引用调用的参数传递方式。

在形参表中，以&打头的参数即为引用参数，引用参数能被函数本身更新值，可以作为输出数据的管道。

4.内存的动态分配与释放使用new和delete动态分配和释放内存空间。

分配空间指针变量=new数据类型；释放空间delete指针变量；,5.不含goto语句，增加以下两条语句:

1）出错处理语句：

Error（字符串），其功能是终止它所在算法的执行，并回送表示出错信息的字符串。

2）返回语句：

Return和Return（表达式），其功能是终止函数的执行，Return（表达式）终止函数的执行并将表达式的值回传给函数名。

6.在算法中任何处均可插入/,进行单行注释。

NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,数据结构,NorthChinaElectricPowerUniversity,DataStructure,第二章线性表,线性表,栈,队列,NorthChinaElectricPowerUniversity,线性表的逻辑结构：

线性表是0个或多个元素的有穷序列，通常可表示成a1,a2,a3,ai,an（n0）,线性表,n:

线性表的表长n=0时称为空表n1时，a1称为第一个元素，an称为最后一个元素ai称为ai+1的前驱，ai+1称为ai的后继，i称为序号或索引,特点：

除第一个和最后一个元素外，每个元素有且只有一个直接前驱和一个直接后继。

NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,线性表的例子：

例1.一副扑克牌中同一花色的13张牌组成一个线性表（A,2,3,4,5,6,7,8,9,10,J,Q,K）,例2.人民币面值的所有种类组成一个线性表（1角，2角，5角，1元，2元，5元，10元，20元，50元，100元）,例3.一本书可以看成是一个线性表，每一页是一数据元素,例4.学生的学籍档案构成一个线性表,数据元素,数据项,线性表的基本运算：

NorthChinaElectricPowerUniversity,1.Initial（&L）:

初始化操作，设定一个空的线性表L。

2.Length（L）:

返回线性表的表长。

3.Get（L,i）:

若1iLength（L）,返回线性表的第i个元素。

4.Locate（L,x）:

若L中存在一个或多个值和x相等，运算结果为这些元素序号的最小值，否则返回0。

5.Insert（&L,i,x）:

在线性表的第i个位置插入一新元素x。

6.Delete（&L,i）:

删除线性表L的第i个元素。

7.Empty（L）:

若线性表L为空返回True,否则返回False。

线性表的其它运算：

如求任一元素的直接前驱或直接后继；合并两个线性表；线性表的拆分；线性表的复制；对线性表按照值的大小进行排序等操作。

NorthChinaElectricPowerUniversity,线性表基本运算的应用示例：

例1.设有两个线性表La和Lb，现将La和Lb合并成一个新表存于La中。

voidUnion（Linear_list,思考题：

例2.判断两个集合A和B是否相等。

intCompare（Linear_listLa,Linear_listlb）/若La和Lb不仅长度相等，而且所含元素也相同则返回1Len_la=Length（La）;Len_lb=Length（Lb）;if（Len_la!

=Len_lb）return（0）;elsefor（k=1;k=Len_la;k+）x=Get（La,k）;m=Locate（Lb,x）;if（m=0）return（0）;return

（1）;,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,线性表的顺序存储：

用一块连续的存储单元依次存放线性表的各个元素。

内存状态,存储地址,元素在线性表中的次序,b=Loc（a1）,b+c,b+（i-1）*c,b+（n-1）*c,b+（max-1）*c,1,2,i,n,空闲,a1,a2,ai,an,顺序存储的线性表的寻址公式：

顺序存储的优点：

1.可以随机存取,2.空间利用率高,3.结构简单,Loc（ai）=Loc（a1）+（i-1）*c1in,Loc（a1）为线性表的第一个元素a1的存储地址,c为每个元素所占的存储单元,线性表的顺序存储可以借用数组类型来实现,NorthChinaElectricPowerUniversity,顺序表的基本运算的实现：

1）在顺序表L的第i个位置上插入一个新元素x,插入前：

元素,序号,1,2,3,4,5,6,7,8,插入27,插入后：

元素,序号,1,2,3,4,5,6,7,8,9,主要操作：

1.将第i到n个元素依次后移一个位置,2.将新元素x放到顺序表的第i个位置上,3.将顺序表的表长由n修改为n+1,28,31,43,78,11,14,25,20,28,31,43,78,11,14,25,20,27,NorthChinaElectricPowerUniversity,在顺序表L的第i个位置上插入新元素x的算法,voidInsert（Linear_list/线性表的长度加1,在一个长度为n的线性表中插入一元素时需移动元素的平均次数为,Ein=Pj*（n-j+1）=n/2（当Pj=1/（n+1）j=1,2,n,n+1）,1,n+1,算法的时间复杂性为O（n）,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,2）删除顺序表L的第i个元素,删除前：

元素,序号,1,2,3,4,5,6,7,8,删除,插入后：

元素,序号,1,2,3,4,5,6,7,主要操作：

1.将第i+1到n个元素依次前移一个位置,2.将顺序表的表长由n修改为n-1,28,31,43,78,11,14,25,20,43,78,11,14,28,20,31,NorthChinaElectricPowerUniversity,删除顺序表L的第i个元素的算法,voidDelete（Linear_list,在一个长度为n的顺序表中删除一元素时需移动元素的平均次数为,Ede=Pj*（n-j）=（n-1）/2（当Pj=1/nj=1,2,n）,算法的时间复杂性为O（n）,3）定位运算：

求x在顺序表L中的最小序号,元素,序号,1,2,3,4,5,6,7,8,28,31,43,78,11,14,25,20,28,x,intLocate（Linear_listL,ElemTypex,intn）/在L中查找第一个值和x相等的元素，若存在，返回该元素L中/的序号，否则返回0i=1;while（i=n）,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,4）顺序表的其他算法举例,例1.按照字典序比较两个线性表A和B的大小,intCompare（Linear_listA,Linear_listB/若AB,则返回1j=1;while（jBj）return

（1）;elsej=j+1;if（Length（A）=Length（B）return（0）;elseif（Length（A）Length（B）return（-1）;elsereturn

（1）;,NorthChinaElectricPowerUniversity,例2.归并两个“其数据元素按值非递减有序”的线性表La,Lb,使求得的线性表Lc也具有同样的特性。

voidMerge（Linear_listLa,Lineare_ListLb,Linear_list,voidDel（Linear_ListA,int,NorthChinaElectricPowerUniversity,顺序存储的缺点：

1.需要一片地址连续的存储空间;2.插入和删除元素时不方便，大量的时间用在元素的搬家上;,2.在预分配存储空间时，可能造成空间的浪费;,3.表的容量难以扩充。

NorthChinaElectricPowerUniversity,解决的方案：

1.对顺序表的插入和删除运算进行限定,2.采用其它的存储结构（链式存储）,栈,NorthChinaElectricPowerUniversity,栈的逻辑结构,栈：

所有的插入和删除都只能在表尾（栈顶）进行的线性表。

允许进行插入和删除操作的一端叫栈顶，不允许插入和删除的一端叫栈底。

没有元素的栈叫空栈。

a1,栈底,栈顶,插入,删除,若给定栈S=（a1,a2,an）,则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,an顺序进栈，按an,a2,a1顺序出栈。

通常把栈称为先进后出的线性表。

因此栈中数据元素的逻辑关系是先进后出（FILO）。

an,a2,a1,NorthChinaElectricPowerUniversity,栈的举例：

1）装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的那个球却被第一个取走。

2）假定有一个问题P,它的解决依赖于两个子问题A和E的解决，而子问题A的解决又依赖于子问题B和C的解决，问题C的解决依赖于问题D的解决。

P,A,E,B,C,D,1,2,3,4,5,6,7,8,10,11,12,9,解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），绿色的箭头表示问题已经解决（或子问题出栈）。

栈一般用来容纳被接受了的而还没有进行处理的信息。

NorthChinaElectricPowerUniversity,栈的基本运算：

1.InitStack（&S）:

初始化操作，设定一个空栈S。

2.PushStack（&S,x）:

将元素x压入到栈S中。

3.PopStack（&S）:

当栈S不空时弹出栈顶元素。

4.TopStack（S）:

当栈S不空时返回栈顶元素。

5.EmptyStack（S）:

若栈S为空，返回True,否则返回False。

栈的顺序存储结构：

S:

top,S1,S2,Si,Stop,maxsize,S：

表示栈S1:

表示底一个进栈的元素S2:

表示第2个进栈的元素Si:

表示第i个进栈的元素Stop:

表示栈顶元素top=0:

表示栈空top=maxsize:

表示栈满,空闲空间,ai,a2,a1,NorthChinaElectricPowerUniversity,栈的基本运算在顺序存储结构上的实现：

1）PushStack（&S,x）:

将元素x压入到栈S中。

voidPushStack（Stack,2）PopStack（&S）:

当栈S不空时弹出栈顶元素。

ProcedurePopStack（Stack,上面两个元素的时间复杂性均为O

（1），压栈和退栈时不需移动元素,NorthChinaElectricPowerUniversity,双重栈,STACK1:

m,top1、top2分别为第1个与第2个栈的栈顶元素的指针。

插入：

当i=1时，将item插入第1个栈，当i=2时，将item插入第2个栈。

可用空间,123m,第1个栈,第2个栈,top1top2,初始条件：

top1=0top2=m+1,123M,第1个栈,第2个栈,可用空间,123M,第1个栈,第2个栈,top1top2,top1top2,栈满的条件是,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,双重栈的基本运算的实现：

1）PushStack（&S,i,x）:

将元素x压入到第i个栈中。

ProcedurePushStack（Stack,2）PopStack（S,i）:

当第i个栈不空时弹出其栈顶元素。

ProcedurePushStack（Stack,NorthChinaElectricPowerUniversity,栈的应用举例：

num=39110,6078,391/8487,6/806,7,0,6,48/860,voidchange（intnum）top=0while（num0）top=top+1;Stacktop=num%8;/余数进栈num=num/8;while（top0）printf（Stacktop）;top=top-1;/退栈,NorthChinaElectricPowerUniversity,NorthChinaElectricPowerUniversity,例2.扩号匹配问题：

假设表达式中有两种扩号,圆括号和方括号,即