数据结构与 绪论 PPT .ppt

本章小结 与数据结构相关的几个名词概念 数据结构研究的内容： 数据的逻辑结构 数据的物理结构（存储结构） 在数据结构上的操作 抽象数据类型 算法分析：时间复杂度、空间复杂度 * * 存储结构的描述 存储结构的描述方法随编程环境的不同而不同，通常可用高级编程语言中提供的数据类型描述之。 例如，用一维数组类型描述顺序存储结构，用指针描述链式存储结构。 例如，定义日期为：　　typedef struct {　　　int y; 　　// 年号 Year　　　int m; 　　// 月号 Month　　　int d; 　　// 日号 Day　　} DateType; 　// 日期类型　　同样，此时对数据元素也要借用高级编程语言中的数据类型描述之。 7、数据类型（data type） 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 数据类型可分两类：原子类型和结构类型。 例如：在C语言中 原子类型：整型、实型、字符型等 结构类型：数组、结构体、联合等 9、抽象抽象数据类型 (Abstract Data Type简称ADT) 由用户定义，用以表示应用问题的数据模型 指一个数学模型以及定义在此数学模型上的一组操作。 例如：计算机拥有的整数类型。 它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 数据对象和数据关系的定义用伪码（不真正执行的符号）描述。 基本操作的定义格式为： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 基本操作有两种参数： 赋值参数只为操作提供输入值； 引用参数以打头， 除了可以提供输入值外，还将返回操作结果。 “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。 “操作结果” 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。 举例——抽象数据类型复数的定义： ADT Complex { 数据对象：D＝{e1,e2｜e1,e2∈RealSet } 数据关系：R1＝{e1,e2| e1是复数的实数部分, e2 是复数的虚数部分 } 基本操作： InitComplex( 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 假设: z1和z2是上述定义的复数，则Add(z1,z2,z3)操作的结果将得到z3=z1+z2 1.3抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 一、类C语言简要说明 (1) 预定义常量和类型： //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE —1 #define OVERFLOW —2 //Status是函数的类型，其值是函数结果状态代码 typedef int Status； (2)数据结构的表示(存储结构)用类型定义(typedef)描述。数据元素