C語言鏈表實作：氣泡排序法完整教學

前言：為什麼要在鏈表上做排序？

陣列排序固然方便，但插入/刪除需搬移元素；鏈表透過指標調整即可完成節點重排，適合頻繁動態增刪的場景。本文示範如何對單向鏈表實作氣泡排序，並完整呈現從輸入、建立、排序、列印到釋放記憶體的流程。

資料結構定義

typedef struct MyNode {
    long value;
    struct MyNode *next;
} MyNode;

每個節點包含一個 long 整數與指向下一節點的指標。

主程式流程

int main(void) {
    MyNode *head = (MyNode *)malloc(sizeof(MyNode));
    if (!head) return 0;               // 配置失敗保護
    head->next = NULL;                 // 初始化空鏈表

    getNum(head);      // 1. 讀取輸入建立鏈表
    sortList(head);    // 2. 氣泡排序
    printStr(head);    // 3. 列印結果
    freeStr(head);     // 4. 釋放記憶體
    return 0;
}

核心函式實作詳解

1. 讀取輸入建立鏈表 getNum()

void getNum(MyNode *head) {
    char buf[20];
    printf("請輸入整數，以空白分隔，輸入 q 或 Q 結束：\n");
    scanf("%19s", buf);

    MyNode *tail = head;               // 尾指標，O(1) 接節點
    while (strcmp(buf, "q") != 0 && strcmp(buf, "Q") != 0) {
        MyNode *node = (MyNode *)malloc(sizeof(MyNode));
        if (!node) return;             // 配置失敗直接返回
        node->value = strtol(buf, NULL, 10);
        node->next = NULL;

        tail->next = node;             // 尾插法
        tail = node;

        scanf("%19s", buf);
    }
}

關鍵點：使用尾指標 tail 避免每次插入都從頭遍歷，時間複雜度從 O(n²) 降為 O(n)。

2. 氣泡排序 sortList()

void sortList(MyNode *head) {
    if (!head || !head->next) return;  // 空或單節點無需排序

    bool swapped;
    MyNode *last = NULL;               // 已排序區域邊界

    do {
        swapped = false;
        MyNode *prev = head;
        MyNode *curr = head->next;

        while (curr->next != last) {
            if (curr->value > curr->next->value) {
                // 交換節點（調整指標，非交換資料）
                MyNode *next = curr->next;
                prev->next = next;
                curr->next = next->next;
                next->next = curr;
                prev = next;
                swapped = true;
            } else {
                prev = curr;
                curr = curr->next;
            }
        }
        last = curr;                   // 縮小未排序範圍
    } while (swapped);
}

改良說明：

• 原始碼採用交換節點資料，若節點結構龐大效率低；此處改為調整指標交換節點位置，更符合鏈表特性。
• 引入 last 標記已排好序的尾部，每輪少比較一個節點。
• 若一輪無交換提早結束，最佳情況 O(n)。

3. 列印鏈表 printStr()

void printStr(const MyNode *head) {
    const MyNode *p = head->next;      // 跳過哨兵節點
    while (p) {
        printf("%ld ", p->value);
        p = p->next;
    }
    putchar('\n');
}

4. 釋放記憶體 freeStr()

void freeStr(MyNode *head) {
    MyNode *curr = head;
    while (curr) {
        MyNode *next = curr->next;
        free(curr);
        curr = next;
    }
}

務必先保存 next 再 free，避免野指標。

完整可編譯程式碼

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

typedef struct MyNode { long value; struct MyNode *next; } MyNode;

void getNum(MyNode *head);      // 如前所示
void sortList(MyNode *head);    // 如前所示
void printStr(const MyNode *head);
void freeStr(MyNode *head);

int main(void) {
    MyNode *head = malloc(sizeof(MyNode));
    if (!head) return 1;
    head->next = NULL;

    getNum(head);
    sortList(head);
    printStr(head);
    freeStr(head);
    return 0;
}
/* 其餘函式定義同上 */

測試範例

輸入： 42 17 89 3 56 q
輸出： 3 17 42 56 89

常見錯誤與優化方向

延伸挑戰

• 改用合併排序（Merge Sort），將鏈表排序時間複雜度降至 O(n log n)。
• 實作雙向鏈表版本，支援反向遍歷。
• 加入泛型比較函式指標，支援任意型別排序。