順序表（Sequence List）資料結構詳解與 C 語言完整實作

編輯：關於C語言

什麼是順序表？

順序表是線性表最基礎的儲存結構，採用連續記憶體空間（陣列）依序存放資料元素，邏輯上相鄰的元素在物理位置上也相鄰。特點是隨機存取 O(1)、插入刪除需移動元素 O(n)，適合「查多改少」的場景。

核心結構定義

#define MAXSIZE 20
typedef int ElemType;

typedef struct {
    ElemType data[MAXSIZE];
    int length;
} SeqList;

data：固定大小陣列，儲存元素；
length：當前有效元素個數，區別於陣列容量 MAXSIZE。

基本操作完整實作

1. 初始化與清空

void InitList(SeqList *L) { L->length = 0; }
void ClearList(SeqList *L) { L->length = 0; }

2. 判空與長度

bool ListEmpty(SeqList L) { return L.length == 0; }
int ListLength(SeqList *L) { return L->length; }

3. 插入操作 `ListInsert(L, i, e)`

在第 i 個位置（1-based）插入元素 e，需檢查滿溢與索引合法性，並將 i 及之後元素後移。

bool ListInsert(SeqList *L, int i, ElemType e) {
    if (L->length >= MAXSIZE) return false;           // 滿
    if (i < 1 || i > L->length + 1) return false;     // 索引非法
    for (int j = L->length; j >= i; j--)
        L->data[j] = L->data[j-1];                      // 後移
    L->data[i-1] = e;
    L->length++;
    return true;
}

4. 刪除操作 `ListDelete(L, i, &e)`

刪除第 i 個元素並以 e 返回，前移後續元素填補空缺。

bool ListDelete(SeqList *L, int i, ElemType *e) {
    if (i < 1 || i > L->length) return false;
    *e = L->data[i-1];
    for (int j = i; j < L->length; j++)
        L->data[j-1] = L->data[j];
    L->length--;
    return true;
}

5. 按位查找 `GetElem` 與按值查找 `LocateElem`

bool GetElem(SeqList *L, int i, ElemType *e) {
    if (i < 1 || i > L->length) return false;
    *e = L->data[i-1];
    return true;
}
int LocateElem(SeqList *L, ElemType e) {          // 返回 1-based 位置，0 表未找到
    for (int i = 0; i < L->length; i++)
        if (L->data[i] == e) return i+1;
    return 0;
}

6. 合併去重 `UnionList`

將 ListB 中不存在於 ListA 的元素插入 ListA 尾部。

void UnionList(SeqList *LA, SeqList LB) {
    for (int i = 0; i < LB.length; i++)
        if (!LocateElem(LA, LB.data[i]))
            ListInsert(LA, ++LA->length, LB.data[i]);
}

7. 遍歷輸出

void ShowList(SeqList L) {
    printf("[ ");
    for (int i = 0; i < L.length; i++) printf("%d ", L.data[i]);
    printf("]\n");
}

主程式測試範例

int main() {
    SeqList L, LB;  ElemType r;
    InitList(&L);  InitList(&LB);
    // 建立測試資料
    ListInsert(&L,1,1); ListInsert(&L,2,2); ListInsert(&L,3,3); ListInsert(&L,4,4);
    ListInsert(&L,2,5); ShowList(L);           // [ 1 5 2 3 4 ]
    ListDelete(&L,4,&r); ShowList(L);          // 刪除第4個(3) → [ 1 5 2 4 ]
    GetElem(&L,2,&r); printf("GetElem 2: %d\n", r); // 5
    printf("Locate 5=%d, Locate 3=%d\n", LocateElem(&L,5), LocateElem(&L,3));
    // 合併測試
    ListInsert(&LB,1,3); ListInsert(&LB,2,5); ListInsert(&LB,3,37);
    ListInsert(&LB,4,4); ListInsert(&LB,2,9); ListInsert(&LB,5,109);
    ListInsert(&LB,3,2); ListDelete(&LB,4,&r);
    UnionList(&L, LB); ShowList(L);            // 合併後結果
    return 0;
}