C 語言動態順序表完整實現：增刪改查、擴容、穩健封裝

編輯：關於C語言

C 語言動態順序表完整實現：增刪改查、擴容、穩健封裝

順序表是線性表的順序存儲結構。動態順序表以 malloc 分配記憶體，支援自動擴容，克服靜態順序表容量固定的缺陷。本文提供生產級封裝：.h 介面與 .c 實現分離、assert 防禦、擴容策略、完整 CRUD 操作。

一、頭文件 seq_list.h

#pragma once
#include <stddef.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

typedef int DataType;
typedef struct SeqList {
    DataType *array;
    size_t size;
    size_t capacity;
} SeqList;

// 初始化/銷毀
void SeqListInit(SeqList *sl);
void SeqListDestroy(SeqList *sl);

// 容量檢查與擴容（內部）
void SeqListCheckCapacity(SeqList *sl);

// 基本操作
void SeqListPushBack(SeqList *sl, DataType x);
void SeqListPopBack(SeqList *sl);
void SeqListPushFront(SeqList *sl, DataType x);
void SeqListPopFront(SeqList *sl);

// 查找/修改/插入/刪除
int  SeqListFind(SeqList *sl, DataType x);        // 返回索引，-1 未找到
void SeqListInsert(SeqList *sl, size_t pos, DataType x);
void SeqListErase(SeqList *sl, size_t pos);
void SeqListModify(SeqList *sl, size_t pos, DataType x);
void SeqListRemove(SeqList *sl, DataType x);      // 刪除第一個 x
void SeqListRemoveAll(SeqList *sl, DataType x);   // 刪除所有 x

// 遍歷
void SeqListPrint(SeqList *sl);

二、核心實現亮點

1. 擴容策略（二倍增長）

void SeqListCheckCapacity(SeqList *sl) {
    assert(sl);
    if (sl->size >= sl->capacity) {
        size_t newCap = (sl->capacity == 0) ? 4 : sl->capacity * 2;
        DataType *tmp = realloc(sl->array, newCap * sizeof(DataType));
        assert(tmp); // 生產環境應處理分配失敗
        sl->array = tmp;
        sl->capacity = newCap;
    }
}

用 realloc 替代 malloc+memcpy+free，更簡潔高效。

2. 刪除所有目標值（雙指針單趟 O(N)）

void SeqListRemoveAll(SeqList *sl, DataType x) {
    assert(sl);
    size_t src = 0, dst = 0;
    while (src < sl->size) {
        if (sl->array[src] != x) {
            sl->array[dst++] = sl->array[src];
        }
        src++;
    }
    sl->size = dst;
}

src 掃描全陣列，dst 指向下一個保留位置，非目標值前移，單趟完成，無需巢狀迴圈。

3. 插入/刪除位置合法性檢查

void SeqListInsert(SeqList *sl, size_t pos, DataType x) {
    assert(sl);
    assert(pos <= sl->size); // 允許 pos == size（相當 PushBack）
    SeqListCheckCapacity(sl);
    for (size_t i = sl->size; i > pos; i--) {
        sl->array[i] = sl->array[i-1];
    }
    sl->array[pos] = x;
    sl->size++;
}

三、測試主程式

#include "seq_list.h"
int main() {
    SeqList sl; SeqListInit(&sl);
    SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2);
    SeqListPushFront(&sl, 0); // 0 1 2
    SeqListInsert(&sl, 2, 99); // 0 1 99 2
    SeqListRemoveAll(&sl, 1);  // 0 99 2
    SeqListPrint(&sl);
    SeqListDestroy(&sl);
    return 0;
}