您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言實現帶頭結點單鏈表的頭插法與尾插法建表

編輯：關於C

單鏈表的構建本質是節點的連續插入過程。根據插入位置不同，分為頭插法（新節點始終插在頭結點之後，逆序輸入）與尾插法（新節點插在鏈表尾部，順序輸入）。本文基於帶頭結點單鏈表，詳細實現這兩種經典建表算法。

節點定義與頭結點初始化

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

void InitialList(Node** ppHead) {
    *ppHead = (Node*)malloc(sizeof(Node));
    if (*ppHead) (*ppHead)->next = NULL;
}

尾插法建表——保持輸入順序

維護尾指針 pMove，每次在鏈表末尾追加節點，輸入序列與鏈表順序一致。

void CreateListTailInsert(Node* pHead) {
    Node *pMove = pHead, *pInsert;
    int val;
    
    while (scanf("%d", &val) == 1 && val > 0) {
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) break;
        pInsert->element = val;
        pInsert->next = NULL;
        pMove->next = pInsert;
        pMove = pInsert; // 尾指針後移
    }
    printf("%s: 尾插法建表完成\n", __FUNCTION__);
}

頭插法建表——逆序輸入順序

新節點始終插入頭結點之後，最先輸入的元素最終位於鏈表末尾。

void CreateListHeadInsert(Node* pHead) {
    Node* pInsert;
    int val;
    
    while (scanf("%d", &val) == 1 && val > 0) {
        pInsert = (Node*)malloc(sizeof(Node));
        if (!pInsert) break;
        pInsert->element = val;
        pInsert->next = pHead->next; // 關鍵：新節點指向原首節點
        pHead->next = pInsert;       // 頭結點指向新節點
    }
    printf("%s: 頭插法建表完成\n", __FUNCTION__);
}

兩種方法對比

特性	尾插法	頭插法
輸入/輸出順序	一致	相反
是否需尾指針	是	否
時間複雜度	O(n) 總體	O(n) 總體
適用場景	需保持原序列	需逆序、或不關心順序

測試驗證

int main() {
    Node *head1 = NULL, *head2 = NULL;
    InitialList(&head1);
    InitialList(&head2);
    
    printf("輸入數據（以負數結束）：");
    // 假設輸入：1 2 3 -1
    CreateListTailInsert(head1); // 鏈表：1 → 2 → 3
    PrintList(head1);
    
    printf("再次輸入相同數據：");
    CreateListHeadInsert(head2); // 鏈表：3 → 2 → 1
    PrintList(head2);
    
    return 0;
}

掌握頭尾插法不僅是單鏈表建表的基礎，更是理解指針操作、內存管理與算法邏輯的關鍵訓練。帶頭結點版本邏輯更統一，工程上更推薦。