ECCH5｜數據結構（Data Structures）

數據結構（Data Structure）是用來組織與儲存資料的一套方法， 目的是令「存取、插入、刪除、搜尋、排序、走訪」等操作更有效率、更易管理。 簡單來說：同一批資料，放法不同，做同一件事所需步數亦會不同。

以下是 DSE 常見 4 種循環偽代碼寫法（格式重點：關鍵字用設／當／執行／重覆／直至）。 你可以把它當作「模板」，之後每個例子示範我都會使用同一套格式。

設 i 由 1至 9
    ...

當 x > 5
    ...

執行
    ...
當 x > 5

重覆
    ...
直至 x > 5

以下課題（陣列 Array、堆疊 Stack、隊列 Queue、循環隊列 Circular Queue、線性鏈表 Linked List）是 DSE 常見的基本數據結構。
建議先掌握「規則」（LIFO/FIFO）與「操作成本」（O(1)/O(n)），再做題目整合。
本頁每個課題都附有可執行的 Python 小練習（放在例子示範之後），請邊看邊做。

重點

• 索引存取：用 index 直接讀取 arr[i]，概念上視作 O(1)。
• 插入／刪除會移位：若不是尾端操作，往往要搬移元素，時間多為 O(n)。
• 二維陣列定位：先列後欄，用 arr[row][col]；row/col 轉錯會取錯格。
• Row-major 理解：2D 可以攤平成 1D；線性索引 ≈ row * 欄數 + col（逐列掃描）。
• 走訪與搜尋：用迴圈逐格處理（例如找最大值、計算總和、掃描 2D 表格）。

按我顯示更多內容

概念講解：陣列的優勢與限制

陣列最核心的概念是「位置（index）」。當你寫 arr[i]，其實你是要求系統去第 i 個位置取數據。 因為位置是已知，所以不需要逐個比較去搵，讀取通常快。

但陣列要維持「次序」：例如你想將一個新元素插入到中間，為了騰出空位，後面元素就要向後搬。 所以即使讀取快，插入／刪除位置錯了都可能好慢。

二維陣列可以視為「表格」。定位一格需要兩個索引：先列（row）後欄（col）。 如果你用 row-major 角度看，掃描表格其實是逐列掃過去，這個理解對之後 heap / graph 的陣列表示很有幫助。

表格整理：常見操作與直覺成本

圖像化 + 可操作示範

例子示範：偽代碼（4 種迴圈） vs Python（for + while）

例子：在陣列中找第一個等於 target 的索引；找不到回傳 -1。

arr = [4, 9, 2, 9]

target = 9
ans = -1

for i in range(len(arr)):
    if arr[i] == target:
        ans = i
        break

print(ans)

arr = [4, 9, 2, 9]

target = 9
ans = -1

i = 0
while i < len(arr):
    if arr[i] == target:
        ans = i
        break
    i += 1

print(ans)

ans ← -1
設 i 由 0至 n-1
    若 arr[i] = target
        ans ← i
        離開循環

ans ← -1
i ← 0
當 i < n
    若 arr[i] = target
        ans ← i
        離開循環
    i ← i + 1

ans ← -1
i ← 0
執行
    若 arr[i] = target
        ans ← i
        離開循環
    i ← i + 1
當 i < n

ans ← -1
i ← 0
重覆
    若 arr[i] = target
        ans ← i
        離開循環
    i ← i + 1
直至 i ≥ n

小遊戲：線性檢索（Linear Search）拖放挑戰

系統會隨機產生一個陣列與目標值 target。請由 index = 0 開始，依次把「指針」拖到下一格進行檢查； 當找到 target 後，系統會產生「回傳索引」代幣，請把它拖到回傳框。
重點：線性檢索必須按次序逐格檢查，不能跳格。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Array / 2D Array）

重點

