C語言從零構建雙向非循環鏈表（無頭結點）：節點定義與尾插建表全過程

雙向鏈表（Doubly Linked List）每個節點包含 prior（前驅）與 next（後繼）兩個指針，使得從任意節點可 O(1) 訪問前後鄰居。本文從零開始，實現無頭結點的雙向非循環鏈表節點定義與尾插法建表，為後續增刪改查操作奠基。

節點類型定義

typedef struct Node {
    int element;          // 數據域
    struct Node* prior;   // 前驅指針
    struct Node* next;    // 後繼指針
} Node;

尾插法建表核心邏輯

維護 pHead（頭指針）與 pMove（尾游標），每次在尾部追加新節點，並雙向鏈接。

Node* CreateList(Node* pHead) {
    Node *pInsert, *pMove = pHead;
    int val;
    
    // 讀取首個值
    pInsert = (Node*)malloc(sizeof(Node));
    if (!pInsert) return NULL;
    memset(pInsert, 0, sizeof(Node));
    scanf("%d", &pInsert->element);
    
    // 首值非正數 => 空鏈表
    if (pInsert->element <= 0) {
        free(pInsert);
        printf("%s: 首值非正，建表終止\n", __FUNCTION__);
        return NULL;
    }
    
    // 循環讀取並尾插
    while (pInsert->element > 0) {
        if (!pHead) {           // 首節點
            pHead = pInsert;
            pMove = pHead;
        } else {                // 非首節點：雙向鏈接
            pMove->next = pInsert;
            pInsert->prior = pMove;
            pMove = pMove->next; // 尾游標後移
        }
        
        // 預分配下一節點
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) break;
        memset(pInsert, 0, sizeof(Node));
        scanf("%d", &pInsert->element);
    }
    
    // 循環結束時 pInsert 為最後分配但未使用的節點
    free(pInsert);
    printf("%s: 雙向非循環鏈表建表成功\n", __FUNCTION__);
    return pHead;
}

關鍵點圖解

輸入序列: 10 20 30 -1

步驟1: 分配節點A(10)  pHead=A  pMove=A
步驟2: 分配節點B(20)  A.next=B  B.prior=A  pMove=B
步驟3: 分配節點C(30)  B.next=C  C.prior=B  pMove=C
步驟4: 讀取-1  釋放最後預分配節點  結束

最終結構:
NULL <-prior- A(10) -next-> B(20) -next-> C(30) -next-> NULL
      <-prior-       <-prior-       <-prior-

常見錯誤與避坑指南

1. 忘記初始化 prior：memset(pInsert, 0, sizeof(Node)) 確保兩指針均為 NULL。
2. 尾游標未後移：插入後必須 pMove = pMove->next，否則下輪覆蓋鏈接。
3. 最後預分配節點洩漏：循環退出時 pInsert 已分配但未掛鏈，必須 free(pInsert)。
4. 輸入緩衝殘留：scanf 失敗時需清理緩衝區，生產代碼建議用 fgets+sscanf。

完整可運行程序

#include 
#include 
#include 

typedef struct Node {
    int element;
    struct Node* prior;
    struct Node* next;
} Node;

Node* CreateList(Node* pHead);
void PrintList(Node* pHead);
void FreeList(Node* pHead);

int main() {
    Node* list = NULL;
    printf("請輸入正整數建表（負數/0結束）：");
    list = CreateList(list);
    PrintList(list);
    FreeList(list);
    return 0;
}

void PrintList(Node* pHead) {
    for (Node* p = pHead; p; p = p->next) printf("%d ", p->element);
    printf("\n");
}

void FreeList(Node* pHead) {
    while (pHead) {
        Node* next = pHead->next;
        free(pHead);
        pHead = next;
    }
}

雙向非循環鏈表的構建是理解雙向指針維護、邊界條件處理、內存管理的綜合訓練場。建議讀者在紙上畫出每步指針變化，反覆練習至盲寫無誤。後續文章將基於此結構實現插入、刪除、逆序等核心操作。