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

《C语言入门教程全第9章.ppt》由会员分享，可在线阅读，更多相关《C语言入门教程全第9章.ppt（282页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、9.1 数据结构与算法概述 9.1.1 数据结构的相关概念数据结构的相关概念实践证明，要想更有效地使用计算机，仅仅掌握计算机语言而缺乏数据结构和算法的有关知识，是难以处理诸多复杂应用问题的。早期的计算机主要解决纯数值计算的问题，以此为加工对象的程序设计称为数值型程序设计。其涉及的操作对象比较简单，其一般为整型、实型数据等。后来，随着计算机应用领域的不断拓宽，解决非数值计算的问题越来越引起人们的关注。例如，金融管理、文献检索、计算机辅助设计等。这些问题主要集中于对数据集合中的各元素以各种方式进行运算，如插入、更新、删除、查找等。在此涉及的数据类型比较复杂，而且数据元素之间具有各种特定的联系，所以

2、，如果了解了数据集合中元素之间的关系以及如何组织和表示这些数据，就能大大提高计算机处理问题的效率。数据结构是一门研究非数值运算的程序设计问题的学科，它包含以下3个方面的内容：（1）数据集合中各数据元素之间的逻辑结构。（2）对数据进行处理时，各数据元素在计算机中的存储（物理）结构。（3）对数据的抽象运算。1数据（data）数据是反映客观事物信息符号的集合，也是计算机程序要加工的对象。这个集合中包括客观事物的数值、字符以及能够输入到计算机中并被计算机程序处理的符号。计算机发展初期，由于计算机主要用于数值计算，数据指的就是数值。随后由于计算机应用的普及，数据的含义也比原来变得更加广泛。如文字、表格、

3、声音、图形、图像等都属于数据的范畴。2数据元素（data element）数据元素是数据集合中的客体（个体），是数据的基本单位，有时也称为节点或记录。例如数据集合N=1，2，3，4，5中整数15都是数据元素。每个数据元素的表现形式是由一个或多个数据项组成的。数据项是具有独立含义的最小标识单位，例如，在老师档案信息管理中的每一位老师就是一个数据元素，组成它的数据项可以是姓名、性别、年龄等。3数据对象（data object）数据对象是具有相同特性的数据元素的集合，是数据的一个子集。例如，一周中的7天就是一个数据对象，可表示为集合W=Mon，Tue，Wed，Thu，Fri，Sat，Sun；再如，字

4、母数据对象可表 示为集合C=A，B，Z。4数据类型（data type）数据类型是一个值的集合和定义在该值集上的一组操作的总称。程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系，它不仅规定了该变量可以设定的值的集合，还规定了该集合上的运算。各种语言规定了它所允许的数据类型。在C语言中，基本数据类型包括整型、实型等，这些变量的值是不可再分的；而构造类型包括数组、结构体等，这些变量的值是可以再分的，也可以说它们是带结构的数据，它们的成分可以是基本数据类型，也可以是构造数据类型等。5数据结构（data structure）数据结构指的是数据之间的相互关系，即数据的组织形式。可以用集合论的

5、方法定义数据结构如下：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所示。图9.1.1 数据的逻辑结构线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，除

6、第一个元素以外，其他元素有且仅有一个直接前驱；除最后一个元素外，其他元素都有且仅有一个直接后继。非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继。线性结构主要有线性表、栈和队列等，而非线性结构分为树型结构和图型结构等。（2）数据的物理结构。数据的物理结构又称存储结构，是数据及其关系在计算机中的存放形式，是逻辑结构在计算机存储器中的映像，也就是它的具体实现，通常用高级语言中各种数据类型来描述。在进行实际的数据处理时，被处理的数据都是存放在计算机的存储空间中，而且，各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的。因此，为了能表示出存放在计算机存储空间的各个节点之间的逻辑关系

