一、线性数据结构
1. 数组（Array）
- 定义：连续内存存储的有序元素集合，通过索引访问。
- 特点：
- 固定大小（静态数组）或动态扩展（动态数组）。
- 快速随机访问（时间复杂度 O(1)）。
- 示例：json
// JSON 表示 [1, 2, 3, 4, 5]python# Python 操作 arr = [1, 2, 3] arr.append(4) # 插入元素 → [1, 2, 3, 4] arr.pop(1) # 删除索引1 → [1, 3, 4]
2. 链表（Linked List）
- 定义：由节点组成的链式结构，每个节点包含值和指向下一节点的指针。
- 特点：
- 内存非连续，插入/删除高效（时间复杂度 O(1)）。
- 不支持快速随机访问（查找需 O(n)）。
- 示例：json
// JSON 表示单链表节点 { "value": 10, "next": { "value": 20, "next": null } }python# Python 实现单链表 class Node: def __init__(self, val): self.val = val self.next = None node1 = Node(10) node2 = Node(20) node1.next = node2
3. 栈（Stack）
- 定义：后进先出（LIFO） 的线性结构，仅允许在顶端操作。
- 操作：
push（入栈）、pop（出栈）、peek（查看栈顶）。
- 示例：python
# Python 用列表模拟栈 stack = [] stack.append(1) # push → [1] stack.append(2) # push → [1, 2] top = stack[-1] # peek → 2 stack.pop() # pop → [1]
4. 队列（Queue）
- 定义：先进先出（FIFO） 的线性结构，队尾插入，队首删除。
- 操作：
enqueue（入队）、dequeue（出队）。
- 示例：python
# Python 用 deque 实现队列 from collections import deque queue = deque() queue.append(1) # enqueue → [1] queue.append(2) # enqueue → [1, 2] front = queue.popleft() # dequeue → 1
二、树形数据结构
1. 二叉树（Binary Tree）
- 定义：每个节点最多有两个子节点（左、右）。
- 示例：json
// JSON 表示二叉树 { "value": 10, "left": { "value": 5, "left": null, "right": null }, "right": { "value": 15, "left": null, "right": null } }python# Python 实现二叉树节点 class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(15)
2. 堆（Heap）
- 定义：完全二叉树，满足父节点值总大于（大顶堆）或小于（小顶堆）子节点。
- 用途：优先队列、堆排序。
- 示例：python
# Python 使用 heapq 模块 import heapq heap = [] heapq.heappush(heap, 3) # 插入 → [3] heapq.heappush(heap, 1) # 插入 → [1, 3] min_val = heapq.heappop(heap) # 弹出最小值 → 1
三、哈希结构
1. 哈希表（Hash Table）
- 定义：通过哈希函数将键映射到值，实现快速查找（平均 O(1)）。
- 示例：json
// JSON 表示哈希表 { "name": "Alice", "age": 30, "is_admin": true }python# Python 字典操作 hashmap = {"name": "Alice", "age": 30} hashmap["email"] = "alice@example.com" # 插入 del hashmap["age"] # 删除 val = hashmap.get("name") # 查找 → "Alice"
四、图结构（Graph）
1. 邻接表表示法
- 定义：用链表或数组存储每个顶点的邻居。
- 示例：json
// JSON 表示无向图（顶点 0 连接 1 和 2） { "0": [1, 2], "1": [0, 2], "2": [0, 1] }python# Python 实现邻接表 graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1] }
五、高级数据结构
1. 字典树（Trie）
- 定义：用于高效存储和检索字符串的树形结构。
- 示例：json
// JSON 表示存储单词 "apple" 和 "app" { "root": { "a": { "p": { "p": { "l": { "e": {"is_end": true} }, "is_end": true } } } } }
2. 并查集（Disjoint Set）
- 定义：管理元素分组，支持合并集合和查询根节点。
- 操作：
find（查找根节点）、union（合并集合）。
- 示例：python
# Python 实现并查集 class UnionFind: def __init__(self, size): self.parent = list(range(size)) def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x != root_y: self.parent[root_y] = root_x
六、数据结构的选择指南
| 场景 | 推荐数据结构 | 理由 |
|---|---|---|
| 快速查找键值对 | 哈希表 | 平均 O(1) 时间复杂度 |
| 维护操作顺序（如撤销） | 栈 | 后进先出特性 |
| 广度优先搜索（BFS） | 队列 | 先进先出保证层级遍历 |
| 有序数据动态插入 | 平衡二叉搜索树（如红黑树） | 插入、删除、查找均 O(log n) |
| 高频求最小值/最大值 | 堆 | 快速获取极值（O(1)） |
七、复杂数据结构的 JSON 表示
1. 嵌套对象和数组（模拟树）
json
{
"name": "root",
"children": [
{
"name": "child1",
"children": [
{
"name": "grandchild1",
"children": []
},
{
"name": "grandchild2",
"children": []
}
]
},
{
"name": "child2",
"children": []
}
]
}2. 图的边列表表示
json
{
"edges": [
{
"from": 0,
"to": 1,
"weight": 5
},
{
"from": 1,
"to": 2,
"weight": 3
},
{
"from": 2,
"to": 0,
"weight": 2
}
]
}