C 語言資料結構入門：結構體、單向/雙向/循環鏈表完整實作教學

第 3 章：資料結構核心——結構體與鏈表

資料結構是計算機科學核心，亦是考研專業課重點。本章涵蓋結構體、鏈表、堆疊/佇列、串/廣義表、二叉樹、圖。本文聚焦結構體與鏈表基礎。

3.1 結構體：自訂複合型別

struct student {
    char name[20];
    int age;
    float score;
};

• 封裝異質資料，形成新型別。
• 記憶體佈局連續，方便整體複製/傳遞。
• 跨函式共享資料時，傳遞指標 struct student * 避免大量複製。

實例 076：電話簿查詢系統

• readin()：迴圈讀入姓名/電話，以 # 結束，回傳筆數。
• search()：線性掃描比對姓名，找到列印並返回。
• 主程式協調流程，展示函式分工與結構體指標傳遞。

3.2 鏈表：動態記憶體的靈活組織

鏈表以節點動態分配儲存空間，空間不連續、不浪費、大小無上限，是動態資料結構基石。面試必考、實務必會。

節點結構

struct LNode {
    int data;
    struct LNode *next;  // 指向下一節點
};

實例 078：建立單向鏈表（尾插法）

struct LNode *create(int n) {
    struct LNode *head = NULL, *p1, *p2;
    for (int i = n; i > 0; --i) {
        p1 = malloc(sizeof(struct LNode));
        scanf("%d", &p1->data);
        if (!head) head = p2 = p1;
        else { p2->next = p1; p2 = p1; }
    }
    p2->next = NULL;
    return head;
}

關鍵行解析：p1 = (struct LNode*)malloc(...) 分配節點並轉型；p2->next = p1; p2 = p1; 維護尾指標實現 O(1) 尾插。

實例 079：雙向鏈表（含前驅 prior）

• 節點增設 prior 指向前一節點。
• 插入：s->prior = q->prior; q->prior = s; q->prior->next = s; s->next = q;（順序不可亂）。
• 刪除：q->next->prior = q->prior; q->prior->next = q->next; free(q);（順序可互換）。

實例 080：循環鏈表

尾節點 next 指向頭節點。遍歷終止條件變為 p->next == head。適合循環輪詢場景（如約瑟夫環）。

實例 081：雙向鏈表逆置

三指標 p, r, h 協作，將 next/prior 互換，最後修正頭尾連結。核心邏輯：
p = h; r = p->next; p->next = NULL; 斷開首節點後向連結，逐步反轉。

學習鏈表的三大核心能力

1. 指標不混淆：區分結構體指標、next/prior 指標、指標的指標。
2. malloc 內化：p = malloc(sizeof(*p)) 肌肉記憶。
3. 圖形化推演：紙筆畫節點連結，驗證插入/刪除/逆置邏輯。

總結

結構體是資料封裝單元，鏈表是動態組織單元。掌握單向/雙向/循環鏈表的建立、遍歷、插入、刪除、逆置、合併等核心操作，並能手寫無 Bug 程式碼，是邁向系統級開發、演算法競賽、面試通關的必經之路。