7、，在数据的存储结构中，不但要存放各个节点的信息，还要存放各个节点之间逻辑关系的信息。下面介绍4种常见的存储结构：1）顺序存储结构。顺序存储结构主要用于线性的数据结构。它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中，各节点之间的逻辑关系由存储单元的邻接关系来体现。如图9.1.2所示为顺序存储结构，假设每个节点占据长度为l（字母，以下同）的存储空间，这个逻辑结构在物理存储器中以一定的顺序占用连续的存储空间。对于这种结构，只需要知道第一个元素的地址和每一个元素所占的存储单元数就可以得到任何一个元素所在的位置。在顺序存储结构中存取任意一个元素所需要的时间是相等的。图9.1.2 顺序存储结构

8、 2）链式存储结构。顺序存储结构比较适合于线性结构，而非线性结构一般很难用顺序存储结构来实现，所以，通常不用顺序存储结构，而是用链式存储结构来实现非线性结构。链式存储结构是给节点附加指针字段。在这种存储结构中，节点所占的存储单元分为两部分：一部分是用来存放节点自身的信息，称为数据域；另一部分是用来存放该节点后继节点的存储单元的地址，称为指针域。指针域中可以有一个或者多个指针，用来表示节点的一个或多个后继，也可以用来表示其他节点的地址。在用链式存储结构存储一个非线性结构时，节点中的指针个数可以根据该节点的直接后继个数来设置。如图9.1.3所示的链式存储结构，在Addr1的存储单元中，既包含了节点

9、a1本身的信息，又包含了它的后继节点a2的存储单元的地址Addr1+3l，其他节点与此类似。图9.1.3 链式存储结构 由此不难看出，链式存储结构可以存储线性结构，也可以存储非线性结构。在链式存储结构中，各个节点在存储空间中的前后位置关系与其逻辑顺序也可以不一致，其存储空间也可以不连续。3）索引存储结构。在线性结构中，所有节点可以排成一个序列，每个节点在该序列中都有对应的位置值，这个位置值就是节点的索引号。索引存储结构是用节点的索引号来确定节点的存储地址。可用以下两种方法实现索引存储：建立一个附加的索引表，索引表中第i项的值就是第i个节点的存储地址。如果每个节点所占单元数都相等，可用位置值的线

10、性函数的值来指出节点对应的存储地址，即第i个节点di的地址为LOC(di)=(i-1)l+d，其中l为节点所占单元数，d为开始节点d1对应的存储地址。4）散列存储结构。散列存储结构是指根据节点的关键字值来确定其存储地址，也称为哈希法。用这种方法进行存储时，每个节点分散地存储在存储单元中，其查找的效率是很高的，关键问题是怎样选择哈希函数和研究解决冲突的办法。上述4种存储结构也可以组合起来对数据进行存储映像。同一个逻辑结构可以有多种不同的存储方法，应根据具体情况进行选择。另外，存储结构只是数据结构的一个重要方面，如果逻辑结构相同但存储结构不同，也是不同的数据结构。例如，如果用顺序存储结构存储线性表

11、，则称为顺序表；如果用链式存储结构存储线性表，则称为链表。9.1.2 算法评价算法评价在第3章中读者已初步了解了算法的概念、特性等，在前面其他章节的编程举例中还学习了不少给定的算法。而解决同一个问题通常有许多不同的算法。算法评价的目的首先在于从解决同一个问题的不同算法中选择出较为合适的一种，其次在于知道怎样对现有算法进行改进，进而设计出更好的算法。对于算法的评价可以从以下几个方面进行。1正确性正确性（correctness）是设计和评价算法的首要条件，一个正确的算法是指在有合理的数据输入的情况下，能够在有限的运行时间内得出正确的结果。要从理论上证明一个算法的正确性，并不是一件容易的事，所以通常