• LIFO：後進先出，只能由頂部進出。
• 三大操作：push（加入頂部）、pop（移除頂部）、peek（查看頂部）。
• 常見用途：括號配對、回溯（backtracking）、撤銷（undo）、深度優先搜尋（DFS）。
• 空堆疊與安全檢查：pop 前先判斷是否為空，避免錯誤與邏輯漏洞。
• 封裝成 ADT：用函式／類別把 push/pop/peek/is_empty 包起來，令程式更清晰。

按我顯示更多內容

概念講解：LIFO 的典型應用

Stack 的特別之處不是它「功能多寡」，而是它限制了你如何存取資料：只准由頂部進出。 這個限制反而令很多演算法更清晰，例如「處理到一半想回到上一層」就直接 pop。

以括號配對為例：每遇到一個左括號，就等於開了一個「未完成的工作」；當遇到右括號，就要把最近未完成那個工作關閉。 由於要處理「最近」那個，LIFO 就非常適合。

實作上，你可以用 Python list 尾端做 stack：append 當 push，pop() 當 pop。 但記住：空 stack pop 會出錯，所以要先檢查長度。

表格整理：Stack 操作

可操作示範：Stack push/pop

例子示範：偽代碼（4 種迴圈） vs Python（for + while）

例子：括號配對（只處理 '(' 與 ')'）。

s = "(()())()"
stack = []
ok = True

for ch in s:
    if ch == "(":
        stack.append(ch)
    else:
        if len(stack) == 0:
            ok = False
            break
        stack.pop()

if ok and len(stack) != 0:
    ok = False

print(ok)

s = "(()())()"
stack = []
ok = True

i = 0
while i < len(s):
    ch = s[i]
    if ch == "(":
        stack.append(ch)
    else:
        if len(stack) == 0:
            ok = False
            break
        stack.pop()
    i += 1

if ok and len(stack) != 0:
    ok = False

print(ok)

ok ← True
設 i 由 0至 n-1
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
若 ok = True 且 stack 非空
    ok ← False

ok ← True
i ← 0
當 i < n
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
    i ← i + 1
若 ok = True 且 stack 非空
    ok ← False

ok ← True
i ← 0
執行
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
    i ← i + 1
當 i < n
若 ok = True 且 stack 非空
    ok ← False

ok ← True
i ← 0
重覆
    ch ← s[i]
    若 ch = "("
        push(stack, ch)
    否則
        若 stack 為空
            ok ← False
            離開循環
        pop(stack)
    i ← i + 1
直至 i ≥ n
若 ok = True 且 stack 非空
    ok ← False

小遊戲：堆疊（Stack）指令拖放練習

系統會提供一個初始堆疊、一些「新數據」以及一串指令（push/pop）。 請按指令次序完成操作：
・push：把指定的新數據拖到堆疊區（會放在頂部）。
・pop：把頂部元素拖到「回傳區」。
做錯時會提示「正確下一步」。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Stack）

重點

• FIFO：先進先出；入隊加尾、出隊移頭。
• 避免慢操作：如果用 list 直接 pop(0) 會慢；可用 head 指針/循環隊列思路。
• 常見用途：排隊系統、BFS、任務排程。
• 常見實作：在 Python 可用 collections.deque 做 O(1) 的入隊／出隊（概念更貼近真・隊列）。
• 封裝成 ADT：把 enqueue / dequeue / front / is_empty / size 寫成一套介面，做題目更穩。

按我顯示更多內容

概念講解：FIFO 與實作技巧

Queue 的概念其實非常貼近生活：排隊就是 FIFO。 但寫程式時，重點是你用甚麼方式實作 dequeue。 如果你用 Python list 的 pop(0)，每次都要把後面元素向前搬，會慢。

一個常見技巧是用 head 指針：入隊仍然 append，出隊不搬陣列，只是 head += 1。 最後真正隊列內容就是 q[head:]。 這個思路亦是循環隊列（circular queue）的基礎。

