1、第1章 绪论 “数据结构”形成和发展的背景：1.1什么是数据结构 1、用计算机解决问题的步骤： 从具体问题抽象出一个适当的数学模型 设计一个解此数学模型的算法 编程序 调试程序直至成功 例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以 使用迭代算法来求解。预报人口增长情况的数学模型为微分方程。 然而更多的分数只计算问题无法用数学方程加以描述解决这类问 题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构， 才能有效地解决问题。下面所列举的就是属于这一类的具体问题例1、人员信息管理问题（线性数据结构）学号 姓名 性别 籍贯 电 话 通 讯 地 址 01 张三 男 长沙 863
2、9000 麓山南路 327 号 02 李四 男 北京 23456789 学院路 435 号 03 王五 女 广州 30472589 天河路 478 号 04 赵六 男 上海 41237568 南京路 1563 号 05 钱七 女 南京 5013472 南京大学 06 刘八 女 武汉 61543726 武汉大学 07 朱九 男 昆明 4089651 云南大学 08 孙十 女 杭州 6154372 西湖路 635 号 图 1-1 学生数据表 例2、人机对弈问题（树型数据结构）例3、多叉路口交通灯的管理问题（图型数据结构）BACDEABACADBABCBDDADBDCEAEBECEDABACADBA
3、BCBDDADBDCEAEBECED例4：汉诺塔问题：(栈结构）ABC以上例子都是非数值计算问题，描述它们的数学模型不再是数学方程，而是表、树、图、栈等数据结构，因此简单说来： 数据结构是一门研究非数值计算的程序设计数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和问题中计算机的操作对象以及它们之间的关系和操作等的学科。操作等的学科。1.2 基本概念和术语1 数据（数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。 2数据元素（数据元素（data element）数据元素是组成数据的基
4、本单位。 数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。3 数据对象（数据对象（data object）是性质相同的数据元素组成的集合，是数据的一个子集。例如，整数数据对象的集合可表示为N0，1，2.，字母字符数据对象的集合可表示为C=A,B,Z。4 数据结构（数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。数据之间的相互关系称为数据之间的相互关系称为逻辑结构逻辑结构数据结构在计算机中的
5、表示称为数据的数据结构在计算机中的表示称为数据的物理结构物理结构，又称，又称为为存储结构存储结构。这三个方面的关系为： （1）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。数据结构从逻辑结构角度通常分为四类基本结构：一、一、集合集合 结构中的数据元素除了同属于一种类型 外，别无 其它关系。二二、线性结构、线性结构 结构中的数据元素之间存在一对一 的关系。三、三、树型结构树型结构 结构中的数据元素之间存在一对 多的关系。四、四、图状结
6、构或网状结构图状结构或网状结构 结构中的数据元素之间 存在多对多的关系。数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例 复数的数据结构定义如下： Complex=(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。例：设有一个线性表(a1,a2,a3,a4,a5)，它的抽象描述可表示为D=(K,R),其中K=a1,a2,a3,a4,a5,R=,，则它的逻辑结构用图描述见图。 a1a2a3a4a5线性表的逻辑结构描述例：设一个数据结构的抽
7、象描述为D=(K,R),其中K=a,b,c,d,e,f,g,h,r=,则它的逻辑结构用图描述见图。 a b c d e f g h 图 1-5 树形结构抽象描述示意图 例 ：设一个数据结构的抽象描述为D=(K,R),其中K=1,2,3,4,而R=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4), 则它的逻辑结构用图描述见图。 1 2 3 4 图 1-6 图形结构抽象描述示意图 数据结构在计算机中的表示称为数据的数据结构在计算机中的表示称为数据的物理结构物理结构，又，又称为称为存储结构存储结构。在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称
8、这个位串为元元素素或结点结点当数据元素有若干个数据项组成时，位串中对应于各个数据项的子串称为数据域数据域数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构顺序存储结构和链式存储结构链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针（Pointer ），用此指针来表示数据元素之间的逻辑关系。我们可以用数据类型来描述存储结构数据类型（数据类型（data type）是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。例如，高级语言中用到的整数数据类
9、型，是指由32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。抽象数据类型（ADT）指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。一个抽象数据类型的软件模块通常包含定义、表示和实现三部分抽象数据类型可用以下三元组表示：（D,S,P)D是数据对象，S是D上的关系集，P是D上的基本操作集。本书用以下格式定义抽象数据类型：ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据关系：数据关系： 基本操作：基本操作：ADT抽象数据类型名抽象数据类型名其中数据对象和数据关系的定义用伪码描述，
10、基本操作的定义格式为：基本操作名（参数表）基本操作名（参数表） 初始条件：初始条件： 操作结果：操作结果：基本操作有两种参数：赋值参数值为操作提供输入值；引用参数以&打头，除了可以提供输入值，还将返回操作结果。“初始条件”描述操作执行前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若为空则省略“操作结果”说明了操作正常完成后，数据结构的变化和应返回的结果。例：抽象数据类型三元组的定义：ADT Triplet数据对象：D=e1,e2,e3|e1,e2,e3ElemSet数据关系：R1=,基本操作： InitTriplet(&T,v1,v2,v3) 操作结果:构造了三元组T
11、，元素e1,e2,e3分别被赋以参数v1,v2,v3的值 DestroyTriplet(&T) 操作结果：三元组T被销毁 Get(T,i,&e) 初始条件：三元组T已存在，1i3 操作结果：用e返回T的第i元的值 ADT Triplet抽象数据类型可通过固有数据类型来表示和实现，即：利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。对教材采用的类C说明：（1）预定义常量和类型：/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVE
12、RFLOW -2/Status 是函数的类型，其值是函数结果状态代码typedef int Status1.3抽象数据类型的表示与实现(2)数据结构的表示用类型定义（typedf)描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义(3)基本操作的算法都用以下形式的函数描述 函数类型函数类型 函数名(函数参数表) /算法说明 语句序列 /函数名 除了函数的参数需要说明类型外，算法中使用的辅助变量 可以不做变量说明，必要时对其作用给予注释。一般： a、b、c、d、e等用作数据元素名； i、j、k、l、m、n等用作整形变量名； p、q、r等用作指针变量名。 当函数返回值为函数
13、结果状态代码时，函数定义为Status 类型。参数两种：赋值参数和引用参数（以&打头）(4)赋值语句有 简单赋值：变量名=表达式; 串联赋值：变量名1=变量名2=变量名k=表达式; 成组赋值： (变量名1，变量名k)=(表达式1，表达式k); 结构名=结构名; 结构名=(值1，值2，,值k); 变量名=表达式； 变量名起始下标.终止下标=变量名起始下标.终止下标; 变换赋值：变量名 变量名; 条件赋值：条件表达式？表达式T : 表达式F;(5)选择语句有 条件语句1 if(表达式)语句； 条件语句2 if(表达式)语句； else 语句； 开关语句1 switch(表达式) case 值1：语
14、句序列1；break; case 值n：语句序列n；break; default:语句序列n+1; 开关语句2 switch case 条件1：语句序列1；break; case 条件n：语句序列n；break; default:语句序列n+1; (6)循环语句有for语句 for(赋初值表达式序列；条件；修改表达式序列)语句；while语句 while（条件）语句；do-while 语句 do 语句序列； while(条件);(7)结束语句有函数结束语句 return 表达式； ruturn;case结束语句 break;异常结束语句 exit(异常代码)(8)输入和输出语句有输入语句 sc
15、anf(变量1，变量n);输出语句 printf(表达式1，表达式n);(9)注释单行注释 /文字序列 (10)基本函数有求最大值 max(表达式1，表达式n)求最小值 min(表达式1，表达式n)求绝对值 abs(表达式)求不足整数值 floor(表达式)求进位整数值 ceil(表达式)判定文件结束 eof(文件变量) 或eof判定行结束 eoln(文件变量)或 eoln(11)逻辑运算约定与运算&：对于A&B,当A的值为0时，不再对B求值或运算|：对于A|B,当A的值为非0时，不再对B求值例：抽象数据类型Triplet的表示和实现 /-采用动态分配的顺序存储结构-typedef ElemT
16、ype *Triplet; /ElemType类型的指针定义为Triplet类型 /-基本操作的函数原型说明-Status InitTriplet(Triplet &T,ElemType v1, ElemType v2, ElemType v3) 操作结果:构造了三元组T，元素e1,e2,e3分别被赋以参数v1,v2,v3的值Status DestroyTriplet(Triplet &T) 操作结果：三元组T被销毁 Status Get(T,i,&e) 初始条件：三元组T已存在，1i3 操作结果：用e返回T的第i元的值 /-基本操作的实现-Status InitTriplet(Triplet
17、 &T,ElemType v1, ElemType v2, ElemType v3) /构造了三元组T，元素e1,e2,e3分别被赋以参数v1,v2,v3的值 T=(ElemType*)malloc(3*sizeof(ElemType); if(!T) exit(OVERFLOW); T0=v1; T1=v2; T2=v3; return OK;/ InitTripletStatus DestroyTriplet(Triplet &T) /三元组T被销毁 free(T); T=NULL; return OK;/ DestroyTriplet Status Get(T,i,&e) /1i3，用e
18、返回T的第i元的值 if(i3) return ERROR; e=Ti-1; return OK;/Get1.4算法和算法分析算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性 （2）确定性 （3）可行性（4）输入 （5）输出 1.4.2 算法设计的要求评价一个好的算法有以下几个标准:(1) 正确性正确性(Correctness ) 算法应满足具体问题的需求。(2)可读性可读性(Readability) 算法应该好读。以有利于阅读者对程 序的理解。 (3)健状性健状性(Robustness) 算法应具有容错处理。当输入非法
19、数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。1.4.3算法效率的度量算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。度量一个程序的执行时间有两种方法：事后统计方法事后统计方法：由于机器本身的限制，易掩盖算法本身的优劣 但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的
20、时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。事前分析估算方法：事前分析估算方法：求出该算法的一个时间界限函数语句的频度：语句的频度：该语句重复执行的次数。算法：控制结构（顺序、分支、循环） 原操作（指固有数据类型的操作）算法时间取决于两者的综合效果。为便于比较同一问题的不同算法，通常：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量一般，算法中语句频度是问题规模n的某个函数f(n)，记作 T(n)=O(f(n)，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同（即同一个数量级），称作算法的(
21、渐进)时间复杂度定理：若定理：若A(n)=am nm +am-1 nm-1 +a1n+a0是一个是一个 m 次多项式，则次多项式，则A(n)=O(n m)例： +x;s=0; T(n)=2 O(1) 常量阶例：for(i=1;i=n;+i) T(n)=2n O(n) 线性阶 +x;s+=x;例：for(i=1;i=n;+i) T(n)= 2n2 O(n2) 平方阶for(j=1;j=n;+j) +x;s+=x;在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度
22、不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间 复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.，k次方阶O(nk),指数阶O(2n)。即：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。例： 求下列算法段的语句频度及时间复杂度for(i=1; i=n; i+)for(j =1; j 1; -i ) for(j=0;jaj+1) aj aj+1; 最好情况：0次 最坏情况：1+2+3+n-1=n(n-1)/2 平均时间复杂度为:O(n2)1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小)与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。如果输入数据所占空间只取决于问题本身，和算法无关，我们只需讨论除正常占用内存开销外的辅助存储单元规模，否则应同时考虑输入本身所需空间。讨论方法与时间复杂度类似。如果所占用空间量依赖于特定的输入，则出特别指明外，按最坏情况来分析。比如二叉树的遍历问题。
