数据结构清华大学殷人昆ppt课件.ppt

《数据结构清华大学殷人昆ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构清华大学殷人昆ppt课件.ppt（54页珍藏版）》请在三一办公上搜索。

1、1,数据结构 引言,清华大学计算机系 殷人昆,数据结构课件,38-2,数据结构在计算机教育中的地位,计算机教育是一个大的系统工程，有计划、有设计、有实施、有检验，最后要有成果。数据结构在计算机教育中是一门核心课程，是程序设计系列课程中重要的一环。数据结构与算法与程序设计课程一脉相承。程序设计训练学生分析问题、解决问题的技能，数据结构与算法则训练学生在问题解决过程中如何组织数据，如何运用合理的数据结构辅助实现高效的算法。,38-3,数据结构在计算机教育中的地位（必修）,38-4,数据结构在计算机教育中的地位（选修）,5,第一章 基本概念,清华大学计算机系 殷人昆,数据结构课件,第一章 数据结构概

2、论,算法与数据结构的预备知识,38-6,数据结构的基本概念抽象数据类型算法定义性能分析与度量,第一章 数据结构的概念,38-7,数据（data）,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据的分类数值性数据、非数值性数据输入数据、输出数据、存储数据计算机软件 = 程序+文档+数据数据是指计算机程序执行所用的数据,38-8,数据元素 (data element),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项（Data Item）组成。数据项是具有独立含义的最小标识单位。数据元素又称为

3、元素、结点、记录。数据元素的集合是针对某种特定的应用，相同数据类型的数据元素的一个聚集。如学生组成班级，学生是数据元素，班级是一学生集合。,38-9,数据在系统开发中的视图,数据在系统开发中的讨论范畴分为数据结构 + 数据内容 + 数据流数据结构指某一数据元素集合中数据元素之间的关系。数据内容指这些数据元素的具体涵义和内容。数据流指这些数据元素在系统处理过程中是如何传递和变换的。因此，讨论数据结构时,主要不是讨论数据元素的内容和如何处理。,38-10,数据结构（Data Structures）,指某一数据元素集合中的所有数据成员之间的关系。完整的定义为： Data_Structure = D,

4、 R, M 其中，D 是某一数据元素的集合；R 是该集合中所有数据成员之间的关系的有限集合；M 是作用在该集合所有数据成员之上的方法（或操作）。,38-11,例：N 个网点之间的连通关系,树形关系：n 个结点用n-1条边连通。网状关系（或图）：n 个结点可以用多条边（0 en(n-1)/2）连通。e 是边数。,38-12,数据结构是数据的组织形式,数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的物理结构；数据的运算，即对数据元素施加的操作。,38-13,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题

5、抽象出来的数据模型（面向应用的）；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对存储位置无关。,38-14,数据的逻辑结构分类,线性结构 线性表非线性结构 多维数组 广义表 树 图（或网络） 无结构 集合,38-15,线性结构,树形结构,38-16,堆结构,38-17,38-18,数据的存储结构,数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示,38-19,数据类型（Data Type）,数据类型 一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。数据类型的分类基本

6、数据类型构造数据类型C语言中的基本数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,38-20,基本数据类型可以看作是计算机中已实现的数据结构。构造数据类型由基本数据类型或构造数据类型组成，在应用中可视为一种数据模型。构造数据类型由不同成分类型构成。数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。,38-21,抽象数据类型 (ADTs: Abstract Data Types),抽象数据类型由用户定义，用以表示应用问题的数据模型。抽象数据类型由构造数据类型组成, 并包括一组相

7、关的服务（或称操作）。三大特征：信息隐蔽数据封装使用与实现相分离。,38-22,38-23,抽象数据类型构成现代程序设计的基础。它的作用是使程序编写得易于编程、易于测试、易于修改。实现信息隐藏，把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。实现数据封装，把数据和操作封装在一起，从语义上更加完整。实现使用与实现相分离，使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。,38-24,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列算法 + 数据结构 = 程序特性： 输入 有0个或多个输入 输出 有一个

8、或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本，可用计算机指令实现,38-25,几种常用算法的类型,三种最基本的常用算法：穷举型：按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。递推型：由已知至i-1规模的解，通过递推，获得规模为 i 的解。 递归型：把规模为N的问题分解成一些规模较小的问题，然后从这些小问题的解构造出大问题的解 。,38-26,穷举法举例,求解“百钱买百鸡”问题：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱。求解思路：设公鸡数为x，母鸡数为y，小鸡数为z，则可以得到下面的整数不定

9、方程组： x + y + z = 100 5*x + 3*y + z/3 = 100利用穷举法可以写出下面的算法程序：#include void main() ,38-27,int x, y, z; for ( x = 0; x = 100; x+ ) for ( y = 0; y = 100; y+ ) for ( z = 0; z = 100; z+ ) if ( x+y+z = 100 执行结果,38-28,穷举法的算法分析,虽然上述程序很简单，但分析一下可知，此程序为三重循环，循环次数为1013 = 1030301，为106量级。如果改为“万钱买万鸡”，循环次数将达1012量级，计算量

