Python 的数据结构可以根据 存储方式、访问方式、适用场景 等进行分类。

线性结构（Linear Structures）

1. 顺序存储

数据结构	说明	适用场景
列表（List）	Python 内置 动态数组，支持 索引访问	适用于 动态数组、查找、排序
元组（Tuple）	不可变 的列表，性能优于 List	适用于 只读数据、键值映射
字符串（String）	Python 视为 不可变的字符数组	适用于 文本处理

列表（List）

• 可变（Mutable）：可以修改、添加或删除元素。
• 有序（Ordered）：元素按插入顺序存储，可通过索引访问。
• 支持重复元素：允许存储相同的值。
• 动态大小：可以随时增减元素。

方法	说明
append(x)	在列表 末尾添加元素 x
extend(iterable)	用可迭代对象 iterable 扩展列表
insert(i, x)	在索引 i 处插入元素 x
remove(x)	删除列表中 第一个值为 x 的元素
pop([i])	删除并返回索引 i 处的元素，默认 删除最后一个
clear()	清空 列表
index(x, [start, end])	返回 元素 x 在列表中的索引，可指定范围
count(x)	统计 元素 x 在列表中出现的次数
sort(key=None, reverse=False)	对列表进行 排序，可指定 key 和是否降序
reverse()	反转 列表
copy()	返回列表的 浅拷贝

my_list = [3, 1, 4, 1, 5, 9, 2] # 创建一个列表

# 1. append() - 在列表末尾添加元素
my_list.append(6) # [3, 1, 4, 1, 5, 9, 2, 6]

# 2. extend() - 用可迭代对象扩展列表
my_list.extend([7, 8, 9]) # [3, 1, 4, 1, 5, 9, 2, 6, 7, 8, 9]

# 3. insert() - 在指定索引处插入元素
my_list.insert(2, 42) # [3, 1, 42, 4, 1, 5, 9, 2, 6, 7, 8, 9]

# 4. remove() - 删除指定值（删除第一个匹配的值）
my_list.remove(1) # [3, 42, 4, 1, 5, 9, 2, 6, 7, 8, 9]

# 5. pop() - 删除并返回指定索引的元素（默认最后一个）
popped_element = my_list.pop() # 9 [3, 42, 4, 1, 5, 9, 2, 6, 7, 8]

# 6. index() - 返回元素第一次出现的索引
index_of_5 = my_list.index(5) # 4

# 7. count() - 统计元素出现次数
count_of_1 = my_list.count(1) # 1

# 8. sort() - 对列表进行排序
my_list.sort() # [1, 2, 3, 4, 5, 6, 7, 8, 9, 42]

# 9. reverse() - 反转列表
my_list.reverse() # [42, 9, 8, 7, 6, 5, 4, 3, 2, 1]

# 10. copy() - 复制列表
copy_list = my_list.copy() # [42, 9, 8, 7, 6, 5, 4, 3, 2, 1]

# 11. clear() - 清空列表
my_list.clear() # []

元组（Tuple）

• 不可变（Immutable）：创建后不能修改元素值。
• 有序：可以通过索引访问。
• 支持重复元素。
• 占用更少内存，比列表更快。

方法	说明
count(x)	统计 元素 x 在元组中出现的次数
index(x, [start, end])	返回 元素 x 在元组中第一次出现的索引，可指定范围

my_tuple = (3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5) # 创建一个元组

# 1. count() - 统计元素出现次数
count_of_5 = my_tuple.count(5)  # 3

# 2. index() - 返回元素第一次出现的索引
index_of_9 = my_tuple.index(9)  # 5

# 3. index()（指定范围） - 在索引 3 到 8 之间查找元素 5
index_of_5_in_range = my_tuple.index(5, 3, 9)  # 6

相比于 List，元组的不可变性使其缺少修改数据的方法，例如 append()、remove()、insert() 等操作。如果 需要修改数据，可以转换成 List，修改后再转换回 Tuple。

• 虽然 元组的方法只有 count() 和 index()。
• 但仍可以使用 +、*、切片、内置函数 等方式进行操作。

1. + 连接（拼接）

tuple1 = (1, 2, 3)
tuple2 = (4, 5, 6)
new_tuple = tuple1 + tuple2  # (1, 2, 3, 4, 5, 6)

2. * 复制

tuple1 = (1, 2, 3)
tuple2 = tuple1 * 2  # (1, 2, 3, 1, 2, 3)

字符串（String）

• 不可变（Immutable）：一旦创建，字符串的内容不可修改。
• 有序（Ordered）：字符串中的字符按顺序排列，可以通过索引访问。
• 支持重复字符：允许出现相同的字符。
• 固定大小：字符串的长度一旦确定，就不能再修改。