在偽代碼中，亦常見用一個（可以很長的）陣列配合「隊列開始 front」及「隊列結束 rear」（或 head / tail），再加上一個「項目數量 count」。入隊時把新值寫到 rear；出隊時不需要把元素真的從陣列移除，只要把 front 往後移一格（或把 count 減一）即可完成更新。陣列內舊位置的值可以保留，但會被視為『不再屬於隊列』。

當你理解到 queue 的 FIFO 特性，你就會自然明白 BFS 為甚麼會「逐層」走訪：因為先發現的節點先出隊、先展開。

可操作示範（一）：移位式隊列（像排隊般全隊向前）

這個版本最貼近「現實排隊」的直覺：enqueue 就在隊尾加入新元素；dequeue 就把隊首元素移走， 然後整隊人向前移一格（也就是把陣列內的元素逐個向前搬移）。

你應該觀察：每次 dequeue 後，原本在第 1、2、3… 位的人都會「搬位」，因此在陣列實作中，dequeue 往往是 O(n)。

# 假設隊列儲存在 arr[0..size-1]
# enqueue(x)：加到尾端
arr[size] ← x
size ← size + 1

# dequeue()：取 arr[0]，其餘向前移一格
若 size = 0
    回傳 NULL
y ← arr[0]
設 i 由 0至 size-2
    arr[i] ← arr[i+1]
size ← size - 1
回傳 y

q = [10, 20, 30]

# enqueue
x = 99
q.append(x)      # 加到隊尾

# dequeue（會把後面元素向前搬）
front = q.pop(0) # 取走隊首
print("dequeue ->", front)
print("queue =", q)

可操作示範（二）：指標式隊列（只移動 head / tail，不搬移元素）

提示：在「指標式隊列」中，dequeue 後不必把元素從陣列刪走；只要 head 往後移一格即可。 你會看到舊值仍留在格子內，但已不再屬於隊列。

例子示範：偽代碼（4 種迴圈） vs Python（for + while）

例子：處理隊列中所有任務（直到 queue 清空），並累計總時間。

tasks = [2, 5, 1, 3]

total = 0
for t in tasks:
    total += t

print(total)

tasks = [2, 5, 1, 3]
q = tasks[:]
head = 0

total = 0
while head < len(q):
    total += q[head]
    head += 1

print(total)

total ← 0
設 i 由 0至 n-1
    total ← total + task[i]

total ← 0
head ← 0
當 head < n
    total ← total + task[head]
    head ← head + 1

total ← 0
head ← 0
執行
    total ← total + task[head]
    head ← head + 1
當 head < n

total ← 0
head ← 0
重覆
    total ← total + task[head]
    head ← head + 1
直至 head ≥ n

小遊戲：隊列（Queue）指令拖放練習（FIFO）

你會得到一個初始隊列與一串指令（enqueue/dequeue）。 請按次序完成：enqueue 時把指定新數據拖到隊尾；dequeue 時把隊首元素拖到回傳區。
重點：隊列是 FIFO（先進先出），只能從隊首取出。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（隊列）

重點

• 固定容量：用一個大小為 n 的陣列作為儲存區（buffer），空位可重用。
• 兩個指標：head 指向下一個出隊位置；tail 指向下一個入隊位置。
• 循環（wrap-around）：指標到達尾端後回到 0；用 (i+1) mod n 表示。
• 滿／空判斷：常見方法是用 size 記錄元素數；或用「下一格是否等於 head」判斷滿。
• 覆蓋模式：當隊列已滿仍入隊時，會覆蓋最舊元素，並把 head 亦向前推一格（常見於資料串流／固定緩衝區）。
• 避免假溢出：普通隊列若只向前移 head，尾端可能有空位但無法再入隊；循環隊列可重用空位。

按我顯示更多內容

概念講解：為何需要循環隊列

在「隊列」的題目中，我們希望維持 FIFO（先進先出）。如果用固定大小的陣列實作，最直觀的方法是用兩個指標： head 指向隊首、tail 指向下一個可放入的位置。每次出隊後，head 向前移動。

