C語言鏈表實現冒泡排序：從鍵盤輸入到有序輸出的完整教學碼

前言

冒泡排序雖非高效演算法（O(n²)），但邏輯直觀，極適合鏈表指標操作練習。本文提供完整可編譯代碼：單鏈表建立、鍵盤輸入終止、冒泡排序（指標交換資料域）、遍歷輸出、記憶體釋放，適合資料結構入門實驗。

一、資料結構定義

#include 
#include 
#include 

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

二、核心功能函數

1. 交互式建立鏈表 getNum()

void getNum(MyNode *head) {
    char s[20];
    printf("請輸入數字，空格分隔，輸入 q/Q 結束：\n");
    scanf("%s", s);
    MyNode *tail = head; // 尾插法
    while (strcmp(s, "q") != 0 && strcmp(s, "Q") != 0) {
        MyNode *node = (MyNode*)malloc(sizeof(MyNode));
        if (!node) return; // 分配失敗保護
        node->value = strtol(s, NULL, 0); // 支援十進位/十六進位/八進位
        node->next = NULL;
        tail->next = node;
        tail = node;
        scanf("%s", s);
    }
}

2. 冒泡排序 sortList()（交換資料域）

void sortList(MyNode *head) {
    if (!head) return;
    MyNode *start = head->next; // 第一個有效節點
    while (start && start->next) {
        MyNode *curr = start->next;
        while (curr) {
            if (start->value > curr->value) {
                long tmp = start->value;
                start->value = curr->value;
                curr->value = tmp;
            }
            curr = curr->next;
        }
        start = start->next;
    }
}

註：鏈表冒泡排序通常交換 資料域 而非指標，避免複雜的前驅指標調整。對於大型結構體，改交換指標更高效。

3. 遍歷輸出 printStr() 釋放 freeStr()

void printStr(MyNode *head) {
    MyNode *p = head->next;
    while (p) {
        printf("%ld ", p->value);
        p = p->next;
    }
    printf("\n");
}

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

三、主函數串聯

int main() {
    MyNode *head = (MyNode*)malloc(sizeof(MyNode)); // 虛擬頭節點
    if (!head) return 1;
    head->next = NULL;

    getNum(head);
    sortList(head);
    printStr(head);
    freeStr(head); // 含虛擬頭節點
    return 0;
}

四、編譯運行示例

$ gcc list_bubble.c -o list_bubble
$ ./list_bubble
請輸入數字，空格分隔，輸入 q/Q 結束：
5 3 8 1 9 q
1 3 5 8 9

五、進階優化方向

• 交換節點指標：維護 prev 指標，實現真正的節點重鏈接，適合大型資料域。
• 歸併排序：鏈表天然適合歸併排序（O(n log n)），只需 split + merge，無需隨機訪問。
• 雙向鏈表：加 prev 指標，支援逆向遍歷、O(1) 刪除已知節點。

六、總結

這份代碼展示了C語言鏈表的完整生命週期管理：malloc 建立、尾插法輸入、冒泡排序（資料域交換）、遍歷輸出、free 釋放。掌握這套流程，是進階掌握紅黑樹、B樹、跳表等高階資料結構的紮實基礎。