C 語言鏈結串列建立與選擇排序完整實作

程式碼總覽

本程式示範單向鏈結串列的動態建立、列印與選擇排序（Selection Sort）。包含節點定義、建立函式、排序函式與主程式測試。

資料結構定義

typedef struct STRUCT {
    int value;
    struct STRUCT *next;
} TS;

建立鏈結串列 CreateLink

TS *CreateLink(int *a, int n) {
    TS *h = NULL, *p;
    for (int i = n; i > 0; i--) {  // 逆序插入，保持陣列順序
        p = (TS *)malloc(sizeof(TS));
        p->value = a[i-1];
        p->next = h;
        h = p;
    }
    return h;
}

• 頭插法建立，時間複雜度 O(n)。
• 傳入整數陣列與長度，回傳串列頭指標。

選擇排序 sort（指標操作版）

void sort(TS **h) {
    TS *h1, *p, *q, *r, *s;
    h1 = p = (TS *)malloc(sizeof(TS));  // 虛擬頭節點
    p->next = *h;

    while (p->next) {          // 外層：已排序部分尾節點 p
        q = p->next;           // 當前待排序區首節點
        r = p;                 // 記錄最小值前驅節點
        while (q->next) {      // 內層：尋找最小值節點
            if (q->next->value < r->next->value)
                r = q;
            q = q->next;
        }
        if (r != p) {          // 找到更小值，移動節點至 p 之後
            s = r->next;
            r->next = s->next;
            s->next = p->next;
            p->next = s;
        }
        p = p->next;           // 推進已排序邊界
    }
    *h = h1->next;             // 更新頭指標
    free(h1);                  // 釋放虛擬頭節點
}

演算法特點

• 原地排序，空間複雜度 O(1)（除虛擬頭節點）。
• 透過調整指標重組節點順序，不交換資料內容。
• 時間複雜度 O(n²)，適合小規模資料或教學示範。
• 虛擬頭節點簡化頭節點變更的邊界條件處理。

主程式測試流程

int main() {
    #define N 9
    int a[N], i;
    TS *head, *p;
    randomize();
    for (i = 0; i < N; i++) a[i] = random(9);  // 產生 0~8 隨機數

    head = CreateLink(a, N);
    for (p = head; p; p = p->next) printf("%-2d", p->value);
    putchar('\n');

    sort(&head);
    for (p = head; p; p = p->next) printf("%-2d", p->value);
    getchar();
    return 0;
}

關鍵指標操作解析

常見錯誤與修正

1. 未檢查 malloc 回傳值：生產碼必須判空。
2. 排序函式參數未用雙重指標：需修改頭指標本身，故傳 TS**。
3. 內層迴圈條件 q->next 而非 q：因比較的是 q->next->value，需確保 q->next 存在。
4. 隨機數重複：選擇排序不穩定，相同值相對順序可能改變。

延伸練習

• 改實作合併排序（O(n log n)）適應大量資料。
• 嘗試雙向鏈結串列版本。
• 加入節點刪除、插入、查找功能構建完整容器。

鏈結串列是指標操作的經典練習場，熟練掌握「虛擬頭節點 + 多指標協作」模式，能輕鬆應對各類鏈表重組問題。

1. 上一篇文章： C 語言位元組對齊詳解：原理、演算法與實戰技巧
2. 下一篇文章： C 語言位元運算精要：補數表示、經典技巧與實用函數庫

關於C語言

《C和指針》讀書筆記第2章：基本概念——內存、地址與指針本質

章節核心觀點 第 2 章奠定了理解指針的基礎：計算機內存模型

C 語言實現字串轉十進制：支援十進制與十六進制輸入

功能說明 提供兩個函數：Read_DecNumber 將字串

C# 設計模式：適配器模式 (3) - Object Adapter 結構圖、角色分析與結構性程式碼

Object Adapter UML 結構 Client

C語言指針進階：數組指針與指針數組的本質區別

一張圖搞懂「數組指針」vs「指針數組」 C 語言中 int