欢迎来到数据结构的世界！
在本章中，我们将探讨计算机如何组织数据。你可以这样想象：如果你的房间很凌乱，就很难找到你最喜欢的那双袜子。但如果你有抽屉柜、鞋架和洗衣篮，找东西就会变得轻而易举！数据结构（Data structures）就像我们在计算机内存中用来存储数据的“家具”，让我们能更有效地运用这些信息。
别担心，如果有些术语乍听之下让你感到陌生，不必紧张。看完这份笔记后，你会发现它们大多数都是基于简单的生活常识。
1. 静态与动态数据结构
在探讨具体的结构之前，我们需要先了解它们是如何增长的（或者是否会增长！）。
静态数据结构（Static Data Structures）：这类结构的大小是固定的。你在程序执行前就决定好所需的空间，且在程序执行期间无法改变。比喻：一个木制鸡蛋盒。无论你里面装了 1 颗还是 12 颗鸡蛋，它永远有 12 个格子。
动态数据结构（Dynamic Data Structures）：这类结构的大小可以随时增加或减少。如果你不知道会有多少数据，用它们就对了！比喻：派对的宾客名单。随着越来越多人的回复，你可以不断新增名字。
快速复习：静态结构大小固定，内存使用效率高，但若空间用尽会有风险；动态结构灵活，但管理内存需要消耗较多的处理能力。
2. 基础：数组、记录与元组
数组（Arrays）
数组是存储在一起的相同类型数据项的集合。每个项目都有一个索引（Index）（一个从 0 开始的数字），让我们可以轻松找到它。
- 一维数组：一个简单的列表。例如：[ "Apple", "Banana", "Cherry" ]
- 二维数组：就像网格或电子表格。你需要两个坐标来定位一个项目：[列, 行]。
- 三维数组：就像一栋大楼或一个魔方。你需要三个坐标：[层, 列, 行]。
常见错误：忘记了大多数编程语言的索引是从 0 而不是从 1 开始计数的！
记录（Records）与元组（Tuples）
元组：一组有序的数值，可以包含不同的数据类型（例如一个整数和一个字符串）。元组一旦创建，通常就无法更改（它们是不可变的）。例如：(12, "High Street", "London")。
记录：这与元组相似，但使用了具名字段（named fields）。例如：“学生”记录可能包含 ID、名（FirstName）和姓（Surname）等字段。 它就像数据库表格中的单行数据。
重点总结：数组适合存储相同类型的列表；记录与元组则用于将关于某个事物的各种不同详情组合在一起。
3. 堆栈与队列（抽象数据类型 ADT）
这些被称为抽象数据类型（Abstract Data Types, ADT）。这意味着我们更关心的是它们的运作方式，而非其底层如何实现。
堆栈（Stack，后进先出 LIFO）
堆栈是一种 LIFO 结构：后进先出（Last-In, First-Out）。
比喻：一叠晚餐碟子。最后放上去的那一个，一定会是第一个被拿走的。
操作：
- Push：将项目推入堆栈顶端。
- Pop：将顶端的项目移除。
- Peek：查看顶端项目而不将其移除。
- IsEmpty：检查堆栈是否为空。
队列（Queue，先进先出 FIFO）
队列是一种 FIFO 结构：先进先出（First-In, First-Out）。
比喻：排队搭巴士的人龙。先来排队的人，就能先上车。
操作：
- Enqueue：在队尾加入项目。
- Dequeue：从队头移除项目。
你知道吗？计算机使用堆栈来记住函数调用时的位置（即“调用堆栈 Call Stack”），并使用队列来管理打印任务！
4. 链表（Linked Lists）
链表是一种动态结构，其中每个项目（称为节点 Node）都“指向”下一个项目。想象一个寻宝游戏，每个线索都会告诉你下一个线索在哪里。
节点包含两个部分：
- 数据（Data）：实际的值（例如："Hello"）。
- 指针（Pointer）：下一个节点的内存地址。
最后一个节点指向 Null，这告诉计算机：“到这里就结束了！”
如何新增/移除：你不需要移动数据，只需要改变指针指向的位置即可。这就像切断一条链子，然后以不同的顺序将链环重新接起来。
5. 树与二叉搜索树（BST）
树（Tree）是一种层次结构。它以顶端的根（Root）节点开始，向下“分枝”到子节点（Child）。没有子节点的节点称为叶子（Leaves）。
二叉搜索树（Binary Search Trees, BST）
BST 是一种特殊的树，每个节点最多有两个子节点。它遵循一个严格的规则：
- 小于父节点的值会放到左边。
- 大于父节点的值会放到右边。
树的遍历（Traversing）：访问每个节点有两种主要方式：
- 广度优先搜索（Breadth-First）：在移动到下一层之前，你会先访问同一层的所有节点。（想象一下逐行扫描书籍的过程）。
- 深度优先搜索（后序遍历，Post-Order）：在“访问”节点之前，你会先尽可能深入一个分枝。在后序遍历中，你会先访问子节点，最后才访问父节点。
重点总结：BST 让搜索数据变得极快！每次你向左或向右移动，都会排除掉剩下一半的数据。
6. 图（Graphs）
图（Graph）是由线（称为边 Edges）连接的节点（称为顶点 Vertices）集合。
比喻：伦敦地铁图。每个车站是一个顶点，而轨道就是边。
图的类型：
- 有向图（Directed）：边有箭头（单行道）。
- 无向图（Undirected）：边没有方向（双向道）。
- 加权图（Weighted）：边有“成本”或“权重”（例如两城市之间的里程距离）。
常见错误：学生经常混淆树与图。记住：树只是一种特殊的图，它没有“环（cycles）”，且所有节点都连接到同一个根节点。
7. 哈希表（Hash Tables）
哈希表是为了实现“即时搜索”而设计的。与其搜索整个列表，我们使用哈希算法（Hashing Algorithm）来精确计算数据应该存储在哪里。
运作方式：
- 取出一笔数据（即键 Key）。
- 将其输入哈希函数（Hash Function）（一个数学公式）。
- 计算结果即为数据存储的索引（Index，即“地址”）。
复杂度：理想情况下，在哈希表中查找数据的时间复杂度为 \(O(1)\)，几乎是瞬间完成！
冲突（Collisions）：有时两个不同的键会计算出相同的索引，这就是冲突。计算机通常通过“溢出区”或“链地址法（chaining，在该索引处建立一个小型链表）”来处理这种情况。
总结检查清单
要在考试中取得好成绩，请确保你能做到：
- 解释静态与动态结构之间的区别。
- 绘制堆栈（Push/Pop）和队列（Enqueue/Dequeue）的图示。
- 描述链表如何利用指针保持连接。
- 应用左 < 父 < 右的规则来构建一个二叉搜索树。
- 识别图中的有向与无向边。
- 解释为什么哈希表的搜索速度如此之快。
如果这些内容看起来很多，不用担心。试着在纸上画出这些结构——当你能看见你正在构建的这些“家具”时，理解起来会容易得多！