C语言入门教程全第9章.ppt

第9章 数据结构与算法基础,9.1 数据结构与算法概述 9.2 线性表9.3 栈和队列 9.4 树和二叉树 9.5 图9.6 排 序9.7 查 找本章小结习题九,9.1 数据结构与算法概述,9.1.1 数据结构的相关概念实践证明，要想更有效地使用计算机，仅仅掌握计算机语言而缺乏数据结构和算法的有关知识，是难以处理诸多复杂应用问题的。早期的计算机主要解决纯数值计算的问题，以此为加工对象的程序设计称为数值型程序设计。其涉及的操作对象比较简单，其一般为整型、实型数据等。,后来，随着计算机应用领域的不断拓宽，解决非数值计算的问题越来越引起人们的关注。例如，金融管理、文献检索、计算机辅助设计等。这些问题主要集中于对数据集合中的各元素以各种方式进行运算，如插入、更新、删除、查找等。在此涉及的数据类型比较复杂，而且数据元素之间具有各种特定的联系，所以，如果了解了数据集合中元素之间的关系以及如何组织和表示这些数据，就能大大提高计算机处理问题的效率。,数据结构是一门研究非数值运算的程序设计问题的学科，它包含以下3个方面的内容：（1）数据集合中各数据元素之间的逻辑结构。（2）对数据进行处理时，各数据元素在计算机中的存储（物理）结构。（3）对数据的抽象运算。1数据（data）数据是反映客观事物信息符号的集合，也是计算机程序要加工的对象。这个集合中包括客观事物,的数值、字符以及能够输入到计算机中并被计算机程序处理的符号。计算机发展初期，由于计算机主要用于数值计算，数据指的就是数值。随后由于计算机应用的普及，数据的含义也比原来变得更加广泛。如文字、表格、声音、图形、图像等都属于数据的范畴。2数据元素（data element）数据元素是数据集合中的客体（个体），是数据的基本单位，有时也称为节点或记录。例如数据,集合N=1，2，3，4，5中整数15都是数据元素。每个数据元素的表现形式是由一个或多个数据项组成的。数据项是具有独立含义的最小标识单位，例如，在老师档案信息管理中的每一位老师就是一个数据元素，组成它的数据项可以是姓名、性别、年龄等。3数据对象（data object）数据对象是具有相同特性的数据元素的集合，是数据的一个子集。例如，一周中的7天就是一个,数据对象，可表示为集合W=Mon，Tue，Wed，Thu，Fri，Sat，Sun；再如，字母数据对象可表 示为集合C=A，B，Z。4数据类型（data type）数据类型是一个值的集合和定义在该值集上的一组操作的总称。程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系，它不仅规定了该变量可以设定的值的集合，还规定了该集合上的运算。各种语言规定了它所允许的数据类型。,在C语言中，基本数据类型包括整型、实型等，这些变量的值是不可再分的；而构造类型包括数组、结构体等，这些变量的值是可以再分的，也可以说它们是带结构的数据，它们的成分可以是基本数据类型，也可以是构造数据类型等。5数据结构（data structure）数据结构指的是数据之间的相互关系，即数据的组织形式。可以用集合论的方法定义数据结构如下：,S=(D,R)D=ai|aiElemSet,i=0,1,2,3,n,n0R=|ai-1,aiD,2in数据结构S是一个二元组，其中D是一个数据元素的有限集合，R是定义在关系D上的有限集合，即R是由有限个关系所构成的集合。若n=0时，则D是一个空集。数据结构分为逻辑结构与物理结构两种。,（1）数据的逻辑结构。数据的逻辑结构就是数据元素间的逻辑关系，它研究的是数据元素及其关系的数学特性，与数据的存储无关，是独立于计算机的。数据的逻辑结构可概括地分为线性结构和非线性结构两种，如图所示。,图9.1.1 数据的逻辑结构,线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，除第一个元素以外，其他元素有且仅有一个直接前驱；除最后一个元素外，其他元素都有且仅有一个直接后继。非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继。线性结构主要有线性表、栈和队列等，而非线性结构分为树型结构和图型结构等。,（2）数据的物理结构。数据的物理结构又称存储结构，是数据及其关系在计算机中的存放形式，是逻辑结构在计算机存储器中的映像，也就是它的具体实现，通常用高级语言中各种数据类型来描述。在进行实际的数据处理时，被处理的数据都是存放在计算机的存储空间中，而且，各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的。因此，为了能表示出存放在计算机存储空间,的各个节点之间的逻辑关系，在数据的存储结构中，不但要存放各个节点的信息，还要存放各个节点之间逻辑关系的信息。下面介绍4种常见的存储结构：1）顺序存储结构。顺序存储结构主要用于线性的数据结构。它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中，各节点之间的逻辑关系由存储单元的邻接关系来体现。,如图所示为顺序存储结构，假设每个节点占据长度为l（字母，以下同）的存储空间，这个逻辑结构在物理存储器中以一定的顺序占用连续的存储空间。对于这种结构，只需要知道第一个元素的地址和每一个元素所占的存储单元数就可以得到任何一个元素所在的位置。在顺序存储结构中存取任意一个元素所需要的时间是相等的。,图9.1.2 顺序存储结构,2）链式存储结构。顺序存储结构比较适合于线性结构，而非线性结构一般很难用顺序存储结构来实现，所以，通常不用顺序存储结构，而是用链式存储结构来实现非线性结构。链式存储结构是给节点附加指针字段。在这种存储结构中，节点所占的存储单元分为两部分：一部分是用来存放节点自身的信息，称为数据域；另一部分是用来存放该节点后继节点的存储单元的地址，称为指针域。指针域中可以有一个或者多个指针，用来表示节点的一个或多个后继，也可以用来,表示其他节点的地址。在用链式存储结构存储一个非线性结构时，节点中的指针个数可以根据该节点的直接后继个数来设置。如图所示的链式存储结构，在Addr1的存储单元中，既包含了节点a1本身的信息，又包含了它的后继节点a2的存储单元的地址Addr1+3l，其他节点与此类似。,图9.1.3 链式存储结构,由此不难看出，链式存储结构可以存储线性结构，也可以存储非线性结构。在链式存储结构中，各个节点在存储空间中的前后位置关系与其逻辑顺序也可以不一致，其存储空间也可以不连续。3）索引存储结构。在线性结构中，所有节点可以排成一个序列，每个节点在该序列中都有对应的位置值，这个位置值就是节点的索引号。索引存储结构是用节点的索引号来确定节点的存储地址。可用以下两种方法实现索引存储：,建立一个附加的索引表，索引表中第i项的值就是第i个节点的存储地址。如果每个节点所占单元数都相等，可用位置值的线性函数的值来指出节点对应的存储地址，即第i个节点di的地址为LOC(di)=(i-1)l+d，其中l为节点所占单元数，d为开始节点d1对应的存储地址。4）散列存储结构。散列存储结构是指根据节点的关键字值来确定其存储地址，也称为哈希法。用这种方法进行存储时，每个节点分散地存储在存储,单元中，其查找的效率是很高的，关键问题是怎样选择哈希函数和研究解决冲突的办法。上述4种存储结构也可以组合起来对数据进行存储映像。同一个逻辑结构可以有多种不同的存储方法，应根据具体情况进行选择。另外，存储结构只是数据结构的一个重要方面，如果逻辑结构相同但存储结构不同，也是不同的数据结构。例如，如果用顺序存储结构存储线性表，则称为顺序表；如果用链式存储结构存储线性表，则称为链表。,9.1.2 算法评价在第3章中读者已初步了解了算法的概念、特性等，在前面其他章节的编程举例中还学习了不少给定的算法。而解决同一个问题通常有许多不同的算法。算法评价的目的首先在于从解决同一个问题的不同算法中选择出较为合适的一种，其次在于知道怎样对现有算法进行改进，进而设计出更好的算法。对于算法的评价可以从以下几个方面进行。,1正确性正确性（correctness）是设计和评价算法的首要条件，一个正确的算法是指在有合理的数据输入的情况下，能够在有限的运行时间内得出正确的结果。要从理论上证明一个算法的正确性，并不是一件容易的事，所以通常可采用各种典型的输入数据上机调试算法，并使算法中的每段代码都被测试过，若发现错误及时修正，最终可以验证出算法的正确性。,2健壮性健壮性（robustness）是指一个算法对不合理（又称不正确、非法、错误等）数据输入的反应和处理能力。一个好的算法应该能够识别出错误数据并进行相应的处理。对错误数据的处理一般包括打印出错误信息、调用错误处理程序、返回标识错误的特定信息、中止程序运行等。,3可读性可读性（readability）是指一个算法供人们阅读和理解的容易程度。一个可读性好的算法，应该符合结构化和模块化程序设计的思想，应该对其中的每个功能模块、重要数据类型或语句加以必要注释；应该建立相应的文档，对整个算法的功能、结构、使用及有关事项进行说明。4简单性简单性（simplicity）是指一个算法所采用数据,结构和方法的简单程度。如对数组进行查找时，采用顺序查找的方法比采用二分查找的方法要简单；对数组进行排序时，采用简单选择排序的方法比采用堆排序或快速排序的方法要简单。但最简单的算法往往不是最有效的，即有可能占用较长的运行时间和较多的内存空间。算法的简单性便于用户编写、分析和调试，所以对于处理少量数据的情况是适用的，但若要处理大量的数据，则算法的有效性比简单性更重要。有效性主要表现为时间复杂度和空间复杂度。,5时间复杂度时间复杂度（time complexity）是指计算机执行一个算法时在时间上的消耗度量。度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算。通常人们采用第二种方法，所以这里只介绍事前分析估算方法。一般情况下，把算法中一条语句重复执行的次数称为此语句的频度，它常表示为问题规模n的某个函数，记作F(n)。而算法的时间复杂度则记作,T(n)=O(F(n)下面举例说明如何求时间复杂度：for(i=0;in;i+)for(j=0;jn;j+)bij=0;for(k=0;kn;k+),bij=bij+aik*akj;以执行次数最多的语句（bij=bij+aik*akj;）进行计算：语句频度：F(n)=n3时间复杂度：T(n)=O(F(n)=O(n3)下列程序段的时间复杂度如下：,（1）x=x+1;T(n)=O(1)（2）for(j=0;jn;j+)x=x+1;T(n)=O(n)（3）for(j=0;jn;j+)for(k=0;kn;k+)x=x+1;T(n)=O(n2)算法的时间复杂度一般是以数量级的形式给出，常见的时间复杂度如下：,（1）O(1)：常量型；（2）O(n)，O(n2)，.，O(nk)：多项式型；（3）O(log2n)，O(2log2n)：对数型；（4）O(2n)，O(en)：指数型。6空间复杂度空间复杂度（space complexity）是指在一个算法的运行过程中，对临时耗费的存储空间的度量，而不包括问题的原始数据占用的空间（因为这些单元与算法无关）。,空间复杂度的表示类似于算法的时间复杂度，可记作S(n)=O(F(n)分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般算法本身较简短，所占用的存储空间较少，但运行时需一个附加堆栈，从而占用较多的临时存储空间；若改成非递归算法，则一般可能算法本身较长，所占用存储空间较多，但运行时可能占用较少的临时存储空间。,高效且低内存要求的算法最好，但在算法中的时间与空间往往是相互影响的，要节约空间往往就要消耗较多的时间，反之亦然。目前由于计算机硬件的发展，一般都有足够的内存空间，因此在算法评价中应着重考虑时间因素。9.1.3 算法分类通常，需要人们解决的特定问题可被分为数值的和非数值的两大类，所以算法通常分为数值算法和非数值算法两类。,1数值算法解决数值问题的算法叫做数值算法。科学和工程计算方面的算法属于数值算法，如求解数值积分、线性方程组、代数方程和微分方程等。2非数值算法解决非数值问题的算法叫做非数值算法。数据处理方面的算法大多属于非数值算法，如在各种数据结构上进行的排序算法、查找算法、插入算法、删除算法、遍历算法等。,数值算法和非数值算法并没有严格的划分，一般说来，在数值算法中主要进行算术运算，而在非数值算法中，则主要进行比较和逻辑运算。,9.2 线性表,9.2.1 线性表的定义及其运算1线性表的定义线性表（linear_list）是由n（n0）个元素a1，a2，a3，an组成的一个有限序列，它有且只有一个开始节点，该节点没有前驱且只有一个后继；有且只有一个终端节点，该节点没有后继且只有一个前驱，其他所有节点都是有且只有一个前驱和一个后继。线性表是最基本、最简单、最常用的数据结构。,在日常生活中，能够找出很多线性表的例子，例如：（1）人民币面值构成线性表（1角、2角、5角、1元、2元、5元、10元、20元、50元、100元），其中每一种面值为一个数据元素。（2）一个n维向量x=(x1,x2,x3,xn)，其中每一个分量为一个数据元素。（3）一年有4个季节（春、夏、秋、冬），其中每一季节为一个数据元素。,现实中客观存在的实体经过数学抽象后都可以用线性表的形式表示如下：L=(a1,a2,an)其中，L为线性表，ai(i=1,2,n)是属于某数据对象的元素，a1为开始节点，an为终端节点，ai-1是ai的前驱，ai是ai-1的后继。n(n0)为元素个数，又称为表长，n=0时，为空表。线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同的特征。从上述对线性表的描述可知线性表是一种线性结构。,2线性表的基本运算线性表是一种非常灵活的数据结构，不仅可对线性表的数据元素进行访问，还可对其进行插入和删除等其他操作。（1）建立一个空线性表。（2）判断空表。（3）求线性表的长度，返回线性表中数据元素的个数。（4）读取线性表中的某个元素。,（5）插入，在线性表的某一个位置插入一个新元素。（6）删除，删除线性表中的某个元素。9.2.2 线性表的顺序存储结构1顺序表在计算机中可以用不同的方式来表示线性表，其中最简单和最常用的存储方式是用一组地址连续的存储单元来依次存放线性表的数据元素，这种表示称为线性表的顺序存储结构，也称为向量式存储,结构。如图所示的就是顺序存储线性表的存储形式。假设已知线性表中每个元素占l个单元，且线性表在内存中的首地址为Addr(a1)，则线性表中第i个元素ai的存储地址为Addr(ai)=Addr(a1)+(i-1)l（1iLength(L)）其中，Length(L)是线性表L的长度，这种存储结构只要确定了存储线性表的起始位置就很容易找到,第i个数据元素，且无论序号i为何值，找到第i个元素所需的时间相同，故这种存储结构也称为随机存储结构。顺序存储的线性表通常称为顺序表。在高级语言中常用一维数组类型表示顺序表，因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。,顺序表用C语言定义如下：typedef struct ElemType*elem;/*elem为顺序表空间的基地址，ElemType表示元素的数据类型*/int listsize;/*listsize为顺序表的存储空间容量（字节数）*/int length;/*length为顺序表的长度*/SqList;,顺序表的存储结构具有以下两个基本特点：（1）顺序表中，所有元素所占的存储空间是连续的。（2）顺序表中，各数据元素在存储空间中是按逻辑顺序依次存放的。由此看出，在线性表的顺序存储结构中，其逻辑上相邻的两个元素在存储空间中也是相邻的。如果顺序表中各数据元素所占的存储空间相等，则在该顺序表中查找某一个元素是非常方便的。,2顺序表的基本运算在顺序存储结构中，线性表的某些运算比较容易实现，如求线性表的长度、读线性表中的元素等，下面只重点讨论线性表的插入与删除运算。（1）插入运算。首先举一个例子来说明如何在顺序存储结构的线性表中插入一个新元素。如图（a）所示，一个长度为8的线性表顺序存储在长度为10的存储空间中。现在要求在第2个元素（即37）之前插入一个新元素55。其插入过,程如下：1）从最后一个元素开始直到第2个位置，每一个元素均依次往后移动一个位置。2）将新元素55插入到第2个位置。插入一个新元素后，线性表的长度变成了9，如图（b）所示。如果再要在线性表的第9个元素之前插入一个新元素32，则采用类似的方法：将第9个元素往后移动一个位置，然后将新元素插入到第9个位置。插,入后，线性表的长度变成了10，如图（c）所示。现在，为线性表开辟的存储空间已经满了，不能再插入新的元素了。如果再要插入，则会造成称为“上溢”的现象。,图9.2.1 顺序表的插入,一般来说，设一个长度为n的线性表为(a 1,a2,ai,an)要在线性表的第i个元素ai之前插入一个新元素b，插入后得到长度为n+1的线性表为(a1,a2,ai-1,b,ai,an)一般情况下要在第i（1in）个元素前插入一个新元素时，先要从最后一个（即第n个）元素开始，直到第i个元素，之间共ni+1个元素，依次向后移一个位置；空出第i个位置，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。,显然，在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第n个元素之后（可以认为是在第n+1个元素之前）插入新元素，只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。所以，如果插入运算在第i（1in）个元素之前进行，则原来第i个元素之后（包括第i个元素）的所有元素都必须向后移动。,【注意】本章所有算法描述中有一些预定义的常量，其定义如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW-1typedef int ElemType;,（2）删除运算。首先举一个例子来说明如何在顺序表中删除一个元素。如图（a）所示，一个长度为8的线性表顺序存储在长度为10的存储空间中，现在要求删除线性表中的第1个元素（即删除元素32）。其删除过程如下：从第2个元素开始直到最后一个元素，每一个元素均依次往前移动一个位置。此时，线性表的长度变成了7，如图（b）所示。如果再要删除线性,表中的第5个元素，则采用类似的方法：将第6和第7个元素依次往前移动一个位置。此时，线性表的长度变成了6，如图（c）所示。,图9.2.2 顺序表的删除,一般来说，设长度为n的线性表为：（a1,a2,ai,an），现要删除第i个元素，删除后得到长度为n1的线性表为：（a1,a2,ai-1,ai+1,an）。一般情况下，要删除第i（1in）个元素，则要从第i+1个元素开始，直到第n个元素，之间共有ni个元素，依次向前移动一个位置。删除结束后，线性表的长度就减小了1。很显然，在线性表采用顺序存储结构时，如果删除运算在线性表的末尾进行，即删除第n个元素，则不需要移动表中的元素；如果要删除线性表,的第1个元素，则需要移动表中所有的元素。所以如果要删除第i（1in）个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。算法描述如下：,3算法分析从上面两个算法可看出，顺序表的插入与删除运算，其时间主要花费在移动元素上，而移动元素的个数不仅依赖于表长n，而且还与插入和删除的位置有关。在平均情况下，要在顺序表中插入或删除一个元素，需要移动表中一半的元素。若表长为n，则两个算法的时间复杂度为O(n)。,由此看出，当表长n较小时，算法的效率较高，此时顺序存储结构对于较小的线性表或者其中元素不常变动的线性表来说是合适的。但当表长n较大时，算法的效率较低，因此顺序存储结构不适合元素经常需要变动的、较大的线性表。9.2.3 线性表的链式存储结构线性表顺序存储结构的特点是逻辑上相邻的两个元素在物理位置上也相邻，这个特点使得我们可以随机存取顺序表中任意元素，但是这种存储结构也存在以下不足：,（1）在插入或删除元素时需移动大量元素。（2）在给长度变化较大的线性表预先分配存储空间时，必须按最大空间分配，使存储空间不能得到充分利用。（3）表的容量难以扩充。下面介绍线性表的另一种存储结构，即链式存储结构，它克服了顺序表的不足，它不要求在逻辑上相邻的两个元素在物理位置上也必须相邻。链式存储的线性表通常称为链表。下面介绍几种常见的链表。,1单链表线性表的链式存储结构不需要一组连续的存储单元，它的数据元素可以分散存放在存储空间中。为了使线性表在逻辑上保持连续，必须在每个元素中存放其后继元素的地址，如图（a）所示。这样由n个节点组成的序列便构成一个线性表的链式存储结构，称为链表，如图（b）所示。由于这种链表的每个节点中只包含一个指针域，故又称为线性链表或单链表。,图9.2.3 线性表的链式存储结构,在链式存储结构中，每一个数据元素由两部分组成：一部分存放元素的值，称为数据域；另一部分存放后继元素的存储地址，称为指针域。即节点a的结构为用data表示数据域，用next表示指针域。其中指示链表中开始节点（第一个节点）地址的指针称为头指针，用“head”表示，最后一个节点的指针为空指针，用“NULL”或符号“”表示。,有时我们在单链表的第一个节点之前附加一个节点，称为头节点。头节点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，它的指针域存储指向第一个节点的指针，也就是第一个元素节点的存储位置。如图（a）所示，单链表的头指针指向头节点。当表空时只有一个头节点，它的指针域为空，如图（b）所示。,图9.2.4 带头节点的单链表,由于单链表可用头指针唯一确定，因此在C语言中可用结构指针来描述，其节点类型定义如下：typedef struct Lnode/*定义单链表节点类型*/ElemType data;struct Lnode*next;Lnode,*LinkList;假设L是LinkList型变量，则L为单链表的头指针，指向表中第一个节点。若L为“空”（L=NULL），,则所表示的线性表为“空”表，其长度n为“0”。在单链表中，任何两个元素的存储位置之间没有必然的联系，不能从线性表的起始位置直接求出某一元素的位置。欲取得某个数据元素必须从头指针出发寻找，因此单链表是非随机存取的存储结构。2单链表的基本运算在讨论单链表的插入、删除运算前，先对一些基本操作进行介绍，插入、删除运算是这些基本操作的组合。设p，q，s均为指针类型变量，它指向,数据域为data，指针域为next的节点，如图所示为单链表的几种基本操作。,图9.2.5 单链表的基本操作,（1）插入运算。在顺序表进行元素插入运算时需要移动大量的元素，而在单链表中元素的插入只需要修改有关的指针内容，不需移动元素。在单链表上进行插入运算时指针的变化如图所示。,图9.2.6 单链表上插入节点时指针的变化情况,上述指针修改可描述如下：s-next=p-next;p-next=s;在进行指针的修改时，必须要注意其修改的顺序，假如把上述两条语句顺序颠倒，那么执行结果就完全错误。在带头节点的单链表的第i个元素之后插入元素x的算法描述如下：ListInsert_L(LinkList*L,int i,ElemType x),（2）删除运算。单链表的删除运算与插入运算一样，在删除时，不需要移动元素，只须修改有关的指针内容。在单链表上进行删除运算时指针的变化如图所示。上述指针修改可描述如下：p-next=p-next-next;,图9.2.7 单链表上删除节点时指针的变化情况,在带头节点的单链表中删除第i个元素的算法描述如下：,3其他形式的链表根据实际需要，线性表的链式存储结构还有循环链表和双向链表等其他形式。（1）循环链表。循环链表是线性表的另一种链式存储结构，它的特点是表中最后一个节点的指针域不为空，而是指向表头，整个链表形成一个环。如图（a）、（b）所示分别表示具有头节点的非空循环链表和空循环链表。,图9.2.8 循环链表,循环链表与一般链表的不同之处在于只要给定循环链表中任一节点的地址，就可以遍历表中所有节点，而不必从头指针开始。这样有可能对某些运算带来方便。,（2）双向链表。前面讨论的链表都是单向链表，它们只能单方向地寻找表中的节点，若要寻找前驱节点，则需从表头指针出发查找或向后循环一周查找，当表长为n时执行时间为O(n)。为克服其单向性缺点，可采用双向链表。在双向链表的节点中有两个指针域，一个指向直接后继，一个指向直接前驱，如图所示。,图9.2.9 双向链表,双向链表的节点类型定义如下：typedef struct Dlnode/*定义双向链表节点 类型*/ElemType data;struct DLnode*left;struct DLnode*right;DLnode,*DLinkList;,此类型包含有3个域：数值域data、左指针域left和右指针域right。left域用于指向其前驱节点，right域用于指向其后继节点。由于双向链表具有对称性，因此从表中某一给定的节点可随意向前或向后查找。但在执行插入、删除运算时，需同时修改两个方向上的指针。,9.2.4 线性表的应用一元多项式相加是线性表的一个典型应用实例。多项式的操作是表处理中经常出现的操作，我们以一元多项式相加为例，说明线性链表在实际中的应用。一个一元多项式Pn(x)可以表示为Pn(x)=P0+P1x+P2x2+pnxn该多项式按升幂排列，并由n+1个系数唯一确定，因此可以用一个线性表P表示为,P=(p0，p1，p2，pn)其指数i隐含在系数pi的序号内。一元多项式的存储结构可以采用顺序存储结构，也可以用链式存储结构，这要取决于执行何种操作。如果只求多项式的值，无须修改多项式的系数和指数，则采用顺序存储结构为宜。但在进行多项式相加时，通常要改变多项式的系数和指数，而且在实际问题中，经常会出现多项式的次数很高但又存在大量的零系数项的情况，例如：,S(x)=8+2x1050+3x2000这时如果采用顺序存储结构会浪费大量的存储空间，故一般采用链式存储结构。用链式存储结构表示多项式是把每一个非零系数项构成链表中的一个节点，节点是由两个数据域和一个指针域构成，如图（a）所示。其中，exp(i)表示该项的指数，称为指数域；coef(i)表示该项的系数，称为系数域；next(i)是指向下一个非零系数的节点，称为指针域。整个多项式Pn(x)如图（b）所示。,图9.2.10 一元多项式的链式存储结构,设有一元多项式A(x)和B(x)，现要求其相加结果C(x)=A(x)+B(x)。其运算规则为：将两个多项式中指数相同的项对应系数相加，若和不为零，则构成C(x)中的一项；A(x)和B(x)中所有指数不相同的项均复制到C(x)中。,其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个节点，则比较两个节点中的指数项，有下列3种情况：（1）指针qa所指节点的指数值指针qb所指向节点的指数值，则应摘取qb指针所指节点插入到C(x)链表中去。,（3）指针qa所指节点的指数值=指针qb所指向节点的指数值，则把两个节点中的系数相加，若和数不为0，则修改qa所指节点的系数值，同时释放 qb所指向节点；反之，从多项式A的链表中删除相应节点，并释放指针qa和qb所指节点。如图（a）所示，为带头节点的单链表表示的多项式A5(x)=8-2x+15x5，B8(x)=2x+7x4-9x5+3x8；如图（b）所示表示相加后的“和多项式”C(x)。,图9.2.11 用链式存储结构进行多项式求和,9.3 栈和队列,9.3.1 栈的定义及其运算1栈的定义栈（stack）又称堆栈，它实际上是一种操作受限的特殊的线性表，是限定仅在表的一端进行插入和删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，自然也是最先被删除的元素；栈底元素总是最先被插入的元素，自然也是最后才被,被删除的元素。也是说栈是按照“先进后出”（First In Last Out，FILO）或者“后进先出”（Last In First Out，LIFO）的原则组织数据的，所以，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆功能。通常用指针top指示栈顶的位置，用指针bottom指向栈底。向栈中插入一个元素（即插入为新的栈顶元素）称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算。栈顶指针top动态反,图9.3.1 栈的示意图,映了栈中元素的变化情况。如图所示为栈的示意图。,栈这种结构在日常生活中是很常见的。例如子弹夹就是一种栈的例子，最先压入的子弹总是最后一个被弹出，而最后压入的子弹最先被弹出，这就遵循了“后进先出”或“先进后出”的原则。2栈的基本运算（1）建立一个空栈。（2）判断空栈。（3）读栈顶元素。（4）求栈的长度，返回栈的数据元素个数。,（5）入栈，将元素插入到栈顶。（6）出栈，删除栈顶元素。9.3.2 栈的存储结构1栈的顺序存储结构顺序栈实现栈的顺序存储结构最简单的方法是用一维数组来存储。由于栈底不变，而栈顶是随入栈、出栈操作动态变化的，因此必须记住栈顶的位置，并且由于栈是有容量限制的，因此用C语言定义顺序栈的结构如下：,#define Stack_NUM 100#define Stack_MORENUM 10typedef struct ElemType*bottom;ElemType*top;int stacksize;SqStack;其中，stacksize说明栈当前可用的最大容量。,栈的初始化操作如下：按设定的初始分配量进行第一次存储分配，bottom称为栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值为NULL，则表明栈结构不存在。在程序设计语言中，用一维数组S（1:m）作为栈的顺序存储空间，其中m为栈的最大容量。如图（a）所示是容量为10的栈顺序存储空间，栈中已经有6个元素；如图（b）和图（c）所示分别为入栈与出栈后的状态。,图9.3.2 顺序栈的插入与删除运算,在栈的顺序存储空间S（1:m）中，S（bottom）通常为栈底元素（是在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示栈满。在栈上进行操作，都比较容易实现，下面介绍顺序栈的建立、插入和删除的算法。（1）建立空栈。Init_StackSq(SqStack*S),2栈的链式存储结构链栈顺序栈最大的缺点是：必须设置最大容量，但是当栈的容量不固定时，这样可能会造成很多存储空间的浪费，也可能产生上溢。栈的链式存储结构克服了这个缺点，它采用一个链表结构来表示栈，栈顶指针就是链表的头指针，其插入和删除操作仅在表头进行，如图所示。,图9.3.3 链栈示意图,链栈节点类型的定义如下：typedef struct Snode ElemType data;/*数据域*/struct Snode*next;/*指针域*/Snode,*LinkStack;假设s是LinkStack型的变量，则s为链栈的头 指针。下面介绍链栈的插入和删除算法。,p=*S;/*使栈顶指针指向下一节点*/*S=pnext;free(p);/*释放栈顶元素*/return temp;9.3.3 栈的应用栈最初用于高级语言的编译程序中，如表达式求值、程序的嵌套以及递归调用等，后来在各类回溯求解问题中也得到应用。下面以过程嵌套的实例来说明栈的应用。,过程（函数）嵌套是程序设计中很重要的应用。当过程调用子过程（自定义函数）时，必须把断点的信息及地址保留起来，当子过程执行完毕返回时，取用这些信息，找到返回地址，由此断点继续执行。当程序中出现多重嵌套调用时，必须开辟一个栈，将各层断点信息依次入栈，当各层子过程返回时，又以相反的次序从栈顶取出。如图所示给出了具有嵌套调用关系的5个程序，其中主程序要调用子程序SUB1，SUB1要调用子程序SUB2，SUB2要调用子程序SUB3，SUB3要调用子程序SUB4，SUB4不再调用其他子程序。,图9.3.4 主程序与子程序之间的调用关系,下面来具体介绍计算机系统是如何处理它们之间的调用关系的。其中的关键是要正确处理好执行过程中的调用层次和返回路径，这就需要记忆每一次调用时的返回点。计算机系统用一个栈来动态记忆调用过程中的路径，其基本原则如下：（1）在开始执行程序前，先建立一个栈，其初始状态为空。（2）当发生调用时，将当前调用的返回点地址（在图中用语句标号表示）插入到栈。,（3）当遇到从某个子程序返回时，就从栈顶取出返回点地址。根据以上原则，图中5个程序在执行过程中的调用顺序以及栈中元素变化的情况如下：（1）主程序开始执行前，建立一个空栈，即栈的状态为（）。（2）开始执行主程序MAIN，当执行到CALL SUB1时，调用子程序SUB1，这时，将本次调用的返回点地址A入栈。此时，栈的状态为（A）。,（3）开始调用执行子程序SUB1，当执行CALL SUB2时，调用子程序SUB2，这时将本次调用的返回点地址B入栈。此时栈状态为（A，B）。（4）开始调用执行子程序SUB2，当执行到CALL SUB3时，调用子程序SUB3，这时将本次调用的返回点地址C入栈。此时栈状态为（A，B，C）。（5）开始调用执行子程序SUB3，当执行到CALL SUB4时，调用子程序SUB4，这时，将本次调用的返回点地址D入栈。此时栈的状态为（A，B，C，D）。,从上述逐步调用的过程可以看出，每次发生调用时，都需要将当前调用的返回点地址入栈，而这种插入操作不需要移动栈中原有元素，并且，各返回点地址在栈中的存放顺序恰好是调用顺序。（6）开始调用执行子程序SUB4，而SUB4不再调用其他子程序，因此执行完子程序后要返回到子程序SUB3的地址D处。其中返回点地址D从栈顶取出，这时，栈的状态为（A，B，C）。,（7）返回到子程序SUB3的D处继续执行，执行完子程序SUB3后要返回到子程序SUB2的地址C处。其中返回点地址C从栈顶取出，这时，栈的状态为（A，B）。（8）返回到子程序SUB2的C处继续执行，执行完子程序SUB2后要返回到子程序SUB1的地址B处。其中返回点地址B从栈顶取出，这时，栈的状态为（A）。,（9）返回到子程序SUB1的B处继续执行，执行完子程序SUB1后要返回到主程序MAIN的地址A处。其中返回点地址A从栈顶取出。取出A后，栈变为空，即栈的状态为（）。（10）返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完毕。由上述逐步返回的过程可以看出，当子程序返回到上一个调用程序时，需要从栈顶取出返回点地址，即对栈作出栈操作。由于各返回点地址在线性,表中的存放顺序恰好是对应的调用顺序，因此，每次从栈顶取出的返回点地址正好对应了各次调用的正确返回顺序。9.3.4 队列的定义及其运算1队列的定义队列（equeue）简称队，也是一种操作受限的线性表，它只允许在表的一端进行插入，而在表的另一端进行删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队首（front）。显然，在队列这种数据结构中，最先插入的元素将,最先被删除，反之，最后插入的元素将最后才被删除。所以，队列又称为“先进先出”（First In First Out，FIFO）或者“后进后出”（Last In Last Out，LILO）的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与队首指针front共同反映了队列中元素动态变化的情况。如图所示是具有5个元素的队列示意图。,图9.3.5 具有5个元素的队列示意图,向队列的尾部插入一个元素称为入队运算，从队列的头部删除一个元素称为出队运算。如图所示在队列中进行插入与删除的示意图。由图可看出，入队运算只涉及尾指针rear的变化，而出队运算只涉及头指针front的变化。,图9.3.6 队列的插入与删除运算,2队列的基本运算（1）建立空队列。（2）判定队列是否为空。（3）入队，在队尾插入元素。（4）