《数据结构概述》PPT课件.ppt

《《数据结构概述》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构概述》PPT课件.ppt（39页珍藏版）》请在三一办公上搜索。

1、第二章 常用数据结构及其运算,1,计算机软件技术基础,上海大学通信与信息工程学院安 平,计算机基础教学课件,第二章 常用数据结构及其运算,2,学时数：40，其中习题课2学时。讲授主要内容：第2、3、4章自学内容：其余各章,课程的主要内容及安排,第二章 常用数据结构及其运算,3,常用数据结构及其运算,第二章,第二章 常用数据结构及其运算,4,内 容,21 概 述,22 线性表,23 栈与队,25 树与二叉树,26 图,27 查 找,28 排 序,第二章 常用数据结构及其运算,5,2.1 概 述,2.1.1 数据结构的概念,数值型与非数值型数据数值型：整型、实型、布尔型等非数值型：文献检索、金融管

2、理、商业系统 等数据处理,数据结构研究非数值运算的程序设计问题。数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。如线性关系、层次关系、网状关系等。,第二章 常用数据结构及其运算,6,2.1 概 述,数据(data)是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数值型和非数值型数据两类。,数据元素(data element)是数据的基本单位。如数据集合N= 1，2，3，4，5 中整数1至5均为数据元素。 数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。,3. 基本概念和术语,第

3、二章 常用数据结构及其运算,7,2.1 概 述,数据类型程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等 结构类型：变量值可分，如数组、结构体等,数据对象(data object)性质相同的数据元素的集合。如大写字母字符的数据对象是集合：C= A，B，.，Z 。,第二章 常用数据结构及其运算,8,2.1 概 述,数据结构(data structure)是指同一数据对象中各数据元素间存在的关系。,数据结构与算法 程序算法数据结构算法指解决特定问题的有限运算序列,第二章 常用数据结构及其运算,9,2.1 概 述,1.逻辑结构：研究数据元素及其关系的数学特

4、性， 即数据元素间的逻辑关系。二元组 S =（D，R） D数据元素的非空有限集合RD上关系的非空有限集合。,2.1.2 数据的逻辑结构和物理结构,第二章 常用数据结构及其运算,10,2.1 概 述,四类基本结构：,举 例,2.1.2 数据的逻辑结构和物理结构,第二章 常用数据结构及其运算,11,例1：linearity = (D, R)，其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , ,例2：Tree= (D, R)，其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , ,第二章 常用数据结构及其运算

5、,12,例4：S = (D, R)，其中D 1,2,3,4,5,6R = r1, r2r 1= , , , , r2=,例3：Graph= (D, R)，其中D 1,2,3,4,5; R = rr = , , , , ,第二章 常用数据结构及其运算,13,2.1 概 述,2.物理结构(存储结构)：是逻辑结构在计算机中的映象，即具体实现。四种基本存储结构：顺序存储结构 链式存储结构 索引存储结构 散列存储结构3.逻辑结构与存储结构的关系算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。同一种逻辑结构可采用不同的存储结构。,2.1.2 数据的逻辑结构和物理结构,第二章 常用数据结

6、构及其运算,14,2.1 概 述,2.1.3 算法与算法分析一、什么是算法, 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。 算法的五个特征：有穷性、确定性、可行性、 输入、输出 算法描述：采用类C语言的形式，有时也用自然语言。注释部分用/或/*.*/表示。,第二章 常用数据结构及其运算,15,2.1 概 述,2.1.3 算法与算法分析,二、算法设计的要求：正确性、健壮性、效率与低存储三、算法评价标准：时间复杂度、空间复杂度一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在时间和空间两方面的消耗多少作为评价该

