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

C語言單鏈表核心操作全集：建立、遍歷、查找、刪除、逆置、排序、去重、有序插入

編輯：關於C

前言

單鏈表是資料結構教學與工程實踐的基石。本文整理一套完整、可編譯運行的單鏈表操作庫，涵蓋 8 大核心功能，採用帶頭節點設計，代碼風格統一，適合教學參考與項目直接複用。

一、資料結構定義


#include 
#include 

typedef int ElemType;
typedef struct Node {
    ElemType data;
    struct Node *next;
} LNode, *LinkList; // LinkList 即指向節點的指標

二、核心操作函數

1. 尾插法建表 `Build()`


void Build(LinkList L) {
    int n; LinkList p = L, q;
    printf("請輸入節點數 n 及 n 個元素值：\n");
    scanf("%d", &n);
    while (n--) {
        q = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &q->data);
        q->next = NULL;
        p->next = q;
        p = q;
    }
}

2. 遍歷輸出與計長 `LinkLength()`


void LinkLength(LinkList L) {
    int len = 0; LinkList p = L->next;
    while (p) { printf("%3d", p->data); p = p->next; len++; }
    printf("\n長度：%d\n", len);
}

3. 查找前驅節點 `Find()`


void Find(LinkList L, int x) {
    LinkList p = L;
    while (p->next && p->next->data != x) p = p->next;
    if (p->next) printf("%d 的前驅節點值為 %d\n", x, p->data);
    else printf("未找到值為 %d 的節點\n", x);
}

4. 刪除指定值節點 `Delete()`（刪除首個匹配）


void Delete(LinkList L, int x) {
    LinkList p = L, q;
    while (p->next && p->next->data != x) p = p->next;
    if (p->next) {
        q = p->next;
        p->next = q->next;
        free(q);
        printf("刪除成功！\n");
    } else printf("未找到，刪除失敗。\n");
}

5. 就地逆置 `Reverse()`（頭插法重建）


void Reverse(LinkList L) {
    LinkList p = L->next, q;
    L->next = NULL; // 斷開原鏈表
    while (p) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
    printf("逆置成功！\n");
}

6. 選擇排序 `sort()`（交換資料域）


void sort(LinkList L) {
    LinkList p, q; int tmp;
    for (p = L; p->next; p = p->next)
        for (q = p->next; q; q = q->next)
            if (p->data > q->data) {
                tmp = p->data; p->data = q->data; q->data = tmp;
            }
    printf("排序成功！\n");
}

7. 刪除重複元素 `Deletesameelem()`（假設已排序）


void Deletesameelem(LinkList L) {
    LinkList p = L, q = L->next, s;
    while (q && q->next) {
        if (q->data == q->next->data) {
            p->next = q->next;
            s = q; q = q->next; free(s);
        } else { p = p->next; q = q->next; }
    }
    printf("去重成功！\n");
}

8. 有序插入 `Insert()`（保持升序）


void Insert(LinkList L, LinkList node) {
    LinkList s = L;
    while (s->next && s->next->data < node->data) s = s->next;
    node->next = s->next;
    s->next = node;
}

三、交互式主程式


void Tips() {
    printf("\n=== 單鏈表操作選單 ===\n");
    printf("1. 輸出鏈表及長度\n");
    printf("2. 查找前驅節點\n");
    printf("3. 刪除指定值節點\n");
    printf("4. 逆置鏈表\n");
    printf("5. 升序排序\n");
    printf("6. 刪除重複元素\n");
    printf("7. 有序插入新元素\n");
    printf("0. 退出\n");
}

int main() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL; L->data = -1; // 頭節點標記
    Build(L);
    Tips();
    int op, x;
    while (scanf("%d", &op), op) {
        switch (op) {
            case 1: LinkLength(L); break;
            case 2: printf("輸入查找值："); scanf("%d",&x); Find(L,x); break;
            case 3: printf("輸入刪除值："); scanf("%d",&x); Delete(L,x); break;
            case 4: Reverse(L); break;
            case 5: sort(L); break;
            case 6: Deletesameelem(L); break;
            case 7: printf("輸入插入值："); scanf("%d",&x);
                    LinkList n = (LinkList)malloc(sizeof(LNode));
                    n->data = x; Insert(L,n); printf("插入成功！\n"); break;
        }
    }
    // 此處應釋放整個鏈表，略
    return 0;
}

四、複雜度與適用場景總結

操作	時間複雜度	空間複雜度	備註
建表/遍歷/計長	O(n)	O(1)	基礎操作
查找/刪除(單次)	O(n)	O(1)	無序鏈表必須遍歷
逆置	O(n)	O(1)	就地指標翻轉
選擇排序	O(n²)	O(1)	教學用，大數據用歸併排序 O(n log n)
去重(已排序)	O(n)	O(1)	單次遍歷
有序插入	O(n)	O(1)	維護有序性