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

C語言實現帶頭節點單鏈表：創建、增刪查、歸併排序完整代碼

編輯：關於C

單鏈表是數據結構教學與工程實踐的基石。本文提供一個模塊化、可編譯、含測試主程序的帶頭節點單鏈表 C 實現，涵蓋逆序建表、指定位置插入/刪除、按位查找、兩有序鏈表歸併，並詳細講解二級指針參數傳遞、內存管理、邊界處理等關鍵工程細節。

項目結構

declaration.h  // 類型定義、狀態碼
function.h     // 接口聲明
function.c     // 核心實現
main.c         // 測試驗證

核心類型定義

// declaration.h
#ifndef DECLARATION_H
#define DECLARATION_H

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int ElemType;
typedef int Status;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;  // LinkList 本質是指向頭節點的指針

#endif

接口聲明

// function.h
#ifndef FUNCTION_H
#define FUNCTION_H

void CreateList_L(LinkList *L, int n);          // 逆序輸入 n 個元素建表
Status ListInsert_L(LinkList *L, int i, ElemType e);  // 第 i 位前插入
Status ListDelete_L(LinkList *L, int i, ElemType *e); // 刪除第 i 位，值回傳 e
Status GetElem_L(LinkList L, int i, ElemType *e);     // 查找第 i 位
Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc); // 歸併有序表
void PrintList_L(LinkList L);                          // 打印鏈表

#endif

關鍵實現細節

1. 二級指針建表：在函數內修改主調用者的頭指針

void CreateList_L(LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(LNode));  // 分配頭節點
    (*L)->next = NULL;
    for (int i = n; i > 0; --i) {          // 逆序輸入 → 正序鏈表
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = (*L)->next;              // 頭插法
        (*L)->next = p;
    }
}

關鍵點：LinkList *L 是二級指針，*L 才是頭指針。調用時傳 &La，函數內 *L = malloc(...) 修改的是主函數的 La 變量本身。

2. 插入操作：前驅定位 + 雙鏈接

Status ListInsert_L(LinkList *L, int i, ElemType e) {
    LinkList p = *L; int j = 0;
    while (p && j < i-1) { p = p->next; ++j; }  // 尋找第 i-1 個節點
    if (!p || j > i-1) return ERROR;            // 位置非法
    LinkList s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;  // ① 先連後繼
    p->next = s;        // ② 再連前驅
    return OK;
}

3. 刪除操作：斷鏈 + 釋放 + 值回傳

Status ListDelete_L(LinkList *L, int i, ElemType *e) {
    LinkList p = *L; int j = 0;
    while (p->next && j < i-1) { p = p->next; ++j; }
    if (!p->next || j > i-1) return ERROR;
    LinkList q = p->next;
    p->next = q->next;  // 斷開 q
    *e = q->data;
    free(q);
    return OK;
}

4. 歸併兩有序鏈表：原地重鏈接，O(m+n) 時間，O(1) 額外空間

Status MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc) {
    LinkList pa = (*La)->next, pb = (*Lb)->next;
    *Lc = (LinkList)malloc(sizeof(LNode));  // Lc 頭節點
    LinkList pc = *Lc;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;  // 連接剩餘段
    // 可選：釋放 La, Lb 頭節點，置空原表
    return OK;
}

測試驗證

// main.c
int main() {
    LinkList La, Lb, Lc;
    printf("Input 5 numbers for La (reverse order stored): ");
    CreateList_L(&La, 5);
    printf("La: "); PrintList_L(La);

    ElemType e;
    GetElem_L(La, 3, &e);
    printf("3rd element: %d\n", e);

    ListDelete_L(&La, 1, &e);
    printf("Deleted 1st: %d, La now: ", e); PrintList_L(La);

    printf("Input 4 numbers for Lb: ");
    CreateList_L(&Lb, 4);
    printf("Lb: "); PrintList_L(Lb);

    ListInsert_L(&Lb, 2, 3);
    printf("After insert 3 at pos 2, Lb: "); PrintList_L(Lb);

    if (MergeList_L(&La, &Lb, &Lc) == OK) {
        printf("Merged Lc: "); PrintList_L(Lc);
    }
    return 0;
}

運行結果示例

Input 5 numbers for La: 5 4 3 2 1
La: 1 2 3 4 5
3rd element: 3
Deleted 1st: 1, La now: 2 3 4 5
Input 4 numbers for Lb: 10 20 30 40
Lb: 40 30 20 10
After insert 3 at pos 2, Lb: 40 3 30 20 10
Merged Lc: 2 3 4 5 10 20 30 40