数据结构 第一章 概论

第一章概论一、什么是数据结构1、数据（Data）：数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。2、数据元素（Data Element）：数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。3、数据结构（Data Structure）：数据结构指的是数据之间的相互关系，即数据的组织形式。4、数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（LogicalStructure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。③数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。注意：在表中指出数据元素、数据项、开始结点和终端结点等概念（1）逻辑结构：表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。（2）存储结构：该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3）数据的运算：在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。5、数据的逻辑结构分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。6、数据的四种基本存储方法数据的存储结构可用以下四种基本存储方法得到：（1）顺序存储方法该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组描述。　该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（2）链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。（3）索引存储方法该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是： (关键字、地址)关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 7、数据的运算为了更有效的处理数据，提高数据运算效率，我们按一定的逻辑结构把数据组织起来，并选择适当的存储表示方法把按逻辑结构组织好的数据存储到计算机的存储器里。数据的运算是定义在逻辑结构上的，但运算的具体实现要在存储结构上进行，数据的各种逻辑结构有相应和各种运算，每种逻辑结构都有一个运算的集合，这里列举常用的几种运算：①检索：在数据结构里查找满足一定条件的结点。②插入：往数据结构里增加新的结点。③删除：把指定的结点从数据结构里去掉。④更新：改变指定结点的一个或多个字段的值。⑤排序：保持线性结构的结点序列里结点数不变，把结点按某种指定的顺序重新排列。此外，一个算法应该具有下列特性：①有穷性：一个算法必须总是在招待有穷步之后结束。②确定性：算法的每一步必须是确切的定义的。③输入：一个算法有零个或多个输入。④输出：一个算法有一个或多个输出。⑤可行性：算法应该是可行的。最后，算法和程序和区别：一般来说，一个程序并不需要满足上述的第一个条件（有穷性），另外程序是用机器可执行语言书写的，而算法通常并没有这种限制。8、数据结构三方面的关系数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。【例】若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。附录一：数据类型（DataType）　　所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。【例1．2】C语言的"整数类型"就定义了一个整数可取值的范围（其最大值INT-MAX依赖于具体机器）以及对整数可施加的加、减、乘、除和取模等操作。按"值"是否可分解，可将数据类型划分为两类：①原子类型：其值不可分解。通常是由语言直接提供。【例】C语言的整型、字符型等标准类型及指针等简单的导出类型；②结构类型：其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它也是一种导出类型。【例】C的数组、结构等类型。附录二：抽象数据类型（AbstractType简称ADT）ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。一个ADT可描述为：ADT ADT-Name{Data://数据说明数据元素之间逻辑关系的描述Operations://操作说明Operation1://操作1，它通常可用C或C﹢﹢的函数原型来描述Input:对输入数据的说明Preconditions:执行本操作前系统应满足的状态//可看作初始条件Process:对数据执行的操作Output:对返回数据的说明Postconditions:执行本操作后系统的状态//"系统"可看作某个数据结构Operation2://操作2……}//ADT　　抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C﹢﹢中，我们可以用类（包括模板类）的说明来表示ADT，用类的实现来实现ADT【参阅[10]】。因此，C﹢﹢中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。此外，C﹢﹢中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C﹢﹢中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，main程序就可看作是用户的应用程序。　　由于C语言中没有提供"类"这一数据类型，因此无法实现ADT，故我们不采用ADT的形式来描述数据结构，以节省篇幅。大家只要记住，它实际上等价于我们定义的数据的逻辑结构以及在逻辑结构上定义的抽象操作。附录三：算法的描述　　数据的运算通过算法(Algorithm)描述，讨论算法是数据结构课程的重要内容之一。1．算法　　非形式地说，算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。（1）一个算法可以被认为是用来解决一个计算问题的工具。（2）一个算法是一系列将输入转换为输出的计算步骤。【例1．3】有这样一个排序问题：将一个数字序列排序为非降序。该问题的形式定义由满足下述关系的输入输出序列构成：输入：数字序列〈a1,a2,…,an〉。输出：输出序列的一个枚举〈a1',a2',…，an'〉使得a1'≤a2'≤…≤a3'对于一个输入实例〈31，41，59，26，41，58〉，排序算法应返回输出序列〈26，31，41，41，58，59〉。（1）输入实例输入实例：一个问题的输入实例是满足问题陈述中所给出的限制、为计算该问题的解所需要的所有输入构成的。（2）正确的算法和不正确的算法若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。一个不正确的算法是指对某些输入实例不终止，或者虽然终止但给出的结果不是所渴望得到的答案，一般只考虑正确的算法。2．算法的描述　　一个算法可以用自然语言、计算机程序语言或其它语言来说明，惟一的要求是该说明必须精确地描述计算过程。　　一般而言，描述算法最合适的语言是介于自然语言和程序语言之间的伪语言。它的控制结构往往类似于Pascal、C等程序语言，但其中可使用任何表达能力强的方法使算法表达更加清晰和简洁，而不至于陷入具体的程序语言的某些细节。　　从易于上机验证算法和提高实际程序设计能力考虑，采用C语言描述算法。【例1．4】定义一个输出错误信息后退出程序运行的错误处理函数，该函数将在后续的许多程序中用来简化处理代码。# include //其中有exit的说明# include //其中有标准错误stderr的说明void Error(char*message){fprintf(stderr,"Error: % s \ n ", message) ; //输出错误信息exit(1) ; //终止程序，返回1给操作系统}附录四：算法分析1．评价算法好坏的标准求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是"正确"的。此外，主要考虑如下三点：①执行算法所耗费的时间；②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③算法应易于理解，易于编码，易于调试等等。2．算法性能选择　　一个占存储空间小、运行时间短、其它性能也好的算法是很难做到的。原因是上述要求有时相互抵触：要节约算法的执行时间往往要以牺牲更多的空间为代价；而为了节省空间可能要耗费更多的计算时间。因此我们只能根据具体情况有所侧重：①若该程序使用次数较少，则力求算法简明易懂；②对于反复多次使用的程序，应尽可能选用快速的算法；③若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。3．算法的时间性能分析（1）算法耗费的时间和语句频度　　一个算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。【例1．5】求两个n阶方阵的乘积C=A×B,其算法如下:# define n 100 // n可根据需要定义,这里假定为100void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n]){ //右边列为各语句的频度int i ,j ,k;(1) for(i=0; i＜n;j++) n+1(2)for (j=0;j＜n;j++) {n(n+1)(3)C[i][j]=0; n2(4)for (k=0; k＜n; k++) n2(n+1)(5)C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3}}该算法中所有语句的频度之和(即算法的时间耗费)为：T(n)=2n3+3n2+2n+1 (1.1)分析：　　语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。　　算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。（2）问题规模和算法的时间复杂度算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。　　一个算法的时间复杂度(TimeComplexity,也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。【例1．6】算法MatrixMultidy的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有　　这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法MatrixMultiply的渐近时间复杂度。数学符号"O"的严格的数学定义：若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0，使得当n≥n0时都满足0≤T(n)≤C·f(n)。（3）渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。【例1．7】有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。【例1．8】交换i和j的内容。 Temp=i; i=j; j=temp;以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。【例1．9】变量计数之一。(1) x=0;y=0;(2)for(k-1;k<=n;k++)(3) x++;(4)for(i=1;i<=n;i++)(5) for(j=1;j<=n;j++)(6) y++;一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。【例1．10】变量计数之二。(1) x=1;(2)for(i=1;i<=n;i++)(3) for(j=1;j<=i;j++)(4) for(k=1;k<=j;k++)(5) x++;该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。【例1．11】在数值A[0..n-1]中查找给定值K的算法大致如下： (1)i=n-1; (2)while(i>=0&&(A[i]!=k)) (3)i--; (4)return i;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。（5）最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。【习题】P151、见书上图3、算法如下：（1）以数组第一个元素为最大值m（2）循环i以1为步长，从1到n-1，执行若A[i]>m则 mßA[i];记录下标i；（3）输出最大值及最大值的下标；（4）算法结束。源程序如下：#include main() {int i,j=0;int a[10]={4,6,87,34,11,43,3,5,22,76};int m=a[0];for (i=1;i<10;i++) if(a[i]>m) { m=a[i]; j=i; }printf("\nMax=%d,j=%d",m,j); }