从数组到哈夫曼树：用Python代码图解软考数据结构核心算法

从数组到哈夫曼树Python实战软考核心数据结构1. 线性结构的Python实现1.1 顺序栈与队列的实现Python的列表(list)天然适合实现顺序存储结构。我们先来看栈的实现class ArrayStack: def __init__(self, capacity10): self._items [] self._capacity capacity def push(self, item): if len(self._items) self._capacity: raise Exception(Stack overflow) self._items.append(item) def pop(self): if not self._items: raise Exception(Stack underflow) return self._items.pop() def peek(self): return self._items[-1] if self._items else None循环队列的实现则需要特别注意队满和队空的判断条件class CircularQueue: def __init__(self, capacity8): self._items [None] * capacity self._front 0 self._rear 0 self._count 0 def enqueue(self, item): if self.is_full(): raise Exception(Queue is full) self._items[self._rear] item self._rear (self._rear 1) % len(self._items) self._count 1 def dequeue(self): if self.is_empty(): raise Exception(Queue is empty) item self._items[self._front] self._front (self._front 1) % len(self._items) self._count - 1 return item def is_full(self): return self._count len(self._items) def is_empty(self): return self._count 0关键点对比操作顺序栈时间复杂度循环队列时间复杂度插入O(1)O(1)删除O(1)O(1)空间复杂度O(n)O(n)1.2 链式存储的实现链式存储结构在Python中可以用类来实现节点class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class LinkedListStack: def __init__(self): self._head None def push(self, val): new_node ListNode(val, self._head) self._head new_node def pop(self): if not self._head: raise Exception(Stack is empty) val self._head.val self._head self._head.next return val链式队列的实现需要同时维护头尾指针class LinkedQueue: def __init__(self): self._head None self._tail None def enqueue(self, val): new_node ListNode(val) if not self._head: self._head self._tail new_node else: self._tail.next new_node self._tail new_node def dequeue(self): if not self._head: raise Exception(Queue is empty) val self._head.val self._head self._head.next if not self._head: self._tail None return val2. 树结构的Python实现2.1 二叉树节点与遍历二叉树节点的Python实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right递归方式实现三种遍历def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val]非递归实现需要借助栈结构def preorder_iter(root): if not root: return [] stack, res [root], [] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res2.2 哈夫曼树的构建哈夫曼树构建过程将所有权值作为单独的树每次选择权值最小的两棵树合并重复直到只剩一棵树Python实现import heapq class HuffmanNode: def __init__(self, val, freq, leftNone, rightNone): self.val val self.freq freq self.left left self.right right def __lt__(self, other): return self.freq other.freq def build_huffman_tree(freq_map): heap [] for val, freq in freq_map.items(): heapq.heappush(heap, HuffmanNode(val, freq)) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) merged HuffmanNode(None, left.freq right.freq, left, right) heapq.heappush(heap, merged) return heapq.heappop(heap)计算带权路径长度(WPL)def calculate_wpl(root, depth0): if not root: return 0 if not root.left and not root.right: return root.freq * depth return (calculate_wpl(root.left, depth 1) calculate_wpl(root.right, depth 1))3. 图的Python实现3.1 邻接矩阵表示class GraphMatrix: def __init__(self, vertices): self.size len(vertices) self.vertices vertices self.matrix [[0]*self.size for _ in range(self.size)] self.vertex_index {v:i for i,v in enumerate(vertices)} def add_edge(self, u, v, weight1): i self.vertex_index[u] j self.vertex_index[v] self.matrix[i][j] weight # 无向图需要对称设置 # self.matrix[j][i] weight3.2 邻接表表示class GraphAdjList: def __init__(self, vertices): self.vertices vertices self.adj {v:[] for v in vertices} def add_edge(self, u, v, weightNone): self.adj[u].append((v, weight)) # 无向图需要双向添加 # self.adj[v].append((u, weight))3.3 图的遍历实现深度优先搜索(DFS)实现def dfs(graph, start): visited set() stack [start] result [] while stack: vertex stack.pop() if vertex not in visited: visited.add(vertex) result.append(vertex) # 邻接表实现需要逆序压栈以保证顺序 for neighbor in reversed(graph.adj[vertex]): if neighbor[0] not in visited: stack.append(neighbor[0]) return result广度优先搜索(BFS)实现from collections import deque def bfs(graph, start): visited set() queue deque([start]) result [] while queue: vertex queue.popleft() if vertex not in visited: visited.add(vertex) result.append(vertex) for neighbor in graph.adj[vertex]: if neighbor[0] not in visited: queue.append(neighbor[0]) return result4. 算法性能对比与优化4.1 时间复杂度分析不同数据结构操作的时间复杂度对比数据结构查找插入删除空间复杂度顺序栈O(n)O(1)O(1)O(n)链式栈O(n)O(1)O(1)O(n)循环队列O(n)O(1)O(1)O(n)二叉树O(n)O(n)O(n)O(n)平衡树O(logn)O(logn)O(logn)O(n)邻接矩阵O(1)O(1)O(1)O(n²)邻接表O(V)O(1)O(E)O(VE)4.2 常见优化技巧空间优化对于稀疏图邻接表比邻接矩阵更节省空间时间优化在树结构中引入平衡因子保持树的平衡缓存优化对于频繁访问的数据可以考虑使用缓存机制并行计算对于大规模图计算可以考虑并行化处理# 平衡二叉树的旋转操作示例 def rotate_left(self, node): new_root node.right node.right new_root.left new_root.left node # 更新高度 node.height 1 max(self._height(node.left), self._height(node.right)) new_root.height 1 max(self._height(new_root.left), self._height(new_root.right)) return new_root4.3 可视化调试技巧使用Graphviz进行数据结构可视化from graphviz import Digraph def visualize_tree(root): dot Digraph() nodes [(root, None)] while nodes: node, parent nodes.pop() dot.node(str(id(node)), str(node.val)) if parent: dot.edge(str(id(parent)), str(id(node))) if node.right: nodes.append((node.right, node)) if node.left: nodes.append((node.left, node)) return dot对于图结构可以类似地添加边和节点进行可视化。这种可视化方法特别适合调试复杂的数据结构问题。