【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(n2)`	平方時間	雙重循環排序
`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(n2)。

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(n2)

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(n2)`	平方空間	使用二維數組保存狀態（如動態規劃中的部分實現）	空間需求隨輸入平方增長
`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 = n2，空間復雜度為 O(n2)。

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']
}