基本概念和术语13抽象数据类型的表示与实现14算法和算

基本概念和术语13抽象数据类型的表示与实现14算法和算内容摘要：

008 007 学生间学号顺序关系 是一种线性结构关系 第 1章 绪论 学生基本情况登记表，记录了每个学生的学号、姓名、专业、政治、面貌，表中的记录是按学生的学号顺序排列的。 基本概念和术语 例 家族的族谱 :假设某家族有 10个成员 A， B， C， D， E， F， G， H， I， J，他们之间的血缘关系可以用如下图表示。 J I A C B D H G F E 第 1章 绪论 基本概念和术语 例 ① 顺序存储方法：数组 ②链接存储方法：指针 ③索引存储方法 ④散列存储方法 说明： • 同一逻辑结构的丌同存储结构，冠以丌同的数据结构名称。 如顺序表、链表、散列表。 • 运算丌同，数据结构也丌同。 如栈和队列。 更进一步，顺序栈、链栈、顺序队列、链队列。 第 1章 绪论 基本概念和术语 数据的存储结构 算法：数据运算的描述 数据结构：数据的逻辑结构和存储结构 算法 +数据结构 =程序 第 1章 绪论 基本概念和术语 数据结构及其讨论范畴 基本概念和术语 抽象数据类型的表示不实现 算法和算法分析 抽象数据型 Abstract Data Types（ ADT） [定义 ]： 抽象数据型是一个数学模型和在该模型 上定义的操作的集合 ADT特点： •降低了软件设计的复杂性； •提高了程序的可读性和可维护性； •程序的正确性容易保证 第 1章 绪论 抽象数据类型的表示与实现 在软件设计中，可以对哪三种丌同的对象进行抽象。 第 1章 绪论 抽象数据类型的表示与实现 第 1章 绪论 抽象数据类型的表示与实现 软件系统 数据结构 控制机能 操作过程 软件设计 抽象 软件设计是对 数据抽象、过程抽象和控制抽象。 抽象数据型的规格描述 完整性：反映所定义的抽象数据型的全部 特征； 统一性：前后协调，丌自相矛盾； 通用性：适用于尽量广泛的对象； 丌依赖性：丌依赖于程序设计语言。 语法：给出操作的名称、 I/O参数的数目和类型； 语义：由一组等式组成，定义各种操作的功能及相互之间的关系； 规格描述的两个方面 : 语法和语义 第 1章 绪论 抽象数据类型的表示与实现 抽象描述 → （高级语言）编写的程序 三条原则： ①符合规格描述的定义； ②有尽可能好的通用性； ③尽可能独立于程序的其它部分 自底向上不自顶向下相结合、由简单到复杂 第 1章 绪论 抽象数据类型的表示与实现 抽象数据型的实现 多层次抽象技术 抽象数据类型的形式描述 ADT = ( D， S， P ),其中： D 是数据对象。 S是 D 上的关系集。 P是 D 的基本操作集。 第 1章 绪论 抽象数据类型的表示与实现 数据类型和抽象数据类型 ① 抽象数据类型需要通过高级编程语言中已经实现的数据类型（通常称之谓固有数据类型）来实现； ② 抽象数据类型的实现包括数据结构的实现和操作的实现。 第 1章 绪论 抽象数据类型的表示与实现 抽象数据类型“复数”的定义为： ADT Complex { 数据对象： D = {e1,e2 | e1,e2 属于 RealSet } 数据关系： R1 = {e1,e2 | e1。