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

1,数据结构 引言,清华大学计算机系 殷人昆,数据结构课件,38-2,数据结构在计算机教育中的地位,计算机教育是一个大的系统工程，有计划、有设计、有实施、有检验，最后要有成果。数据结构在计算机教育中是一门核心课程，是程序设计系列课程中重要的一环。数据结构与算法与程序设计课程一脉相承。程序设计训练学生分析问题、解决问题的技能，数据结构与算法则训练学生在问题解决过程中如何组织数据，如何运用合理的数据结构辅助实现高效的算法。,38-3,数据结构在计算机教育中的地位（必修）,38-4,数据结构在计算机教育中的地位（选修）,5,第一章 基本概念,清华大学计算机系 殷人昆,数据结构课件,第一章 数据结构概论,算法与数据结构的预备知识,38-6,数据结构的基本概念抽象数据类型算法定义性能分析与度量,第一章 数据结构的概念,38-7,数据（data）,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据的分类数值性数据、非数值性数据输入数据、输出数据、存储数据计算机软件 = 程序+文档+数据数据是指计算机程序执行所用的数据,38-8,数据元素 (data element),数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项（Data Item）组成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。数据元素的集合是针对某种特定的应用，相同数据类型的数据元素的一个聚集。如学生组成班级，学生是数据元素，班级是一学生集合。,38-9,数据在系统开发中的视图,数据在系统开发中的讨论范畴分为数据结构 + 数据内容 + 数据流数据结构指某一数据元素集合中数据元素之间的关系。数据内容指这些数据元素的具体涵义和内容。数据流指这些数据元素在系统处理过程中是如何传递和变换的。因此，讨论数据结构时,主要不是讨论数据元素的内容和如何处理。,38-10,数据结构（Data Structures）,指某一数据元素集合中的所有数据成员之间的关系。完整的定义为： Data_Structure = D, R, M 其中，D 是某一数据元素的集合；R 是该集合中所有数据成员之间的关系的有限集合；M 是作用在该集合所有数据成员之上的方法（或操作）。,38-11,例：N 个网点之间的连通关系,树形关系：n 个结点用n-1条边连通。网状关系（或图）：n 个结点可以用多条边（0 en(n-1)/2）连通。e 是边数。,38-12,数据结构是数据的组织形式,数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的物理结构；数据的运算，即对数据元素施加的操作。,38-13,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题抽象出来的数据模型（面向应用的）；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对存储位置无关。,38-14,数据的逻辑结构分类,线性结构 线性表非线性结构 多维数组 广义表 树 图（或网络） 无结构 集合,38-15,线性结构,树形结构,38-16,堆结构,38-17,38-18,数据的存储结构,数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示,38-19,数据类型（Data Type）,数据类型 一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称。数据类型的分类基本数据类型构造数据类型C语言中的基本数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,38-20,基本数据类型可以看作是计算机中已实现的数据结构。构造数据类型由基本数据类型或构造数据类型组成，在应用中可视为一种数据模型。构造数据类型由不同成分类型构成。数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。,38-21,抽象数据类型 (ADTs: Abstract Data Types),抽象数据类型由用户定义，用以表示应用问题的数据模型。抽象数据类型由构造数据类型组成, 并包括一组相关的服务（或称操作）。三大特征：信息隐蔽数据封装使用与实现相分离。,38-22,38-23,抽象数据类型构成现代程序设计的基础。它的作用是使程序编写得易于编程、易于测试、易于修改。实现信息隐藏，把所有数据和操作分为公有和私有，可减少接口复杂性，从而减少出错机会。实现数据封装，把数据和操作封装在一起，从语义上更加完整。实现使用与实现相分离，使用者只能通过接口上的操作来访问数据，一旦将来修改数据结构，可以使得修改局部化，提高系统灵活性。,38-24,算法定义,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列算法 + 数据结构 = 程序特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本，可用计算机指令实现,38-25,几种常用算法的类型,三种最基本的常用算法：穷举型：按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。递推型：由已知至i-1规模的解，通过递推，获得规模为 i 的解。 递归型：把规模为N的问题分解成一些规模较小的问题，然后从这些小问题的解构造出大问题的解 。,38-26,穷举法举例,求解“百钱买百鸡”问题：公鸡每只5钱，母鸡每只3钱，小鸡3只1钱。求解思路：设公鸡数为x，母鸡数为y，小鸡数为z，则可以得到下面的整数不定方程组： 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量级，计算量太大，这正是穷举法的缺点。为此，可考虑对程序做优化。例如，针对“百钱买百鸡”问题，如果用所有的钱去买公鸡，最多可买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 ); 这个程序的循环次数只有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 = 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);/递归项递归算法简单，但不能无限递归。因此，算法中需要设置递归结束条件。,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;,更复杂的实例,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以后的区间逐个检查。,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 n ,38-38,插装 time( ) 后的计时程序为 double start, stop; time (可以测算。但受限于硬件设备和操作系统、编译器等，测算比较有一定困难。,38-39,算法的事前估计,空间复杂度度量存储空间的固定部分附加存储空间，常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占空间可变部分尺寸与问题规模有关的成分变量所占空间、递归栈所用空间、通过 malloc 和 free 命令动态使用空间,38-40,时间复杂度度量运行时间 = 算法每条语句执行时间之和。每条语句执行时间 = 该语句的执行次数 (频度)语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。,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 + 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 (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) = 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(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。算法的具体执行时间与计算机硬件的运行速度、编译产生的目标程序的质量有关，但这属于事后测量。算法的时间复杂度的度量属于事前估计，与问题的规模有关。,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. 下面说法中错误的是（ ）。 算法原地工作的含义是指不需要任何额外的辅助空间 在相同问题规模 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，算法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),计算*,