【Python】进阶 - 数据结构与算法

系列篇章🎉

No.	文章
1	【Python】基础知识（详细）🚀
2	【Python】基础 - 循环、容器类型🚀
3	【Python】基础 - 推导式、函数🚀
4	【Python】基础 - 文件、异常、模块🚀
5	【Python】进阶 - 面向对象（详细）🚀
6	【Python】进阶 - 闭包、装饰器、深浅拷贝🚀
7	【Python】进阶 - 网络编程(TCP开发基础、进程和线程）🚀
8	【Python】进阶 - 生成器、正则表达式🚀

文章目录🎉

一、简介

二、算法

2.1 时间复杂度🕒

1. 常数时间：

2. 对数时间：

3. 线性时间：

4. 线性对数时间：

5. 平方时间：

6. 指数时间：

2.2 空间复杂度🚀

1. 常数空间：

2. 对数空间：

3. 线性空间：

4. 线性对数空间：

5. 平方空间：

6. 指数空间：

三、数据结构

3.1 线性结构

1. 数组（列表）

2. 链表🔗

3. 栈

4. 队列

3.2 非线性结构

1. 树🌳

2. 二叉树🌳

3. 二叉搜索树🌳

4. 完全二叉树🌳

5.堆

6. 图

一、简介

数据结构与算法主要的作用就是为了提升程序的性能。

算法：是一组解决特定问题的有限、明确、可执行的操作步骤。它接收输入数据并产生输出结果，强调的是逻辑性和效率。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，用于组织、管理和存储数据，以便能够高效地访问和修改数据。

程序 = 算法 + 数据结构

总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

二、算法

特性：
输入         有零个或多个输入
输出         至少有一个输出
确定性   每一步都必须清晰无歧义
有穷性在有限步内结束
可行性算法的每一步都是可行的

2.1 时间复杂度🕒

时间复杂度是一个用于描述算法运行时间与输入规模之间关系的函数。它衡量的是算法执行所需的时间随着输入数据量增长的趋势。通常使用大 O 表示法来描述。

时间复杂度不是表示程序运行的具体时间（如秒、毫秒），而是表示算法操作次数的增长趋势。

①基本操作

时间复杂度为O(1)

②顺序结构

时间复杂度按加法进行计算

③循环结构

时间复杂度按乘法进行计算

④分支结构

时间复杂度取最大值

⑤判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略

⑥在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

常见时间复杂度（从快到慢）：

复杂度	名称	示例
`O(1)`	常数时间	访问数组元素
`O(log n)`	对数时间	二分查找
`O(n)`	线性时间	遍历数组
`O(n log n)`	线性对数时间	快速排序、归并排序
`O(n²)`	平方时间	双重循环排序
`O(2ⁿ)`	指数时间	递归计算斐波那契数列（不带缓存）

1. 常数时间：

无论数据规模多大，执行时间都是固定的。例如访问数组中的某个元素,操作次数总是1次，时间复杂度是O(1).

arr = [10, 20, 30, 40, 50]
print(arr[2])  # 直接访问索引为 2 的元素

2. 对数时间：

log $^{_{2}7}$ >100>log $^{_{2}6}$ ，这里 i 是指数增长，每次运行 i 翻一倍，函数的时间复杂度O(log n).

count = 0
i = 1
while i<100:i *= 2count += 1print(count)    # 7 （2的7次方大于100）

3. 线性时间：

当循环变量每次线性递增（如 i += 1），且循环次数依赖于 n 的大小时，时间复杂度就是 O(n)

n = 100    # 这里 n 不是固定值，可以换成任意数
i = 0
while i < n:i += 1

4. 线性对数时间：

快速排序：每次分区操作需要遍历整个数组（O(n)），而每次分区后数组被大致分成两个相等的部分，所以总的递归深度是 log n。时间复杂度在平均情况下为 O(n log n)，但在最坏情况下（每次选择的基准值middle都是最大值或则最小值）可能退化到 O(n²)。

def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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 = [38, 27, 43, 3, 9, 82, 10]
print(quick_sort(arr))  # 输出: [3, 9, 10, 27, 38, 43, 82]

5. 平方时间：

冒泡排序：两层循环，时间复杂度为O(n²)

def bubble_sort(arr):n = len(arr)for i in range(n):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))  # 输出: [11, 12, 22, 25, 34, 64, 90]

6. 指数时间：