方法	说明
upper()	将字符串中的 所有字母 转换为 大写
lower()	将字符串中的 所有字母 转换为 小写
capitalize()	将字符串的 第一个字符 转换为 大写，其余字符转换为 小写
title()	将字符串中的 每个单词的首字母 转换为 大写
strip()	移除字符串 两端的空白字符（包括空格、换行符等）
replace(old, new)	将字符串中的 old 字符替换为 new 字符
split(separator)	使用 指定的分隔符 将字符串分割成一个 列表，默认为按空白字符分割
join(iterable)	将 可迭代对象（如列表）中的元素连接成一个字符串
find(sub)	返回子字符串 sub 在字符串中 首次出现的位置，若未找到返回 -1
count(sub)	返回子字符串 sub 在字符串中出现的 次数
index(sub)	返回子字符串 sub 在字符串中 首次出现的位置，若未找到则抛出异常
startswith(prefix)	判断字符串是否以指定的 prefix 开头
endswith(suffix)	判断字符串是否以指定的 suffix 结尾
isalpha()	判断字符串是否只包含 字母
isdigit()	判断字符串是否只包含 数字
isalnum()	判断字符串是否只包含 字母和数字

my_string = " Hello, Python!  "  # 创建一个字符串

# 1. upper() - 将所有字母转换为大写
upper_str = my_string.upper()  # " HELLO, PYTHON!  "

# 2. lower() - 将所有字母转换为小写
lower_str = my_string.lower()  # " hello, python!  "

# 3. capitalize() - 将第一个字符转换为大写，剩余字符为小写
capitalized_str = my_string.capitalize()  # " hello, python!  "

# 4. title() - 将每个单词的首字母转换为大写
title_str = my_string.title()  # " Hello, Python!  "

# 5. strip() - 移除两端的空白字符
stripped_str = my_string.strip()  # "Hello, Python!"

# 6. replace() - 替换字符串中的子字符串
replaced_str = my_string.replace("Python", "World")  # " Hello, World!  "

# 7. split() - 按空白字符拆分字符串
split_list = my_string.split()  # ['Hello,', 'Python!']

# 8. join() - 将列表元素连接为字符串
joined_str = "-".join(split_list)  # "Hello,-Python!"

# 9. find() - 查找子字符串的位置
index_of_python = my_string.find("Python")  # 8

# 10. count() - 统计子字符串出现的次数
count_python = my_string.count("Python")  # 1

# 11. index() - 查找子字符串的位置，未找到则抛出异常
index_of_world = my_string.index("World")  # 会抛出 ValueError: substring not found

# 12. startswith() - 判断字符串是否以 "Hello" 开头
starts_with_hello = my_string.startswith("Hello")  # True

# 13. endswith() - 判断字符串是否以 "!" 结尾
ends_with_exclamation = my_string.endswith("!")  # False

# 14. isalpha() - 判断字符串是否只包含字母
is_alpha = "abc".isalpha()  # True
is_alpha_num = "abc123".isalpha()  # False

# 15. isdigit() - 判断字符串是否只包含数字
is_digit = "12345".isdigit()  # True

# 16. isalnum() - 判断字符串是否只包含字母和数字
is_alnum = "abc123".isalnum()  # True

2. 线性存储

数据结构	说明	适用场景
栈（Stack）	后进先出（LIFO），用 list.append() & list.pop() 实现	撤销操作、括号匹配、深度优先搜索（DFS）
队列（Queue）	先进先出（FIFO），用 collections.deque 实现	任务调度、消息队列
双端队列（Deque）	两端可进可出，用 collections.deque 实现	滑动窗口、缓存管理
优先队列（Priority Queue）	元素按优先级排列，用 heapq 实现	调度系统、最短路径算法（Dijkstra）

栈（Stack）

• 后进先出（LIFO, Last In First Out）
• 只能在一端进行插入和删除（称为栈顶）
• 操作类似于“堆叠的盘子”，后放的盘子要先取出

方法	说明
stack.append(x)	入栈（Push）：将元素 x 压入栈顶
stack.pop()	出栈（Pop）：移除并返回栈顶元素
stack[-1]	查看栈顶元素（Peek）
len(stack)	查看栈的大小
not stack	判断栈是否为空

stack = []  # 创建一个空栈

# 1. 入栈
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack after push:", stack)  # [1, 2, 3]

# 2. 查看栈顶元素（不删除）
top = stack[-1]
print("Top element:", top)  # 3

# 3. 出栈
popped = stack.pop()
print("Popped element:", popped)  # 3
print("Stack after pop:", stack)  # [1, 2]

# 4. 判断是否为空
print("Is stack empty?", not stack)  # False

# 5. 栈的大小
print("Stack size:", len(stack))  # 2

高效栈用 deque 实现。

from collections import deque

stack = deque()

stack.append(1)  # 入栈
stack.append(2)
stack.append(3)
print(stack.pop())  # 出栈，返回 3
print(stack)  # deque([1, 2])