12、可采用各种典型的输入数据上机调试算法，并使算法中的每段代码都被测试过，若发现错误及时修正，最终可以验证出算法的正确性。2健壮性健壮性（robustness）是指一个算法对不合理（又称不正确、非法、错误等）数据输入的反应和处理能力。一个好的算法应该能够识别出错误数据并进行相应的处理。对错误数据的处理一般包括打印出错误信息、调用错误处理程序、返回标识错误的特定信息、中止程序运行等。3可读性可读性（readability）是指一个算法供人们阅读和理解的容易程度。一个可读性好的算法，应该符合结构化和模块化程序设计的思想，应该对其中的每个功能模块、重要数据类型或语句加以必要注释；应该建立相应的文档，对整

13、个算法的功能、结构、使用及有关事项进行说明。4简单性简单性（simplicity）是指一个算法所采用数据结构和方法的简单程度。如对数组进行查找时，采用顺序查找的方法比采用二分查找的方法要简单；对数组进行排序时，采用简单选择排序的方法比采用堆排序或快速排序的方法要简单。但最简单的算法往往不是最有效的，即有可能占用较长的运行时间和较多的内存空间。算法的简单性便于用户编写、分析和调试，所以对于处理少量数据的情况是适用的，但若要处理大量的数据，则算法的有效性比简单性更重要。有效性主要表现为时间复杂度和空间复杂度。5时间复杂度时间复杂度（time complexity）是指计算机执行一个算法时在时间上的

14、消耗度量。度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算。通常人们采用第二种方法，所以这里只介绍事前分析估算方法。一般情况下，把算法中一条语句重复执行的次数称为此语句的频度，它常表示为问题规模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)下列程序段的时间复杂度如下

15、：（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;knext=p-next;p-next=s;在进行指针的修改时，必须要注意其修改的顺序，假如把上述两条语句顺序颠倒，那么执行结果就完全错误。在带头节点的单链表的第i个元素之后插入元素x的算法描述如下：ListInsert_L(LinkList*L,int i,ElemType x)（2）删除运算。单链表的删除运算与插入运算一样，在删除时，不需要移动元素，只须修改有关的指针内容。在单链表上进行删除运算时指针的变化如图9.2.7所示。上述指针修改可

16、描述如下：p-next=p-next-next;图9.2.7 单链表上删除节点时指针的变化情况在带头节点的单链表中删除第i个元素的算法描述如下：3其他形式的链表根据实际需要，线性表的链式存储结构还有循环链表和双向链表等其他形式。（1）循环链表。循环链表是线性表的另一种链式存储结构，它的特点是表中最后一个节点的指针域不为空，而是指向表头，整个链表形成一个环。如图9.2.8（a）、（b）所示分别表示具有头节点的非空循环链表和空循环链表。图9.2.8 循环链表循环链表与一般链表的不同之处在于只要给定循环链表中任一节点的地址，就可以遍历表中所有节点，而不必从头指针开始。这样有可能对某些运算带来方便。（

17、2）双向链表。前面讨论的链表都是单向链表，它们只能单方向地寻找表中的节点，若要寻找前驱节点，则需从表头指针出发查找或向后循环一周查找，当表长为n时执行时间为O(n)。为克服其单向性缺点，可采用双向链表。在双向链表的节点中有两个指针域，一个指向直接后继，一个指向直接前驱，如图9.2.9所示。图9.2.9 双向链表双向链表的节点类型定义如下：typedef struct Dlnode /*定义双向链表节点 类型*/ElemType data;struct DLnode*left;struct DLnode*right;DLnode,*DLinkList;此类型包含有3个域：数值域data、左指针域

18、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的序号内。

19、一元多项式的存储结构可以采用顺序存储结构，也可以用链式存储结构，这要取决于执行何种操作。如果只求多项式的值，无须修改多项式的系数和指数，则采用顺序存储结构为宜。但在进行多项式相加时，通常要改变多项式的系数和指数，而且在实际问题中，经常会出现多项式的次数很高但又存在大量的零系数项的情况，例如：S(x)=8+2x1050+3x2000这时如果采用顺序存储结构会浪费大量的存储空间，故一般采用链式存储结构。用链式存储结构表示多项式是把每一个非零系数项构成链表中的一个节点，节点是由两个数据域和一个指针域构成，如图9.2.10（a）所示。其中，exp(i)表示该项的指数，称为指数域；coef(i)表示该项

