資料結構教材實作：順序表（動態陣列）完整原始碼解析

資料結構教材實作：順序表（動態陣列）完整原始碼解析

概述

順序表是線性表最基礎的儲存結構，本質為可變長度陣列。教材採用 malloc 分配初始容量，滿時以 realloc 擴容，實現空間自適應。

儲存結構示意

核心型別定義 (SequenceList.h)

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *elem;     // 儲存空間基址
    int length;         // 當前長度
    int listsize;       // 當前分配容量
} SqList;

關鍵操作實作 (SequenceList.c)

初始化與銷毀

Status InitList(SqList &L) {
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem) return ERROR;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}

Status DestroyList(SqList &L) {
    free(L.elem);
    L.elem = NULL;
    L.length = L.listsize = 0;
    return OK;
}

插入操作（含自動擴容）

Status ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return ERROR;
    if (L.length >= L.listsize) {
        ElemType *newbase = (ElemType*)realloc(L.elem,
            (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase) return ERROR;
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    for (int j = L.length - 1; j >= i - 1; --j)
        L.elem[j + 1] = L.elem[j];
    L.elem[i - 1] = e;
    ++L.length;
    return OK;
}

刪除、查找、遍歷等操作

刪除同樣需前移元素；按值查找採線性掃描；遍歷直接迴圈輸出。完整程式碼含 ListDelete、LocateElem、ListTraverse 等函數。

測試主程式與結果

int main() {
    SqList L; InitList(L);
    for (int i = 1; i <= 5; ++i) ListInsert(L, i, i * 10);
    ListTraverse(L); // 輸出: 10 20 30 40 50
    ListDelete(L, 3);  // 刪除 30
    ListTraverse(L);   // 輸出: 10 20 40 50
    DestroyList(L);
    return 0;
}

語法難點提示

• 結構體與動態陣列結合
• 指標運算與 realloc 記憶體管理
• 函數指標作為回調（如 ListTraverse 的 visit 參數）

建議初學者親手敲碼、觀察記憶體變化，方能深入理解。