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

抽象数据类型、算法学习目的：*了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。重点难点：算法的时间复杂度和空间复杂度的概念与分析。1.3抽象数据类型的表示和实现1.4算法和算法分析教学内容1.3抽象数据类型的表示和实现(P9)

抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。本书采用类C语言，是C语言的一个核心子集。1.预定义常量和类型

//函数结果状态代码

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码

typedef

intStatus;类C介绍2.数据结构的表示（存储结构）用类型定义typedef

描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。

typedef

intStatus;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；//存储结构的定义//基本操作的函数原型说明void

Assign(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)辅助变量所占空间

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

课堂总结

主要内容：了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。重