1、数据结构数据结构North China Electric Power UniversityData Structure(Dept.of Computer,North China Electric Power University)第一章第一章 绪绪 论论 课程简介课程简介 基本概念基本概念 算法算法 算法语言的说明算法语言的说明North China Electric Power University开设本课程的必要性以及课程的特点：开设本课程的必要性以及课程的特点：1.计算机专业重要的专业基础课之一计算机专业重要的专业基础课之一.2.需要有关需要有关“程序设计语言程序设计语言”和和“离散数学
2、离散数学”的知识作为课程的基础的知识作为课程的基础.3.实践性较强实践性较强.North China Electric Power University 课程简介课程简介 在计算机发展的初期，计算机主要用于科在计算机发展的初期，计算机主要用于科学计算，因此程序设计者的主要精力集中在程学计算，因此程序设计者的主要精力集中在程序设计的技巧上，而不重视数据结构。当时处序设计的技巧上，而不重视数据结构。当时处理一个计算问题的一般步骤为：理一个计算问题的一般步骤为：具体数值问题具体数值问题 数学模型数学模型 设计算法设计算法 编程编程抽象出抽象出North China Electric Power Un
3、iversityNorth China Electric Power University 随着计算机的推广普及，计算机越来越多随着计算机的推广普及，计算机越来越多地应用于非数值领域，使人们逐渐认识到选择地应用于非数值领域，使人们逐渐认识到选择一门好的数据结构，从而设计一种好的算法是一门好的数据结构，从而设计一种好的算法是得到一个好的程序的基础。得到一个好的程序的基础。算法算法+数据结构数据结构=程序程序(Niklaus Wirth)（Algorithm+Data structure=Program)North China Electric Power University例例 人机对奕问题人
4、机对奕问题.North China Electric Power University登录号登录号书名书名作者作者分类号分类号172832172832离散数学离散数学樊映川樊映川S01S01172833172833理论力学理论力学罗远祥罗远祥S01S01172834172834高等数学高等数学华罗庚华罗庚S01S01172835172835线性代数线性代数滦汝书滦汝书S02S02书名书名登录号登录号高等数学高等数学1 7 2 8 3 2、172834理论力学理论力学172833线性代数线性代数172835作者作者登录号登录号樊映川樊映川172832华罗庚华罗庚172834滦汝书滦汝书17283
5、5类别类别登录号登录号L172833S1 7 2 8 3 2、172834North China Electric Power UniversityNorth China Electric Power University 1.研究数据元素之间的客观联系研究数据元素之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的存储方式。3.研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的)的基础上对数据实施一系列有效的基本操作。的基础上对数据实施一系列有效的基本操作。逻辑结构逻辑结构存储结构存储结构数据结构
6、课程研究的主要内容数据结构课程研究的主要内容算法算法 基本概念基本概念North China Electric Power University 1 1）集合：集合中任何两个结点之间都）集合：集合中任何两个结点之间都没有逻辑关系，组织形式松散。没有逻辑关系，组织形式松散。2 2）线性结构：元素之间存在着一对一）线性结构：元素之间存在着一对一的关系。依次排列形成一条的关系。依次排列形成一条“锁链锁链”。North China Electric Power University3 3）树形结构：数据元素之间存在着一对）树形结构：数据元素之间存在着一对多的关系，具有分支、层次特性。多的关系，具有分支
7、、层次特性。4 4）图状结构：数据元素之间存在多对多）图状结构：数据元素之间存在多对多的关系，元素之间互相缠绕，任何两个的关系，元素之间互相缠绕，任何两个元素都可以邻接。元素都可以邻接。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是是 复数的虚数部分复数的虚数部分 基本操作：基本操作：InitCo
9、mplex(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 注：对于数据成员完全
10、相同的数据类型，如果给它们赋予不同的语义，注：对于数据成员完全相同的数据类型，如果给它们赋予不同的语义，则可形成不同的抽象数据类型则可形成不同的抽象数据类型。North China Electric Power University 算法算法算法：算法：解决问题的方法和策略，指为解决一个或解决问题的方法和策略，指为解决一个或一类问题给出的一个确定的、有限长的操作序列。一类问题给出的一个确定的、有限长的操作序列。算法的特性算法的特性:1.有穷性有穷性2.确定性确定性3.可行性可行性4.有输入有输入5.有输出有输出North China Electric Power University算法设计的
11、原则算法设计的原则1.正确性正确性a.a.程序中不含语法错误程序中不含语法错误b.b.程序对于几组给定的输入数据能得出满足要求的结果程序对于几组给定的输入数据能得出满足要求的结果c.c.程序对于精心选择的、典型的、苛刻的且带有刁难程序对于精心选择的、典型的、苛刻的且带有刁难 性的几组输入能得出满足要求的结果性的几组输入能得出满足要求的结果d.d.程序对一切合法输入都能得出满足要求的结果程序对一切合法输入都能得出满足要求的结果2.可读性：可读性：算法主要是为了人的阅读与交流，其次才是为了计算算法主要是为了人的阅读与交流，其次才是为了计算 机执行，因此算法应该易于理解；另外，晦涩难懂的机执行，因此
12、算法应该易于理解；另外，晦涩难懂的 程序易于隐藏较多错误而难于调试程序易于隐藏较多错误而难于调试3.健壮性：健壮性：当输入的数据非法时，算法应当恰当地做出反应或进当输入的数据非法时，算法应当恰当地做出反应或进 行相应的处理，而不是产生莫名其妙的错误输出；并行相应的处理，而不是产生莫名其妙的错误输出；并 且处理错误的方法不应该是中断程序的执行，而应是且处理错误的方法不应该是中断程序的执行，而应是 返回一个表示错误或错误性质的值，以便在更高的抽返回一个表示错误或错误性质的值，以便在更高的抽 象层次进行处理象层次进行处理4.4.高效率和低存储量需求：高效率和低存储量需求：效率：指算法的执行时间效率：
13、指算法的执行时间 存储量：算法执行过程中所需的最大存储空间存储量：算法执行过程中所需的最大存储空间 两者都与问题的规模有关两者都与问题的规模有关North China Electric Power University算法的复杂性算法的复杂性复杂性：复杂性：指实现或运行某一算法所需资源的多少。指实现或运行某一算法所需资源的多少。时间复杂性时间复杂性空间复杂性空间复杂性人工复杂性人工复杂性(指编程、调试等所需的人工指编程、调试等所需的人工)North China Electric Power University和算法执行时和算法执行时间相关的因素：间相关的因素：1.1.算法选用的策略算法选用的
14、策略2.2.问题的规模问题的规模3.3.编写程序的语言编写程序的语言4.4.编译程序产生的机器代码的质量编译程序产生的机器代码的质量5.5.计算机执行指令的速度计算机执行指令的速度一个特定算法的一个特定算法的“运行工作量运行工作量”的大小，只依赖于问题的规模（通的大小，只依赖于问题的规模（通常用整数量常用整数量n n来表示），或者说它是问题规模的函数。来表示），或者说它是问题规模的函数。算法的时间复杂性：算法的时间复杂性：假如随着问题规模假如随着问题规模n的增长，的增长，算法执行时间的增长率和算法执行时间的增长率和f(n)的增长率相同，则的增长率相同，则记作记作T(n)=O(f(n)，称，称T
15、(n)为算法的时间复杂性。为算法的时间复杂性。算法时间复杂性的度量：算法时间复杂性的度量：任何一个算法都是由一个控制结构和若干原子操作组成任何一个算法都是由一个控制结构和若干原子操作组成 算法的执行时间算法的执行时间=原操作原操作(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
17、;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!)算法的空间复杂性：算法的空间复杂性：假如随着问题规模假如随着问题
18、规模n的增长，的增长，算法执行所需存储量的增长率和算法执行所需存储量的增长率和g(n)的增长率相的增长率相同，则记作同，则记作S(n)=O(g(n)，称，称S(n)为算法的空间为算法的空间复杂性。复杂性。算法的存储量：算法执行过程中所需的最大存储空间。算法的存储量：算法执行过程中所需的最大存储空间。算法的存储空间算法的存储空间1.1.输入数据所占的空间输入数据所占的空间2.2.程序本身所占的空间程序本身所占的空间3.3.辅助变量所占的空间辅助变量所占的空间North China Electric Power University1.采用自然语言来描述采用自然语言来描述问题问题：求两个正整数：求
19、两个正整数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.程序设计语言描述的算法程序设计语言描述的算法算法描述语
20、言：算法描述语言：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语言的修改
21、，它描述的算法是不能直语言的修改，它描述的算法是不能直接在机器上执行的程序过程。它与标准接在机器上执行的程序过程。它与标准C C的主要区的主要区别如下：别如下：1.1.局部变量的说明可以省略局部变量的说明可以省略(但形参表中及函数类型的但形参表中及函数类型的 说明必须保留说明必须保留)，重要的变量须在注解中说明其类，重要的变量须在注解中说明其类型和作用。型和作用。2.2.算法写成函数的形式。算法写成函数的形式。函数类型函数类型 函数名函数名(函数参数表）函数参数表）/算法说明算法说明 语句序列语句序列;/函数名函数名North China Electric Power University 类
22、类C C语言说明语言说明3.3.在函数中除了值调用方式之外，增添了在函数中除了值调用方式之外，增添了C+C+语语言的引用调用的参数传递方式。在形参表中，言的引用调用的参数传递方式。在形参表中，以以&打头的参数即为引用参数，引用参数能被打头的参数即为引用参数，引用参数能被函数本身更新值，可以作为输出数据的管道。函数本身更新值，可以作为输出数据的管道。4.4.内存的动态分配与释放内存的动态分配与释放 使用使用newnew和和deletedelete动态分配和释放内存空间。动态分配和释放内存空间。分配空间分配空间 指针变量指针变量=new=new 数据类型；数据类型；释放空间释放空间 delete
23、delete 指针变量；指针变量；5.5.不含不含goto goto 语句，增加以下两条语句语句，增加以下两条语句:1)1)出错处理语句：出错处理语句：Error(Error(字符串字符串)，其功能是终止它所在算法，其功能是终止它所在算法 的执行，并回送表示出错信息的字符串。的执行，并回送表示出错信息的字符串。2)2)返回语句：返回语句：ReturnReturn和和Return(Return(表达式表达式)，其功能是终止函数的，其功能是终止函数的执行，执行，Return(Return(表达式表达式)终止函数的执行并将表终止函数的执行并将表达式的值回传给函数名。达式的值回传给函数名。6.6.在算
24、法中任何处均可插入在算法中任何处均可插入/,/,进行单行注释。进行单行注释。North China Electric 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 线性表的逻辑结构：线性表的
25、逻辑结构：线性表是线性表是0 0个或多个元素的有穷序列，通常可个或多个元素的有穷序列，通常可表示成表示成 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.一副扑克牌中同一花色的13张牌组成一个线性表 (A,2,3,4,5,6,7,8,9,10,J,Q,K)例2.人民币面值的所有种类组成一个线性表(1角，2角，5角，1元，2元，5元，10元，20元，
26、50元，100元)例3.一本书可以看成是一个线性表，每一页是一数据元素例4.学生的学籍档案构成一个线性表学号姓名入学总分数学分析程序设计离散数学981201王国强435886582981202赵济实429859078981203刘晔512978895981204叶桑林488939185981250田华月501899587数据元素数据项North China Electric Power University1.Initial(&L):初始化操作，设定一个空的线性表L。2.Length(L):返回线性表的表长。3.Get(L,i):若1iLength(L),返回线性表的第i个元素。4.Locat
27、e(L,x):若L中存在一个或多个值和x相等，运算 结果为这些元素序号的最小值，否则返回0。5.Insert(&L,i,x):在线性表的第i个位置插入一新元素x。6.Delete(&L,i):删除线性表L的第i个元素。7.Empty(L):若线性表L为空返回True,否则返回False。如求任一元素的直接前驱或直接后继；合并两个线性表；线性表的拆分；线性表的复制；对线性表按照值的大小进行排序等操作。North China Electric Power University线性表基本运算的应用示例：例1.设有两个线性表La和Lb，现将La 和Lb合并成一个 新表存于La中。void Union(
28、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
29、_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(a1)b+cb+(i-1)*cb+(n-1)*cb+(max-1)*c12in空闲 a1 a2 ai an顺序存储的优点：1.可以随机存取2.空间利用率高3.结构简单aia11ina1a1North China El
30、ectric Power University插入前：元素序号 12345678插入27插入后：元素序号 123456789主要操作：1.将第i到n个元素依次后移一个位置2.将新元素x放到顺序表的第i个位置上3.将顺序表的表长由n修改为n+128 31 437811 14252028 31 437811 14252027North 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=L
31、j;/数据元素依次向后移动一个位置 Li=x;/将X插入线性表的第i个位置 n=n+1;/线性表的长度加1 在一个长度为n的线性表中插入一元素时需移动元素的平均次数为Ein=Pj*(n-j+1)=n/2 (当Pj=1/(n+1)j=1,2,n,n+1)1n+1算法的时间复杂性为O(n)North China Electric Power UniversityNorth China Electric Power University删除前：元素序号 12345678删除插入后：元素序号 1234567主要操作：1.将第i+1到n个元素依次前移一个位置2.将顺序表的表长由n修改为n-128 31
32、437811 14252043 7811 14282031North 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的顺序表中删除一元素时需移动元素的平均次数为Ede=Pj*(n-j)=(n-1)/2 (当Pj=1/n j=1,2,n)算法的时间复杂性为O(n)元素序号 123456782831 437811 14252028xint Locate(Linear_list
33、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 University例1.按照字典序比较两个线性表A和B的大小int Compare(Linear_list A,Linear_list B/若AB,则返回1 j=1;while(j=Length(A)&(j=Length(B)if(A
34、jBj)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
35、=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 (
36、in)if (AiAi+1)i=i+1 else for(j=i+1;j=n;j+)Aj1=Aj;n=n1;North China Electric Power University顺序存储的缺点：1.需要一片地址连续的存储空间;2.插入和删除元素时不方便，大量的时间用在元 素的搬家上;2.在预分配存储空间时，可能造成空间的浪费;3.表的容量难以扩充。North China Electric Power University解决的方案：1.对顺序表的插入和删除运算进行限定2.采用其它的存储结构(链式存储)栈North China Electric Power University栈的逻辑结构栈
37、：所有的插入和删除都只能在表尾（栈顶）进 行的线性表。允许进行插入和删除操作的一 端叫栈顶，不允许插入和删除的一端叫栈底。没有元素的栈叫空栈。a1栈底栈顶插入删除 若给定栈S=(a1,a2,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,an顺序进栈，按an,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。an a2 a1North China Electric Power University 栈的举例：1)装乒乓球的圆筒，装的时候是第一个装入的球放在 最底下，第二在它的上面，一个个依次装入，取出 时最后装入的那个球却被第一
38、个取走。2)假定有一个问题P,它的解决依赖于两个子问题A和E 的解决，而子问题A的解决又依赖于子问题B和C的 解决，问题C的解决依赖于问题D的解决。PAEBCD123456781011129 解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），绿色的箭头表示问题已经解决（或子问题出栈）。栈一般用来容纳被接受了的而还没有进行处理的信息。North China Electric Power University1.InitStack(&S):初始化操作，设定一个空栈S。2.PushStack(&S,x):将元素x压入到栈S中。3.PopStack(&S):当栈S不空时弹出栈顶
39、元素。4.TopStack(S):当栈S不空时返回栈顶元素。5.EmptyStack(S):若栈S为空，返回True,否则返回False。S:topS1S2SiStopmaxsizeS：表示栈S1:表示底一个进栈的元素S2:表示第2个进栈的元素Si:表示第i个进栈的元素Stop:表示栈顶元素top=0:表示栈空top=maxsize:表示栈满 空闲空间 ai a2 a1North China Electric Power University1)PushStack(&S,x):将元素x压入到栈S中。void PushStack(Stack&s,ElemType x)/m为栈的最大容量 if(t
40、op=m)Error(“栈已满”);else top=top+1;Stop=x;2)PopStack(&S):当栈S不空时弹出栈顶元素。Procedure PopStack(Stack&S);/m为栈的最大容量 if(top=0)Error(“栈空”);else y=Stop;top=top-1;上面两个元素的时间复杂性均为O(1)，压栈和退栈时不需移动元素North China Electric Power UniversitySTACK1:mtop1、top2 分别为第1个与第2个栈的栈顶元素的指针。插入：当i=1时，将item 插入第1个栈，当i=2时，将item 插入第2个栈。可用空间
41、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=top1+1STACKtop1=itemi=1top2=top21STACKtop2=itemi=2North China Electric Power UniversityNorth China Electric Power University1)PushStack(&S,i,x):将元素x压入到第i个栈中。Procedure Push
42、Stack(Stack&S,int i,ElemType x);/S为两个栈的共享空间 if(top2=top1+1)Error(“栈已满”);else switch(i)case 1:topi=topi+1;Stopi=x;break;case 2:topi=topi-1;Stopi=x;break;2)PopStack(S,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(
43、topi=m+1)Error(“栈空”);else topi=topi+1;break;North China Electric Power Universitynum=391106078391/8 48 76/8 0 6商除以8 商 余数 已知一个无符号十进制整数 num，写一算法，依次输出其对应的八进制数的各位数字。例170648/8 6 0 void change(int num)top=0 while (num 0)top=top+1;Stacktop=num%8;/余数进栈 num=num/8;while (top 0)printf(Stacktop);top=top-1;/退栈 算
44、法North China Electric Power UniversityNorth China Electric Power University例2.扩号匹配问题：假设表达式中有两种扩号,圆括号和 方括号,即()或()为正确的格式,()等 为不正确的格式，写一个算法检验表达式中的扩号 是否匹配。分析：检验扩号是否匹配可以用“期待的紧迫程度”这个概念来描述。例如考虑下面的扩号序列：()1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况：1)到来的右扩号并非所期待的；2)到来的是“不速之客”;3)直到结束，也没有到来所“期待”的；int matching(String exp)/检验
45、表达式中的扩号是否匹配,若匹配返回1,否则返回0 State=1;InitStack(S);while (inext=null;单链表的类型定义如下：单链表的类型定义如下：typedef struct Node ElemType data;struct Node*next;*Pointer;North China Electric Power University2)Length_Link(Head):返回单链表中所含表结点的个数。返回单链表中所含表结点的个数。int Length_Link(Pointer Head)p=Head;j=0;while(p-Next!=null)p=p-next
46、;j=j+1;return(j);3)Find_Link(Head):返回指向线性表第返回指向线性表第i个结点的指针。个结点的指针。Pointer Find_Link(Pointer Head,int i)p=Head;j=0;while(p-next!=null)&(jnext;j=j+1;if(i=j)return(p);else return(null);North China Electric Power University4)Locate_Link(Head,x):在单链表中查找值等于在单链表中查找值等于x的结点，的结点，返回指向该结点的指针。返回指向该结点的指针。Pointer
47、Locate_Link(Pointer Head,ElemType x)p=Head-next;while(p!=null)&(p-data!=x)p=p-next;return(p);ABCD x=CHeadpNorth China Electric Power University5)Insert_Link(Head,x,i):在单链表的第在单链表的第i个结点之前插入值个结点之前插入值 等于等于x的结点。的结点。void Insert_Link(Pointer&Head,ElemType x,int i)p=Find_Link(Head,i-1);if(p=null)Error(“With
48、out”)else s=new Node;s-data=x;s-next=p-next;p-next=s;ABCD x=F i=3HeadpF SNorth China Electric Power University6)Delete_Link(Head,i):删除单链表的第删除单链表的第i个结点。个结点。void Delete_Link(Pointer&Head,int i)p=Find_Link(Head,i-1);if(p!=null)&(p-next!=null)q=p-next;p-next=q-next;delete q;else Error(“Without”);ABCD i=
49、3HeadpNorth China Electric Power University7)Create_Link(Head):建立一个单链表。建立一个单链表。void Create_Link_1(Pointer&Head)Init_Link(Head);scanf(“%c”,&x);i=1;while(x!=*)Insert_Link(head,x,i);i=i+1;scanf(“%c”,&x);North China Electric Power Universityvoid Create_Link_2(Pointer&Head)/顺序顺序 Init_Link(Head);p=Head;sc
50、anf(“%c”,&x);while(x!=*)q=new Node;q-data=x;p-next=q;p=q;scanf(“%c”,&x);p-next=null;void Create_Link_3(Pointer&Head)/逆序逆序 p=null;scanf(“%c”,&x);while(x!=*)q=new Node;q-data=x;q-next=p;p=q;scanf(“%c”,&x);Head=new Node;Head-next=p;North China Electric Power University线性表的链式存储结构的优缺点：线性表的链式存储结构的优缺点：优点：优
