Python常用算法与数据结构
Python 常用数据结构
列表（List）
列表是 Python 中最常用的数据结构之一，它是一种有序的可变序列。可以通过方括号 [] 来创建列表，其中的元素用逗号分隔。
示例代码：
my_list = [1, 2, 3, 'apple', 4.5]
print(my_list)
在上述代码中，我们创建了一个包含整数、字符串和浮点数的列表。
列表支持多种操作，如索引、切片、添加元素、删除元素等。
索引操作：
my_list = [1, 2, 3, 'apple', 4.5]
print(my_list[0]) # 输出第一个元素，结果为 1
print(my_list[-1]) # 输出最后一个元素，结果为 4.5
索引从 0 开始，负数索引表示从列表末尾开始计数。
切片操作：
my_list = [1, 2, 3, 'apple', 4.5]
print(my_list[1:3]) # 输出从索引 1 到索引 3 之前的元素，结果为 [2, 3]
print(my_list[:3]) # 输出从开头到索引 3 之前的元素，结果为 [1, 2, 3]
print(my_list[3:]) # 输出从索引 3 到末尾的元素，结果为 ['apple', 4.5]
切片操作返回一个新的列表，原列表不变。
添加元素：
my_list = [1, 2, 3]
my_list.append(4) # 在列表末尾添加元素 4
print(my_list)
my_list.insert(1, 'new') # 在索引 1 处插入元素 'new'
print(my_list)
append 方法在列表末尾添加单个元素，insert 方法在指定索引位置插入元素。
删除元素：
my_list = [1, 2, 3, 'apple', 4.5]
del my_list[2] # 删除索引 2 处的元素
print(my_list)
removed = my_list.pop(1) # 删除索引 1 处的元素并返回该元素
print(removed)
print(my_list)
my_list.remove('apple') # 删除值为 'apple' 的元素
print(my_list)
del 语句用于删除指定索引处的元素，pop 方法删除指定索引处的元素并返回该元素，remove 方法删除第一个值匹配的元素。
元组（Tuple）
元组是一种有序的不可变序列，用圆括号 () 来创建，元素之间用逗号分隔。
示例代码：
my_tuple = (1, 2, 3, 'apple')
print(my_tuple)
元组一旦创建，其元素就不能被修改。但如果元组中包含可变对象，如列表，那么可变对象内部可以被修改。
示例：
my_tuple = (1, [2, 3], 4)
my_tuple[1].append(5)
print(my_tuple)
这里元组中的列表被修改了，而元组本身的结构并未改变。
元组支持索引和切片操作，与列表类似。
my_tuple = (1, 2, 3, 'apple')
print(my_tuple[0]) # 输出第一个元素，结果为 1
print(my_tuple[1:3]) # 输出从索引 1 到索引 3 之前的元素，结果为 (2, 3)
集合（Set）
集合是一种无序的、不包含重复元素的数据结构，用花括号 {} 或者 set() 函数来创建。
示例代码：
my_set = {1, 2, 3, 3}
print(my_set) # 输出 {1, 2, 3}，重复元素被自动去除
集合支持多种集合操作，如并集、交集、差集等。
并集：
set1 = {1, 2, 3}
set2 = {3, 4, 5}
union_set = set1.union(set2)
print(union_set) # 输出 {1, 2, 3, 4, 5}
交集：
set1 = {1, 2, 3}
set2 = {3, 4, 5}
intersection_set = set1.intersection(set2)
print(intersection_set) # 输出 {3}
差集：
set1 = {1, 2, 3}
set2 = {3, 4, 5}
difference_set = set1.difference(set2)
print(difference_set) # 输出 {1, 2}
集合也支持添加和删除元素的操作。
添加元素：
my_set = {1, 2, 3}
my_set.add(4)
print(my_set) # 输出 {1, 2, 3, 4}
删除元素：
my_set = {1, 2, 3}
my_set.remove(2)
print(my_set) # 输出 {1, 3}
如果要删除的元素不存在，remove 方法会引发 KeyError 异常。可以使用 discard 方法，它在元素不存在时不会引发异常。
my_set = {1, 3}
my_set.discard(2)
print(my_set) # 输出 {1, 3}，不会引发异常
字典（Dictionary）
字典是一种无序的键值对（key - value）数据结构，用花括号 {} 创建，键和值之间用冒号 : 分隔，键值对之间用逗号 , 分隔。
示例代码：
my_dict = {'name': 'John', 'age': 30, 'city': 'New York'}
print(my_dict)
字典中的键必须是唯一且不可变的，通常使用字符串、数字或元组作为键。值可以是任意类型。
访问字典的值：
my_dict = {'name': 'John', 'age': 30, 'city': 'New York'}
print(my_dict['name']) # 输出 'John'
如果访问不存在的键，会引发 KeyError 异常。可以使用 get 方法，它在键不存在时返回 None 或者指定的默认值。
my_dict = {'name': 'John', 'age': 30}
print(my_dict.get('city')) # 输出 None
print(my_dict.get('city', 'Unknown')) # 输出 'Unknown'
添加和修改键值对：
my_dict = {'name': 'John', 'age': 30}
my_dict['city'] = 'New York' # 添加新的键值对
my_dict['age'] = 31 # 修改已存在键的值
print(my_dict)
删除键值对：
my_dict = {'name': 'John', 'age': 30, 'city': 'New York'}
del my_dict['city'] # 删除 'city' 键值对
print(my_dict)
removed_value = my_dict.pop('age') # 删除 'age' 键值对并返回值
print(removed_value)
print(my_dict)
Python 常用算法
排序算法
冒泡排序（Bubble Sort） 冒泡排序是一种简单的比较排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码示例：
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))
时间复杂度：冒泡排序的时间复杂度为 (O(n^2))，其中 (n) 是待排序元素的数量。在最坏和平均情况下，它都需要比较和交换 (n(n - 1)/2) 次。在最好情况下（数组已经有序），它只需要比较 (n - 1) 次，时间复杂度为 (O(n))。
选择排序（Selection Sort） 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
算法步骤：
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
代码示例：
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(arr))
时间复杂度：选择排序的时间复杂度为 (O(n^2))，无论在最好、最坏还是平均情况下，它都需要比较 (n(n - 1)/2) 次。因为每次选择最小（大）元素时，都需要遍历剩余未排序的元素。
插入排序（Insertion Sort） 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤：
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤 2 到 5。
代码示例：
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(arr))
时间复杂度：在最坏情况下，插入排序的时间复杂度为 (O(n^2))，当数组是逆序时，每次插入都需要比较和移动前面所有的元素。在最好情况下（数组已经有序），时间复杂度为 (O(n))，因为只需要比较 (n - 1) 次，不需要移动元素。平均情况下时间复杂度也是 (O(n^2))。
快速排序（Quick Sort） 快速排序是一种分治算法。它采用了一种高效的策略，通过选择一个基准元素，将数组分为两部分，左边部分的元素都小于基准元素，右边部分的元素都大于基准元素，然后分别对左右两部分进行递归排序。
算法步骤：
- 从数列中挑出一个元素，称为 “基准”（pivot）。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码示例：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(arr))
时间复杂度：在平均情况下，快速排序的时间复杂度为 (O(n log n))，其中 (n) 是待排序元素的数量。在最坏情况下（例如每次选择的基准都是最大或最小元素），时间复杂度会退化为 (O(n^2))。但通过合理选择基准元素（如随机选择或使用三数取中方法），可以尽量避免最坏情况的发生。
查找算法
线性查找（Linear Search） 线性查找是一种最简单的查找算法。它从列表的第一个元素开始，逐个检查元素，直到找到目标元素或者遍历完整个列表。
算法步骤：
- 从列表的第一个元素开始。
- 检查当前元素是否是目标元素。
- 如果是，返回当前元素的索引。
- 如果不是，继续检查下一个元素。
- 重复步骤 2 到 4，直到找到目标元素或者遍历完整个列表。如果遍历完整个列表仍未找到目标元素，返回 -1。
代码示例：
def linear_search(arr, target):
for i, element in enumerate(arr):
if element == target:
return i
return -1
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target)) # 输出 2
时间复杂度：线性查找的时间复杂度为 (O(n))，其中 (n) 是列表中元素的数量。在最坏情况下，需要遍历整个列表才能确定目标元素是否存在。
二分查找（Binary Search） 二分查找是一种高效的查找算法，它要求列表必须是有序的。二分查找每次都将查找范围缩小一半。
算法步骤：
- 设定两个指针，一个指向列表的开头（left），一个指向列表的结尾（right）。
- 计算中间位置（mid），mid = (left + right) // 2。
- 比较中间位置的元素与目标元素。
- 如果中间元素等于目标元素，返回中间位置。
- 如果中间元素大于目标元素，将 right 指针移动到 mid - 1，继续在左半部分查找。
- 如果中间元素小于目标元素，将 left 指针移动到 mid + 1，继续在右半部分查找。
- 重复步骤 2 和 3，直到找到目标元素或者 left 大于 right（表示目标元素不存在）。
代码示例：
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
arr = [10, 20, 30, 40, 50]
target = 30
print(binary_search(arr, target)) # 输出 2
时间复杂度：二分查找的时间复杂度为 (O(log n))，其中 (n) 是列表中元素的数量。每次查找都将查找范围缩小一半，因此查找次数与列表长度的对数成正比。这使得二分查找在处理大规模有序数据时非常高效。
树相关算法
二叉树遍历 二叉树是一种重要的数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历（Pre - order Traversal）：
- 访问根节点。
- 前序遍历左子树。
- 前序遍历右子树。
代码示例（使用递归实现）：
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def pre_order_traversal(root):
if root:
print(root.value)
pre_order_traversal(root.left)
pre_order_traversal(root.right)
# 创建一个简单的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
pre_order_traversal(root)
中序遍历（In - order Traversal）：
- 中序遍历左子树。
- 访问根节点。
- 中序遍历右子树。
代码示例（使用递归实现）：
def in_order_traversal(root):
if root:
in_order_traversal(root.left)
print(root.value)
in_order_traversal(root.right)
in_order_traversal(root)
后序遍历（Post - order Traversal）：
- 后序遍历左子树。
- 后序遍历右子树。
- 访问根节点。
代码示例（使用递归实现）：
def post_order_traversal(root):
if root:
post_order_traversal(root.left)
post_order_traversal(root.right)
print(root.value)
post_order_traversal(root)
二叉搜索树（Binary Search Tree，BST）操作 二叉搜索树是一种特殊的二叉树，对于树中的每个节点，其左子树中的所有节点值都小于该节点值，右子树中的所有节点值都大于该节点值。
插入操作：
- 从根节点开始。
- 如果插入值小于当前节点值，向左子树移动；如果插入值大于当前节点值，向右子树移动。
- 当找到一个空位置（即叶子节点的子节点为空）时，插入新节点。
代码示例：
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if not root:
return TreeNode(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
values = [5, 3, 7, 2, 4, 6, 8]
for value in values:
root = insert(root, value)
查找操作：
- 从根节点开始。
- 如果查找值等于当前节点值，返回当前节点。
- 如果查找值小于当前节点值，向左子树移动；如果查找值大于当前节点值，向右子树移动。
- 重复步骤 2 和 3，直到找到目标节点或者到达空节点（表示未找到）。
代码示例：
def search(root, value):
if not root or root.value == value:
return root
if value < root.value:
return search(root.left, value)
return search(root.right, value)
found_node = search(root, 6)
if found_node:
print(f"找到节点，值为: {found_node.value}")
else:
print("未找到节点")
删除操作：删除操作相对复杂，需要考虑三种情况：
- 要删除的节点是叶子节点，直接删除。
- 要删除的节点只有一个子节点，将该子节点替代要删除的节点。
- 要删除的节点有两个子节点，找到其右子树中的最小节点（或左子树中的最大节点），用该节点的值替换要删除的节点的值，然后删除找到的这个节点（它必然属于前两种情况之一）。
代码示例：
def find_min(root):
while root.left:
root = root.left
return root
def delete(root, value):
if not root:
return root
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
temp = find_min(root.right)
root.value = temp.value
root.right = delete(root.right, temp.value)
return root
root = delete(root, 5)
图相关算法
深度优先搜索（Depth - First Search，DFS） 深度优先搜索是一种用于遍历或搜索图或树的算法。它从起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续或达到目标顶点，然后回溯到上一个节点，继续探索其他路径。
算法步骤（以邻接表表示图为例）：
- 从起始顶点开始，标记该顶点为已访问。
- 对于当前顶点的所有未访问邻接顶点，递归地进行深度优先搜索。
代码示例：
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
visited = set()
def dfs(vertex):
if vertex not in visited:
print(vertex)
visited.add(vertex)
for neighbor in graph[vertex]:
dfs(neighbor)
dfs('A')
时间复杂度：对于有 (V) 个顶点和 (E) 条边的图，使用邻接表表示时，深度优先搜索的时间复杂度为 (O(V + E))。因为每个顶点和每条边最多被访问一次。
广度优先搜索（Breadth - First Search，BFS） 广度优先搜索也是一种用于遍历或搜索图或树的算法。它从起始顶点开始，首先访问其所有邻接顶点，然后依次访问这些邻接顶点的邻接顶点，以此类推，一层一层地进行搜索。
算法步骤（以邻接表表示图为例）：
- 使用一个队列存储待访问的顶点。
- 从起始顶点开始，将其加入队列并标记为已访问。
- 当队列不为空时，取出队首顶点，访问它，并将其所有未访问邻接顶点加入队列并标记为已访问。
代码示例：
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
visited = set()
def bfs(start):
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
bfs('A')
时间复杂度：同样对于有 (V) 个顶点和 (E) 条边的图，使用邻接表表示时，广度优先搜索的时间复杂度为 (O(V + E))。因为每个顶点和每条边最多被访问一次。
迪杰斯特拉算法（Dijkstra's Algorithm） 迪杰斯特拉算法是一种用于在带权有向图中寻找从一个给定顶点到其他所有顶点的最短路径的算法。
算法步骤：
- 初始化：将起始顶点的距离设为 0，其他顶点的距离设为无穷大。创建一个优先队列（最小堆）用于存储顶点及其距离。
- 从优先队列中取出距离最小的顶点 (u)。
- 对于 (u) 的所有邻接顶点 (v)，如果通过 (u) 到 (v) 的距离小于当前 (v) 的距离，更新 (v) 的距离，并将 (v) 及其新距离加入优先队列。
- 重复步骤 2 和 3，直到优先队列为空。
代码示例：
import heapq
graph = {
'A': {'B': 10, 'C': 3},
'B': {'C': 1, 'D': 2},
'C': {'B': 4, 'D': 8, 'E': 2},
'D': {'E': 7},
'E': {'D': 9}
}
def dijkstra(graph, start):
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
distances = dijkstra(graph, 'A')
print(distances)
时间复杂度：使用优先队列（最小堆）实现时，迪杰斯特拉算法的时间复杂度为 (O((V + E) log V))，其中 (V) 是顶点数，(E) 是边数。每次从优先队列中取出最小距离顶点的时间为 (O(log V))，而对于每个顶点，最多需要将其邻接顶点加入优先队列一次，所以总时间复杂度为 (O((V + E) log V))。
通过对这些常用的数据结构和算法的学习，在 Python 编程中可以更高效地处理各种数据处理和问题求解的任务。无论是开发小型脚本还是大型复杂的应用程序，合理选择和运用数据结构与算法都是至关重要的。