队列（Queue）

• 先进先出（FIFO, First In First Out）
• 从队尾入队，从队首出队
• 操作类似于“排队买票”，先来的人先买票离开

方法	说明
queue.append(x)	入队（Enqueue）：将元素 x 插入队尾
queue.pop(0)	出队（Dequeue）：移除并返回队首元素
queue[0]	查看队首元素（Peek）
len(queue)	查看队列大小
not queue	判断队列是否为空

queue = []  # 创建一个空队列

# 1. 入队
queue.append("A")
queue.append("B")
queue.append("C")
print("Queue after enqueue:", queue)  # ['A', 'B', 'C']

# 2. 查看队首元素（不删除）
front = queue[0]
print("Front element:", front)  # 'A'

# 3. 出队
dequeued = queue.pop(0)
print("Dequeued element:", dequeued)  # 'A'
print("Queue after dequeue:", queue)  # ['B', 'C']

# 4. 判断是否为空
print("Is queue empty?", not queue)  # False

# 5. 队列大小
print("Queue size:", len(queue))  # 2

高效队列用 deque 实现。

queue = deque()

queue.append("A")  # 入队
queue.append("B")
queue.append("C")
print(queue.popleft())  # 出队，返回 'A'
print(queue)  # deque(['B', 'C'])

双端队列（Deque，Double-Ended Queue）

• 两端插入和删除都是 $O(1)$ 的时间复杂度（比 list.pop(0) 快）
• 适用于队列和栈的双重需求

方法	说明
deque.append(x)	右端入队（等同于 list.append(x)）
deque.appendleft(x)	左端入队
deque.pop()	右端出队
deque.popleft()	左端出队
deque.extend(iterable)	批量右端入队
deque.extendleft(iterable)	批量左端入队（注意：会逆序插入）
deque.rotate(n)	循环右移 n 位（n 为负数则左移）
deque.reverse()	原地反转队列
deque.clear()	清空队列

from collections import deque

# 创建一个双端队列
dq = deque([1, 2, 3])

# 1. 右端入队
dq.append(4) # deque([1, 2, 3, 4])

# 2. 左端入队
dq.appendleft(0) # deque([0, 1, 2, 3, 4])

# 3. 右端出队
dq.pop() # deque([0, 1, 2, 3])

# 4. 左端出队
dq.popleft() # deque([1, 2, 3])

# 5. 扩展队列（右侧）
dq.extend([4, 5]) # deque([1, 2, 3, 4, 5]) 

# 6. 扩展队列（左侧，逆序插入）
dq.extendleft([-1, -2]) # deque([-2, -1, 1, 2, 3, 4, 5])

# 7. 旋转（循环右移2位）
dq.rotate(2) # deque([4, 5, -2, -1, 1, 2, 3])

# 8. 旋转（循环左移1位）
dq.rotate(-1) # deque([5, -2, -1, 1, 2, 3, 4])

# 9. 反转队列
dq.reverse() # deque([4, 3, 2, 1, -1, -2, 5])

# 10. 清空队列
dq.clear() # deque([])

优先队列（Priority Queue）/ 最小堆

优先队列是一种 按照优先级顺序存储元素 的数据结构，Python 提供 heapq 模块来实现 最小堆（Min-Heap），默认情况下 最小值优先出队。

• 元素按照优先级排序，默认最小值优先
• 插入和删除的时间复杂度为 $O(logn)$
• 适用于任务调度、路径搜索（Dijkstra 算法）等

方法	说明
heapq.heappush(heap, x)	入队（x 加入 heap 并保持最小堆）
heapq.heappop(heap)	出队（移除并返回最小元素）
heapq.heappushpop(heap, x)	先入队，再出队最小值（比 push+pop 快）
heapq.heapify(iterable)	将列表转换为最小堆
heapq.nlargest(n, heap)	获取前 n 个最大元素（不会改变堆）
heapq.nsmallest(n, heap)	获取前 n 个最小元素（不会改变堆）

import heapq

# 创建一个空的优先队列（最小堆）
pq = []

# 1. 入队
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 2)
print("After heappush:", pq)  # [1, 2, 4, 3] (最小值在前)

# 2. 出队（返回最小值）
min_item = heapq.heappop(pq)
print("heappop():", min_item)  # 1
print("After heappop:", pq)  # [2, 3, 4]

# 3. 批量建堆
nums = [9, 5, 7, 2, 6]
heapq.heapify(nums)  # 直接转换成最小堆
print("heapify():", nums)  # [2, 5, 7, 9, 6] (2 最小)

# 4. 先入队再出队最小值（比 heappush+heappop 效率高）
result = heapq.heappushpop(pq, 0)
print("heappushpop(0):", result)  # 0
print("After heappushpop:", pq)  # [2, 3, 4]

