Abstract Data Type

概述

概念

• data：数据，对客观事物的符号表示，在计算机科学中，指 所以能输入计算机中、并被计算机处理的符号总称
• data element：数据元素，数据基本单位，在计算机中通常 作为整体考虑
• data item：数据项，数据元素的组成部分
• data object：数据对象，性质相同的数据元素的集合，数据 的子集

Data Structure

数据结构：相互直接存在一种或多种特定关系的数据元素的集合

• 使用基本类型不断组合形成的层次结构
• 某种意义上，数据结构可以看作是一组具有相同结构的值

$$Data_Structure = (D, S)$$

• $D$：数据元素有限集
• $S$：结构/关系有限集，数据元素之间相互之间的逻辑关系

• 集合：结构中数据元素只有同属一个集合的关系

• 线性结构：结构中数据元素之间存在一对一关系

  • 存在唯一一个被称为“第一个”的数据元素
  • 存在唯一一个被称为“最后一个”的数据元素
  • 除第一个外，每个数据元素均只有一个前驱
  • 除最后一个外，每个数据元素均只有一个后继

• 树型结构：结构中数据元素存在一对多关系

• 图状/网状结构：结构中数据元素存在多对多的关系

关系表示

• 逻辑结构：数据结构中描述的逻辑关系
• 物理/存储结构：数据结构在计算机中的表示（映像）

数据元素之间关系在计算机中映像/表示方法/存储结构

• 顺序映像：借助元素在存储器中的相对位置表示数据元素 之间的逻辑关系

  • 需要使用地址连续的存储单元依次存储数据元素
  • 所以需要静态分配空间，即给可能数据对象预分配空间 ，空间不够时只能重新分配
  • 由此得到顺序存储结构

• 非顺序/链式映像：借助指示元素存储地址的指针表示数据 元素之间的逻辑关系

  • 可以使用任意存储单元存储数据元素，另外存储一个指示 其直接后继的信息
  • 常用动态分配空间，即在需要创建数据对象时给其分配空间
  • 也可以静态分配空间，使用地址连续的存储单元存储数据 对象，此时指示元素可以是序号
  • 由此得到链式存储结构

• node：节点，数据元素信息、直接后继元素信息的存储映像
• 数据域：存储元素信息的域
• 指针域：存储直接后继位置的域

Data Type

数据类型：值的集合和定义在值集上的一组操作的总称

• atomic data type：原子类型，值不可分解
• fixed-aggregate data type：固定聚合类型，值由确定数目 的成分按某种结构组成
• variable-aggregate data type：可变聚合类型，值的成分 数目不确定
• 结构类型：固定、可变聚合类型的统称，值由若干成分按某种 结构组成，可分解，其成分可以是结构或非结构

  • 结构类型可以看作是由一种数据结构和定义在其上的一组 操作组成

• 在计算机中，每个处理核心（硬件、软件）都提供了一组原子 类型或结构类型
• 从硬件角度，引入数据类型是作为解释计算机内存中信息 含义的手段
• 对使用者而言，实现了信息的隐蔽

Abtract Data Type

ADT：抽象数据类型，一个数学模型已经定义在该模型上的 一组操作

$$Data_Type = (D, S, P)$$

• $D$：数据对象
• $S$：D上的关系集
• $P$：对D的基本操作集

• 根据其行为而不是其内部表示定义类型
• 实质上与数据类型是同一个概念，“抽象”的意义在于数据类型的 数学抽象特性
  • 或者说抽象数据类型范畴更广，包括自定义数据类型
• 抽象层次越高，含有该抽象数据类型的程序复用程度越高

面向对象

• ADT是面向对象编程的核心

• 将对象行为和其实现相分离，这也是面向对象编程的基本 技术

  • simplicity：简单性，隐藏细节方便理解
  • flexibility：灵活性，类通过对外行为被定义，可以 自由改变内部实现
  • security：安全性，扮演防火墙，确保实现、用户彼此 分离