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

動態分配順序線性表的 15 種核心操作——C 語言完整實現與解析

編輯：關於C語言

動態分配順序線性表的 15 種核心操作——C 語言完整實現與解析

線性表是最基礎、最常用的資料結構之一。它是由零個或多個資料元素組成的有限序列，具有明確的順序關係。本文將系統介紹動態分配順序線性表（動態順序表）的 15 種核心操作，並提供完整的 C 語言實現代碼與深度解析。

一、線性表與順序表基礎概念

線性表定義：由 n（n≥0）個資料元素組成的有限序列。非空線性表具有唯一的「首元素」與「尾元素」，除首尾元素外，每個元素僅有一個直接前驅和一個直接後繼。

順序表（順序存儲結構）：用一組地址連續的記憶體單元依次存儲線性表的資料元素，使邏輯鄰近的元素在物理位置上也相鄰。特點是支援隨機存取，但插入、刪除操作需移動大量元素。

靜態 vs 動態分配：靜態順序表使用固定大小陣列，容量不可變；動態順序表使用 malloc/realloc 在堆區分配記憶體，可根據需要動態擴容，更具實用性。

二、動態順序表的結構定義

// ADT.h
#define LIST_INIT_SIZE 100  // 線性表儲存空間的初始分配量
#define LISTINCREMENT 10    // 線性表儲存空間的分配增量

typedef struct {
    int *elem;      // 儲存空間基址
    int length;     // 當前長度（元素個數）
    int listsize;   // 當前分配的儲存容量
} SqList;

三、15 種核心操作詳細實現與分析

第一類：初始化與銷毀操作

1. 初始化操作 `InitList`

int InitList(SqList *L) {
    L->elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
    if (!L->elem) {
        printf("線性表記憶體分配失敗！\n");
        exit(1);
    }
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return 0;
}

關鍵點：必須傳遞指標參數以修改結構體成員；分配失敗需處理；length 表示當前元素個數，listsize 表示最大容量，兩者含義不同。

2. 銷毀操作 `DestroyList`

void DestroyList(SqList *L) {
    if (L->elem) {
        free(L->elem);
        L->elem = NULL;
        L->length = 0;
        L->listsize = 0;
        printf("線性表已銷毀！\n");
    }
}

注意：順序表記憶體連續，只需釋放基址即可釋放全部空間；鏈表則需逐節點釋放。

第二類：引用型操作（不修改資料）

3. 判空 `ListEmpty` / 4. 求長度 `ListLength`

void ListEmpty(SqList L) {
    if (!L.elem) { puts("表不存在！"); return; }
    puts(L.length == 0 ? "本表為空！" : "表不為空！");
}

int ListLength(SqList L) {
    if (!L.elem) { puts("表不存在！"); return 0; }
    return L.length;
}

5. 定位操作 `LocateElem`

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e) {
            printf("定位成功，位置 = %d\n", i + 1);
            return i + 1;  // 返回邏輯位序（從 1 開始）
        }
    }
    puts("定位失敗！");
    return 0;
}

時間複雜度：最好 O(1)，最壞 O(n)，平均 O(n)。

6. 求後繼 `NextElem` / 7. 求前驅 `PriorElem`

void NextElem(SqList L, int cur_e) {
    int i = LocateElem(L, cur_e);
    if (i == 0) { puts("元素不存在！"); return; }
    if (i == L.length) puts("此為尾元素，無後繼！");
    else printf("%d 的後繼是 %d\n", L.elem[i-1], L.elem[i]);
}

void PriorElem(SqList L, int cur_e) {
    int i = LocateElem(L, cur_e);
    if (i == 0) { puts("元素不存在！"); return; }
    if (i == 1) puts("此為首元素，無前驅！");
    else printf("%d 的前驅是 %d\n", L.elem[i-1], L.elem[i-2]);
}

索引轉換：邏輯位序 i 對應物理下標 i-1，需仔細區分。

8. 取值操作 `GetElem` / 9. 遍歷操作 `ListTraverse`

// 改進版：使用指標回傳值
int GetElem(SqList L, int i, int *e) {
    if (i < 1 || i > L.length) { puts("位置超出範圍！"); return 0; }
    *e = L.elem[i-1];
    printf("第 %d 個元素值為：%d\n", i, *e);
    return 1;
}

void ListTraverse(SqList L) {
    for (int i = 0; i < L.length; i++)
        printf("%5d", L.elem[i]);
    putchar('\n');
}

第三類：加工型操作（修改資料）

10. 清空表 `ClearList` / 11. 賦值操作 `PutElem`

void ClearList(SqList *L) {
    if (L->elem) L->length = 0;  // 僅重置長度，不釋放記憶體
}

void PutElem(SqList *L, int i, int e) {
    if (i < 1 || i > L->length) { puts("位置非法！"); return; }
    L->elem[i-1] = e;
}

12. 插入操作 `ListInsert`（核心難點）

void ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) { puts("插入位置非法！"); return; }

    // 容量不足時自動擴容
    if (L->length >= L->listsize) {
        int *newbase = (int *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
        if (!newbase) { puts("擴容失敗！"); exit(1); }
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }

    // 從後向前移動元素騰出位置
    int *q = &(L->elem[i-1]);           // 插入位置指標
    for (int *p = &(L->elem[L->length-1]); p >= q; --p)
        *(p+1) = *p;

    *q = e;            // 插入新元素
    ++L->length;       // 長度加 1
}

realloc 陷阱：realloc 可能返回新地址，必須用臨時指標接收，失敗時原記憶體不會被釋放，避免記憶體洩漏。

時間複雜度：最好 O(1)（尾插），最壞 O(n)（頭插），平均 O(n)。

13. 刪除操作 `ListDelete`

void ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) { puts("刪除位置非法！"); return; }

    int *p = &(L->elem[i-1]);
    *e = *p;                           // 保存被刪元素值

    // 從前向後移動元素填補空缺
    for (++p; p <= &(L->elem[L->length-1]); ++p)
        *(p-1) = *p;

    --L->length;
}

時間複雜度：同插入操作，平均需移動半數元素，O(n)。

第四類：複雜綜合操作

14. 集合並運算 `Union`（無序表合併）

void Union(SqList *LA, SqList LB) {
    int e;
    for (int i = 1; i <= LB.length; i++) {
        GetElem(LB, i, &e);
        if (!LocateElem(*LA, e))      // A 中不存在該元素
            ListInsert(LA, ++LA->length, e);  // 尾插
    }
}

時間複雜度：O(lengthA × lengthB)，主要耗時在 LocateElem。

15. 有序表歸併 `MergeList`（雙指標法）

void MergeList(SqList LA, SqList LB, SqList *LC) {
    InitList(LC);
    int *pa = LA.elem, *pb = LB.elem;
    int *pa_last = LA.elem + LA.length - 1;
    int *pb_last = LB.elem + LB.length - 1;

    while (pa <= pa_last && pb <= pb_last) {
        if (*pa <= *pb) ListInsert(LC, ++LC->length, *pa++);
        else ListInsert(LC, ++LC->length, *pb++);
    }
    while (pa <= pa_last) ListInsert(LC, ++LC->length, *pa++);
    while (pb <= pb_last) ListInsert(LC, ++LC->length, *pb++);
}

優化版：直接用指標賦值而非調用 ListInsert，避免重複移動元素，時間複雜度 O(lengthA + lengthB)。

核心洞見：有序表歸併效率遠高於無序表合併；歸併到新表比原地歸併更高效（無需移動元素）。