# 5. 获取前 n 个最大/最小元素
largest = heapq.nlargest(2, pq)
smallest = heapq.nsmallest(2, pq)
print("nlargest(2):", largest)  # [4, 3]
print("nsmallest(2):", smallest)  # [2, 3]

非线性结构（Non-Linear Structures）

• 数据 非顺序存储
• 适用于 查找、关联映射、层级关系

1. 哈希表

数据结构	说明	适用场景
字典（Dict）	键值对存储，O(1) 查询	索引、缓存、数据存储
集合（Set）	无序、不重复，O(1) 查询	去重、集合运算

哈希表（Hash Table）/ 哈希映射（Hash Map）特点：

• 通过 键值对（key-value） 存储数据
• 平均 O(1) 的查找、插入和删除
• Python 的 dict 本质上是一个 哈希表

hash_map = {}  # 或 hash_map = dict()
hash_map["name"] = "Alice"
hash_map["age"] = 25
print(hash_map["name"])  # Alice
print(hash_map.get("age", "Not Found"))  # 25

字典（Dictionary）

• 键值对存储（Key-Value）：类似 JavaScript 的对象。
• 无序（Python 3.6 之前），有序（Python 3.7+）：Python 3.7+ 中，字典保持插入顺序。
• 键唯一：不能有重复的键。

方法	说明
dict.keys()	返回 所有键 的 dict_keys 视图
dict.values()	返回 所有值 的 dict_values 视图
dict.items()	返回 键值对 的 dict_items 视图
dict.get(key, default)	返回 key 对应的值，若 key 不存在返回 default
dict.pop(key, default)	删除 key 并返回对应的值，若 key 不存在返回 default
dict.popitem()	随机删除并返回（Python 3.7+ 为删除最后插入的键值对）
dict.update(other_dict)	合并字典，若 key 已存在，则覆盖其值
dict.setdefault(key, default)	获取 key 对应的值，若 key 不存在，则添加 default
dict.clear()	清空 字典
dict.copy()	返回字典的 浅拷贝

完整示例：

my_dict = {"name": "Alice", "age": 25, "city": "New York"} # 创建一个字典

# 1. keys() - 获取所有键
print("keys():", my_dict.keys())  # dict_keys(['name', 'age', 'city'])

# 2. values() - 获取所有值
print("values():", my_dict.values())  # dict_values(['Alice', 25, 'New York'])

# 3. items() - 获取所有键值对
print("items():", my_dict.items())  
# dict_items([('name', 'Alice'), ('age', 25), ('city', 'New York')])

# 4. get() - 获取键的值（若不存在返回默认值）
print("get('age'):", my_dict.get("age"))  # 25
print("get('gender', 'Not Found'):", my_dict.get("gender", "Not Found"))  # 'Not Found'

# 5. pop() - 删除指定键并返回其值
age = my_dict.pop("age")
print("pop('age'):", age, my_dict)  # 25 {'name': 'Alice', 'city': 'New York'}

# 6. popitem() - 删除并返回最后插入的键值对（Python 3.7+）
last_item = my_dict.popitem() 
print("popitem():", last_item, my_dict)  # ('city', 'New York') {'name': 'Alice'}

# 7. update() - 合并另一个字典
my_dict.update({"gender": "Female", "age": 26}) # {'name': 'Alice', 'gender': 'Female', 'age': 26}

# 8. setdefault() - 获取 key 的值，若 key 不存在，则赋默认值
print("setdefault('city', 'Los Angeles'):", my_dict.setdefault("city", "Los Angeles")) # Los Angeles
print("After setdefault:", my_dict) # {'name': 'Alice', 'gender': 'Female', 'age': 26, 'city': 'Los Angeles'}

# 9. copy() - 复制字典
copy_dict = my_dict.copy()  # {'name': 'Alice', 'gender': 'Female', 'age': 26, 'city': 'Los Angeles'}

# 10. clear() - 清空字典
my_dict.clear() # {}

集合（Set）

• 无序（Unordered）：元素没有固定的顺序。
• 不允许重复元素（Unique）。
• 支持集合运算（交集、并集、差集等）。

方法	说明
set.add(x)	添加元素 x 到集合
set.remove(x)	删除元素 x，如果 x 不存在，则抛出 KeyError
set.discard(x)	删除元素 x，如果 x 不存在，不报错
set.pop()	随机删除 并返回一个元素（由于无序性，不确定删除哪个）
set.clear()	清空集合
set.copy()	复制集合
set.update(iterable)	用可迭代对象 扩展集合
set.union(other_set)	并集（返回新集合）
set.intersection(other_set)	交集（返回新集合）
set.difference(other_set)	差集（返回新集合）
set.symmetric_difference(other_set)	对称差集（返回新集合）
set.issubset(other_set)	判断是否为 子集（返回 True/False）
set.issuperset(other_set)	判断是否为 超集（返回 True/False）
set.isdisjoint(other_set)	判断两个集合是否 无交集（返回 True/False）

