外观
数据结构核心知识
约 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等平台练习典型题目
- 分析复杂度:每次解题后分析时间和空间复杂度
- 考虑边界:注意处理空输入、重复元素等边界情况
