目录
1. 数组（Array）
2. 链表（Linked List）
3. 栈（Stack）
4. 队列（Queue）
5. 哈希表（Hash Table）
6. 树（Tree）
7. 图（Graph）
1. 数组（Array）
- 特点：连续的内存空间，支持快速随机访问。
- 适用场景：需要频繁读取数据，但对插入、删除操作要求不高。
示例：使用列表实现数组
# 定义一个数组
array = [10, 20, 30, 40]# 访问元素
print(array[2]) # 输出：30# 插入元素
array.insert(2, 25) # 在索引2位置插入25
print(array) # 输出：[10, 20, 25, 30, 40]# 删除元素
array.pop(2) # 删除索引2位置的元素
print(array) # 输出：[10, 20, 30, 40]
2. 链表（Linked List）
- 特点：通过指针将一组节点连接起来，分为单链表和双链表。
- 适用场景：插入和删除频繁，但随机访问不常用。
示例：实现单链表
class Node:def __init__(self, value):self.value = valueself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, value):new_node = Node(value)if not self.head:self.head = new_nodereturncurrent = self.headwhile current.next:current = current.nextcurrent.next = new_nodedef display(self):current = self.headwhile current:print(current.value, end=" -> ")current = current.nextprint("None")# 创建链表并操作
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display() # 输出：10 -> 20 -> 30 -> None
3. 栈（Stack）
- 特点：后进先出（LIFO），只能从栈顶操作。
- 适用场景：递归处理、括号匹配、函数调用等。
示例：用列表实现栈
stack = []# 压入栈
stack.append(10)
stack.append(20)
stack.append(30)# 弹出栈
print(stack.pop()) # 输出：30
print(stack) # 输出：[10, 20]
4. 队列（Queue）
- 特点：先进先出（FIFO）。
- 适用场景：任务调度、消息传递。
示例：用 collections.deque 实现队列
from collections import dequequeue = deque()# 入队
queue.append(10)
queue.append(20)
queue.append(30)# 出队
print(queue.popleft()) # 输出：10
print(queue) # 输出：deque([20, 30])
5. 哈希表（Hash Table）
- 特点：通过哈希函数实现快速查找、插入。
- 适用场景：需要高效的键值对存储和查找。
示例：用字典实现哈希表
hash_table = {}# 插入键值对
hash_table['name'] = 'Alice'
hash_table['age'] = 25# 访问元素
print(hash_table['name']) # 输出：Alice# 删除键值对
del hash_table['age']
print(hash_table) # 输出：{'name': 'Alice'}
6. 树（Tree）
- 特点：层次结构的数据结构，每个节点有子节点。
- 适用场景：搜索、排序、层次分类。
示例：实现二叉树
class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef inorder_traversal(node):if not node:returninorder_traversal(node.left)print(node.value, end=" ")inorder_traversal(node.right)# 创建二叉树
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)# 遍历
inorder_traversal(root) # 输出：5 10 15
7. 图（Graph）
- 特点：节点通过边连接，可以是有向或无向。
- 适用场景：网络连接、最短路径、推荐系统。
示例：用邻接表表示图
graph = {'A': ['B', 'C'],'B': ['A', 'D'],'C': ['A', 'D'],'D': ['B', 'C']
}# 深度优先搜索
def dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start, end=" ")for neighbor in graph[start]:if neighbor not in visited:dfs(graph, neighbor, visited)dfs(graph, 'A') # 输出：A B D C