20、的系数，称为系数域；next(i)是指向下一个非零系数的节点，称为指针域。整个多项式Pn(x)如图 9.2.10（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指针所指节

21、点插入到C(x)链表中去。（3）指针qa所指节点的指数值=指针qb所指向节点的指数值，则把两个节点中的系数相加，若和数不为0，则修改qa所指节点的系数值，同时释放 qb所指向节点；反之，从多项式A的链表中删除相应节点，并释放指针qa和qb所指节点。如图9.2.11（a）所示，为带头节点的单链表表示的多项式A5(x)=8-2x+15x5，B8(x)=2x+7x4-9x5+3x8；如图9.2.11（b）所示表示相加后的“和多项式”C(x)。图9.2.11 用链式存储结构进行多项式求和9.3 栈和队列 9.3.1 栈的定义及其运算栈的定义及其运算1栈的定义栈（stack）又称堆栈，它实际上是一种操作

22、受限的特殊的线性表，是限定仅在表的一端进行插入和删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，自然也是最先被删除的元素；栈底元素总是最先被插入的元素，自然也是最后才被被删除的元素。也是说栈是按照“先进后出”（First In Last Out，FILO）或者“后进先出”（Last In First Out，LIFO）的原则组织数据的，所以，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆功能。通常用指针top指示栈顶的位置，用指针bottom指向栈底。向栈中插入一个元素（即插入为新的栈顶元素）称为入栈运算，从

23、栈中删除一个元素（即删除栈顶元素）称为出栈运算。栈顶指针top动态反图9.3.1 栈的示意图映了栈中元素的变化情况。如图9.3.1所示为栈的示意图。栈这种结构在日常生活中是很常见的。例如子弹夹就是一种栈的例子，最先压入的子弹总是最后一个被弹出，而最后压入的子弹最先被弹出，这就遵循了“后进先出”或“先进后出”的原则。2栈的基本运算（1）建立一个空栈。（2）判断空栈。（3）读栈顶元素。（4）求栈的长度，返回栈的数据元素个数。（5）入栈，将元素插入到栈顶。（6）出栈，删除栈顶元素。9.3.2 栈的存储结构栈的存储结构1栈的顺序存储结构顺序栈实现栈的顺序存储结构最简单的方法是用一维数组来存储。由于栈底

24、不变，而栈顶是随入栈、出栈操作动态变化的，因此必须记住栈顶的位置，并且由于栈是有容量限制的，因此用C语言定义顺序栈的结构如下：#define Stack_NUM 100#define Stack_MORENUM 10typedef struct ElemType*bottom;ElemType*top;int stacksize;SqStack;其中，stacksize说明栈当前可用的最大容量。栈的初始化操作如下：按设定的初始分配量进行第一次存储分配，bottom称为栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值为NULL，则表明栈结构不存在。在程序设计语言中，用一维数组S（

25、1:m）作为栈的顺序存储空间，其中m为栈的最大容量。如图9.3.2（a）所示是容量为10的栈顺序存储空间，栈中已经有6个元素；如图9.3.2（b）和图9.3.2（c）所示分别为入栈与出栈后的状态。图9.3.2 顺序栈的插入与删除运算 在栈的顺序存储空间S（1:m）中，S（bottom）通常为栈底元素（是在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示栈满。在栈上进行操作，都比较容易实现，下面介绍顺序栈的建立、插入和删除的算法。（1）建立空栈。Init_StackSq(SqStack*S)2栈的链式存储结构链栈顺序栈最大的缺点是：必须设置最大容量，但是当栈的容量不固

26、定时，这样可能会造成很多存储空间的浪费，也可能产生上溢。栈的链式存储结构克服了这个缺点，它采用一个链表结构来表示栈，栈顶指针就是链表的头指针，其插入和删除操作仅在表头进行，如图9.3.3所示。图9.3.3 链栈示意图链栈节点类型的定义如下：typedef struct Snode ElemType data;/*数据域*/struct Snode*next;/*指针域*/Snode,*LinkStack;假设s是LinkStack型的变量，则s为链栈的头 指针。下面介绍链栈的插入和删除算法。p=*S;/*使栈顶指针指向下一节点*/*S=pnext;free(p);/*释放栈顶元素*/retur

