1、1第第1章章 绪论绪论本章学习内容:1.1 什么是数据结构 1.2 算法描述 1.3 算法分析21.1 什么是数据结构1.1.1 数据结构示例学号姓名性别籍贯电话通讯地址01张三男长沙8639000麓山南路327号02李四男北京23456789学院路435号03王五女广州30472589天河路478号04赵六男上海41237568南京路1563号05钱七女南京5013472南京大学06刘八女武汉61543726武汉大学07朱九男昆明4089651云南大学08孙十女杭州6154372西湖路635号【例1-1】给出一张学生数据表 如下:3在学生表中，一行为一个学生信息，代表一个学生数据，一列为一个
2、属性，整个二维表格形成学生数据的一个线性序列，每个学生排列的位置有先后次序，它们之间形成一种线性关系，是一种典型的数据结构（线性结构），我们将它称为线性表。【例1-2】描述一个磁盘的目录及文件结构，包含一个根目录，若干个一级子目录（文件夹），每个一级子目录中又包含若干个二级子目录（子文件夹），如下所示:d a b c e T g h i j k l m f 在此种结构中，数据之间呈现一对多的非线性关系，也是我们常用的一种数据结构（非线性结构），我们将它称为树形结构。4【例1-3】描述一个大学的校园网，（圆圈代表站点，边表示网线）如下所示。a b c d e f 在此种结构中，数据之间呈现多对多
3、的非线性关系，这也是我们常用的一种数据结构（非线性结构），我们将它称为图形结构。51.1.2 基本术语1数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。2数据元素（data element）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位，但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。3数据对象（data object）数据对象是性质相同的数据元素组成的集合，是数据的一个子集。例如，整数数据对象的集合可表示为N=0,1,2.，大写字母字符数据对象的集合可表示为C=A
4、,B,Z。64数据类型（data type）数据是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。例如，高级语言中用到的整数数据类型，是指由-3276832767中的整数数值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。5抽象数据类型（Abstract Data Types）抽象数据类型通常是指由用户定义，用以表示应用问题的数据模型，抽象数据类型由基本数据类型组成，并包括一组相关的操作。抽象数据类型有些类似于C/C+语言中的struct类型和pascal语言中的record类型，但它增加了相关的操作。在本书中，描述一种抽象数据类型将采用如下书写格式：ADT is Data
5、:Operation:END7【例1-4】给出自然数（Natural Number）的抽象数据类型定义。ADT Natural Number isData:一个整数的有序子集合，它开始于0，终止于机器能表示的最大整数（MAXINT）。Operation:对于所有x,y Natural Number，定义如下操作：add(x,y)求XYsub(x,y)求XYmul(x,y)求XYdiv(x,y)求XYequal(x,y)判断X，Y是否相等end81.1.3 数据结构1数据结构（data structure）数据结构是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构包含三
6、个方面的内容，即数据的逻辑结构、数据的存储结构和对数据所施加的运算。这三个方面的关系为：（1）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存储结构是逻辑结构在计算机存储器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存储结构。比如，例1-1提到的学生数据表，除了有8个学生的数据外，还存在着一对一的线性关系，例1-2提到的磁盘目录及文件结构，除包含文件数据外，还存在着目录之间一对多的非线性关系，例1-3提到的大学校园网，除包含站点数据外，还存在着站点间的多对多的非线性关系。92从逻辑结构划分数据结构数据结构从逻辑结构划
7、分为：（1）线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。（2）非线性结构元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。（3）集合结构元素之间无任何关系，元素的排列无任何顺序。3从存储结构划分数据结构数据结构从存储结构划分为：（1）顺序存储（向量存储）所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存中仍然相邻。10（2）链式存储所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。4数据结构的抽象描述数据结
8、构可用二元组D=(K,R)的形式来描述。其中，K=a1,a2,an为元素集合，R=r1,r2,rm为关系的集合。【例1-5】设有一个线性表（a1,a2,a3,a4,a5），它的抽象描述可表示为D=(K,R)，其中K=a1,a2,a3,a4,a5，R=,，则它的逻辑结构的图形描述如下。a1 a2 a3 a4 a5（3）索引存储使用该方法存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能惟一标识一个结点的那些数据项。（4）散列存储通过构造散列函数，用函数的值来确定元素存放的地址11【例1-6】设一个数据结构的抽象描述为D=(K,R
9、)，其中K=a,b,c,d,e,f,g,h，r=,，则它的逻辑结构的图形描述如下。【例1-7】设一个数据结构的抽象描述为D=(K,R)，其中K=1,2,3,4，而R=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)，则它的逻辑结构的图形描述如下。a b c d e f g h 1 2 3 4 121.2 算法描述1.2.1 基本概念1算法（algorithm）通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）。（2）输出：至少产生一个输出，
10、它们是算法执行完后的结果。（3）有穷性：每条指令的执行次数必须是有限的。（4）确定性：每条指令的含义都必须明确，无二义性。（5）可行性：每条指令的执行时间都是有限的。132算法和程序的关系算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。1.2.2 算法描述1用流程图描述算法一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。2用自然语言描
11、述算法用我们日常生活中的自然语言（可以是中文形式，也可以是英文形式）也可以描述算法。143用其他方式描述算法我们还可以用数学语言或约定的符号语言来描述算法。4用C+描述算法在本教材中，我们将采用C+或类C+来描述算法。用C+描述算法遵循如下规则：（1）所有算法的描述都用C+中的函数形式函数类型 函数名(形参及类型说明)函数语句部分return(表达式值)；（2）函数中的形式参数有两种传值方式若为一般变量名，则为单向传值参数，若在变量前面增加“&”符号，则为双向传地址参数。例如有一个函数为void swap(&i,&j,k)，则i，j为双向传地址参数，k为单向传值参数。15（3）函数的说明部分与
12、函数的实现部分分离在C+中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说明部分与函数的实现部分分离开来。（4）输入函数C+中的输入函数调用为:cin变量名。（5）输出函数C+中的输出函数调用为:cout变量名。（6）C+中的类C+对于面向对象程序设计的支持，核心部分就是类的定义。类的定义体现了抽象数据类型的思想，可以支持说明与实现的分离，将抽象数据类型的实现封装在类的内部，使之达到信息隐蔽的目的。（7）public 说明对于C+的类，类成员可以用public 声明，表示这些东西是公有的，可以在此类及其他类中使用。16（8）private 说明对于C+类，类成员可以用pr
13、ivate声明，表示这些东西是私有的，只能在本类中使用。（9）protected说明对于C+类，类成员可以用protected声明，表示这部分是受保护的，只能在本类及它的所有派生类中使用。（10）C+的作用域在C+中，每个变量都有一个作用域。在函数内声明的变量，仅能在该函数内部有效，在类中声明的变量，可以在该类内部有效。在整个程序中都能使用的变量，为全局变量，否则称为局部变量。若一个全局变量与一个局部变量同名，则该范围内全局变量不起作用。若要使之起作用，可以使用域操作符 来实现。（11）函数名重载C+中允件多个函数取相同的函数名，但形式参数或返回类型可以不同。17（12）友元函数在C+的类声明
14、中，可以使用保留字friend定义友元函数，使用友元函数可以在一个类中访问另一个类中的私有成员（private）和被保护成员（protected）。（13）内联（inline）函数在一个函数定义前加上inline前缀就成为内联函数。使用内联函数可以减少函数调用和参数传递的系统开销。181.3 算法分析求解同一个问题，可以有许多不同的算法，那么怎样来衡量这些算法的优劣呢？首要的条件是选用的算法必须是正确的，其次，考虑如下三点：（1）执行算法所耗费的时间。（2）执行算法所占用的内存开销（主要考虑占用的辅助存储空间）。（3）算法应易于理解，易于编码，易于调试等。191.3.1 时间复杂度1时间频度一
15、个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试（因为，计算机的运行速度与CPU等因素有关。同一算法在不同的计算机上运行的时间是不同的），只需知道在相同的条件下，哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费的时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。【例1-8】求下列算法段的语句频度。for(i=1;i=n;i+)for(j=1;j=i;j+)x=x+1;分析：该算法为一个二重循环，执行次数为内、外循环次数
16、相乘，但内循环次数不固定，与外循环有关，因此，时间频度T(n)=1+2+3+n=。2)1(nn202时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此，引入时间复杂度概念。设T(n)的一个辅助函数为g(n)，定义为当n大于等于某一足够大的正整数n0时，存在两个正的常数A和B（其中AB），使得A B均成立，或有 =A，（其中A为常数），则称g(n)是T(n)的同数量级函数。把T(n)表示成数量级的形式为：T(n)=(g(n),其中大写字母为英文Order（即数量级）一词的第一个字母。)()(ngnTnlim
17、)()(ngnT例如，若T(n)=，则有 =，故它的时间复杂度为(n2)，即(n)与n2数量级相同。2)1(nnnlim2)(nnT2121【例1-9】分析下列算法段的时间频度及时间复杂度。for （i=1;i=n;i+）for (j=1;j=i;j+)for(k=1;k=j;k+)x=i+j-k;分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+(1+2+3+n)=+=+nkkk12)1(nkk1)321(nkk122nkk12216)12)(1(nnn2)1(nn由于有 =，故时间复杂度为(n3)。nlim3)(nnT6122在各种不同算法中，若算法中语句执行次数为一个常数
18、，则时间复杂度为O(1)，另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的时间频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间 复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n2)，立方阶O(n3)，k次方阶O(nk)，指数阶O(2n)，O(3n)，O(kn)，阶乘阶O(n!)等。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率降低。231.3.2 空间复杂度1空间频度一个算法在执行时所占有的内存开销，称为空间频度，但我们一般是讨论算法占用的辅助存储空间。讨论方法与时间频度类似，不再赘述。2空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。
