112 年 國立中正大學電機工程學系碩士班計算機工程組《資料結構》

核心觀念

題目未給定特定的 BST 圖形，以下以 root 指向樹根，空樹以 NULL 表示。

1. BST 對每個節點 $u$ 滿足：

   • 左子樹所有鍵值小於 u->key
   • 右子樹所有鍵值大於 u->key

   本題的廣度優先走訪不使用鍵值比較，只使用節點的左右子樹指標，因此相同方法也適用於一般二元樹。

2. Queue（佇列）遵守 FIFO（First In, First Out）：

   • 從尾端 rear 插入資料：EnQ
   • 從前端 front 取出資料：DeQ

3. Breadth First Traversal（BFS，廣度優先走訪）按照「由上到下、同層由左到右」的順序走訪節點。使用佇列可以保留節點被發現的先後順序。

---

i. 佇列設計、ADT 與走訪策略

本解答採用「單向鏈結串列」實作佇列。每個佇列節點存放一個 BSTNode *，而不是只存放鍵值，這樣取出樹節點後即可直接存取其左右子樹。

佇列設計如下：

Queue
┌─────────────────────────────┐
│ front ───────┐              │
│ rear ────────┼──────┐       │
│ size         │      │       │
└──────────────┼──────┼───────┘
               ▼      ▼
          front/rear
               │
               ▼
        ┌──────────────┬──────┐
        │ BSTNode *item│ next ├──►
        └──────────────┴──────┘
                              ┌──────────────┬──────┐
                              │ BSTNode *item│ next ├──► NULL
                              └──────────────┴──────┘
                                                     ▲
                                                     │
                                                    rear

當佇列為空時：

front = NULL
rear  = NULL
size  = 0

當佇列只有一個節點時，front 與 rear 同時指向該節點。

ADT 的重點是將「操作介面」與「內部實作」分離。呼叫端只使用：

• NewQ：建立佇列
• EnQ：加入資料
• DeQ：取出資料
• IsEmpty：判斷是否為空

呼叫端不必直接處理鏈結串列的 next 指標。即使日後將鏈結串列改成循環陣列，只要操作介面與行為不變，BFS 程式也不需要修改。

佇列的表示不變量為：

• size == 0 時，front == NULL 且 rear == NULL
• 佇列非空時，front 與 rear 都不為 NULL
• rear->next == NULL
• size 等於鏈結串列中的節點數

BFS 的走訪策略如下：

1. 將 root 放入佇列。
2. 只要佇列不為空，就取出前端節點。
3. 先走訪取出的節點。
4. 依序將其左子節點、右子節點加入佇列。
5. 重複步驟 2 至 4。

例如：

初始：
Queue = [root]

取出 root，加入 left、right：
Queue = [left, right]

取出 left，加入 left 的兩個子節點：
Queue = [right, left.left, left.right]

因此可確保同一層的節點先於下一層節點被處理，且左子節點先於右子節點被處理。

---

ii. 資料結構定義

#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