完整示例：

# 创建集合
my_set = {1, 2, 3, 4, 5}
another_set = {3, 4, 5, 6, 7}

print(my_set & another_set)  # 交集 {3, 4, 5}
print(my_set | another_set)  # 并集 {1, 2, 3, 4, 5, 6, 7}

# 1. add() - 添加元素
my_set.add(6) # {1, 2, 3, 4, 5, 6}

# 2. remove() - 删除元素（不存在会报错）
my_set.remove(6) # {1, 2, 3, 4, 5}

# 3. discard() - 删除元素（不存在不会报错）
my_set.discard(10)  # 无影响 {1, 2, 3, 4, 5}

# 4. pop() - 随机删除一个元素
popped_item = my_set.pop() # 可能删除 1, 2, 3, 4, 5 中的任意一个
print("pop():", popped_item, my_set) # 1 {2, 3, 4, 5}  (结果可能不同)

# 5. clear() - 清空集合
my_set.clear() # set()

# 6. copy() - 复制集合
copy_set = another_set.copy() # {3, 4, 5, 6, 7}

# 7. update() - 用另一个集合扩展
my_set.update([1, 2, 3]) # {1, 2, 3}

# 8. union() - 并集
union_set = my_set.union(another_set) # {1, 2, 3, 4, 5, 6, 7}

# 9. intersection() - 交集
intersection_set = my_set.intersection(another_set) # {3}

# 10. difference() - 差集（存在于 my_set 但不存在于 another_set）
difference_set = my_set.difference(another_set) # {1, 2}

# 11. symmetric_difference() - 对称差集（只在其中一个集合中存在）
symmetric_diff_set = my_set.symmetric_difference(another_set) # {1, 2, 4, 5, 6, 7}

# 12. issubset() - 判断是否为子集
print("issubset(another_set):", {3}.issubset(my_set))  # True

# 13. issuperset() - 判断是否为超集
print("issuperset({3}):", my_set.issuperset({3}))  # True

# 14. isdisjoint() - 判断是否无交集
print("isdisjoint({10, 11}):", my_set.isdisjoint({10, 11}))  # True

2. 树结构

数据结构	说明	适用场景
二叉树（Binary Tree）	每个节点最多两个子节点	表达式解析、层次遍历
二叉搜索树（BST）	有序存储，O(log n) 查询	排序、搜索
AVL 树 / 红黑树	自平衡二叉搜索树，O(log n) 操作	数据库索引、C++ map/set
Trie（字典树）	字符串前缀存储，O(m) 查询	搜索引擎、拼写检查

二叉树（Binary Tree）

二叉树 (Binary Tree)，是一种 每个节点最多有两个子节点 的数据结构。二叉树并 没有对节点值的排列做任何特殊限制。

二叉查找树 是二叉树的一种特例，它要求节点的值必须满足如下条件：

• 对于任何节点 node，node 的左子树中的所有节点值都比 node 的值小。
• 对于任何节点 node，node 的右子树中的所有节点值都比 node 的值大。

这种排列使得查找、插入和删除操作能以 $O(logn)$ 的时间复杂度进行（在树平衡的情况下）。

平衡二叉树（AVL 树 / 红黑树）

• 自平衡 的二叉搜索树，确保 O(log n) 查找、插入、删除
• Python sortedcontainers 库可以用于 平衡树结构
• Python 的 dict 和 set 底层使用哈希表，但 C++ 的 map/set 是 红黑树

sortedcontainers 是一个第三方库，提供了高效的排序容器，支持自动平衡。这个库实现了 平衡二叉树（如 AVL 树 / 红黑树） 的功能，允许 O(log n) 的插入、删除和查找操作。

方法	说明
SortedList	类似于列表，但元素始终保持排序。
add(value)	向 SortedList 中添加一个元素，并保持排序。
remove(value)	从 SortedList 中移除一个元素。
bisect_left(value)	查找元素插入的位置，返回第一个大于等于 value 的索引位置。
bisect_right(value)	查找元素插入的位置，返回第一个严格大于 value 的索引位置。
index(value)	返回 value 元素的索引位置，如果不存在则抛出异常。
__getitem__(index)	获取指定索引处的元素。
__delitem__(index)	删除指定索引处的元素。
__contains__(value)	判断元素是否在 SortedList 中。
pop(index)	弹出指定索引处的元素，删除并返回该元素。
__iter__()	迭代遍历 SortedList 中的元素。
__len__()	返回 SortedList 中的元素个数。

from sortedcontainers import SortedList

# 创建一个 SortedList 对象
sorted_list = SortedList()

# 1. 向 SortedList 中添加元素
sorted_list.add(10)
sorted_list.add(5)
sorted_list.add(20)
sorted_list.add(15)