斐波那契数列：从下图这个树可以看出，每个节点会分裂成两个子节点（除了叶子节点），形成一棵二叉树。对于较大的 n，这棵树的深度为 n，而每层的节点数量大致翻倍。时间复杂度接近O(2ⁿ)

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)├── fib(2)│   ├── fib(1) = 1│   └── fib(0) = 0└── fib(1) = 1

def fib(n):if n <= 1:return nreturn fib(n - 1) + fib(n - 2)# 测试
print(fib(5))  # 输出: 5
print(fib(10)) # 输出: 55

2.2 空间复杂度🚀

空间复杂度是指算法运行过程中需要的额外内存空间随着输入数据量增长的趋势。通常也使用大 O 表示法来描述。

额外内存空间：指的是除了输入数据本身占用的空间外，算法运行期间额外使用的内存。
不考虑输入数据本身的大小：因为输入数据大小通常是固定的或外部给定的，我们关注的是算法自身的开销。
递归调用栈：如果算法中有递归调用，那么递归深度会影响空间复杂度。

空间复杂度	名称	示例代码 / 场景	简要说明
`O(1)`	常数空间	交换两个变量、访问数组元素	额外空间固定，与输入规模无关
`O(log n)`	对数空间	快速排序（递归实现）	递归深度为 `log n`，栈空间增长缓慢
`O(n)`	线性空间	创建新数组、哈希表存储数据、带缓存的斐波那契	额外空间与输入规模成正比
`O(n log n)`	线性对数空间	归并排序（非原地实现）	分治过程中需要较多辅助空间
`O(n²)`	平方空间	使用二维数组保存状态（如动态规划中的部分实现）	空间需求随输入平方增长
`O(2ⁿ)`	指数空间	多重递归（如汉诺塔、无剪枝的回溯算法）	空间消耗爆炸式增长，慎用

1. 常数空间：

def swap(a, b):a, b = b, areturn a, b

只使用了固定数量的变量（a、b），不随输入变化。空间复杂度为 O(1)。

2. 对数空间：

快速排序前面线性对数时间已经举例过了，是递归实现的分治算法。虽然每次递归会创建新数组（非原地），但调用栈深度为 log n。因此空间复杂度为 O(log n)（主要是递归栈的空间）。

3. 线性空间：

def create_array(n):return [0] * n

创建了一个长度为 n 的数组，额外空间大小直接与输入规模成正比，空间复杂度为 O(n)。

4. 线性对数空间：

归并排序（非原地实现）了解即可。

5. 平方空间：

创建一个 n x n 的二维数组，额外空间为 n * n = n²，空间复杂度为 O(n²)。

def create_2d_table(n):
# 下划线 _ 只是一个约定俗成的写法，表示这个循环变量在后续代码中不会被使用。return [[0] * n for _ in range(n)]    print(create_2d_table(3))   # [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

6. 指数空间：

汉诺塔问题是典型的多重递归问题，每层递归都会产生两个子问题，导致调用栈指数级增长。空间复杂度为 O(2ⁿ)，非常消耗内存。

def hanoi(n, source, target, auxiliary):"""汉诺塔游戏规则：使用三根柱子，将叠放的圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且小圆盘不能放在大圆盘下方。:param n:         当前要移动的圆盘数量:param source:    当前圆盘所在的柱子:param target:    希望把圆盘移动到的目标柱子:param auxiliary: 辅助用的第三根柱:return:"""if n == 1:print(f"Move disk from {source} to {target}")returnhanoi(n - 1, source, auxiliary, target)print(f"Move disk from {source} to {target}")hanoi(n - 1, auxiliary, target, source)

三、数据结构

数据结构（Data Structure）是计算机中存储和组织数据的一种方式。它描述了数据之间的关系以及对这些数据的操作。

Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。

3.1 线性结构

线性结构的特点是每个元素（除了第一个和最后一个）都有一个直接前驱和一个直接后继。常见的线性结构包括数组、列表、栈、队列等。

结构	特点
数组（Array）	固定大小，连续内存，随机访问快
链表（Linked List）	动态大小，非连续内存，插入删除快
栈（Stack）	后进先出（LIFO）
队列（Queue）	先进先出（FIFO）

1. 数组（列表）

Python中通过list实现，支持动态扩容和多种数据类型混合存储。支持随机访问（通过索引），缺点是插入/删除慢（需要移动其他元素）。

