順序表完整實現：初始化、增刪查、動態擴容

什麼是順序表

順序表是線性表的**順序存儲結構**，用一塊連續記憶體依次存放元素。特點：隨機存取 O(1)，插入/刪除需移動元素 O(n)。本文給出帶**動態擴容**的完整 C 實現。

資料結構定義

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int ElemType;

typedef struct {
    ElemType *elem;   // 動態陣列基址
    int length;       // 當前長度
    int listsize;     // 當前分配容量
} SqList;

核心操作實現

1. 初始化與銷毀

int InitSqList(SqList &L) {
    L.elem = new ElemType[LIST_INIT_SIZE];
    if (!L.elem) exit(OVERFLOW);
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}

void DestroySqList(SqList &L) {
    delete [] L.elem;   // 注意用 delete[] 配合 new[]
    L.elem = nullptr;
    L.length = L.listsize = 0;
}

2. 動態擴容插入

int SqListInsert(SqList &L, int i, ElemType x) {
    // 位置合法性：1-based 索引
    if (i < 1 || i > L.length + 1) return ERROR;

    // 滿了就擴容
    if (L.length >= L.listsize) {
        ElemType *newBase = (ElemType*)realloc(L.elem,
            (L.listsize + LIST_INCREMENT) * sizeof(ElemType));
        if (!newBase) exit(OVERFLOW);
        L.elem = newBase;
        L.listsize += LIST_INCREMENT;
    }

    // 向後挪移騰位
    for (int j = L.length - 1; j >= i - 1; --j)
        L.elem[j + 1] = L.elem[j];

    L.elem[i - 1] = x;
    ++L.length;
    return OK;
}

3. 刪除操作

int SqListDelete(SqList &L, int i) {
    if (i < 1 || i > L.length) return ERROR;
    for (int j = i - 1; j < L.length - 1; ++j)
        L.elem[j] = L.elem[j + 1];
    --L.length;
    return OK;  // 不縮容，避免頻繁 realloc
}

4. 按值查找

int LocateElem(SqList L, ElemType x) {
    int i = 1;
    while (i <= L.length && L.elem[i-1] != x) ++i;
    return (i <= L.length) ? i : ERROR;  // 返回 1-based 位置
}

測試主程式

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

int main() {
    SqList L; InitSqList(L);
    CreateSqList(L, 5);  // 輸入 5 個數
    DispSqList(L);

    int x, pos;
    printf("插入值: "); scanf("%d", &x);
    printf("插入位置: "); scanf("%d", &pos);
    while (!SqListInsert(L, pos, x)) {
        printf("越界，重輸入位置: "); scanf("%d", &pos);
    }
    DispSqList(L);

    printf("刪除位置: "); scanf("%d", &pos);
    while (!SqListDelete(L, pos)) {
        printf("越界，重輸入位置: "); scanf("%d", &pos);
    }
    DispSqList(L);

    printf("查找值: "); scanf("%d", &x);
    int p = LocateElem(L, x);
    if (p) printf("位置 %d\n", p);
    else puts("不存在");

    DestroySqList(L);
    return 0;
}

關鍵點總結

• 1-based 介面：符合教材習慣，內部轉 0-based。
• realloc 保留內容：擴容不丟失舊數據。
• 不縮容：刪除只減 length，避免抖動。
• 錯誤碼而非例外：C 風格返回 OK/ERROR，調用者必檢查。