1. 数组

# Python 中的数组通常使用列表来实现
arr = [1, 2, 3, 4, 5]  # 创建一个数组
print(arr[0])  # 访问第一个元素

2. 链表

class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, data):if not self.head:self.head = Node(data)else:current = self.headwhile current.next:current = current.nextcurrent.next = Node(data)# 创建链表并添加元素
ll = LinkedList()
ll.append(1)
ll.append(2)

3. 栈

class Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def is_empty(self):return len(self.items) == 0# 使用栈
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 输出 2

4. 队列和双端队列

from collections import deque# 队列
queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft())  # 输出 1# 双端队列
deque = deque()
deque.append(1)
deque.append(2)
deque.appendleft(0)
print(deque.pop())  # 输出 2
print(deque.popleft())  # 输出 0

5. 哈希表

# Python 的字典就是哈希表的实现
hash_table = {}
hash_table['key1'] = 'value1'
print(hash_table['key1'])  # 输出 'value1'

6. 二叉树

class TreeNode:def __init__(self, data):self.data = dataself.left = Noneself.right = None# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

7. 二叉搜索树

class BSTNode(TreeNode):def __init__(self, data):super().__init__(data)class BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, data):if not self.root:self.root = BSTNode(data)else:self._insert(self.root, data)def _insert(self, node, data):if data < node.data:if node.left:self._insert(node.left, data)else:node.left = BSTNode(data)else:if node.right:self._insert(node.right, data)else:node.right = BSTNode(data)# 使用二叉搜索树
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)

8. 平衡二叉树 (AVL 树)

class AVLNode(TreeNode):def __init__(self, data):super().__init__(data)self.height = 1class AVLTree:def __init__(self):self.root = Nonedef insert(self, data):self.root = self._insert(self.root, data)def _insert(self, node, data):# 插入操作# 更新高度# 检查平衡并调整pass# 使用 AVL 树
avl = AVLTree()
avl.insert(10)
avl.insert(20)
avl.insert(30)

9. 优先队列

import heapq# 使用列表实现优先队列
priority_queue = []
heapq.heappush(priority_queue, (1, 'low'))
heapq.heappush(priority_queue, (5, 'high'))
print(heapq.heappop(priority_queue))  # 输出 (5, 'high')

10. 并查集

class UnionFind:def __init__(self, size):self.parent = [i for i in range(size)]self.rank = [1] * sizedef find(self, x):if self.parent[x] != x:self.parent[x] = self.find(self.parent[x])return self.parent[x]def union(self, x, y):rootX = self.find(x)rootY = self.find(y)if rootX != rootY:if self.rank[rootX] > self.rank[rootY]:self.parent[rootY] = rootXelif self.rank[rootX] < self.rank[rootY]:self.parent[rootX] = rootYelse:self.parent[rootY] = rootXself.rank[rootX] += 1# 使用并查集
uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2))  # 输出 True

11. 前缀和与差分

def prefix_sum(arr):for i in range(1, len(arr)):arr[i] += arr[i - 1]return arrdef difference_array(arr):diff = [0] * len(arr)for i in range(1, len(arr)):diff[i] = arr[i] - arr[i - 1]return diff# 使用前缀和与差分
arr = [1, 2, 4, 7, 0]
prefix_sum(arr)
difference_array(arr)

12. 线段树

class SegmentTree:def __init__(self, data):self._build(data, 0, len(data) - 1)def _build(self, data, start, end):if start == end:self.data[start] = data[start]else:mid = (start + end) // 2self._build(data, start, mid)self._build(data, mid + 1, end)self.data[start] = min(self.data[start], self.data[mid + 1])def query(self, start, end):# 查询操作pass# 使用线段树
st = SegmentTree([1, 3, 5, 7, 9, 2])

13. 树状数组

def build_tree(arr):n = len(arr)tree = [0] * (n + 1)for i in range(1, n + 1):tree[i] = arr[i - 1]while i + (i & -i) <= n:tree[i + (i & -i)] += tree[i]return treedef query(tree, start, end):res = 0while start:res += tree[start]start -= start & -startwhile end:res -= tree[end]end -= end & -endreturn res# 使用树状数组
arr = [1, 2, 3, 4, 5]
tree = build_tree(arr)
print(query(tree, 1, 3))  # 输出 6

14. 字典树和后缀数组

class TrieNode:def __init__(self):self.children = {}self.is_end_of_word = Falseclass Trie:def __init__(self):self.root = TrieNode()def insert(self, word):node = self.rootfor char in word:if char not in node.children:node.children[char] = TrieNode()node = node.children[char]node.is_end_of_word = True# 使用字典树
trie = Trie()
trie.insert("hello")
trie.insert("world")