数据结构第一章课件.ppt

1、数据的逻辑结构数据的逻辑结构数据的物理结构（存储结构）数据的物理结构（存储结构）数据的运算数据的运算 数据数据 ：在计算机科学中其含义是指所有能够输入到计：在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。算机中并被计算机程序处理的符号集合。数据元素数据元素 ：是数据集合中的一个实体，是计算机程序中加工处理是数据集合中的一个实体，是计算机程序中加工处理的基本单位。的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项据元素。简单型数据元素由一个数据项组成，所谓数据项就是

2、数据中不可再分割的最小单位；复杂型数据元素由多就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。个数据项组成，它通常携带着一个概念的多方面信息。数据结构数据结构 ：带结构的数据元素的集合带结构的数据元素的集合 简单地说，就是相互之间存在一种或多种特定关系的简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。数据元素的集合。逻辑结构逻辑结构：用数学语言描述数据之间的相互关系。：用数学语言描述数据之间的相互关系。与数据如何存储无关，通常分为四类基本结构：与数据如何存储无关，通常分为四类基本结构：一、集合一、集合 结构中的数据元素除了同属于一

3、种类型结构中的数据元素除了同属于一种类型外，别无其它关系。外，别无其它关系。二、线性结构二、线性结构 结构中的数据元素之间存在一对一结构中的数据元素之间存在一对一的关系。的关系。三、树型结构三、树型结构 结构中的数据元素之间存在一对多结构中的数据元素之间存在一对多的关系。的关系。四四、图状结构或网状结构图状结构或网状结构 结构中的数据元素之间结构中的数据元素之间存在多对多的关系。存在多对多的关系。数据的数据的逻辑结构逻辑结构形式上可以用二元组表示形式上可以用二元组表示:Data-Structure=(D，S)其中：其中：D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集。上关系的

4、有限集。例例 复数的数据结构定义如下：复数的数据结构定义如下：Complex=(C，R)其中：其中：C是含两个实数的集合是含两个实数的集合C1，C2，分别表示分别表示复数的实部和虚部。复数的实部和虚部。R=P，P是定义在集合上的一种关是定义在集合上的一种关系系C1，C2，其中有序偶其中有序偶表示表示C1是复数的是复数的实部，实部，C2 是复数的虚部。是复数的虚部。数据结构的举例数据结构的举例“应用举例应用举例1学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包假设一个学籍档案管理系统应包含如下表含如下表1-1所示的学生信息。所示的学生信息。学 号 姓 名 性别 籍 贯 出生年月 1 981

5、31 刘激扬 男 北 京 1979.12 2 98164 衣春生 男 青 岛 1979.07 3 98165 卢声凯 男 天 津 1981.02 4 98182 袁秋慧 女 广 州 1980.10 5 98203 林德康 男 上 海 1980.05 6 98224 洪 伟 男 太 原 1981.01 7 98236 熊南燕 女 苏 州 1980.03 8 98297 宫 力 男 北 京 1981.01 9 98310 蔡晓莉 女 昆 明 1981.02 10 98318 陈 健 男 杭 州 1979.12表表1-11-1所示的学生信息所示的学生信息 特点：特点：l每个学生的信息占据一行，所有学

6、生的信息按学号顺序依次排列构成一张表格；2表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；3 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。应用举例应用举例2输出输出n个对象的全排列个对象的全排列 输出输出n个对象的全排列可个对象的全排列可以使用下图所示的形式描述。以使用下图所示的形式描述。31213212312321231213211 特点：特点：l在求解过程中，所处理的数据之间具在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；有层次关系，这是我们所说的树形结构；2对它的操作有：建立

7、树形结构，输出对它的操作有：建立树形结构，输出最低层结点内容等等。最低层结点内容等等。应用举例应用举例3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：专业课程的开设情况如下表所示：计 算 机 专 业 学 生 的 必 修 课 程课 程 编 号课 程 名 称需 要 的 先 导 课 程编 号C1程 序 设 计 基 础无C2离 散

