Computer Science · An Overview · Chapter 8
数据抽象DATA ABSTRACTION
主存储器只是一排可寻址的单元——本章研究如何模拟出数组、栈、队列、树这样的结构，让数据的用户把它们当作抽象工具来访问，再进一步用抽象数据类型（ADT）和类把数据与操作打包成完整的类型。
主存储器只是一排可寻址的单元——本章研究如何模拟出数组、栈、队列、树这样的结构，让数据的用户把它们当作抽象工具来访问，再进一步用抽象数据类型（ADT）和类把数据与操作打包成完整的类型。
每节末尾附「本节小结」与 2 道课堂选择题（A / B / C / D），共 12 题，参考答案见页尾。一条主线：内存只有一排单元——所有数据结构都是模拟出来的抽象工具。
| 小节 | 核心问题 | 关键概念 |
|---|---|---|
| 8.1 基本数据结构 | 常用的数据组织方式有哪些？ | 数组 / 聚合 · 列表 · 栈 LIFO · 队列 FIFO · 树 |
| 8.2 相关概念 | 这些结构在内存里真实存在吗？ | 抽象与用户 · 静态 / 动态结构 · 指针 · 垃圾收集 |
| 8.3 数据结构的实现 | 抽象结构怎样落进主存储器？ | 邻接表 · 头 / 尾指针 · 环状队列 · 链式二叉树 |
| 8.4 案例研究 | 如何按字母顺序存储名字列表？ | 二叉搜索树 · 递归搜索 |
| 8.5 定制的数据类型 | 基本类型不够用怎么办？ | 用户定义类型 · 实例 · 抽象数据类型 ADT |
| 8.6 类和对象 | ADT 在面向对象里长什么样？ | 类是 ADT 的扩展 · 对象是实例 |
数据结构 data structure：在计算机内存中组织和存储数据的方式——选合适的数据结构可以显著提高程序的效率和性能。
数组 array：“矩形的”数据块，每一项具有相同的数据类型——例：24 小时的温度读数表。
聚合类型 aggregate type：数据项可以有不同类型和大小的块，各项称为字段 field——例：一条员工记录 = 姓名 + 年龄 + 技能级别。
列表 list：表项按顺序排列的集合。开头叫表头 head，结尾叫表尾 tail。
严格限制列表项的访问方式，就得到两种特殊列表：栈和队列。
栈 stack：项只能在表头（栈顶 top）添加和删除——入栈 push、出栈 pop。最后放入的最先移除，故称后进先出 LIFO。
栈常用于回溯 backtracking——退出顺序与进入顺序相反，像一摞盘子：最后放上去的最先被拿走。
队列 queue：项只能从表头移除，新项只能从表尾插入——按存储的顺序依次移除，故称先进先出 FIFO。
像排队买票：先来先服务。打印任务、消息缓冲都是队列的典型应用。
树 tree：项具有层次化组织形式的集合——例：公司组织结构图。树中每个位置叫节点 node；顶部是根节点 root node，端点处是终端节点 / 叶节点 leaf node；从根到叶子的最长路径上的节点数叫树的深度 depth。
直接后代 / 直接祖先 / 同一双亲的节点分别称为孩子 / 双亲 / 兄弟 children / parent / sibling。每个双亲的孩子都不超过两个的是二叉树 binary tree，提及时分左分支和右分支；任意节点与其下面的节点构成子树 subtree，每个孩子是其双亲下面一棵子树的根，称为一个分支 branch。
数组各项同类型，聚合各项可不同类型；栈在栈顶进出（LIFO，用于回溯），队列头出尾进（FIFO）；树 = 层次化的集合，根、叶、深度、孩子 / 双亲 / 兄弟、子树 / 分支是描述树的基本词汇，孩子不超过两个的是二叉树。一句话：栈像一摞盘子，队列像一条队伍——限制访问方式，就得到了可预期的行为。
主存储器并不是按数组、栈、队列、树来组织的——它只是一组可寻址的存储单元顺序组成，所有这些结构都必须被模拟。
数组、列表、栈、队列、树都是被创建的抽象工具：对数据的用户屏蔽实际存储的细节，让用户就像数据以方便的形式存储着一样来访问。
用户不一定是人——可能是客户机，也可能是程序中的任何模块 user = person / client / module。
主存单元由数字地址标识，地址本身也可编码存储。指针 pointer 就是包含这种编码地址的存储区，用来记录数据项的位置。
许多现代语言把指针作为基本数据类型——像整数一样可声明、分配和操作。
| 对比项 | 静态结构 static | 动态结构 dynamic |
|---|---|---|
| 判断依据 | 大小或形状不随时间改变 | 大小或形状会随时间改变 |
| 实现要求 | 只需提供访问（或许加修改）指定项的方法 | 要处理添加和删除项，还要找到增长所需的存储空间 |
| 管理难度 | 更容易管理 | 更复杂：伴随垃圾收集 garbage collection——回收不再使用的存储空间以备将来使用 |
所有数据结构都是模拟出来的抽象工具；用户（人或模块）享有按抽象方式访问数据的特权。静态结构只管访问，动态结构还要管增删与扩容；指针 = 存着地址的存储区，是链接结构的黏合剂；垃圾收集回收动态结构不再使用的空间。抽象的意义：换一个底层实现，用户的代码一行都不用改。
目标：理解处理这些结构的程序，如何被翻译成处理主存储器中数据的机器语言程序。
邻接表 contiguous list：整个列表存储在一大块存储单元中，连续的项依次放在相邻单元——适合顺序访问，但插入删除要挪动一片。
存栈：预留足够容纳最大栈的存储块，块底为栈底；用一个栈指针记录栈顶位置，push 时指针上移，pop 时下移。
每个节点 = 数据 + 左孩子指针 + 右孩子指针；专门的根指针 root pointer 存放根节点地址，对树的访问从根指针开始。
某方向没有节点时，对应指针赋 null（终端节点的两个指针都是 null）。另一种方案：连续存储块——单元 n 的左、右孩子分别存单元 2n 和 2n+1，一层接一层。
def PrintList(List): CurrentPointer = List.Head while CurrentPointer != None: print(CurrentPointer.Value) · 沿指针走向下一项
函数完成后就是一个抽象工具：用户只管调用 PrintList(Economics301)；以后改存储方式只需改函数内部，用户调用不变。
栈：一块存储 + 一个栈指针；队列：一块存储 + 头指针和尾指针，并以环状方式防止队列漂移出存储块；链式二叉树：节点 = 数据 + 左 / 右孩子指针，根指针指路，null 标记尽头，也可用 2n / 2n+1 规则连续存储。把存储细节包进函数，用户按抽象工具的方式下指令——指针微调 = 逻辑操作：移动一个指针，就完成了“出队”这个动作。
任务：对一个按字母顺序的名字列表，支持搜索 search、按序打印 print、插入 insert——开发一组函数构成完整的抽象工具。
每次比较都能排除一半的子树——和二分查找异曲同工，比在顺序列表里逐个翻找快得多。
“在子树中搜索”与“在整棵树中搜索”是同一个问题，只是规模更小——所以直接调用 Search 自己，代码简洁且与树的层次结构天然吻合。
def Search(Tree, TargetValue): if Tree is None: return None # 失败：走到空树 elif 目标 == Tree.Value: return Tree # 成功 elif 目标 < Tree.Value: 搜左子树 Search(Tree.Left, ...) elif 目标 > Tree.Value: 搜右子树 Search(Tree.Right, ...)
案例研究把本章串起来：选结构（二叉搜索树）→ 定存储（链式节点）→ 写函数（Search 递归）→ 得抽象工具。递归搜索的核心：与当前节点比较，小了去左子树、大了去右子树，空树则失败。好的数据结构 + 好的算法 = 又快又清晰的程序。
基本类型（整型 / 浮点型 / 字符型 / 布尔型）不够用？用它们作构建块，定义自己的类型——用户定义的数据类型 user-defined data type。
struct EmployeeType { char Name[25]; int Age; float SkillRating; }; struct EmployeeType DistManager, SalesRep1, SalesRep2; Employee1.Age = 26;
用户定义的数据类型本质上是构建实例的模板：模板描述所有实例共有的属性，但本身不是实例。EmployeeType 是模板，DistManager、SalesRep1、SalesRep2 是它的 3 个实例 instance。
只允许程序员定义新的存储系统，没有提供对这些数据进行的操作——而且程序里任何函数都能直接访问字段，绕开仔细检查，可能破坏结构的固有特征（比如栈的 LIFO）。
抽象数据类型 abstract data type（ADT）：同时包含数据（表示）和函数（行为）的用户定义数据类型。两大特征：① 定义为单个单元——语言提供语法把 ADT 的数据和函数组织在一起，简化维护和调试；② 隐藏内部结构——外部代码要访问数据，必须通过专门提供的函数，提供了可靠性。对比：用户定义类型只有数据；ADT 有数据 + 操作，因此是完整的数据类型。
interface StackType { public int pop(); // 取栈顶项 public void push(int item); // 入栈 public boolean isEmpty(); // 是否为空 public boolean isFull(); // 是否已满 }
interface 不指定栈如何存储、函数用什么算法——细节被抽象出来，由别处的代码实现；程序员照样可以把变量声明为 StackType 类型，用 StackOne.push(25) 这样的调用使用栈。
用户定义的数据类型 = 基本类型组合成的同名聚合体；用与基本类型相同的方式声明变量，用“变量.字段”访问各项；区分类型与实例：类型是模板，实例是按模板建的实例。ADT = 数据表示 + 操作函数，组织成单个单元并隐藏内部结构，外部只能通过规定好的函数访问——模板描述“有什么”，实例才是“那一个”，就像图纸与房子。
面向对象范型：系统由称为对象的单元组成，对象通过彼此交互完成任务；每个对象都是响应其他对象消息的实体，对象由称为类的模板描述。
class StackOfIntegers implements StackType { private int[] StackEntries = new int[20]; private int StackPointer = 0; public void push(int NewEntry) { ... } public int pop() { ... } public boolean isEmpty() { ... } public boolean isFull() { ... } } StackType StackOne = new StackOfIntegers(); StackOne.push(106); OldValue = StackOne.pop();
类 class 为 ADT（StackType）中声明的每个函数提供函数体，并包含实现所需的数据（数组 + 栈指针）——类的实例就称为对象 object。
特征与 ADT 本质上一样（数据 + 操作 + 隐藏），但类更进一步：支持继承 inheritance 等面向对象机制——所以说类是抽象数据类型的扩展。
对象是响应消息的实体，由类这个模板描述；类为 ADT 的每个函数提供实现，并私有地持有数据。类与 ADT 的区别：类是 ADT 的扩展——在数据 + 操作 + 隐藏之上，加入了继承等面向对象的能力。ADT 定契约（interface），类给实现（class），对象是干活的实例。
逐题一句话解析；错题请回到对应小节复习。速记：8.1→B C｜8.2→B B｜8.3→B B｜8.4→B D｜8.5→B C｜8.6→B B
Q1 B 栈的添加和删除只能在表头（栈顶）进行。
Q2 C 深度 = 根到叶子的最长路径上的节点数。
Q3 B “用户”取决于视角：人、客户机或程序模块都行。
Q4 B 指针存的是编码地址，用来记录数据项的位置。
Q5 B 环状队列让队列首尾相接，不再漂出存储块。
Q6 B 终端节点两个指针都为 null——下面没有孩子了。
Q7 B 目标更小 → 去左子树递归；更大 → 去右子树。
Q8 D 任务是搜索、按序打印、插入，没有“数笔画”。
Q9 B ADT 有数据 + 操作，是完整的数据类型。
Q10 C 类型是模板，DistManager 是按模板建的实例。
Q11 B 类在 ADT 之上加入继承等机制，是其扩展。
Q12 B 对象 = 响应消息的实体，由类模板描述。
内存只有一排可寻址单元——数组、栈、队列、树都是模拟出来的抽象工具；ADT 和类把数据与操作打包成完整类型。下一章预告：数据库系统。
| 小节 | 一句话总结 |
|---|---|
| 8.1 基本数据结构 | 数组同类型、聚合可混合；栈 LIFO、队列 FIFO；树分层 |
| 8.2 相关概念 | 结构都是模拟的抽象；静态易管、动态要收集垃圾；指针存地址 |
| 8.3 实现 | 栈一个指针、队列两个指针成环；二叉树链式或 2n / 2n+1 |
| 8.4 案例研究 | 二叉搜索树 + 递归搜索：小了往左、大了往右 |
| 8.5 定制类型 | 用户定义类型只有数据；ADT 数据 + 操作 + 隐藏 |
| 8.6 类和对象 | 类是 ADT 的扩展，对象是类的实例 |