C语言入门教程全第9章

第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．数据元素（dataelement）数据元素是数据集合中的客体（个体），是数据的基本单位，有时也称为节点或记录。例如数据集合N={1，2，3，4，5}中整数1～5都是数据元素。每个数据元素的表现形式是由一个或多个数据项组成的。数据项是具有独立含义的最小标识单位，例如，在老师档案信息管理中的每一位老师就是一个数据元素，组成它的数据项可以是姓名、性别、年龄等。3．数据对象（dataobject）数据对象是具有相同特性的数据元素的集合，是数据的一个子集。例如，一周中的7天就是一个数据对象，可表示为集合W={Mon，Tue，Wed，Thu，Fri，Sat，Sun}；再如，字母数据对象可表示为集合C={‘A’，‘B’，…，‘Z’}。4．数据类型（datatype）数据类型是一个值的集合和定义在该值集上的一组操作的总称。程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系，它不仅规定了该变量可以设定的值的集合，还规定了该集合上的运算。各种语言规定了它所允许的数据类型。在C语言中，基本数据类型包括整型、实型等，这些变量的值是不可再分的；而构造类型包括数组、结构体等，这些变量的值是可以再分的，也可以说它们是带结构的数据，它们的成分可以是基本数据类型，也可以是构造数据类型等。5．数据结构（datastructure）数据结构指的是数据之间的相互关系，即数据的组织形式。可以用集合论的方法定义数据结构如下：S=(D,R)D={ai|ai∈ElemSet,i=0,1,2,3,…,n,n≥0}R={ai-1,ai|ai-1,ai∈D,2≤i≤n}数据结构S是一个二元组，其中D是一个数据元素的有限集合，R是定义在关系D上的有限集合，即R是由有限个关系所构成的集合。若n=0时，则D是一个空集。数据结构分为逻辑结构与物理结构两种。（1）数据的逻辑结构。数据的逻辑结构就是数据元素间的逻辑关系，它研究的是数据元素及其关系的数学特性，与数据的存储无关，是独立于计算机的。数据的逻辑结构可概括地分为线性结构和非线性结构两种，如图9.1.1所示。图9.1.1数据的逻辑结构线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素，除第一个元素以外，其他元素有且仅有一个直接前驱；除最后一个元素外，其他元素都有且仅有一个直接后继。非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继。线性结构主要有线性表、栈和队列等，而非线性结构分为树型结构和图型结构等。（2）数据的物理结构。数据的物理结构又称存储结构，是数据及其关系在计算机中的存放形式，是逻辑结构在计算机存储器中的映像，也就是它的具体实现，通常用高级语言中各种数据类型来描述。在进行实际的数据处理时，被处理的数据都是存放在计算机的存储空间中，而且，各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的。因此，为了能表示出存放在计算机存储空间的各个节点之间的逻辑关系，在数据的存储结构中，不但要存放各个节点的信息，还要存放各个节点之间逻辑关系的信息。下面介绍4种常见的存储结构：1）顺序存储结构。顺序存储结构主要用于线性的数据结构。它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中，各节点之间的逻辑关系由存储单元的邻接关系来体现。如图9.1.2所示为顺序存储结构，假设每个节点占据长度为l（字母，以下同）的存储空间，这个逻辑结构在物理存储器中以一定的顺序占用连续的存储空间。对于这种结构，只需要知道第一个元素的地址和每一个元素所占的存储单元数就可以得到任何一个元素所在的位置。在顺序存储结构中存取任意一个元素所需要的时间是相等的。图9.1.2顺序存储结构2）链式存储结构。顺序存储结构比较适合于线性结构，而非线性结构一般很难用顺序存储结构来实现，所以，通常不用顺序存储结构，而是用链式存储结构来实现非线性结构。链式存储结构是给节点附加指针字段。在这种存储结构中，节点所占的存储单元分为两部分：一部分是用来存放节点自身的信息，称为数据域；另一部分是用来存放该节点后继节点的存储单元的地址，称为指针域。指针域中可以有一个或者多个指针，用来表示节点的一个或多个后继，也可以用来表示其他节点的地址。在用链式存储结构存储一个非线性结构时，节点中的指针个数可以根据该节点的直接后继个数来设置。如图9.1.3所示的链式存储结构，在Addr1的存储单元中，既包含了节点a1本身的信息，又包含了它的后继节点a2的存储单元的地址Addr1+3×l，其他节点与此类似。图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．时间复杂度时间复杂度（timecomplexity）是指计算机执行一个算法时在时间上的消耗度量。度量一个程序的执行时间通常有两种方法：事后统计和事前分析估算。通常人们采用第二种方法，所以这里只介绍事前分析估算方法。一般情况下，把算法中一条语句重复执行的次数称为此语句的频度，它常表示为问题规模n的某个函数，记作F(n)。而算法的时间复杂度则记作T(n)=O(F(n))下面举例说明如何求时间复杂度：for(i=0;in;i++){for(j=0;jn;j++){b[i][j]=0;for(k=0;kn;k++){b[i][j]=b[i][j]+a[i][k]*a[k][j];}}}以执行次数最多的语句（b[i][j]=b[i][j]+a[i][k]*a[k][j];）进行计算：语句频度：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．空间复杂度空间复杂度（spacecomplexity）是指在一个算法的运行过程中，对临时耗费的存储空间的度量，而不包括问题的原始数据占用的空间（因为这些单元与算法无关）。空间复杂度的表示类似于算法的时间复杂度，可记作S(n)=O(F(n))分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般算法本身较简短，所占用的存储空间较少，但运行时需一个附加堆栈，从而占用较多的临时存储空间；若改成非递归算法，则一般可能算法本身较长，所占用存储空间较多，但运行时可能占用较少的临时存储空间。高效且低内存要求的算法最好，但在算法中的时间与空间往往是相互影响的，要节约空间往往就要消耗较多的时间，反之亦然。目前由于计算机硬件的发展，一般都有足够的内存空间，因此在算法评价中应着重考虑时间因素。9.1.3算法分类通常，需要人们解决的特定问题可被分为数值的和非数值的两大类，所以算法通常分为数值算法和非数值算法两类。1．数值算法解决数值问题的算法叫做数值算法