這是一個完整的資料結構與演算法學習專案，包含從基礎搜尋演算法到進階樹結構的實作練習。本專案按照課程單元循序漸進，涵蓋資料結構核心概念與經典演算法的 Python 實現。
專案目標: 透過實作學習經典資料結構與演算法 開發語言: Python 3.12 程式碼規模: 27 個 Python 檔案，約 1440 行程式碼 課程單元: 11 個主題單元 版本控制: Git + GitHub
- ✅ 完整實作: 涵蓋 Linked List, Stack, Queue, Tree 等核心資料結構
- ✅ 經典演算法: 包含 Binary Search, Quick Sort, Merge Sort 等常見演算法
- ✅ 測試驗證: 每個模組都包含完整的測試案例
- ✅ 中文註解: 詳細的中文說明，幫助理解關鍵概念
- ✅ 漸進式學習: 從基礎到進階，循序漸進的學習路徑
檔案: 1_1/main.py
實現二元搜尋 (Binary Search) 演算法，在已排序的陣列中快速查找目標值。
def search(data, target):
# 二元搜尋實現
# 時間複雜度: O(log n)關鍵概念:
- 二元搜尋的基本原理
- 已排序資料的高效查找
- 時間複雜度分析
檔案: Test1.py, Test2.py, Test3.py, Test4.py
def decode(x):
# 求整數平方根
# 時間複雜度: O(√n)def tub(height):
# 使用雙指針技巧
# 時間複雜度: O(n)def checkClose(s):
# 驗證括號是否正確配對
# 時間複雜度: O(n)關鍵概念:
- Two Pointers 雙指針技巧
- 時間複雜度優化
- Stack 在括號匹配中的應用
完整的單向鏈表實現，包含所有基本操作：
class LinkedList:
def print() # 顯示鏈表內容
def append(value) # 尾部添加節點
def insertAt(index, value) # 指定位置插入
def removeAt(index) # 指定位置刪除
def remove(value) # 根據值刪除
def indexOf(value) # 查找值的索引
def isEmpty() # 檢查是否為空
def size() # 獲取鏈表大小使用範例:
# 建立鏈表: 1 -> 2 -> 3 -> 4 -> 5
list = LinkedList(Node(1, Node(2, Node(3, Node(4, Node(5))))))
list.print() # 輸出: 1 -> 2 -> 3 -> 4 -> 5 -> Null
# 添加節點
list.append(6) # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Null
# 插入節點
list.insertAt(0, 13) # 13 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Null
# 刪除節點
list.remove(3) # 13 -> 1 -> 2 -> 4 -> 5 -> 6 -> Null環形佇列 (Circular Queue) 實現：
class Queue:
def enqueue(item) # 入隊
def dequeue() # 出隊
def get_front() # 獲取隊首
def is_empty() # 檢查是否為空
def is_full() # 檢查是否已滿
def display() # 顯示隊列內容使用雙向鏈表實現的進階佇列：
class MyQueue:
def insertFront(value) # 前端插入
def insertRear(value) # 後端插入
def deleteFront() # 前端刪除
def deleteRear() # 後端刪除
def getFront() # 獲取前端值
def getRear() # 獲取後端值class Tree:
def insert(data) # 插入節點
def inOrder(node) # 中序遍歷 (左-根-右)
def preOrder(node) # 前序遍歷 (根-左-右)
def postOrder(node) # 後序遍歷 (左-右-根)
def isSymmetric() # 檢查樹是否對稱樹的遍歷範例:
tree = Tree()
for value in [5, 3, 7, 2, 4, 6, 8]:
tree.insert(value)
# 樹的結構:
# 5
# / \
# 3 7
# / \ / \
# 2 4 6 8
tree.preOrder(tree.root) # 輸出: 5 3 2 4 7 6 8
tree.inOrder(tree.root) # 輸出: 2 3 4 5 6 7 8 (已排序)
tree.postOrder(tree.root) # 輸出: 2 4 3 6 8 7 5D1345490_1.py - MinStack (追蹤最小值的堆疊)
class MinStack:
def push(x) # 壓入元素
def pop() # 彈出元素
def peek() # 查看頂部
def getMin() # O(1) 時間獲取最小值D1345490_2.py - String 操作
D1345490_3.py - 環形佇列完整實現
class MyCircleQueue:
# 循環佇列的完整實現
# 包含詳細中文註解說明常見錯誤實現三種經典排序演算法：
# 1. 冒泡排序 (Bubble Sort)
def bubble_sort(data):
# 時間複雜度: O(n²)
# 空間複雜度: O(1)
# 穩定排序
# 2. 歸併排序 (Merge Sort)
def merge_sort(data):
# 時間複雜度: O(n log n)
# 空間複雜度: O(n)
# 穩定排序 (Divide and Conquer)
# 3. 快速排序 (Quick Sort)
def quick_sort(data):
# 時間複雜度: 平均 O(n log n), 最差 O(n²)
# 空間複雜度: O(log n)
# 不穩定排序排序演算法比較:
| 演算法 | 最佳 | 平均 | 最差 | 空間 | 穩定性 |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ |
經典的遞迴問題實現：
class Hanoi:
def solve(self, n, source, auxiliary, destination):
# 遞迴求解河內塔問題
# 最少移動次數: 2^n - 1河內塔問題:
- n = 1: 1 步
- n = 2: 3 步
- n = 3: 7 步
- n = 4: 15 步
D1345490_1.py - 河內塔改進版本
D1345490_2.py - 鏈表轉二元搜尋樹
class Solution:
def sortedListToBST(head):
# 將排序鏈表轉為平衡 BST
# 使用快慢指針找中點
# 遞迴構建平衡樹
def levelOrder(root):
# 層序遍歷 (BFS)
# 使用 deque 實現主題: 樹的對稱性檢驗 (LeetCode 101)
D1345490_1.py- 對稱性檢驗初始版本D1345490_2.py- 改進版本 (邊界處理)Test1.py- isSameTree 測試Test2.py- 完整的 isSymmetric 實現
class Solution:
def isSymmetric(self, root):
"""檢查二元樹是否左右對稱"""
if root is None:
return True
return self.sym(root.left, root.right)
def sym(self, left, right):
"""遞迴比較左右子樹"""
if left is None and right is None:
return True
if left is None or right is None:
return False
if left.val != right.val:
return False
# 比較 left.left ↔ right.right 和 left.right ↔ right.left
return (self.sym(left.left, right.right) and
self.sym(left.right, right.left))測試案例:
# Test 1: 完全對稱樹
# 1
# / \
# 2 2
# / \ / \
# 3 4 4 3
# 結果: True
# Test 2: 單節點樹
# 1
# 結果: True
# Test 3: None 根節點
# 結果: True
# Test 4: 不對稱樹
# 1
# / \
# 2 2
# \ \
# 3 3
# 結果: False主題: 鏈表數學運算與矩陣遍歷
D1345490_1.py- 兩數相加 (LeetCode 2)D1345490_2.py- 螺旋矩陣 (LeetCode 54)
使用鏈表表示數字，實現大數相加：
class Solution:
def addTwoNumbers(self, l1, l2):
"""
兩個鏈表代表的數字相加
數字以反向儲存（個位在前）
時間複雜度: O(max(m, n))
空間複雜度: O(max(m, n))
"""
head = ListNode()
current = head
carry = 0
while l1 or l2 or carry:
v1 = l1.value if l1 else 0
v2 = l2.value if l2 else 0
total = v1 + v2 + carry
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
l1 = l1.next if l1 else 0
l2 = l2.next if l2 else 0
return head.next測試案例:
# 輸入: l1 = [2,4,6], l2 = [5,6,4]
# 代表: 642 + 465 = 1107
# 輸出: [7,0,1,1] -> 7 -> 0 -> 1 -> 1以螺旋順序遍歷矩陣：
class Solution:
def spiral_Matrix(self, matrix, result=None):
"""
螺旋順序遍歷矩陣
順序: 右 -> 下 -> 左 -> 上 (遞迴)
時間複雜度: O(m * n)
空間複雜度: O(m * n)
"""
if result is None:
result = []
if matrix:
result.extend(matrix.pop(0)) # 右
for row in matrix:
if row:
result.append(row.pop()) # 下
if matrix:
result.extend(reversed(matrix.pop())) # 左
for i in range(len(matrix) - 1, -1, -1):
if matrix[i]:
result.append(matrix[i].pop(0)) # 上
return self.spiral_Matrix(matrix, result)
return result測試案例:
# 輸入:
# [[1, 2, 3, 4],
# [5, 6, 7, 8],
# [9, 10, 11, 12]]
# 輸出: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]關鍵概念:
- 鏈表的數學運算與進位處理
- 矩陣的螺旋遍歷
- 遞迴解法
主題: 自平衡二元搜尋樹 (AVL Tree)
D1345490_1.py- AVL Tree 完整實現 (插入 + 刪除)D1345490_2.py- AVL Tree 改進版本Assignment.pdf- 作業說明文件
class AVLTree:
def height(self, root):
"""獲取節點高度"""
if not root:
return 0
return root.height
def get_balance(self, root):
"""計算平衡因子 (左子樹高度 - 右子樹高度)"""
if not root:
return 0
return self.height(root.left) - self.height(root.right)
def Right_rotation(self, root):
"""右旋轉 (LL 情況)"""
x = root.left
temp = x.right
x.right = root
root.left = temp
# 更新高度
root.height = 1 + max(self.height(root.left), self.height(root.right))
x.height = 1 + max(self.height(x.left), self.height(x.right))
return x
def Left_rotation(self, root):
"""左旋轉 (RR 情況)"""
y = root.right
temp = y.left
y.left = root
root.right = temp
# 更新高度
root.height = 1 + max(self.height(root.left), self.height(root.right))
y.height = 1 + max(self.height(y.left), self.height(y.right))
return y
def insert(self, root, value):
"""
插入節點並自動平衡
時間複雜度: O(log n)
"""
# 1. 執行標準 BST 插入
if not root:
return Node(value)
if value < root.value:
root.left = self.insert(root.left, value)
elif value > root.value:
root.right = self.insert(root.right, value)
else:
return root # 重複值不插入
# 2. 更新節點高度
root.height = 1 + max(self.height(root.left), self.height(root.right))
# 3. 計算平衡因子
balance = self.get_balance(root)
# 4. 進行平衡調整 (4 種情況)
# LL: 左子樹的左側插入
if balance > 1 and value < root.left.value:
return self.Right_rotation(root)
# LR: 左子樹的右側插入
if balance > 1 and value > root.left.value:
root.left = self.Left_rotation(root.left)
return self.Right_rotation(root)
# RR: 右子樹的右側插入
if balance < -1 and value > root.right.value:
return self.Left_rotation(root)
# RL: 右子樹的左側插入
if balance < -1 and value < root.right.value:
root.right = self.Right_rotation(root.right)
return self.Left_rotation(root)
return root
def delete(self, root, value):
"""
刪除節點並自動平衡
時間複雜度: O(log n)
"""
# 1. 執行標準 BST 刪除
if root is None:
return root
if value < root.value:
root.left = self.delete(root.left, value)
elif value > root.value:
root.right = self.delete(root.right, value)
else:
# 找到要刪除的節點
if root.left is None and root.right is None:
return None
elif root.left is None:
return root.right
elif root.right is None:
return root.left
else:
# 有兩個子節點: 找右子樹的最小值
temp = root.right
while temp.left:
temp = temp.left
root.value = temp.value
root.right = self.delete(root.right, temp.value)
# 2. 更新高度
root.height = 1 + max(self.height(root.left), self.height(root.right))
# 3. 計算平衡因子並調整
balance = self.get_balance(root)
# LL
if balance > 1 and self.get_balance(root.left) >= 0:
return self.Right_rotation(root)
# LR
if balance > 1 and self.get_balance(root.left) < 0:
root.left = self.Left_rotation(root.left)
return self.Right_rotation(root)
# RR
if balance < -1 and self.get_balance(root.right) <= 0:
return self.Left_rotation(root)
# RL
if balance < -1 and self.get_balance(root.right) > 0:
root.right = self.Right_rotation(root.right)
return self.Left_rotation(root)
return root測試案例 (D1345490_1.py):
# 插入: [10, 20, 30, 40, 50, 25]
# 前序遍歷: 30 -> 20 -> 10 -> 25 -> 40 -> 50
# 刪除 20 後
# 前序遍歷: 30 -> 25 -> 10 -> 40 -> 50測試案例 (D1345490_2.py):
# 插入: [10, 11, 12, ..., 30] (連續數字)
# 刪除 15, 14
# 展示大量節點的平衡維護AVL Tree 四種旋轉情況:
| 情況 | 插入位置 | 調整方式 | 說明 |
|---|---|---|---|
| LL | 左子樹的左側 | 右旋轉 | balance > 1, left.balance >= 0 |
| LR | 左子樹的右側 | 左旋轉 + 右旋轉 | balance > 1, left.balance < 0 |
| RR | 右子樹的右側 | 左旋轉 | balance < -1, right.balance <= 0 |
| RL | 右子樹的左側 | 右旋轉 + 左旋轉 | balance < -1, right.balance > 0 |
AVL Tree 特性:
- 平衡因子: 左子樹高度 - 右子樹高度 ∈ {-1, 0, 1}
- 高度保證: 對於 n 個節點，樹高度 ≈ 1.44 log n
- 插入/刪除: O(log n) 時間複雜度
- 查詢效率: 保證 O(log n) (相比未平衡 BST 最差 O(n))
- 自動平衡: 每次插入/刪除後自動調整
關鍵概念:
- 平衡因子計算與維護
- 四種旋轉操作 (LL, LR, RR, RL)
- 插入後的自動平衡
- 刪除後的自動平衡
- 高度更新策略
主題: 紅黑樹 (Red-Black Tree) - 自平衡二元搜尋樹的進階實現
D1345490_1.py- 紅黑樹驗證演算法D1345490_2.py- 紅黑樹完整實現 (插入 + 搜尋)test.py- 紅黑樹驗證器（測試版本）Assignment.pdf- 作業說明文件
class Solution:
def isValidRedBlackTree(self, root):
"""
驗證是否為合法的紅黑樹
檢查五大性質：
1. 節點顏色為紅或黑
2. 根節點為黑色
3. 所有葉節點(NIL)為黑色
4. 紅色節點的子節點必須為黑色
5. 從任一節點到其葉節點的所有路徑包含相同數量的黑色節點
"""
if root is None:
return True
# 檢查性質 2: 根節點必須是黑色
if root.color == 'R':
return False
result, _ = self.validate(root)
return result
def validate(self, node):
"""
遞迴檢查子樹
返回: (bool: 是否合法, int: 黑高)
"""
if node is None:
return True, 1 # NIL 節點貢獻 1 個黑高
left_valid, left_bh = self.validate(node.left)
right_valid, right_bh = self.validate(node.right)
# 檢查黑高是否一致 (性質 5)
if not left_valid or not right_valid or left_bh != right_bh:
return False, 0
# 檢查性質 4: 紅色節點的子節點必須是黑色
if node.color == 'R':
if (node.left and node.left.color == "R") or \
(node.right and node.right.color == 'R'):
return False, 0
# 計算當前黑高
current_bh = left_bh + (1 if node.color == 'B' else 0)
return True, current_bh測試案例 (D1345490_1.py):
# 測試案例 1: 合法的紅黑樹
# 10(B)
# / \
# 5(R) 15(R)
# 結果: True
# 測試案例 2: 根節點為紅色 (違反性質 2)
# 結果: Falseclass RedBlackTree:
def __init__(self):
"""使用 TNULL 哨兵節點代替 None"""
self.TNULL = Node(0)
self.TNULL.color = 'B' # 黑色
self.TNULL.left = None
self.TNULL.right = None
self.root = self.TNULL
def left_rotate(self, x):
"""
左旋轉
x 的右子節點 y 變成 x 的父節點
"""
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def right_rotate(self, x):
"""
右旋轉
x 的左子節點 y 變成 x 的父節點
"""
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent is None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
def insert_fix(self, k):
"""
插入後修復紅黑樹性質
處理三種情況：
1. 叔節點是紅色 -> 重新著色
2. 叔節點是黑色且當前節點是右子節點 -> 左旋轉
3. 叔節點是黑色且當前節點是左子節點 -> 右旋轉 + 重新著色
"""
while k.parent and k.parent.color == 'R':
if k.parent == k.parent.parent.left:
u = k.parent.parent.right # 叔節點
if u.color == 'R':
# Case 1: 叔節點是紅色
u.color = 'B'
k.parent.color = 'B'
k.parent.parent.color = 'R'
k = k.parent.parent
else:
if k == k.parent.right:
# Case 2: 叔節點是黑色，當前節點是右子節點
k = k.parent
self.left_rotate(k)
# Case 3: 叔節點是黑色，當前節點是左子節點
k.parent.color = 'B'
k.parent.parent.color = 'R'
self.right_rotate(k.parent.parent)
else:
# 對稱情況
u = k.parent.parent.left
if u.color == 'R':
u.color = 'B'
k.parent.color = 'B'
k.parent.parent.color = 'R'
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self.right_rotate(k)
k.parent.color = 'B'
k.parent.parent.color = 'R'
self.left_rotate(k.parent.parent)
if k == self.root:
break
self.root.color = 'B'
def insert(self, key):
"""
插入新節點
時間複雜度: O(log n)
"""
node = Node(key)
node.left = self.TNULL
node.right = self.TNULL
node.color = 'R' # 新節點初始為紅色
# 標準 BST 插入
y = None
x = self.root
while x != self.TNULL:
y = x
if node.value < x.value:
x = x.left
else:
x = x.right
node.parent = y
if y is None:
self.root = node
elif node.value < y.value:
y.left = node
else:
y.right = node
# 特殊情況處理
if node.parent is None:
node.color = 'B'
return
if node.parent.parent is None:
return
# 修復紅黑樹性質
self.insert_fix(node)
def search(self, target):
"""
搜尋節點
時間複雜度: O(log n)
"""
current = self.root
while current != self.TNULL:
if target == current.value:
return True
elif target < current.value:
current = current.left
else:
current = current.right
return False測試案例 (D1345490_2.py):
# 插入: [10, 5, 15]
# 搜尋 5: True
# 搜尋 20: False
# 插入 20 後
# 搜尋 20: True紅黑樹五大性質:
| 性質 | 描述 | 檢查方式 |
|---|---|---|
| 1 | 每個節點顏色為紅或黑 | 數據結構定義 |
| 2 | 根節點為黑色 | root.color == 'B' |
| 3 | 所有葉節點(NIL)為黑色 | 使用 TNULL 哨兵節點 |
| 4 | 紅色節點的子節點必須為黑色 | 遞迴檢查 |
| 5 | 從任一節點到葉節點的所有路徑黑高相同 | 遞迴計算黑高 |
紅黑樹 vs AVL 樹:
| 特性 | 紅黑樹 | AVL 樹 |
|---|---|---|
| 平衡條件 | 黑高差 ≤ 1 | 高度差 ≤ 1 |
| 平衡嚴格度 | 較寬鬆 | 嚴格 |
| 插入/刪除效率 | 較快 (旋轉次數少) | 較慢 (旋轉次數多) |
| 查詢效率 | 較慢 | 較快 |
| 最大高度 | 2 log(n+1) | 1.44 log n |
| 應用場景 | Java TreeMap, C++ map | 資料庫索引 |
紅黑樹特性:
- 顏色標記: 每個節點帶有紅或黑的顏色標記
- 平衡保證: 最長路徑 ≤ 最短路徑的 2 倍
- 高度保證: 對於 n 個節點，樹高度 ≤ 2 log(n+1)
- 插入修復: 最多 2 次旋轉，O(log n) 重新著色
- 刪除修復: 最多 3 次旋轉
- 哨兵節點: 使用 TNULL 簡化邊界處理
關鍵概念:
- 紅黑樹五大性質的驗證
- 黑高 (Black Height) 的計算
- 左旋轉與右旋轉操作
- 插入後的修復策略（三種情況）
- 哨兵節點 (TNULL) 的使用
- 紅黑樹與 AVL 樹的比較
主題: Trie 前綴樹與雜湊表應用
D1345490_1.py- Trie 前綴樹實現D1345490_2.py- 雜湊表演算法 (Two Sum)Trie and Hash.pdf- 教學文件
完整的 Trie 樹實現，用於高效的字串前綴搜索。
class Trie:
def add_Word(self, word) # 添加單詞
def search_Word(self, word) # 搜尋單詞
def query(self, prefix, k) # 查詢前綴並返回頻率最高的 k 個結果
def remove_Word(self, word) # 刪除單詞關鍵功能:
add_Word: 支持重複添加單詞，並記錄頻率。query: 根據前綴查找單詞，並按照 頻率 和 字典序 進行排序。remove_Word: 刪除單詞（如果單詞頻率大於 1，則只減少頻率）。
測試案例:
# 插入: "Apple", "Apple", "App", "Application"
# 查詢 "App" (k=5): [('App', 1), ('Apple', 2), ('Application', 1)]
# 移除 "Apple" 一次後
# 查詢 "App" (k=5): [('App', 1), ('Apple', 1), ('Application', 1)]使用雜湊表（字典）解決 LeetCode 經典問題 "Two Sum"。
def two_sum(nums, target):
"""
在整數陣列中查找兩個數，使其和為目標值
時間複雜度: O(n)
空間複雜度: O(n)
"""
seen = {} # 雜湊表，用於存儲看過的數字及其索引
for i, num in enumerate(nums):
remain = target - num
if remain in seen:
return (seen[remain], i)
seen[num] = i測試案例:
# 輸入: nums = [2, 7, 11, 15], target = 9
# 輸出: (0, 1) (因為 nums[0] + nums[1] == 9)關鍵概念:
- Trie (前綴樹): 高效的字串儲存與前綴查詢結構。
- 雜湊表 (Hash Table): O(1) 時間複雜度的查找、插入和刪除。
- Two Sum 問題: 雜湊表的經典應用場景。
主題: 歸併排序與快速排序 (Merge Sort & Quick Sort)
D1345490_1.py- 歸併排序 (Merge Sort)D1345490_2.py- 快速排序 (Quick Sort)Assignment.pdf- 作業說明文件
實現穩定的歸併排序演算法：
def merge_sort(nums):
# Divide and Conquer 策略
# 時間複雜度: O(n log n)
# 空間複雜度: O(n)實現經典的快速排序演算法：
def quick_sort(nums):
# 選擇 Pivot 進行分區
# 平均時間複雜度: O(n log n)
# 最差時間複雜度: O(n²)關鍵概念:
- Divide and Conquer (分治法)
- 遞迴實現排序
- 穩定排序 vs 不穩定排序
主題: 貪婪演算法 (Greedy Algorithms)
Count_min_length.py- 最小成本連接問題Greep_Heap.py- 跳躍遊戲 (Jump Game)Assignment.pdf- 作業說明文件
類似 Huffman Coding 的概念，每次選擇最小的兩個元素合併：
def count_min_length(data):
# 每次取最小的兩個數相加
# 累積成本即為總成本
# 類似 Huffman Tree 建構過程計算到達終點的最少跳躍次數：
def jump_times(data):
# 使用貪婪策略
# 每次選擇能跳最遠的範圍
# 時間複雜度: O(n)關鍵概念:
- 貪婪策略 (局部最優解 -> 全局最優解)
- 堆積 (Heap) 在貪婪算法中的應用 (用於快速取最小值)
- 區間覆蓋問題
主題: 深度優先搜尋 (DFS) 與廣度優先搜尋 (BFS)
D1345490_1.py- 迷宮路徑搜尋 (Maze Path Finding)D1345490_2.py- 島嶼數量 (Number of Islands)Assignment.pdf- 作業說明文件
比較 DFS 與 BFS 在迷宮搜尋中的差異：
def DFS(data, x, y):
# 深度優先搜尋
# 尋找是否存在路徑 (可行性)
def BFS(data, start, end):
# 廣度優先搜尋
# 尋找最短路徑
# 記錄路徑來源 (parent)LeetCode 200 經典題，計算網格中相連的陸地數量：
def number_of_island_DFS(data):
# 使用 DFS 遍歷並標記已訪問陸地
def number_of_island_BFS(data):
# 使用 BFS 遍歷並標記已訪問陸地關鍵概念:
- DFS vs BFS 的特性與應用場景
- Stack (遞迴) vs Queue (佇列) 的使用
- 圖形遍歷與連通分量 (Connected Components)
- Python: 3.12 或以上
- 作業系統: macOS, Linux, Windows
- 依賴套件: 無 (僅使用 Python 標準庫)
git clone git@github.com:Yacolate0519-cmd/DataStructure.git
cd DataStructure每個單元的程式碼都可以直接執行：
# 執行 Linked List 範例
python 1_3/Linked_list.py
# 執行排序演算法
python 1_4/Algorithm.py
# 執行樹的遍歷
python 1_3/Tree.py
# 執行對稱樹檢驗
python 1_5/Test2.py# 單元 1: 二元搜尋
cd 1_1 && python main.py
# 單元 2: Two Pointers
cd 1_2 && python Test2.py
# 單元 3: 資料結構
cd 1_3 && python Linked_list.py
cd 1_3 && python Queue.py
cd 1_3 && python Tree.py
# 單元 4: 排序與遞迴
cd 1_4 && python Algorithm.py
cd 1_4 && python main.py
# 單元 5: 樹的對稱性
cd 1_5 && python Test2.py
# 單元 6: 鏈表與矩陣應用
cd 1_6 && python D1345490_1.py
cd 1_6 && python D1345490_2.py
# 單元 7: AVL 平衡樹
cd 1_7 && python D1345490_1.py
cd 1_7 && python D1345490_2.py
# 單元 8: 紅黑樹
cd 1_8 && python D1345490_1.py
cd 1_8 && python D1345490_2.py
# 單元 9: Trie 與雜湊表
cd 1_9 && python D1345490_1.py
cd 1_9 && python D1345490_2.py
# 單元 10: 排序演算法複習
cd 1_10 && python D1345490_1.py
cd 1_10 && python D1345490_2.py
# 單元 11: 貪婪演算法
cd 1_11 && python Count_min_length.py
cd 1_11 && python Greep_Heap.py
# 單元 12: DFS 與 BFS
cd 1_12 && python D1345490_1.py
cd 1_12 && python D1345490_2.py本專案實現了以下資料結構：
| 資料結構 | 檔案 | 特點 |
|---|---|---|
| 單向鏈表 | 1_3/Linked_list.py |
完整的插入、刪除、查找操作 |
| 雙向鏈表 | 1_3/Queue_1.py |
支援前後端雙向操作 |
| 堆疊 (Stack) | 1_3/D1345490_1.py |
MinStack 變種，O(1) 查詢最小值 |
| 佇列 (Queue) | 1_3/Queue.py |
環形佇列實現 |
| 環形佇列 | 1_3/D1345490_3.py |
詳細中文註解版本 |
| 資料結構 | 檔案 | 特點 |
|---|---|---|
| 二元搜尋樹 (BST) | 1_3/Tree.py |
插入、三種遍歷方式 |
| 平衡 BST | 1_4/D1345490_2.py |
從排序鏈表構建 |
| 對稱樹檢驗 | 1_5/Test2.py |
遞迴比較左右子樹 |
| AVL 樹 | 1_7/D1345490_1.py |
自平衡 BST，四種旋轉操作 |
| 紅黑樹 | 1_8/D1345490_2.py |
自平衡 BST，顏色標記與修復 |
- Binary Search (
1_1/main.py) - O(log n)
- Bubble Sort (
1_4/Algorithm.py) - O(n²) - Merge Sort (
1_4/Algorithm.py) - O(n log n) - Quick Sort (
1_4/Algorithm.py) - O(n log n)
- Tower of Hanoi (
1_4/main.py) - 經典遞迴問題 - 樹的遍歷 (
1_3/Tree.py) - 前序、中序、後序 - 鏈表轉樹 (
1_4/D1345490_2.py) - 快慢指針 + 遞迴
- AVL 旋轉 (
1_7/D1345490_1.py) - 四種旋轉操作 (LL, LR, RR, RL) - AVL 自動平衡 (
1_7/D1345490_1.py) - 插入/刪除後平衡維護 - 紅黑樹旋轉 (
1_8/D1345490_2.py) - 左旋轉與右旋轉 - 紅黑樹修復 (
1_8/D1345490_2.py) - 插入後的三種修復情況 - 紅黑樹驗證 (
1_8/D1345490_1.py) - 五大性質的遞迴驗證
- Two Pointers (
1_2/Test2.py) - 容器盛水問題 - Stack 應用 (
1_2/Test3.py) - 括號匹配 - BFS (
1_4/D1345490_2.py) - 層序遍歷 - 鏈表數學 (
1_6/D1345490_1.py) - 兩數相加 - 矩陣遍歷 (
1_6/D1345490_2.py) - 螺旋矩陣
建議按照以下順序學習：
1. 1_1 搜尋演算法
↓
2. 1_2 Two Pointers 技巧
↓
3. 1_3 線性資料結構
├─ Linked List (基礎)
├─ Stack & Queue
└─ Tree (入門)
↓
4. 1_4 排序與遞迴
├─ 排序演算法比較
├─ Hanoi 遞迴思維
└─ 鏈表轉樹 (綜合應用)
↓
5. 1_5 樹的進階問題
└─ 對稱性檢驗 (遞迴應用)
↓
6. 1_6 鏈表與矩陣應用
├─ 兩數相加 (進位處理)
└─ 螺旋矩陣 (遞迴遍歷)
↓
7. 1_7 AVL 平衡樹
├─ 平衡因子與樹高度
├─ 四種旋轉操作
└─ 自動平衡維護 (綜合應用)
↓
8. 1_8 紅黑樹
├─ 紅黑樹五大性質
├─ 黑高計算與驗證
├─ 插入與修復操作
└─ 紅黑樹 vs AVL 樹 (進階比較)
↓
9. 1_9 Trie 與雜湊表
├─ Trie 前綴樹
└─ 雜湊表應用 (Two Sum)
↓
10. 1_10 排序演算法複習
├─ 歸併排序 (Merge Sort)
└─ 快速排序 (Quick Sort)
↓
11. 1_11 貪婪演算法
├─ 最小成本連接 (Huffman-like)
└─ 跳躍遊戲 (Jump Game)
↓
12. 1_12 DFS 與 BFS 演算法
├─ 迷宮路徑搜尋
└─ 島嶼數量 (連通分量)
基礎 → 技巧 → 結構 → 演算法 → 應用 → 進階樹結構
↓ ↓ ↓ ↓ ↓ ↓ ↓
搜尋 雙指針 鏈表 排序 樹的 AVL樹 紅黑樹
堆疊 遞迴 對稱性 自平衡 顏色平衡
佇列 鏈表+ 樹旋轉 修復策略
樹 矩陣 黑高計算
專案包含以下 PDF 教學文檔：
1_3/Stack and Queue.pdf- Stack 與 Queue 教學1_4/Recursion.pdf- 遞迴概念教學1_5/題目.pdf- 第 5 單元習題說明1_7/Assignment.pdf- AVL Tree 作業說明1_8/Assignment.pdf- Red-Black Tree 作業說明
每個實作都包含 if __name__ == '__main__': 測試區塊：
if __name__ == '__main__':
# 測試案例 1
# 測試案例 2
# 預期輸出特別是在複雜實作中，如 D1345490_3.py：
# 常見錯誤說明
# 正確的實現方式
# 邊界條件處理程式碼中標註了關鍵演算法的時間複雜度：
- O(1) - 常數時間
- O(log n) - 對數時間
- O(n) - 線性時間
- O(n log n) - 線性對數時間
- O(n²) - 平方時間
- 總程式碼行數: ~1800 行
- Python 檔案: 35 個
- 平均每檔: 50 行
- 課程單元: 12 個
- 實現的資料結構: 12+ 種
- 實現的演算法: 25+ 種
歡迎提交 Issue 和 Pull Request！
- Fork 本專案
- 建立您的 Feature Branch (
git checkout -b feature/AmazingFeature) - Commit 您的變更 (
git commit -m 'Add some AmazingFeature') - Push 到 Branch (
git push origin feature/AmazingFeature) - 開啟一個 Pull Request
- 遵循 PEP 8 風格指南
- 添加適當的中文註解
- 包含測試案例
- 標註時間複雜度
本專案採用 MIT 授權 - 詳見 LICENSE 檔案
Yacolate0519-cmd
- GitHub: @Yacolate0519-cmd
- Repository: DataStructure
- 感謝所有資料結構與演算法課程的教材
- 感謝 LeetCode 提供的經典題目
- 感謝開源社群的貢獻
如有任何問題或建議，歡迎：
- 開啟 GitHub Issue
- 提交 Pull Request
最後更新: 2025-12-27 專案狀態: 持續更新中 🚧
Happy Coding! 🎉