数据结构入门教程

数据结构（Data Structure）是计算机存储、组织数据的一种方式，是算法实现的基础。合理选择数据结构可以显著提高程序的效率与可维护性。

---

🧱 1. 数据结构的分类

按照结构关系分类：

1. 线性结构（Linear Structure）
2. 非线性结构（Non-linear Structure）

---

📏 2. 线性结构

线性结构中的元素存在一对一关系，常见的有：

2.1 数组（Array）

- 定义：固定长度的连续内存空间
- 特点：支持随机访问，增删效率低
- 示例：int arr[5] = {1, 2, 3, 4, 5};

适用场景：读多写少、元素数量固定的场景。

2.2 链表（Linked List）

- 定义：由若干个节点构成的线性集合，每个节点包含数据 + 指向下一节点的指针
- 特点：动态增长，插入/删除效率高，不支持随机访问

常见类型：

- 单向链表
- 双向链表
- 循环链表

2.3 栈（Stack）

- 定义：后进先出（LIFO）的数据结构
- 操作：push（入栈）、pop（出栈）
- 应用：函数调用栈、括号匹配、DFS 等

2.4 队列（Queue）

- 定义：先进先出（FIFO）的数据结构
- 操作：enqueue（入队）、dequeue（出队）
- 应用：消息队列、BFS 等

扩展：

- 双端队列（Deque）
- 优先队列（PriorityQueue）

---

🌳 3. 非线性结构

3.1 树（Tree）

- 定义：层级结构，根节点 + 若干子节点
- 应用：文件系统、HTML DOM、表达式解析等

常见类型：

- 普通树
- 二叉树（Binary Tree）
- 二叉搜索树（BST）
- AVL 树（自平衡 BST）
- 红黑树
- B 树、B+ 树
- 堆（最大堆/最小堆）
- 字典树（Trie）

遍历方式：

- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历

3.2 图（Graph）

- 定义：由顶点（Vertex）和边（Edge）组成的结构
- 应用：社交网络、地图、调度系统

图的分类：

- 有向图 / 无向图
- 带权图 / 无权图
- 稀疏图 / 稠密图

图的存储方式：

- 邻接矩阵
- 邻接表

图的遍历：

- 广度优先搜索（BFS）
- 深度优先搜索（DFS）

---

💡 4. 抽象数据类型（ADT）

- List：顺序集合
- Stack：先进后出
- Queue：先进先出
- Deque：双端队列
- Set：不重复元素集合
- Map：键值对映射
- Graph：点与边的结构
- Tree：分层结构

---

🛠️ 5. 常见操作复杂度对比

| 数据结构 | 查找     | 插入     | 删除     |
|----------|----------|----------|----------|
| 数组     | O(1)     | O(n)     | O(n)     |
| 链表     | O(n)     | O(1)     | O(1)     |
| 栈       | O(1)     | O(1)     | O(1)     |
| 队列     | O(1)     | O(1)     | O(1)     |
| 哈希表   | O(1)     | O(1)     | O(1)     |
| BST      | O(log n) | O(log n) | O(log n) |
| 堆       | O(1)     | O(log n) | O(log n) |
| 图       | O(n)     | O(1~n)   | O(1~n)   |

注：哈希表在最坏情况下可能退化到 O(n)，BST 如果不平衡也可能退化。

---

🎯 6. 如何选择数据结构？

| 场景               | 推荐数据结构       |
|--------------------|--------------------|
| 快速查找           | 哈希表、BST        |
| 频繁插入/删除      | 链表、跳表         |
| 栈式操作           | 栈（Stack）        |
| 队列处理           | 队列、Deque        |
| 快速取最值         | 堆（Heap）         |
| 有序数据结构       | 平衡树、跳表       |
| 实现自动补全       | Trie（字典树）     |
| 表示网络关系       | 图（Graph）        |

---

📚 7. 数据结构学习建议

1. 学习基础结构（数组、链表、栈、队列）
2. 掌握树、图的构建与遍历
3. 结合算法训练平台（如 LeetCode、牛客网）做题
4. 写一遍自己语言版本的实现，锻炼抽象能力
5. 掌握空间与时间复杂度分析

---

✅ 8. 推荐练习题目（LeetCode）

1. 反转链表（链表）
2. 有效的括号（栈）
3. 用队列实现栈 / 用栈实现队列
4. 二叉树的前中后序遍历
5. 合并两个有序链表
6. 最小堆（合并 K 个升序链表）
7. 图的 BFS 和 DFS 遍历

---