外观
数据结构核心知识
约 3844 字大约 13 分钟
2025-08-16
一、数据结构基础
1. 基本概念
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
数据结构三要素：
逻辑结构：数据元素之间的逻辑关系
- 集合：数据元素间除"同属一个集合"外无其他关系
- 线性结构：数据元素间存在一对一关系（如数组、链表）
- 树形结构：数据元素间存在一对多关系
- 图状结构：数据元素间存在多对多关系
存储结构（物理结构）：数据结构在计算机中的表示
- 顺序存储：物理位置相邻（如数组）
- 链式存储：物理位置未必相邻，通过指针连接
- 索引存储：通过索引查找数据
- 散列存储：通过哈希函数计算存储位置
数据的运算：在数据结构上定义的操作
2. 算法基础
算法特性：
- 有穷性：算法必须在有限步骤后结束
- 确定性：相同输入得到相同输出
- 可行性：每一步都可在有限时间内完成
- 输入/输出：有零个或多个输入，一个或多个输出
算法复杂度：
时间复杂度：衡量算法执行时间随输入规模增长的趋势
- 常见时间复杂度（从小到大）：
- O(1)：常数时间
- O(log n)：对数时间
- O(n)：线性时间
- O(n log n)：线性对数时间
- O(n²)：平方时间
- O(2ⁿ)：指数时间
- 常见时间复杂度（从小到大）：
空间复杂度：衡量算法所需存储空间随输入规模增长的趋势
复杂度计算技巧：
- 循环嵌套：内层循环次数相乘
- 顺序执行：取最大值
- 递归：建立递推关系式
二、线性表
1. 顺序表（数组实现）
特点：
- 物理存储连续
- 支持随机访问（O(1)时间访问任意元素）
- 插入/删除操作需移动元素（平均O(n)时间）
基本操作：
插入：在位置i插入元素
def insert(arr, i, element): # 将i及之后元素后移 for j in range(len(arr)-1, i-1, -1): arr[j] = arr[j-1] arr[i-1] = element- 最好情况：表尾插入，O(1)
- 最坏情况：表头插入，O(n)
- 平均情况：O(n)
删除：删除位置i的元素
def delete(arr, i): # 将i之后元素前移 for j in range(i, len(arr)-1): arr[j-1] = arr[j]- 最好情况：表尾删除，O(1)
- 最坏情况：表头删除，O(n)
- 平均情况：O(n)
2. 链表
单链表：
- 每个节点包含数据域和指针域
- 不支持随机访问，需从头遍历
- 插入/删除操作只需修改指针（O(1)时间，前提是已找到位置）
双链表：
- 每个节点包含前驱指针和后继指针
- 可双向遍历
- 插入/删除操作更灵活
链表基本操作：
头插法：将新节点插入到链表头部
def insert_head(head, element): new_node = Node(element) new_node.next = head return new_node尾插法：将新节点插入到链表尾部
def insert_tail(head, element): new_node = Node(element) if not head: return new_node current = head while current.next: current = current.next current.next = new_node return head删除节点：
def delete(head, value): # 处理头节点 if head and head.data == value: return head.next current = head while current and current.next: if current.next.data == value: current.next = current.next.next return head current = current.next return head
提示：实际开发中，大多数语言都提供了内置的列表/数组实现，但理解底层原理对性能优化至关重要。
三、栈和队列
1. 栈（Stack）
特点：
- 后进先出（LIFO）
- 只允许在一端（栈顶）进行插入和删除操作
实现方式：
顺序栈（基于数组）
class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() return None def peek(self): if not self.is_empty(): return self.items[-1] return None def is_empty(self): return len(self.items) == 0 def size(self): return len(self.items)链式栈（基于链表）
class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.top = None def push(self, data): new_node = Node(data) new_node.next = self.top self.top = new_node def pop(self): if self.top: data = self.top.data self.top = self.top.next return data return None def peek(self): if self.top: return self.top.data return None def is_empty(self): return self.top is None
常用场景：
- 函数调用栈
- 括号匹配检查
- 表达式求值
- 递归实现
2. 队列（Queue）
特点：
- 先进先出（FIFO）
- 在一端（队尾）插入，在另一端（队头）删除
实现方式：
顺序队列（循环队列）
class Queue: def __init__(self, max_size=100): self.items = [None] * max_size self.front = 0 self.rear = 0 self.max_size = max_size def enqueue(self, item): if (self.rear + 1) % self.max_size != self.front: self.items[self.rear] = item self.rear = (self.rear + 1) % self.max_size return True return False def dequeue(self): if self.front != self.rear: item = self.items[self.front] self.front = (self.front + 1) % self.max_size return item return None def is_empty(self): return self.front == self.rear def size(self): return (self.rear - self.front + self.max_size) % self.max_size链式队列
class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def enqueue(self, data): new_node = Node(data) if self.rear: self.rear.next = new_node self.rear = new_node if not self.front: self.front = self.rear def dequeue(self): if self.front: data = self.front.data self.front = self.front.next if not self.front: self.rear = None return data return None def is_empty(self): return self.front is None
常用场景：
- 任务调度
- 广度优先搜索
- 缓冲区管理
- 打印任务队列
四、树与二叉树
1. 树的基本概念
- 结点：树中的数据元素
- 根结点：树中唯一没有双亲的结点
- 叶子结点：度为0的结点
- 分支结点：度不为0的结点
- 结点的度：结点拥有的子树数量
- 树的度：树中结点度的最大值
- 层次：根结点为第1层，其子结点为第2层，以此类推
- 高度/深度：树中结点的最大层次
2. 二叉树
定义：
- 或为空树
- 或由根结点和互不相交的左子树、右子树组成
性质：
- 非空二叉树上叶子结点数等于度为2的结点数加1
- 非空二叉树上第K层上至多有2^(K-1)个结点（K≥1）
- 高度为H的二叉树至多有2^H-1个结点（H≥1）
特殊二叉树：
- 满二叉树：所有分支结点都有左、右子树，且所有叶子都在同一层
- 完全二叉树：除最后一层外，其他层都是满的，且最后一层的结点都连续集中在左边
存储结构：
- 顺序存储：适用于完全二叉树，使用数组存储
- 链式存储：每个结点包含数据域、左孩子指针和右孩子指针
3. 二叉搜索树（BST）
定义：
- 左子树上所有结点的值均小于根结点的值
- 右子树上所有结点的值均大于根结点的值
- 左右子树也分别是二叉搜索树
基本操作：
查找：
def search(root, key): if not root or root.val == key: return root if key < root.val: return search(root.left, key) return search(root.right, key)- 平均时间复杂度：O(log n)
- 最坏情况（退化为链表）：O(n)
插入：
def insert(root, key): if not root: return TreeNode(key) if key < root.val: root.left = insert(root.left, key) elif key > root.val: root.right = insert(root.right, key) return root删除：
def delete(root, key): if not root: return root # 找到要删除的节点 if key < root.val: root.left = delete(root.left, key) elif key > root.val: root.right = delete(root.right, key) else: # 情况1：叶子节点 if not root.left and not root.right: return None # 情况2：只有一个子节点 elif not root.left: return root.right elif not root.right: return root.left # 情况3：有两个子节点，找右子树的最小节点 else: min_node = find_min(root.right) root.val = min_node.val root.right = delete(root.right, min_node.val) return root def find_min(node): current = node while current.left: current = current.left return current
4. 平衡二叉树（AVL树）
特点：
- 任何节点的两个子树的高度差不超过1
- 通过旋转操作维持平衡
旋转操作：
- LL旋转：左子树的左子树导致不平衡
- RR旋转：右子树的右子树导致不平衡
- LR旋转：左子树的右子树导致不平衡
- RL旋转：右子树的左子树导致不平衡
提示：实际开发中，大多数语言标准库都提供了平衡二叉搜索树的实现（如Java的TreeMap、C++的std::map），但理解原理对性能优化很重要。
五、图
1. 图的基本概念
- 顶点（Vertex）：图中的基本单元
- 边（Edge）：连接两个顶点的线
- 有向图：边有方向
- 无向图：边无方向
- 权重：边可以有权值
- 路径：顶点序列，其中连续顶点由边连接
- 连通：两个顶点间存在路径
2. 图的存储方式
邻接矩阵：
- 二维数组表示，matrix[i][j]表示顶点i到j的边
- 优点：判断两点是否有边O(1)
- 缺点：稀疏图时空间浪费
- 空间复杂度：O(V²)
邻接表：
- 数组+链表（或列表）结构
- 每个顶点对应一个链表，存储与其相连的顶点
- 优点：空间效率高（O(V+E)）
- 缺点：判断两点是否有边需O(V)
3. 图的遍历
深度优先搜索（DFS）：
- 类似树的先序遍历
- 使用栈（递归或显式栈）实现
- 时间复杂度：
- 邻接表：O(V+E)
- 邻接矩阵：O(V²)
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
# 添加未访问的邻居
stack.extend(graph[vertex] - visited)
return visited广度优先搜索（BFS）：
- 类似树的层序遍历
- 使用队列实现
- 时间复杂度：
- 邻接表：O(V+E)
- 邻接矩阵：O(V²)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited常用场景：
- DFS：连通性检查、拓扑排序、寻找路径
- BFS：最短路径（无权图）、社交网络关系
六、查找
1. 顺序查找
原理：从表的一端开始，顺序扫描，比较关键字
时间复杂度：O(n)
def sequential_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i
return -12. 二分查找
前提：有序数组
原理：每次将搜索范围缩小一半
时间复杂度：O(log n)
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
low = mid + 1
else:
high = mid - 1
return -13. 哈希表（散列表）
原理：通过哈希函数将关键字映射到表中位置
关键概念：
- 哈希函数：将关键字转换为存储地址
- 冲突：不同关键字映射到同一位置
- 负载因子：α = 填入表中的元素个数 / 哈希表长度
常用哈希函数：
- 除留余数法：H(key) = key % p（p为不大于表长的质数）
- 平方取中法：取关键字平方值的中间几位
冲突处理方法：
开放定址法：
- 线性探测：Hi = (H(key) + i) % m
- 平方探测：Hi = (H(key) ± i²) % m
拉链法：将冲突元素组织成链表
查找性能：
- 成功查找的平均查找长度：约1 + α/2
- 不成功查找的平均查找长度：约1 + α²/2
提示：哈希表是实际开发中最常用的查找结构，Python的字典、Java的HashMap都是基于哈希表实现的。
七、排序
1. 冒泡排序
原理：重复遍历要排序的数列，一次比较两个元素，如果顺序错误就交换
时间复杂度：
- 最好：O(n)（已排序）
- 平均：O(n²)
- 最坏：O(n²)
空间复杂度：O(1)
稳定性：稳定
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr2. 选择排序
原理：每次从未排序部分找出最小元素，放到已排序部分的末尾
时间复杂度：O(n²)（最好、平均、最坏）
空间复杂度：O(1)
稳定性：不稳定
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr3. 插入排序
原理：将数组分为已排序和未排序两部分，每次将未排序部分的第一个元素插入到已排序部分的适当位置
时间复杂度：
- 最好：O(n)（已排序）
- 平均：O(n²)
- 最坏：O(n²)
空间复杂度：O(1)
稳定性：稳定
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr4. 快速排序
原理：选择一个基准元素，将数组分为两部分（小于基准和大于基准），递归排序两部分
时间复杂度：
- 最好：O(n log n)
- 平均：O(n log n)
- 最坏：O(n²)（已排序数组）
空间复杂度：O(log n)（递归栈）
稳定性：不稳定
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)5. 归并排序
原理：将数组分成两半，递归排序，然后合并两个有序数组
时间复杂度：O(n log n)（最好、平均、最坏）
空间复杂度：O(n)
稳定性：稳定
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result八、常用数据结构选择指南
| 使用场景 | 推荐数据结构 | 原因 |
|---|---|---|
| 需要频繁随机访问 | 数组 | O(1)时间随机访问 |
| 需要频繁插入/删除 | 链表 | O(1)时间插入/删除（已找到位置） |
| LIFO操作 | 栈 | 天然支持后进先出 |
| FIFO操作 | 队列 | 天然支持先进先出 |
| 快速查找 | 哈希表 | 平均O(1)时间查找 |
| 有序数据查找 | 二叉搜索树 | O(log n)平均时间查找 |
| 有序数据范围查询 | 平衡二叉搜索树 | O(log n)时间范围查询 |
| 无权图最短路径 | BFS | 可找到最短路径 |
| 有权图最短路径 | Dijkstra算法 | 可找到最短路径 |
| 拓扑排序 | DFS | 可确定依赖关系 |
| 连通性检查 | 并查集 | 高效检查连通性 |
九、实用技巧与建议
1. 数据结构选择原则
- 明确需求：分析操作频率（查找、插入、删除等）
- 考虑时间复杂度：选择最适合操作需求的结构
- 考虑空间开销：在时间和空间之间权衡
- 考虑实现复杂度：简单问题用简单结构
2. 常见问题解决方案
| 问题 | 可能原因 | 解决思路 |
|---|---|---|
| 查找速度慢 | 使用了线性查找 | 考虑哈希表或二叉搜索树 |
| 插入/删除慢 | 使用了顺序表 | 考虑链表或跳表 |
| 内存占用高 | 数据结构选择不当 | 考虑更紧凑的表示方式 |
| 递归栈溢出 | 递归深度过大 | 考虑迭代实现或增加栈空间 |
| 排序效率低 | 选择了不合适的排序算法 | 根据数据规模选择排序算法 |
3. 面试准备建议
- 掌握基础：确保理解各种数据结构的基本操作和复杂度
- 动手实现：亲手实现常用数据结构，加深理解
- 练习题目：通过LeetCode等平台练习典型题目
- 分析复杂度：每次解题后分析时间和空间复杂度
- 考虑边界：注意处理空输入、重复元素等边界情况