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

抽象数据类型、算法学习目的：*了解抽象数据类型的表示与实现;把握算法的特征和算法分析的方法。重点难点：算法的时间简洁度和空间简洁度的概念与分析。1.3抽象数据类型的表示和实现1.4算法和算法分析教学内容1.3抽象数据类型的表示和实现(P9)抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。本书承受类C语言，是C语言的一个核心子集。1.预定义常量和类型

//函数结果状态代码

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码typedefintStatus;类C介绍2.数据构造的表示〔存储构造〕用类型定义typedef描述。数据元素类型商定为ElemType，由用户在使用该数据类型时自行定义。typedefintStatus;3.根本操作的算法使用函数描述函数类型函数名〔参数表〕{//算法说明语句序列}//函数名

4.赋值语句a=1;a=b=c=1;a=b>10?c:d;5.选择语句if〔表达式〕语句；if〔表达式〕语句；else语句;switch(表达式){case值1：语句序列1；break;……case值n：语句序列n；break;default:语句序列n+1;}

6.循环语句for,while,do-while7.完毕语句函数完毕：return表达式；return；case完毕：break；特殊完毕：exit(特殊代码)；

8.输入输出语句scanf([格式串],变量〕;printf(([格式串],表达式);9.注释//,/*……*/10.根本函数max,min,abs,eof,eoln

11.规律运算商定&&：A&&BA为0时，不再对B求值||：A||BA为非0时，不再对B求值12.构造体struct构造体类型名{成员说明列表}；structstudent{intnum;charname[20];intage;};structstudentstu1;13.指针

int*p;//定义了一个指向整型变量的指针变量p*p//表示p指向的对象structstudent{intnum;charname[20];intage;}stu1,stu2;stu1.num=1111;typedefstruct{

floatrealpart；

floatimagpart；}complex；//存储构造的定义//根本操作的函数原型说明voidAssign(complex&Z,floatrealval,floatimagval)；//构造复数Z,其实部和虚局部别被赋以参数realval和imagval的值例

复数的实现float

GetReal(cpmplexZ)；

//返回复数Z的实部值float

Getimag(cpmplexZ)；

//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回两个复数z1,z2的和

//-----根本操作的实现voidadd(complexz1,complexz2,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){

c[i,j]=0;

for(k=1;k<=n;++k)

c[i,j]+=a[i,k]*b[k,j];

}

乘法运算是矩阵相乘问题的根本操作，整个算法的执行时间与该根本操作〔乘法〕重复执行的次数n3成正比。一般状况下，算法中根本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T〔n〕=O〔f(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表示〕，或者说，它是问题规模的函数。与待处理数据的初态无关。例4for(i=1;i<n;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)例5i=1;while(i<=n)i=i*2;频度1?设为x，则有：2x<=n,即x<=log2n,所以i=i*2的频度为log2nT(n)=O(log2n)例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)

一个算法的时间简洁度还可以具体分为最好、最差〔最坏〕、平均三种状况争论。最好状况下最简洁求出，但没有多大实际意义最差状况下也简洁求出，而且这是估量该算法执行时间的一个上界平均状况下最难计算：在很多状况下地输入数据集消逝的概率难以确定。一般，算法的时间简洁度如无特殊说明，则指最坏状况下的时间简洁度。4、算法的存储空间需求算法的空间简洁度定义为:S(n)=O(f(n))表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率一样。算法的存储量包括:1)输入数据所占空间2)程序本身所占空间3)帮助变量所占空间

假设输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的帮助变量所占额外空间。假设所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。假设所需存储量依靠于特定的输入，则通常按最坏状况考虑。

课堂总结

主要内容：了解抽象数据类型的表示与实现;把握算法的特征和算法分析的方法。重点难点：算法的时间简洁度和空间简洁度的概念与分析。作业：指出