Python数据结构与算法实现总结（python数据结构知乎）
学习数据结构与算法是编程的核心基础之一。以下是使用Python实现常见数据结构与算法的总结：
一、数据结构
1. 链表
- 节点定义：
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
- 链表操作：插入、删除、遍历。
2. 栈
- 实现（后进先出）：
python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
3. 队列
- 实现（先进先出，使用链表）：
python
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, data):
new_node = Node(data)
if self.tail is None:
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
def dequeue(self):
if self.head is None:
return None
data = self.head.data
self.head = self.head.next
if self.head is None:
self.tail = None
return data
4. 树
- 二叉树节点：
python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
- 遍历（前序、中序、后序、层序）：
python
# 前序遍历（递归）
def preorder(root):
if root:
print(root.val)
preorder(root.left)
preorder(root.right)
# 层序遍历（队列）
from collections import deque
def level_order(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
5. 图
- 邻接表表示：
python
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['E'],
'D': ['F'],
'E': [],
'F': []
}
- 遍历：
python
# DFS（递归）
def dfs(graph, node, visited):
if node not in visited:
print(node)
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# BFS（队列）
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
6. 堆
- 使用heapq模块（最小堆）：
python
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
print(heapq.heappop(heap)) # 输出1
二、算法
1. 排序算法
- 快速排序：
python
def quicksort(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 quicksort(left) + middle + quicksort(right)
- 归并排序：
python
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
2. 查找算法
- 二分查找：
python
def binary_search(arr, target):
low, high = 0, len(arr)-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
3. 动态规划
- 斐波那契数列：
python
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
- 0-1背包问题：
python
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0]*(capacity+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, capacity+1):
if weights[i-1] > w:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
return dp[n][capacity]
三、总结
- 时间复杂度：理解各算法的时间复杂度（如快速排序平均O(n log n)，冒泡排序O(n^2)）。
- 空间复杂度：如归并排序需要额外空间，原地排序更高效。
- 应用场景：根据问题特点选择合适的数据结构与算法（如频繁查找用哈希表，有序数据用二分查找）。
通过实践和刷题（如LeetCode）加深理解，掌握不同场景下的最优解。