10、太大，这正是穷举法的缺点。为此，可考虑对程序做优化。例如，针对“百钱买百鸡”问题，如果用所有的钱去买公鸡，最多可买20只，而用所有的钱去买母鸡，最多可买33只，所以x、y的值范围可限定在20和33。这样，z的值就自然确定了，而不再是一个变量，可剪去第3层循环。,38-29,与上面程序等效的程序：#include void main() int x, y, z; for ( x = 0, x = 20; x+ ) for ( y = 0; y = 33; y+ ) z = 100-x-y; if ( 5*x+3*y+z/3 = 100 ) printf ( %d%d%dn, x, y, z );

11、 这个程序的循环次数只有21*34 = 714。,38-30,递推法举例,编写程序，用递推法计算斐波那契（Fibonacci）数列的第n项。求解思路：斐波那契（Fibonacci）数列为0, 1, l, 2, 3, 5, 8, 13, ，即： F(0) = 0，F(1) = 1， F(n) = F(n-1)+F(n-2)，当n 1时。用递推法编写的程序为： # include int Fib ( int n ) int f0 = 0, f1 = 1, f, i;,38-31,if ( n = 0 | n = 1 ) return n; for ( i = 2; i = n; i+ ) f =

12、f0 + f1; /由前两步结果推出当前结果 f0 = f1; /原前一步当作下一次的前两步 f1 = f; /当前结果当作下一次的前一步 /在进行向前传递时，要注意传递的时序 return f; 主程序调用方式：int n = 7; printf ( ”Fib(%d)=%dn”, n, Fib (n) );,38-32,递归法举例,所谓递归算法就是在函数过程中直接或间接调用自己。还是求斐波那契数列的问题，相应的递归程序为：int Fib ( int n ) if ( n = 0 | n = 1 ) return n;/结束项else return Fib (n-1) + Fib(n-2);/

13、递归项递归算法简单，但不能无限递归。因此，算法中需要设置递归结束条件。,38-33,递归法分析,递归法的时间效率较低，原因是重复计算太多。例如，计算Fib(5)，总计算次数为2Fib(6)-1 = 15。 递归调用树,38-34,例如，编写一个算法，在一个一维整数数组An中查找满足给定值 x 的元素，找到后函数返回该元素的位置，否则函数返回 -1。int Search ( int A , int x, int n ) int i = 0; while ( i n ) /通过循环枚举检查 if ( Ai = x ) return i; /满足要求 else i = i+1; return -1;

14、,更复杂的实例,38-35,再看递归法。每次递归自己是为了缩小查找区间，逐步逼近到要查找的元素。在函数参数表中增加本次递归调用时的开始查找位置。 int Search ( int A , int x, int n, int start ) if ( start = n ) return -1; if ( Astart = x ) return start; else return Search ( A, x, n, start+1 ); 递归的主调用语句为loc = Search ( A, x, n, 0 )。如果查找失败或查找成功，函数直接返回结果，否则通过递归，到start以后的区间逐个检

