数据结构 02 向量.pdf

2.向量 2.向量 (a) 接口与实现 (a) 接口与实现 邓俊辉 邓俊辉 deng@tsinghua.edu.cn deng@tsinghua.edu.cn Abstract Data Type vs. Data Structure Abstract Data Type vs. Data Structure 抽象数据类型 = 数据模型 + 定义在该模型上的一组操作 抽象数据类型 = 数据模型 + 定义在该模型上的一组操作 数据结构 = 基于某种特定语言实现ADT的一整套算法 数据结构 = 基于某种特定语言实现ADT的一整套算法 区别与联系 区别与联系 抽象定义 具体实现 抽象定义 具体实现 外部的逻辑特性 内部的表示与实现 外部的逻辑特性 内部的表示与实现 操作语义 完整的算法 操作语义 完整的算法 一种定义 多种实现 一种定义 多种实现 不考虑时间复杂度 与时间复杂度密切相关 不考虑时间复杂度 与时间复杂度密切相关 不涉及数据的存储方式 要考虑数据的具体存储机制 不涉及数据的存储方式 要考虑数据的具体存储机制 Data Structures  Algorithms (Fall 2012), Tsinghua University 1 Application = Interface x Implementation Application = Interface x Implementation 在数据结构的具体实现与实际应用之间 在数据结构的具体实现与实际应用之间 ADT就分工与接口制定了统一的规范 ADT就分工与接口制定了统一的规范 实现: 高效率地兑现数据结构的ADT接口操作 //造汽车 实现: 高效率地兑现数据结构的ADT接口操作 //造汽车 应用: 便捷地通过操作接口使用数据结构 //开汽车 应用: 便捷地通过操作接口使用数据结构 //开汽车 按照ADT规范 按照ADT规范 信息隐蔽和数据封装，使用与实现得以分离 信息隐蔽和数据封装，使用与实现得以分离 高层算法设计者与底层数据结构实现者可高效地分工协作 高层算法设计者与底层数据结构实现者可高效地分工协作 前者可超脱于具体实现；后者只需将精力于具体环节的优化 前者可超脱于具体实现；后者只需将精力于具体环节的优化 不同的算法与数据结构可以任意组合，便于确定最优配置 不同的算法与数据结构可以任意组合，便于确定最优配置 每种操作接口只需实现一次，代码篇幅缩短，软件复用度提高 每种操作接口只需实现一次，代码篇幅缩短，软件复用度提高