7、算法优劣的标准。 度量一个程序的执行时间通常有两种方法： 事后统计和事前分析估算着重介绍第二种方法。（算法、问题规模、语言、机器代码质量、机器执行指令的速度）,第二章 常用数据结构及其运算,16,2.1 概 述,一、时间复杂度1. 频度：指一条语句重复执行的次数。记作：F(n)2. 算法的时间度量：T(n)=O(F(n)是问题规模 n 的某个函数F(n),称为算法的渐进时间复杂度或时间复杂度。例：T(n)=3n2 + 2n, 则 T(n)=O(n2) T(n)=3n + 2n,则 T(n)=O(3n),2.1.4 算法分析技术初步,第二章 常用数据结构及其运算,17,2.1 概 述,“+x”的

8、语句频度及三段程序的时间复杂度：(a) (b) (c)F(n): 1 n n2T(n): O(1) O(n) O(n2),2.1.4 算法分析技术初步,例: (a) +x;s=0 (b) for (i=1;i=n;+i) +x;s+=x; (c) for (j=1;j=n;+j)for (k=1;k=n;+k) +x;s+=x;,第二章 常用数据结构及其运算,18,问题 ？有A、B两段程序同时运行，在某时刻A的运行速度是B的2倍，因此，A的算法复杂度比B低（即效率高）。,2.1 概 述,第二章 常用数据结构及其运算,19,2.1 概 述, 常见的时间复杂度 1）O(1)：常量型 2）O(n)、

9、O(n2)、.、O(nk)：多项式型 3）O(log2n)、O(2log2n)：对数型 4）O(2n)、O(en)：指数型按增长率排序，一般有：1) 3) 2) 4),2.1.4 算法分析技术初步,第二章 常用数据结构及其运算,20,2.1 概 述, 当难以精确计算基本操作执行次数（或语句频度）情况下，只需求出关于 n 的增长率或阶即可。 当难以确定各种输入数据集出现的概率时，平均时间复杂度也难以确定时，可用最坏的情况作为分析依据,2.1.4 算法分析技术初步,第二章 常用数据结构及其运算,21,2.1 概 述,例：求下列程序段的时间复杂度1. for (i=0; in; i+)2. for