arr = [1, 2, 3, 'a', True]  # 创建列表
arr.append(4)               # 添加元素
print(arr[0])               # 访问元素

2. 链表🔗

分为单链表和双链表，适合频繁插入/删除的场景。

✅ 特点：

每个节点包含数据和指向下一个节点的指针
可以动态增长

⚠️ 缺点：

不支持随机访问
查找慢（O(n)）

单链表：

单链表是链表的一种形式，包含两个域（元素域和链接域）。表元素域data用来存放具体的数据，链接域next用来存放下一个结点的位置，变量head指向链表的头结点（首结点）的位置，从head出发能找到表中的任意结点。

class Node:def __init__(self, data):self.data = dataself.next = None# 创建链表
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)# 遍历
current = head
while current:print(current.data)current = current.next

双向链表：

相较于单向链表，双向链表多了一个指针，不仅有指向下一节点的指针，还有一个指针指向前一个结点。

class Node:"""节点类：表示双向链表中的一个节点"""def __init__(self, data):self.data = data      # 节点存储的数据self.prev = None      # 指向前一个节点的指针self.next = None      # 指向下一个节点的指针class DoublyLinkedList:"""双向链表类：支持头尾插入、删除指定值节点以及正反向遍历"""def __init__(self):self.head = None      # 链表的头节点指针self.tail = None      # 链表的尾节点指针def append(self, data):"""在链表尾部插入一个新节点"""new_node = Node(data)  # 创建新节点if self.head is None:  # 如果链表为空self.head = new_nodeself.tail = new_nodeelse:new_node.prev = self.tail  # 新节点前驱指向当前尾节点self.tail.next = new_node  # 当前尾节点后继指向新节点self.tail = new_node       # 更新尾节点为新节点def prepend(self, data):"""在链表头部插入一个新节点"""new_node = Node(data)  # 创建新节点if self.head is None:  # 如果链表为空self.head = new_nodeself.tail = new_nodeelse:new_node.next = self.head  # 新节点后继指向当前头节点self.head.prev = new_node  # 当前头节点前驱指向新节点self.head = new_node       # 更新头节点为新节点def delete(self, data):"""删除第一个匹配指定数据的节点（若存在）"""current = self.headwhile current:if current.data == data:  # 找到要删除的节点if current.prev:current.prev.next = current.next  # 前驱节点连接后继节点else:self.head = current.next  # 如果是头节点，更新头指针if current.next:current.next.prev = current.prev  # 后继节点连接前驱节点else:self.tail = current.prev  # 如果是尾节点，更新尾指针returncurrent = current.next  # 继续遍历下一个节点def traverse_forward(self):"""从头到尾遍历链表并打印节点数据"""current = self.headwhile current:print(current.data, end=" ")  # 打印当前节点数据current = current.next        # 移动到下一个节点print()def traverse_backward(self):"""从尾到头遍历链表并打印节点数据"""current = self.tailwhile current:print(current.data, end=" ")  # 打印当前节点数据current = current.prev        # 移动到前一个节点print()

测试代码：

# 测试双向链表
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.prepend(5)
print("正向遍历:")
dll.traverse_forward()  # 输出: 5 10 20
print("反向遍历:")
dll.traverse_backward()  # 输出: 20 10 5dll.delete(10)
print("删除后正向遍历:")
dll.traverse_forward()  # 输出: 5 20

3. 栈

后进先出（LIFO），仅允许在栈顶进行插入或删除，通过列表模拟或collections.deque实现。

stack = []
stack.append(1)  # push
stack.append(2)
print(stack.pop())  # pop -> 2

4. 队列

先进先出（FIFO），推荐使用queue.Queue或collections.deque。

from collections import deque
q = deque()
q.append(1)
q.append(2)
print(q.popleft())  # 出队 -> 1

3.2 非线性结构

非线性结构是数据元素之间不再保持一对一关系的数据结构，主要包括树形结构、图形结构和集合结构等。与线性结构（如数组、链表）不同，非线性结构中的元素可以有多于一个的前驱或后继元素。

结构	特点
树（Tree）	层次结构，根节点到叶子节点分支
堆（Heap）	完全二叉树，堆顶最大或最小
图（Graph）	节点和边组成，表示复杂关系
散列表 / 哈希表（Hash Table）	键值对存储，查找非常快

1. 树🌳

树形结构是层次化的非线性结构，数据元素之间存在一对多的关系。

参考上面这张图我们介绍一下树相关的一些基本术语：