27、n temp;9.3.3 栈的应用栈的应用栈最初用于高级语言的编译程序中，如表达式求值、程序的嵌套以及递归调用等，后来在各类回溯求解问题中也得到应用。下面以过程嵌套的实例来说明栈的应用。过程（函数）嵌套是程序设计中很重要的应用。当过程调用子过程（自定义函数）时，必须把断点的信息及地址保留起来，当子过程执行完毕返回时，取用这些信息，找到返回地址，由此断点继续执行。当程序中出现多重嵌套调用时，必须开辟一个栈，将各层断点信息依次入栈，当各层子过程返回时，又以相反的次序从栈顶取出。如图9.3.4所示给出了具有嵌套调用关系的5个程序，其中主程序要调用子程序SUB1，SUB1要调用子程序SUB2，SUB2

28、要调用子程序SUB3，SUB3要调用子程序SUB4，SUB4不再调用其他子程序。图9.3.4 主程序与子程序之间的调用关系下面来具体介绍计算机系统是如何处理它们之间的调用关系的。其中的关键是要正确处理好执行过程中的调用层次和返回路径，这就需要记忆每一次调用时的返回点。计算机系统用一个栈来动态记忆调用过程中的路径，其基本原则如下：（1）在开始执行程序前，先建立一个栈，其初始状态为空。（2）当发生调用时，将当前调用的返回点地址（在图9.3.4中用语句标号表示）插入到栈。（3）当遇到从某个子程序返回时，就从栈顶取出返回点地址。根据以上原则，图9.3.4中5个程序在执行过程中的调用顺序以及栈中元素变化

29、的情况如下：（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，这时，将本次调用的返回

30、点地址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处继续执行，执行完子程序

31、SUB2后要返回到子程序SUB1的地址B处。其中返回点地址B从栈顶取出，这时，栈的状态为（A）。（9）返回到子程序SUB1的B处继续执行，执行完子程序SUB1后要返回到主程序MAIN的地址A处。其中返回点地址A从栈顶取出。取出A后，栈变为空，即栈的状态为（）。（10）返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完毕。由上述逐步返回的过程可以看出，当子程序返回到上一个调用程序时，需要从栈顶取出返回点地址，即对栈作出栈操作。由于各返回点地址在线性表中的存放顺序恰好是对应的调用顺序，因此，每次从栈顶取出的返回点地址正好对应了各次调用的正确返回顺序。9.3.4 队列的定义及其运算队列的定

32、义及其运算1队列的定义队列（equeue）简称队，也是一种操作受限的线性表，它只允许在表的一端进行插入，而在表的另一端进行删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队首（front）。显然，在队列这种数据结构中，最先插入的元素将最先被删除，反之，最后插入的元素将最后才被删除。所以，队列又称为“先进先出”（First In First Out，FIFO）或者“后进后出”（Last In Last Out，LILO）的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与队首指针front共同反映了队列中元素动态变化的情况。如图9.3.5所示是具有5个元素的队

33、列示意图。图9.3.5 具有5个元素的队列示意图向队列的尾部插入一个元素称为入队运算，从队列的头部删除一个元素称为出队运算。如图9.3.6所示在队列中进行插入与删除的示意图。由图9.3.6可看出，入队运算只涉及尾指针rear的变化，而出队运算只涉及头指针front的变化。图9.3.6 队列的插入与删除运算 2队列的基本运算（1）建立空队列。（2）判定队列是否为空。（3）入队，在队尾插入元素。（4）出队，删除队首元素。（5）返回队首元素。9.3.5 队列的存储结构队列的存储结构线性表的存储结构同样适用于队列，也可根据不同的应用场合分别采用顺序存储结构和链式存储结构。1队列的顺序存储结构顺序队列在