8、数 学C1C3数 据 结 构C1，C2C4汇 编 语 言C1C5算 法 分 析 与 设 计C3，C4C6计 算 机 组 成 原 理C11C7编 译 原 理C5，C3C8操 作 系 统C3，C6C9高 等 数 学无C10线 性 代 数C9C11普 通 物 理C9C12数 值 分 析C9，C10，C1c1c9c4c2c12c10c11c5c3c6c7c8特点特点 l l、课程之间的先后关系用图结构、课程之间的先后关系用图结构描述；描述；2 2、通过实施创建图结构，按要求、通过实施创建图结构，按要求将图结构中的顶点进行线性排序。将图结构中的顶点进行线性排序。常见的存储结构常见的存储结构 顺序存储结构

9、顺序存储结构 链式存储结构链式存储结构 索引存储结构索引存储结构 散列存储结构散列存储结构物理结构（存储结构）：物理结构（存储结构）：现在现在抽象数据类型的表示与抽象数据类型的表示与实现实现 数据类型数据类型 在一种程序设计语言中，变量、表达式、常量都具有在一种程序设计语言中，变量、表达式、常量都具有数据类型。通过运算它的值域一定在这个范围之内。数据类型。通过运算它的值域一定在这个范围之内。例例 1 1 在在FORTRANFORTRAN语言中：语言中：变量的数据类型有整型、实型、和复数型变量的数据类型有整型、实型、和复数型 例例2 2 在在C C语言中：语言中：数据类型：基本类型和构造类型数据

10、类型：基本类型和构造类型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义构造类型：数组、结构、联合、指针、枚举型、自定义 数据对象数据对象 某种数据类型元素的集合。某种数据类型元素的集合。例：整数的数据对象是例：整数的数据对象是-3-3，-2-2，-1-1，0 0，1 1，2 2，3 3，英文字符类型的数据对象是英文字符类型的数据对象是AA，B B，C C，D D，E E，F F，抽象数据类型：抽象数据类型：一个数学模型以及定义在该一个数学模型以及定义在该 模型上的一组操模型上的一组操作。作。抽象数据类型实际上就是对该数据结构的定义。

11、抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。的一组算法。用三元组描述如下：用三元组描述如下：（，）分别是数据对象，关系集、基（，）分别是数据对象，关系集、基本操作集本操作集 由于数据结构和操作是分不开的，所以今后我由于数据结构和操作是分不开的，所以今后我们就在们就在抽象数据类型抽象数据类型的角度来研究数据结构。的角度来研究数据结构。抽象数据类型：抽象数据类型：指一个数学模型以及定义在该模型上的一组操作。指一个数学模型以及定义在该模型上的一组操作。抽象数据类型格式：抽象数据类型格式：ADT 抽象数据

12、类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名 1.预定义常量及类型（预定义常量及类型（P12）#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1 数据元素被约定为数据元素被约定为ElemType 类型，用户需要根据类型，用户需要根据具体情况，在使用时自行定义该数据类型。具体情况，在使用时自行定义该数据类型。2.算法描述为以下的函数形式：算法描述为以下的函数形式：函数类型函数类型 函数名（函数参数表）函数名（函数参数表）语句

13、序列；语句序列；为了简化函数的书写，提高算法描述的清晰度，我们为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，规定除函数参数表中的参数需要说明数据类型外，函数函数中使用的局部变量可以不做变量说明中使用的局部变量可以不做变量说明，必要时给出相应，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语的注释即可。另外，在书写算法时，应该养成对重点语句段落句段落添加注解添加注解的良好习惯。的良好习惯。3.在算法描述中可以使用的赋值语句形式有：在算法描述中可以使用的赋值语句形式有：简单赋值简单赋值 变量名变量名=表达式；表达式；串联赋值串联赋值 变量名

14、变量名1=变量名变量名2=.=变量名变量名n=表表达式；达式；成组赋值成组赋值（变量名（变量名1，.，变量名，变量名n）=（表达式表达式1，.，表达式，表达式n）；）；结构赋值结构赋值 结构名结构名1=结构名结构名2；结构名结构名=（值（值1，值，值2，.，值，值n）；）；条件赋值条件赋值 变量名变量名=条件表达式条件表达式?表达式表达式1：表达：表达式式2；交换赋值交换赋值 变量名变量名1 变量名变量名2；4.在算法描述中可以使用的选择结构语句形式有：在算法描述中可以使用的选择结构语句形式有：条件语句条件语句1 if（表达式）表达式）语句；语句；条件语句条件语句2 if（表达式）表达式）语句