print("SortedList after adding elements:")
print(sorted_list)  # SortedList([5, 10, 15, 20])

# 2. 从 SortedList 中删除元素
sorted_list.remove(10)
print("SortedList after removing 10:")
print(sorted_list)  # SortedList([5, 15, 20])

# 3. 查找元素的索引位置
print("Index of 15:", sorted_list.index(15))  # 1

# 4. 查找元素的插入位置 (返回插入位置)
print("Bisect left for 12:", sorted_list.bisect_left(12))  # 1
print("Bisect right for 12:", sorted_list.bisect_right(12))  # 2

# 5. 判断元素是否存在
print("Does SortedList contain 15?", 15 in sorted_list)  # True
print("Does SortedList contain 10?", 10 in sorted_list)  # False

# 6. 获取指定索引的元素
print("Element at index 1:", sorted_list[1])  # 15

# 7. 弹出指定索引处的元素
popped_element = sorted_list.pop(1)
print("Popped element:", popped_element)  # 15
print("SortedList after pop:")
print(sorted_list)  # SortedList([5, 20])

# 8. 迭代遍历 SortedList
print("Iterating over SortedList:")
for item in sorted_list:
    print(item, end=" ")  # 5 20

# 9. 获取元素的个数
print("\nNumber of elements in SortedList:", len(sorted_list))  # 2

Trie（字典树 / 前缀树）

• 用于 高效的字符串查找（如自动补全、字典存储）
• 查找时间复杂度为 O(m)（m 是字符串长度）
• 适用于 搜索引擎、字典匹配、DNA 序列匹配

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

trie = Trie()
trie.insert("hello")
print(trie.search("hello"))  # True
print(trie.search("hell"))   # False

3. 图（Graph）

• 由顶点（Nodes） 和 边（Edges） 组成
• 可以是 有向图 / 无向图，支持 加权 / 无权
• 广泛用于社交网络、地图导航、网络路由等

数据结构	说明	适用场景
邻接表（Adjacency List）	用 dict 存储邻接关系	社交网络、地图路径
邻接矩阵（Adjacency Matrix）	用 list[list] 存储连接关系	稠密图、动态规划
并查集（Union-Find）	快速合并 & 查找集合	连通性检测、最小生成树（MST）

networkx 图论库

方法	说明
Graph()	创建一个空的无向图
add_node(node)	向图中 添加一个节点
add_nodes_from(nodes)	向图中 添加多个节点
add_edge(u, v, weight=w)	向图中 添加一条边，（从节点 u 到节点 v），权重为 w （可选）
add_edges_from(ebunch, weight=w)	向图中 添加多条边，所有边的权重为 w（可选）
remove_node(node)	删除一个节点（删除节点及其相关边）
remove_edge(u, v)	删除一条边
has_node(node)	判断图中是否包含节点 node
has_edge(u, v)	判断图中是否包含从 u 到 v 的边
nodes()	返回图中 所有节点
edges(data=True)	返回图中 所有边，data=True 包括权重（可选）
get_edge_data(u, v)	获取从 u 到 v 的 边的属性，包括权重
set_edge_attributes(G, values, name='weight')	设置图 G 中所有边的 权重（或其他属性）
degree(node)	返回节点 node 的 度数（连接到该节点的边的数目）
neighbors(n)	返回节点 n 的 所有邻居节点
adjacency()	返回图的 邻接列表
shortest_path(source, target, weight='weight')	返回从 source 到 target 的 最短路径（权重可选）
shortest_path_length(source, target, weight='weight')	返回从 source 到 target 的 最短路径长度（权重可选）
diameter()	返回图的 直径（最长最短路径的长度）
center()	返回图的 中心节点（距离最远节点最短的节点）
closeness_centrality(node)	返回节点 node 的 接近中心性
betweenness_centrality(node)	返回节点 node 的 介数中心性
pagerank()	返回图的 PageRank 值
is_connected()	判断图是否 连通
draw()	绘制图的 可视化（需要 Matplotlib）
draw_networkx_edge_labels()	在绘图时 显示边的权重
subgraph(nodes)	返回一个包含指定节点的 子图
set_edge_attributes(G, values, name='weight')	设置边的属性（例如权重）

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个无向图
G = nx.Graph()

# 1. 添加带权重的单条边
G.add_edge(1, 2, weight=4.2)

# 2. 添加带权重的多条边
G.add_edges_from([(2, 3, {'weight': 2.5}), (3, 4, {'weight': 7.1})])

# 3. 打印所有边及其属性（包括权重）
print("Edges with weights:", G.edges(data=True))  
# 输出: Edges with weights: [(1, 2, {'weight': 4.2}), (2, 3, {'weight': 2.5}), (3, 4, {'weight': 7.1})]

# 4. 获取指定边的权重
edge_weight = G[1][2]['weight']
print("Weight of edge (1, 2):", edge_weight)  # 输出: Weight of edge (1, 2): 4.2

