2-抽象数据类型的表示与实现、算法课件

*,*,2014-2-20,*,抽象数据类型、算法,学习目的：*了解抽象数据类型的表示与实现;把握算法的特征和算法分析的方法。,重点难点：算法的时间简洁度和空间简洁度的概念与分析。,1.3,抽象数据类型的表示和实现,1.4,算法和算法分析,教学内容,1.3,抽象数据类型的表示和实现,(P9),抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,本书承受类C语言，是C语言的一个核心子集。,1.,预定义常量和类型,/,函数结果状态代码,#define TRUE 1,#define FALSE 0,#define OK 1,#define ERROR 0,#define INFEASIBLE -1,#define OVERFLOW -2,/Status,是函数的类型，其值是函数结果状态代码,typedef int Status;,类,C,介绍,2.数据构造的表示存储构造用类型定义typedef 描述。数据元素类型商定为ElemType，由用户在使用该数据类型时自行定义。,typedef int Status;,3.根本操作的算法使用函数描述,函数类型 函数名参数表,/算法说明,语句序列,/函数名,4.,赋值语句,a=1;,a=b=c=1;,a=b10?c:d;,5.选择语句,if表达式 语句；,if表达式 语句；,else 语句;,switch(表达式),case 值1：语句序列1；break;,case 值n：语句序列n；break;,default:语句序列n+1;,6.,循环语句,for,while,do-while,7.完毕语句,函数完毕：return 表达式；,return；,case完毕：break；,特殊完毕：exit(特殊代码)；,8.输入输出语句,scanf(格式串,变量;,printf(格式串,表达式);,9.,注释,/,/*/,10.根本函数,max,min,abs,eof,eoln,11.规律运算商定,&：A&B A为0时，不再对B求值,|：A|B A为非0时，不再对B求值,12.构造体,struct 构造体类型名,成员说明列表,；,struct student,int num;,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;,typedef struct,float,realpart,；,float,imagpart,；,complex,；,/存储构造的定义,/根本操作的函数原型说明,void Assign(complex&Z,float realval,float imagval)；,/构造复数 Z,其实部和虚局部别被赋以参数realval 和 imagval 的值,例,复数的实现,float,GetReal(cpmplex Z),；,/,返回复数,Z,的实部值,float,Getimag(cpmplex Z),；,/,返回复数,Z,的虚部值,void,add(complex z1,complex z2,complex&sum),；,/,以,sum,返回两个复数,z1,z2,的和,/-根本操作的实现,void,add(complex z1,complex z2,complex&sum),/,以,sum,返回两个复数,z1,z2,的和,sum.realpart=z1.realpart+z2.realpart;,sum.imagpart=z1.imagpart+z2.imagpart;,其它省略,1.4,算法和算法分析,(P13),1,、算法,2,、算法设计的要求,3,、算法效率的度量,4,、算法的存储空间需求,算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。,算法的描述：本书中使用类C语言。,一个算法必需满足以下五个重要特性：,1),有穷性,2),确定性,3),可行性,4),输入,5),输出,1,、算法,1)有穷性 对于任意一组合法输入值，在执行有穷步骤之后确定能完毕，即：,算法中的每个步骤都能在有限时间内完成。,2)确定性 算法中每条指令必需有准确的含义，读者理解时不会产生二义性，并且在任何条件下，算法都只有唯一的一条执行路径，即对于一样的输入只能得出一样的输出。,3)可行性 算法中的全部操作都必需足够根本，都可以通过已经实现的根本操作运算有限次实现之。,4)输入 0个或多个输入。作为算法加工对象的量值，通常表达为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法外表上可以没有输入，实际上已被嵌入算法之中。,5)输出 一个或多个输出。它是一组与“输入”有确定关系的量值，是算法进展信息加工后得到的结果，这种确定关系即为算法的功能。,2,、算法设计的要求,设计算法时，通常应考虑到达以下目标：,1,),正确性,2,),可读性,3)强健性,4,),高效率与低存储量需求,1),正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“,正确,”的理解可以有以下四个层次：,a,程序中不含语法错误；,b程序对于几组输入数据能够得出满足要求的结果；,c程序对于细心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,d程序对于一切合法的输入数据都能得出满足要求的结果。,一般状况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。,2),可读性,算法主要是为了人的阅读与沟通，,其次才是为计算机执行，因此算法应当易于人的理解；另一方面，晦涩难读的程序易于隐蔽较多错误而难以调试。,3)强健性,当输入的数据非法时，算法应当恰当地作出反响或进展相应处理，而不是产生莫名奇异的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进展处理。,4),效率与低存储量需求,效率指算法执行的时间，对于同一个问题假设有多个算法可以解决，执行时间短的算法效率高。,存储量需求指算法执行过程中所需要的最大存储空间。,这两者都与问题的规模有关。,3,、算法效率的度量,通常有两种衡量算法效率的方法:,事后统计法,缺点：1必需执行程序；,2所得时间的统计量依靠于计算机的软硬件环境，会掩盖算法本质。,事前分析估算法：有误差，不准确，但是带来的效率高于它的误差。,和算法执行时间相关的因素有：,1算法所用“策略”；,2算法所解问题的“规模”；,3编程所用“语言”；,4“编译”的质量；,5执行算法的计算机的“速度”。,明显，同一个算法用不同的语言实现，或者用不同的编译程序进展编译，或者在不同计算机上运行，效率不同，这说明使用确定的时间单位衡量算法的效率是不适宜的，撇开这些与计算机软硬件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依靠于问题的规模-它是问题规模的函数。,算法=把握构造+原操作,简洁操作/固有数据类型的操作,为了便于比较同一问题的不同算法，通常从算法中选取一种对于所争论的问题来说是根本操作的原操作，以该根本操作在算法中重复执行的次数作为算法的时间量度。,如：for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k=n;+k)ci,j+=ai,k*bk,j;乘法运算是矩阵相乘问题的根本操作，整个算法 的执行时间与该根本操作乘法重复执行的次数n3成正比。,一般状况下，算法中根本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：,Tn=Of(n),它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率一样，称作算法的渐近时间简洁度，简称时间简洁度。,算法的时间简洁度计算,语句频度：语句重复执行的次数,例,1,：,+x;s=0;,例,2,：,for(i=1;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表示，或者说，它是问题规模的函数。与待处理数据的初态无关。,例,4,for(i=1;in;i+),y=y+1;,for(j=0;j=2n;j+),x+;,频度,n-1,(n-1)(2n+1),T(n)=n-1+(n-1)(2n+1)=O(n,2,),例,5,i=1;,while(i=n),i=i*2;,频度,1,?,设为,x,，则有：,2,x,=n,即,x=log,2,n,所以,i=i*2,的频度为,log,2,n,T(n)=O(log,2,n),例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=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),一个算法的时间简洁度还可以具体分为最好、最差最坏、平均三种状况争论。,最好状况下最简洁求出，但没有多大实际意义,最差状况下也简洁求出，而且这是估量该算法执行时间的一个上界,平均状况下最难计算：在很多状况下地输入数据集消逝的概率难以确定。,一般，算法的时间简洁度如无特殊说明，则指最坏状况下的时间简洁度。,4,、算法的存储空间需求,算法的空间简洁度定义为:,S(n)=O(f(n),表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 f(n)的增长率一样。,算法的存储量包括:,1)输入数据所占空间,2)程序本身所占空间,3)帮助变量所占空间,假设输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的帮助变量所占额外空间。,假设所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。,假设所需存储量依靠于特定的输入，则通常按最坏状况考虑。,课堂总结主要内容：了解抽象数据类型的表示与实现;把握算法的特征和算法分析的方法。重点难点：算法的时间简洁度和空间简洁度的概念与分析。,作业：,指出以下程序段的时间简洁度写出主要语句的频度,1.int sum1(int n),int p=1,sum=0,i;,for(i=1;i=n;i+),p*=i;sum+=p;,return(sum);,2.int sum2(int n),int sum=0,i,j;,for(i=1;i=n;i+),p=1;,for(j=1;j=i;j+),p*=j;,sum+=p;,return(sum);,