問題是：當 tail 走到陣列尾端時，即使前面已經出隊騰出了空位，尾端也「看似」沒有位置可以再入隊，這就是假溢出（false overflow）。 循環隊列的做法是把陣列當作一個「環」，讓指標到尾端後回到 0，從而重用空位。

實作時最關鍵是兩點：第一是用 (i+1) mod n 處理循環；第二是清楚定義「空」與「滿」。 最穩的方法是用 size 記錄目前元素數，避免 head==tail 造成判斷混亂。

本頁示範採用「覆蓋模式」：當 size==n（已滿）仍然 enqueue，新元素會寫入 tail（此時 tail==head），然後 head 會同步向前推一格，代表最舊元素被覆蓋而離開隊列。這種設計常用於固定容量的緩衝區，例如保留最近 n 筆資料。

表格整理：操作、指標與條件

可操作示範：循環隊列（固定容量）

提示：本示範採用「覆蓋模式」。當 size==n（已滿）仍 enqueue，新值會覆蓋最舊元素（head 會同步向前移）。

例子示範：用循環隊列處理一串操作

示範重點：mod 處理循環；先判斷滿／空；enqueue 先寫入再移 tail，dequeue 先讀取再移 head。

ops = ["enq 5", "enq 8", "enq 3", "deq", "enq 9", "deq", "enq 1", "enq 7", "enq 6"]
n = 5
buf = [None] * n
head = 0
tail = 0
size = 0

for op in ops:
    if op.startswith("enq"):
        x = int(op.split()[1])
        if size == n:
            # 覆蓋最舊元素：在 tail（此時 tail==head）寫入，並同步推進 head
            buf[tail] = x
            tail = (tail + 1) % n
            head = (head + 1) % n
            print("滿：覆蓋最舊 -> enqueue", x)
        else:
            buf[tail] = x
            tail = (tail + 1) % n
            size += 1
    else:  # deq
        if size == 0:
            print("空：不能 dequeue")
        else:
            x = buf[head]
            buf[head] = None
            head = (head + 1) % n
            size -= 1
            print("dequeue ->", x)

print("buf =", buf)
print("head =", head, "tail =", tail, "size =", size)

# 假設 buf / head / tail / size 已由上面程式得到
out = []
while size > 0:
    x = buf[head]
    buf[head] = None
    head = (head + 1) % n
    size -= 1
    out.append(x)

print("全部出隊次序 =", out)

設每個 op 依序由 ops 取出
    若 op 為 enqueue(x)
        若 size == n
            輸出「滿」
        否則
            buffer[tail] = x
            tail = (tail + 1) mod n
            size = size + 1
    否則（op 為 dequeue）
        若 size == 0
            輸出「空」
        否則
            x = buffer[head]
            buffer[head] = 空
            head = (head + 1) mod n
            size = size - 1
            輸出 x

當 size > 0
    x = buffer[head]
    buffer[head] = 空
    head = (head + 1) mod n
    size = size - 1
    輸出 x

執行
    x = buffer[head]
    buffer[head] = 空
    head = (head + 1) mod n
    size = size - 1
    輸出 x
當 size > 0

重覆
    x = buffer[head]
    buffer[head] = 空
    head = (head + 1) mod n
    size = size - 1
    輸出 x
直至 size == 0

小遊戲：循環隊列（Circular Queue）拖放挑戰（覆蓋模式）

此小遊戲採用「覆蓋模式」：當循環隊列已滿仍然 enqueue，新元素會覆蓋最舊元素（同時把 head 推進一格）。 請按指令次序完成操作：
・enqueue：把指定新數據拖到tail 指向的格。
・dequeue：把head 指向的格拖到回傳區。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（循環隊列）

重點

• 節點串接：每個節點包含資料 + next 指針（指向下一個節點）。
• 定位後插入/刪除快：只需改指針，不用整體移位。
• 無法索引直取：要由 head 開始逐個走訪，取第 k 個通常要 O(n)。
• 指針要小心：接錯 next 可能造成遺失節點或形成 cycle（循環）。
• 封裝與常用操作：用類別整理 head/tail，以及 append / find / delete 等操作，較不易「斷鏈」。

