DATA STRUCTURES · PYTHON
数据结构学习笔记：Python 实现
从线性表到图论——用 Python 手写实现常用数据结构及其核心算法。包含顺序存储与链式存储对比、栈与队列的工程应用、二叉树的遍历与递归思维、图的最小生成树算法。
Python
Data Structures
Algorithms
Recursion
Chapter 1
线性表
线性表是最基础的数据结构——元素之间存在一对一的前驱后继关系。两种存储方式代表了时空权衡的核心思想。
顺序存储 · SeqList
用 Python 列表模拟连续内存。支持任意位置插入（insert）、追加（append）、按位置/按值删除（delete/remove）、按位置/按值查找（get_item/locate）。核心权衡：随机访问 O(1)，但插入删除需移动元素 O(n)。
SeqList — insert
def insert(self,pos,item):
if self.length>=self.maxsize:
raise Exception ("full")
if pos > self.length or pos < -self.length:
raise Exception ("out of range!")
self.elem.insert(pos,item)
self.length += 1
if self.length>=self.maxsize:
raise Exception ("full")
if pos > self.length or pos < -self.length:
raise Exception ("out of range!")
self.elem.insert(pos,item)
self.length += 1
链式存储 · LinkList
带头节点的单链表。head.data 存储链表长度——将元数据写进头节点是个巧妙的时间换空间技巧。核心权衡：插入删除 O(1)（已知位置），但遍历查找 O(n)。
LinkList — insert
def insert(self,pos,item):
if self.is_empty():
self.head.next=Node(item)
self.head.value+=1
elif pos2 and pos>0:
cursor=self.head
while count1: cursor=cursor.next
node.next=cursor.next
cursor.next=node
self.head.value+=1
if self.is_empty():
self.head.next=Node(item)
self.head.value+=1
elif pos
cursor=self.head
while count
node.next=cursor.next
cursor.next=node
self.head.value+=1
Chapter 2
栈
后进先出（LIFO）的线性结构。push/pop 的时间复杂度均为 O(1)。栈是递归的底层实现机制——每个函数调用就是一个栈帧。
SeqStack — 顺序栈
class SeqStack:
def __init__(self,MAXSIZE=10):
self.elem=[None]*MAXSIZE
self.top=-1
def push(self,item):
self.top+=1
self.elem[self.top]=item
def pop(self):
self.top-=1
return self.elem[self.top+1]
def __init__(self,MAXSIZE=10):
self.elem=[None]*MAXSIZE
self.top=-1
def push(self,item):
self.top+=1
self.elem[self.top]=item
def pop(self):
self.top-=1
return self.elem[self.top+1]
LinkStack — 链式栈
class LinkStack:
def push(self,item):
node=Node(item)
node.next=self.head.next
self.head.next=node
def pop(self):
item=self.head.next.value
self.head.next=self.head.next.next
return item
def push(self,item):
node=Node(item)
node.next=self.head.next
self.head.next=node
def pop(self):
item=self.head.next.value
self.head.next=self.head.next.next
return item
▸ 经典应用：括号匹配
输入一个含括号的字符串，判定括号是否合法配对。算法：遍历字符，遇左括号入栈，遇右括号则弹出栈顶并检查是否匹配。最终栈为空则合法。
def match(s):
stack=SeqStack()
for i in s:
if i in '{[(': stack.push(i)
if i in '}':
if stack.pop()!='{': return False
# 同理处理 ] 和 )
return stack.is_empty()
stack=SeqStack()
for i in s:
if i in '{[(': stack.push(i)
if i in '}':
if stack.pop()!='{': return False
# 同理处理 ] 和 )
return stack.is_empty()
Assignments
栈与链表 · 经典算法题
作业一 · 有序链表合并
两个递增有序线性表 llst_a=[3,5,8,9,12,15,17]，llst_b=[3,6,7,8,11,15,17,19]。合并为递增有序链表，不占用额外存储空间，不允许重复数据。
def merge_lists(l1, l2):
merged = Linklist()
# 双指针归并：同时遍历两个链表
while cursor_a and cursor_b:
if cursor_a.value < cursor_b.value:
merged.append(cursor_a.value)
cursor_a = cursor_a.next
elif cursor_a.value > cursor_b.value:
merged.append(cursor_b.value)
cursor_b = cursor_b.next
else: # 相等时跳过重复
merged.append(cursor_a.value)
cursor_a = cursor_a.next
cursor_b = cursor_b.next
return merged
merged = Linklist()
# 双指针归并：同时遍历两个链表
while cursor_a and cursor_b:
if cursor_a.value < cursor_b.value:
merged.append(cursor_a.value)
cursor_a = cursor_a.next
elif cursor_a.value > cursor_b.value:
merged.append(cursor_b.value)
cursor_b = cursor_b.next
else: # 相等时跳过重复
merged.append(cursor_a.value)
cursor_a = cursor_a.next
cursor_b = cursor_b.next
return merged
作业二 · 绝对值去重
链表保存 [-2,3,12,2,5,7,-5,-2,-3,-12]，对于 data 绝对值相等的结点仅保留第一次出现。要求时间复杂度尽可能低。
def remove_abs_duplicate(linklist):
seen = set() # 用哈希表记录已出现的绝对值
cursor = linklist.head
while cursor.next:
val = abs(cursor.next.data)
if val in seen:
cursor.next = cursor.next.next
else:
seen.add(val)
cursor = cursor.next
seen = set() # 用哈希表记录已出现的绝对值
cursor = linklist.head
while cursor.next:
val = abs(cursor.next.data)
if val in seen:
cursor.next = cursor.next.next
else:
seen.add(val)
cursor = cursor.next
作业三 · 递归求最大/计数/平均
链表存储 [-4,30,21,-14,100,75,9,-43,42,-1,0]，用递归实现：(1) 求最大整数 (2) 求结点个数 (3) 求所有整数平均值。
# 求最大整数 — 递归版
def find_max(head):
if not head.next: return head.data
current_max = find_max(head.next)
return max(head.data, current_max)
# 求结点个数 — 递归版
def node_num(head):
if not head: return 0
return 1 + node_num(head.next)
# 求平均值 = sum / count
def average(head):
return sum_nodes(head) / node_num(head)
def find_max(head):
if not head.next: return head.data
current_max = find_max(head.next)
return max(head.data, current_max)
# 求结点个数 — 递归版
def node_num(head):
if not head: return 0
return 1 + node_num(head.next)
# 求平均值 = sum / count
def average(head):
return sum_nodes(head) / node_num(head)
作业四 · 栈操作序列合法性
I 表示进栈，O 表示出栈。栈初态为空。判定 IOIIOIOO、IOOIOIIO、IIIOIOIO、IIIOOIOO 是否合法。合法条件：出栈时栈不能为空。
def is_valid_seq(seq):
stack = [] # 模拟栈中元素数量
for op in seq:
if op == 'I': stack.append(1)
else:
if not stack: return False
stack.pop()
return True
# IOIIOIOO → True IIIOIOIO → True
# IOOIOIIO → False IIIOOIOO → True
stack = [] # 模拟栈中元素数量
for op in seq:
if op == 'I': stack.append(1)
else:
if not stack: return False
stack.pop()
return True
# IOIIOIOO → True IIIOIOIO → True
# IOOIOIIO → False IIIOOIOO → True
Chapter 3
队列
先进先出（FIFO）。循环队列用取模实现 rear/front 指针循环利用数组空间。
SeqQueue — 循环队列
class SeqQueue:
def __init__(self,MAXSIZE=10):
self.elem=[None]*MAXSIZE
self.front,self.rear=0,0
def en_queue(self,item):
self.elem[self.rear]=item
self.rear=(self.rear+1)%self.capacity
def de_queue(self):
item=self.elem[self.front]
self.front=(self.front+1)%self.capacity
return item
def length(self):
return (self.rear+self.capacity-self.front)%self.capacity
def __init__(self,MAXSIZE=10):
self.elem=[None]*MAXSIZE
self.front,self.rear=0,0
def en_queue(self,item):
self.elem[self.rear]=item
self.rear=(self.rear+1)%self.capacity
def de_queue(self):
item=self.elem[self.front]
self.front=(self.front+1)%self.capacity
return item
def length(self):
return (self.rear+self.capacity-self.front)%self.capacity
Chapter 4
二叉树
非线性结构的起点。前序/中序/后序三种深度遍历对应递归的三种处理顺序，层序遍历用队列实现。
BinaryTree — 三种深度遍历
def PreOrder(self,root): # 根→左→右
if root==None: return
print(root.data,end=' ')
self.PreOrder(root.lchild)
self.PreOrder(root.rchild)
def InOrder(self,root): # 左→根→右
if root==None: return
self.InOrder(root.lchild)
print(root.data,end=' ')
self.InOrder(root.rchild)
def PostOrder(self,root): # 左→右→根
if root==None: return
self.PostOrder(root.lchild)
self.PostOrder(root.rchild)
print(root.data,end=' ')
if root==None: return
print(root.data,end=' ')
self.PreOrder(root.lchild)
self.PreOrder(root.rchild)
def InOrder(self,root): # 左→根→右
if root==None: return
self.InOrder(root.lchild)
print(root.data,end=' ')
self.InOrder(root.rchild)
def PostOrder(self,root): # 左→右→根
if root==None: return
self.PostOrder(root.lchild)
self.PostOrder(root.rchild)
print(root.data,end=' ')
层序遍历 + 求深度
# 层序遍历 — 队列实现
def Traverse(self):
queue=[self.root]
while len(queue)>0:
node=queue.pop(0)
print(node.data,end=' ')
if node.lchild: queue.append(node.lchild)
if node.rchild: queue.append(node.rchild)
# 二叉树深度 — 递归
def Depth(self,root):
if root==None: return 0
return 1+max(self.Depth(root.lchild),
self.Depth(root.rchild))
def Traverse(self):
queue=[self.root]
while len(queue)>0:
node=queue.pop(0)
print(node.data,end=' ')
if node.lchild: queue.append(node.lchild)
if node.rchild: queue.append(node.rchild)
# 二叉树深度 — 递归
def Depth(self,root):
if root==None: return 0
return 1+max(self.Depth(root.lchild),
self.Depth(root.rchild))
二叉树作业一 · 统计叶子结点
以二叉链表存储，递归统计二叉树中叶子结点的个数。叶子结点的判定条件：左右孩子均为空。
def count_leaf(root):
if root == None: return 0
if root.lchild == None and root.rchild == None:
return 1
return count_leaf(root.lchild) + count_leaf(root.rchild)
if root == None: return 0
if root.lchild == None and root.rchild == None:
return 1
return count_leaf(root.lchild) + count_leaf(root.rchild)
二叉树作业二 · 统计度为 1 的结点
按层次顺序遍历二叉树，统计度为 1 的结点数量。度为 1 的定义：有且仅有一个孩子。
def count_one_degree(root):
queue = [root]
while queue:
node = queue.pop(0)
degree = bool(node.lchild) + bool(node.rchild)
if degree == 1: count += 1
if node.lchild: queue.append(node.lchild)
if node.rchild: queue.append(node.rchild)
queue = [root]
while queue:
node = queue.pop(0)
degree = bool(node.lchild) + bool(node.rchild)
if degree == 1: count += 1
if node.lchild: queue.append(node.lchild)
if node.rchild: queue.append(node.rchild)
二叉树作业三 · 叶子到根的路径
递归输出二叉树中从每个叶子结点到根结点的路径。这是回溯思想的经典体现——深入到底后逐层返回并记录经过的节点。
def leaf_paths(root, path=[]):
if not root: return
path.append(root.data)
if not root.lchild and not root.rchild:
print(path) # 到达叶子，输出路径
leaf_paths(root.lchild, path)
leaf_paths(root.rchild, path)
path.pop() # 回溯：移除当前节点
if not root: return
path.append(root.data)
if not root.lchild and not root.rchild:
print(path) # 到达叶子，输出路径
leaf_paths(root.lchild, path)
leaf_paths(root.rchild, path)
path.pop() # 回溯：移除当前节点
Chapter 5
图 · 最小生成树
图论的两个经典贪心算法——Kruskal 对边排序后贪心选边，Prim 从顶点出发逐步扩张。两者都能在 O(E log E) 内求出 MST。
Kruskal · 克鲁斯卡尔算法
核心思想：对所有边按权重升序排序，依次检查每条边——如果加入该边不会形成环（并查集判定），则将其加入 MST。本质是"边贪心"。
def kruskal(edges, n):
edges.sort(key=lambda x: x[2]) # 按权重排序
parent = list(range(n))
def find(x):
if parent[x]!=x: parent[x]=find(parent[x])
return parent[x]
mst = []
for u,v,w in edges:
if find(u)!=find(v):
parent[find(u)]=find(v)
mst.append((u,v,w))
return mst
edges.sort(key=lambda x: x[2]) # 按权重排序
parent = list(range(n))
def find(x):
if parent[x]!=x: parent[x]=find(parent[x])
return parent[x]
mst = []
for u,v,w in edges:
if find(u)!=find(v):
parent[find(u)]=find(v)
mst.append((u,v,w))
return mst
Prim · 普里姆算法
核心思想：从任意顶点出发，维护已选顶点集合 S。每次从 S 到 V-S 的横切边中选权重最小的加入 MST。本质是"点贪心"。
def prim(graph, start=0):
n = len(graph)
visited = [False]*n
visited[start] = True
for _ in range(n-1):
min_w, u, v = float('inf'), -1, -1
# 遍历所有横切边，选最小的
for i in range(n):
if visited[i]:
for j in range(n):
if not visited[j] and graph[i][j] < min_w:
min_w = graph[i][j]
u, v = i, j
visited[v] = True
mst.append((u, v, min_w))
return mst
n = len(graph)
visited = [False]*n
visited[start] = True
for _ in range(n-1):
min_w, u, v = float('inf'), -1, -1
# 遍历所有横切边，选最小的
for i in range(n):
if visited[i]:
for j in range(n):
if not visited[j] and graph[i][j] < min_w:
min_w = graph[i][j]
u, v = i, j
visited[v] = True
mst.append((u, v, min_w))
return mst
5 Chapters · 8 Algorithms · Pure Python
从线性表到图论，每次 Push/Pop 都是对计算机底层的一次致敬。