根节点（Root）：树中没有父节点的节点。在这个例子中，节点A是根节点。
子节点（Child）：一个节点直接连接到另一个节点下方，则这个节点称为另一个节点的子节点。例如，B、C和D是A的子节点。
父节点（Parent）：如果一个节点有子节点，那么这个节点就是其子节点的父节点。例如，A是B、C和D的父节点。
兄弟节点（Sibling）：具有相同父节点的节点互为兄弟节点。例如，B、C和D互为兄弟节点。
叶节点（Leaf）：没有子节点的节点称为叶节点或终端节点。在这个例子中，F、G、H、J、K和L都是叶节点。
内部节点（Internal Node）：除了根节点外，所有有子节点的节点都称为内部节点。在这个例子中，B、C、D、G和I是内部节点。
路径（Path）：从一个节点到另一个节点的路径是由这两个节点之间的边组成的序列。例如，从A到L的路径是A -> B -> G -> L。
深度（Depth）：一个节点的深度是从根节点到该节点的唯一路径上的边的数量。例如，A的深度为0，B、C和D的深度为1，而L的深度为3。
高度（Height）：一棵树的高度是从根节点到最远叶节点的最长路径上的边的数量。在这个例子中，树的高度为3。

树的遍历：

前序遍历（根-左-右）：先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。对于给定的树，前序遍历的结果为：A -> B -> F -> G -> L -> C -> H -> D -> I -> M -> J -> K。
中序遍历（左-根-右）：首先递归地进行左子树的中序遍历，然后访问根节点，最后递归地进行右子树的中序遍历。对于给定的树，中序遍历的结果为：F -> B -> L -> G -> A -> C -> H -> I -> M -> D -> J -> K。
后序遍历（左-右-根）：首先递归地进行左子树的后序遍历，然后递归地进行右子树的后序遍历，最后访问根节点。对于给定的树，后序遍历的结果为：F -> L -> G -> B -> H -> C -> M -> I -> J -> K -> D -> A。

代码实现：

class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.middle = Noneself.right = None# 构建树
def build_tree():# 创建节点A = TreeNode('A')B = TreeNode('B')C = TreeNode('C')D = TreeNode('D')F = TreeNode('F')G = TreeNode('G')H = TreeNode('H')I = TreeNode('I')J = TreeNode('J')K = TreeNode('K')L = TreeNode('L')M = TreeNode('M')# 构建树结构A.left = BA.middle = CA.right = DB.left = FB.right = GG.left = LC.left = HD.left = ID.middle = JD.right = KI.left = Mreturn A# 前序遍历
def preorder_traversal(node):if node:print(node.val, end=' ')preorder_traversal(node.left)preorder_traversal(node.middle)preorder_traversal(node.right)# 中序遍历
def inorder_traversal(node):if node:inorder_traversal(node.left)print(node.val, end=' ')inorder_traversal(node.middle)inorder_traversal(node.right)# 后序遍历
def postorder_traversal(node):if node:postorder_traversal(node.left)postorder_traversal(node.middle)postorder_traversal(node.right)print(node.val, end=' ')# 使用
root = build_tree()print("Pre-order traversal:")
preorder_traversal(root)
print("\nIn-order traversal:")
inorder_traversal(root)
print("\nPost-order traversal:")
postorder_traversal(root)

2. 二叉树🌳

二叉树是每个节点最多有两个子节点的树结构。

class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = None# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)# 前序遍历
def preorder_traversal(node):if node:print(node.value, end=' ')preorder_traversal(node.left)preorder_traversal(node.right)print("前序遍历:")
preorder_traversal(root)  # 输出: 1 2 4 5 3

3. 二叉搜索树🌳

二叉搜索树是一种特殊的二叉树，左子节点的值小于父节点，右子节点的值大于父节点。