15、查。,38-36,性能分析与度量,算法就是为了问题求解。算法的效率是衡量是否具有可计算性的关键。性能分析的目的就是要了解算法的效率。性能（Performance），指算法功能实际执行的功效或表现如何。主要从算法执行的时间和空间效率进行分析。分析方式有：算法的后期测试算法的事前估计,38-37,算法的后期测试,在算法中的某些部位插装时间函数 time ( )，测定算法完成某一功能所花费时间。例如，有一个顺序搜索 (Sequenial Search)算法int seqsearch ( int a , int n, int x ) /在a0,an-1中搜索x int i = 0; while ( i

16、 n ,38-38,插装 time( ) 后的计时程序为 double start, stop; time (可以测算。但受限于硬件设备和操作系统、编译器等，测算比较有一定困难。,38-39,算法的事前估计,空间复杂度度量存储空间的固定部分附加存储空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占空间可变部分尺寸与问题规模有关的成分变量所占空间、递归栈所用空间、通过 malloc 和 free 命令动态使用空间,38-40,时间复杂度度量运行时间 = 算法每条语句执行时间之和。每条语句执行时间 = 该语句的执行次数 (频度)语句执行一次所需时间。语句执行一次所需时

17、间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。,38-41,2n3 + 3n2 + 2n +1,例 求两个 n 阶方阵的乘积 C = AB void MatrixMultiply ( int A , int B , int C , int n ) for ( int i = 0; i n; i+ ) n+1 for ( int j = 0; j n; j+ ) n(n+1) Cij = 0; n2 for ( int k = 0; k n; k+ ) n2(n+1) Cij = Cij +

18、 Aik * Bkj; n3 ,38-42,渐进时间复杂度 大O表示法,算法中所有语句的频度之和是矩阵阶数 n 的函数 T(n) = 2n3 + 2n2 + 2n +1称 n 是问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数。当 n 趋于无穷大时，称时间复杂度的数量级为算法的渐进时间复杂度 T(n) = O(n3) 算法的大O表示大O表示表明当n时，T(n)的变化趋势。,38-43,大O表示法的加法规则（针对并列程序段） T1(n) = O( f (n) ) T2(m) = O( g (m) ) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g

19、 (m)例如，有三段并列程序段 x = 0; y = 0; T1(n) = O(1) for ( int k = 0; k n; k + ) x +; T2(n) = O(n) for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +; T3(n) = O(n2),38-44,整个程序的渐进时间复杂性为 T(n) = T1(n)+T2(n)+T3(n) = O(max(1, n, n2) = = O(n2)大O表示法的乘法规则（针对嵌套程序段）T1(n) = O( f (n) ) T2(m) = O( g (m) ) T(n, m) =

20、 T1(n)T2(m) = O(f (n)g (m)例如，一个选择排序程序，算法思路为：共循环 n-1 次，循环变量 i 从 1 到 n-1，每次循环从 i 到 n 选择最小者，将其对调到第 i 个元素位置。,38-45,void SelectSort ( int A , int n ) / n 是表当前长度 for ( i = 0; i n-1; i+ ) k = i; for ( j = i+1; j n; j+ ) if ( Aj Ak ) k = j; if ( k != i ) Swap(Ak, Ai ); /一趟比较 ,38-46,渐进时间复杂度 O(f (n)*g (n) = O

21、(n2),38-47,c log2n n nlog2n n2 n3 2n 3n n!,38-48,有时, 算法的时间复杂度不仅依赖于问题规模n，还与输入实例的初始排列有关。例如，在数组 An 中查找给定值 k 的算法： int i = n-1; while ( i = 0 算法的语句 i-的频度不仅与 n 有关，还与 A 中各元素的取值，以及 k 的取值有关。,38-49,算法分析例题,例题1. 算法的时间复杂度与（ ）有关。A. 问题规模 B. 计算机硬件的运行速度C. 源程序的长度 D. 编译后执行程序的质量解答：A。算法的具体执行时间与计算机硬件的运行速度、编译产生的目标程序的质量有关，

22、但这属于事后测量。算法的时间复杂度的度量属于事前估计，与问题的规模有关。,38-50,例题2. 某算法的时间复杂度是O(n2)，表明该算法（ ）。A. 问题规模是n2 B. 问题规模与n2成正比C. 执行时间等于n2 D. 执行时间与n2成正比解答：D。算法的的时间复杂度是O(n2)，这是设定问题规模为 n 的分析结果，所以A、B 都不对；它也不表明执行时间等于n2，它只表明算法的执行时间T(n)cn2（c为比例常数）。有的算法，如nn矩阵的转置，时间复杂度为O(n2)，不表明问题规模是n2。,38-51,例题3. 下面说法中错误的是（ ）。 算法原地工作的含义是指不需要任何额外的辅助空间 在

23、相同问题规模 n 下，时间复杂度为O(n)的算法总是优于时间复杂度为O(2n)的算法 所谓时间复杂度是指在最坏情形下估算算法执行时间的一个上界 同一个算法，实现语言的级别越高，执行效率越低A. B. C. D. 解答：A。算法原地工作的含义指空间复杂度O(1),38-52,例题4. 有实现同一功能的两个算法A1和 A2，其中A1 的渐进时间复杂度是T1(n) = O(2n)，A2 的渐进时间复杂度是T2(n) = O(n2)。仅就时间复杂度而言，具体分析这两个算法哪个好。解答：比较算法好坏需比较两个函数2n和n2。当n = 1时，21 12，算法A2好于A1当n = 2时，22 = 22，算法

24、A1与A2相当当n = 3时，23 42，算法A2好于A1当n 4时，2n n2，算法A2好于A1当n时，算法A2在时间上显然优于A1。,38-53,例题5 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是x = 2;while ( x n/2 ) x = 2*x;A. O(log2n)B. O(n) C. O(nlog2n) D. O(n2)解答：选A。找关键操作，即最内层循环中的执行语句 x = 2*x。因为每次循环x都成倍增长，设 x = 2k n/2，2k+1 n，则k log2n-1，实际while循环内的语句执行了log2n-2次。,38-54,例题6 求整数n（n0）阶乘的算法如下，其时间复杂度是int fact ( int n ) if ( n = 1 ) return 1; return n*fact ( n-1 );A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)解答：选B。因为T(1) = 1，T(n) = 1+T(n-1) = 1+(1+T(n-2) = 2+(1+T(n-3) = 3+(1+T(n-4) = = (n-1)+T(1) = n。,计算fact(n-1),计算*,