15、；语句；else 语句；语句；开关语句开关语句1 switch（表达式）表达式）case 值值1：语句序列：语句序列1；break；case 值值2：语句序列：语句序列2；break；.case 值值n：语句序列语句序列n；break；default：语句序列语句序列n+1；开关语句开关语句2 switch case 条件条件1：语句序列：语句序列1；break；case 条件条件2：语句序列：语句序列2；break；.case 条件条件n：语句序列语句序列n；break；default：语句序列语句序列n+1；5.在算法描述中可以使用的循环结构语句形式有：在算法描述中可以使用的循环结构语句形

16、式有：for循环语句循环语句 for（表达式表达式1；循环条件表达式；循环条件表达式；表达式表达式2）语句；语句；while循环语句循环语句 while（循环条件表达式）循环条件表达式）语句；语句；do-while循环语句循环语句 do 语句序列；语句序列；while（循环条件表达式）；循环条件表达式）；6.在描述算法中可以使用的结束语句形式有：在描述算法中可以使用的结束语句形式有：函数结束语句函数结束语句 return 表达式；表达式；return;case或循环结束语句或循环结束语句 break;异常结束语句异常结束语句 exit（异常代码）；异常代码）；7.在算法描述中可以使用的输入输出

17、语句形式有：在算法描述中可以使用的输入输出语句形式有：输入语句输入语句 scanf(格式串格式串，变量名，变量名1，.，变量名，变量名n)；输出语句输出语句 printf(格式串格式串，表达式，表达式1，.，表达式，表达式n);方括号（方括号（）中的内容是可以省略的部分。）中的内容是可以省略的部分。8.在算法描述中使用的注释格式为：在算法描述中使用的注释格式为：单行注释单行注释 /文字序列文字序列 9.在算法描述中可以使用的扩展函数有：在算法描述中可以使用的扩展函数有：求最大值求最大值 max（表达式表达式1，.，表达式，表达式n）；）；求最小值求最小值 min（表达式表达式1，.，表达式，表