# 5. 修改某条边的权重
G[1][2]['weight'] = 9.0
print("Updated weight of edge (1, 2):", G[1][2]['weight'])  # 输出: Updated weight of edge (1, 2): 9.0

# 6. 获取某条边的所有属性
edge_data = G.get_edge_data(1, 2)
print("Edge data for (1, 2):", edge_data)  # 输出: Edge data for (1, 2): {'weight': 9.0}

# 7. 获取所有带属性的边（包括权重）
print("All edges with data:", list(G.edges(data=True))) 
# 输出: All edges with data: [(1, 2, {'weight': 9.0}), (2, 3, {'weight': 2.5}), (3, 4, {'weight': 7.1})]

# 8. 获取图的最短路径（带权重）
shortest_path = nx.shortest_path(G, source=1, target=4, weight='weight')
print("Shortest path from 1 to 4:", shortest_path)  # 输出: Shortest path from 1 to 4: [1, 2, 3, 4]

# 9. 获取图的最短路径长度（带权重）
shortest_path_length = nx.shortest_path_length(G, source=1, target=4, weight='weight')
print("Shortest path length from 1 to 4:", shortest_path_length)  # 输出: Shortest path length from 1 to 4: 18.8

# 10. 绘制带权重的图
pos = nx.spring_layout(G)
labels = nx.get_edge_attributes(G, 'weight')  # 获取边的权重
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=15)
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
plt.show()

# 11. 获取图的直径
# 直径是图中最长的最短路径的长度
print("Diameter of the graph:", nx.diameter(G))  # 输出: Diameter of the graph: 2

# 12. 获取图的中心节点
print("Center of the graph:", nx.center(G))  # 输出: Center of the graph: [2, 3]

# 13. 获取节点的接近中心性
print("Closeness centrality of node 2:", nx.closeness_centrality(G, 2))  # 输出接近中心性

# 14. 获取节点的介数中心性
print("Betweenness centrality of node 2:", nx.betweenness_centrality(G)[2])  # 输出节点 2 的介数中心性

# 15. 获取 PageRank 值
print("PageRank values:", nx.pagerank(G))  # 输出节点的 PageRank 值

# 16. 获取子图
subgraph = G.subgraph([1, 2, 3])
print("Subgraph nodes:", subgraph.nodes())  # 输出: Subgraph nodes: [1, 2, 3]

并查集（Union-Find）

• 高效合并（Union）和查找（Find），用于动态连通性问题
• 主要用于 图的连通性检测、最小生成树（Kruskal）、网络连接等
• 路径压缩 + 按秩合并 可以优化到 O(α(n)) ≈ O(1)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def 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:
            self.parent[rootX] = rootY  # 合并集合

uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2))  # True（0 和 2 连接在一起）

特殊结构

数据结构	说明	适用场景
跳表（Skip List）	O(log n) 查询，链表+多级索引	有序集合（Redis）、区间查询
布隆过滤器（Bloom Filter）	概率型结构，快速检测元素是否存在	黑名单过滤、去重
LRU 缓存（Least Recently Used Cache）	自动移除最久未使用的数据	网页缓存、CPU缓存

跳表（Skip List）

• 通过 多层链表结构 提供 O(log n) 搜索，类似于平衡二叉树
• 建立 多层次的索引，允许在 每一层上进行跳跃式的查找
• 用于 高效的区间查询、排序数据结构
• Redis 的 有序集合（SortedSet） 采用 跳表实现

方法	说明
insert(value)	插入值为 value 的新节点。
search(value)	查找值为 value 的节点，若存在返回节点，否则返回 None。
delete(value)	删除值为 value 的节点。
random_level()	生成一个随机层级，用于决定新节点的高度。
print_list()	打印跳表的层次结构。

import random

class Node:  # 节点类 (Node)：每个节点有多个指针（表示跳跃层级）
    def __init__(self, value, level):
        self.value = value  # 节点值
        self.forward = [None] * (level + 1)  # forward[i]是指向第i层的下一个节点

