Data structures and abstract data types

欢迎来到数据结构的世界！

在本章中，我们将探讨计算机是如何组织信息的。试想一下，如果你要在凌乱的衣柜里找一双特定的袜子，这简直是永无止境的折磨！但如果你把袜子放进抽屉，把衬衫挂好，把鞋子摆在鞋架上，找东西就变得轻而易举了。数据结构 (Data structures) 正是计算机世界里的“抽屉”与“架子”。它们能帮助我们有效地存储与管理数据，让程序运行得既快速又有条理。如果初次接触觉得有点抽象也别担心，我们会运用大量生活中的例子，让一切变得一目了然！

1. 什么是数据结构？

数据结构是一种用于组织、处理、检索与存储数据的特殊格式。你可以把它想象成将相关的数据项目归类在一起，以便更有效地使用它们。

现实类比： 图书馆就是一个巨大的数据结构。书本绝不会被随意扔在地上，而是按照类别、作者或杜威十进制图书分类法进行整理。这种“结构”让我们能在几分钟内，从成千上万本书中找到想要的那一本。

重点回顾：为什么我们需要它？

• 处理大量数据。
• 加快搜索信息的速度。
• 运用经过验证的方法，解决复杂的问题。

2. 数组：结构的基石

数组 (Array) 是最基本且最常见的数据结构之一。它是一组相同数据类型的元素，按顺序存储而成。

一维数组 (Single-Dimensional Arrays)

你可以把它想象成一个简单的清单。在一维数组中，你可以用来表示数学上的向量 (vector)。清单中的每一项都有一个索引（通常从 0 或 1 开始），让你能轻松找到它。

多维数组 (Multi-Dimensional Arrays)

二维数组就像一个网格或表格（包含行与列），在数学上常用用来表示矩阵 (matrix)。广义来说，n 维数组就是一组由 \(n\) 个整数组成的“元组 (tuple)”来进行索引的元素集合。

现实类比：
- 一维数组： 学校走廊上的一排储物柜。
- 二维数组： 电影院的座位表（F 行，12 号座）。

3. 字段、记录与文件

有时候，我们需要将不同类型的数据组合在一起。例如，如果你正在建立一个学生数据库，你可能需要姓名（字符串）、年龄（整数）和成绩（浮点数）。

• 字段 (Field)： 单一信息（例如：“学生姓名”）。
• 记录 (Record)： 相关字段的集合（例如：某位特定学生的所有数据）。
• 文件 (File)： 存储在计算机中的记录集合。

重要提示： 你需要学会如何读取与写入文本文件 (text files)（人类可读）以及二进制文件 (binary files)（计算机可读代码）。

4. 抽象数据类型 (ADTs)

这听起来很深奥，但其实是个非常有用的概念！抽象数据类型 (Abstract Data Type, ADT) 是一种从使用者角度定义其行为的数据结构。它告诉我们数据“做什么”，而不是在底层“如何编码”。

“汽车”类比： 当你开车时，你只需要操作方向盘和踏板（接口）。你不需要确切了解引擎如何燃烧燃料或齿轮如何转动（实现），就能让车子移动。ADT 的运作原理正是如此！

你需要掌握的关键 ADT：

• 队列 (Queue)： 就像店里的排队。最先进入的人最先获得服务（FIFO - 先进先出）。
• 栈 (Stack)： 就像堆叠餐盘。最后放上去的盘子，是第一个拿走的（LIFO - 后进先出）。
• 图 (Graph)： 由“节点”与连接它们的“边”组成的集合（就像伦敦地铁图）。
• 树 (Tree)： 数据的阶层结构（就像家谱或你电脑里的文件夹）。
• 哈希表 (Hash Table)： 一种存储数据的方式，让你通过“键 (key)”几乎能瞬间找到数据。
• 字典 (Dictionary)： 键值对的集合（就像真正的字典：单词 -> 定义）。
• 向量 (Vector)： 一种表示同时具有大小与方向的数学量的方式。

核心观念： ADT 让程序员能专注于程序的逻辑，而不必陷入内存管理的“繁琐细节”中。

5. 静态与动态数据结构

这是考试中的热门题目！数据结构可分为静态或动态。

静态数据结构 (Static Data Structures)

这类结构在程序启动时就有固定大小。
- 优点： 内存一次性分配，速度快且效率高。
- 缺点： 如果没用满会浪费内存；如果数据太多则会空间不足。

动态数据结构 (Dynamic Data Structures)

这些结构在程序运行时可以扩展或缩减。
- 优点： 仅使用实际需要的内存空间。
- 缺点： 编写程序较复杂，且因为计算机需要不断搜索新的内存空间，速度可能稍慢。

快速回顾框：
静态 (Static) = 固定大小（像木盒）。
动态 (Dynamic) = 灵活大小（像气球）。

6. 建立与维护数据

课程大纲要求你理解如何建立并维护特定的结构。我们会在后续章节深入探讨，但这里先提供一个“速查表”：

队列 (Queue)（线性、循环、优先级）

• 新增 (Add)： 将项目放到末端 (Enqueue)。
• 移除 (Remove)： 从前端取出项目 (Dequeue)。
• 满/空检查： 新增前务必检查空间是否足够，移除前检查是否有数据！

栈 (Stack)

• 推入 (Push)： 将项目加到顶端。
• 弹出 (Pop)： 从顶端移除项目。
• 查看 (Peek)： 查看顶端项目而不移除它。

哈希表 (Hash Table)

• 使用哈希算法 (hashing algorithm) 将“键”转为内存地址。
• 碰撞 (Collision)： 如果两个不同的键想要同一个地址怎么办？你需要处理方法（例如“再哈希”）。

栈与队列的记忆法：
- Stack = Stop（最后进去的是在顶部/停止的地方）。LIFO。
- Queue = Quick（最先进去的人很快就出去了）。FIFO。

最终重点整理

1. 数据结构只是存储数据的组织方式。
2. 数组是最基本的结构，且可以是多维的。
3. 抽象数据类型 (ADT) 专注于逻辑行为，而非物理代码。
4. 静态结构大小固定；动态结构则灵活可变。
5. 不同的结构（如栈与队列）用于不同的特定任务。

如果觉得要背的东西很多，不用担心！当你开始在自己的程序中使用它们时，这些概念就会变得像直觉一样自然。继续练习吧！