34、程序设计语言中，一般要用一维数组作为队列的顺序存储空间，同时尚需附设两个指针front和 rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便，我们约定：用队尾指针rear指向队列中的队尾元素，用队首指针front指向头元素的前一个位置。每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。若对存储队列的数组空间采用动态分配，则顺序队列的结构类型可定义如下：typedef struct ElemType*base;/*初始化的动态分配存储空间*/int front;/*头指针，若队列不空，则指向队列头元素*/int rear;/*尾指针，若队列不空，则

35、指向队列尾元素的下一位置*/SqQueue;假设为某队列分配的最大空间为n，则当队尾指针指向数组空间的最后一个位置时，不能再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破坏。然而此时又不适合进行存储再分配扩大数组空间，因为队列的实际可用空间可能并未占满。一个巧妙的方法是采用循环队列。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图9.3.7所示。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列的初始状态为空

36、，即rear=front=0，如图9.3.7所示。图9.3.7 循环队列存储空间示意图在循环队列中，每进行一次入队的运算，队尾指针就加1，当队尾指针rear=m+1时，置rear=0；每进行一次出队运算，队首指针就加1，当队首指针front=m+1时，置front=0。下面介绍顺序队列的建立、插入和删除算法。（1）建立空队列。Init_Queue(SqQueue*Q)2队列的链式存储结构链队列如果应用程序中使用顺序队列，则必须为它设定一个最大的队列长度，但这样往往会造成存储空间的浪费；当无法预先估计所用队列的最大长度时，则宜采用链式存储结构，即链队列，如图9.3.8所示。链队列的操作即为单链表

37、的插入和删除操作的特殊情况，只是同时需要修改尾指针或头指针，如图9.3.9所示为进行这两种操作时指针变化的情况。图9.3.8 链队列示意图图9.3.9 链队列操作指针变化情况 假定链队列的节点类型类似于前面定义的单链表节点类型，定义如下：9.3.6 队列的应用队列的应用这里从两个方面简述队列在计算机科学领域中的应用：一是解决主机与外部设备之间速度不匹配的问题，二是解决由多用户引起的资源竞争问题。对于第一个方面，这里以主机和打印机之间速度不匹配的问题为例进行简要说明。主机输出数据给打印机，输出数据的速度比打印数据的速度要快得多，若直接把输出的数据送给打印机打印，则由于速度不匹配，显然是不行的。所

38、以解决的方法是设置一个打印数据缓冲区，主机把需要打印的数据依次写入到这个缓冲区中，写满后就暂停写入，转去做其他的事情；打印机就从缓冲区中按照先进先出的队列操作原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样做既保证了打印数据的正确性，又提高了主机的效率。由此可见，在打印数据缓冲区中所存储的数据就是一个队列。对于第二个方面，CPU资源的竞争也是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU运行自己的程序，它们分别通过各自终端向操作系统提出占用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU

39、分配给队首请求的用户使用，当相应的程序运行结束或用完规定的时间间隔后，则令其出队，再把CPU分配给新的队首请求的用户使用，这样既满足了每个用户的请求，又使CPU能够正常运行。9.4 树和二叉树 树型结构是一种重要的非线性结构，它与线性结构的最大区别在于：在这种结构中，除去根节点外每个节点最多只能和上层的一个节点相关，除叶子节点外每个节点都可以和下层的多个节点相关，节点间存在着明显的分支和层次关系。树型结构在客观世界中广泛存在，例如家族关系中的家谱、各种社会组织机构等，都可以形象地用树型结构表示；在计算机软件技术中，树型结构也得到广泛的应用，例如操作系统中的目录（树型）结构、高级语言中源程序的语

