# Python資料結構與演算法實戰
資料結構和演算法是電腦科學的基礎，也是程式設計師必須掌握的核心技能。Python因其簡潔的語法和豐富的內建資料結構，成為學習演算法的理想語言。
## 1. 基礎資料結構
### 陣列與串列
Python的list是動態陣列，提供了靈活的操作方式：
python
# 基本操作
arr = [1, 2, 3, 4, 5]
arr.append(6) # 添加元素
arr.insert(0, 0) # 在指定位置插入
arr.remove(3) # 移除指定值
arr.pop() # 移除最後一個元素
# 串列推導式
squares = [x**2 for x in range(10)]
even_numbers = [x for x in range(20) if x % 2 == 0]
### 堆疊（Stack）
python
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
return None
def peek(self):
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# 使用範例
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 輸出: 2
### 佇列（Queue）
python
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
return None
def front(self):
if not self.is_empty():
return self.items[0]
return None
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
## 2. 進階資料結構
### 二元樹
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
else:
self._insert_recursive(self.root, val)
def _insert_recursive(self, node, val):
if val < node.val:
if node.left:
self._insert_recursive(node.left, val)
else:
node.left = TreeNode(val)
else:
if node.right:
self._insert_recursive(node.right, val)
else:
node.right = TreeNode(val)
def inorder_traversal(self, node):
result = []
if node:
result.extend(self.inorder_traversal(node.left))
result.append(node.val)
result.extend(self.inorder_traversal(node.right))
return result
### 雜湊表
python
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
hash_index = self._hash(key)
bucket = self.table[hash_index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
hash_index = self._hash(key)
bucket = self.table[hash_index]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
def remove(self, key):
hash_index = self._hash(key)
bucket = self.table[hash_index]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return
raise KeyError(key)
## 3. 經典演算法
### 排序演算法
#### 快速排序
python
def quicksort(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 quicksort(left) + middle + quicksort(right)
# 測試
numbers = [3, 6, 8, 10, 1, 2, 1]
print(quicksort(numbers)) # [1, 1, 2, 3, 6, 8, 10]
#### 合併排序
python
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
### 搜尋演算法
#### 二元搜尋
python
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:
left = mid + 1
else:
right = mid - 1
return -1 # 找不到
# 測試
sorted_arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(sorted_arr, 7)) # 輸出: 3
## 4. 動態規劃
### 費氏數列
python
def fibonacci_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 空間優化版本
def fibonacci_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
### 背包問題
python
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w-weights[i-1]] + values[i-1]
)
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
# 測試
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity)) # 輸出: 9
## 5. 圖論演算法
### 深度優先搜尋（DFS）
python
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)
# 範例圖
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
dfs(graph, 'A') # 輸出: A B D E F C
### 廣度優先搜尋（BFS）
python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
bfs(graph, 'A') # 輸出: A B C D E F
## 總結
本文涵蓋了Python中的核心資料結構和演算法：
1. **基礎資料結構**：陣列、堆疊、佇列
2. **進階資料結構**：二元樹、雜湊表
3. **排序演算法**：快速排序、合併排序
4. **搜尋演算法**：二元搜尋
5. **動態規劃**：費氏數列、背包問題
6. **圖論**：DFS、BFS
理解這些概念並能靈活運用，將大大提升你的程式設計能力。建議多練習實作，並分析時間複雜度和空間複雜度。