数据结构课件(全)全书教学教程完整版电子教案最全幻灯片.ppt

数据结构数据结构North China Electric Power UniversityData Structure 第一章第一章 绪绪 论论 课程简介课程简介 基本概念基本概念 算法算法 算法语言的说明算法语言的说明North China Electric Power University开设本课程的必要性以及课程的特点：开设本课程的必要性以及课程的特点：1.计算机专业重要的专业基础课之一计算机专业重要的专业基础课之一.2.需要有关需要有关“程序设计语言程序设计语言”和和“离散数学离散数学”的知识作为课程的基础的知识作为课程的基础.3.实践性较强实践性较强.North China Electric Power University 课程简介课程简介在计算机发展的初期，计算机主要用于科在计算机发展的初期，计算机主要用于科学计算，因此程序设计者的主要精力集中在程学计算，因此程序设计者的主要精力集中在程序设计的技巧上，而不重视数据结构。当时处序设计的技巧上，而不重视数据结构。当时处理一个计算问题的一般步骤为：理一个计算问题的一般步骤为：具体数值问题具体数值问题 数学模型数学模型 设计算法设计算法 编程编程抽象出抽象出 例如：桥梁结构的应力计算例如：桥梁结构的应力计算 （结构静力分析、线性代数方程）（结构静力分析、线性代数方程）例如：全球天气预报（环流模式方程）例如：全球天气预报（环流模式方程）例如：预报人口增长率（微分方程）例如：预报人口增长率（微分方程）North China Electric Power UniversityNorth China Electric Power University 随着计算机的推广普及，计算机越来越多随着计算机的推广普及，计算机越来越多地应用于非数值领域，使人们逐渐认识到选择地应用于非数值领域，使人们逐渐认识到选择一门好的数据结构，从而设计一种好的算法是一门好的数据结构，从而设计一种好的算法是得到一个好的程序的基础。得到一个好的程序的基础。算法算法+数据结构数据结构=程序程序(Niklaus Wirth)（Algorithm+Data structure=Program)程序：为计算机处理问题编写的一组指令。程序：为计算机处理问题编写的一组指令。算法：处理问题的策略。算法：处理问题的策略。数据结构：问题的数学模型。数据结构：问题的数学模型。例如：铺设煤气管道问题例如：铺设煤气管道问题 A AB BC CD DI IH HGGE EF F18.218.232.832.844.644.612.112.18.78.756.456.421.321.341.141.167.367.310.510.585.685.698.798.752.552.579.279.2A AB BC CD DI IH HGGE EF F32.832.812.112.18.78.721.321.341.141.110.510.579.279.2(a)(a)(a)(a)居民区示意图居民区示意图居民区示意图居民区示意图(b)(b)(b)(b)铺设煤气管道设计图铺设煤气管道设计图铺设煤气管道设计图铺设煤气管道设计图North China Electric Power University例如：酒店客房管理系统中的客房分配问题例如：酒店客房管理系统中的客房分配问题 例例 人机对奕问题人机对奕问题.North China Electric Power University例如：图书馆的书目检索问题例如：图书馆的书目检索问题登录号登录号书名书名作者作者分类号分类号172832172832离散数学离散数学樊映川樊映川S01S01172833172833理论力学理论力学罗远祥罗远祥S01S01172834172834高等数学高等数学华罗庚华罗庚S01S01172835172835线性代数线性代数滦汝书滦汝书S02S02书名书名登录号登录号高等数学高等数学172832、172834理论力学理论力学172833线性代数线性代数172835作者作者登录号登录号樊映川樊映川172832华罗庚华罗庚172834滦汝书滦汝书172835类别类别登录号登录号L172833S172832、172834North China Electric Power University数据结构：数据结构：按照某种逻辑结构组织的一组数据，按照某种逻辑结构组织的一组数据，按一定的存储方式将它们映射到计算机的存按一定的存储方式将它们映射到计算机的存 储器中，并且在这些数据上定义了一个运算储器中，并且在这些数据上定义了一个运算 的集合，运算的结果保持原来的结构。的集合，运算的结果保持原来的结构。North China Electric Power University 1.研究数据元素之间的客观联系研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的存储方式。3.研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。的基础上对数据实施一系列有效的基本操作。逻辑结构逻辑结构存储结构存储结构数据结构课程研究的主要内容数据结构课程研究的主要内容算法算法 基本概念基本概念1.数据：数据：所有能输入到计算机中并为计算机程序所有能输入到计算机中并为计算机程序 处理的对象的集合。处理的对象的集合。2.2.数据元素：数据元素：数据的基本单位，在程序中作为一数据的基本单位，在程序中作为一 个整体加以考虑和处理。个整体加以考虑和处理。3.3.数据项：数据项：数据处理的最小单位。数据处理的最小单位。980604980604980604980604刘晔刘晔刘晔刘晔女女女女181818188080808010101010学号学号学号学号姓名姓名姓名姓名性别性别性别性别年年年年月月月月日日日日组合项组合项组合项组合项原子项原子项原子项原子项出生出生出生出生日期日期日期日期（学生情况）（学生情况）（学生情况）（学生情况）North China Electric Power University4.4.数据对象：数据对象：性质相同的数据元素的集合。性质相同的数据元素的集合。5.5.数据的逻辑结构：数据的逻辑结构：对数据元素之间逻辑关系的对数据元素之间逻辑关系的 描述。它可以用一个数据元素的集合和定义在描述。它可以用一个数据元素的集合和定义在 这个集合上的若干关系来表示。这个集合上的若干关系来表示。Data Structure=(D,S)D:数据元素的集合数据元素的集合;S:D上关系的集合上关系的集合 1 1）集合：集合中任何两个结点之间都）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。没有逻辑关系，组织形式松散。2 2）线性结构：元素之间存在着一对一）线性结构：元素之间存在着一对一的关系。依次排列形成一条的关系。依次排列形成一条“锁链锁链”。North China Electric Power University3 3）树形结构：数据元素之间存在着一对）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。多的关系，具有分支、层次特性。4 4）图状结构：数据元素之间存在多对多）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，任何两个的关系，元素之间互相缠绕，任何两个元素都可以邻接。元素都可以邻接。6.6.数据的存储结构：数据的存储结构：数据在计算机中的表示，包数据在计算机中的表示，包 括数据元素的表示和关系的表示。括数据元素的表示和关系的表示。1 1）顺序存储方式（向量存储）顺序存储方式（向量存储）2 2）链式存储方式）链式存储方式3 3）索引存储方式）索引存储方式4 4）散列存储方式）散列存储方式North China Electric Power University7.7.数据类型：数据类型：一个值的集合和定义在这个值上的一个值的集合和定义在这个值上的 一组操作。一组操作。8.8.抽象数据类型：抽象数据类型：一个数学模型和定义在这个数一个数学模型和定义在这个数学模型的一组操作。学模型的一组操作。特性特性数据抽象：用数据抽象：用ADT描述程序处理的实体时，强调的是其本描述程序处理的实体时，强调的是其本 质的特征，其完成的功能以及和外部的接口质的特征，其完成的功能以及和外部的接口。数据封装：将实体的外部特性和其内部实现分离，并对外数据封装：将实体的外部特性和其内部实现分离，并对外 部用户隐藏其内部实现细节部用户隐藏其内部实现细节。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名North China Electric Power University例如例如:抽象数据类型复数的定义抽象数据类型复数的定义ADT Complex ADT Complex ADT Complex ADT Complex 数据对象：数据对象：数据对象：数据对象：D=e1,e2|e1,e2D=e1,e2|e1,e2D=e1,e2|e1,e2D=e1,e2|e1,e2RealsetRealset 数据关系：数据关系：R1=|e1R1=|e1是复数的实数部分、是复数的实数部分、e2e2是是 复数的虚数部分复数的虚数部分 基本操作：基本操作：InitComplex(v1,v2)InitComplex(v1,v2)DestroyComplex(Z)DestroyComplex(Z)GetReal(Z,realPart)GetReal(Z,realPart)GetImag(Z,ImagPart)GetImag(Z,ImagPart)Add(Z1,Z2,Sum)Add(Z1,Z2,Sum)Subtract(Z1,Z2,Difference)Subtract(Z1,Z2,Difference)Multiply(Z1,Z2,Product)Multiply(Z1,Z2,Product)ADT Complex ADT Complex 注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，则可形成不同的抽象数据类型则可形成不同的抽象数据类型。North China Electric Power University 算法算法算法：算法：解决问题的方法和策略，指为解决一个或解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。一类问题给出的一个确定的、有限长的操作序列。算法的特性算法的特性:1.有穷性有穷性2.确定性确定性3.可行性可行性4.有输入有输入5.有输出有输出North China Electric Power University算算法法设设计计的的原原则则1.正确性正确性a.a.程序中不含语法错误程序中不含语法错误b.b.程序对于几组给定的输入数据能得出满足要求的结果程序对于几组给定的输入数据能得出满足要求的结果c.c.程序对于精心选择的、典型的、苛刻的且带有刁难程序对于精心选择的、典型的、苛刻的且带有刁难 性的几组输入能得出满足要求的结果性的几组输入能得出满足要求的结果d.d.程序对一切合法输入都能得出满足要求的结果程序对一切合法输入都能得出满足要求的结果2.可读性：可读性：算法主要是为了人的阅读与交流，其次才是为了计算算法主要是为了人的阅读与交流，其次才是为了计算 机执行，因此算法应该易于理解；另外，晦涩难懂的机执行，因此算法应该易于理解；另外，晦涩难懂的 程序易于隐藏较多错误而难于调试程序易于隐藏较多错误而难于调试3.健壮性：健壮性：当输入的数据非法时，算法应当恰当地做出反应或进当输入的数据非法时，算法应当恰当地做出反应或进 行相应的处理，而不是产生莫名其妙的错误输出；并行相应的处理，而不是产生莫名其妙的错误输出；并 且处理错误的方法不应该是中断程序的执行，而应是且处理错误的方法不应该是中断程序的执行，而应是 返回一个表示错误或错误性质的值，以便在更高的抽返回一个表示错误或错误性质的值，以便在更高的抽 象层次进行处理象层次进行处理4.4.高效率和低存储量需求：高效率和低存储量需求：效率：指算法的执行时间效率：指算法的执行时间 存储量：算法执行过程中所需的最大存储空间存储量：算法执行过程中所需的最大存储空间 两者都与问题的规模有关两者都与问题的规模有关North China Electric Power University算法的复杂性算法的复杂性复杂性：复杂性：指实现或运行某一算法所需资源的多少。指实现或运行某一算法所需资源的多少。时间复杂性时间复杂性空间复杂性空间复杂性人工复杂性人工复杂性(指编程、调试等所需的人工指编程、调试等所需的人工)North China Electric Power University和算法执行时和算法执行时间相关的因素：间相关的因素：1.1.算法选用的策略算法选用的策略2.2.问题的规模问题的规模3.3.编写程序的语言编写程序的语言4.4.编译程序产生的机器代码的质量编译程序产生的机器代码的质量5.5.计算机执行指令的速度计算机执行指令的速度一个特定算法的一个特定算法的“运行工作量运行工作量”的大小，只依赖于问题的规模（通的大小，只依赖于问题的规模（通常用整数量常用整数量n n来表示），或者说它是问题规模的函数。来表示），或者说它是问题规模的函数。算法的时间复杂性：算法的时间复杂性：假如随着问题规模假如随着问题规模n的增长，的增长，算法执行时间的增长率和算法执行时间的增长率和f(n)的增长率相同，则的增长率相同，则记作记作T(n)=O(f(n)，称，称T(n)为算法的时间复杂性。为算法的时间复杂性。算法时间复杂性的度量：算法时间复杂性的度量：任何一个算法都是由一个控制结构和若干原子操作组成任何一个算法都是由一个控制结构和若干原子操作组成 算法的执行时间算法的执行时间=原操作原操作(i)(i)的执行次数的执行次数*原操作原操作(i)(i)的执行时间的执行时间 因为原操作的执行时间相对问题的规模因为原操作的执行时间相对问题的规模n n而言是个常量，所以而言是个常量，所以 算法的执行时间与原操作执行次数之和成正比。算法的执行时间与原操作执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操从算法中选取一种对于所研究的问题来说是基本操作的原操 作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的 度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。North China Electric Power University例如：例如：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)North China Electric Power University -n+1-n(n+1)-n2 -n2(n+1)-n3对于足够大的对于足够大的n，存在下述关系：，存在下述关系：O(log n)O(n)O(nlog n)O(n2)O(n3)O(2n)O(3n)O(n!)算法的空间复杂性：算法的空间复杂性：假如随着问题规模假如随着问题规模n的增长，的增长，算法执行所需存储量的增长率和算法执行所需存储量的增长率和g(n)的增长率相的增长率相同，则记作同，则记作S(n)=O(g(n)，称，称S(n)为算法的空间为算法的空间复杂性。复杂性。算法的存储量：算法执行过程中所需的最大存储空间。算法的存储量：算法执行过程中所需的最大存储空间。算法的存储空间算法的存储空间1.1.输入数据所占的空间输入数据所占的空间2.2.程序本身所占的空间程序本身所占的空间3.3.辅助变量所占的空间辅助变量所占的空间North China Electric Power University1.采用自然语言来描述采用自然语言来描述问题问题：求两个正整数：求两个正整数M M与与N N的最大公因子。的最大公因子。(1)M除以除以N，将余数送中间变量，将余数送中间变量R；(2)测试余数测试余数R是否等于零？是否等于零？a)若若R等于零，求得的最大公因子为当前等于零，求得的最大公因子为当前N 的值的值,算法到此结束。算法到此结束。b)若若R不等于零，将不等于零，将N送入送入M，将，将R送送N,重重 复算法的复算法的(1)和和(2)。North China Electric Power University分类：分类：1.非形式算法（自然语言算法）非形式算法（自然语言算法）2.流程图语言流程图语言3.程序设计语言描述的算法程序设计语言描述的算法算法描述语言：算法描述语言：4.伪语言描述的算法伪语言描述的算法开始开始M除以除以N的余数送的余数送R余数余数R为为0否？否？输出输出N的值的值结束结束将将N送送M将将R送送Nnoyes2.采用程序流程图的形式来描述采用程序流程图的形式来描述North China Electric Power University3.采用采用某种具体程序语言某种具体程序语言来描述来描述COMFACTOR(int M,int N)int R;while(1)R=M%N;if (R=0)return N;M=N;N=R;North China Electric Power University 来来自自对对C C语语言言的的修修改改，它它描描述述的的算算法法是是不不能能直直接接在在机机器器上上执执行行的的程程序序过过程程。它它与与标标准准C C的的主主要要区区别如下：别如下：1.1.局部变量的说明可以省略局部变量的说明可以省略(但形参表中及函数类型的但形参表中及函数类型的 说明必须保留说明必须保留)，重要的变量须在注解中说明其类型，重要的变量须在注解中说明其类型和作用。和作用。2.2.算法写成函数的形式。算法写成函数的形式。函数类型函数类型 函数名函数名(函数参数表）函数参数表）/算法说明算法说明 语句序列语句序列;/函数名函数名North China Electric Power University 类类C C语言说明语言说明3.3.在函数中除了值调用方式之外，增添了在函数中除了值调用方式之外，增添了C+C+语语言的引用调用的参数传递方式。在形参表中，言的引用调用的参数传递方式。在形参表中，以以&打头的参数即为引用参数，引用参数能被打头的参数即为引用参数，引用参数能被函数本身更新值，可以作为输出数据的管道。函数本身更新值，可以作为输出数据的管道。4.4.内存的动态分配与释放内存的动态分配与释放 使用使用newnew和和deletedelete动态分配和释放内存空间。动态分配和释放内存空间。分配空间分配空间 指针变量指针变量=new=new 数据类型；数据类型；释放空间释放空间 delete delete 指针变量；指针变量；5.5.不含不含goto goto 语句，增加以下两条语句语句，增加以下两条语句:1)1)出错处理语句：出错处理语句：Error(Error(字符串字符串)，其功能是终止它所在算法，其功能是终止它所在算法 的执行，并回送表示出错信息的字符串。的执行，并回送表示出错信息的字符串。2)2)返回语句：返回语句：ReturnReturn和和Return(Return(表达式表达式)，其功能是终止函数的，其功能是终止函数的执行，执行，Return(Return(表达式表达式)终止函数的执行并将表终止函数的执行并将表达式的值回传给函数名。达式的值回传给函数名。6.6.在算法中任何处均可插入在算法中任何处均可插入/,/,进行单行注释。进行单行注释。North China Electric Power UniversityNorth China Electric Power University数据结构数据结构North China Electric Power UniversityData Structure 第二章第二章 线性表线性表 线性表线性表 栈栈 队列队列North China Electric Power University 线性表的逻辑结构：线性表的逻辑结构：线性表是线性表是0 0个或多个元素的有穷序列，通常可个或多个元素的有穷序列，通常可表示成表示成 a a1 1,a,a2 2,a a3 3,a,ai i,a,an n(n0)(n0)线性表线性表 n:n:线性表的表长线性表的表长 n=0n=0时称为空表时称为空表 n1时，a1称为第一个元素，称为第一个元素，an称为最后一个元素称为最后一个元素 ai称为称为ai+1的前驱，的前驱，ai+1称为称为ai的后继，的后继，i i称为序号或索引称为序号或索引 特点：除第一个和最后一个元素外，每个元素有 且只有一个直接前驱和一个直接后继。North China Electric Power UniversityNorth China Electric Power University线性表的例子：线性表的例子：例例1 1.一副扑克牌中同一花色的一副扑克牌中同一花色的1313张牌组成一个线性表张牌组成一个线性表 (A,2,3,4,5,6,7,8,9,10,J,Q,K)(A,2,3,4,5,6,7,8,9,10,J,Q,K)例例2 2.人民币面值的所有种类组成一个线性表人民币面值的所有种类组成一个线性表 (1(1角，角，2 2角，角，5 5角，角，1 1元，元，2 2元，元，5 5元，元，1010元，元，2020元，元，5050元，元，100100元元)例例3 3.一本书可以看成是一个线性表，每一页是一数据元素一本书可以看成是一个线性表，每一页是一数据元素例例4 4.学生的学籍档案构成一个线性表学生的学籍档案构成一个线性表学号学号姓名姓名入学总分入学总分数学分析数学分析程序设计程序设计离散数学离散数学981201王国强王国强435886582981202赵济实赵济实429859078981203刘晔刘晔512978895981204叶桑林叶桑林488939185981250田华月田华月501899587数据元素数据元素数据项数据项线性表的基本运算：North China Electric Power University1.Initial(&L):1.Initial(&L):初始化操作，设定一个空的线性表初始化操作，设定一个空的线性表L L。2.Length(L):2.Length(L):返回线性表的表长。返回线性表的表长。3.Get(L,i):3.Get(L,i):若若1 1i iLength(L),Length(L),返回线性表的第返回线性表的第i i个元素。个元素。4.Locate(L,x):4.Locate(L,x):若若L L中存在一个或多个值和中存在一个或多个值和x x相等，运算相等，运算 结果为这些元素序号的最小值，否则返回结果为这些元素序号的最小值，否则返回0 0。5.Insert(&L,i,x):5.Insert(&L,i,x):在线性表的第在线性表的第i i个位置插入一新元素个位置插入一新元素x x。6.Delete(&L,i):6.Delete(&L,i):删除线性表删除线性表L L的第的第i i个元素。个元素。7.Empty(L):7.Empty(L):若线性表若线性表L L为空返回为空返回True,True,否则返回否则返回FalseFalse。线性表的其它运算：如求任一元素的直接前驱或直接后继；合并两个线性表；线如求任一元素的直接前驱或直接后继；合并两个线性表；线性表的拆分；线性表的复制；对线性表按照值的大小进行排序性表的拆分；线性表的复制；对线性表按照值的大小进行排序等操作。等操作。North China Electric Power University线性表基本运算的应用示例线性表基本运算的应用示例：例例1.设有两个线性表设有两个线性表La和和Lb，现将，现将La 和和Lb合并成一个合并成一个 新表存于新表存于La中。中。void Union(Linear_list&La,Linear_list Lb)/将所有在将所有在Lb中存在而在中存在而在La中不存在的数据元素插入到中不存在的数据元素插入到La中中 n=Length(La);for(i=1;i=Length(Lb);i+)x=Get(Lb,i);k=Locate(La,x);if(k=0)then Insert(La,n+1,x);n=n+1;思考题：思考题：例例2.判断两个集合判断两个集合A和和B是否相等。是否相等。int Compare(Linear_list La,Linear_list lb)/若若La和和Lb不仅长度相等，而且所含元素也相同则返回不仅长度相等，而且所含元素也相同则返回1 Len_la=Length(La);Len_lb=Length(Lb);if(Len_la!=Len_lb)return(0);else for(k=1;k=Len_la;k+)x=Get(La,k);m=Locate(Lb,x);if(m=0)return(0);return(1);North China Electric Power UniversityNorth China Electric Power University线性表的顺序存储：用一块连续的存储单元依次存放线性表的各个元素。内存状态内存状态存储地址存储地址元素在线性表中的次序元素在线性表中的次序b=Loc(a a1 1)b+cb+(i-1)*cb+(n-1)*cb+(max-1)*c12in空闲空闲 a a1 1 a a2 2 a ai i a an n顺序存储的线性表的寻址公式：顺序存储的优点：顺序存储的优点：1.1.可以随机存取可以随机存取2.2.空间利用率高空间利用率高3.3.结构简单结构简单Loc(ai)=Loc(a1)+(i-1)*c 1in Loc(a1)为线性表的第一个元素a1的存储地址 c为每个元素所占的存储单元 线性表的顺序存储可以借用数组类型来实现North China Electric Power University顺序表的基本运算的实现：1)在顺序表L的第i个位置上插入一个新元素x插入前：插入前：元素元素序号序号 1 12 23 34 45 56 67 78 8插入插入27插入后：插入后：元素元素序号序号 1 12 23 34 45 56 67 78 89 9主要操作：主要操作：1.将第将第i到到n个元素依次后移一个位置个元素依次后移一个位置2.将新元素将新元素x放到顺序表的第放到顺序表的第i个位置上个位置上3.将顺序表的表长由将顺序表的表长由n修改为修改为n+12828 3131 434378781111 1414252520202828 3131 434378781111 1414252520202727North China Electric Power University在顺序表L的第i个位置上插入新元素x的算法void Insert(Linear_list&L,ElemType x,int i,int&n);if (in+1)Error(“插入的位置非法插入的位置非法”);else for(j=n;j=i;j-)Lj+1=Lj;/数据元素依次向后移动一个位置数据元素依次向后移动一个位置 Li=x;/将将X插入线性表的第插入线性表的第i个位置个位置 n=n+1;/线性表的长度加线性表的长度加1 在一个长度为在一个长度为n的线性表中插入一元素时需移动元素的平均次数为的线性表中插入一元素时需移动元素的平均次数为Ein=P Pj j*(n-j+1)=n/2 (当当P Pj j=1/(n+1)j=1,2,=1/(n+1)j=1,2,n,n+1)n,n+1)1 1n+1n+1算法的时间复杂性为算法的时间复杂性为O(n)(n)North China Electric Power UniversityNorth China Electric Power University2)删除顺序表L的第i个元素删除前：删除前：元素元素序号序号 1 12 23 34 45 56 67 78 8删除删除插入后：插入后：元素元素序号序号 1 12 23 34 45 56 67 7主要操作：主要操作：1.将第将第i+1到到n个元素依次前移一个位置个元素依次前移一个位置2.将顺序表的表长由将顺序表的表长由n修改为修改为n-12828 3131 434378781111 1414252520204343 78781111 1414282820203131North China Electric Power University删除顺序表L的第i个元素的算法void Delete(Linear_list&L,int i,int&n)if (in)Error(“没有这个元素没有这个元素”)；else for(j=i+1;j=n;j+)Lj-1=Lj;n=n-1;在一个长度为在一个长度为n的顺序表中删除一元素时需移动元素的平均次数为的顺序表中删除一元素时需移动元素的平均次数为Ede=P Pj j*(n-j)=(n-1)/2 (当当P Pj j=1/n j=1,2,=1/n j=1,2,n)n)算法的时间复杂性为算法的时间复杂性为O(n)(n)3)定位运算：求x在顺序表L中的最小序号元素元素序号序号 1 12 23 34 45 56 67 78 828283131 434378781111 1414252520202828x xint Locate(Linear_list L,ElemType x,int n)/在在L中查找第一个值和中查找第一个值和x相等的元素，若存在，返回该元素相等的元素，若存在，返回该元素L中中/的序号，否则返回的序号，否则返回0 i=1;while(i=n)&(Li!=x)i=i+1;if(i=n)return(i)else return(0);North China Electric Power UniversityNorth China Electric Power University4)顺序表的其他算法举例例例1.按照字典序比较两个线性表按照字典序比较两个线性表A和和B的大小的大小int Compare(Linear_list A,Linear_list B/若若AB,则返回则返回1 j=1;while(j=Length(A)&(j=Length(B)if(AjBj)return(1);else j=j+1;if(Length(A)=Length(B)return(0);else if(Length(A)Length(B)return(-1);else return(1);North China Electric Power University例例2.归并两个归并两个“其数据元素按值非递减有序其数据元素按值非递减有序”的线性表的线性表La,Lb,使求得的线性表使求得的线性表Lc也具有同样的特性。也具有同样的特性。void Merge(Linear_list La,Lineare_List Lb,Linear_list&Lc)Initial(Lc);i=1;j=1;k=0;Len_la=Length(La);Len_lb=Length(Lb);while(i=Len_la)&(j=Len_lb)if(Lai=Lbj)k=k+1;Insert(Lc,k,Lai);i=i+1;else k=k+1;Insert(Lc,k,Lbj);j=j+1;while(i=Len_la)k=k+1;Insert(Lc,k,Lai);i=i+1;while(j=Len_lb)k=k+1;Insert(Lc,k,Lbj);j=j+1;已知长度为已知长度为n 的线性表的线性表A采用顺序存储结构，并且数据采用顺序存储结构，并且数据元素按值大小非递减排列。元素按值大小非递减排列。写一算法，删除线性表中值相写一算法，删除线性表中值相同的多余元素。同的多余元素。例例3void Del(Linear_List A,int&n);i=1;while (in)if (Ai Ai+1)i=i+1 else for(j=i+1;j=n;j+)Aj 1=Aj;n=n1;North China Electric Power University顺序存储的缺点：顺序存储的缺点：1.1.需要一片地址连续的存储空间需要一片地址连续的存储空间;2.2.插入和删除元素时不方便，大量的时间用在元插入和删除元素时不方便，大量的时间用在元 素的搬家上素的搬家上;2.2.在预分配存储空间时，可能造成空间的浪费在预分配存储空间时，可能造成空间的浪费;3.3.表的容量难以扩充。表的容量难以扩充。North China Electric Power University解决的方案：解决的方案：1.1.对顺序表的插入和删除运算进行限定对顺序表的插入和删除运算进行限定2.2.采用其它的存储结构采用其它的存储结构(链式存储链式存储)栈栈North China Electric Power University栈的逻辑结构栈的逻辑结构栈：所有的插入和删除都只能在表尾（栈顶）进栈：所有的插入和删除都只能在表尾（栈顶）进 行的线性表。允许进行插入和删除操作的一行的线性表。允许进行插入和删除操作的一 端叫栈顶，不允许插入和删除的一端叫栈底。端叫栈顶，不允许插入和删除的一端叫栈底。没有元素的栈叫空栈。没有元素的栈叫空栈。a1栈底栈底栈顶栈顶插入插入删除删除 若给定栈若给定栈S=(a1,a2,S=(a1,a2,an),an),则则a1a1是栈底元素，是栈底元素，anan是栈顶元素，表中是栈顶元素，表中元素按元素按a1,a2,a1,a2,an,an顺序进栈，按顺序进栈，按an,an,a2,a1,a2,a1顺序出栈。通常把栈顺序出栈。通常把栈称为先进后出的线性表。因此栈中称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出数据元素的逻辑关系是先进后出(FILO)(FILO)。an a2 a1North China Electric Power University 栈的举例栈的举例：1)1)装乒乓球的圆筒，装的时候是第一个装入的球放在装乒乓球的圆筒，装的时候是第一个装入的球放在 最底下，第二在它的上面，一个个依次装入，取出最底下，第二在它的上面，一个个依次装入，取出 时最后装入的那个球却被第一个取走时最后装入的那个球却被第一个取走。2)2)假定有一个问题假定有一个问题P,P,它的解决依赖于两个子问题它的解决依赖于两个子问题A A和和E E 的解决，而子问题的解决，而子问题A A的解决又依赖于子问题的解决又依赖于子问题B B和和C C的的 解决，问题解决，问题C C的解决依赖于问题的解决依赖于问题D D的解决。的解决。PAEBCD1 12 23 34 45 56 67 78 81010111112129 9 解决问题的步骤如左图所示解决问题的步骤如左图所示，红色的箭头表示进入这个问，红色的箭头表示进入这个问题（或者说子问题进栈），绿题（或者说子问题进栈），绿色的箭头表示问题已经解决色的箭头表示问题已经解决（或子问题出栈）。（或子问题出栈）。栈一般用来容纳被接受了的栈一般用来容纳被接受了的而还没有进行处理的信息。而还没有进行处理的信息。