按我顯示更多內容

概念講解：指標走訪與插入刪除

Linked list 的重點是「資料不靠索引定位，而是靠連結」。 所以你要存取某個位置，就要由 head 開始，然後 next 一步一步行。 這個特性令到 random access（隨機存取）不方便，但插入/刪除（定位後）又非常自然。

考試與教學時，好多人覺得指針抽象，所以我哋可以用「索引當指針」去理解： 用 nxt[i] 存下一個節點的索引；-1 代表 NULL。 你會發現操作指針其實就是改幾個數字。

最後要提醒：指針改動次序好重要。 插入時要先保存原 next，再把新節點接上；刪除時要處理刪 head 的特別情況。 這一些都是 DSE 常見失分位。

圖像化 + 可操作示範：拖拉 next 指針

拖住每個節點右邊的圓點（●），拖到另一個節點或 NULL，就可以改 next。下面會即時顯示由 head 走訪的結果（亦會提示是否出現 cycle）。

可操作示範：線性鏈表加入／刪除（拖放）

上一個示範讓你自由拖拉 next 指針，建立直覺；下面這個示範則按照「線性鏈表」的規則， 讓你練習加入／刪除節點時指針應如何更新。系統會自動計算並顯示 prev/next。

例子示範：偽代碼（4 種迴圈） vs Python（for + while）

例子：沿 next 走訪 linked list，把所有值加總。

# 用索引當指針
val = [10, 20, 30]
next_idx = [1, 2, -1]
head = 0

s = 0
curr = head
while curr != -1:
    s += val[curr]
    curr = next_idx[curr]

print(s)

val = [10, 20, 30]
next_idx = [1, 2, -1]
head = 0

s = 0
curr = head
n = 3  # 假設已知長度
for _ in range(n):
    s += val[curr]
    curr = next_idx[curr]

print(s)

sum ← 0
curr ← head
設 i 由 1至 n
    sum ← sum + val[curr]
    curr ← next[curr]

sum ← 0
curr ← head
當 curr ≠ NULL
    sum ← sum + val[curr]
    curr ← next[curr]

sum ← 0
curr ← head
執行
    sum ← sum + val[curr]
    curr ← next[curr]
當 curr ≠ NULL

sum ← 0
curr ← head
重覆
    sum ← sum + val[curr]
    curr ← next[curr]
直至 curr = NULL

小遊戲：線性鏈表（Linked List）加減節點拖放練習

系統會提供一條初始鏈表、一些新節點，以及一串指令（插入／刪除）。 你需要按指令次序拖放：
・插入：把指定的新節點拖到指令指定的節點上（代表「插入在該節點之後」）。
・刪除：把指令指定的節點拖到「刪除區」。
做對後，系統會自動更新 prev/next，並在表格顯示新的索引與指針。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（線性鏈表）

本部分用較多動畫／互動去建立直覺：Tree Traversal（走訪次序）→ Hash（碰撞處理）→ Heap（優先隊列）→ Graph（BFS/DFS + visited）。 你不需要一次背完所有細節，但要能說得出「為甚麼要用它」以及「它比其他結構好在甚麼地方」。

重點

• 走訪目的：用一個固定次序，把每個節點「visit」一次。
• DFS 家族：前序（根→左→右）、中序（左→根→右）、後序（左→右→根）。
• BFS 層序：逐層走訪，通常配合 queue。

按我顯示更多內容

概念講解：走訪次序的意義

走訪（traversal）其實是為了把「非線性」結構轉成一個「線性次序」。 一旦你得到次序，你就可以做很多線性處理：例如輸出、比較、搜尋。

DFS 三種（前序/中序/後序）最大分別在於「根」在不同時機被 visit。 你可以用一句記法：前序根先，中序根中，後序根後。

