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

2014-2-20抽象数据类型的表示与实现、算法学习目的：了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。重点难点：算法的时间复杂度和空间复杂度的概念与分析。2014-2-201.3抽象数据类型的表示和实现1.4算法和算法分析教学内容2014-2-201.3抽象数据类型的表示和实现(P9)抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。本书采用类C语言，是C语言的一个核心子集。2014-2-20类C介绍1.预定义常量和类型//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码typedefintStatus;2014-2-202.数据结构的表示（存储结构）用类型定义typedef描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。typedefintStatus;3.基本操作的算法使用函数描述函数类型函数名（参数表）{//算法说明语句序列}//函数名2014-2-204.赋值语句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;}2014-2-206.循环语句for,while,do-while7.结束语句函数结束：return表达式；return；case结束：break；异常结束：exit(异常代码)；8.输入输出语句scanf([格式串],变量）;printf(([格式串],表达式);2014-2-209.注释//,/*……*/10.基本函数max,min,abs,eof,eoln11.逻辑运算约定&&：A&&BA为0时，不再对B求值||：A||BA为非0时，不再对B求值2014-2-2012.结构体struct结构体类型名{成员说明列表}；structstudent{intnum;charname[20];intage;};structstudentstu1;13.指针int*p;//定义了一个指向整型变量的指针变量p*p//表示p指向的对象structstudent{intnum;charname[20];intage;}stu1,stu2;stu1.num=1111;2014-2-20typedefstruct{floatrealpart；floatimagpart；}complex；//存储结构的定义//基本操作的函数原型说明voidAssign(complex&Z,floatrealval,floatimagval)；//构造复数Z,其实部和虚部分别被赋以参数realval和imagval的值例复数的实现。2014-2-20floatGetReal(cpmplexZ)；//返回复数Z的实部值floatGetimag(cpmplexZ)；//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；//以sum返回两个复数z1,z2的和2014-2-20//-----基本操作的实现voidadd(complexz1,complexz2,complex&sum){//以sum返回两个复数z1,z2的和sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}{其它省略}2012-8-201.4算法和算法分析(P13)1、算法2、算法设计的要求3、算法效率的度量4、算法的存储空间需求2012-8-20算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。算法的描述：本书中使用类C语言。一个算法必须满足以下五个重要特性：1)有穷性2)确定性3)可行性4)输入5)输出1、算法2012-8-201)有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2)确定性算法中每条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法都只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。2012-8-203)可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4)输入0个或多个输入。作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。2012-8-205)输出一个或多个输出。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。2012-8-202、算法设计的要求设计算法时，通常应考虑达到以下目标：1)正确性2)可读性3)健壮性4)高效率与低存储量需求2012-8-201)正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；d．程序对于一切合法的输入数据都能得出满足要求的结果。一般情况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。2012-8-202)可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。2012-8-203)健壮性当输入的数据非法时，算法应当恰当地作出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。2012-8-204)效率与低存储量需求•效率指算法执行的时间，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。•存储量需求指算法执行过程中所需要的最大存储空间。•这两者都与问题的规模有关。2012-8-203、算法效率的度量通常有两种衡量算法效率的方法:事后统计法缺点：1．必须执行程序；2．所得时间的统计量依赖于计算机的软硬件环境，会掩盖算法本质。事前分析估算法：有误差，不确切，但是带来的效率高于它的误差。2012-8-20和算法执行时间相关的因素有：1）算法所用“策略”；2）算法所解问题的“规模”；3）编程所用“语言”；4）“编译”的质量；5）执行算法的计算机的“速度”。显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同计算机上运行，效率不同，这表明使用绝对的时间单位衡量算法的效率是不合适的，撇开这些与计算机软硬件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模-它是问题规模的函数。2012-8-20算法=控制结构+原操作（简单操作//固有数据类型的操作）为了便于比较同一问题的不同算法，通常从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法的时间量度。如：for(i=1;i=n;++i)for(j=1;j=n;++j){c[i,j]=0;for(k=1;k=n;++k)c[i,j]+=a[i,k]*b[k,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;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例4for(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(n2)2012-8-20例5i=1;while(i=n)i=i*2;频度1?设为x，则有：2x=n,即x=log2n,所以i=i*2的频度为log2nT(n)=O(log2n)2012-8-20例6两个n×n的矩阵相乘。voidMult_matrix(intc[][],inta[][],intb[][]，intn){//a、b和c均为n阶方阵，且c是a和b的乘积for(i=1;i=n;++i)for(j=1;j=n;++j){c[i,j]=0;for(k=1;k=n;++k)c[i,j]+=a[i,k]*b[k,j];}}//Mult_matrix算法的时间复杂度为T(n)=O(n3)2012-8-20一个算法的时间复杂度还可以具体分为最好、最差（最坏）、平均三种情况讨论。•最好情况下最容易求出，但没有多大实际意义•最差情况下也容易求出，而且这是估计该算法执行时间的一个上界•平均情况下最难计算：在很多情况下地输入数据集出现的概率难以确定。一般，算法的时间复杂度如无特别说明，则指最坏情况下的时间复杂度。2012-8-204、算法的存储空间需求算法的空间复杂度定义为:S(n)=O(f(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。算法的存储量包括:1)输入数据所占空间2)程序本身所占空间3)辅助变量所占空间2012-8-20若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。2012-8-20课堂总结主要内容：了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。重点难点：算法的时间复杂度和空间复杂度的概念与分析。2012-8-20作业：指出下列程序段的时间复杂度（写出主要语句的频度）1.intsum1(intn){intp=1,sum=0,i;for(i=1;i=n;i++){p*=i;sum+=p;}return(sum);}2012-8-202.intsum2(intn){intsum=0,i,j;for(i=1;i=n;i++){p=1;for(j=1;j=i;j++)p*=j;sum+=p;}return(sum);}