40、法结构等。本节主要讨论树和二叉树的定义及其存储结构。9.4.1 树的定义及其存储结构树的定义及其存储结构1树的定义和术语树（tree）是由n个（n0）节点组成的有限集合T，其中有且仅有一个节点称为根节点（root），其余节点可分为m（m0）个互不相交的有限集合T1，T2，Tm，其中每个集合Ti本身又是一棵树，称为根节点root的子树。当n=0时称为空树。这是一个递归的描述，即在描述树时又用到树本身这个术语。如图9.4.1所示为一棵树，A为根节点，其余节点分为3个不相交的子集T1=B,E,F,K,L，T2=C,G，T3=D,H,I,J,M，它们均为根节点 A下的3棵子树，而这3棵子树本身也是树。

41、图9.4.1 树树型结构中常用的术语有：（1）节点（node）：表示树中的元素。（2）节点的度（degree）：节点拥有的子树数，如图9.4.1中节点D的度为3，C的度为1。一棵 树中最大的节点度数为这棵树的度，如图9.4.1所示的树的度为3。（3）叶子（leaf）：度为零节点，又称端节点。（4）孩子（child）：除根节点外，每个节点都是其前驱节点的孩子。（5）双亲（parents）：对应上述孩子节点的上层节点称为这些节点的双亲。（6）兄弟（sibling）：同一双亲的孩子。（7）节点的层次（level）：从根节点开始算起，根为第一层，根的直接后继节点为第二层，其余各层以此类推。例如图9.4

42、.1中的节点K，L和M都在第4层。（8）深度（depth）：树中节点的最大层次数。如图9.4.1中树的深度为4。（9）森林（forest）：是m（m0）棵互不相交的树的集合。（10）有序树、无序树：树中节点在同层中按从左至右有序排列、不能互换的称为有序树，并把各子树分别称为第一子树，第二子树反之称为无序树。2树的存储结构树的存储结构根据应用可以有多种形式，如常见的顺序存储和链式存储结构等，但由于树是非线性结构，因此常采用链式存储结构来表示树，在这里我们只介绍链式存储结构。因为树是多分支非线性表，所以需要采用多重链表结构，即每个节点设有多个指针域，其中每一个指针指向一棵子树的根节点。对于每一个节

43、点的结构类型可以有两种形式：一种是节点异构型，它根据每个节点的子树数设置相应的指针域，由于树中每个节点的度数不尽相同，因此一棵树中各节点的结构形式也不同。这种结构形式虽能节省存储空间，但不方便运算；另一种是采用同构型，即每个节点的指针域个数均为树的度数，这种形式运算方便，但会使链表中出现很多空链域，浪费空间，如图9.4.2所示。假设有一棵具有n个节点的k叉树，则有nk个指针域，其中有用的指针域为n1个，这时的空链域个数为nk(n1)=n(k1)+1个。图9.4.2 树的链式存储结构由此可见，k越大则空链域所占比例也越高，其中k=2时空链域的比例最低，这就是我们下面要着重讨论的二叉树结构。9.4

44、.2 二叉树二叉树1二叉树的定义二叉树（binary tree）是n（n0）个节点的有限集合，它或为空树（n=0），或由一个根节点和两棵互不相交的分别称为这个根的左子树和右子树的二叉树构成。可以看出，和树的定义一样，二叉树也是递归定义的。应该引起注意的是，二叉树的节点的子树有明确的左、右之分。2几种特殊形式的二叉树（1）满二叉树。深度为h且含有2h1个节点的二叉树称为满二叉树。如图9.4.3所示为一棵深度为4的满二叉树，其节点的编号为自上至下，自左至右，共有241=15个节点。图9.4.3 满二叉树 （2）完全二叉树。如果一棵有n个节点的二叉树，按与满二叉树相同的编号方式对节点进行编号，若树中

45、n个节点和满二叉树1n编号完全一致，则称该树为完全二叉树，如图9.4.4（a）所示。如图9.4.4（b）所示的就不是完全二叉树。图9.4.4 完全二叉树与非完全二叉树 完全二叉树具有以下特点：1）叶子节点只在层次最大的两层出现。2）其中任一节点，如果其左子树深度为k，则其右子树的深度为k或k1。（3）平衡二叉树。平衡二叉树又称AVL树，它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，而且左子树和右子树的深度之差的绝对值不超过1。节点的左子树深度减去它的右子树深度定义为节点的平衡因子，所以，平衡二叉树上所有节点的平衡因子只可能是1，0和1。只要二叉树上有一个节点的

