3.1 資料操作：插入、刪除、查找
插入 (Insert)：
將新元素加入資料結構的操作。插入可以發生在資料結構的開始、結束或任意位置。
刪除 (Delete)：
從資料結構中刪除元素的操作。刪除可以根據元素的值、索引或位置進行。
查找 (Search)：
在資料結構中找到元素的操作。查找可以根據值或其他標準進行。
操作示例：
- 陣列： 插入和刪除需要移動元素，這可能會消耗時間 —
O(n)。 - 鏈接列表： 如果已知節點位置，插入和刪除可在
O(1)時間內發生。 - 散列表： 查找、插入和刪除通常在平均情況下為
O(1)。 - 樹： 在平衡樹中，查找、插入和刪除的操作可在
O(log n)時間內完成。
3.2 基本概念：陣列、列表、堆疊、隊列
陣列
陣列 是一個元素類型相同的序列，可以通過索引訪問。
操作複雜度：索引訪問 — O(1)，插入和刪除 — O(n)。
範例：創建陣列，修改元素並輸出結果
# 創建一個數字陣列
arr = [1, 2, 3, 4, 5]
# 修改索引為2的元素 (第三個元素，因為索引從0開始)
arr[2] = 10
# 輸出修改後的陣列
print(arr) # 輸出: [1, 2, 10, 4, 5]
# 在陣列末尾添加新元素
arr.append(6)
print(arr) # 輸出: [1, 2, 10, 4, 5, 6]
# 根據索引刪除元素
del arr[1]
print(arr) # 輸出: [1, 10, 4, 5, 6]
列表
列表 是一個集合，裡面的每個元素都包含一個到下一個元素（單鏈表）或到下一個和上一個元素（雙鏈表）的引用。
操作複雜度：插入和刪除 — O(1) 如果已知位置，查找 — O(n)。
範例：創建簡單的單鏈表並迭代遍歷
# 定義列表節點結構
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 創建單鏈表
node1 = Node("101")
node2 = Node("102")
node3 = Node("103")
# 連接節點
node1.next = node2
node2.next = node3
# 設置列表的頭部
list_head = node1
# 遍歷列表並輸出資料
current = list_head
while current:
print(current.data)
current = current.next
# 輸出:
# 101
# 102
# 103
堆疊 (Stack)
堆疊 是一個元素的集合，遵循 LIFO（後進先出）的原則：最後加入的最先出。
操作複雜度：插入 (push) 和刪除 (pop) — O(1)。
範例：實現和使用堆疊來檢查括號的平衡性
def is_balanced(expression):
stack = []
opening = "({["
closing = ")}]"
pairs = {")": "(", "}": "{", "]": "["}
for char in expression:
if char in opening:
stack.append(char)
elif char in closing:
if not stack or stack.pop() != pairs[char]:
return False
return len(stack) == 0
# 檢查不同的表達式
print(is_balanced("({[]})")) # 輸出: True
print(is_balanced("([)]")) # 輸出: False
print(is_balanced("((")) # 輸出: False
隊列 (Queue)
隊列 是一個元素的集合，遵循 FIFO（先進先出）的原則：第一個加入的第一個出。
操作複雜度：插入 (enqueue) 和刪除 (dequeue) — O(1)。
範例：實現和使用隊列來模擬任務處理
from collections import deque
class TaskQueue:
def __init__(self):
self.queue = deque()
def add_task(self, task):
self.queue.append(task)
print(f"任務 '{task}' 已加入隊列")
def process_task(self):
if self.queue:
task = self.queue.popleft()
print(f"處理任務: '{task}'")
else:
print("隊列為空")
def display_queue(self):
print("當前任務隊列:", list(self.queue))
# 創建並使用任務隊列
task_queue = TaskQueue()
task_queue.add_task("發送 email")
task_queue.add_task("更新資料庫")
task_queue.add_task("創建報告")
task_queue.display_queue()
task_queue.process_task()
task_queue.process_task()
task_queue.display_queue()
# 輸出:
# 任務 '發送 email' 已加入隊列
# 任務 '更新資料庫' 已加入隊列
# 任務 '創建報告' 已加入隊列
# 當前任務隊列: ['發送 email', '更新資料庫', '創建報告']
# 處理任務: '發送 email'
# 處理任務: '更新資料庫'
# 當前任務隊列: ['創建報告']
3.3 不同類型資料結構的區別
以下是不同比資料結構的主要區別：
陣列：
- 訪問： 快速的索引訪問 —
O(1)。 - 大小變更： 固定大小，增加需要複製所有元素 —
O(n)。 - 適合： 當數據大小已知時的隨機訪問。
鏈接列表：
- 訪問： 慢速的索引訪問 —
O(n)。 - 大小變更： 容易變更大小，插入和刪除在
O(1)時間內。 - 適合： 頻繁增加和刪除元素的情況。
堆疊：
- 工作原則：
LIFO。 - 操作： 插入和刪除只在一端執行 —
O(1)。 - 適合： 反向執行任務，函數調用管理。
隊列：
- 工作原則：
FIFO。 - 操作： 插入和刪除在不同端執行 —
O(1)。 - 適合： 按順序處理任務。
3.4 不同資料結構的應用
各種資料結構的實際應用示例：
陣列
存儲固定長度的數據，比如星期或月份。
範例：使用陣列來處理星期
# 創建一個包含星期的陣列
days = ["星期一", "星期二", "星期三", "星期四", "星期五", "星期六", "星期日"]
# 通過索引獲取星期 (例如，第三天)
print(days[2]) # 輸出: 星期三
# 修改星期名稱
days[0] = "星期一 (一周的開始)"
print(days[0]) # 輸出: 星期一 (一周的開始)
# 遍歷所有星期
for day in days:
print(day)
# 輸出:
# 星期一 (一周的開始)
# 星期二
# 星期三
# 星期四
# 星期五
# 星期六
# 星期日
鏈接列表
動態集合的實現，其中元素可以從集合中間增減。
範例：實現和使用鏈表來存儲待辦事項列表
class TodoItem:
def __init__(self, task):
self.task = task
self.next = None
class TodoList:
def __init__(self):
self.head = None
def add_task(self, task):
new_item = TodoItem(task)
if not self.head:
self.head = new_item
else:
current = self.head
while current.next:
current = current.next
current.next = new_item
def display_tasks(self):
current = self.head
if not current:
print("待辦事項清單為空")
else:
while current:
print(f"- {current.task}")
current = current.next
# 創建並使用待辦事項列表
todo = TodoList()
todo.add_task("買食品")
todo.add_task("給媽媽打電話")
todo.add_task("準備簡報")
print("我的待辦事項列表:")
todo.display_tasks()
# 輸出:
# 我的待辦事項列表:
# - 買食品
# - 給媽媽打電話
# - 準備簡報
堆疊
逆序執行任務，例如遞歸中的函數調用處理，撤銷操作（undo）。
範例：使用堆疊來反轉字符串
def reverse_string(s):
stack = []
# 將字符串的每個字符放入堆疊
for char in s:
stack.append(char)
reversed_s = ''
# 從堆疊中提取字符，形成反轉字符串
while stack:
reversed_s += stack.pop()
return reversed_s
# 使用範例
original = "Hello, World!"
reversed_str = reverse_string(original)
print(f"原始字符串: {original}")
print(f"反轉字符串: {reversed_str}")
# 輸出:
# 原始字符串: Hello, World!
# 反轉字符串: !dlroW ,olleH
隊列
按順序管理任務，例如打印任務、客戶服務等待隊列。
範例：打印文件隊列的模擬
from collections import deque
class PrinterQueue:
def __init__(self):
self.queue = deque()
def add_document(self, document):
self.queue.append(document)
print(f"文檔 '{document}' 已加入打印隊列")
def print_document(self):
if self.queue:
document = self.queue.popleft()
print(f"打印文檔: '{document}'")
else:
print("打印隊列為空")
def display_queue(self):
print("當前打印隊列:", list(self.queue))
# 創建並使用打印隊列
printer = PrinterQueue()
printer.add_document("報告")
printer.add_document("簡報")
printer.add_document("合同")
printer.display_queue()
printer.print_document()
printer.print_document()
printer.display_queue()
# 輸出:
# 文檔 '報告' 已加入打印隊列
# 文檔 '簡報' 已加入打印隊列
# 文檔 '合同' 已加入打印隊列
# 當前打印隊列: ['報告', '簡報', '合同']
# 打印文檔: '報告'
# 打印文檔: '簡報'
# 當前打印隊列: ['合同']
在這個範例中，我們創建了一個簡單的打印隊列模擬。文件被添加到隊列的末尾，並按它們的加入順序打印，這展示了 FIFO（先進先出）原則。
GO TO FULL VERSION