層序走訪（level-order）就是 BFS：用 queue 令「先入隊」的節點先被處理，形成逐層效果。 這個概念會延伸到圖（graph）和最短路徑問題。

圖像化：一步一步看走訪次序

例子示範：層序走訪（level-order）如何配合 queue

同一個概念可以用不同迴圈形式表達；考試寫偽代碼時，重點在於「先出隊再入隊」與「直到 queue 清空」的流程。

設 step 由 1至 N
    若 Q 為空
        離開循環
    將 Q 的第一個節點出隊 → u
    輸出 u
    若 u 有左孩子
        將 左孩子 入隊
    若 u 有右孩子
        將 右孩子 入隊

當 Q 不為空
    將 Q 的第一個節點出隊 → u
    輸出 u
    若 u 有左孩子
        將 左孩子 入隊
    若 u 有右孩子
        將 右孩子 入隊

執行
    將 Q 的第一個節點出隊 → u
    輸出 u
    若 u 有左孩子
        將 左孩子 入隊
    若 u 有右孩子
        將 右孩子 入隊
當 Q 不為空

重覆
    將 Q 的第一個節點出隊 → u
    輸出 u
    若 u 有左孩子
        將 左孩子 入隊
    若 u 有右孩子
        將 右孩子 入隊
直至 Q 為空

val   = ["A", "B", "C", "D", "E"]
left  = [ 1,  3, -1, -1, -1]
right = [ 2,  4, -1, -1, -1]
root = 0
N = len(val)

q = [root]
head = 0
order = []

for _ in range(N):
    if head == len(q):   # queue 已空
        break
    u = q[head]
    head += 1
    order.append(val[u])

    if left[u] != -1:
        q.append(left[u])
    if right[u] != -1:
        q.append(right[u])

print(order)

val   = ["A", "B", "C", "D", "E"]
left  = [ 1,  3, -1, -1, -1]
right = [ 2,  4, -1, -1, -1]
root = 0

q = [root]
head = 0
order = []

while head < len(q):
    u = q[head]
    head += 1
    order.append(val[u])

    if left[u] != -1:
        q.append(left[u])
    if right[u] != -1:
        q.append(right[u])

print(order)

小遊戲：Tree Traversal 次序挑戰（點擊節點）

選擇一種走訪（前序／中序／後序／層序），然後依次點擊節點。 做錯會提示你「下一個正確節點」。
重點：把走訪規則變成動作記憶——你會更容易分辨「根在前／中／後」。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Tree Traversal）

重點

• key → index：用 hash function 把 key 映射到陣列索引位置。
• collision 必然出現：要用 chaining / open addressing 處理。
• 負載因子：太滿會變慢；常用 rehash（擴容後重算）改善。

按我顯示更多內容

概念講解：雜湊與碰撞處理

Hash table 的直覺是：不想每次都逐個掃描 key，所以先用 hash function 把 key 變成一個數字，再對表大小取模得到索引。 理想情況下，每個 key 都分散得好平均，就可以用很少步數找到。

但 collision 是一定會出現：因為索引格數有限，而 key 可能無限。 所以 hash table 的真正核心不是「hash」本身，而是「collision 如何處理」。 chaining 是最直觀：同一格存一條清單。

當表愈來愈滿，碰撞機會愈大，查找就愈慢。 所以實際系統會按負載因子擴容，再把所有 key 重新 hash（rehash）。

可操作示範：簡易 hashing（chaining）

例子示範：Linear Probing（開放定址）處理 collision

概念要點：先計算 index = key mod m；若位置已被佔用，就按固定規則（例如 +1）逐格探測（probe），直到找到空位。

設每個 key 依序由 keys 取出
    start = key mod m
    設 step 由 0至 m-1
        idx = (start + step) mod m
        若 table[idx] 為空
            table[idx] = key
            離開循環

設每個 key 依序由 keys 取出
    idx = key mod m
    當 table[idx] 不為空
        idx = (idx + 1) mod m
    table[idx] = key

