摘要：def knapsack(weights, values, capacity):
学习数据结构与算法是编程的核心基础之一。以下是使用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
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)
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x
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)
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
if left[i]
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
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid]
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²)）。空间复杂度：如归并排序需要额外空间，原地排序更高效。应用场景：根据问题特点选择合适的数据结构与算法（如频繁查找用哈希表，有序数据用二分查找）。通过实践和刷题（如LeetCode）加深理解，掌握不同场景下的最优解。
来源：老客数据一点号
