什么是数据结构抽象数据类型及面向对象概念模板算法定义.ppt

定义： 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。 特性： 输入 输出 确定性 有穷性 有效性 1.4 算法定义 算法设计： 自顶向下，逐步求精 例：选择排序问题 算法框架： 初始值a[k] for ( int i = 0; i n-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[i], 交换a[i]与a[k]; } 细化程序：程序 SelectSort void selectSort ( int a[ ], const int n ) { //对n个整数a[0],a[1],…,a[n-1], 按非递减顺序排序 for ( int i = 0; i n-1; i++ ) { int k = i; //从a[i]检查到a[n-1], 找最小的整数, 在a[k] for ( int j = i+1; j n; j++ ) if ( a[j] a[k] ) k = j; //k指示当前找到的最小整数 int temp = a[i]; a[i] = a[k]; a[k] = temp; //交换a[i]与a[k] } } 四个层次： 程序不含语法错误; 程序对于几组输入数据能够得出满足规格说明要求的结果; 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果; 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。 1.5 算法性能分析与度量 正确性 可使用性 可读性 健壮性(鲁棒性) 效率 时间代价 空间代价 后期测试 事前估计 —— 空间复杂性度量 —— 时间复杂性度量 算法效率的度量： 一般算法在执行期间所需要的存储量应该包括以下3个部分： （1）输入数据所占用的空间 （2）程序代码所占用的空间 （3）辅助变量所占用的空间 算法空间复杂度度量 例1：求表达式a+b+b*c+(a+b-c)/(a+b)+4.0 float abc (float a, float b, float c ) { return a+b+b*c+(a+b-c)/(a+b)+4.0 } 例2: 以迭代方式求累加和 float sum ( float a[ ], const int n ) { float s = 0.0; for ( int i = 0; i n; i++ ) s += a[i]; return s; } 例3.递归实现累加和 float rsum(float a[ ],const int n) { if (n=0) return 0; else return rsum(a,n-1)+a[n-1] ) 空间复杂度是指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的存储空间也以某种单位由1增加到S（n）------P.27 运行时间 程序步 语法上或语义上有意义的一段指令序列 执行时间与实例特性无关 例如： 注释：程序步数为0 声明语句：程序步数为0 表达式：程序步数为1， return a+b+b*c 算法的时间复杂度度量 赋值语句 变量=表达式 循环语句（循环控制部分，执行语句） for(初始化语句;表达式1;表达式2)… while 表达式 do… do …while 表达式 switch 语句 if then 函数执行语句： 动态存储管理：new delete sizeof( ) 转移语句：continue,break,goto,return 例 以迭代方式求累加和的函数 行 float sum ( float a[ ], const int n ) 1 { 2 float s = 0.0; 3 for ( int i = 0; i n; i++ ) 4 s += a[i]; 5 return s; 6 } 程序步确定方法 ——插入计数全局变量count float sum ( float a[ ], const int n ) { float s = 0.0;