《(2020年){技术管理套表}计算机软件技术基础数据结构及算法概述线性表》由会员分享，可在线阅读，更多相关《(2020年){技术管理套表}计算机软件技术基础数据结构及算法概述线性表（80页珍藏版）》请在金锄头文库上搜索。
1、常用数据结构及其运算,第三章,1,3.1 概述 3.2 线性表 3.3 栈与队 3.4 树与二叉树 3.5 图 3.6 查找与排序,目录,2,3.1 概 述,3.1.1 数据结构的概念 3.1.2 数据的逻辑结构和物理结构 3.1.3 算法与算法分析 3.1.4 算法分析技术初步 3.1.5 小结,3,3.1.1 数据结构的概念,数值型与非数值型数据 数值型：整型、实型、布尔型等 非数值型：文献检索、金融管理、商业系统 等数据处理,数据结构 研究非数值运算的程序设计问题。 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 如线性关系、层次关系、网状关系等。,4,数据(data)是信
2、息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数值型和非数值型数据两类。,数据元素(data element)是数据的基本单位。如数据集合N= 1，2，3，4，5 中整数1至5均为数据元素。 数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。,3. 基本概念和术语,3.1.1 数据结构的概念,5,数据类型程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分， 如整型、实型、字符型等 结构类型：变量值可分，如数组、结构体等,数据对象(data object)性质相同的数据元素的集
3、合。如大写字母字符的数据对象是集合：C= A，B，.，Z 。,3.1.1 数据结构的概念,6,数据结构(data structure)是指同一数据对象中各数据元素间存在的关系。,数据结构与算法 程序算法数据结构 算法指解决特定问题的有限运算序列,3.1.1 数据结构的概念,7,1.逻辑结构：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。 二元组 S =（D，R） D数据元素的非空有限集合 RD上关系的非空有限集合。,3.1.2 数据的逻辑结构和物理结构,8,四类基本结构：,举 例,3.1.2 数据的逻辑结构和物理结构,9,例1：linearity = (D, R)，其中 D 1,2
4、,3,4,5,6,7,8,9,10 R = r r = , , , , , , , , ,例2：Tree= (D, R)，其中 D 1,2,3,4,5,6,7,8,9,10 R = r r = , , , , , , , , ,3.1.2 数据的逻辑结构和物理结构,10,例4：S = (D, R)，其中 D 1,2,3,4,5,6 R = r1, r2 r 1= , , , , r2=,例3：Graph= (D, R)，其中 D 1,2,3,4,5; R = r r = , , , , ,3.1.2 数据的逻辑结构和物理结构,11,2.物理结构(存储结构)：是逻辑结构在计算机中的映象，即具体实
5、现。 四种基本存储结构：顺序存储结构 链式存储结构 索引存储结构 散列存储结构 3.逻辑结构与存储结构的关系 算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。 同一种逻辑结构可采用不同的存储结构。,3.1.2 数据的逻辑结构和物理结构,12,一、什么是算法, 算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。 算法的五个特征：有穷性、确定性、可行性、 输入、输出 算法描述：采用类C语言的形式，有时也用自然语言。注释部分用/或/*.*/表示。,3.1.3 算法与算法分析,13,二、算法设计的要求：正确性、健壮性、效率与低存储 三、算法评价标
6、准：时间复杂度、空间复杂度 一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法： 事后统计和事前分析估算着重介绍第二种方法。（算法、问题规模、语言、机器代码质量、机器执行指令的速度）,3.1.3 算法与算法分析,14,一、时间复杂度 1. 频度：指一条语句重复执行的次数。记作：F(n) 2. 算法的时间度量：T(n)=O(F(n) 是问题规模 n 的某个函数F(n),称为算法的渐进时间复杂度或时间复杂度。 例：T(n)=3n2 + 2n, 则 T(n)=O(n
7、2) T(n)=3n + 2n,则 T(n)=O(3n),3.1.4 算法与分析技术初步,15,“+x”的语句频度及三段程序的时间复杂度： (a) (b) (c) F(n): 1 n n2 T(n): O(1) O(n) O(n2),例: (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;,3.1.4 算法与分析技术初步,16,问题 ？ 有A、B两段程序同时运行，在某时刻A的运行速度是B的2倍，因此，A的算法复杂度比B低（即效率高）。,3.1.4 算法与分析技术初步,17
8、, 常见的时间复杂度 1）O(1)：常量型 2）O(n)、O(n2)、.、O(nk)：多项式型 3）O(log2n)、O(2log2n)：对数型 4）O(2n)、O(en)：指数型 按增长率排序，一般有：1) 3) 2) 4),3.1.4 算法与分析技术初步,18, 当难以精确计算基本操作执行次数（或语句频度）情况下，只需求出关于 n 的增长率或阶即可。 当难以确定各种输入数据集出现的概率时，平均时间复杂度也难以确定时，可用最坏的情况作为分析依据,3.1.4 算法与分析技术初步,19,例：求下列程序段的时间复杂度 1. for (i=0; in; i+)2. for (j=0; jn; j+)
9、3. bij=0;4. for (k=0; kn; k+)5. bij=bij+aik*akj;6. ,以执行次数最多的语句（第5句）进行计算： 语句频度为：F(n)=n3 时间复杂度：T(n)=O(F(n)=O(n3),3.1.4 算法与分析技术初步,20,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(n) = O( F(n) (G(n) ),3.1.4 算法与
10、分析技术初步,21,例：三个程序段执行时间分别为O(n)、O(n3)、O(nlogn) 则 T(n)= max(O(n),O(n3),O(nlogn)= O(n3),加法法则特例：某两步的运行时间分别为 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为奇数时；,3.1.4 算法与分析技术初步,22,(2) 常用的六条分析规则： 1)每个赋值语句或读/写语句的运行时间通常是O(1)。 例外情况：赋值语句的右部表达式出
11、现函数调用，此时要考虑计算函数值所耗费的时间 2)一个序列语句的运行时间由加法法则确定，即为该序列中耗时最多的语句的运行时间。,3.1.4 算法与分析技术初步,23,3) if(),S语句：执行时间为条件测试时间(O(1)分支语句S的执行时间。 if(),S1 条件测试(O(1)+ S1和S2中运行时 else S2 间较大者。,4) 循环语句的运行时间：是n次重复执行循环体所耗 时间的总和。（应用乘法法则） 即：执行一次循环体时间的最大值循环次数 每次执行循环体的时间 = 循环体本身运行时间计算循环参数及测试时间（通常为O(1)）。 多层循环：由内层外层逐层分析,3.1.4 算法与分析技术初
12、步,24,5) 过程调用语句： a.非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。 b.递归调用：可先对递归过程设一特定的运行时间 函数T(n)，根据过程递归调用的情况，得到T(n) 的一个递推关系。 6) go to 语句：可以最坏情况进行计算，即在遇到向下转移的go to 语句时，可认为go to 语句所引起的控制转移根本没有发生；当遇到向上转移的go to 语句时，则必须考虑它对程序运行时间的影响。,3.1.4 算法与分析技术初步,25,4. 时间复杂度计算举例,例1： (1) for ( i=1; i=i+1; -j ) (3) if ( Aj-1Aj ) (4)tem
13、p = 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),3.1.4 算法与分析技术初步,26,例2：for ( i=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),3.1.4 算法与分析技术初步,27,例3：i=1; Whi
14、le ( i=n) i=i*3 ;,求语句的频度及整个程序段的算法复杂度,分析：设句的频度为F(n) 则：,T(n) = O(log3n),3.1.4 算法与分析技术初步,28,例4：prime( int n ) / n为一正整数 int i=2 ; while ( n%i)!=0 ,求算法的复杂度,分析：设嵌套最深层语句“ i+”的频度为F(n), 有：F(n)1.0sqrt(n) 则,3.1.4 算法与分析技术初步,29,例5：x = n ; y = 0 ; while ( x = (y+1)(y+1) do y = y+1 ;,求语句的频度和整个程序段的算法复杂度,分析：F(n)F(n)
15、 = n,3.1.4 算法与分析技术初步,30,例6：w = 11 ; k= 21 ; while ( k 10 ) do if w 20 then w=w-10 ; k- elsew=w+10;,求语句的频度,分析：对每一合法k值，句执行2次 则，句频度F(n)= (21-10)222,3.1.4 算法与分析技术初步,31,例7： x = 87 ; y = 10 ; while ( y 0 ) if ( x 100 ) x - = 10 ; y - - ; else x + + ; ,求语句的频度和整个算法的复杂度。,分析：句频度F(n)= 15119114 T(n)=O(1),3.1.4
16、算法与分析技术初步,32,例8：int fact ( int n)/ 计算n! (1)if ( n=1) (2)fact=1; else (3)fact=n*fact(n-1) ; ,计算程序段的时间复杂度,3.1.4 算法与分析技术初步,33,例9：float p (n) int n; (1) if (n=1) return(n) ; (2) else return(p(n-1)+p(n-2); ,计算程序段的时间复杂度,3.1.4 算法与分析技术初步,34,二、空间复杂度 空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间（因为这些单元与算法无关），记作：S(n) 时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于计算机硬件的发展，一般都有足够的内存空间，因
