二、知识总结

✨ 核心思想

在计算机科学中，数据结构是存储和组织数据的方式，以便可以有效地访问和修改数据。根据组织数据的方式，数据结构主要可以分为线性数据结构、树形数据结构和图形数据结构。

✨ 线性数据结构

线性数据结构中的数据元素排列在一条线上。在这类数据结构中，每个数据元素最多只有一个前驱和一个后继。

常见的线性数据结构包括：

• 数组：一种固定大小的数据结构，用于存储元素的集合。这些元素都是相同类型的，并且可以通过索引快速访问。
• 链表：由节点组成，每个节点包含数据部分和一个或多个指向列表中其他节点的链接。链表可以是单向的、双向的或循环的。
• 栈：遵循后进先出（LIFO）原则的集合。只允许在集合的一端（顶部）进行添加和删除操作。
• 队列：遵循先进先出（FIFO）原则的集合。元素从队列的后端添加，从前端移除。

✨ 树形数据结构

树形数据结构是元素以分层方式组织的非线性数据结构，每个元素称为节点，每两个节点间的连接称为边。

常见的树形数据结构包括：

• 二叉树：每个节点最多有两个子节点（通常称为左子节点和右子节点）。
• 二叉搜索树（BST）：一种特殊的二叉树，其中每个节点都满足左子节点的值小于父节点的值，右子节点的值大于父节点的值。
• 平衡树（如AVL树、红黑树）：是特殊类型的BST，自动保持低高度，以确保操作的高效性。
• B树和B+树：通常用于数据库和文件系统中的索引结构。
• 堆：一种特殊的完全二叉树，其中每个节点的值都满足特定的顺序属性（如大顶堆或小顶堆）。

✨ 图形数据结构

图是一种复杂的数据结构，由一组顶点和一组连接顶点对的边组成。它用于表示多对多的关系。图可以是有向的（箭头显示连接方向）或无向的。

常见的图形数据结构和特性包括：

• 邻接矩阵和邻接列表：这两种结构分别用于图数据的存储和表示。
• 加权图和非加权图：图中的边可能包含权重（表示成本、距离等）。
• 有向图和无向图：边可以有或没有方向。

✨ 应用场景

不同数据结构适用于不同的场景：

• 线性数据结构常用于实现简单的数据集合和数据处理操作，如文本编辑器中的文本存储（链表）、撤销操作（栈）和打印任务管理（队列）。
• 树形数据结构适用于实现优先队列（堆）、数据库索引（B树、红黑树）和文件系统。
• 图形数据结构用于网络路由、社交网络分析、组织结构图和城市交通网络。

每种数据结构的选择都取决于特定应用的需求，例如数据元素的组织方式、数据的使用模式以及操作的效率要求。

✨ 执行示例

以一个实际场景来展示不同数据结构的操作特点。假设我们要管理一个待办事项列表：

用数组实现

1初始状态：["吃饭", "写作业", "跑步"]
2
3在末尾添加 "看书"：
4  → ["吃饭", "写作业", "跑步", "看书"]   O(1)
5
6在位置1插入 "洗衣服"：
7  → 先将位置1及之后的元素后移
8  → ["吃饭", "洗衣服", "写作业", "跑步", "看书"]   O(n)
9
10删除位置2的 "写作业"：
11  → 将位置3及之后的元素前移
12  → ["吃饭", "洗衣服", "跑步", "看书"]   O(n)
13
14访问位置0的元素：
15  → "吃饭"   O(1)，直接通过下标访问

用链表实现

1初始状态：头→[吃饭]→[写作业]→[跑步]→null
2
3在 "吃饭" 后插入 "洗衣服"：
4  → 只需修改两个指针
5  → 头→[吃饭]→[洗衣服]→[写作业]→[跑步]→null   O(1)（已知位置时）
6
7删除 "写作业"：
8  → 只需修改一个指针
9  → 头→[吃饭]→[洗衣服]→[跑步]→null   O(1)（已知位置时）
10
11访问第3个元素：
12  → 必须从头遍历：吃饭→洗衣服→跑步
13  → "跑步"   O(n)，需要逐个遍历

用栈实现（浏览器的后退功能）

访问页面A → 压栈：[A]
访问页面B → 压栈：[A, B]
访问页面C → 压栈：[A, B, C]
点击后退 → 弹栈：弹出C，回到B，栈变为 [A, B]
点击后退 → 弹栈：弹出B，回到A，栈变为 [A]

用队列实现（打印任务排队）

文件1请求打印 → 入队：[文件1]
文件2请求打印 → 入队：[文件1, 文件2]
文件3请求打印 → 入队：[文件1, 文件2, 文件3]
打印机处理   → 出队：处理文件1，队列变为 [文件2, 文件3]
打印机处理   → 出队：处理文件2，队列变为 [文件3]

✨ 解题步骤详解

选择合适的数据结构是解题的关键一步。遇到问题时，按以下思路分析：

1. 分析操作类型：题目主要涉及哪些操作？插入、删除、查找、还是排序？
2. 分析操作频率：哪些操作最频繁？选择对高频操作效率最优的数据结构。
3. 分析数据规模：数据量大小直接影响选择。n 很小时任何结构都行，n 很大时必须选择高效结构。
4. 常见选择指南：
   • 频繁随机访问 → 数组 / vector
   • 频繁在两端插入删除 → 双端队列 deque
   • 频繁在任意位置插入删除 → 链表
   • 后进先出的场景 → 栈
   • 先进先出的场景 → 队列
   • 需要快速查找最大/最小值 → 堆（优先队列）
   • 需要有序存储和快速查找 → 二叉搜索树 / set / map

✨ 常见错误

• 盲目选择数组：数组虽然简单，但中间位置的插入和删除效率为 O(n)。如果题目频繁进行这类操作，应考虑链表。
• 混淆栈和队列：栈是"后进先出"（LIFO），队列是"先进先出"（FIFO），两者的出入方向完全不同。
• 忽略空间开销：链表的每个节点都需要额外存储指针，如果数据量很大且内存受限，数组可能更合适。
• 不考虑缓存友好性：数组在内存中连续存储，对 CPU 缓存友好，实际运行速度往往比链表快。理论上的时间复杂度不等于实际运行时间。
• 对数据结构的操作复杂度记忆错误：例如误以为链表的随机访问是 O(1)，或者误以为数组的中间插入是 O(1)。建议总结一张各数据结构操作复杂度的对照表。