算法与数据结构：从基础到深入

1. 数组 (Array)

定义

• 一组连续内存空间存储的相同类型元素的集合。
• 特点：通过下标（索引）快速访问元素，但大小固定（静态数组）或可扩展（动态数组）。

核心操作

操作	时间复杂度	说明
访问元素	O(1)	通过索引直接访问（如arr[3]）
插入元素	O(n)	需要移动后续元素
删除元素	O(n)	同上
查找元素	O(n)	遍历查找（无序数组）

代码示例

# 创建数组
arr = [1, 2, 3, 4]# 访问元素
print(arr[0])  # 输出 1# 插入元素（在末尾添加）
arr.append(5)   # O(1)（动态数组均摊时间）
arr.insert(2, 10)  # O(n)（插入到中间）# 删除元素
arr.pop()      # 删除末尾元素 O(1)
arr.pop(0)     # 删除第一个元素 O(n)

应用场景

• 需要快速随机访问（如矩阵运算）
• 数据量已知或变化较小的场景

---

2. 链表 (Linked List)

定义

• 由节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。
• 特点：内存非连续，插入/删除高效，但访问元素需要遍历。

类型

• 单链表：每个节点指向下一个节点。
• 双链表：节点同时指向前驱和后继。
• 循环链表：尾节点指向头节点。

核心操作

操作	时间复杂度	说明
访问元素	O(n)	从头节点开始遍历
插入/删除	O(1)	已知前驱节点时（如双链表）
查找元素	O(n)	必须遍历

代码示例（单链表）

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next# 创建链表：1 -> 2 -> 3
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)# 插入节点（在节点2后插入4）
node = head.next
new_node = ListNode(4)
new_node.next = node.next
node.next = new_node  # 链表变为1 -> 2 -> 4 -> 3# 删除节点（删除节点4）
node.next = node.next.next  # 链表恢复为1 -> 2 -> 3

应用场景

• 频繁插入/删除的场景（如LRU缓存）
• 实现栈、队列等数据结构

---

3. 栈 (Stack)

定义

• 后进先出(LIFO)的线性结构。
• 核心操作：push（入栈）、pop（出栈）、peek（查看栈顶）。

代码示例

# 用列表模拟栈
stack = []
stack.append(1)   # push 1
stack.append(2)   # push 2
top = stack[-1]   # peek -> 2
stack.pop()       # pop -> 2

应用场景

• 函数调用栈
• 括号匹配、表达式求值（如逆波兰表达式）

---

4. 队列 (Queue)

定义

• 先进先出(FIFO)的线性结构。
• 核心操作：enqueue（入队）、dequeue（出队）。

代码示例

from collections import deque
queue = deque()
queue.append(1)    # 入队
queue.append(2)
front = queue[0]   # 查看队首
queue.popleft()    # 出队 -> 1

变种队列

• 双端队列 (Deque)：两端均可插入/删除。
• 优先队列 (Priority Queue)：按优先级出队（通常用堆实现）。

应用场景

• 任务调度、消息队列
• BFS（广度优先搜索）

---

5. 哈希表 (Hash Table)

5.1 哈希表 概念

定义

• 通过键(Key)直接访问值(Value)的数据结构。
• 核心思想：哈希函数将键映射到存储位置。

冲突解决

• 开放寻址法：冲突时寻找下一个空槽。
• 链地址法：每个槽存储链表（如Python的字典）。

代码示例

# Python字典 即哈希表实现
hash_map = {}
hash_map["apple"] = 1  # 插入
hash_map["banana"] = 2
print(hash_map.get("apple"))  # 获取 -> 1
del hash_map["banana"]        # 删除

应用场景

• 快速查找（如数据库索引）
• 统计频率（如字母异位词分组）

5.2 链地址法（Chaining）

核心思想

• 每个数组的索引位置（称为“桶”）不再直接存储单个键值对，而是存储一个链表（或红黑树等其他数据结构）。
• 当多个键的哈希值冲突时，它们会被添加到同一个桶的链表中。

具体操作

1. 插入键值对：
   • 计算键的哈希值，找到对应桶。
   • 如果桶为空，直接存入链表头节点。
   • 如果桶不为空，遍历链表：
     • 如果发现键已存在，更新值。
     • 如果不存在，将新键值对添加到链表末尾（或头部）。
2. 查找键值对：
   • 计算键的哈希值，找到对应桶。
   • 遍历链表，逐个比较键是否匹配。

代码示例（Python简化版）

class HashTable:def __init__(self, size=10):self.size = sizeself.table = [[] for _ in range(size)]  # 每个桶是一个列表（模拟链表）def _hash(self, key):return hash(key) % self.size  # 哈希函数def put(self, key, value):bucket_idx = self._hash(key)bucket = self.table[bucket_idx]# 遍历链表，检查是否已存在该键for i, (k, v) in enumerate(bucket):if k == key:bucket[i] = (key, value)  # 更新键值对returnbucket.append((key, value))  # 添加新键值对def get(self, key):bucket_idx = self._hash(key)bucket = self.table[bucket_idx]for k, v in bucket:if k == key:return vreturn None  # 未找到

为什么链地址法不会导致效率低下？

