《C语言入门教程全第9九章数据结构与算法基础【高等教学】》由会员分享，可在线阅读，更多相关《C语言入门教程全第9九章数据结构与算法基础【高等教学】（283页珍藏版）》请在金锄头文库上搜索。
1、第第9章章 数据结构与算法基础数据结构与算法基础 9.1 数据结构与算法概述数据结构与算法概述 9.2 线性表线性表9.3 栈和队列栈和队列 9.4 树和二叉树树和二叉树 9.5 图图9.6 排排 序序9.7 查查 找找本章小结本章小结习题九习题九 9.1 数据结构与算法概述 9.1.1 数据结构的相关概念数据结构的相关概念实践证明，要想更有效地使用计算机，仅仅掌握计算机语言而缺乏数据结构和算法的有关知识，是难以处理诸多复杂应用问题的。早期的计算机主要解决纯数值计算的问题，以此为加工对象的程序设计称为数值型程序设计。其涉及的操作对象比较简单，其一般为整型、实型数据等。后来，随着计算机应用领域的
2、不断拓宽，解决非数值计算的问题越来越引起人们的关注。例如，金融管理、文献检索、计算机辅助设计等。这些问题主要集中于对数据集合中的各元素以各种方式进行运算，如插入、更新、删除、查找等。在此涉及的数据类型比较复杂，而且数据元素之间具有各种特定的联系，所以，如果了解了数据集合中元素之间的关系以及如何组织和表示这些数据，就能大大提高计算机处理问题的效率。数据结构是一门研究非数值运算的程序设计问题的学科，它包含以下3个方面的内容：（1）数据集合中各数据元素之间的逻辑结构。（2）对数据进行处理时，各数据元素在计算机中的存储（物理）结构。（3）对数据的抽象运算。1数据（data）数据是反映客观事物信息符号的
3、集合，也是计算机程序要加工的对象。这个集合中包括客观事物的数值、字符以及能够输入到计算机中并被计算机程序处理的符号。计算机发展初期，由于计算机主要用于数值计算，数据指的就是数值。随后由于计算机应用的普及，数据的含义也比原来变得更加广泛。如文字、表格、声音、图形、图像等都属于数据的范畴。2数据元素（data element）数据元素是数据集合中的客体（个体），是数据的基本单位，有时也称为节点或记录。例如数据集合N=1，2，3，4，5中整数15都是数据元素。每个数据元素的表现形式是由一个或多个数据项组成的。数据项是具有独立含义的最小标识单位，例如，在老师档案信息管理中的每一位老师就是一个数据元素，
4、组成它的数据项可以是姓名、性别、年龄等。3数据对象（data object）数据对象是具有相同特性的数据元素的集合，是数据的一个子集。例如，一周中的7天就是一个数据对象，可表示为集合W=Mon，Tue，Wed， Thu，Fri，Sat，Sun；再如，字母数据对象可表 示为集合C=A， B ，Z。4数据类型（data type）数据类型是一个值的集合和定义在该值集上的一组操作的总称。程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系，它不仅规定了该变量可以设定的值的集合，还规定了该集合上的运算。各种语言规定了它所允许的数据类型。在C语言中，基本数据类型包括整型、实型等，这些变量的值是不
5、可再分的；而构造类型包括数组、结构体等，这些变量的值是可以再分的，也可以说它们是带结构的数据，它们的成分可以是基本数据类型，也可以是构造数据类型等。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）数据的逻辑结构。数据的逻辑结
6、构就是数据元素间的逻辑关系，它研究的是数据元素及其关系的数学特性，与数据的存储无关，是独立于计算机的。数据的逻辑结构可概括地分为线性结构和非线性结构两种，如图9.1.1所示。图9.1.1 数据的逻辑结构线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，除第一个元素以外，其他元素有且仅有一个直接前驱；除最后一个元素外，其他元素都有且仅有一个直接后继。非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继。线性结构主要有线性表、栈和队列等，而非线性结构分为树型结构和图型结构等。 （2）数据的物理结构。数据的物理结构又称存储结构，是数据及其关系在计算机中的存放形式，是逻辑结构在计算机存储器
7、中的映像，也就是它的具体实现，通常用高级语言中各种数据类型来描述。在进行实际的数据处理时，被处理的数据都是存放在计算机的存储空间中，而且，各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的。因此，为了能表示出存放在计算机存储空间的各个节点之间的逻辑关系，在数据的存储结构中，不但要存放各个节点的信息，还要存放各个节点之间逻辑关系的信息。下面介绍4种常见的存储结构：1）顺序存储结构。顺序存储结构主要用于线性的数据结构。它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中，各节点之间的逻辑关系由存储单元的邻接关系来体现。如图9.1.2所示为顺序存储结构，假设每个节点占据长度为l（字母
8、，以下同）的存储空间，这个逻辑结构在物理存储器中以一定的顺序占用连续的存储空间。对于这种结构，只需要知道第一个元素的地址和每一个元素所占的存储单元数就可以得到任何一个元素所在的位置。在顺序存储结构中存取任意一个元素所需要的时间是相等的。图9.1.2 顺序存储结构 2）链式存储结构。顺序存储结构比较适合于线性结构，而非线性结构一般很难用顺序存储结构来实现，所以，通常不用顺序存储结构，而是用链式存储结构来实现非线性结构。链式存储结构是给节点附加指针字段。在这种存储结构中，节点所占的存储单元分为两部分：一部分是用来存放节点自身的信息，称为数据域；另一部分是用来存放该节点后继节点的存储单元的地址，称为
9、指针域。指针域中可以有一个或者多个指针，用来表示节点的一个或多个后继，也可以用来表示其他节点的地址。在用链式存储结构存储一个非线性结构时，节点中的指针个数可以根据该节点的直接后继个数来设置。如图9.1.3所示的链式存储结构，在Addr1的存储单元中，既包含了节点a1本身的信息，又包含了它的后继节点a2的存储单元的地址Addr1+3l，其他节点与此类似。图9.1.3 链式存储结构 由此不难看出，链式存储结构可以存储线性结构，也可以存储非线性结构。在链式存储结构中，各个节点在存储空间中的前后位置关系与其逻辑顺序也可以不一致，其存储空间也可以不连续。3）索引存储结构。在线性结构中，所有节点可以排成一
10、个序列，每个节点在该序列中都有对应的位置值，这个位置值就是节点的索引号。索引存储结构是用节点的索引号来确定节点的存储地址。可用以下两种方法实现索引存储： 建立一个附加的索引表，索引表中第i项的值就是第i个节点的存储地址。 如果每个节点所占单元数都相等，可用位置值的线性函数的值来指出节点对应的存储地址，即第i个节点di的地址为LOC(di)=(i-1)l+d，其中l为节点所占单元数，d为开始节点d1对应的存储地址。4）散列存储结构。散列存储结构是指根据节点的关键字值来确定其存储地址，也称为哈希法。用这种方法进行存储时，每个节点分散地存储在存储单元中，其查找的效率是很高的，关键问题是怎样选择哈希函
11、数和研究解决冲突的办法。 上述4种存储结构也可以组合起来对数据进行存储映像。同一个逻辑结构可以有多种不同的存储方法，应根据具体情况进行选择。另外，存储结构只是数据结构的一个重要方面，如果逻辑结构相同但存储结构不同，也是不同的数据结构。例如，如果用顺序存储结构存储线性表，则称为顺序表；如果用链式存储结构存储线性表，则称为链表。9.1.2 算法评价算法评价在第3章中读者已初步了解了算法的概念、特性等，在前面其他章节的编程举例中还学习了不少给定的算法。而解决同一个问题通常有许多不同的算法。算法评价的目的首先在于从解决同一个问题的不同算法中选择出较为合适的一种，其次在于知道怎样对现有算法进行改进，进而
12、设计出更好的算法。对于算法的评价可以从以下几个方面进行。 1正确性正确性（correctness）是设计和评价算法的首要条件，一个正确的算法是指在有合理的数据输入的情况下，能够在有限的运行时间内得出正确的结果。要从理论上证明一个算法的正确性，并不是一件容易的事，所以通常可采用各种典型的输入数据上机调试算法，并使算法中的每段代码都被测试过，若发现错误及时修正，最终可以验证出算法的正确性。 2健壮性健壮性（robustness）是指一个算法对不合理（又称不正确、非法、错误等）数据输入的反应和处理能力。一个好的算法应该能够识别出错误数据并进行相应的处理。对错误数据的处理一般包括打印出错误信息、调用错
13、误处理程序、返回标识错误的特定信息、中止程序运行等。 3可读性可读性（readability）是指一个算法供人们阅读和理解的容易程度。一个可读性好的算法，应该符合结构化和模块化程序设计的思想，应该对其中的每个功能模块、重要数据类型或语句加以必要注释；应该建立相应的文档，对整个算法的功能、结构、使用及有关事项进行说明。4简单性简单性（simplicity）是指一个算法所采用数据结构和方法的简单程度。如对数组进行查找时，采用顺序查找的方法比采用二分查找的方法要简单；对数组进行排序时，采用简单选择排序的方法比采用堆排序或快速排序的方法要简单。但最简单的算法往往不是最有效的，即有可能占用较长的运行时间
14、和较多的内存空间。算法的简单性便于用户编写、分析和调试，所以对于处理少量数据的情况是适用的，但若要处理大量的数据，则算法的有效性比简单性更重要。有效性主要表现为时间复杂度和空间复杂度。 5时间复杂度时间复杂度（time complexity）是指计算机执行一个算法时在时间上的消耗度量。度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算。通常人们采用第二种方法，所以这里只介绍事前分析估算方法。一般情况下，把算法中一条语句重复执行的次数称为此语句的频度，它常表示为问题规模n的某个函数，记作F(n)。而算法的时间复杂度则记作T(n)=O(F(n)下面举例说明如何求时间复杂度：for(i=0
15、;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;knext=p-next;p-next=s;在进行指针的修改时，必须要注意其修改的顺序，假如把上述两条语句顺序颠倒，那么执行结果就完全错误。在带头节点的
16、单链表的第i个元素之后插入元素x的算法描述如下：ListInsert_L(LinkList *L,int i,ElemType x) （2）删除运算。单链表的删除运算与插入运算一样，在删除时，不需要移动元素，只须修改有关的指针内容。在单链表上进行删除运算时指针的变化如图9.2.7所示。上述指针修改可描述如下：p-next=p-next-next;图9.2.7 单链表上删除节点时指针的变化情况在带头节点的单链表中删除第i个元素的算法描述如下： 3其他形式的链表根据实际需要，线性表的链式存储结构还有循环链表和双向链表等其他形式。（1）循环链表。循环链表是线性表的另一种链式存储结构，它的特点是表中最
17、后一个节点的指针域不为空，而是指向表头，整个链表形成一个环。如图9.2.8（a）、（b）所示分别表示具有头节点的非空循环链表和空循环链表。图9.2.8 循环链表循环链表与一般链表的不同之处在于只要给定循环链表中任一节点的地址，就可以遍历表中所有节点，而不必从头指针开始。这样有可能对某些运算带来方便。（2）双向链表。前面讨论的链表都是单向链表，它们只能单方向地寻找表中的节点，若要寻找前驱节点，则需从表头指针出发查找或向后循环一周查找，当表长为n时执行时间为O(n)。为克服其单向性缺点，可采用双向链表。在双向链表的节点中有两个指针域，一个指向直接后继，一个指向直接前驱，如图9.2.9所示。图9.2
18、.9 双向链表双向链表的节点类型定义如下：typedef struct Dlnode /*定义双向链表节点 类型*/ ElemType data; struct DLnode *left; struct DLnode *right;DLnode,*DLinkList;此类型包含有3个域：数值域data、左指针域left和右指针域right。left域用于指向其前驱节点，right域用于指向其后继节点。由于双向链表具有对称性，因此从表中某一给定的节点可随意向前或向后查找。但在执行插入、删除运算时，需同时修改两个方向上的指针。9.2.4 线性表的应用线性表的应用一元多项式相加是线性表的一个典型应用
19、实例。多项式的操作是表处理中经常出现的操作，我们以一元多项式相加为例，说明线性链表在实际中的应用。一个一元多项式Pn(x)可以表示为Pn(x)= P0+P1x+P2x2+pnxn该多项式按升幂排列，并由n+1个系数唯一确定，因此可以用一个线性表P表示为P=(p0，p1，p2，pn)其指数i隐含在系数pi的序号内。一元多项式的存储结构可以采用顺序存储结构，也可以用链式存储结构，这要取决于执行何种操作。如果只求多项式的值，无须修改多项式的系数和指数，则采用顺序存储结构为宜。但在进行多项式相加时，通常要改变多项式的系数和指数，而且在实际问题中，经常会出现多项式的次数很高但又存在大量的零系数项的情况，
20、例如： S(x)=8+2x1050+3x2000这时如果采用顺序存储结构会浪费大量的存储空间，故一般采用链式存储结构。用链式存储结构表示多项式是把每一个非零系数项构成链表中的一个节点，节点是由两个数据域和一个指针域构成，如图9.2.10（a）所示。其中，exp(i)表示该项的指数，称为指数域；coef(i)表示该项的系数，称为系数域；next(i)是指向下一个非零系数的节点，称为指针域。整个多项式Pn(x)如图 9.2.10（b）所示。图9.2.10 一元多项式的链式存储结构设有一元多项式A(x)和B(x)，现要求其相加结果C(x)=A(x)+B(x)。其运算规则为：将两个多项式中指数相同的项
21、对应系数相加，若和不为零，则构成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所指节点。如图9.2.11（a）所示，为带头节
22、点的单链表表示的多项式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）又称堆栈，它实际上是一种操作受限的特殊的线性表，是限定仅在表的一端进行插入和删除的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，自然也是最先被删除的元素；栈底元素总是最先被插入的元素，自然也是最后才被被删除的元素。也是说栈是按照“先进后出”（Fir
23、st In Last Out，FILO）或者“后进先出”（Last In First Out，LIFO）的原则组织数据的，所以，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆功能。通常用指针top指示栈顶的位置，用指针bottom指向栈底。向栈中插入一个元素（即插入为新的栈顶元素）称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算。栈顶指针top动态反图9.3.1 栈的示意图映了栈中元素的变化情况。如图9.3.1所示为栈的示意图。栈这种结构在日常生活中是很常见的。例如子弹夹就是一种栈的例子，最先压入的子弹总是最后一个被弹出，而最后压入的子弹最先被弹出，这就遵循了
24、“后进先出”或“先进后出”的原则。2栈的基本运算（1）建立一个空栈。（2）判断空栈。（3）读栈顶元素。 （4）求栈的长度，返回栈的数据元素个数。（5）入栈，将元素插入到栈顶。（6）出栈，删除栈顶元素。9.3.2 栈的存储结构栈的存储结构1栈的顺序存储结构顺序栈实现栈的顺序存储结构最简单的方法是用一维数组来存储。由于栈底不变，而栈顶是随入栈、出栈操作动态变化的，因此必须记住栈顶的位置，并且由于栈是有容量限制的，因此用C语言定义顺序栈的结构如下： #define Stack_NUM 100#define Stack_MORENUM 10typedef struct ElemType *bottom
25、; ElemType *top; int stacksize;SqStack;其中，stacksize说明栈当前可用的最大容量。栈的初始化操作如下：按设定的初始分配量进行第一次存储分配，bottom称为栈底指针，在顺序栈中，它始终指向栈底的位置，如果bottom的值为NULL，则表明栈结构不存在。在程序设计语言中，用一维数组S（1:m）作为栈的顺序存储空间，其中m为栈的最大容量。如图9.3.2（a）所示是容量为10的栈顺序存储空间，栈中已经有6个元素；如图9.3.2（b）和图9.3.2（c）所示分别为入栈与出栈后的状态。图9.3.2 顺序栈的插入与删除运算 在栈的顺序存储空间S（1:m）中，S
26、（bottom）通常为栈底元素（是在栈非空的情况下），S（top）为栈顶元素。top=0表示栈空，top=m表示栈满。在栈上进行操作，都比较容易实现，下面介绍顺序栈的建立、插入和删除的算法。（1）建立空栈。Init_StackSq(SqStack *S) 2栈的链式存储结构链栈顺序栈最大的缺点是：必须设置最大容量，但是当栈的容量不固定时，这样可能会造成很多存储空间的浪费，也可能产生上溢。栈的链式存储结构克服了这个缺点，它采用一个链表结构来表示栈，栈顶指针就是链表的头指针，其插入和删除操作仅在表头进行，如图9.3.3所示。图9.3.3 链栈示意图链栈节点类型的定义如下：typedef struc
27、t Snode ElemType data;/*数据域*/ struct Snode *next;/*指针域*/Snode,*LinkStack;假设s是LinkStack型的变量，则s为链栈的头 指针。下面介绍链栈的插入和删除算法。 p=*S;/*使栈顶指针指向下一节点*/*S=pnext; free(p);/*释放栈顶元素*/return temp;9.3.3 栈的应用栈的应用栈最初用于高级语言的编译程序中，如表达式求值、程序的嵌套以及递归调用等，后来在各类回溯求解问题中也得到应用。下面以过程嵌套的实例来说明栈的应用。过程（函数）嵌套是程序设计中很重要的应用。当过程调用子过程（自定义函数）
28、时，必须把断点的信息及地址保留起来，当子过程执行完毕返回时，取用这些信息，找到返回地址，由此断点继续执行。当程序中出现多重嵌套调用时，必须开辟一个栈，将各层断点信息依次入栈，当各层子过程返回时，又以相反的次序从栈顶取出。如图9.3.4所示给出了具有嵌套调用关系的5个程序，其中主程序要调用子程序SUB1，SUB1要调用子程序SUB2，SUB2要调用子程序SUB3，SUB3要调用子程序SUB4，SUB4不再调用其他子程序。图9.3.4 主程序与子程序之间的调用关系下面来具体介绍计算机系统是如何处理它们之间的调用关系的。其中的关键是要正确处理好执行过程中的调用层次和返回路径，这就需要记忆每一次调用时
29、的返回点。计算机系统用一个栈来动态记忆调用过程中的路径，其基本原则如下：（1）在开始执行程序前，先建立一个栈，其初始状态为空。（2）当发生调用时，将当前调用的返回点地址（在图9.3.4中用语句标号表示）插入到栈。 （3）当遇到从某个子程序返回时，就从栈顶取出返回点地址。根据以上原则，图9.3.4中5个程序在执行过程中的调用顺序以及栈中元素变化的情况如下：（1）主程序开始执行前，建立一个空栈，即栈的状态为（）。（2）开始执行主程序MAIN，当执行到CALL SUB1时，调用子程序SUB1，这时，将本次调用的返回点地址A入栈。此时，栈的状态为（A）。 （3）开始调用执行子程序SUB1，当执行CAL
30、L 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，而S
31、UB4不再调用其他子程序，因此执行完子程序后要返回到子程序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后，栈变为空，即栈的状
32、态为（）。（10）返回到主程序MAIN的A处继续执行，直到主程序MAIN执行完毕。由上述逐步返回的过程可以看出，当子程序返回到上一个调用程序时，需要从栈顶取出返回点地址，即对栈作出栈操作。由于各返回点地址在线性表中的存放顺序恰好是对应的调用顺序，因此，每次从栈顶取出的返回点地址正好对应了各次调用的正确返回顺序。9.3.4 队列的定义及其运算队列的定义及其运算1队列的定义队列（equeue）简称队，也是一种操作受限的线性表，它只允许在表的一端进行插入，而在表的另一端进行删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队首（front）。显然，在队列这种数据结构中，最先插入的元
33、素将最先被删除，反之，最后插入的元素将最后才被删除。所以，队列又称为“先进先出”（First In First Out，FIFO）或者“后进后出”（Last In Last Out， LILO）的线性表，它体现了“先来先服务”的原则。在队列中，队尾指针rear与队首指针front共同反映了队列中元素动态变化的情况。如图9.3.5所示是具有5个元素的队列示意图。图9.3.5 具有5个元素的队列示意图向队列的尾部插入一个元素称为入队运算，从队列的头部删除一个元素称为出队运算。如图9.3.6所示在队列中进行插入与删除的示意图。由图9.3.6可看出，入队运算只涉及尾指针rear的变化，而出队运算只涉及
34、头指针front的变化。图9.3.6 队列的插入与删除运算 2队列的基本运算（1）建立空队列。（2）判定队列是否为空。（3）入队，在队尾插入元素。（4）出队，删除队首元素。（5）返回队首元素。9.3.5 队列的存储结构队列的存储结构线性表的存储结构同样适用于队列，也可根据不同的应用场合分别采用顺序存储结构和链式存储结构。 1队列的顺序存储结构顺序队列在程序设计语言中，一般要用一维数组作为队列的顺序存储空间，同时尚需附设两个指针front和 rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便，我们约定：用队尾指针rear指向队列中的队尾元素，用队首指针front指向头元素的前一
35、个位置。每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。 若对存储队列的数组空间采用动态分配，则顺序队列的结构类型可定义如下： typedef struct ElemType *base;/*初始化的动态分配存储空间*/ int front;/*头指针，若队列不空，则指向队列头元素*/ int rear;/*尾指针，若队列不空，则指向队列尾元素的下一位置*/SqQueue;假设为某队列分配的最大空间为n，则当队尾指针指向数组空间的最后一个位置时，不能再继续插入新的队尾元素，否则会因数组越界而导致程序代码被破坏。然而此时又不适合进行存储再分配扩大数组空间，因为队列
36、的实际可用空间可能并未占满。一个巧妙的方法是采用循环队列。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图9.3.7所示。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列的初始状态为空，即rear=front=0，如图9.3.7所示。图9.3.7 循环队列存储空间示意图在循环队列中，每进行一次入队的运算，队尾指针就加1，当队尾指针rear=m+1时，置rear=0；每进行一次出队运算，队首指针就加1，当队首指针fro
37、nt=m+1时，置front=0。下面介绍顺序队列的建立、插入和删除算法。（1）建立空队列。Init_Queue(SqQueue *Q) 2队列的链式存储结构链队列如果应用程序中使用顺序队列，则必须为它设定一个最大的队列长度，但这样往往会造成存储空间的浪费；当无法预先估计所用队列的最大长度时，则宜采用链式存储结构，即链队列，如图9.3.8所示。链队列的操作即为单链表的插入和删除操作的特殊情况，只是同时需要修改尾指针或头指针，如图9.3.9所示为进行这两种操作时指针变化的情况。图9.3.8 链队列示意图图9.3.9 链队列操作指针变化情况 假定链队列的节点类型类似于前面定义的单链表节点类型，定义
38、如下：9.3.6 队列的应用队列的应用这里从两个方面简述队列在计算机科学领域中的应用：一是解决主机与外部设备之间速度不匹配的问题，二是解决由多用户引起的资源竞争问题。对于第一个方面，这里以主机和打印机之间速度不匹配的问题为例进行简要说明。主机输出数据给打印机，输出数据的速度比打印数据的速度要快得多，若直接把输出的数据送给打印机打印，则由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把需要打印的数据依次写入到这个缓冲区中，写满后就暂停写入，转去做其他的事情；打印机就从缓冲区中按照先进先出的队列操作原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区
39、写入打印数据，这样做既保证了打印数据的正确性，又提高了主机的效率。由此可见，在打印数据缓冲区中所存储的数据就是一个队列。对于第二个方面，CPU资源的竞争也是一个典型的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU运行自己的程序，它们分别通过各自终端向操作系统提出占用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU分配给队首请求的用户使用，当相应的程序运行结束或用完规定的时间间隔后，则令其出队，再把CPU分配给新的队首请求的用户使用，这样既满足了每个用户的请求，又使CPU能够正常运行。9.4 树和二叉树 树型结构是一种重要的非线性结构，它与线
40、性结构的最大区别在于：在这种结构中，除去根节点外每个节点最多只能和上层的一个节点相关，除叶子节点外每个节点都可以和下层的多个节点相关，节点间存在着明显的分支和层次关系。树型结构在客观世界中广泛存在，例如家族关系中的家谱、各种社会组织机构等，都可以形象地用树型结构表示；在计算机软件技术中，树型结构也得到广泛的应用，例如操作系统中的目录（树型）结构、高级语言中源程序的语法结构等。本节主要讨论树和二叉树的定义及其存储结构。9.4.1 树的定义及其存储结构树的定义及其存储结构1树的定义和术语树（tree）是由n个（n0）节点组成的有限集合T，其中有且仅有一个节点称为根节点（root），其余节点可分为m
41、（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棵子树本身也是树。图9.4.1 树树型结构中常用的术语有：（1）节点（node）：表示树中的元素。（2）节点的度（degree）：节点拥有的子树数，如图9.4.1中节点D的度为3，C的度为1。一棵 树中最大的节点度数为这棵树的度，如图9.4.1所
42、示的树的度为3。（3）叶子（leaf）：度为零节点，又称端节点。（4）孩子（child）：除根节点外，每个节点都是其前驱节点的孩子。（5）双亲（parents）：对应上述孩子节点的上层节点称为这些节点的双亲。（6）兄弟（sibling）：同一双亲的孩子。（7）节点的层次（level）：从根节点开始算起，根为第一层，根的直接后继节点为第二层，其余各层以此类推。例如图9.4.1中的节点K，L和M都在第4层。（8）深度（depth）：树中节点的最大层次数。如图9.4.1中树的深度为4。 （9）森林（forest）：是m（m0）棵互不相交的树的集合。（10）有序树、无序树：树中节点在同层中按从左至右有
43、序排列、不能互换的称为有序树，并把各子树分别称为第一子树，第二子树反之称为无序树。2树的存储结构树的存储结构根据应用可以有多种形式，如常见的顺序存储和链式存储结构等，但由于树是非线性结构，因此常采用链式存储结构来表示树，在这里我们只介绍链式存储结构。因为树是多分支非线性表，所以需要采用多重链表结构，即每个节点设有多个指针域，其中每一个指针指向一棵子树的根节点。对于每一个节点的结构类型可以有两种形式：一种是节点异构型，它根据每个节点的子树数设置相应的指针域，由于树中每个节点的度数不尽相同，因此一棵树中各节点的结构形式也不同。这种结构形式虽能节省存储空间，但不方便运算；另一种是采用同构型，即每个节
44、点的指针域个数均为树的度数，这种形式运算方便，但会使链表中出现很多空链域，浪费空间，如图9.4.2所示。假设有一棵具有n个节点的k叉树，则有nk个指针域，其中有用的指针域为n1个，这时的空链域个数为nk(n1)=n(k1)+1个。 图9.4.2 树的链式存储结构由此可见，k越大则空链域所占比例也越高，其中k=2时空链域的比例最低，这就是我们下面要着重讨论的二叉树结构。9.4.2 二叉树二叉树1二叉树的定义二叉树（binary tree）是n（n0）个节点的有限集合，它或为空树（n=0），或由一个根节点和两棵互不相交的分别称为这个根的左子树和右子树的二叉树构成。可以看出，和树的定义一样，二叉树也
45、是递归定义的。应该引起注意的是，二叉树的节点的子树有明确的左、右之分。2几种特殊形式的二叉树（1）满二叉树。深度为h且含有2h1个节点的二叉树称为满二叉树。如图9.4.3所示为一棵深度为4的满二叉树，其节点的编号为自上至下，自左至右，共有241=15个节点。图9.4.3 满二叉树 （2）完全二叉树。如果一棵有n个节点的二叉树，按与满二叉树相同的编号方式对节点进行编号，若树中n个节点和满二叉树1n编号完全一致，则称该树为完全二叉树，如图9.4.4（a）所示。如图9.4.4（b）所示的就不是完全二叉树。图9.4.4 完全二叉树与非完全二叉树 完全二叉树具有以下特点： 1）叶子节点只在层次最大的两层
46、出现。 2）其中任一节点，如果其左子树深度为k，则其右子树的深度为k或k1。（3）平衡二叉树。平衡二叉树又称AVL树，它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，而且左子树和右子树的深度之差的绝对值不超过1。节点的左子树深度减去它的右子树深度定义为节点的平衡因子，所以，平衡二叉树上所有节点的平衡因子只可能是1，0和1。只要二叉树上有一个节点的平衡因子绝对值大于1，则该二叉树就是不平衡的。如图9.4.5（a）所示为平衡二叉树，如图9.4.5（b）所示为不平衡二叉树。图9.4.5 平衡二叉树与不平衡二叉树 3二叉树的基本性质性质1：二叉树的第i层上至多有2i-1
47、（i1）个节点。可用数学归纳法予以证明。性质2：深度为h的二叉树中至多含有2h1个节点。利用性质1的结论可推导得出。性质3：在任意二叉树中，若有n0个叶子节点，n2个度为2的节点，则必有n0=n2+1。性质4：具有n个节点的完全二叉树的深度为log2n+1或log2( n+1)。性质5：如果对一棵有n个节点的完全二叉树（深度为log2n+1）的节点编号，从根节点开始，自上而下，自左而右，则对任一节点i(1in)有（1）如果i=l，则节点i是二叉树的根，无双亲；如果i1，则其双亲是节点i/2 。（2）如果2in，则节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i。（3）如果2i+1n，
48、则节点i无右孩子；否则其右孩子是节点2i+1。 【注意】符号x表示不大于x的最大整数，反之，x表示不小于x的最小整数。4二叉树的存储结构二叉树的存储结构有顺序存储结构和链式存储结构两种。（1）顺序存储结构。顺序存储结构是将二叉树的所有节点，按照一定的顺序方式，存储到一段连续的存储单元中。节点的顺序反映出节点之间的逻辑关系。对于满二叉树或完全二叉树，可用顺序存储结构将n个节点按自上而下、自左至右的顺序依次存放在一段地址连续的存储单元中，即按层存放。如用C语言定义一个完全二叉树为anytype bn;为处理方便，我们定义数组长度为n+1，不用 b0，只用b1bn。一般的二叉树虽然也可以按完全二叉树
49、的形式来存储，但会造成存储空间的浪费。（2）链式存储结构。二叉树通常都采用链式存储。在这种存储方式下，二叉树的每个节点由数据域（data）、左指针域（Lchild）和右指针域（Rchild）组成，即链式存储不要求各个节点的存储空间连续，二叉树的这种存储结构也称为二叉链表，如图9.4.6（a）所示二叉树的二叉链表如图9.4.6（b）所示。图9.4.6 二叉树二叉链表节点描述如下：typedef int datatype;typedef struct node datatype data; struct node *lchild,*rchild;BTnode;BTnode *root;其中，roo
50、t是指向根节点的头指针，当二叉树为空时，rootNULL。当节点某个孩子不存在时，相应的指针为空。5一般树转换为二叉树为了使一般树也能像二叉树一样用二叉链表表示，必须找出树与二叉树间的对应关系。这样当给定一棵树时，可找到唯一的一棵二叉树与之对应，而且这种关系的逆变换也是存在的。在这里只介绍变换的方法，对于变换过程的唯一性不作证明。将一般树转换为二叉树的步骤如下：（1）在兄弟节点之间加一连线。（2）对每个节点，除了保留与其左孩子的连线外，去除与其他孩子间的连线。（3）以树根为轴心，将整棵树顺时针旋转45。如图9.4.7（a），（b），（c）所示为一般树转换为二叉树的过程。图9.4.7 一般树转换
51、为二叉树由转换结果可以看出，任何一棵树转换成二叉树，其右子树必为空。9.4.3 二叉树的遍历二叉树的遍历遍历（traversing）是指按照某条搜索路线，依次访问某数据结构中的全部节点，而且每个节点只被访问一次。对于线性结构来说，遍历很容易实现，只需顺序访问每个节点即可；但是对于非线性结构来说，则要人为设定搜索的路径，路径即连接两个节点的边的集合。 遍历是二叉树中最重要的运算。按照搜索路径的不同，二叉树的遍历分为深度优先遍历和广度优先遍历两种方式。 1深度优先遍历 一棵非空二叉树是由根节点、左子树和右子树 3个基本部分组成的，深度优先遍历二叉树就是依次遍历这3部分。若我们以D，L，R分别表示访
52、问根节点、遍历左子树和遍历右子树，则按顺序排列可以有DLR，LDR，LRD，DRL，RDL和RLD 6种遍历形式。 若规定先左后右，那么上述6种形式可以归并成下述3种形式： DLR：先序遍历； LDR：中序遍历； LRD：后序遍历。由于二叉树是递归定义，因此用递归方式描述二叉树的深度优先遍历较清楚。如先序遍历可定义为：若二叉树为空，则为空操作，否则先访问根节点，然后先序遍历左子树，再先序遍历右子树。这里在遍历左、右子树时递归应用先序遍历的定义。对于中序、后序遍历的定义与此类似，不再赘述。由上述遍历的定义可知，用不同的遍历方式对同一棵二叉树进行遍历，可以得到不同的节点序列。以如图9.4.8所示的
53、二叉树为例，分别用3种遍历方式遍历的结果如下：图9.4.8 遍历二叉树先序：ABCDEFG；中序：CBDAEFG；后序：CDBGFEA。由遍历的定义可以看出，遍历左、右子树的问题仍然是遍历二叉树的问题，当二叉树为空时递归结束，所以很容易给出这3种遍历的递归算法。算法中参量p是指向当前遍历二叉树的根节点指针,函数Visit表示访问当前遍历的节点。 Post_Order(plchild); /*后序遍历左子树*/ Post_Order(prchild); /*后序遍历右子树*/ Visit(pdata); /*访问根节点*/在这3种遍历算法中，访问根节点的操作Visit可视具体应用情况而定。 2广
54、度优先遍历二叉树的广度优先遍历又称为按层次遍历，这种遍历方式是先遍历二叉树的第一层节点，然后遍历第二层节点，最后遍历最下层的节点，而对每一层的遍历是按从左至右的方式进行的。对如图9.4.8所示的二叉树进行广度优先遍历，可得到遍历序列ABECDFG。广度优先遍历算法一般需使用一个队列，开始时把整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都把它的非空左、右孩子节点入队，当队列为空时算法结束。9.4.4 二叉树的应用二叉树的应用二叉树是一种非常有用的树型结构，其应用十分广泛。例如在通信中，对于概率不等的数据的发送，为使传送的代码长度最短，使用了哈夫曼编码，其结构就称哈夫曼树。除
55、此之外二叉树的应用还有二叉排序树与表达式树等，在这里以二叉排序树作为应用的一个例子。二叉排序树是一种特殊结构的二叉树，它或是空树或是具有下述性质的二叉树：（1）其左子树上所有节点的数据值均小于根节点的数值。（2）其右子树上所有节点的数据值均大于或等于根节点的数据值。（3）左子树和右子树又各是一棵二叉排序树。如图9.4.9所示就是一棵二叉排序树。图9.4.9 二叉树的排序在二叉排序树中，若按中序遍历就可以得到由 小到大的有序序列，如图9.4.9所示的二叉排序树，中序遍历可得有序序列2，5，6，7，9，11，14， 16，19，21。二叉排序树是一种动态表结构，也就是说二叉 排序树的生成过程是不断
56、地向二叉排序树中插入新 的节点。对任意的一组数据元素序列R1，R2，Rn，生成一棵二叉排序树的过程为（1）令R1为二叉排序树的根节点。（2）若R2R1，则令R2为R1的左子树的根节点；否则R2为R1的右子树的根节点。（3）R3，Rn节点的插入方法同上。如图9.4.10所示为将序列11，18，3，9，12，2，7，5构成一棵二叉排序树的过程。从以上插入过程可以看出，每次插入的新节点都是二叉排序树上新的叶子节点，因此在进行插入操作时不必移动其他节点。这一特性适用于需要经常插入有序表的场合。图9.4.10 二叉排序树插入过程9.5 图 图（graph）是一种比树和二叉树更为复杂的非线性数据结构。在图
57、这种数据结构中，数据节点之间的关系是任意的，因此，图这种数据结构可以更广泛地表示数据元素之间的关系。可以说，树和二叉树是图的特例，也可以说，树和二叉树是最简单的图。本节简要介绍图的基本概念、存储结构以及遍历。9.5.1 图的定义及其基本操作图的定义及其基本操作1图的定义和术语如果数据元素集合D中的各数据元素之间存在任意的直接前驱或直接后继关系，则此数据结构称为图，通常用G表示。G是一个有序对（V，E），记作G=（V，E），V是一个非空有限集合，它的元素称为顶点（vertex）；E是由V中两个元素vi.，vj组成的序偶或无序对的集合，E的元素称为边（edge）。图分为有向图和无向图。在有向图中，
58、每个边都是有方向的，又称为弧，两顶点间弧的流向只能朝一个指定方向。在无向图中，边是没有方向的，两顶点间的流向可以朝任意一个方向。在无向图中，用不带箭头的边来连接两个有关联的节点（表示这两个节点互为直接前驱和直接后继关系），如图9.5.1所示为两个无向图。若任意两个节点之间存在路径，则称该无向图为连通图。图9.5.1 无向图在有向图中，通常用带有箭头的边（路径）来连接两个有关联的顶点（由直接前驱节点指向直接后继节点）。如图9.5.2所示为两个有向图。若任意一对顶点之间都存在路径，则称该有向图为强连通图，如图9.5.2（b）所示。图9.5.2 有向图在具有n个顶点的无向图中，边的最大数目为n(n1
59、)/2。边数达最大值的无向图称为无向完全图。若一个有向图中每一对顶点之间都存在两条不同方向的边，则称该有向图为有向完全图，此时在n个顶点的有向图中，其边数为n(n1)。在图中，一个顶点的直接后继个数称为该顶点的出度，其直接前驱个数称为该顶点的入度。一个顶点的入度与出度之和称为该顶点的度。对于无向图来说，其中每一个顶点的入度等于该顶点的出度。图中顶点的最大度称为图的度。 实际应用中，图中的每条边可以标上具有某种含义的数值，此数值称为该边的权（weight）；边上带有权的图称做带权图，也称做网（network）。带权图有着极为广泛的应用，例如，在用图表示有公共交通联系的一组城市时，带权图可以表示每
60、两个城市（即图中两个顶点）之间的距离、车费、班次数目等。2图的基本运算由于图中的任何一个顶点都可看成第一个顶点，因此任一顶点的邻接点之间不存在次序问题。为了操作方便，人为地将图中的顶点按一定顺序排列起来，这就出现了对顶点和其邻接点的相应操作，下面列出图的几种基本运算：（1）定位顶点。（2）取顶点。（3）求第一个邻接点。（4）求下一个邻接点。（5）插入顶点。 （6）插入弧。（7）删除顶点。（8）删除弧。9.5.2 图的存储结构图的存储结构由于图的结构比较复杂，图中任意两个顶点之间都有可能存在联系，因此无法用数据元素在存储空间中的物理位置来表示各数据元素之间的直接前驱和直接后继关系。图的存储方法很
61、多，常用的有邻接矩阵法、邻接表法、十字链表法、多重邻接表法等。由于图中各顶点的度各不相同，其最大度数与最小度数可能相差很大，因此在实际应用中，一般是根据对图的具体运算来选取合适的存储结构。我们这里重点介绍常用的两种存储方法邻接矩阵和邻接表。1邻接矩阵假设图中总共有n个顶点，其顶点值分别为d1，d2，dn，并且用自然数将它们依次编号为1，2，n。为了存储图，首先用一个长度为n的一维数组D(1:n)来存放图中各数据顶点的信息，再用一个n阶的二维数组R(1:n,1:n)来存放图中各顶点的关联信息。其中二维数组R称为图的邻接矩阵，也可称为关联矩阵。在邻接矩阵R中，每一个元素R(i,j) (1in,1j
62、n)的定义如下：例如，图9.5.1（a）与图9.5.1（b）所示图的邻接矩阵分别如下：图9.5.2（a）与图9.5.2（b）所示图的邻接矩阵分别如下：由上述邻接矩阵可以明显地看出，无向图的邻接矩阵是对称矩阵，且对角线上的元素均为0。这是因为，对于无向图来说，各顶点之间的直接前驱和直接后继关系是对称的，且不考虑顶点自身之间的直接前驱和直接后继关系。有向图的邻接矩阵不一定是对称的，且其对角线上的元素也不一定是0，因为有可能要考虑顶点自身之间的直接前驱和直接后继关系。如果考虑到无向图的邻接矩阵是对称矩阵，且其对角线上的元素均为0，则在实际存储邻接矩阵时，只需存储其右上三角（或左下三角）的元素即可，这
63、样，具有n个顶点的无向图，其邻接矩阵的存储容量为n（n1）/2。根据邻接矩阵，很容易判断图中任意两个顶点之间是否有边关联，并且也很容易求得各顶点的度。2邻接表邻接表这种存储结构也称为“顺序-索引-链式”存储结构，即顺序与链式存储相结合的存储结构。在这种结构中，只考虑非零元素，所以图中的顶点很多而边很少，可以节省存储空间。 假设图中共有n个顶点，其顶点值分别为d1，d2，dn，并且用自然数将它们依次编号为1，2，n。 首先，用一个顺序存储空间来存储图中各顶点的信息。该顺序存储空间中的每一个存储节点有两个域：数据域data和指针域Link，如图9.5.3（a）所示。其中数据域data用于存放各顶点
64、的信息，即顺序存储空间的第k个存储节点的数据域存放图中编号为k的节点值dk；指针域Link用于链接相应顶点的直接后继，即顺序存储空间的第k个存储节点的指针域链接了图中编号为k的顶点的所有直接后继信息。其次，对图中每一个顶点dk（k=1，2，n）构造一个单链表。该单链表的头指针即为顺序空间中的对应存储节点的指针域。单链表中各存储节点的结构如图9.5.3（b）所示。其中，adjvex域用于存放图中某个顶点的编号；val域用于存放编号为adjvex节点的直接前驱到adjvex节点之间的权值，如果不是带权图，则val域可以不要；Next域用于指向与adjvex节点是同一个直接前驱的另一个直接后继信息的
65、节点。图9.5.3 邻接表中的存储节点结构 由此可知，在图的邻接表表示中，图中某个顶点的所有直接后继被链接成一个单链表，并且，该单链表被链接在顺序存储空间中该节点的Link域上。邻接表特别适合用来表示顶点数多但边数较少的图。例如，对于如图9.5.4所示的带权图，其邻接表如图9.5.5所示。图9.5.4 带权图 图9.5.5 带权图的邻接表表示 由上例可看出，图的邻接表不是唯一的，因为在每个顶点的邻接表中，各边顶点的链接次序可以任意安排，其具体次序与边的输入次序和生成算法有关。在C语言中，邻接表中边节点类型的定义如下：#define VERTEX_NUM 20 /*定义图中最大顶点数*/type
66、def struct edgenode int adjvex; struct edgenode *next;/*指向下一个邻接点的指针*/edgenode;edgenode *adlistVERTEX_NUM; /*定义adlist为存储表头指针的数组*/图的邻接表这种存储结构，对于检测图中某个顶点的直接后继是很方便的，只要随机查找顺序存储空间，便可找到该顶点的所有直接后继所链接的单链表，从该单链表中就可以依次检测到各直接后继的信息。在实际应用中，有时为了能方便地检测到图中各顶点的直接前驱，往往将该顶点的所有直接前驱链接成单链表，这种链式存储结构称为逆邻接表。3多重邻接表在图中，每一条边连接了
67、两个顶点。在有些应用中，需要同时找到表示一条边的两个顶点，此时，邻接表的存储方式就显得不太方便了。在这种情况下，可以用多重邻接表作为图的存储结构。在多重邻接表中，每条边用一个存储节点表示，每个存储节点由5个域组成，如图9.5.6所示。其中，Mark为标志域，用于在遍历图的过程中标记该条边是否被访问过；di与dj分别为与该条边邻接的两个顶点；Di-link用来指向下一条邻接于di的边；Dj-link用来指向下一条邻接于dj的边。图9.5.6 多重邻接表中的节点结构可以看出，在一般情况下，使用多重邻接表会浪费空间或操作不便，所以一般不用。9.5.3 图的遍历图的遍历在实际应用中，往往需要从图的某一
68、个顶点出发访问到图中的所有顶点，这个访问过程称为图的遍历。由于图的结构比二叉树复杂，因此图的遍历要比二叉树的遍历复杂得多。图的任意一个顶点都可能与其他顶点有关联，因此，在遍历图的过程中，当访问了某个顶点之后，必须记录下被访问过的顶点，以避免沿另外的路径重复访问该顶点。为此，在图的遍历过程中，一般会需要设置一个标志数组 visitedn，用它来标记图中某一顶点是否已被访问过，它的初始值为逻辑值假（FALSE），表示未访问过；一旦访问过该顶点，就把它置为逻辑值真（TRUE）。工程中常用的遍历图的方法主要有两种：深度优先搜索法和广度优先搜索法。但不管用哪种方法来遍历图，具体的遍历过程都与图的具体存储
69、结构有关。下面讨论无向图在用邻接表表示下的遍历。1深度优先搜索DFS（Depth First Search）深度优先搜索类似于树的先序遍历，是树的先序遍历的推广。其基本思想如下：以图中某一顶点作为当前节点，然后按以下步骤进行：（1）处理或输出当前节点，并记录当前节点的访问标志。 （2）若当前节点有直接后继节点，则取第一个直接后继节点；若该直接后继节点未被访问过，则以该直接后继节点为当前节点，用深度优先搜索法对其进行访问。（3）如果此时图中还有顶点尚未被访问过，则另选图中一个未访问过的顶点作为起始点，重复上述过程，直到所有顶点都被访问过为止。由上述过程可以看出，深度优先搜索的访问过程是一个递归过
70、程。深度优先搜索遍历图的递归算法描述如下：Boolean visitedMAX;/*访问标志数组*/DFS_Traverse(adlist G, int(*Visit)(int v)/*对图进行深度优先遍历*/ VisitFunc=Visit;/*VisitFunc是全局变量*/ for(v=0;vVERTEX_NUM;+v) /*访问标志数组初始化*/ 2广度优先搜索BFS（Breadth First Search）广度优先搜索类似于树的按层次遍历的过程。 其基本思想如下：以图中某一顶点作为初始点v0，然后按以下步 骤进行：（1）从当前顶点v0出发，并记录当前顶点的访问标志。（2）从v0出发
71、，依次访问v0的未被访问过的邻接点v1，v2，vk，然后依次从v1，v2， vk出发，访问各自未被访问过的邻接点。（3）重复步骤（2）直到图中所有顶点都被访问过为止。广度优先搜索与深度优先搜索不同的是：它首先访问指定出发顶点，然后依次访问该顶点所有未被访问过的邻接点，接下来再访问邻接点的未被访问过的邻接点，依次类推。在用广度优先搜索遍历图的过程中，需要用到一个工作队列，以便正确管理其遍历顺序。广度优先搜索遍历图的算法描述如下：BFS_Traverse(adlist G, int(*Visit)(int v) int u; edgenode *p; SqQueue *Q;for(v=0;vVER
72、TEX_NUM;+v) visitedv=FALSE; Init_Queue(Q);/*初始化队列*/ for(v=0;v VERTEX_NUM;+v)以如图9.5.7所示为例，得出两种遍历序列如下：深度优先搜索遍历得到的顶点序列：V1V2 V4V8V5V3V6V7；广度优先搜索遍历得到的顶点序列：V1V2 V3V4V5V6V7V8。图9.5.7 图的示例9.5.4 最短路径最短路径最短路径问题的背景是：从一个给定的城市出发，能否到达其他各城市？走哪几条公路花费最少？我们用一有向网表示城市的公路网，顶点表示城市，弧表示公路段，弧上的权值代表两个城市之间的距离或运输所需的代价。习惯上称给定的出发
73、点为源点，其他的节点称为终点。最短路径问题的一般提法是：从有向网的源点到其他各终点是否有路径？最短路径是什么？它的长度是多少？从源点到终点的路径存在3种情况：（1）没有路径；（2）只有一条路径，即为最短路径；（3）有几条路径，其中有一条为最短路径。以如图9.5.8所示为例，设顶点v0为源点，从v5到v1没有路径；从 v4到v1只有一条路径（v4，v3，v1），路径长度为35；从v1到v3有3条路径（v1，v3）、（v1，v2， v3）、（v1，v4，v3），其中以路径（v1，v2，v3）为最短，其路径长度为30。图9.5.8 最短路径 求最短路径的算法思想如下：先找出从原点v0到各终点vk的直
74、达路径（v0，vk），即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（v0，u），然后对其余各条路径进行适当调整：若在图中存在弧（u，vk），且（u，vk）和（v0，u）两条弧上权之和小于弧（v0，vk）的权，则以路径（v0，u，vk）代替（v0，vk）。在调整后的各条路径中，再找长度最短的路径，以此类推。迪杰斯特拉给出了一个按路径长度递增次序产生最短路径的算法：用邻接矩阵COST表示有向图G=（V，E），其中设V中有n+1个顶点，COSTij代表（Vi，Vj）上的权，如果边（Vi，Vj）不存在，则COSTij=（在计算机中用允许的最大值代替），若i=j，也取COSTij=。同时，
75、引入一个数组DISTi表示当前所找到的从始点V0到每个终点Vi的最短路径的长度；再引入一个数组PATHi表示从始点V0到每个终点Vi的最短路径。集合S用于存放已求得最短路径的顶点。 算法步骤如下： （1）初始化数组DIST，PATH，S。其中DISTi=COST0i，S为空集，PATHi均为空。（2）选择当前从V0出发的一条最短路径的终点Vi，即DISTi=MinDISTi |ViV-S。（3）将Vi并入S中，即令S=Si，将Vi并入 PATHi中。（4）修改从V0出发到集合VS上所有顶点Vk可以到达的最短路径长度，即如果DISTi+COSTikKi+1，则交换Ri和Ri+1的位置。第一趟全部
76、比较完毕后Rn是序列中最大的记录。再从R1开始两两比较Ri和Ri+1（i=1，2，n-2）的排序码大小，若KiKi+1，则交换Ri和Ri+1的位置。第二趟全部比较完毕后Rn-1是序列中次大的记录。如此反复，进行n-1趟冒泡排序后所有待排序的n个记录序列按排序码排序。例如：待排序记录序列的排序码序列是（26， 47，32，10，15，18，23），写出冒泡排序每一趟执行后的序列状态，如下所示：初始状态26473210151823第1趟（i=16） 263210151823 47第2趟（i=15） 261015182332 47第3趟（i=14） 101518232632 47第4趟（i=13）
77、101518232632 47第5趟（i=12） 101518232632 47第6趟（i=1）1015182326 3247按照上面给出的算法，对具有n个记录的待排序序列要执行n-1趟冒泡排序。但从上例中我们可以发现，执行完第3趟冒泡排序后记录序列已经有序，后面的3趟冒泡“空跑”没有发生交换。因此应该对算法加以改进：能“记住”每趟加工时是否发生了“交换”，若某一趟未发生“交换”，则表示此时记录序列已经有序，就应结束排序过程。冒泡排序是稳定的，其最坏情况下的时间复杂度是O(n2)。但由于冒泡排序能“判别”记录的状态，因此当待排序序列是基本有序的序列时采用冒泡排序方法的效率是很高的。2快速排序在
78、冒泡排序中，比较和交换是在相邻两元素间进行的，每次交换只能前移或后移一个位置，这样总的比较和移动次数就会增多。快速排序（QuickSorting），顾名思义，是目前所有排序方法中速度最快的。它是对冒泡排序的一种改进，此时比较和交换是从两端向中间进行的，总的比较和移动次数就减少了。快速排序的基本思想是：在待排序的n个记录中任取一个记录R（为了方便，一般选取R1），以该记录的排序码k作为初始关键字，以它为准，将所有剩下的n-1个记录分为两个子序列：第一个子序列中每个记录的排序码均小于或等于k；第二个子序列中每个记录的排序码均大于或等于k。然后将k所对应的记录放在第一个子序列之后，第二个子序列之前，
79、使待排序序列成为子序列1R子序列2，完成快速排序的第1趟排序。分别对子序列1和子序列2重复上述划分，直到每个子序列中只有一个记录时为止。快速排序过程如图9.6.1所示。图9.6.1 快速排序过程 可见，快速排序中的基本操作是子序列的划分。设序列的下界是low，上界是hig，则划分操作的步骤如下：第一步：初始化指针i指向序列的第一个记录low，指针j指向序列的最后一个记录hig，并将第一个记录的关键字设为k。第二步：循环（ij）重复用k与j指向的记录关键字比较，若kRj.key，则再比较j的前一个记录（j-1）关键字；否则将记录Rj和Ri互换位置。重复用k与i指向的记录关键字比较，若kRi.ke
80、y，则与i的后一个记录（i+1）关键字比较；否则将记录Ri和Rj互换位置。第三步：重复当i = j时，划分操作结束。例如：一组待排序记录的排序码序列为（59， 38，60，75，70，26，30，59），初始关键字为 59,在第1趟快速排序中记录的交换示意图如图9.6.2所示。图9.6.2 第1趟快速排序过程 快速排序是不稳定排序，它的快慢取决于选择基准元素的方法。如果选择的基准元素恰好是序列中所有元素的中间位数，则所划分的前后两个子序列的元素数目近乎相等。这时排序速度最快，此时的时间复杂度为O(nlog2n)。在理论上已证明，在平均情况下，快速排序时间复杂度仍为O(nlog2n)。大量的实践
81、也已证明：当n较大时，它是目前为止在平均情况下速度最快的一种排序方法。但在最坏情况下，如待排序记录已为有序时，其时间复杂度为O(n2)，这时就退化为“慢速”排序了，从而成为了最差的排序方法。9.6.4 选择排序选择排序选择排序（Select Sorting）的基本思想是：每一趟在待排序的记录中“选择”关键字最小的记录，将它依次加入已排序的记录序列的最后，直至全部记录排完为止。1简单选择排序简单选择排序的基本思想是：通过比较，首先在所有记录中选出关键字最小的记录，把它与第一个记录交换，然后在其余的记录中再选出关键字次小的记录与第二个记录交换，依次类推，直至所有的记录成为有序序列。 例如：待排序记
82、录序列的排序码序列是（26，47，32，10，15，18），使用简单选择排序每一趟执行后的序列状态如下所示： 初始状态264732101518第1趟（i = 1）104732261518第3趟（i = 3）101518264732第4趟（i = 4）101518264732第5趟（i = 5）101518263247简单选择排序是不稳定的，其时间复杂度是O(n2)。这种排序在进行记录交换时需要一个辅助单元，因此，其空间复杂度为O(1)。 2堆排序在简单选择排序中，第1趟在n个关键字中选出最小值，需经过n-1次比较，但没有把比较结果保留下来，以至第2趟需要重新在n1个关键字中进行比较，选出次小值
83、，这样增加了时间开销，堆排序克服了这一缺点。堆排序（Heap Sorting）是在排序过程中将存放在向量中的数据看做是一棵完全二叉树，向量的下标即为完全二叉树的节点序号。它利用完全二叉树上、下层节点之间的特殊关系，不断调整节点的位置，最终完成排序。堆的定义：设有序列K1，K2，Kn，对i=1，2，n/2，若满足则称此序列为堆，其中堆顶是序列中的最大或最小元素。堆排序的过程如下： （1）把现有的序列构成一个堆。设完全二叉树rn中节点rk的左右子树均为堆，为构成以rk为根节点的堆，须进行节点调整，具体操作为把rk的值与其左、右子树根节点值进行比较，若不满足堆的条件，则把rk与其左、右子树根节点中小
84、者进行交换，继续进行比较，直到所有子树均满足为止。对于一个由无序序列rn构成的完全二叉树，只要从它最后一个非叶子节点（第n/2个元素）开始直到根节点（第1个元素）为止，逐步进行上述调整，即可将此完全二叉树构成堆。 （2）输出堆顶元素，重新调整元素，构成新的堆，直到堆空为止。其具体操作为：先由给定的无序序列构造堆，然后把堆顶元素与堆中最后一个元素交换，再把最后一个元素从堆中删除，将余下的元素构成的完全二叉树重新调整为堆，反复进行直到堆空为止。堆排序是不稳定的排序方法，它的时间复杂度为O(nlog2n)，空间复杂度为O(1)。9.6.5 归并排序归并排序归并排序（Merge Sorting）不同于
85、前面已经介绍过的排序方法。“归并”的含义就是将两个（或两个以上）有序表合并成一个新的有序表的操作。若是对两个有序表进行的归并则又称为二路归并。同理有三路归并、四路归并等。二路归并最简单、常用，所以我们只讨论二路归并。二路归并排序的基本步骤如下：第一步：把待排序的n个记录看做是n个长度为1 （记录数目为1）的有序序列，把相邻的序列两两归并成长度为2的有序序列。第二步：把第一步得到的n/2个长度为2的有序序列成对归并。第三步：按照第二步方式对所得有序序列成对归并，直到只剩下一个有序序列时为止。例如：待排序序列为（26，58，49，38，13，69，63），写出二路归并排序每一趟执行后的序列状态。归
86、并排序的序列状态如图9.6.3所示。由上例的二路归并排序过程可以看到，实现二路归并排序算法须先解决两个问题：（1）两个有序子序列的归并算法。图9.6.3 归并排序的序列状态（2）二路归并排序进行一趟的算法。二路归并排序是稳定的，时间复杂度为O(nlog 2n)，由于进行二路归并排序需要附加待排序序列 大小的空间，故其空间复杂度为O(n)。9.6.6 内部排序方法小结内部排序方法小结本节所讨论的几种内部排序方法时间复杂度的比较，如表9.2所示。表9.2 各种内部排序方法比较其中，插入排序、冒泡排序和简单选择排序也可称为“简单排序”。在实际应用中，可根据需要选择合适的排序方法解决问题，主要可以考虑
87、以下3个因素：（1）若待排序的一组记录数目n较小，则可采用插入排序和选择排序，若记录数目信息量较大，则应考虑用其他排序方法。（2）若n较大，则应采用时间复杂度为O(nlog2n)的排序方法。（3）若待排序记录按关键字已基本有序，则应采用直接插入排序或冒泡排序方法。本节介绍的排序方法中，直接插入排序、冒泡排序和归并排序是稳定的排序，而简单选择排序、快速排序和堆排序是不稳定的排序。9.7 查 找 9.7.1 查找的基本概念查找的基本概念查找（Searching）就是根据给定的关键字值，在一组数据中确定一个与其关键字值相等的给定值的数据元素。若存在这样的数据元素，则称查找是成功的；否则称查找不成功。
88、一组待查数据元素的集合又称为查找表。关于查找，一般要明确以下两个问题。 1查找的方法很显然，查找某个数据元素依赖于该数据元素在一组数据中所处的位置，即该组数据中数据元素的组织方式，也就是说，根据数据元素的组织方式来决定采用何种查找方法；反过来，为了提高查找效率，往往要求数据元素采用某些特殊的组织方式。因此在研究各种查找方法时，必须弄清各种方法所适用的组织方式。 2查找算法的评价衡量一个算法的优劣主要有两个标准：时间复杂度和空间复杂度。就查找算法而言，通常只需用一个或几个辅助空间，因此，我们更关心的是时间复杂度。而在查找算法中，基本运算是给定值与关键字值的比较，即算法的主要时间是花费在“比较”上
89、的，所以，我们引出一个称为平均查找长度ASL（Average Search Length）的概念，把它作为评价查找算法好坏的依据。定义：对于含有n个数据元素的查找表，查找成功时的平均查找长度为其中，Pi为查找第i个数据元素的概率，若不特别声明，均认为每个元素的查找概率相等，即P1= P2=Pn=1/n；Ci为查找到第i个数据元素时，需进行的比较次数。查找也分为内部查找和外部查找，内部查找指对存放在内存中的数据结构的查找，外部查找指对存放在外存中的数据结构的查找。在这里，只讨论内部查找。9.7.2 线性表的查找线性表的查找在表的组织方式中，线性表是最简单的一种。下面介绍3种在线性表上进行查找的方
90、法，即顺序查找、折半查找和分块查找。1顺序查找顺序查找（Sequential Searching）也称为线性查找，它是最普通也是最简单的查找技术。其基本思想是从第一个元素开始，逐个把元素的关键字值和给定值比较，若某个元素的关键字值和给定值相等，则查找成功；否则，若直至第n个记录都不相等，说明不存在满足条件的数据元素，查找失败。顺序查找方法不但适用于以顺序存储结构组织的查找表的查找，还适用于以链式存储结构组织的查找表的查找。顺序查找的算法如下（其中ri.key表示数据元素i中的关键字项）：对于本算法，Ci取决于所查元素所处的位置。当查找记录是rn时，仅需比较一次；而查找记录r1时，要比较n次；查
91、找记录是ri时，要比较ni+1次。设每个记录的查找概率相等，则Pi=1/n，故在等概率情况下算法查找成功的平均查找长度为也就是说成功查找的平均比较次数约为表长的一半。顺序查找算法简单，并且对表的结构无任何的要求。但是平均查找长度较大，查找效率低，因此，它只适用于小表，当表较大时，不宜采用顺序查找。2折半查找如果按顺序存储结构组织的查找表中的所有数据元素按关键字有序，则可以采用一种高效率的查找方法折半查找（Binary Searching）（或称为二分查找）。折半查找的基本思想是先确定待查元素所在区域，然后逐步缩小区域，直到查找成功或失败为止。由于查找表中的数据元素按关键字有序（假设递增有序），
92、因此在查找时可不必逐个顺序比较，而采用跳跃的方式先与“中间位置”的记录关键字值比较，若相等，则查找成功；若给定值大于“中间位置”的关键字值，则在查找表的后半部继续进行折半查找，否则在前半部进行折半查找。折半查找的过程如下：假设待查元素所在区域的下界为low，上界hig，则中间位置mid=(low+hig)/2。（1）如果此元素关键字值等于给定值，则查找成功。（2）如果此元素关键字值大于给定值，则在区域(mid+1)hig内进行折半查找。（3）如果此元素关键字值小于给定值，则在区域low(mid1)内进行折半查找。因为折半查找要求数据元素的组织方式应具有随机存取的特性，所以它只适用于以顺序存储结
93、构组织的有序查找表。折半查找成功的平均查找长度为ASLlog2(n+1)1。折半查找的优点是比较次数较少，查找速度快。但为了快速查找所付出的代价是要对数据元素按关键字值的大小进行排序，而排序通常是很费时的，所以折半查找适用于一经建立就很少变动而又经常需进行查找的有序表。 3分块查找分块查找（Block Searching）又称索引顺序查找，把关键字分成若干块，且后一块中的所有关键字均大于前一块中最大的关键字，而每一块中的关键字则不一定有序。例如将16个元素8，12，20，7，31，35，22，25，43，39，40，51，78，73，55，79可划分为4块：8，12，20，7，31，35，22
94、，25， 43，39，40，51，78，73，55，79，则以每一块中的最大关键字作为该块所有元素的索引，这组数据的组织方式如图9.7.1所示。图9.7.1 表及其索引由此可以得出分块查找的基本步骤：第一步：先抽取各块中的最大关键字构成一个递增的索引表；第二步：查找。分两步进行：（1）先对索引表进行折半查找或顺序查找，确定待查记录所在块。（2）在所在块中进行顺序查找。可以证明，当m块中每一块的元素个数接近时，分块查找成功的平均查找长度最小。分块查找的优点是：在表中插入或删除一个元素时，只要找到该元素所属的块，然后在块内进行插入和删除。因为块内元素的存放是任意的，所以插入和删除时无须移动大量元素
95、，所付出的代价是增加了存放索引表的辅助空间，如图9.7.1所示。9.7.3 二叉排序树的查找二叉排序树的查找前面介绍的3种顺序表的查找方法中，折半查找的效率最高，但是折半查找要求查找表中的数据元素按关键字有序，而且不能用链表作存储结构。当对查找表中的数据元素进行插入和删除时，为了保持查找表的有序性，势必要移动很多记录，这就造成新的时间开销。当插入和删除频繁进行时，这种额外开销就会抵消折半查找的优点。由此可以看出，使折半查找效率降低的根本原因是查找表的顺序组织方式，采用二叉排序树作为查找表中数据元素的组织结构，就能避免折半查找方法的不足。二叉排序树或者为空，或者满足下列3个条件：（1）如果二叉排
96、序树根的左子树非空，则左子树上所有节点的关键字值，都小于其根节点的关键字值。（2）如果二叉排序树根的右子树非空，则右子树上所有节点的关键字值都大于或等于其根节点的关键字值。 （3）二叉排序树根的左、右子树均为二叉排 序树。根据二叉排序树的定义，在二叉排序树中，左子树上所有节点的关键字都小于根节点的关键字，右子树上所有节点的关键字都大于或等于根节点的关键字。因此，二叉排序树查找的基本思想是：（1）当二叉排序树不空时，首先将给定值k与根节点的关键字进行比较，如果相等则查找成功。（2）如果给定值k小于根节点的关键字，则下一次与左子树的根节点的关键字进行比较，如果给定值k大于根节点的关键字，则与右子树
97、的根节点的关键字进行比较。如此递归地进行下去，直到某一次比较相等，查找成功；如果一直比较到树叶都不等，则查找失败。例如：数组元素的关键字序列是39，22，42， 17，31，50，28，35，46。这一组数据元素按二叉排序树组织后，所构成的查找表的结构为如图9.7.2所示的二叉树。图9.7.2 构造的二叉排序树如果要查找关键字是31的节点，则第一步：31与根节点P1的关键字比较，因3139，故查找左子树；第二步：31与左子树根节点P2的关键字比较，因为3122，故查找P2的右子树；第三步：31与节点P5的关键字比较，因为31=31，故查找成功。如果要查找关键字是40的节点，则第一步：40与根节
98、点P1的关键字比较，因4039，故查找P1的右子树；第二步：40与节点P3的关键字比较，因4042，故查找P3的左子树；第三步：P3的左子为空，故查找失败。由上例可以看出：在二叉排序树中查找成功时是一条从根节点到所查节点的路径。因此二叉排序树查找的平均查找长度取决于二叉排序树的深度。最好的情况是二叉排序树的形态和折半查找的判定树相同，其ASLlog2n。但值得注意的是，由于二叉排序树是动态生成的，树的节点随节点插入的先后次序的不同而不同，因此有时会蜕化成一棵单支树，此时树的深度为n，其ASL=(n+1)/2（和顺序查找相同），这是最差的情况。9.7.4 哈希表技术及其查找哈希表技术及其查找1哈
99、希表的概念无论是顺序查找、折半查找、分块查找，还是二叉排序树查找，都要通过一系列的比较才能确定被查找元素在查找表中的位置。而哈希（Hash）查找的思想与前面4种方法完全不同，哈希查找方法是利用关键字进行某种运算后直接确定元素的存储位置，所以哈希查找方法是用关键字进行转换，计算元素存储位置的查找方法。在介绍哈希查找之前，先介绍适用于哈希查找的查找表的组织方式哈希表。在一块连续的内存空间采用哈希法建立起来的符号表就称为哈希表。2哈希表的建立哈希表中的数据元素是这样组织的：某个关键字为key的数据元素在放入哈希表时，根据key确定该数据元素在哈希表中的位置。从数学的观点来看就是产生一个函数变换： D
100、=H(key)其中，key是数据元素的关键字，D是在哈希表中的存储位置，H称为哈希函数。为此在建立一个哈希表之前需要解决以下两个问题：（1）构造合适的哈希函数。分析数据元素的关键字集合之特性，找出适当的函数H，使得计算出的存储地址尽可能均匀地分布在哈希表中，尽量减少冲突次数，同时希望函数H尽量简单，以提高关键字到存储地址的转换速度。常用的一些构造方法有：数字分析法、平方取中法、折叠法、除留余数法、直接定址法等。（2）冲突的处理。在哈希表中，不同的关键字值对应到同一个存储位置的现象称为冲突，即K1K2时，H(K1)=H(K2)。K2和K1发生冲突时，就是在存放关键字为K2的数据元素时，同一存储位
101、置已经存放了关键字为K1的数据元素。解决的办法只有重新为关键字是K2的数据元素寻找新的存储地址，这就是冲突处理要完成的任务。 3解决冲突的常用方法利用哈希法建立哈希表时，发生冲突是不可避免的，因此，如何处理冲突是建立哈希表不可缺少的一个方面。处理冲突的方法多种多样，常用的方法有开放地址法、链地址法、再哈希法和公共溢出区法。下面简单介绍开放地址法和链地址法。（1）开放地址法。假设一数据元素的关键字为key，其在哈希表中的存储地址是D=H(key)，此时在哈希表中该地址的存储位置非空，发生了冲突。那么关键字为Key的数据元素在哈希表中的下一个存储位置应该为 D=(H(Key)+di)MOD m i
102、=1，2，k（km-1）其中，H(Key)为哈希函数，m为哈希表表长，di是增量序列。（2）链地址法。链地址法处理冲突的基本思想是：将所有具有相同哈希地址的i个数据元素存储在同一个单链表中。其中，哈希地址等于H(key 1)=H(key 2)=H(key 3)=H(key i)。 4哈希查找在哈希表上进行查找的过程和构造哈希表的过程基本一致。设哈希表为HSTm，哈希函数取H(key)，解决冲突的方法为R(x)，则哈希查找步骤如下：第一步：对给定值k，计算哈希地址i=H(key)，如果HSTi为空，则查找失败；如果HSTi等于k，则查找成功；否则，执行第二步。第二步：重复计算处理冲突后的下一个存
103、储地址dk=R(dk1)，直到HSTdk为空或HSTdk等于k为止；如果HSTdk等于k，则查找成功，否则查找失败。从哈希表的查找过程可知，尽管哈希表在关键字与数据元素的存储位置之间建立了映像关系，但由于“冲突”的产生，使得哈希表的查找过程仍然需要用给定值与元素的关键字值进行比较，所以平均查找长度依然可以作为评价哈希查找效率的标准。本章小结 利用计算机进行数据处理是计算机应用的一个重要方面。大量的数据元素在计算机中如何组织管理，以便提高数据处理的效率，并且节省计算机的内存空间，这是进行数据处理的关键。数据结构是一门研究非数值运算的程序设计问题的学科，它包含数据及其它们之间的关系的描述，以及对数
104、据的抽象运算，如插入、删除运算等。根据数据之间关系性质的不同，数据结构分为逻辑结构与物理结构两种。逻辑结构反映各数据之间的逻辑关系，与数据的存储无关，逻辑结构又分为线性结构和非线性结构。存储结构反映了各数据在计算机内部的实际安排，存储结构又分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构4种。算法的性能主要从正确性、健壮性、可读性、简单性、有效性（即程序运行时的时间复杂度和空间复杂度）几个方面进行评价。其中，时间复杂度和空间复杂度是衡量算法优劣的关键指标。时间复杂度尤其重要，它的数量级采用大写的O表示，通常有常量型、多项式型、对数型、指数型等。线性结构的特点是若结构为非空集，则该结构
105、有且仅有一个开始节点和一个终端节点，并且所有节点都最多只有一个直接前驱和一个直接后继。线性结构主要有线性表、栈和队列等。线性表是最简单、最常用的数据结构。线性表既可以顺序存储，也可以链式存储。顺序存储就是用一段地址连续的存储单元依次存储数据元素，这种结构的表称为顺序表，存储单元中的各元素的物理位置和逻辑结构中各节点相邻关系是一致的。链式存储就是用一段地址任意的存储单元来存储数据元素，这种结构的表称为链表，存储单元可以分布在内存的任何位置上，链表中节点的逻辑次序和物理次序不一定相同。栈是一种特殊的线性表，这种表只在表头（栈顶）进行插入和删除操作，栈的修改遵循后进先出的原则。根据不同的存储结构，栈
106、也分为顺序栈和链栈。队列也是一种特殊的线性表，对这种表，删除操作只在表头（队头）进行，插入操作只在表尾（队尾）进行，队列的修改遵循先进先出的原则。根据不同的存储结构，队列也分为顺序队和链队。非线性结构的特点是一个节点可能有多个直接前驱和直接后继。非线性结构主要分为树型结构和图型结构等。在树型结构中，除根节点外每个节点最多只能和上层的一个节点相关，除叶子节点外每个节点都可以和下层的多个节点相关，这种结构各节点间存在着明显的分支和层次关系。树和二叉树都是树型结构。二叉树的遍历是一种很重要的运算，遍历方法主要有先序、中序和后序遍历。二叉树的存储结构分为顺序存储结构和链式存储结构。图中数据节点之间的关
107、系是任意的，图的存储结构主要有邻接矩阵、邻接表、多重邻接表等几种，图的遍历方法可分为深度优先遍历和广度优先遍历。排序和查找技术是两种应用最广泛的数据处理方法。排序分为内部排序和外部排序两类，几种常用的内部排序有插入排序、交换排序（冒泡排序和快速排序）、选择排序（简单选择排序和堆排序）和归并排序等。查找技术经常应用于线性表，这里主要有顺序查找、折半查找和分块查找等几种方法，另外，还有应用于二叉排序树和哈希表上的查找等。习题九 1简述数据结构的概念，它包括哪几方面的内容？ 2数据的存储结构被分为_、_、_和_4种。 3指出下面算法的时间复杂度。（1）int sum(int n) int p=1,s
108、=0; for(int i=1;i=n;i+) p*=i; s+=p; return s;（2）void mtable(int n) int i,j; for(i=1;i=n;i+) for(j=i;j=n;j+) printf(%d*%d=%dn,i, j, i*j); printf(n); 4什么是线性表、栈和队列？比较其特点。5在线性表的单链表存储中，若一个元素所在节点的地址为p，则其后继节点的地址为_。6设有一个空栈，栈顶指针为1000H，现有一输入序列为a，b，c，d，e，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是_，栈顶指针是_。7有3个元素
109、a，b，c依次入栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。 8假定用一维数组a7顺序存储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23，45，67，80，34，其中23为队首元素，front的值为3，请画出对应的存储状态；当连续作4次出队运算后，再让15，36，48元素依次入队，请再次画出对应的存储状态。9什么是二叉树、满二叉树和完全二叉树？10已知一棵二叉树的先序、中序序列如下，求其后序序列。先序序列：ABDFKICEHJG中序序列：DBKFIAHEJCG11对如题图1所示的二叉树，分别写出它的先序、中序和后序遍历序列。题图112对如题图2（a），（b）所示的图，画出每个图的邻接矩阵和邻接表。题图2 13_排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。 14已知一组关键字序列为：（46，16，53，26，40，38，86，65），请写出执行下列各种排序算法的每一步过程。（1）直接插入排序。（2）冒泡排序。（3）快速排序。（4）简单选择排序。（5）堆排序。15二叉排序树的查找和折半查找的时间性能相同，这种说法是否正确？
