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

動態順序表（線性表）C語言完整實現：15 種核心操作詳解

編輯：關於C

線性表與順序表基礎

線性表：n 個數據元素的有限序列，邏輯關係為一對一。
順序表：用一組連續內存單元順序存儲線性表元素，邏輯與物理鄰接一致，支持隨機訪問。
動態順序表：內存由 malloc/realloc 動態管理，容量可自動擴展。

ADT 接口設計 (ADT.h)

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct {
    int *elem;     // 數據基址
    int length;    // 當前長度
    int listsize;  // 當前分配容量
} SqList;

// 15 操作聲明
int InitList(SqList *L);
void DestroyList(SqList *L);
void ClearList(SqList *L);
int ListEmpty(SqList L);
int ListLength(SqList L);
int GetElem(SqList L, int i, int *e);
int LocateElem(SqList L, int e);
void PriorElem(SqList L, int cur_e);
void NextElem(SqList L, int cur_e);
void ListTraverse(SqList L);
void PutElem(SqList *L, int i, int e);
void ListInsert(SqList *L, int i, int e);
void ListDelete(SqList *L, int i, int *e);
void Union(SqList *LA, SqList LB);        // 合並：B中不在A的插入A
void MergeList(SqList LA, SqList LB, SqList *LC); // 歸並：有序A+B→有序C

核心操作實現與複雜度分析

1. 初始化 `InitList` - O(1)

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;
}

2. 銷毀 `DestroyList` - O(1)

void DestroyList(SqList *L) {
    if (L->elem) { free(L->elem); L->elem = NULL; }
    L->length = L->listsize = 0;
}

順序表內存連續，單次 free 即可釋放全部。

3. 清空 `ClearList` - O(1)

void ClearList(SqList *L) { if (L->elem) L->length = 0; }

僅重置長度，保留內存供下次復用。

4. 判空/求長 `ListEmpty/ListLength` - O(1)

直接檢查 L.elem 和 L.length。

5. 定位 `LocateElem` - O(n)

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++)
        if (L.elem[i] == e) return i + 1; // 返回邏輯位序(1-based)
    return 0; // 未找到
}

6. 取值 `GetElem` - O(1)

int GetElem(SqList L, int i, int *e) {
    if (i < 1 || i > L.length) return 0;
    *e = L.elem[i - 1];
    return 1;
}

注意用輸出參數 int* e 返回值，避免值傳遞無效。

7. 前驅/後繼 `PriorElem/NextElem` - O(n)

先定位再判斷邊界，輸出邏輯鄰接元素。

8. 遍歷 `ListTraverse` - O(n)

順序訪問數組輸出。

9. 賦值 `PutElem` - O(1)

void PutElem(SqList *L, int i, int e) {
    if (i >= 1 && i <= L->length) L->elem[i - 1] = e;
}

10. 插入 `ListInsert` - O(n)

void ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return;
    if (L->length >= L->listsize) { // 擴容
        int *newbase = (int*)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(int));
        if (!newbase) exit(0);
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    }
    int *p = &L->elem[i - 1];          // 插入位置
    for (int *q = &L->elem[L->length - 1]; q >= p; q--)
        *(q + 1) = *q;                 // 後移
    *p = e;
    L->length++;
}

關鍵點：realloc 可能移動內存，必須用臨時指針接收返回值，防止分配失敗導致原指針丟失（內存洩漏）。

平均時間：移動元素期望 n/2，O(n)。

11. 刪除 `ListDelete` - O(n)

void ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return;
    int *p = &L->elem[i - 1];
    *e = *p;
    for (; p < &L->elem[L->length - 1]; p++)
        *p = *(p + 1); // 前移
    L->length--;
}

平均時間：同插入，O(n)。

12. 無序合並 `Union` - O(LA_len * LB_len)

遍歷 B，若 A 中無該元素（LocateElem），插入 A 尾部。

13. 有序歸並 `MergeList` - O(LA_len + LB_len)

雙指針法，類似歸並排序合併階段。利用有序性，單次掃描完成。

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;
    LC->listsize = LC->length = LA.length + LB.length;
    LC->elem = (int*)malloc(LC->listsize * sizeof(int));
    int *pc = LC->elem;
    while (pa <= pa_last && pb <= pb_last)
        *pc++ = (*pa <= *pb) ? *pa++ : *pb++;
    while (pa <= pa_last) *pc++ = *pa++;
    while (pb <= pb_last) *pc++ = *pb++;
}

此版本直接指針操作，避免重複調用 GetElem/ListInsert 開銷，更高效。