### 数据结构与算法的 Python 实现 在 Python 中，数据结构与算法可以通过多种方式实现。以下是一些常见的数据结构和算法的示例代码。 --- #### 1. 数组（列表） 数组是 Python 中最常用的数据结构之一，通常通过列表来实现。 ```python # 创建一个简单的数组（列表） arr = [1, 2, 3, 4, 5] # 访问元素 print(arr[0]) # 输出第一个元素 # 修改元素 arr[0] = 10 print(arr) # 输出修改后的数组 ``` [^1] --- #### 2. 栈 栈是一种后进先出（LIFO）的数据结构，可以使用列表来实现。 ```python # 创建一个栈 stack = [] # 入栈 stack.append(1) stack.append(2) stack.append(3) # 出栈 print(stack.pop()) # 输出 3 print(stack.pop()) # 输出 2 ``` --- #### 3. 队列 队列是一种先进先出（FIFO）的数据结构，可以使用 `collections.deque` 来实现。 ```python from collections import deque # 创建一个队列 queue = deque() # 入队 queue.append(1) queue.append(2) queue.append(3) # 出队 print(queue.popleft()) # 输出 1 print(queue.popleft()) # 输出 2 ``` --- #### 4. 链表 链表由节点组成，每个节点包含数据和指向下一个节点的指针。以下是单链表的实现： ```python class Node: def __init__(self, data=None): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): if not self.head: self.head = Node(data) else: current = self.head while current.next: current = current.next current.next = Node(data) def display(self): elements = [] current = self.head while current: elements.append(current.data) current = current.next return elements # 测试链表 ll = LinkedList() ll.append(1) ll.append(2) ll.append(3) print(ll.display()) # 输出 [1, 2, 3] ``` --- #### 5. 哈希表 哈希表是一种基于键值对存储数据的数据结构，Python 中的字典就是一种哈希表。 ```python # 创建一个哈希表 hash_table = {} # 插入键值对 hash_table['key1'] = 'value1' hash_table['key2'] = 'value2' # 访问值 print(hash_table['key1']) # 输出 value1 # 删除键值对 del hash_table['key1'] print(hash_table) # 输出 {'key2': 'value2'} ``` [^1] --- #### 6. 二叉树 二叉树是一种非线性数据结构，每个节点最多有两个子节点。以下是二叉树的简单实现： ```python class TreeNode: def __init__(self, key): self.left = None self.right = None self.val = key def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.val, end=" ") inorder_traversal(root.right) # 测试二叉树 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) inorder_traversal(root) # 输出 4 2 5 1 3 ``` [^3] --- #### 7. 动态规划：斐波那契数列 动态规划是一种解决复杂问题的有效方法。以下是一个使用动态规划计算斐波那契数列的示例： ```python def fibonacci(n): F = [0, 1] + [0] * (n - 1) for i in range(2, n + 1): F[i] = F[i - 1] + F[i - 2] return F[n] print(fibonacci(10)) # 输出 55 ``` [^5] --- #### 8. 背包问题 背包问题是经典的动态规划问题。以下是一个 0-1 背包问题的实现： ```python def knapsack(W, weight, value, n): dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, W + 1): if weight[i - 1] <= w: dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]) else: dp[i][w] = dp[i - 1][w] return dp[n][W] # 测试背包问题 weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 5 print(knapsack(capacity, weights, values, len(weights))) # 输出 6 ``` [^5] ---