1、数据结构数据结构North China Electric Power UniversityData Structure第一章第一章 绪绪 论论 课程简介课程简介 基本概念基本概念 算法算法 算法语言的说明算法语言的说明North China Electric Power University开设本课程的必要性以及课程的特点：开设本课程的必要性以及课程的特点：1.计算机专业重要的专业基础课之一计算机专业重要的专业基础课之一.2.需要有关需要有关“程序设计语言程序设计语言”和和“离散数学离散数学”的知识作为课程的基础的知识作为课程的基础.3.实践性较强实践性较强.North China Elect
2、ric Power University 课程简介课程简介 在计算机发展的初期，计算机主要用于科在计算机发展的初期，计算机主要用于科学计算，因此程序设计者的主要精力集中在程学计算，因此程序设计者的主要精力集中在程序设计的技巧上，而不重视数据结构。当时处序设计的技巧上，而不重视数据结构。当时处理一个计算问题的一般步骤为：理一个计算问题的一般步骤为：具体数值问题具体数值问题 数学模型数学模型 设计算法设计算法 编程编程抽象出抽象出North China Electric Power UniversityNorth China Electric Power University 随着计算机的推广普及
3、，计算机越来越多地随着计算机的推广普及，计算机越来越多地应用于非数值领域，使人们逐渐认识到选择一应用于非数值领域，使人们逐渐认识到选择一门好的数据结构，从而设计一种好的算法是得门好的数据结构，从而设计一种好的算法是得到一个好的程序的基础。到一个好的程序的基础。算法算法+数据结构数据结构=程序程序(Niklaus Wirth)（Algorithm+Data structure=Program)North China Electric Power University例例 人机对奕问题人机对奕问题.North China Electric Power University登录号登录号书名书名作者作
4、者分类号分类号172832172832离散数学离散数学樊映川樊映川S01S01172833172833理论力学理论力学罗远祥罗远祥S01S01172834172834高等数学高等数学华罗庚华罗庚S01S01172835172835线性代数线性代数滦汝书滦汝书S02S02书名书名登录号登录号高等数学高等数学1 7 2 8 3 2、172834理论力学理论力学172833线性代数线性代数172835作者作者登录号登录号樊映川樊映川172832华罗庚华罗庚172834滦汝书滦汝书172835类别类别登录号登录号L172833S1 7 2 8 3 2、172834North China Electri
5、c Power UniversityNorth China Electric Power University 1.研究数据元素之间的客观联系研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的存储方式。3.研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。的基础上对数据实施一系列有效的基本操作。逻辑结构逻辑结构存储结构存储结构数据结构课程研究的主要内容数据结构课程研究的主要内容算法算法 基本概念基本概念North China Electric
6、Power University 1 1）集合：集合中任何两个结点之间都）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。没有逻辑关系，组织形式松散。2 2）线性结构：元素之间存在着一对一）线性结构：元素之间存在着一对一的关系。依次排列形成一条的关系。依次排列形成一条“锁链锁链”。North China Electric Power University3 3）树形结构：数据元素之间存在着一对）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。多的关系，具有分支、层次特性。4 4）图状结构：数据元素之间存在多对多）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，
7、任何两个的关系，元素之间互相缠绕，任何两个元素都可以邻接。元素都可以邻接。1 1）顺序存储方式（向量存储）顺序存储方式（向量存储）2 2）链式存储方式）链式存储方式3 3）索引存储方式）索引存储方式4 4）散列存储方式）散列存储方式North China Electric Power University特性特性数据抽象：用数据抽象：用ADT描述程序处理的实体时，强调的是其本描述程序处理的实体时，强调的是其本 质的特征，其完成的功能以及和外部的接口质的特征，其完成的功能以及和外部的接口数据封装：将实体的外部特性和其内部实现分离，并对外数据封装：将实体的外部特性和其内部实现分离，并对外 部用户隐
8、藏其内部实现细节部用户隐藏其内部实现细节ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名North China Electric Power University例如例如:抽象数据类型复数的定义抽象数据类型复数的定义RealsetRealset 数据关系：数据关系：R1=|e1R1=|e1是复数的实数部分、是复数的实数部分、e2e2是是 复数的虚数部分复数的虚数部分 基本操作：基本操作：InitComplex(v1,v2)InitComplex(v1,v2)DestroyComplex(Z)DestroyCo
9、mplex(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 注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，则可形成
10、不同的抽象数据类型则可形成不同的抽象数据类型。North China Electric Power University 算法算法算法：算法：解决问题的方法和策略，指为解决一个或解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。一类问题给出的一个确定的、有限长的操作序列。算法的特性算法的特性:1.有穷性有穷性2.确定性确定性3.可行性可行性4.有输入有输入5.有输出有输出North China Electric Power University算法设计的原则算法设计的原则1.正确性正确性a.a.程序中不含语法错误程序中不含语法错误b.b.程序对于几组给定的输入数据
11、能得出满足要求的结果程序对于几组给定的输入数据能得出满足要求的结果c.c.程序对于精心选择的、典型的、苛刻的且带有刁难程序对于精心选择的、典型的、苛刻的且带有刁难 性的几组输入能得出满足要求的结果性的几组输入能得出满足要求的结果d.d.程序对一切合法输入都能得出满足要求的结果程序对一切合法输入都能得出满足要求的结果2.可读性：可读性：算法主要是为了人的阅读与交流，其次才是为了计算算法主要是为了人的阅读与交流，其次才是为了计算 机执行，因此算法应该易于理解；另外，晦涩难懂的机执行，因此算法应该易于理解；另外，晦涩难懂的 程序易于隐藏较多错误而难于调试程序易于隐藏较多错误而难于调试3.健壮性：健壮
12、性：当输入的数据非法时，算法应当恰当地做出反应或进当输入的数据非法时，算法应当恰当地做出反应或进 行相应的处理，而不是产生莫名其妙的错误输出；并行相应的处理，而不是产生莫名其妙的错误输出；并 且处理错误的方法不应该是中断程序的执行，而应是且处理错误的方法不应该是中断程序的执行，而应是 返回一个表示错误或错误性质的值，以便在更高的抽返回一个表示错误或错误性质的值，以便在更高的抽 象层次进行处理象层次进行处理4.4.高效率和低存储量需求：高效率和低存储量需求：效率：指算法的执行时间效率：指算法的执行时间 存储量：算法执行过程中所需的最大存储空间存储量：算法执行过程中所需的最大存储空间 两者都与问题
13、的规模有关两者都与问题的规模有关North China Electric Power University算法的复杂性算法的复杂性复杂性：复杂性：指实现或运行某一算法所需资源的多少。指实现或运行某一算法所需资源的多少。时间复杂性时间复杂性空间复杂性空间复杂性人工复杂性人工复杂性(指编程、调试等所需的人工指编程、调试等所需的人工)North China Electric Power University和算法执行时和算法执行时间相关的因素：间相关的因素：1.1.算法选用的策略算法选用的策略2.2.问题的规模问题的规模3.3.编写程序的语言编写程序的语言4.4.编译程序产生的机器代码的质量编译程序
14、产生的机器代码的质量5.5.计算机执行指令的速度计算机执行指令的速度一个特定算法的一个特定算法的“运行工作量运行工作量”的大小，只依赖于问题的规模（通的大小，只依赖于问题的规模（通常用整数量常用整数量n n来表示），或者说它是问题规模的函数。来表示），或者说它是问题规模的函数。算法的时间复杂性：算法的时间复杂性：假如随着问题规模假如随着问题规模n的增长，的增长，算法执行时间的增长率和算法执行时间的增长率和f(n)的增长率相同，则的增长率相同，则记作记作T(n)=O(f(n)，称，称T(n)为算法的时间复杂性。为算法的时间复杂性。算法时间复杂性的度量：算法时间复杂性的度量：任何一个算法都是由一个
15、控制结构和若干原子操作组成任何一个算法都是由一个控制结构和若干原子操作组成 算法的执行时间算法的执行时间=原操作原操作(i)(i)的执行次数的执行次数*原操作原操作(i)(i)的执行时间的执行时间 因为原操作的执行时间相对问题的规模因为原操作的执行时间相对问题的规模n n而言是个常量，所以而言是个常量，所以 算法的执行时间与原操作执行次数之和成正比。算法的执行时间与原操作执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操从算法中选取一种对于所研究的问题来说是基本操作的原操 作，以该基本操作在算法中重复执行的次数作为时间复杂的依据。作，以该基本操作在算法中重复执行的次数作为
16、时间复杂的依据。这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的这种衡量效率的办法所得出的不是时间量，而指一种增长趋势的 度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。度量，它与软、硬件无关，只揭示出算法本身执行效率的优劣。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;i
17、n;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)的增长率相的增长率相同，则
18、记作同，则记作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；
19、(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否？
20、否？输出输出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语言的修改，它描述的算法是不能直语言的修改，它描述的算法是不能直接在机器上执行的程序过程。它与标准接在机器上执行的程序过程
21、。它与标准C C的主要区的主要区别如下：别如下：1.1.局部变量的说明可以省略局部变量的说明可以省略(但形参表中及函数类型的但形参表中及函数类型的 说明必须保留说明必须保留)，重要的变量须在注解中说明其类，重要的变量须在注解中说明其类型和作用。型和作用。2.2.算法写成函数的形式。算法写成函数的形式。函数类型函数类型 函数名函数名(函数参数表）函数参数表）/算法说明算法说明 语句序列语句序列;/函数名函数名North China Electric Power University 类类C C语言说明语言说明3.3.在函数中除了值调用方式之外，增添了在函数中除了值调用方式之外，增添了C+C+语语
22、言的引用调用的参数传递方式。在形参表中，言的引用调用的参数传递方式。在形参表中，以以&打头的参数即为引用参数，引用参数能被打头的参数即为引用参数，引用参数能被函数本身更新值，可以作为输出数据的管道。函数本身更新值，可以作为输出数据的管道。4.4.内存的动态分配与释放内存的动态分配与释放 使用使用newnew和和deletedelete动态分配和释放内存空间。动态分配和释放内存空间。分配空间分配空间 指针变量指针变量=new=new 数据类型；数据类型；释放空间释放空间 delete delete 指针变量；指针变量；5.5.不含不含goto goto 语句，增加以下两条语句语句，增加以下两条语
23、句:1)1)出错处理语句：出错处理语句：Error(Error(字符串字符串)，其功能是终止它所在算法，其功能是终止它所在算法 的执行，并回送表示出错信息的字符串。的执行，并回送表示出错信息的字符串。2)2)返回语句：返回语句：ReturnReturn和和Return(Return(表达式表达式)，其功能是终止函数的，其功能是终止函数的执行，执行，Return(Return(表达式表达式)终止函数的执行并将表终止函数的执行并将表达式的值回传给函数名。达式的值回传给函数名。6.6.在算法中任何处均可插入在算法中任何处均可插入/,/,进行单行注释。进行单行注释。North China Electr
24、ic Power UniversityNorth China Electric Power University数据结构数据结构North China Electric Power UniversityData Structure华北电力大学计算机系华北电力大学计算机系(Dept.of Computer,North China Electric Power University)第二章第二章 线性表线性表 线性表线性表 栈栈 队列队列North China Electric Power University 线性表的逻辑结构：线性表的逻辑结构：线性表是线性表是0 0个或多个元素的有穷序列，通常
25、个或多个元素的有穷序列，通常可表示成可表示成 a a1 1,a,a2 2,a a3 3,a,ai i,a,an n(n0)(n0)线性表线性表n1时，a1anaiai+1ai+1aiNorth 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.人民币面值的所有
26、种类组成一个线性表人民币面值的所有种类组成一个线性表 (1(1角，角，2 2角，角，5 5角，角，1 1元，元，2 2元，元，5 5元，元，1010元，元，2020元，元，5050元，元，100100元元)例例3 3.一本书可以看成是一个线性表，每一页是一数据元素一本书可以看成是一个线性表，每一页是一数据元素例例4 4.学生的学籍档案构成一个线性表学生的学籍档案构成一个线性表学号学号姓名姓名入学总分入学总分数学分析数学分析程序设计程序设计离散数学离散数学981201王国强王国强435886582981202赵济实赵济实429859078981203刘晔刘晔512978895981204叶桑林叶
27、桑林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中存在一个
28、或多个值和中存在一个或多个值和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。如求任一元素的直接前驱或直接后继；合并两个线性表；如求任一元素的
29、直接前驱或直接后继；合并两个线性表；线性表的拆分；线性表的复制；对线性表按照值的大小进行排线性表的拆分；线性表的复制；对线性表按照值的大小进行排序等操作。序等操作。North China Electric Power University线性表基本运算的应用示例线性表基本运算的应用示例：例例1.设有两个线性表设有两个线性表La和和Lb，现将，现将La 和和Lb合并成一个合并成一个 新表存于新表存于La中。中。void Union(Linear_list&La,Linear_list Lb)/将所有在将所有在Lb中存在而在中存在而在La中不存在的数据元素插入到中不存在的数据元素插入到La中中 n
30、=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(
31、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.空间
32、利用率高空间利用率高3.3.结构简单结构简单aia11ina1a1North China Electric Power University插入前：插入前：元素元素序号序号 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 141425252020
33、2828 3131 434378781111 1414252520202727North China Electric Power Universityvoid 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的线性表中插入一元素时需移动元素
34、的平均次数为的线性表中插入一元素时需移动元素的平均次数为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 University删除前：删除前：元素元素序号序号 1 12 23 34 45 56 67 78 8删除删除插入后：插入后：元素元素序号序号 1 12 23 34 45 56 67 7主要操作：主要操作
35、：1.将第将第i+1到到n个元素依次前移一个位置个元素依次前移一个位置2.将顺序表的表长由将顺序表的表长由n修改为修改为n-12828 3131 434378781111 1414252520204343 78781111 1414282820203131North China Electric Power Universityvoid 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的顺序表中删除一元素时需移动元素的平均
36、次数为的顺序表中删除一元素时需移动元素的平均次数为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)元素元素序号序号 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
37、=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 University例例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)=L
38、ength(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=L
39、ength(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采用顺序存储结构，并且数据采用顺序存储结构，并且数据元素按值大小非递减排列。元素按值大小非递减排列。写一算法，删除线性表中值相写一算法，删除线性表中值相同的多余元
40、素。同的多余元素。例例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.表的容量
41、难以扩充。表的容量难以扩充。North China Electric Power University解决的方案：解决的方案：1.1.对顺序表的插入和删除运算进行限定对顺序表的插入和删除运算进行限定2.2.采用其它的存储结构采用其它的存储结构(链式存储链式存储)栈栈North China Electric Power University栈的逻辑结构栈的逻辑结构栈：所有的插入和删除都只能在表尾（栈顶）进栈：所有的插入和删除都只能在表尾（栈顶）进 行的线性表。允许进行插入和删除操作的一行的线性表。允许进行插入和删除操作的一 端叫栈顶，不允许插入和删除的一端叫栈底。端叫栈顶，不允许插入和删除的一端
42、叫栈底。没有元素的栈叫空栈。没有元素的栈叫空栈。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 Universit
43、y 栈的举例栈的举例：1)1)装乒乓球的圆筒，装的时候是第一个装入的球放在装乒乓球的圆筒，装的时候是第一个装入的球放在 最底下，第二在它的上面，一个个依次装入，取出最底下，第二在它的上面，一个个依次装入，取出 时最后装入的那个球却被第一个取走时最后装入的那个球却被第一个取走。2)2)假定有一个问题假定有一个问题P,P,它的解决依赖于两个子问题它的解决依赖于两个子问题A A和和E E 的解决，而子问题的解决，而子问题A A的解决又依赖于子问题的解决又依赖于子问题B B和和C C的的 解决，问题解决，问题C C的解决依赖于问题的解决依赖于问题D D的解决。的解决。PAEBCD1 12 23 34
44、45 56 67 78 81010111112129 9 解决问题的步骤如左图所解决问题的步骤如左图所示，红色的箭头表示进入这个示，红色的箭头表示进入这个问题（或者说子问题进栈），问题（或者说子问题进栈），绿色的箭头表示问题已经解决绿色的箭头表示问题已经解决（或子问题出栈）。（或子问题出栈）。栈一般用来容纳被接受了栈一般用来容纳被接受了的而还没有进行处理的信息。的而还没有进行处理的信息。North China Electric Power University1.InitStack(&S):1.InitStack(&S):初始化操作，设定一个空栈初始化操作，设定一个空栈S S。2.PushSt
45、ack(&S,x):2.PushStack(&S,x):将元素将元素x x压入到栈压入到栈S S中。中。3.PopStack(&S):3.PopStack(&S):当栈当栈S S不空时弹出栈顶元素。不空时弹出栈顶元素。4.TopStack(S):4.TopStack(S):当栈当栈S S不空时返回栈顶元素。不空时返回栈顶元素。5.EmptyStack(S):5.EmptyStack(S):若栈若栈S S为空，返回为空，返回True,True,否则返回否则返回FalseFalse。S:toptopS1S1S2S2SiSiStopStopmaxsizemaxsizeS S：表示栈：表示栈S1:S1
46、:表示底一个进栈的元素表示底一个进栈的元素S2:S2:表示第表示第2 2个进栈的元素个进栈的元素Si:Si:表示第表示第i i个进栈的元素个进栈的元素Stop:Stop:表示栈顶元素表示栈顶元素top=0:top=0:表示栈空表示栈空top=maxsize:top=maxsize:表示栈满表示栈满 空闲空间空闲空间 aiai a2a2 a1a1North China Electric Power University1)PushStack(&S,x):1)PushStack(&S,x):将元素将元素x x压入到栈压入到栈S S中。中。void PushStack(Stack&s,ElemTyp
47、e x)/m为栈的最大容量为栈的最大容量 if(top=m)Error(“栈已满栈已满”);else top=top+1;Stop=x;2)PopStack(&S):2)PopStack(&S):当栈当栈S S不空时弹出栈顶元素。不空时弹出栈顶元素。Procedure PopStack(Stack&S);/m为栈的最大容量为栈的最大容量 if(top=0)Error(“栈空栈空”);else y=Stop;top=top-1;上面两个元素的时间复杂性均为上面两个元素的时间复杂性均为O(1)，压栈和退栈时不需移动元素，压栈和退栈时不需移动元素North China Electric Power
48、UniversitySTACK1:mtop1、top2 分别为第分别为第1个与第个与第2个栈的栈顶元素的指针。个栈的栈顶元素的指针。插入：插入：当当i=1时，将时，将item 插入第插入第1个栈，个栈，当当i=2时，将时，将item 插入第插入第2个栈。个栈。可用空间可用空间1 2 3 m第第 1 个栈个栈第第 2 个栈个栈top1 top2初始条件：初始条件：top1=0 top2=m+11 2 3 M第第 1 个栈个栈第第 2 个栈个栈可用空间可用空间1 2 3 M第第 1 个栈个栈第第 2 个栈个栈top1 top2top1 top2栈满的条件是栈满的条件是top1=top21top1=
49、top1+1STACKtop1=itemi=1top2=top21STACKtop2=itemi=2North China Electric Power UniversityNorth China Electric Power University1)PushStack(&S,i,x):1)PushStack(&S,i,x):将元素将元素x x压入到第压入到第i i个栈中。个栈中。Procedure PushStack(Stack&S,int i,ElemType x);/S为两个栈的共享空间为两个栈的共享空间 if(top2=top1+1)Error(“栈已满栈已满”);else switc
50、h(i)case 1:topi=topi+1;Stopi=x;break;case 2:topi=topi-1;Stopi=x;break;2)PopStack(S,i):2)PopStack(S,i):当第当第i i个栈不空时弹出其栈顶元素。个栈不空时弹出其栈顶元素。Procedure PushStack(Stack&S,int i,ElemType x)switch(i)case 1:if(topi=0)Error(“栈空栈空”);else topi=topi-1;break;case 2:if(topi=m+1)Error(“栈空栈空”);else topi=topi+1;break;N
