抽象数据类型的表示与实现算法

1、抽象数据类型的表示与实现、算法,学习目的：了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。,重点难点：算法的时间复杂度和空间复杂度的概念与分析。,2014-2-20,1.3 抽象数据类型的表示和实现,1.4 算法和算法分析,教学内容,2014-2-20,1.3抽象数据类型的表示和实现(P9),抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 本书采用类C语言，是C语言的一个核心子集。,2014-2-20,类C介绍,1. 预定义常量和类型 /函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #defi

2、ne ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /Status是函数的类型，其值是函数结果状态代码 typedef int Status;,2014-2-20,2. 数据结构的表示（存储结构）用类型定义typedef 描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。 typedef int Status;,3.基本操作的算法使用函数描述 函数类型 函数名（参数表） /算法说明 语句序列 /函数名,2014-2-20,4. 赋值语句 a=1; a=b=c=1; a=b10?c:d;,5. 选择语句 if（表达式

3、） 语句； if（表达式） 语句； else 语句; switch(表达式) case 值1：语句序列1；break; case 值n：语句序列n；break; default:语句序列n+1; ,2014-2-20,6. 循环语句 for, while, do-while,7.结束语句 函数结束：return 表达式； return； case结束： break； 异常结束： exit(异常代码)；,8. 输入输出语句 scanf(格式串,变量）; printf(格式串,表达式);,2014-2-20,9. 注释 / , /* */,10.基本函数 max, min, abs, eof, e

4、oln,11. 逻辑运算约定 char name20; int age; ; struct student stu1;,13. 指针 int *p; /定义了一个指向整型变量的指针变量p *p / 表示p指向的对象,struct student int num; char name20; int age; stu1, stu2; stu1.num=1111;,2014-2-20,typedef struct float realpart； float imagpart； complex；,/存储结构的定义,/基本操作的函数原型说明,void Assign( complex i=n; +i)fo

5、r (j=1; j=n; +j) ci,j = 0;for (k=1; k=n; +k)ci,j += ai,k*bk,j;乘法运算是矩阵相乘问题的基本操作，整个算法 的执行时间与该基本操作（乘法）重复执行的次数n3成正比。,2012-8-20,一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作： T（n）=O（f(n)） 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。,2012-8-20,算法的时间复杂度计算,语句频度：语句重复执行的次数 例1： +x;s=0; 例2： for(i=1;

6、i=n;+i) +x;s+=x; 例3： for(j=1;j=n;+j) for(k=1;k=n;+=k) +x;s+=x;,含基本操作“x增1”的语句的频度分别为1, n, n2 则这3个程序段的时间复杂度分别为O(1),O(n),O(n2),分别称为常量阶、线性阶、平方阶。 我们总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长（最坏情况下估算算法执行时间的一个上界） 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。与待处理数据的初态无关。,2012-8-20,例4 for( i=1; in; i+) y=y+1;

7、for( j=0; j=2n; j+) x+; ,频度,n-1,(n-1)(2n+1),T(n)=n-1+(n-1)(2n+1)=O(n2),2012-8-20,例5 i=1; while ( i=n ) i=i*2;,频度,1,?,设为x，则有：2x=n,即x=log2n,所以i=i*2的频度为log2n T(n)=O(log2n),2012-8-20,例6 两个 n n 的矩阵相乘。 void Mult_matrix( int c, int a, int b， int n)/ a、b 和 c 均为 n 阶方阵，且 c 是 a 和 b 的乘积for (i=1; i=n; +i)for (j=

8、1; j=n; +j) ci,j = 0;for (k=1; k=n; +k)ci,j += ai,k*bk,j;/ Mult_matrix 算法的时间复杂度为T(n)=O (n3),2012-8-20,一个算法的时间复杂度还可以具体分为最好、最差（最坏）、平均三种情况讨论。 最好情况下最容易求出，但没有多大实际意义 最差情况下也容易求出，而且这是估计该算法执行时间的一个上界 平均情况下最难计算：在很多情况下地输入数据集出现的概率难以确定。 一般，算法的时间复杂度如无特别说明，则指最坏情况下的时间复杂度。,2012-8-20,4、算法的存储空间需求,算法的空间复杂度定义为: S(n) = O(

9、f(n) 表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 f(n) 的增长率相同。 算法的存储量包括: 1)输入数据所占空间 2)程序本身所占空间 3)辅助变量所占空间,2012-8-20,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,2012-8-20,课堂总结主要内容：了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。重点难点：算法的时间复杂度和空间复杂度的概念与分析。,2012-8-20,作业：,指出下列程序段的时间复杂度（写出主要语句的频度） 1. int sum1( int n ) int p=1 , sum = 0 , i; for( i=1; i=n; i+) p*= i ; sum+= p ; retur