class BSTNode:# 定义二叉搜索树节点类def __init__(self, value):self.value = value  # 节点值self.left = None    # 指向左子节点self.right = None   # 指向右子节点class BinarySearchTree:# 定义二叉搜索树类def __init__(self):self.root = None  # 初始化根节点为空# 插入新值到二叉搜索树中def insert(self, value):if not self.root:  # 如果树为空，则创建根节点self.root = BSTNode(value)else:self._insert_recursive(self.root, value)  # 否则，使用递归方法插入# 递归实现插入操作def _insert_recursive(self, node, value):if value < node.value:  # 如果新值小于当前节点值if node.left is None:  # 若左子节点为空，则插入为左子节点node.left = BSTNode(value)else:self._insert_recursive(node.left, value)  # 否则，继续在左子树中查找位置else:  # 如果新值大于或等于当前节点值if node.right is None:  # 若右子节点为空，则插入为右子节点node.right = BSTNode(value)else:self._insert_recursive(node.right, value)  # 否则，继续在右子树中查找位置# 在二叉搜索树中搜索指定值def search(self, value):return self._search_recursive(self.root, value)  # 使用递归方法进行搜索# 递归实现搜索操作def _search_recursive(self, node, value):if node is None or node.value == value:  # 如果节点为空或找到了目标值，则返回该节点return nodeif value < node.value:  # 如果目标值小于当前节点值，则在左子树中继续搜索return self._search_recursive(node.left, value)return self._search_recursive(node.right, value)  # 否则，在右子树中继续搜索# 使用示例
bst = BinarySearchTree()  # 创建一个二叉搜索树实例
bst.insert(50); bst.insert(30); bst.insert(20); bst.insert(40); bst.insert(70); bst.insert(60); bst.insert(80)print("\n查找40:", bst.search(40) is not None)  # 输出: True
print("查找100:", bst.search(100) is not None)  # 输出: False

4. 完全二叉树🌳

完全二叉树是一棵深度为 h 的二叉树，除了最后一层外，其他层的节点都是满的，并且最后一层的节点都尽可能靠左排列。完全二叉树是构建堆的基础结构。

我们可以用列表来模拟完全二叉树的存储方式。在完全二叉树中，可以通过索引快速找到父节点和子节点：

父节点索引：(i - 1) // 2
左子节点索引：2 * i + 1
右子节点索引：2 * i + 2

class CompleteBinaryTree:def __init__(self):self.tree = []  # 使用列表存储完全二叉树的节点值def insert(self, value):"""向完全二叉树中插入一个节点"""self.tree.append(value)def get_parent_index(self, index):"""获取父节点的索引"""if index == 0:return Nonereturn (index - 1) // 2def get_left_child_index(self, index):"""获取左子节点的索引"""left_index = 2 * index + 1if left_index >= len(self.tree):return Nonereturn left_indexdef get_right_child_index(self, index):"""获取右子节点的索引"""right_index = 2 * index + 2if right_index >= len(self.tree):return Nonereturn right_indexdef display(self):"""显示完全二叉树的结构"""print("完全二叉树的层次遍历:")for i in range(len(self.tree)):print(f"节点 {self.tree[i]} | 父节点索引: {self.get_parent_index(i)} | 左子节点索引: {self.get_left_child_index(i)} | 右子节点索引: {self.get_right_child_index(i)}")# 使用示例
cbt = CompleteBinaryTree()
cbt.insert(1)
cbt.insert(2)
cbt.insert(3)
cbt.insert(4)
cbt.insert(5)
cbt.insert(6)cbt.display()

输出结果：

完全二叉树的层次遍历:
节点 1 | 父节点索引: None | 左子节点索引: 1 | 右子节点索引: 2
节点 2 | 父节点索引: 0 | 左子节点索引: 3 | 右子节点索引: 4
节点 3 | 父节点索引: 0 | 左子节点索引: 5 | 右子节点索引: None
节点 4 | 父节点索引: 1 | 左子节点索引: None | 右子节点索引: None
节点 5 | 父节点索引: 1 | 左子节点索引: None | 右子节点索引: None
节点 6 | 父节点索引: 2 | 左子节点索引: None | 右子节点索引: None

5.堆

堆是一种特殊的完全二叉树，分为最大堆和最小堆。

最大堆（Max Heap）：每个节点的值都大于等于其子节点的值。
最小堆（Min Heap）：每个节点的值都小于等于其子节点的值。

Python 中可以使用 heapq 模块实现最小堆：

import heapq# 创建一个最小堆
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 4)print("最小堆的内容:", min_heap)
print("弹出最小值:", heapq.heappop(min_heap))
print("更新后的最小堆:", min_heap)

6. 图

图形结构是最一般的非线性结构，数据元素之间存在多对多的关系。表示对象之间的复杂关系，由节点（Vertex）和边（Edge）组成。

邻接表表示法（Python 字典）：

graph = {'A': ['B', 'C'],'B': ['A', 'D'],'C': ['A', 'D'],'D': ['B', 'C']
}