DS01-概论C语言描述.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数据结构,C,语言描述,王国钧 主 编,唐国民、苏晓萍、马 瑜 副主编,科学出版社,2005年8月,第 1 章 概 论,什么是数据结构,为什么要学习数据结构,算法和算法分析,1.1 什么是数据结构,1.1.,1 数据和数据元素,数据,（,data）,是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。,可以说，数据是计算机程序加工的“原料”。目前，象图像、声音、视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。,数据元素,（,data element）,是数据的基本单位，通常在计算机程序中作为一个整体进行考虑和处理。,数据元素也称为元素、结点或记录。有时，一个数据元素可以由若干个数据项（也称字段、域），数据项是数据不可分割的最小单位。,1.1.2,数据对象和数据类型,数据对象,（,data object）,是性质相同的数据元素的集合，它是数据的一个子集。例如，整数数据对象是集合,N=0，1，2，3，；,大写字母字符数据对象是集合,C=A，B，Z。,要注意的是，计算机中的整数数据对象集合,N,1,应该是上述集合,N,的一个子集，,N,1,=0，1，2，,maxint,，,其中,maxint,是依赖于所使用的计算机和语言的最大整数。,数据类型,（,data type）,是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。例如，,C,语言中的整数类型是区间,-,maxint,，,maxint,上的整数，在这个集合上可以进行加、减、乘、整除、求余等操作。,1.1.3,数据结构,数据结构,（,data structure）,是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。,数据元素的组织形式一般包含下列内容：,数据元素之间的逻辑关系，也称为数据的,逻辑结构,。数据的逻辑结构通常有下列4类（见图1.1）：,集合,：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。,线性结构,：其中的数据元素之间存在一对一的关系。,树型结构,：其中的数据元素之间存在一对多的关系。,图状结构,（或称,网状结构,）：其中的数据元素之间存在多对多的关系。,数据元素以及它们之间的相互关系在计算机存储器内的表示（又称映象），称为数据的,存储结构,，也称数据的,物理结构,。,数据元素之间的,运算,，亦即对数据元素施加的,操作,，有时也直接称为数据的运算或操作。,例1.1,学生成绩表（表1.1）是一个数据结构。,表1.1 学生成绩表,学号,姓名,计算机导论,高等数学,普通物理,平均成绩,04081101,陈小洁,80,90,85,85,04081102,马丽丽,75,68,78,74,04081103,林春英,82,78,66,75,04081104,王澄娟,90,85,93,89,04081150,张吉祥,70,88,75,78,数据结构可以理解为：,按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。,数据结构的内容可归纳为三个部分：,逻辑结构、存储结构和运算集合,。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些,数据上定义了一个运算的集合，就叫做数据结构。,数据的存储结构可采用以下4种基本的存储方法得到：,顺序存储方法,链接存储方法,索引存储方法,散列存储方法,上述,4,种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行,存储映象,。同一种逻辑结构，若采用不同的存储方法，则可以得到不同的存储结构。,1.2 为什么要学习数据结构?,1.2.,1 学习数据结构的重要性,算法+数据结构=程序,1.2.,2 数据结构的应用举例,例1.2,电话号码的查询问题。,要求编写一个电话号码的查询程序。对于任意给出的一个姓名，如果该人留有电话号码，那么就找出他的电话号码；否则就指出该人没有电话号码。,例1.3,n,个城市之间铺设光缆的问题。,假设需要在,n,个城市之间铺设光缆，并且任意两个城市之间都可以铺设。大家知道，在,n,个城市之间只要铺设,n-1,条光缆，即能将这,n,个城市连成网络，只是由于地理位置的不同，所需经费也不同，问题是采用什么样的设计方案能使总投资最省。,这个问题的数学模型是如图1.3（,a）,所示的“图”，图中“顶点”表示城市，顶点之间的连线及其上面的数值表示可以铺设的光缆及所需经费。,1.3 算法和算法分析,1.3.,1 什么是算法?,由于数据的运算是通过算法来描述的，因此，讨论算法是数据结构课程的重要内容之一。,算法,（,Algorithm）,是,对特定问题求解步骤的一种描述,，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个特性：,1、,有穷性,2、,确定性,3、,可行性,4、,输入,5、,输出,程序与算法的异同,在一个算法中，有些指令可能重复执行，因而指令的执行次数可能远远大于算法中的指令条数。由有穷性和可行性得知，对于任何输入，一个算法在执行了有限条指令后一定要终止，而且必须在有限时间内完成。因此，,一个程序如果对任何输入都不会产生无限循环，则它就是一个算法,。,尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。,如果一个算法采用机器可执行的语言来书写，那么它就是一个程序,。,1.3.,2 算法的描述和设计,一个算法可以采用自然语言、数学语言或者约定的符号语言（如伪码、框图等）来描述。,为了方便读者的阅读和实践，本书中的算法和数据结构均使用,C,语言来描述。,本书中采用的,C,语言遵照,ANSI C,标准，各章的程序都在,Turbo C,或,Visual C+6.0,中调试通过。对书中采用的一些预定义常量，简要说明如下：,/*函数结果的状态代码*/,#,define TRUE 1,#define FALSE 0,#define OK 1,#define ERROR 0,其他有关,C,语言的知识，请参考专门介绍,C,语言的书籍。,如何评价算法的优劣？,一般来说，设计一个“好”的算法应该考虑以下几点：,1、正确性算法应当满足具体问题的需求。,2、健壮性当输入数据,非法,时，算法也能适当地作反应或进行处理，而不会产生莫明其妙的输出结果或出错信息，并中止程序的执行。,3、可读性算法主要是为了方便人们的阅读和交流，其次才是机器执行。,4、执行算法所耗费的时间。,5、执行算法所耗费的存储空间，其中主要考虑辅助存储空间。,1.3.,3 算法分析,评价一个程序优劣的重要依据是看这个程序的执行需要占用多少机器资源。在各种机器资源中，最重要的是,时间资源,和,空间资源,。因此，在进行程序分析时，大家最关心的就是程序所用算法在运行时所要花费的时间代价和程序中使用的数据结构所占有的空间代价。通常就称之为,时间复杂度,（时间代价）和,空间复杂度,（空间代价）。,1、算法的时间复杂度分析,一般，一个算法所耗费的时间将随输入数据量,n,的增大而增大。所以算法的时间复杂性是输入数据量,n,的函数,，,这时就称该算法的时间代价为,T,（,n,）。,评价算法的时间复杂性，就是设法找出,T,（,n,）,和,n,的关系，即求出,T,（,n,）。,通常，一个算法是由控制结构（顺序、选择和循环）和“原操作”（指固有数据类型的操作，一条基本语句）构成的，而算法时间取决于两者的综合效果。假定算法每执行一条基本语句（对于所研究的问题来说是基本操作的“原操作”），以该原操作重复执行的次数作为算法的时间度量。大部分情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。所谓语句的,频度,，指的是该语句重复执行的次数。,一个算法所耗费的时间是算法中所有语句执行时间之和，而每条语句的执行时间是该语句的执行次数（频度）与该语句执行一次所需时间（略，因机器不同而不同）的乘积。,通常，只求出,T（n）,随输入数据量,n,而增长的趋势(极限),称,T（n）,的渐近时间复杂性。如果存在正的常数,M,和,n,0,，,当问题的规模,n,n,0,后，算法的时间量度,T,（,n,）,M,f,(,n,)，,那么就称该,算法的时间复杂度,为,O,(,f,(,n,)。,人们通常采用,大,O,表示法,来描述算法分析的结果。,f,(,n,),是某个值非负的函数，这种说法意味着：当,n,充分大时，该算法的复杂度不大于,f,(,n,),的一个常数倍。,一般，求时间复杂度时，只考虑与程序规模有关的频度最大的语句，如循环语句的循环体，多重循环的内循环等。,例1.4,有下列三个程序段：,x=x+1;s=0;,for(i=1;i=n;i+)x=x+1;s=s+x;,for(j=1;j=n;j+),for(k=1;k=n;k+),x=x+1;s=s+x;,它们含基本操作“,x,加1”的语句的频度分别为1、,n,和,n,2,，,因此，对于,程序段来说，其时间复杂度为,O,(,1,)，,程序段的时间复杂度为,O,(,n,)，,程序段的时间复杂度为,O,(,n,2,)。,例1.5,对,n,个记录进行升序排序的问题，采用最简单的选择排序方法。,每次处理时，先从,n,个未排序的记录中选出一个最小记录，则第一次要经过,n-1,次比较，才能选出最小记录；第二次再从剩下的,n-1,个记录中经过,n-2,次比较，选出次小记录；如此反复，直到只剩两个记录时，经过1次比较就可以确定它们的大小。整个排序过程的基本操作（即“原操作”）是“比较两个记录的大小”，含“比较”的语句的频度是：,（,n-1）+（n-2）+1=n（n-1）/2,因此，,其时间复杂度为,O,（,n,2,）。,在同一个算法处理两个规模相同的问题，所花费的时间和空间代价也不一定相同。要全面分析一个算法，应该考虑它在最坏情况下的代价（即对同样规模的问题所花费的最大代价）、最好情况下的代价和平均情况下的代价等。然而，要全面准确地分析每个算法是相当困难的，因此，本书中在分析算法时将主要考虑它们在最坏情况下的代价，个别地方也涉及到其他情况。,通常有如下的函数关系排序：,c,log,2,n,n,n log,2,n,n,2,n,3,10,n,其中，,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+;”,的频度是,n,3,，,所以该程序段的时间复杂度为,O,（,n,3,）。,2、算法的空间复杂度分析,与算法的时间复杂度类似，可以定义算法的空间复杂度如下：如果存在正的常数,M,和,n,0,，,当问题的规模,n,n,0,后，算法的空间量度,S,（,n,）,M,f,(,n,)，,那么就称该,算法的空间复杂度,为,O,（,f,(,n,)）。,一个上机执行的程序，除了需要存储空间来寄存本身所用的指令、常数、变量和输入数据以外，也需要一些,对数据进行处理的工作单元和存储一些为实现计算机所需信息的辅助空间,。如果输入数据所占空间只取决于问题本身，而与算法无关，那么只需要分析除了输入和程序之外的额外空间，否则应该同时考虑输入本身所需要的空间（与输入数据的表示形式有关）。若额外空间相对于输入数据来说是常数，则称此算法为原地工作，有一些排序的算法就属于此类（见第8章）。若所占空间的大小依赖于特定的输入，则一般应按最坏情况来分析。,例1.8,求例1.5中选择排序方法的空间复杂度。,由于第一次处理时，要找出最小记录，并交换位置到最前面；第二次处理时，要找出次小记录，并交换位置到第2位；如此反复，直至排序结束。而每次交换位置需要1个中间变量（,temp）,的存储空间，这是与问题规模,n,无关的常数，因此，选择排序方法的空间复杂度为,O,（1）。,