虽然链表需要遍历，但哈希表的设计目标是通过以下两点保证高效性：

(1) 哈希函数的均匀性

• 好的哈希函数会将键均匀分布到各个桶中，避免大量冲突。
• 例如，Python的哈希函数对字符串、整数等类型有优化，冲突概率极低。

(2) 负载因子（Load Factor）控制

• 负载因子 = 哈希表中元素数量 / 桶的数量。
• 当负载因子超过阈值（如0.75），哈希表会触发扩容（Rehashing）：
  • 创建一个更大的桶数组（例如翻倍）。
  • 将所有键值对重新哈希到新桶中。
• 扩容后，冲突概率显著降低，链表长度保持较短（通常为0-2个节点）。

现代哈希表（如Java的HashMap）会进一步优化链地址法：

• 链表转红黑树（Java）：当链表长度超过阈值（如8），将链表转换为红黑树，将查找时间从O(n)优化为O(log n)。
• 动态扩容策略：根据负载因子智能调整桶的数量，平衡时间和空间。

5.3 开放地址法（Open Addressing）

核心思想

开放地址法的思想是，当发生冲突时，寻找另一个空的数组位置来存储冲突的元素。常见的解决方法有线性探测法、二次探测法和双重哈希法等。

具体实现

• 插入：当插入新元素时，计算哈希值，如果该位置已经被占用，就按照预定的探测策略（如线性探测）尝试查找下一个空的位置。
• 查找：查找时，先计算哈希值，如果当前位置的元素就是我们要查找的键，就直接返回值。如果当前位置不匹配，就根据探测策略继续查找其他位置，直到找到目标或确认该键不存在。

代码示例（Python简化版）

class HashTable:def __init__(self, size=10):self.size = sizeself.table = [None] * self.size  # 每个桶直接存储键值对或标记def _hash(self, key):return hash(key) % self.sizedef _probe(self, start_idx):"""线性探测下一个可用位置"""idx = start_idxwhile True:if self.table[idx] is None or self.table[idx] == "DELETED":return idxidx = (idx + 1) % self.size  # 回绕到数组开头if idx == start_idx:  # 整个表已满raise Exception("Hash table is full")def put(self, key, value):start_idx = self._hash(key)idx = start_idx# 查找可插入的位置或更新现有键while True:if self.table[idx] is None or self.table[idx] == "DELETED":# 插入新键值对self.table[idx] = (key, value)returnelif self.table[idx][0] == key:# 键已存在，更新值self.table[idx] = (key, value)returnidx = (idx + 1) % self.size # 通过取余方式能够遍历整个数组if idx == start_idx:raise Exception("Hash table is full")def get(self, key):start_idx = self._hash(key)idx = start_idxwhile True:entry = self.table[idx]if entry is None:return None  # 未找到elif entry != "DELETED" and entry[0] == key:return entry[1]  # 返回找到的值idx = (idx + 1) % self.sizeif idx == start_idx:return None  # 遍历完整个表未找到

---

6. 二叉树 (Binary Tree)

定义

• 每个节点最多有两个子节点（左子节点、右子节点）。
• 特殊类型：
  • 二叉搜索树 (BST)：左子树所有节点 < 根节点 < 右子树所有节点。
  • 平衡二叉树（如AVL树、红黑树）：通过旋转保持高度平衡。

遍历方式

遍历方式	顺序
前序遍历	根 -> 左 -> 右
中序遍历	左 -> 根 -> 右
后序遍历	左 -> 右 -> 根
层序遍历	按层级从上到下、从左到右

代码示例（二叉树节点）

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

应用场景

• 文件系统结构
• 表达式树（用于计算）

---

7. 堆 (Heap)

定义

• 一种完全二叉树，满足：
  • 最大堆：父节点值 ≥ 子节点值。
  • 最小堆：父节点值 ≤ 子节点值。

:::tip

完全二叉树是指除了最后一层外，其他层的节点都是 满的，并且最后一层的节点 尽可能靠左排列。

:::

核心操作

操作	时间复杂度	说明
插入元素	O(log n)	上浮调整（sift up）
删除堆顶	O(log n)	下沉调整（sift down）

代码示例（Python的 heapq 模块）

import heapq# 最小堆
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # 输出1

应用场景

• 优先队列
• Top K问题（如最大的K个元素）

---

8. 图 (Graph)

定义

• 由 顶点(Vertex) 和 边(Edge) 组成的非线性结构。
• 表示方式：
  • 邻接矩阵：二维数组表示顶点连接关系。
  • 邻接表：为每个顶点维护一个链表，记录其邻居。

常见算法

• 遍历：DFS（深度优先）、BFS（广度优先）
• 最短路径：Dijkstra（无负权边）、Bellman-Ford（含负权边）
• 最小生成树：Prim算法、Kruskal算法

代码示例（邻接表表示图）

# 使用字典表示邻接表
graph = {'A': ['B', 'C'],'B': ['D'],'C': ['E'],'D': [],'E': []
}# DFS遍历
def dfs(graph, node, visited):if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:dfs(graph, neighbor, visited)dfs(graph, 'A', set())  # 输出A -> B -> D -> C -> E

应用场景

• 社交网络（顶点为用户，边为好友关系）
• 路径规划（如地图导航）