在计算机科学的世界里，数据结构是构成一切算法的基础。严蔚敏先生的《数据结构》教材，以其深入浅出的讲解和丰富的习题，成为了许多学习者的首选。本文将带你一起解析严蔚敏经典习题，帮助你轻松掌握数据结构的核心技巧。
一、线性表
1.1 线性表的顺序存储结构
习题：给定一个线性表的顺序存储结构，如何实现对该表的元素进行逆序操作？
解析：
def reverse_list(arr):
n = len(arr)
for i in range(n // 2):
arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]
return arr
# 示例
arr = [1, 2, 3, 4, 5]
print(reverse_list(arr)) # 输出: [5, 4, 3, 2, 1]
1.2 线性表的链式存储结构
习题：如何实现一个循环链表，并实现其在O(1)时间复杂度内删除指定节点？
解析：
class Node:
def __init__(self, value):
self.value = value
self.next = None
def create_cycle_list(arr):
head = Node(arr[0])
current = head
for value in arr[1:]:
current.next = Node(value)
current = current.next
current.next = head
return head
def delete_node(head, value):
current = head
while current.next != head:
if current.next.value == value:
current.next = current.next.next
break
current = current.next
if current.next.value == value:
current.next = head
# 示例
arr = [1, 2, 3, 4, 5]
head = create_cycle_list(arr)
delete_node(head, 3)
二、栈和队列
2.1 栈
习题：使用栈实现一个函数，实现两个字符串的括号匹配。
解析：
def is_balanced(s):
stack = []
for char in s:
if char == '(' or char == '[' or char == '{':
stack.append(char)
elif char == ')' or char == ']' or char == '}':
if not stack or not (char == ')' and stack[-1] == '(') or not (char == ']' and stack[-1] == '[') or not (char == '}' and stack[-1] == '{'):
return False
stack.pop()
return not stack
# 示例
s = "{[()]}()"
print(is_balanced(s)) # 输出: True
2.2 队列
习题：如何使用队列实现一个循环队列？
解析：
class CircularQueue:
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.head = 0
self.tail = 0
def enqueue(self, value):
if (self.tail + 1) % self.size == self.head:
raise Exception("Queue is full")
self.queue[self.tail] = value
self.tail = (self.tail + 1) % self.size
def dequeue(self):
if self.head == self.tail:
raise Exception("Queue is empty")
value = self.queue[self.head]
self.queue[self.head] = None
self.head = (self.head + 1) % self.size
return value
# 示例
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue()) # 输出: 1
三、树和图
3.1 二叉树
习题：如何实现一个二叉搜索树，并实现其在O(log n)时间复杂度内查找指定节点？
解析：
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def search(root, value):
if root is None:
return False
if root.value == value:
return True
if value < root.value:
return search(root.left, value)
return search(root.right, value)
# 示例
root = None
root = insert(root, 5)
root = insert(root, 3)
root = insert(root, 7)
print(search(root, 3)) # 输出: True
3.2 图
习题：如何使用邻接表实现一个加权无向图，并实现Dijkstra算法找到最短路径？
解析：
from heapq import heappop, heappush
import sys
class Graph:
def __init__(self):
self.nodes = {}
self.edges = {}
def add_node(self, node):
self.nodes[node] = None
def add_edge(self, u, v, weight):
if u not in self.nodes:
self.add_node(u)
if v not in self.nodes:
self.add_node(v)
if u not in self.edges:
self.edges[u] = []
if v not in self.edges:
self.edges[v] = []
self.edges[u].append((v, weight))
self.edges[v].append((u, weight))
def dijkstra(self, start):
distances = {node: sys.maxsize for node in self.nodes}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in self.edges[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heappush(priority_queue, (distance, neighbor))
return distances
# 示例
graph = Graph()
graph.add_edge("A", "B", 1)
graph.add_edge("B", "C", 2)
graph.add_edge("C", "D", 3)
print(graph.dijkstra("A")) # 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 6}
通过以上解析，相信你已经对严蔚敏经典习题有了更深入的理解。掌握数据结构的核心技巧，不仅能够让你在计算机科学领域游刃有余，还能为你的未来职业生涯打下坚实的基础。祝你在数据结构的学习道路上越走越远！