/* BST 節點 */
typedef struct BSTNode {
    int key;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

/* 佇列節點：存放一個 BST 節點指標 */
typedef struct QueueNode {
    BSTNode *item;
    struct QueueNode *next;
} QueueNode;

/* Queue ADT 的實作結構 */
typedef struct Queue {
    QueueNode *front;   /* 取出端 */
    QueueNode *rear;    /* 插入端 */
    size_t size;        /* 目前元素數量 */
} Queue;

此處佇列元素的型別是 BSTNode *。BFS 取出節點後，需要使用：

current->left
current->right

因此儲存節點指標比只儲存 key 更適合本題。

---

iii. Queue 操作

1. NewQ：建立並初始化佇列

Queue *NewQ(void)
{
    Queue *q = malloc(sizeof *q);

    if (q == NULL) {
        return NULL;
    }

    q->front = NULL;
    q->rear = NULL;
    q->size = 0;

    return q;
}

建立完成後，佇列為空，且：

$$q\text{->front}=NULL,\qquad q\text{->rear}=NULL,\qquad q\text{->size}=0$$

---

2. EnQ：加入元素

核心觀念

Selection Sort 的作法是：

1. 將陣列分成「已排序區」與「未排序區」。
2. 每一回合從未排序區找出最小值。
3. 將該最小值與未排序區的第一個元素交換。
4. 重複此步驟，直到陣列遞增排序完成。

第 $i$ 回合結束後，前 $i+1$ 個元素已是目前最小的 $i+1$ 個元素，且排列為遞增順序。

i. Selection Sort 程式碼

以下函式直接修改原陣列，使用索引從 $0$ 到 $n-1$：

void selectionSort(int a[], int n)
{
    int i, j;
    int minIndex;
    int temp;

    for (i = 0; i < n - 1; i++) {
        // 假設目前未排序區的第一個元素是最小值
        minIndex = i;

        // 在未排序區間 a[i+1] ~ a[n-1] 中尋找真正的最小值
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }

        // 將最小值移到未排序區的開頭
        if (minIndex != i) {
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

參數與區域變數意義如下：

• a[]：待排序的整數陣列。
• n：陣列元素個數。
• i：外層迴圈索引，代表目前未排序區的起點。
• j：內層迴圈索引，用來搜尋最小值。
• minIndex：目前找到的最小元素索引。
• temp：交換兩個陣列元素時使用的暫存變數。

例如陣列為：

$$[64,25,12,22,11]$$

各回合結果為：

$$[11,25,12,22,64]$$ $$[11,12,25,22,64]$$

核心觀念

本題考查以**單向鏈結串列（singly linked list）**表示字串，以及下列三種操作：

1. 節點資料結構的設計。
2. 逐字元比較兩個字串。
3. 深拷貝（deep copy）字串，建立完全獨立的新節點。
4. 逐一釋放整條鏈結串列的動態記憶體。

以下採用約定：

• 空字串以 NULL 表示。
• 字串結尾以 next == NULL 表示。
• 字串比較結果與 strcmp 類似：
  • 回傳負值：第一個字串較小。
  • 回傳 0：兩字串相同。
  • 回傳正值：第一個字串較大。

---

i. 節點資料結構

每個節點必須包含：

• 一個儲存單一字元的欄位。
• 一個指向下一個節點的指標。

typedef struct Node {
    char data;
    struct Node *next;
} Node;

例如字串 "HELLO" 可表示為：

[H | next] -> [E | next] -> [L | next] -> [L | next] -> [O | NULL]

其中第一個節點的位址就是整個字串的 head。

---

ii. 字串比較函式

解題方法

從兩條鏈結串列的 head 同時開始走訪：

1. 只要兩個節點都存在，就比較目前字元。
2. 若字元不同，立即依字元大小回傳結果。
3. 若目前字元相同，兩個指標同時前進。
4. 若其中一條字串先結束：
   • 兩條同時結束，代表字串相同。
   • 第一條先結束，代表第一個字串較短。
   • 第二條先結束，代表第一個字串較長。

程式碼

int compareString(const Node *str1, const Node *str2)
{
    const Node *p;
    const Node *q;

    p = str1;
    q = str2;

    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            return -1;
        }

        if (p->data > q->data) {
            return 1;
        }

        p = p->next;
        q = q->next;
    }

    if (p == NULL && q == NULL) {
        return 0;
    }

    if (p == NULL) {
        return -1;
    }

    return 1;
}

範例

比較：

str1: H -> E -> L -> L -> O -> NULL
str2: H -> E -> L -> P -> NULL

前三個字元相同，第四個字元比較：

'L' < 'P'

因此 compareString(str1, str2) 回傳負值。

複雜度

設兩字串長度分別為 $m$、$n$：

• 時間複雜度：$O(\min(m,n))$
• 額外空間複雜度：$O(1)$

解題技巧與陷阱

• 不能只比較 head，必須依序比較所有節點。
• 兩字串前段相同時，較短者字典序較小。
• 比較結束後，必須處理一條串列先結束的情況。
• 不可使用 p->next、q->next 前未確認 p、q 不為 NULL。

---

iii. 字串複製函式

解題方法

本題要求建立新字串，因此不能只執行：

newString = oldString;

這只會複製 head 指標，兩者仍指向同一批節點，稱為淺拷貝（shallow copy）。

正確作法是：

1. 逐一走訪來源字串。
2. 每讀取一個字元，就配置一個新的節點。
3. 將新節點接到新串列尾端。
4. 回傳新串列的 head。

程式碼

Node *copyString(const Node *source)
{
    const Node *current;
    Node *newHead;
    Node *tail;
    Node *newNode;

    current = source;
    newHead = NULL;
    tail = NULL;

    while (current != NULL) {
        newNode = (Node *)malloc(sizeof(Node));

        if (newNode == NULL) {
            freeString(newHead);
            return NULL;
        }

        newNode->data = current->data;
        newNode->next = NULL;

        if (newHead == NULL) {
            newHead = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }

        current = current->next;
    }

    return newHead;
}