数据结构选讲datastructure

数据结构选讲datastructure内容摘要：

义： 抽象数据类型 好的和坏的数据结构。 如果一个 DS可以通过某种 “ 线性规则 ” 被转化为线性的DS（例如线性表），则称它为 好的 DS。 好的 DS通常对应于好的（高效的）算法。 这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如果没有线性化的结构逻辑上是不可计算的。 树是好的 DS—— 它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。 树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。 树的结构本质上有递归的性质。 2020/11/4 25 C语言的数据类型 基本数据类型 int short。 long。 unsigned float float。 double。 long double 指针类型 数组类型 字符串 结构体类型 共用体类型 枚举类型 自定义类型 用 C语言编写算法的注意事项 避免使用出现二义性的表达式 i++。 i = ++ i。 i = 1。 j = i + + + i。 避免使用转向语句 避免使用预处理 避免函数返回值隐含说明 算法设计目标和算法效率度量 定义： 一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： – 输入 有 0个或多个输入 – 输出 有一个或多个输出 (处理结果 ) – 确定性 每步定义都是确切、无歧义的 – 有穷性 算法应在执行有穷步后结束 – 有效性 每一条运算应足够基本 算法的描述 :c++,c,PASCAL等语言 2020/11/4 28 算法有这样一些 特点： 有穷性： 要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。 确定性： 算法中的每一个步骤都必须是确定的 ， 而不应当含糊 、 模棱两可。 有零个或多个输入 有一个或多个输出 有效性： 算法中的每一个步骤都应当能被有效的执行， 并得到确定的结果。 例如：被零除的计算动作是不能被有效执行的。  设计算法的基本方法 :把一个具体问题转变成一个算法  事例学习： 选择排序问题  明确问题： 非递减排序  解决方案： 逐个选择最小数据  算法框架： for ( int i=0。 in2。 i++ ) { //n1趟 从 a[i]检查到 a[n1]。 若最小的整数在 a[k], 交换 a[i]与 a[k]。 }  细化程序： 程序 SelectSort 算法设计 自顶向下，逐步求精 性能分析与度量 算法的性能标准 算法的后期测试 算法的事前估计 2020/11/4 31 分析评价算法时应考虑的 因素： 正确性 在给定有效的输入数据后 ， 算法经过有穷时间的计算能给出正确的答案。 复杂度 时间复杂度 简单性 最优性 算法 A是最优的是指：在给定问题的所有算法中， A执行的进步运算次数最少 可读性 要求算法易于理解 ， 便于。