[理学]数据结构之第1章绪论.ppt

吾日三省吾身：为人谋而不忠乎？与朋友交而不信乎？传而不习乎？ 行有余力，则以学文？ 授课内容：第1章～第9章 及时、认真完成课后习题 预习并完成指定实验 上课不能迟到、早退和旷课 准备一个笔记本 成绩总评比例： 习题20% 实验20% 闭卷考试60% 1.1 数据结构的概念 1.2 抽象的数据类型 1.3 算法和算法分析 学习目标 掌握基本概念，特别是数据的逻辑和存储结构之间的关系。 理解抽象数据类型的定义、表示和实现方法。 明确算法的作用，并掌握算法时间复杂度估算方法。 Donald Knuth自传的开头这样写道： “Donald Knuth真的只是一个人么？”作为世界顶级计算机科学家之一，Knuth教授已经完成了编译程序、属性文法和运算法则的前沿研究，并编著完成了已在程序设计领域中具有权威标准和参考价值的书目的前三卷(《计算机程序设计艺术第1卷 基本算法》）。 程序是计算机处理问题编制一组指令集。 算法是处理问题的策略。 数据结构是解决问题的数学模型。 例1： 求一组（n个）整数中的最大值 算法：基本操作是“比较两个数的大小” 模型：线性表，数据的取值取决于整数值的范围 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 GB/T 11457-2006中定义算法为： 用有限步数求解某问题的一套明确定义的规则的集合。例如，求sin(x)到给定精度的一系列算术运算的顺序的完整规格说明； 为执行特定任务的任何运算序列。 算法具有五大特性： 输入 。有0个或多个输入； 输出 。有一个或多个输出； 确定性。 每步定义都是确切、无歧义的； 有穷性 。算法应在执行有穷步后结束； 可行性 。每一条运算应足够基本。 算法的性能标准包括： 正确性 能正确实现预定的功能和性能； 可使用性 能方便使用； 可读性 可理解、可测试和可修改； 效率 执行算法时计算机资源的消耗，包括时间代价和空间代价； 健壮性 对不同的输入能做出相应的响应。 一个特定算法的“运行工作量”的大小，依赖于：问题的规模（问题规模函数）；数据元素初始状态。 算法复杂度的度量属于事前估计，可分为： 时间复杂度度量：当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所耗费的时间也以某种单位由1增加到T(n)。 空间复杂度度量：当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的存储空间也以某种单位由1增加到S(n)。 存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间。 存储空间的可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间。 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作： T (n) = O(f(n)) T (n) 为算法的(渐近)时间复杂度 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。 设T(n)和f(n)是将非负整数映射为实数的函数。如果存在常数c0和整常数n0≥1对于每个n ≥n0，满足T(n) ≤c·f(n)，则称T(n)是O(f(n))。 这个定义长称为大O符号，因为有时它读作“T(n)是f(n)的大O”，或读作T(n)是f(n)阶的。 借助大O符号可以说，随着n趋向无穷（依据定义中的n ≥n0 )，在渐进意义上，n的一个函数“小于或等于”另一个函数（依据定义中的不等号） 的常数倍（依据定义中的常数c）。 程序分析法则： 简单的输入、输出和赋值语句，需要O(1)时间。 对于顺序结构，求一次执行时间用O的“求和法则”，即： T（n）=T1（n）+T2（n） =O（f1（n））+ O（f2（n）） =O（max（ f1（n）, f2（n）） ） 对于选择结构，时间耗费在then和else语句，检测条件还需O(1)时间。 对于循环结构，运行时间体现在多次迭代中执行循环体以及检验循环条件，用O的“乘法法则”，即： T（n）=T1（n）×T2（n） =O（f1（n））× O（f2（n）） =O（ f1（n）×f2（n） ） 对于复杂的