46、平衡因子绝对值大于1，则该二叉树就是不平衡的。如图9.4.5（a）所示为平衡二叉树，如图9.4.5（b）所示为不平衡二叉树。图9.4.5 平衡二叉树与不平衡二叉树 3二叉树的基本性质性质1：二叉树的第i层上至多有2i-1（i1）个节点。可用数学归纳法予以证明。性质2：深度为h的二叉树中至多含有2h1个节点。利用性质1的结论可推导得出。性质3：在任意二叉树中，若有n0个叶子节点，n2个度为2的节点，则必有n0=n2+1。性质4：具有n个节点的完全二叉树的深度为log2n+1或log2(n+1)。性质5：如果对一棵有n个节点的完全二叉树（深度为log2n+1）的节点编号，从根节点开始，自上而下，自

47、左而右，则对任一节点i(1in)有（1）如果i=l，则节点i是二叉树的根，无双亲；如果i1，则其双亲是节点i/2。（2）如果2in，则节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i。（3）如果2i+1n，则节点i无右孩子；否则其右孩子是节点2i+1。【注意】符号x表示不大于x的最大整数，反之，x表示不小于x的最小整数。4二叉树的存储结构二叉树的存储结构有顺序存储结构和链式存储结构两种。（1）顺序存储结构。顺序存储结构是将二叉树的所有节点，按照一定的顺序方式，存储到一段连续的存储单元中。节点的顺序反映出节点之间的逻辑关系。对于满二叉树或完全二叉树，可用顺序存储结构将n个节点按自上而下

48、、自左至右的顺序依次存放在一段地址连续的存储单元中，即按层存放。如用C语言定义一个完全二叉树为anytype bn;为处理方便，我们定义数组长度为n+1，不用 b0，只用b1bn。一般的二叉树虽然也可以按完全二叉树的形式来存储，但会造成存储空间的浪费。（2）链式存储结构。二叉树通常都采用链式存储。在这种存储方式下，二叉树的每个节点由数据域（data）、左指针域（Lchild）和右指针域（Rchild）组成，即链式存储不要求各个节点的存储空间连续，二叉树的这种存储结构也称为二叉链表，如图9.4.6（a）所示二叉树的二叉链表如图9.4.6（b）所示。图9.4.6 二叉树二叉链表节点描述如下：typ

49、edef int datatype;typedef struct node datatype data;struct node*lchild,*rchild;BTnode;BTnode*root;其中，root是指向根节点的头指针，当二叉树为空时，rootNULL。当节点某个孩子不存在时，相应的指针为空。5一般树转换为二叉树为了使一般树也能像二叉树一样用二叉链表表示，必须找出树与二叉树间的对应关系。这样当给定一棵树时，可找到唯一的一棵二叉树与之对应，而且这种关系的逆变换也是存在的。在这里只介绍变换的方法，对于变换过程的唯一性不作证明。将一般树转换为二叉树的步骤如下：（1）在兄弟节点之间加一连线

50、。（2）对每个节点，除了保留与其左孩子的连线外，去除与其他孩子间的连线。（3）以树根为轴心，将整棵树顺时针旋转45。如图9.4.7（a），（b），（c）所示为一般树转换为二叉树的过程。图9.4.7 一般树转换为二叉树由转换结果可以看出，任何一棵树转换成二叉树，其右子树必为空。9.4.3 二叉树的遍历二叉树的遍历遍历（traversing）是指按照某条搜索路线，依次访问某数据结构中的全部节点，而且每个节点只被访问一次。对于线性结构来说，遍历很容易实现，只需顺序访问每个节点即可；但是对于非线性结构来说，则要人为设定搜索的路径，路径即连接两个节点的边的集合。遍历是二叉树中最重要的运算。按照搜索路径的