18、达式n）；）；求求绝对值绝对值 abs(表达式）表达式）判断文件结束判断文件结束 eof（文件变量）或文件变量）或eof 【算法算法1-1】用类用类C描述将三个数值排序的算法。描述将三个数值排序的算法。viod Three_Sort(int*x,int*y,int*z)/将将x,y,z三个指针所指示的内容按从小到大的顺序重新排列三个指针所指示的内容按从小到大的顺序重新排列 if(*y*x&*y*z)*x*y;/挑选出最小的数值并换到挑选出最小的数值并换到 x指针所指的存储单元中指针所指的存储单元中 else if(*z*x&*z*y)*x*z;if(*z*y)*y*z;/在在y和和z所指示的存

19、储单元中挑选出较小者换到所指示的存储单元中挑选出较小者换到y中中 1.4.1 算法的概念算法的概念 算法是解决某个特定问题的一种方法或一个过算法是解决某个特定问题的一种方法或一个过程，是求借问题步骤的一种描述。程，是求借问题步骤的一种描述。计算机对数据的操作可以分为数值性和非数值计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。插入、删除等等。设计算法的基本过程设计算法的基本过程 l l通过对问题进行详细地分析

20、，抽象出相应的数学模型；通过对问题进行详细地分析，抽象出相应的数学模型；2 2确定使用的数据结构，并在此基础上设计对此数据结确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；构实施各种操作的算法；3 3 选用某种语言将算法转换成程序；选用某种语言将算法转换成程序；4 4调试并运行这些程序。调试并运行这些程序。算法应该具有下列五个特性算法应该具有下列五个特性 （1）有穷性有穷性：一个算法必须在执行有穷步之后结束。：一个算法必须在执行有穷步之后结束。（2）确定性确定性：算法中的每一步，必须有确切的含义，：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。在他人理解时不

21、会产生二义性。（3）可行性可行性：算法中描述的每一步操作都可以通过已：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。有的基本操作执行有限次实现。（4）输入：输入：一个算法应该有多个输入。一个算法应该有多个输入。（5）输出：输出：一个算法应该有一个或多个输出。这里所一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。说的输出是指与输入有某种特定关系的量。1.4.2 算法的描述算法的描述 选择算法描述语言的准则选择算法描述语言的准则 （1）该语言应该具有描述数据结构和算）该语言应该具有描述数据结构和算法的基本功能；法的基本功能；（2）该语言应该尽可能地简捷，以

22、便于）该语言应该尽可能地简捷，以便于掌握、理解；掌握、理解；（3）使用该语言描述的算法应该能够比）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。较容易地转换成任何一种程序设计语言。举例举例 问题：按从小到大的顺序重新排列问题：按从小到大的顺序重新排列x，y，z三三个数值的内容。个数值的内容。算法：算法：（1）输入）输入x，y，z三个数值；三个数值；（2）从三个数值中挑选出最小者并换到）从三个数值中挑选出最小者并换到x中；中；（3）从）从y，z中挑选出较小者并换到中挑选出较小者并换到y中；中；（4）输出排序后的结果。）输出排序后的结果。1.4.3 1.4.3 算法的评价算法的

23、评价 (1)(1)正确性：正确性：要求算法能够正确地执行预先规定的要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。功能，并达到所期望的性能要求。(2)(2)可读性：可读性：为了便于理解、测试和修改算法，算为了便于理解、测试和修改算法，算法应该具有良好的可读性。法应该具有良好的可读性。(3)(3)健壮性：健壮性：算法中拥有对输入数据、打开文件、算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。与用户对话的形式做出相应的处理选择。(4)(4)时间与空间效率：时间与空间

24、效率：算法的时间与空间效率是算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。的时间及所占据空间的度量。0nn)()(nfcnT)()(nfOnT采用大采用大O表示时间（或空表示时间（或空间）耗费函数，即求出间）耗费函数，即求出T（n）的最高阶，忽略其的最高阶，忽略其低阶项和常系数。低阶项和常系数。1232)(23nnnnT2/2/)1(6/)12)(1(2/)1(111111nnnnniijiniijniniijjk)1(O)(log2nO)(nO)log(2nnO)(2nO)(3nO)(knO

25、)2(nO常数时间，即算法时间用量与输入数据量常数时间，即算法时间用量与输入数据量n的大小无关。的大小无关。对数时间，对数阶通常不写底数（底数无关）。对数时间，对数阶通常不写底数（底数无关）。线性时间，即算法时间用量与线性时间，即算法时间用量与n成正比。成正比。超指数阶，这个算法属于超指数阶，这个算法属于无效算法无效算法，因为只要输入，因为只要输入数据量数据量n稍大一点，算法不能在稍大一点，算法不能在“有限有限”时间内完成时间内完成在算法理论中，当阶不超过在算法理论中，当阶不超过O（nd）（）（d是任意一个正是任意一个正的常数），即为多项式时间，都属于的常数），即为多项式时间，都属于“有效有效

26、范畴范畴”。在有限的时间内完成在有限的时间内完成)(nO！n2算法效率的度量算法效率的度量 对一个算法要作出全面的分析可对一个算法要作出全面的分析可分成两个阶段进行，即分成两个阶段进行，即事先分析事先分析和和事后测试事后测试事先分析事先分析 ：求出该算法的一个时间求出该算法的一个时间界限函数界限函数事后测试事后测试 ：依赖计算机内部的记时依赖计算机内部的记时器器1、依据的算法选用的策略、依据的算法选用的策略2、问题的规模、问题的规模3、书写程序的语言、书写程序的语言4、编译程序时产生的机器代码质量、编译程序时产生的机器代码质量5、计算机执行指令的速度、计算机执行指令的速度定义：定义：如果存在两

27、个正常数如果存在两个正常数c和和n0，对于所有的对于所有的nn0，则记则记T(n)=O(f(n)例、例、for(i=1，i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1到到n，则总次数则总次数为为:nnn=n3时间复杂度为时间复杂度为T(n)=O(n3)频度频度：是指该语句重复执行的次数。一个算法中所有语句：是指该语句重复执行的次数。一个算法中所有语句 的频度之和构成了该算法的运行时间。的频度之和构成了该算法的运行时间。例例+x;s=0;将将x自增看成是基本操作，则语句

28、频度为，即时间自增看成是基本操作，则语句频度为，即时间复杂度为复杂度为(1)如果将如果将s=0也看成是基本操作，则语句频度为，其也看成是基本操作，则语句频度为，其时间复杂度仍为时间复杂度仍为(1)，即常量阶。，即常量阶。例、例、for(i=1;i=n;+i)+x;s+=x;语句频度为：语句频度为：2n其时间复杂度为其时间复杂度为：O(n)即时间复杂度为线性阶。即时间复杂度为线性阶。例、例、for(I=1;I=n;+I)for(j=1;j=n;+j)+x;s+=x;语句频度为：语句频度为：2n2其时间复杂度为：其时间复杂度为：O(n2)即时间复杂度为平方阶。即时间复杂度为平方阶。例例 for(i

29、=2;i=n;+i)for(j=2;j=i-1;+j)/T(n)考虑的是对于问题规模考虑的是对于问题规模n的增长率，在难以精确计算基本的增长率，在难以精确计算基本操作执行次数的情况下，只求出它关于操作执行次数的情况下，只求出它关于n的增长率的增长率 阶阶 +x;ai，j=x;语句频度为：语句频度为：1+2+3+n-2=(1+n-2)(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为时间复杂度为O(n2)即此算法的时间复杂度为平方阶即此算法的时间复杂度为平方阶.一个算法时间为一个算法时间为O(1)的算法，它的基本运算执行的次数是的算法，它的基本运算执行的次数是固定的。因此

30、，总的时间由一个常数（即零次多项式）来限固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为界。而一个时间为O(n2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关以下六种计算算法时间的多项式是最常用的。其关系为系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间的关系为：指数时间的关系为：O(2n)O(n!)1&change;-I)change=false;for(j=0;jaj+1)aj aj+1;change=TURE 最好情况：最好情况：0次次 最坏情况：最坏情况：1+2+3+n-

31、1 =n(n-1)/2 平均时间复杂度为平均时间复杂度为:O(n2)分析以下程序段的时间复杂度：分析以下程序段的时间复杂度：a=0;b=1;(1)for(I=2;I =n;I+)(2)s=a+b;(3)b=a;(4)a=s;(5)T(n)=2+n+n 1+n 1+n 1=2+n+3*(n 1)=4 n 1=O(n)I=1;(1)while(I =n)I=I*2 (2)其中语句其中语句(1)的频度是的频度是1，设语句设语句(2)的频度的频度f(n)，则则有：有：2 f(n)=n 即有即有f(n)=log2n,取最大值取最大值f(n)=log2n 则该则该程序段的时间复杂度程序段的时间复杂度T(n

32、)=1+f(n)=1+log2n=O(log2n)空间效率的分析空间效率的分析 一个算法的空间效率是指在算法的执行过程中，一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该注意空一种是较理想的情况。在设计算法时，应该注

33、意空间效率。间效率。图图1 时间函数的增长率时间函数的增长率常见的多项式阶有常见的多项式阶有:O(1)O(1)O(lognO(logn)O(n)O(n)O(nlognO(nlogn)O(nO(n2 2)O(nO(n3 3)O(2O(2n n)O(n!)O(n!)O(nO(nn n)常见的指数阶有常见的指数阶有:对规模较小的问题对规模较小的问题,决定算法决定算法工作效率的可能是算法的简工作效率的可能是算法的简单性而不是算法执行的时间单性而不是算法执行的时间.当比较两个算法的效率时当比较两个算法的效率时,若两个算法是同阶的若两个算法是同阶的,必须进必须进一步考察阶的常数因子才能一步考察阶的常数因子才能辨别优劣辨别优劣.小小 结结