用c语言描述课件全套整本书电子讲义全书电子课件教学教程.ppt

,第二级,第三级,第四级,第五级,第,一,章 绪论,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 线性表,第二级,第三级,第四级,第五级,*,第,三,章 栈和队列,第,四,章 串,第二级,第三级,第四级,第五级,*,第,五,章 数组和广义表,第二级,第三级,第四级,第五级,第,六,章 树,第二级,第三级,第四级,第五级,第,七,章 图,第二级,第三级,第四级,第五级,第,八,章 检索,第二级,第三级,第四级,第五级,第,九,章 排序,第二级,第三级,第四级,第五级,第,十,章 文件,第1章 绪论,1.1 什么是数据结构,1.2,基本概念和术语,1.3 数据类型和抽象数据类型,1.4 算法描述与算法评价,本章将介绍数据结构研究的对象、基本概念和术语、算法的概念及其描述方法（C语言描述）、数据类型以及抽象数据类型，并概述数据结构的发展概况及其在计算机科学中的地位。,第1章 绪 论,随着计算机应用领域的不断扩大，计算机处理的对象更多的是非数值计算问题，它们的数学模型无法用数学方程来进行描述，此时就必须建立相应的数据结构来进行描述，分析问题中所用到的数据是如何组织的，研究数据之间的关系如何，进而为解决这些问题设计出合适的数据结构。,1.1 什么是数据结构,例1 职工信息管理,图1.1 职工花名册表,编号,姓 名,性 别,年 龄,月 收 入,1,李 泉,男,51,980,2,王 怡,女,47,945,3,张 三,男,35,870,4,马小丁,男,27,840,.,.,将每位职工的信息组织成如图1.1所示的花名册。花名册中每个职工的信息由编号、姓名、性别、年龄、月收入等项目组成，占表的一行，表中的结点和结点之间是一种简单的线性关系,这就是上述花名册表的线性逻辑结构。当用计算机对上述花名册表中的数据进行运算时，就要考虑那些结点在计算机中的存储表示，即存储结构。另外，还必须考虑如何进行结点的插入、删除、修改、检索或查找，这就涉及到数据的运算,例2 旅游交通网络图,如图1.2所示，为一个旅游交通网络咨询系统，可采用一种称之为图的结构来表示实际的交通网络，此时，这个交通网络图就表示一个数据结构。在这个数据结构中，结点之间的关系可以是任意的，图中任意两个结点之间都可以相关。同样，必须考虑构造后将这张图存放入计算机中，这就要涉及到图的存储结构问题，以及图的运算。,从以上例子可见，要描述诸如此类的非数值计算问题的数学模型，涉及到一些诸如表、图还有树之类的数据结构。,数据结构课程实际上是一门研究非数值计算问题的程序设计中计算机的操作对象以及它们之间的关系和运算操作等的一门学科。在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。,数据是指信息的载体，是对客观事物的符号表示，是对有效地输入到计算机中并能被计算机程序处理的符号的总称。如声音、图形、图像。,数据元素是数据的基本单位，数据项是数据的不可分割的最小单位。有时也称之为结点、元素、顶点、记录等。一个数据元素可由若干个数据项组成，如上面职工花名册中的每个人的信息就是一个数据元素，而每个人的信息包括编号、姓名、性别、年龄、月收入等，这每一个项目就属于数据项。,1.2,基本概念和术语,数据对象是性质相同的数据元素的集合，是数据的一个子集。,数据类型（数据类型）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。数据类型有时还分为原子数据类型和结构数据类型。,数据结构指的是数据及数据之间的相互关系。一般地，数据结构包括以下三个方面的内容：,（1）数据元素之间的逻辑关系，有时也称为数据的逻辑结构。,（2）数据元素及其关系在计算机内存中的表示（又称为映象），称之为数据的物理结构，又称为数据的存储结构，它包括数据元素的表示和数据元素之间关系的表示。,（3）数据的运算及实现，即对数据元素可以施加的操作及其这些操作在相应的存储结构上的实现。,数据的逻辑结构是从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数学模型。如上例中的职工花名册表。根据数据元素之间的不同特性，通常有下列四类基本逻辑结构：,（1）线性结构：结构中的数据元素存在一个对一个的关系，即所谓的线性关系。,（2）树型结构：结构中的数据元素之间存在一个对多个的关系，是结点之间有分支、并具有层次关系的结构，它非常类似于自然界中的树。,（3）图或网状结构：该结构中的数据元素之间的关系存在多个对多个的关系，如交通网络图就是一个图状结构。,（4）集合：结构中的数据元素之间除了“同属于一个集合”的相互关系外，别无其它关系。,有时将树形结构、集合和图或网状结构称为非线性结构，此时数据逻辑结构就可分为线性结构和非线性结构两类。,数据的存储结构是指逻辑结构用计算机语言的实现，就是数据元素及其关系如何存放入计算机内存的问题。一般地，数据的存储结构可按以下四种基本存储方法而得到：,（1）顺序存储方法：是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点间的逻辑关系由存储单元的相邻关系而体现。由此得到的存储表示称为顺序存储结构，通常可借助计算机语言的数组来描述。,（2）链状存储方式：不要求逻辑上相邻的结点在物理位置上也相邻，数据元素可以存储在任意位置。为了实现数据元素之间逻辑关系的存储，必须通过一些附加的手段来存储这种相互关系，由此得到的存储表示称为链状存储结构。一般可以用指针来实现，通常可借助计算机程序语言的指针类型或者游标来来描述。,（3）索引存储方法：该方法通常是在存储结点信息的同时，建立附加的索引表。索引表一般有稠密索引和稀疏索引两种。,（4）散列存储方法：该方法是依据结点的关键字直接计算出该结点的存储地址，而后将结点按某种方式存入该地址的一种存储方法。,数据的运算是指定义在数据的逻辑结构上的一组操作的集合。例如，检索（查找）、插入、删除、定位、修改、排序等。要注意的是，这些运算实际上是在逻辑结构上对抽象数据所施加的一系列抽象的操作，运算的实现依赖于所选取的存储结构，是依赖于不同的计算机程序设计语言的。,数据类型是具有相同性质的计算机数据的集合及在这个数据集合上的一组运算。,在高级程序语言中，数据类型可以分为原子类型和结构类型。原子类型即值不可分解的类型，如C语言中的整型、字符型、实型、指针类型等；而结构类型则指的是其值可由若干成分按某种结构组成的类型，是可以分解的，如C语言中提供的结构体。,抽象数据类型（ADT）是指一个数学模型及定义在该数学模型上的一组操作。抽象数据模型的定义取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。,1.3 数据类型和抽象数据类型,算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列。一个算法必须具备以下五个重要特性：,（1）输入：一个算法必须具有零个或多个的外界输入。,（2）输出：一个算法必须有一个或多个的输出。,（3）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之后结束，并且每步都必须在有穷时间内完成。利用这一点，我们可以区别算法与程序。,（4）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。,（5）可行性：算法中描述的操作都必须可以通过已经实现的基本运算有限次执行来实现，而且算法必须在有限时间内完成。,一个算法可以用自然语言、数学语言或约定的符号来描述，也可用计算机高级程序语言来描述，如PASCAl语言、C语言、C、Java或伪代码等。本书选用C语言作为描述算法的工具。,1.4.1 算法描述,1.4 算法描述与算法评价,1.4.2 算法的设计要求,设计一个好的算法可以从以下几个方面考虑：,（1）正确性。算法是为了针对解决具体问题而提出的，算法的正确与否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。,（2）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然也必须有效。,（3）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处理。,（4）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽可能地少，即做到既省时又节省空间。,要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出较好较优的算法。,考虑算法的效率应从下几个方面考虑：（1）时间效率。考虑算法所耗费的运行时间。（2）空间效率。考虑运行算法需要耗费的存储空间，其中主要考虑算法所需的辅助存储空间。（3）算法应尽可能地简单，易于理解，易于编码和调试并能得出正确结果。,一个算法的运行时间是指一个算法在计算机上运行所耗费的时间。它可以认为是算法中每条语句的执行时间之和。,1.4.3 算法的评价,例如，两个nn矩阵相乘的算法：,for（i=1；i=n；i+）/*n+1次*/for（j=1；j=n；j+）/*n（n+1）次*/ci j=0；/*nn次*/for（k=1；k0时的线性表记为：（a,1,，a,2,，a,i,，a,n,）,其中，a,1,是第一个数据元素，又称为起始结点，a,n,是最后一个数据元素，又称为终端结点。当i=1，2，n-1时，a,i,有且仅有一个直接后继a,i+1,；当i=2，3，n 时，a,i,有且仅有一个直接前趋a,i-1,。注意这里的a,i,（1 i n）仅仅是一个抽象的符号，其具体含义，在不同的情况下各不相同，它可以是一个数，一条记录或一个符号，甚至是更复杂的信息。例如，英文字母表(A，B，Z)是一个线性表，职工工资表等。,线性表的结点之间的逻辑关系符合线性结构的逻辑特征，是一种线性结构。,2.1.1 线性表的逻辑结构,2.1 线性表的基本概念,常见的线性表的基本运算：,（1）置空表SETNULL(L)：将线性表L置成空表。,（2）求长度LENGTH(L)：求给定线性表L中数据元素的个数。,（3）取元素GET(L,i)：结果是线性表L中的第i个数据元素。,（4）定位函数LOCATE(L,x)：当线性表中存在一个值为x的数据元素，则结果是该数据元素在表中的位序，否则，表示值为x的数据元素不存在。,（5）前趋函数PRIOR(L,x)：若x为线性表中的一个数据元素，且其位序大于1，则结果为L 的直接前趋，否则，给出一个特殊值示出该元素没有直接前趋。,（6）后继函数NEXT（L，x）：若x的位序小于LENGTH（L），则结果为该元素的直接后继，否则，给出一个特殊值，示出x无直接后继。,2.1.2 线性表的运算,（7）插入INSERT(L,x,i)：函数功能为在线性表L中的第i 个位置上插入一个值为x 的新元素，使运算前长度为n 的线性表变为长度为n+1的线性表。,（8）删除DELETE(L,i)：函数功能为删除线性表L中的第i 个数据元素，使在此之前长度为n 的线性表L变成长度为n1的线性表。,利用基本运算可以实现线性表的其它复杂运算。,需要指出的是，这里给出的只是定义在逻辑结构上的抽象运算，即只关心这些运算是“做什么”的，至于“怎样实现”则依赖于所选定的存储结构。,顺序表是线性表的顺序存储结构，即按顺序存储方式构成的线性表的存储结构。其存储方式是：线性表的第一个元素存放在个一片连续的存储空间开始位置处，第二个元素紧跟着存放在第一元素之后，以此类推。,利用顺序表来存储线性表，可借助数据元素在计算机内的物理位置相邻特性来表示线性表中数据元素之间的线性逻辑关系。,设线性表每个元素占c个存储单元，若以第一个数据元素在存储单元中的存储地址作为起始地址，则可得出线性表中第i个数据元素的地址为：,LOC(ai)=LOC(a1)+(i-1)*c（1iLENGTH(L)）,这样，一旦起始地址LOC（a,1,）（图2.1中设为b）和一个数据元素占用的存储单元的大小（c值）确定下来，就可求出任一个数据元素的存储地址，显然，这种表便于进行随机访问，因此，顺序表是一种随机存取的结构。,2.2.1 顺序表,2.2 线性表的顺序存储,在具体实现时，可利用高级程序设计语言中的一维数组即向量来为线性表的顺序存储开辟存储空间，存储空间大小应大于等于线性表长度，用一个整型变量来表示线性表的长度，从而可将顺序表描述为：,#define MAXSIZE 999,typedef int elemtype；/*elemtype表示元素类型，此处设为 int*/,typedef struct,elemtype vecMAXSIZE；,int len；,sequenlist；,在上面描述中，顺序表是一个结构体类型。其中，vec成员（又称为数据域）指线性表数据元素所占用的存储空间，而len成员（又称为长度域）则用于存储线性表长度，它表示线性表最后一个元素在向量中的位置，elemtype 则为线性表中数据元素类型。,本节讨论在定义线性表顺序存储结构之后，如何在这种结构上实 现有关数据运算。下面重点讨论线性表的数据元素的插入和删除运算。,1插入运算,线性表的插入运算是指在表的第i个元素之前插入一个新的数据元素，插入的结果使得线性表的长度由n变为n+1，线性表的数据元素间的逻辑关系发生了变化，使得物理存储顺序也发生相应的变化。插入过程如图2.2所示。,2.2.2 顺序表上的基本运算,具体算法描述如下：int insert(sequenlist *L，int i，elemtype x),int j；,if(*L).len)=MAXSIZE-1),printf(“the list is overflow!n”)；/*溢出判断*/,return（0）；,else,if(i(*L).len+1),printf(“position is not correct!n”)；,return（0）；/*插入位置不正确*/,else,for(j=(*L).len；j=i-1；j-)/*后移元素*/,(*L).vec j+1=(*L).vec j；,(*L).veci-1=x；/*插入新元素x*/,(*L).len=(*L).len+1；/*修改表长*/,return(1);,/*insert*/,在本算法中是从最后一个元素开始后移，直到第i个元素为止。该算法时间主要花费在for循环语句上，执行的次数为n-i+1。当i=1时，全部元素均参加移动，共需要移动n次；当i=n+1时，不需移动元素。,算法在最坏情况下，时间复杂度为O(n)，最好情况下时间复杂度为O(1)。显然，元素移动的次数直接影响了算法执行时间。,平均移动次数。假设p,i,为在第i个元素之前插入一个元素的概率，且为等概率，则平均移动次数的期望值为：其中，当1in+1时，p,1,=p,2,=p,n+1,=可见，在顺序存储的线性表中插入一个元素，约平均移动线性表中一半的元素，显然，当n较大时，算法效率较低，算法的平均时间复杂度为O(n)。2删除运算 删除运算是指将线性表中的第i个元素删除，使线性表的长度由n变成n-1，由：(a,1,，a,2,，a,i-1,，a,i,，a,i+1,，a,n,)变成为：(a,1,，a,2,，a,i-1,，a,i+1,，a,n,)其中，,1,i,n。,线性表进行删除元素后，仍是一个线性表。删除过程如图2.3所示。,具体算法如下：,void delete(L，i),sequenlist *L；,int i；,int j；,if(i(*L).len+1),printf(“delete fail！n”)；/*删除位置不正确*/,else,*y=(*L).veci-1；/*y为一外部变量，用于接收被删除的元素*/,for(j=i；j=(*L).len；j+),(*L).vecj-1=(*L).vecj；/*元素前移*/,(*L).Len-；/*修改表长*/,/*delete*/,与插入算法相似，要删除一个元素需向前移动元素，,删除第i个元素时，,将第i+1，i+2，n个元素依次前移，其移动次数为n-i，假设删除线性表中的任一位置上元素的概率相等（等于1/n），则删除运算所需的移动元素的平均移动次数如下所示。,由此可见，对线性表删除一个元素时，约需有一半的元素参加移动。,显然，该算法的时间复杂度为,(n),。,通过以上讨论可以发现，当表长较大时，对顺序存储结构进行插入和删除运算，由于要移动元素，运算效率低，但这种存储结构对于随机存取元素却十分方便。,例如，一个线性表中可能含有重复的元素（值相同），现要求删除重复元素中的多余元素，只保留其中位序最小的一个。如线性表（5，2，2，3，5，2），经过清除重复元素后变为(5，2，3)。假定线性表以顺序存储方式存储，则其算法可描述如下：void purge(sequenlist*L)int i=0，j，k；while(i=(*L).Len-1),j=i+1；while(j=(*L).Len-1)if(*L).veci=(*L).vecj)for(k=j；knext=NULL；/*生成头结点*/r=p；/*建立单链表表尾指针*/ch=getchar()；/*ch为建立与否标志*/while(ch!=?)/*?为输入结束标志符*/scanf(“%d”,p-next=NULL；/*生成新结点*/r-next=p；/*连接新结点*/r=r-next；/*修改尾指针*/ch=getchar()；/*读入建立与否的标志*/return(head)；/*返回表头指针head*/*creatlist*/,（2）建立不带头结点的单链表 linklist *creatlist()/*函数返回一个指向链表表头的指针*/char ch；int x；linklist *head，*p，*r head=NULL；r=NULL；/*设立尾指针r，其初值为空*/ch=getchar()；/*读入建立与否标志*/while(ch!=?)/*?为输入结束标志符*/p=(linklist*)malloc(sizeof(linklist)；/*申请新结点空间*/scanf(“%d”，if(head=NULL)head=p；,else r-next=p；/*非空表，则新结点*p插入到*r之后*/r=p；/*尾指针移动，指向新的表尾*/ch=getchar()；/*读入建立与否的标志*/if(r!=NULL)r-next=NULL；,return head；/*返回表头指针head*/*creatlist*/在算法中引入头结点可以不必区分空表与非空表，可以统一空链表与非空链表的处理。上述两个算法的时间复杂度都为O(n)。,2.单链表上元素的检索,一般情况下，可以按某个元素的序号或按某给定值两种方法检索。,（1）按值检索,按值检索，即是检索单链表中是否存在值为给定值k的结点，整个过程可以通过结点的值和给定值的比较而实现。,linklist *locate（linklist *head，elemtype k）,linklist *s；s=head-next；/*从第一个结点起开始比较*/while(s!=NULL)/*扫描整个链表*/if(s-data!=k),s=s-next；,else,break；,return s；/*返回结点的位置或NULL*/*Locate*/算法时间复杂度为O(n)。,（2）按序号检索 即利用被访问结点的序号而检索或查找结点的过程。linklist *get(linklist*head，int i)int j；linklist *p；p=head；j=0；while(p-next!=NULL)&(i j)p=p-next；j+；if(i=j)return p；,else return NULL；,/*get*/该算法中最坏情况下的时间复杂度为O(n)。,3单链表上元素的插入和删除运算 插入结点的指针变化图2.8所示。指针的修改操作为：s-next=p-next；p-next=s；,上述指针进行相互赋值的语句顺序不能颠倒，,若次序变化为：p-next=s；s-next=p-next；则会导致错误。,同样，要删除单链表结点*p的后继结点也很简单，只要用一个指针指向被删除结点，修改*p的指针域，最后释放结点*p即可，如图2.9所示。,删除一个结点*p的后继结点的指针操作为：p-next=p-next-next；不难发现，,在单链表存储结构中进行元素的插入和删除时，只需要修改有关的指针内容，而不需要移动元素。,（1）插入算法 （a）insert(linklist*p,elemtype x),/*将值为x的新结点插入*p之后*/linklist *s；s=（linklist*）malloc(sizeof(linklist)；/*生成x的新结点*s*/s-data=x；s-next=p-next；/*新结点链入单链表*/p-next=s；/*insert*/,（b）void insert(linklist*head,elemtype k,elemtype x)/*在单链表中值为k的结点之前插入一个值为x的新结点*/linklist *q，*p，*r；r=(linklist*)malloc(sizeof(linklist)；/*生成新结点*/r-data=x；if(head-next=NULL),head-next=r；r-next=NULL；,else q=head-next；p=head-next-next；while(p!=NULL)if(p-data!=k)*/q=p；p=p-next；,else,break；,if(p!=NULL)q-next=r；r-next=p；else /*在链表表尾处插入新结点*/q-next=r；r-next=NULL；/*insert*/该算法的时间主要耗费在查找值为k的结点位置上，算法时间复杂度为O(n)。,（2）删除算法（a）delete(linklist *p)/*删除*p结点的后继结点*/linklist *r；r=p-next；if(r!=NULL)p-next=r-next；,free(r)；,/*delete*/（b）linklist*delete(linklist*head，int i)/*删除单链表head的第i个结点*/int j=0；linklist *p，*s，*q；p=head；j=0；while(p-next!=NULL)&(jnext；j+；,if(p-next!=NULL)q=p-next；p-next=p-next-next；free(q)；else return NULL ；s=head；return s；/*delete*/该算法时间复杂度为O(n)。,例，将两个递增的单链表合并为一个递增单链表，且要求不重新开辟空间，其算法可描述如下：,void*union(linklist*heada，linklist*headb),/*合并单链表heada与headb*/linklist *p，*q，*r，*u；,p=heada-next；q=headb-next；r=heada；while(p!=NULL)&(q!=NULL)if(p-data q-data；u=q-next；r-next=q；r=q；q-next=p；q=u；,else if(p-data data)r=p；p=p-next；,if(q!=NULL)r-next=q；/*union*/,2.3.3 循环链表,如果将单链表最后一个结点的指针域改为存放链表中头结点（或第一个表结点）的地址值，就使得整个链表构成一个环，如图2.10所示，这样的链表称为循环链表。显然，它是一种首尾相接的链表，从循环链表中任一个结点出发都可访问到表中所有其它结点。对单链表的链接方式稍作一些改变，就可构成一个新的存储结构单循环链表。同样，也有多重链的循环链表。在循环链表中，为了使空表和非空表的处理一致，同样可设置一个头结点。,循环链表的基本运算与单链表基本一致，差别只在于最后一个结点的循环处理上。只要将单链表算法中出现NULL处改为头指针即可。,例如，将单循环链表倒置或逆置。linklist*invert(head)linklist*head；linklist *p，*q，*s;q=head；p=head-next；while(p!=head)s=q；q=p；p=p-next；q-next=s；p-next=q；return head；/*invert*/,2.3.4 双向链表,在单循环链表中，从任一个已知结点出发可以找到其前趋结点，但时间耗费需O(n)，若希望能快速确定一个结点的直接前趋，可以再加上一个指针域存储其直接前趋的信息，这样就可以构成双向链表，它有两个方向不同的链，如果将每个方向的链表构成一个环，则可以构成双向循环链表。,双向链表的C语言描述：,typedef struct dupnode elemtype data；struct dupnode*next，*prior；dulinklist；dulinklist*head;,双向循环链表也可由头指针head唯一确定，同样可增加头结点，使得双链表的某些运算简便一些，如图2.11所示。,由于双向链表在其结构中，每个结点既有指向其直接前趋的指针域，又有指向其直接后继的指针域，因此比起单链表来，要在一个双向链表中检索某一个已知结点的直接前趋和后继结点要方便得多。,结点*p可通过多种方式访问，设指针p指向双向链表中某个结点，则有：p-next-prior=p=p-prior-next,双向链表中结点的插入情况如图2.12所示。,在*p结点之前插入结点*s的正确步骤应为：p-prior-next=s；s-prior=p-prior；s-next=p；p-prior=s；,由于双向链表中每个结点涉及两个指针的运算，对于某些运算要注意运算顺序。,在上面的步骤中指针p-prior的修改必须在*p结点的前趋结点*(p-prior)的后继指针修改之后方可改动，否则会不能正确地插入结点。在双向链表中删除一个结点*p的指针变化如图2.13所示。,指针修改的运算步骤为：,p-prior-next=p-next；,p-next-prior=p-prior；,1插入算法 void indulist(dulinklist*head,int i,elemtype x)/*在双向循环链表head中的第i个结点之前插入值为x的新结点*/dulinklist*p，*s;int j;p=head;j=0;while(p-next!=head),if(i 0),s-data=x;s-next=p-next;s-prior=p；p-next=s；s-next-prior=s;,else printf(“error！n”)/*indulist*/,2删除算法 void deledulist(dulinklist*head,int i),/*删除双向链表head中的第i个结点*/dulinklist*p;int j;p=head;j=0;while(p-next!=head)/*deledulist*/以上两个算法的时间复杂度都为O(n)。,一般而言，对存储结构的选择应主要从存储空间、运算时间、程序设计语言三方面考虑。（1）存储空间。（2）运算时间。（3）程序设计语言。线性表的顺序实现和链接实现各有优缺点，只能根据实际问题的具体实现需要，对各个方面的优缺点加以综合平衡后来确定适宜的存储结构。,2.4 线性表存储结构的选择,2.5 线性表的应用举例,在数学上，一个一元多项式Pn(x)可写成：Pn(x)=p,0,+p,1,x+p,2,x,2,+p,n,x,n,显然，该多项式可以由每项的系数p,0,，p,1,，p,n,唯一地确定，所以，可以将它用一个线性表P来表示成：P=(p,0,，p,1,，p,i,，p,n,)若Qm(x)也是一元多项式，则其也可用线性表Q表示为：,Q=(q,0,，q,1,，q,m,)则Pn(x)+Qm(x)同样也可用线性表R表示。设mexpq-exp，此时*q结点应为和多项式中的一项，*q 结点应插在*p结点之前，然后q指针在原来的链表上后移。,（2）若p-exp=q-exp，则对应项的系数相加，若系数和不为零，只要修改*p 结点的系数域，释放q结点，否则，应删除*p 结点，释放p、q结点。,（,3）若p-expexp，则*p 应为和多项式的一项，p指针在原来的链表上后移。,其算法描述如下：polynode *polyadd(pa，pb),polynode *pa,*pb;polynode*p,*q,*pre,*r;float x;p=pa-next;q=pb-next;pre=pa;while(p!=NULL),else if(p-exp=q-exp)x=p-coef+q-coef;if(x!=0)p-coef=x;pre=p;,else pre-next=p-next;free(p);p=pre-next;r=q;q=q-next;free(r);,else,if(p-expexp)pre=p;p=p-next;/,if(q!=NULL)/pre-next=q;free(pb);return pa；/*polyadd*/假设P多项式n项，Q多项式m项，则该算法的时间复杂度为O(m+n)。,图2.15和图2.16为两多项式相加和的示意图，其中空白结点表示已被释放的结点空间。,第3章 栈和队列,3.1 栈,3.2 栈的应用举例,3.3 队列,3.4 队列的应用举例,第3章 栈和队列,栈和队列是两类特殊的线性表，其逻辑结构仍然是线性结构，但栈和队列是运算受限的线性表。栈和队列结构被广泛应用于各种程序设计中。,本章讨论栈和队列的定义、运算及其实现等。,3.1.1 栈的定义及其运算,栈是一类特殊的线性表，,数据元素的插入和删除运算,只能在表的一端进行，,通常将进行插入和删除的一端称为栈顶，另一端称为栈底。将元素的插入称为入栈或进栈，元素的删除称为出栈或退栈。栈也称为后进先出的线性表（简称LIFO表）如图3.1(a)所示。,在日常生活中，栈的形式经常出现。例如，一叠盘子或一叠书的取放、铁路调度站，如图3.1(b)所示。,栈的基本运算：,（1）置空栈setnull(s)：将栈s置成空栈，建立起栈顶指针。,（2）判栈空empty(s)：若s为空栈，则返回TRUE值，否则返回FALSE值。,（3）入栈push(s,x)：若s未满，将x插入s栈栈顶，并使栈顶指针指向x。,（4）出栈pop(s)：若s栈非空，则从栈中删去栈顶元素，返回原栈顶元素。,（5）取栈顶元素gettop(s)：若s栈非空，则返回当前栈顶元素。,3.1 栈,3.1.2 栈的顺序存储结构,栈的顺序存储结构又称为顺序栈，顺序栈也可用向量来实现。顺序栈的类型定义如下：,#define MAXSIZE 100 /*栈的最大容量，这里设为100*/typedef struct datatype stackMAXSIZE;int top;seqstack;/*顺序栈类型定义*/seqstack*s;/*定义s为指向顺序栈的指针变量*/,在顺序栈中进栈或出栈运算时要注意空间的“溢出”。当栈满时，若再进行入栈运算，会产生空间“上溢”；而当栈空时，再进行出栈运算，会产生空间“下溢”。图3.2说明了栈中元素与栈顶指针的关系。,在顺序栈上实现的栈的基本运算。,（1）置空栈,void setnull(seqstack*s),s-top=-1;,（2）判栈空算法 int empty(seqstack*s)if(s-toptop=MAXSIZE-1)printf(“stack overflow！n”);return(FALSE);else s-stack+s-top=x;return(TRUE);,（4）出栈 datatype pop(seqstack*s)if(s-toptop-;,return(s-stacks-top+1);（5）取栈顶元素算法 datatype gettop(seqstack*s)if(s-topstacks-top);,有时可以将多个栈安排在同一个顺序存储空间中，实现多个栈共享存储空间。假定两个栈共享空间，可以给它们分配一个长度为m的数组空间如图3.3所示。,两个栈共享的数据类型定义如下：,typedef struct,datatype stackm;,int top2;/*top0和top1分别为两栈的栈顶指针*/,sharedstack;,两个栈,共享存储单元,的部分运算算法如下：,（1）置空栈 void setnull(sharedstack*s)s-top0=-1;s-top1=m;/*setnull*/（2）入栈 int push(sharedstack*s，int i，datatype x)if(i1|s-top0+1=s-top1)return FALSE;else if(i=0)s-stack+s-top0=x;else s-stack-s-top1=x;return TRUE;/*push*/,（3）出栈 datatype pop(sharedstack*s，int i)if(i1)return NULL;else if(i=0)if(s-top0=-1)return NULL;else return（s-stacks-top0-）;else if(s-top1=m)return NULL;else return（s-stacks-top1+）;,/*pop*/,3.1.3 栈的链式存储结构,栈的链式存储结构称为链栈。链栈是运算受限的单链表，其运算只能在链表头部进行，其头指针就是栈顶指针。,链栈的数据类型定义：,typedef struct node,datatype data;,struct node*next;,linkstack;,linkstack *top;/*链栈头指针，即栈顶指针*/,链栈如图3.5所示，其中top是栈顶指针。当top=NULL时，该链栈是空栈。,链栈的入栈和出栈运算算法。（1）入栈 void push(linkstack*top，datatype x)linkstack*p;p=(linkstack*)malloc(sizeof(linkstack);/*生成一个新结点*p*/p-data=x;p-next=top;top=p;（2）出栈 datatype pop(linkstack*top)linkstack*p;datatype x;if(top=NULL)printf(stack empty！n);return(NULL);,else ptop；top=top-next;x=p-data;free(p);/*释放p所指的结点*/return(x);,3.2 栈的应用举例,3.2.1 表达式求值,一般的，一个表达式由操作数、运算符和分界符组成。,若运算符出现在两个运算数或操作数之间（单目运算符除外），称为中缀表达式。中缀表达式有利于人的理解，但不适合机器的实现。,因此，,在编译系统中，要把中缀表达式变换成一种后缀表达式（也称为逆波兰式），在后缀表达式中，运算符处在两个操作数之后。后缀表达式一不需要使用括号；二不需要考虑运算符的优先级，只需从左到右扫描后缀表达式，当扫描遇到运算符时，就把它前面的两个操作数取出，然后进行运算。如图3.6所示。,把中缀表达式变换为相应的后缀表达式，然后根据后缀表达式计算表达式的值，这两个步骤都可以利用栈结构来实现。,运算,后缀表达式,ABCD/-E*+,T,1,C/D,ABT,1,-E*+,T,2,B-T,1,AT,2,E*+,T,3,T,2,*E,AT,3,+,T,4,A+T,3,T,4,图3.6 后缀表达式的计算过程,要把中缀表达式转变为后缀表达式可以从左到右依次扫描中缀表达式，根据所读到的是操作数还是运算符，利用栈并结合各个运算符之间的优先级关系（表3-1）来进行运算。其,算法思想是：设置一个栈并初始化，然后从左到右顺序读入中缀表达式。当读到的是操作数时就直接将其输出，并接着读下一个。当读到的是运算符时，就将它赋给,2，并根据运算符的优先级关系表3-1，比较,2与当前栈顶运算符,1的优先级。若,2的优先级比,1的高，则将,2进栈，继续读下一个；若,2的优先级比