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

1. 预定义常量和类型 //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status是函数的类型，其值是函数结果状态代码 typedef int Status; 2. 数据结构的表示（存储结构）用类型定义typedef 描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。 typedef int Status; 4. 赋值语句 a=1; a=b=c=1; a=b10?c:d; 6. 循环语句 for, while, do-while 9. 注释 // , /* …… */ 12. 结构体 struct 结构体类型名{ 成员说明列表 }； struct student{ int num; char name[20]; int age; }; struct student stu1; 4)效率与低存储量需求 效率指算法执行的时间，对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。 存储量需求指算法执行过程中所需要的最大存储空间。 这两者都与问题的规模有关。 一般情况下，算法中基本操作重复执行的次数是问题规模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;} 例4 for( i=1; in; i++) { y=y+1; for( j=0; j=2n; j++) x++; } 例5 i=1; while ( i=n ) i=i*2; 例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) {　　　　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) 一个算法的时间复杂度还可以具体分为最好、最差（最坏）、平均三种情况讨论。 最好情况下最容易求出，但没有多大实际意义 最差情况下也容易求出，而且这是估计该算法执行时间的一个上界 平均情况下最难计算：在很多情况下地输入数据集出现的概率难以确定。 一般，算法的时间复杂度如无特别说明，则指最坏情况下的时间复杂度。 课堂总结主要内容：了解抽象数据类型的表示与实现;掌握算法的特征和算法分析的方法。重点难点：算法的时间复杂度和空间复杂度的概念与分析。 作业： 指出下列程序段的时间复杂度（写出主要语句的频度） 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 ;