設每個 key 依序由 keys 取出
    idx = key mod m
    若 table[idx] 不為空
        執行
            idx = (idx + 1) mod m
        當 table[idx] 不為空
    table[idx] = key

設每個 key 依序由 keys 取出
    idx = key mod m
    若 table[idx] 不為空
        重覆
            idx = (idx + 1) mod m
        直至 table[idx] 為空
    table[idx] = key

keys = [15, 11, 27, 8, 12]
m = 5
table = [None] * m

for key in keys:
    start = key % m
    for step in range(m):
        idx = (start + step) % m
        if table[idx] is None:
            table[idx] = key
            break

print(table)

keys = [15, 11, 27, 8, 12]
m = 5
table = [None] * m

for key in keys:
    idx = key % m
    while table[idx] is not None:
        idx = (idx + 1) % m
    table[idx] = key

print(table)

小遊戲：Hash Table（Chaining）拖放練習

你會得到一些 key（整數）以及 bucket 數 m。請把每個 key 拖到正確 bucket： bucket = key mod m。若同一 bucket 出現多個 key，代表碰撞（collision），會放在同一條鏈（chain）內。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Hash Table）

重點

• Heap property：最小堆（min-heap）根最小；最大堆（max-heap）根最大。
• 完整二元樹：可以用陣列表示；parent/child 用索引計算。
• 插入/移除根：靠 sift up/down 維持性質，通常 O(log n)。

按我顯示更多內容

概念講解：堆與優先隊列

Heap 最大優點是：可以快速取得「最小（或最大）」元素，同時插入新元素亦不會太慢。 因為 heap 是完整二元樹，所以高度約 log n，sift up/down 都只需沿樹高移動。

用陣列表示 heap 是一個非常重要的技巧：你不需要真的指針節點，只需用索引計算父子關係。 例如 i 的左孩子是 2i+1，右孩子是 2i+2。

記住：heap 只保證「父比子更符合規則」（例如 min-heap 父 ≤ 子）。 它不是排序結構，所以中間元素不一定有序。

可操作示範：min-heap 插入/取出根

例子示範：Min-Heap 插入（sift up）

插入的兩步：① 把新元素放到陣列尾端；② 與 parent 比較，若更小就交換並向上移，直到回復 min-heap 性質。

將 x 放到 heap 尾端
i = 最後索引
設 step 由 1至 H
    若 i = 0
        離開循環
    p = (i - 1) div 2
    若 heap[i] < heap[p]
        交換 heap[i], heap[p]
        i = p
    否則
        離開循環

將 x 放到 heap 尾端
i = 最後索引
當 i > 0 且 heap[i] < heap[parent(i)]
    交換 heap[i], heap[parent(i)]
    i = parent(i)

將 x 放到 heap 尾端
i = 最後索引
若 i > 0
    執行
        p = (i - 1) div 2
        若 heap[i] < heap[p]
            交換 heap[i], heap[p]
            i = p
    當 i > 0 且 heap[i] < heap[(i - 1) div 2]

將 x 放到 heap 尾端
i = 最後索引
重覆
    若 i = 0
        離開循環
    p = (i - 1) div 2
    若 heap[i] < heap[p]
        交換 heap[i], heap[p]
        i = p
    否則
        離開循環
直至 i = 0

heap = [3, 5, 8, 10, 9]
x = 1

heap.append(x)
i = len(heap) - 1

for _ in range(len(heap)):
    if i == 0:
        break
    p = (i - 1) // 2
    if heap[i] < heap[p]:
        heap[i], heap[p] = heap[p], heap[i]
        i = p
    else:
        break

print(heap)

heap = [3, 5, 8, 10, 9]
x = 1

heap.append(x)
i = len(heap) - 1

while i > 0:
    p = (i - 1) // 2
    if heap[i] < heap[p]:
        heap[i], heap[p] = heap[p], heap[i]
        i = p
    else:
        break

print(heap)