10、(j=0; jn; j+)3. bij=0;4. for (k=0; kn; k+)5. bij=bij+aik*akj;6. ,2.1.4 算法分析技术初步,以执行次数最多的语句（第5句）进行计算： 语句频度为：F(n)=n3 时间复杂度：T(n)=O(F(n)=O(n3),第二章 常用数据结构及其运算,22,2.1 概 述,3. 程序运行时间计算方法 (1) 两条法则 加法法则若 T1(n)=O(F(n)， T2(n)=O(G(n)则： T1(n)+ T2(n) = max(O(F(n),O(G(n) 乘法法则：若 T1(n)=O(F(n)， T2(n)=O(G(n)则： T1(n) T2

11、(n) = O( F(n) (G(n) ),2.1.4 算法分析技术初步,第二章 常用数据结构及其运算,23,2.1 概 述,例：三个程序段执行时间分别为O(n)、O(n3)、O(nlogn)则 T(n)= max(O(n),O(n3),O(nlogn)= O(n3),2.1.4 算法分析技术初步,加法法则特例：某两步的运行时间分别为 O(F(n)、O(G(n)其中 F(n)= n4, n为偶数； G(n)= n2, n为偶数 = n2, n为奇数； G(n)= n3, n为奇数,则总运行时间：T(n)= O(n4), 当n为偶数时；= O(n3), 当n为奇数时；,第二章 常用数据结构及其运

12、算,24,2.1 概 述,2.1.4 算法分析技术初步,(2) 常用的六条分析规则： 1)每个赋值语句或读/写语句的运行时间通常是O(1)。例外情况：赋值语句的右部表达式出现函数调用，此时要考虑计算函数值所耗费的时间 2)一个序列语句的运行时间由加法法则确定，即为该序列中耗时最多的语句的运行时间。,第二章 常用数据结构及其运算,25,2.1 概 述,2.1.4 算法分析技术初步,3) if(),S语句：执行时间为条件测试时间(O(1)分支语句S的执行时间。if(),S1 条件测试(O(1)+ S1和S2中运行时else S2 间较大者。,4) 循环语句的运行时间：是n次重复执行循环体所耗 时间

13、的总和。（应用乘法法则）即：执行一次循环体时间的最大值循环次数每次执行循环体的时间 = 循环体本身运行时间计算循环参数及测试时间（通常为O(1)）。多层循环：由内层外层逐层分析,第二章 常用数据结构及其运算,26,2.1 概 述,2.1.4 算法分析技术初步,5) 过程调用语句：a.非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。b.递归调用：可先对递归过程设一特定的运行时间 函数T(n)，根据过程递归调用的情况，得到T(n) 的一个递推关系。 6) go to 语句：可以最坏情况进行计算，即在遇到向下转移的go to 语句时，可认为go to 语句所引起的控制转移根本没有发生；

14、当遇到向上转移的go to 语句时，则必须考虑它对程序运行时间的影响。,第二章 常用数据结构及其运算,27,2.1 概 述,4. 时间复杂度计算举例,2.1.4 算法分析技术初步,例1： (1) for ( i=1; i=i+1; -j ) (3) if ( Aj-1Aj ) (4)temp = Aj-1;(5)Aj-1=Aj;(6)Aj=temp; ,分析：(4)(6): O(1)(3)(6): O(1)(2)(6): O(1(n-i) = O(n-i)(1)(6): T(n)=O(n2),第二章 常用数据结构及其运算,28,2.1 概 述,2.1.4 算法分析技术初步,例2：for ( i

15、=2 ; i= i ; -j) S ;,求“S”语句的频度及整个程序段的算法复杂度,分析：i=2：执行 n-1 次i=3：执行 n-2 次i=n-2；执行 3 次则：F(n) = 3+4+5+n-1 = (n-3)(n+2)/2 T(n) = O(n2),第二章 常用数据结构及其运算,29,2.1 概 述,2.1.4 算法分析技术初步,例3：i=1; While ( i=n) i=i*3 ;,求语句的频度及整个程序段的算法复杂度,分析：设句的频度为F(n)则：,T(n) = O(log3n),第二章 常用数据结构及其运算,30,2.1 概 述,2.1.4 算法分析技术初步,例4：prime(

16、int n ) / n为一正整数 int i=2 ; while ( n%i)!=0 ,求算法的复杂度,分析：设嵌套最深层语句“ i+”的频度为F(n),有：F(n)1.0sqrt(n)则,第二章 常用数据结构及其运算,31,2.1 概 述,2.1.4 算法分析技术初步,例5：x = n ; y = 0 ;while ( x = (y+1)(y+1) do y = y+1 ;,求语句的频度和整个程序段的算法复杂度,分析：F(n)F(n) = n,第二章 常用数据结构及其运算,32,2.1 概 述,2.1.4 算法分析技术初步,例6：w = 11 ; k= 21 ;while ( k 10 )

17、do if w 20 then w=w-10 ; k-elsew=w+10;,求语句的频度,分析：对每一合法k值，句执行2次则，句频度F(n)= (21-10)222,第二章 常用数据结构及其运算,33,2.1 概 述,2.1.4 算法分析技术初步,例7： x = 87 ; y = 10 ; while ( y 0 ) if ( x 100 ) x - = 10 ; y - - ; else x + + ;,求语句的频度和整个算法的复杂度。,分析：句频度F(n)= 15119114T(n)=O(1),第二章 常用数据结构及其运算,34,2.1 概 述,2.1.4 算法分析技术初步,例8：int

18、 fact ( int n)/ 计算n! (1)if ( n=1)(2)fact=1;else(3)fact=n*fact(n-1) ; ,计算程序段的时间复杂度,第二章 常用数据结构及其运算,35,2.1 概 述,2.1.4 算法分析技术初步,例9：float p (n) int n; (1) if (n=1) return(n) ; (2) else return(p(n-1)+p(n-2);,计算程序段的时间复杂度,第二章 常用数据结构及其运算,36,2.1 概 述,二、空间复杂度 空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间（因为这些单元与算法无关），记作：

19、S(n) 时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于计算机硬件的发展，一般都有足够的内存空间，因此在分析中着重考虑时间的因素。,2.1.4 算法分析技术初步,第二章 常用数据结构及其运算,37,2.1 概 述,2.1.5 小结, 理解数据、数据元素、数据对象、逻辑结构和物理结构、数据类型、数据结构、算法等基本概念。 掌握频度、时间复杂度的计算。 了解空间复杂度。,第二章 常用数据结构及其运算,38,2.1 概 述,2.1.6 作业, 教材第101页习题中的2.4、2.5(1)(3)(5)、2.7(1)(3)(5) 为一个课题组定义一个数据结构。每组一位教师，13名研究生，16名本科生，关系是教师指导研究生，每名研究生指导12名本科生，画出该数据结构的逻辑结构图。 按增长率由小至大的顺序排列下列各函数：2100, (3/2)n, (4/3)n, nn, n3/2, n2/3, n1/2, n!, n, log2n, n/log2n, log22n, log2(log2n), nlog2n,nlog2n,第二章 常用数据结构及其运算,39,2.1 概 述,2.1.6 作业, 求语句的频度x=91 ; y=100 ;while (y0) if (x100) x - = 10 ; y-elsex+ ; ,本节结束，返回目录,