数据结构语言描述耿国华第一章.ppt

3.赋值语句 对C语言作以下描述： （1）简单赋值 1）〈变量名〉=〈表达式〉 2） 〈变量〉++， 3） 〈变量〉- -， （2）串联赋值 〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉 * * 第三十一页，共七十八页，2022年，8月28日 对C语言作以下描述： （4）条件赋值 〈变量名〉=〈条件表达式〉？〈表达式1〉:〈表达式2〉 （3）成组赋值 (变量,变量2,变量3,…变量k〉=(表达式1,表达式2 ,表达式3,…表达式k) 〈数组名1〉[下标1][下标2]=〈数组名2〉[下标1][下标2] * * 第三十二页，共七十八页，2022年，8月28日 4.条件选择语句 对C语言作以下描述： if (表达式) 语句; if (表达式) 语句1; else 语句2; * * 第三十三页，共七十八页，2022年，8月28日 情况语句 switch (表达式） {case 判断值1: 语句组 1； break; case 判断值2: 语句组 2； break; …… case 判断值n: 语句组n; break; [default: 语句组； break;] } 对C语言作以下描述： * * 第三十四页，共七十八页，2022年，8月28日 对C语言作以下描述： 5.循环语句 for 语句 for (表达式1；表达式2；表达式3） {循环体语句；} * * 第三十五页，共七十八页，2022年，8月28日 while 语句 while (条件表达式） {循环体语句； } 对C语言作以下描述： do –while 语句 do { 循环体语句 }while (条件表达式） * * 第三十六页，共七十八页，2022年，8月28日 1.5 对算法作性能评价 评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 性能评价 有关数量关系计算 * * 第三十七页，共七十八页，2022年，8月28日 性能评价 定义： 对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。 问题规模N—对不同的问题其含义不同： 对矩阵是阶数； 对多项式运算是多项式项数； 对图是顶点个数； 对集合运算是集合中元素个数。 * * 第三十八页，共七十八页，2022年，8月28日 有关数量关系计算 数量关系评价体现在时间——算法在机器中所耗费时间。 数量关系评价体现在空间——算法在机器中所占存储量。 关于算法执行时间 语句频度 算法的时间复杂度 数据结构中常用的时间复杂度频率计数 最坏时间复杂度 算法的空间复杂度 * * 第三十九页，共七十八页，2022年，8月28日 关于算法执行时间 定义： 一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 分析： 不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。 * * 第四十页，共七十八页，2022年，8月28日 语句频度 定义： 语句频度是指该语句在一个算法中重复执行的次数。 例如： 两个矩阵相乘 算法语句 对应的语句频度 1 for（i=0；i n;i++） n 2 for （j=0；jn;j++） n2 3 {c[i][j]=0; n2 4 for (k=0;k n; k++) n3 c[i][j]=c[i][j]+a[i][k]*b[k][j]; n3 } 总执行次数：Tn=2n