搜索
——C语言版清华大学出版社2009年9月第1章概论o什么是数据结构o为什么要学习数据结构o算法和算法分析1.1.1数据和数据元素数据（data）是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。1.1什么是数据结构数据——在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。如图像、数、字符、声音、视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。是数据的基本单位。通常在计算机程序中作为一个整体进行考虑和处理。数据元素也称为元素、结点或记录。一个数据元素可以由若干个数据项（也称字段、域）组成，数据项是数据不可分割的最小单位。数据元素（dataelement）：数据对象（dataobject）：是性质相同的数据元素的集合，它是数据的一个子集。例如，所有的“数”构成了数据集合，而正整数集合N={1，2，3，…}是“数”的数据对象；所有的字符是数据，大写字母集合C={‘A’，‘B’，…，‘Z’}是该数据的数据对象。1.1.2数据对象和数据类型要注意的是：计算机中的正整数数据对象集合N1应该是上述集合N的一个子集，N1={1，2，…，maxint}，其中maxint是依赖于所使用的计算机和语言的最大整数。数据类型（datatype）是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。可以看作是数据结构的实现。例如，C语言中的整数类型是区间[-maxint，maxint]上的整数，在这个集合上可以进行加、减、乘、整除、求余等操作。数据结构（datastructure）是指数据对象（集合）以及该数据对象集合中的数据元素之间的相互关系的集合（即数据元素的组织形式）。一组数据元素和一组运算（关系）两个集合组成的集合1.1.3数据结构根据数据元素之间关系的不同，数据结构分为两大类：线性结构非线性结构①集合：数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。②线性结构：数据元素之间存在一对一的关系。③树型结构：数据元素之间存在一对多的关系。④图状结构（或称网状结构）：数据元素之间存在多对多的关系。⑴数据元素之间的逻辑关系，也称为数据的逻辑结构。是数据元素之间抽象化的相互关系。是用户所看到的数据结构，是面向问题的，它不考虑数据的存储。数据的逻辑结构通常有下列4类：⑶数据元素之间的运算（关系）：对数据元素施加的操作，有时也直接称为数据的运算或操作。⑵数据的物理结构：又称存储结构。是数据的逻辑结构在计算机存储器内的表示（又称映象）。它属于具体实现的视图，是面向计算机的。例1.1学生成绩表（表1.1）是一个数据结构。表1.1学生成绩表(每行是一个数据元素)学号姓名计算机导论高等数学普通物理平均成绩04081101陈小洁8090858504081102马丽丽7568787404081103林春英8278667504081104王澄娟90859389┆┆┆┆┆┆04081150张吉祥70887578数据结构可以理解为：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。数据结构主要研究什么？（或者说数据结构的研究对象是什么？）数据结构的内容可归纳为三个部分：按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。逻辑结构存储结构运算集合上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映象。同一种逻辑结构，若采用不同的存储方法，则可以得到不同的存储结构。数据的存储结构（4种基本的存储）⑴顺序存储方法⑵链接存储方法⑶索引存储方法⑷散列存储方法算法+数据结构=程序1.2为什么要学习数据结构?1.2.1学习数据结构的重要性数据结构是计算机专业的专业基础课。它主要讨论在软件开发中如何进行数据的组织、数据的表示和数据的处理。它不仅为操作系统、编译原理、数据库系统、计算机网络等后续课提供必要的知识，而且也为学习者提供必要的技能训练。例1.2电话号码的查询问题。要求编写一个电话号码的查询程序。对于任意给出的一个姓名，如果该人留有电话号码，那么就找出他的电话号码；否则就指出该人没有电话号码。1.2.2数据结构的应用举例例1.3n个城市之间铺设光缆的问题。假设需要在n个城市之间铺设光缆，并且任意两个城市之间都可以铺设。大家知道，在n个城市之间只要铺设n-1条光缆，即能将这n个城市连成网络，只是由于地理位置的不同，所需经费也不同，问题是采用什么样的设计方案能使总投资最省。这个问题的数学模型如下页所示的“图”，图中“顶点”表示城市，顶点之间的连线及其上面的数值表示可以铺设的光缆及所需经费。1.3算法和算法分析1.3.1什么是算法?由于数据的运算是通过算法来描述的，因此，讨论算法是数据结构课程的重要内容之一。算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：1、有穷性在有穷步内结束2、确定性算法中的每一步不会产生二义性3、可行性每一步均可经有限次运算实现4、输入有零个或多个输入5、输出有零个或多个输出程序与算法的异同在一个算法中，有些指令可能重复执行，因而指令的执行次数可能远远大于算法中的指令条数。由有穷性和可行性得知，对于任何输入，一个算法在执行了有限条指令后一定要终止，而且必须在有限时间内完成。因此，一个程序如果对任何输入都不会产生无限循环，则它就是一个算法。尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。1.3.2算法的描述和设计一个算法可以采用自然语言、数学语言或者约定的符号语言（如伪码、框图等）来描述。我们使用C语言来描述。书中采用的一些预定义常量，简要说明如下：/*函数结果的状态代码*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0其他有关C语言的知识，请参考专门介绍C语言的书籍。如何评价算法的优劣？一般来说，设计一个“好”的算法应该考虑以下几点：1、正确性——算法应当满足具体问题的需求。2、健壮性——当输入数据非法时，算法也能适当地作反应或进行处理，而不会产生莫明其妙的输出结果或出错信息，并中止程序的执行。3、可读性——算法主要是为了方便人们的阅读和交流，其次才是机器执行。4、执行算法所耗费的时间。5、执行算法所耗费的存储空间，其中主要考虑辅助存储空间。1.3.3算法分析评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。在各种机器资源中，最重要的是时间资源和空间资源。因此，在进行程序分析时，大家最关心两点：①程序所用算法运行时所要花费的时间代价—时间复杂度②程序中使用的数据结构所占有的空间代价—空间复杂度通常，一个算法是由控制结构（顺序、选择和循环）和基本语句构成的，而算法时间取决于两者的综合效果。以基本语句重复执行的次数作为算法的时间度量。大部分情况下它是最深层循环语句内的基本语句的执行次数（频度）。所谓语句的频度，指的是该语句重复执行的次数。1、算法的时间复杂度分析一般，我们把算法运行的时间定义成函数T(n)，一个算法所耗费的时间将随输入数据量n的增大而增大，n是该算法输入数据的规模，这个数据规模不是某一个具体的输入。T(n)的单位是不确定的，一般把它看成是在一个特定的计算机上执行的指令条数。当讨论一个程序的运行时间T(n)时，注重的不是T(n)的具体值，而是它的增长率。即求出T(n)随输入数据量n而增长的趋势(极限)。称函数f(n)是T(n)增长率的上界，是指存在一个常数M和一个整数n0，当问题的规模n≥n0时，T(n)≤M·f(n)，记为T（n）=O(f(n)),并称该算法的时间复杂度为O(f(n))。这时就称该算法的时间代价为T(n)。人们通常采用大O表示法来描述算法分析的结果。f(n)是某个值非负的函数，这种说法意味着：当n充分大时，该算法的复杂度不大于f(n)的一个常数倍。评价算法的时间复杂性，就是设法找出T(n)和n的关系，即求出T(n)一个算法所耗费的时间是算法中所有语句执行时间之和，而每条语句的执行时间是该语句的执行次数（频度）与该语句执行一次所需时间（略，因机器不同而不同）的乘积。求时间复杂度方法：一般，求时间复杂度时，只考虑与程序规模有关的频度最大的语句，如循环语句的循环体，多重循环的内循环等。例1.4有下列三个程序段：⑴{x=x+1;s=0;}频度为1⑵for(i=1;i=n;i++){x=x+1;s=s+x;}频度为n⑶for(j=1;j=n;j++)for(k=1;k=n;k++){x=x+1;s=s+x;}频度为n2它们含基本操作“x加1”的语句的频度分别为1、n和n2，因此，对于程序段⑴来说，其时间复杂度为O(1)，程序段⑵的时间复杂度为O(n)，程序段⑶的时间复杂度为O(n2)。例1.5对n个记录进行升序排序的问题，采用最简单的选择排序方法。每次处理时，先从n个未排序的记录中选出一个最小记录，则第一次要经过n-1次比较，才能选出最小记录；第二次再从剩下的n-1个记录中经过n-2次比较，选出次小记录；…；如此反复，直到只剩两个记录时，经过1次比较就可以确定它们的大小。整个排序过程的基本操作（即“原操作”）是“比较两个记录的大小”，含“比较”的语句的频度是：（n-1）+（n-2）+…+1=n×（n-1）/2因此，其时间复杂度为O（n2）。在同一个算法处理两个规模相同的问题，所花费的时间和空间代价也不一定相同。要全面分析一个算法，应该考虑它在最坏情况下的代价（即对同样规模的问题所花费的最大代价）、最好情况下的代价和平均情况下的代价等。然而，要全面准确地分析每个算法是相当困难的，因此，我们在分析算法时将主要考虑它们在最坏情况下的代价，个别地方也涉及到其他情况。通常有如下的函数关系排序：clog2nnnlog2nn2n310n其中，c是与n无关的任意常数。上述函数排序与数学中对无穷大的分级完全一致，因为考虑的也是n值变化过程中的趋势，参见图1.4。例1.6要交换变量x和y中的内容，其程序段为temp=x;x=y;y=temp;由于以上三条语句的频度均为1，说明该程序段的执行时间是一个与问题规模n无关的常数，因此，算法的时间复杂度为O（1）。例1.7有程序段如下：x=1;for((i=1;i=n;i++)for(j=1;j=n;j++)for(k=1;k=n;k++)x++;在此程序段中，因为含基本操作“x加1”的语句“x++;”的频度是n3，所以该程序段的时间复杂度为O（n3）。2、算法的空间复杂度分析与算法的时间复杂度类似，可以定义算法的空间复杂度如下：如果存在正的常数M和n0，当问题的规模n≥n0后，算法的空间量度S（n）≤M·f(n)，那么就称该算法的空间复杂度为O（f(n)）。一个上机执行的程序，除了需要存储空间来寄存本身所用的指令、常数、变量和输入数据以外，也需要一些对数据进行处理的工作单元和存储一些为实现计算机所需信息的辅助空间。如果输入数据所占空间只取决于问题本身，而与算法无关，那么只需要分析除了输入和程序之外的额外空间，否则应该同时考虑输入本身所需要的空间（与输入数据的表示形式有关）。若额外空间相对于输入数据来说是常数，则称此算法为原地工作，有一些排序的算法就属于此类（见第8章）。若所占空间的大小依赖于特定的输入，则一般应按最坏情况来分析。例1.8求例1.5中选择排序方法的空间复杂度。由于第一次处理时，要找出最小记录，并交换位置到最前面；