class SkipList:  # 跳表类 (SkipList)：包含插入、查找和删除等操作
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level  # 最大层数
        self.p = p  # 节点升层概率
        self.header = Node(None, self.max_level)  # 跳表头节点
        self.level = 0  # 当前跳表的层数

    def random_level(self):
        level = 0
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level

    def insert(self, value):
        update = [None] * (self.max_level + 1)  # 记录查找路径
        current = self.header
        
        # 从跳表的最高层开始查找
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        # 如果找到了相同的值，则不插入
        if current and current.value == value:
            return
        
        # 否则插入新节点
        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header
            self.level = new_level
        
        new_node = Node(value, new_level)
        
        # 在各个层级插入新节点
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, value):
        current = self.header
        # 从最高层开始查找
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
        current = current.forward[0]
        
        return current if current and current.value == value else None

    def delete(self, value):
        update = [None] * (self.max_level + 1)
        current = self.header
        
        # 查找节点并更新路径
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].value < value:
                current = current.forward[i]
            update[i] = current
        
        current = current.forward[0]
        
        # 如果节点存在，删除节点
        if current and current.value == value:
            for i in range(self.level + 1):
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]
            
            # 如果最高层的节点没有节点，更新跳表的层数
            while self.level > 0 and not self.header.forward[self.level]:
                self.level -= 1

    def print_list(self):
        for i in range(self.level + 1):
            current = self.header.forward[i]
            print(f"Level {i}: ", end="")
            while current:
                print(current.value, end=" -> ")
                current = current.forward[i]
            print("None")

# 测试跳表
skip_list = SkipList()

# 插入元素
skip_list.insert(3)
skip_list.insert(6)
skip_list.insert(7)
skip_list.insert(9)
skip_list.insert(12)
skip_list.insert(19)
skip_list.insert(17)

# 打印跳表
skip_list.print_list()

# 查找元素
print(skip_list.search(6))  # <__main__.Node object at 0x7f856fc748b0>
print(skip_list.search(15))  # None

# 删除元素
skip_list.delete(6)
skip_list.print_list()

Bloom Filter（布隆过滤器）

• 高效存储和检测集合中的元素，但可能产生误判（可能会错误地认为某个元素存在）
• 适用于 去重、黑名单检测
• 不能 删除元素
• 用于 Google Chrome 安全浏览、Redis 缓存去重

• 每个元素通过多个哈希函数计算出多个哈希值，将这些哈希值对应的位数组位置标记为 True。
• 查询时，再次通过哈希函数计算出这些位置，若所有位置均为 True，则认为元素可能存在；若 有任一位置为 False，则元素肯定不存在。

方法	说明
add(item)	将元素 item 添加到布隆过滤器中。
contains(item)	检查元素 item 是否在布隆过滤器中，返回 True 或 False。

import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size  # 位数组的大小
        self.num_hashes = num_hashes  # 哈希函数的数量
        self.bit_array = [False] * size  # 初始化位数组为False

    def _hash(self, item, seed):
        """ 基于给定种子的哈希函数 """
        return int(hashlib.md5((str(seed) + item).encode()).hexdigest(), 16) % self.size

    def add(self, item):
        """ 添加元素到布隆过滤器 """
        for i in range(self.num_hashes):
            index = self._hash(item, i)
            self.bit_array[index] = True

    def contains(self, item):
        """ 检查元素是否在布隆过滤器中 """
        for i in range(self.num_hashes):
            index = self._hash(item, i)
            if not self.bit_array[index]:  # 如果有任何一个哈希位置为False，则元素不在集合中
                return False
        return True

# 测试布隆过滤器
bloom = BloomFilter(size=1000, num_hashes=5)

# 添加元素
bloom.add("apple")
bloom.add("banana")
bloom.add("cherry")

# 查询元素
print(bloom.contains("apple"))  # True
print(bloom.contains("banana"))  # True
print(bloom.contains("orange"))  # False (可能为False, 但也可能是误判)

LRU 缓存（Least Recently Used Cache）

• 最近最少使用，即 使用频率最低的元素最先被淘汰
• Python functools.lru_cache 提供了现成实现
• 适用于缓存系统，如 CPU 缓存、网页缓存

示例（使用 OrderedDict 实现 LRU 缓存）：

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # 最近使用的移到末尾
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 移除最久未使用的元素

lru = LRUCache(2)
lru.put(1, "A")
lru.put(2, "B")
print(lru.get(1))  # "A"
lru.put(3, "C")  # 2 被移除
print(lru.get(2))  # -1（缓存淘汰）

总结：如何选择数据结构？

• 需要快速查询？ → 哈希表（dict）、集合（set）、Trie
• 需要顺序存储？ → list（动态数组）、tuple
• 需要按顺序处理？ → 栈（LIFO）、队列（FIFO）、优先队列
• 需要排序查找？ → 二叉搜索树（BST）、跳表
• 需要高效合并？ → 并查集
• 需要图结构？ → 邻接表、邻接矩阵
• 需要去重检测？ → 布隆过滤器
• 需要缓存管理？ → LRU 缓存

数据结构	可变性	有序性	是否允许重复元素	典型应用
列表（List）	可变	有序	允许	适合存储 序列 数据
元组（Tuple）	不可变	有序	允许	适合存储 固定 数据
字典（Dictionary）	可变	有序（3.7+）	键不能重复	映射关系（Key-Value） 存储
集合（Set）	可变	无序	不允许	去重、集合 运算
栈（Stack）	可变	有序	允许	后进先出（LIFO）
队列（Queue）	可变	有序	允许	先进先出（FIFO）