C語言雙向鏈表實作：建立、查找與列印完整程式碼解析

雙向循環鏈表結構定義

typedef struct node {
    char name[20];
    struct node *llink;  // 指向前驅節點
    struct node *rlink;  // 指向後繼節點
} stud;

特徵：

• 雙向：每節點擁有前驅（llink）與後繼（rlink）指標
• 循環：頭節點 llink 指向尾節點，尾節點 rlink 指向頭節點
• 帶頭節點：頭節點不存資料，簡化邊界條件處理

核心操作函數

1. 建立鏈表 creat()

stud *creat(int n) {
    stud *p, *h, *s;
    int i;

    // 配置頭節點
    if ((h = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("記憶體配置失敗!");
        exit(0);
    }
    h->name[0] = '\0';
    h->llink = NULL;
    h->rlink = NULL;
    p = h;

    // 迴圈建立 n 個資料節點
    for (i = 0; i < n; i++) {
        if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
            printf("記憶體配置失敗!");
            exit(0);
        }
        p->rlink = s;           // 前一節點後繼指向新節點
        printf("請輸入第%d個人的姓名: ", i+1);
        scanf("%s", s->name);
        s->llink = p;           // 新節點前驅指向前一節點
        s->rlink = NULL;        // 暫時設 NULL
        p = s;                  // 移動 p 到新節點
    }

    // 完成循環連結
    h->llink = p;   // 頭節點前驅指向尾節點
    p->rlink = h;   // 尾節點後繼指向頭節點

    return h;       // 返回頭節點指標
}

2. 查找節點 search()

stud *search(stud *h, char *x) {
    stud *p;
    char *y;
    p = h->rlink;        // 從第一個資料節點開始
    while (p != h) {     // 未回到頭節點
        y = p->name;
        if (strcmp(y, x) == 0)  // 找到目標
            return p;           // 返回節點指標
        else
            p = p->rlink;       // 移向後繼
    }
    printf("沒有查找到該資料!\n");
    return NULL;  // 未找到
}

3. 列印鏈表 print()

void print(stud *h) {
    stud *p;
    p = h->rlink;
    printf("資料資訊為:\n");
    while (p != h) {
        printf("%s ", p->name);  // 或 &*p->name
        p = p->rlink;
    }
    printf("\n");
}

主程式整合

#include 
#include 
#include 

#define N 10

typedef struct node {
    char name[20];
    struct node *llink, *rlink;
} stud;

stud *creat(int n);
stud *search(stud *h, char *x);
void print(stud *h);

main() {
    int number = N;
    char studname[20];
    stud *head, *searchpoint;

    // clrscr();  // 清螢幕（特定編譯器）
    head = creat(number);
    print(head);

    printf("請輸入你要查找的人的姓名: ");
    scanf("%s", studname);
    searchpoint = search(head, studname);
    if (searchpoint)
        printf("你所要查找的人的姓名是: %s\n", searchpoint->name);
}

記憶體圖解：建立過程

// 初始：頭節點
h → [name=""][llink=NULL][rlink=NULL]
p = h

// 第 1 節點插入
s → [name="Alice"][llink=h][rlink=NULL]
h->rlink = s; s->llink = h; p = s

// 第 2 節點插入
s → [name="Bob"][llink=Alice][rlink=NULL]
Alice->rlink = s; s->llink = Alice; p = s

// ... 完成 n 節點後
h->llink = 尾節點
尾節點->rlink = h

// 最終結構：
h ↔ 節點1 ↔ 節點2 ↔ ... ↔ 節點n
↑______________________________↓  (循環)

查找演算法流程

1. 從 h->rlink（首資料節點）開始
2. 迴圈條件：p != h（未繞回頭節點）
3. 比較 p->name 與目標 x
4. 相符 → 返回 p；不符 → p = p->rlink 移向下一節點
5. 迴圈結束未找到 → 列印提示、返回 NULL

雙向鏈表優勢

常見錯誤與注意事項

1. malloc 失敗檢查：必須判斷回傳值是否為 NULL
2. 循環連結收尾：最後必須連接頭尾節點形成環
3. 查找終止條件：p != h 而非 p != NULL
4. 字串比較：用 strcmp 而非 ==
5. 釋放記憶體：程式結束前應遍歷釋放所有節點（教學範例常省略）
6. 輸入緩衝區：scanf("%s") 遇空白停止，姓名含空格需用 gets/fgets

擴展操作：插入與刪除（雙向循環）

// 在 p 之後插入新節點 s
s->rlink = p->rlink;
s->llink = p;
p->rlink->llink = s;
p->rlink = s;

// 刪除節點 p
p->llink->rlink = p->rlink;
p->rlink->llink = p->llink;
free(p);

雙向特性使插入刪除無需尋找前驅，極大簡化邏輯。

1. 上一篇文章： C語言結構體類型完整指南：定義三種形式、成員存取、初始化與巢狀結構
2. 下一篇文章： C語言單向鏈表插入操作：後插演算法與完整程式碼實作

關於C語言

C語言實戰：軟體工程師存定期能否買得起房？完整試算與代碼解析

問題背景：從「零理財」到「銀行定期」的差距 承接前一題「問題

Visual Studio 安裝專案實作（1）：完整解決方案概覽與前置準備

問題情境 部署 WinForms 應用程式時，需讓使用者在安

C語言實作：計算兩陣列支配值數目（num[] 中大於 cou[] 的配對數）

陣列配對比較：支配值計數 給定兩個等長陣列 num[] 與

APUE 讀書筆記：標準 I/O 庫 (下) —— 二進制 I/O、流定位、格式化 I/O、實現細節與臨時檔案

前言：《UNIX 環境高級程式設計》(APUE) 第 5 章