《数据结构》课件1第1章 绪论.ppt

若输入数据所占空间只取决于问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。 若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入， 则通常按最坏情况考虑。 注意： 算法分析中最主要的三点是： 时间复杂度； 空间复杂度； 算法本身的复杂度。 学习总结 　　1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 　　2. 了解抽象数据类型的定义、表示和实现方法。 　　3. 熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。 　　4. 理解算法五个要素的确切含义和对算法正确性的理解。 　　　5. 掌握计算语句频度和估算算法时间复杂度的方法 《数据结构实例解析与实验指导》书中 P12/四(3) P13/四(9) 作业： * * * 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 二、数据类型 其实数据类型反映三个方面的内容：存储结构，取值范围和能进行的操作。 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。 三、抽象数据类型 抽象数据类型的形式描述: ADT=（D，R，P） 其中：D 是数据对象； R 是 D 上的关系集； P 是对 D 的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 赋值参数 只为操作提供输入值。 引用参数 以打头，除可提供输入值外， 还将返回操作结果。 初始条件 描述了操作执行之前数据结构 和参数应满足的条件，若不满足，则 操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数 据结构的变化状况和应返回的结果。 若初始条件为空，则省略之。 例如，(参看书P9/例1-6） 抽象数据类型复数的定义： 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R＝{e1,e2 | e1是复数的实数部分 | e2 是复数的虚数部分 } ADT Complex { 基本操作： AssignComplex( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。 DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 } ADT Complex 抽象数据类型的表示和实现 存储结构需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数。 typedef struct { float realpart； float imagpart； }complex； // -----存储结构的定义 // -----基本操作的函数原型说明 void Assign( complex Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值 float GetReal( complex Z )； // 返回复数 Z 的