数据结构选讲83.ppt

数据结构选讲DATA STRUCTURE;课程内容： 计算机软件的基础知识———数据结构 课时安排： 数据结构——32学时 教 材： 严蔚敏，吴伟民. 数据结构. 北京：清华大学出版社，1997. 参考书： 数据结构习题与解析（C语言篇） 李春葆 数据结构题集 严蔚敏，吴伟民 数据结构算法与应用—C++语言描述 （英文版） Sartaj Sahni McGraw-Hill 机械工业出版社 ; 数据结构的基本概念 数据类型和抽象数据类型 C语言的数据类型 用C语言描述算法的注意事项 算法设计目标和算法效率度量;1.1 数据结构的基本概念 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = { 0, ?1, ?2, … } 学生数据对象:初等项（不可分割）、组合项（可再划分）;数据元素：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位） 数据类型：具有相同性质的计算机数据集合及在这个集合上的一组操作。 数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为： Data_Structure = {D, R} 其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。;数据结构依据视点的不同，分为数据逻辑结构和物理结构：;逻辑结构： 线性结构 非线性结构 物理结构： 顺序存储 链接存储 索引存储 散列存储;“学生”表格;“课程”表格;线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素);方法2：有序顺序存储，二分查找 ;方法3：部分有序，建立索引表 ;非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个;UNIX文件系统的系统结构图;;堆结构;图结构 网络结构;例：田径赛的时间安排问题;在解决问题时可能遇到的典型的逻辑结构（数据结构） 逻辑结构的存储映象（存储实现） 数据结构的相关操作及其实现。;1.2 数据类型和抽象数据类型;抽象数据和抽象数据类型 (ADTs: Abstract Data Types);ADT：抽象数据类型名数据对象：数据对象的定义数据关系：数据逻辑关系的定义基本操作：基本操作的定义;抽象数据类型;好的和坏的数据结构？ ;1.3 C语言的数据类型;1.4 用C语言编写算法的注意事项;1.5 算法设计目标和算法效率度量;算法有这样一些特点： 1、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。 2、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。 3、有零个或多个输入 4、有一个或多个输出 5、有效性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。例如：被零除的计算动作是不能被有效执行的。;设计算法的基本方法:把一个具体问题转变成一个算法 事例学习：选择排序问题 明确问题：非递减排序 解决方案：逐个选择最小数据 算法框架： for ( int i=0; in-2; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小的整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort ;性能分析与度量;分析评价算法时应考虑的因素： 1、正确性 在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。 2、复杂度 时间复杂度 3、简单性 4、最优性 算法A是最优的是指：在给定问题的所有算法中，A执行的进步运算次数最少 5、可读性 要求算法易于理解，便于分析 6、可修改可扩展性 如果问题P 的一个算法是A，为了解答一个与P类似的问题，希望对A稍做改动就可正确运行，如算法A满足这一点，则说A的可修改性好。;与算法效率有关的因素;求解同样一个问题可能会有许多不同的算法，如何评价这些算法的好坏呢？ 首先算法必须是正确的。此外还需考虑： 1、算法易于理解，易于编程（在计算机上实现） ，易于调试。 2、要求算法高效，节省时间与空间。 一个算法运行所需时间的长短、空间的大小具有非常重要的意义。 时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。 ;算法高效与算法易理解、易编程之间也有一种制约关系 这两个要求有时互相矛盾。