小遊戲：Heap（最小堆）加入／取出拖放練習

你會按指令進行 insert（加入）及 extract-min（取出最小值）。 插入時請把指定新數據拖到「下一個空位」；取出時請把根（index 0）拖到回傳區。
系統會自動完成上濾/下濾（sift up/down），你重點觀察：最小堆的最小值永遠在根。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Heap）

重點

• 節點 + 邊：可有向/無向，可加權/無權。
• 表示法：鄰接表（稀疏圖常用）或鄰接矩陣（查邊快但耗空間）。
• 遍歷：BFS 用 queue，DFS 用 stack/遞迴；必須記 visited 避免循環。

按我顯示更多內容

概念講解：BFS/DFS 的核心思路

Graph 可以比 tree 更自由：tree 無循環、有唯一父節點；graph 可以有循環、可以多條路。 所以做遍歷時，visited 幾乎是必備。

BFS / DFS 本質都是「從一個起點出發，不斷擴展下一批要處理的節點」； 分別只在於你用 queue（FIFO）或 stack（LIFO）去管理「下一批」。

表示法方面，鄰接表（adjacency list）用「每個節點的鄰居清單」去表示邊，對稀疏圖特別省空間。

圖像化：BFS / DFS 步進示範

例子示範：BFS（廣度優先搜尋）與 visited

BFS 的核心流程：用 queue 逐層擴展；每次取出一個節點後，把未到訪的鄰居加入 queue，並立刻標記 visited（避免重覆與循環）。

Q ← [start]
visited[start] ← True
設 step 由 1至 N
    若 Q 為空
        離開循環
    u ← 出隊(Q)
    輸出 u
    對於 u 的每個鄰居 v
        若 visited[v] 為 False
            visited[v] ← True
            入隊(Q, v)

Q ← [start]
visited[start] ← True
當 Q 不為空
    u ← 出隊(Q)
    輸出 u
    對於 u 的每個鄰居 v
        若 visited[v] 為 False
            visited[v] ← True
            入隊(Q, v)

Q ← [start]
visited[start] ← True
執行
    u ← 出隊(Q)
    輸出 u
    對於 u 的每個鄰居 v
        若 visited[v] 為 False
            visited[v] ← True
            入隊(Q, v)
當 Q 不為空

Q ← [start]
visited[start] ← True
重覆
    u ← 出隊(Q)
    輸出 u
    對於 u 的每個鄰居 v
        若 visited[v] 為 False
            visited[v] ← True
            入隊(Q, v)
直至 Q 為空

adj = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
start = 1
N = len(adj)

q = [start]
head = 0
visited = set([start])
order = []

for _ in range(N):
    if head == len(q):
        break
    u = q[head]
    head += 1
    order.append(u)

    for v in adj[u]:
        if v not in visited:
            visited.add(v)
            q.append(v)

print(order)

adj = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
start = 1

q = [start]
head = 0
visited = set([start])
order = []

while head < len(q):
    u = q[head]
    head += 1
    order.append(u)

    for v in adj[u]:
        if v not in visited:
            visited.add(v)
            q.append(v)

print(order)

小遊戲：Graph 走訪次序挑戰（BFS / DFS）

選擇 BFS 或 DFS，然後依次點擊節點。系統會根據「從起點出發」的走訪規則計算正確次序。 做錯會提示下一個正確節點。

請先閱讀上面的例子示範，再完成以下練習。練習按難度由淺入深，並對應本課題的重點。

Python 小練習（填充題）

Check Point：小測（Graph）

十一、小結與下一步

• 掌握 DSE 核心：陣列 Array／堆疊 Stack／隊列 Queue／循環隊列 Circular Queue／線性鏈表 Linked List（重點是「操作成本」與「適用情景」）。
• 增潤部分先建立直覺：Traversal（DFS/BFS）、Hash（collision）、Heap（priority queue）、Graph（visited）。
• 做練習時，先寫到「可運行」，再追求「寫得漂亮／快」。