C語言順序表（線性表）完整實作：初始化、插入、刪除、查找

編輯：關於C語言

順序表定義

順序表用**連續記憶體**存儲線性表元素，支援隨機存取。結構包含：資料陣列、當前長度、最大容量。

資料結構定義

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status;

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

核心操作實作

1. 初始化

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

2. 獲取元素 (按位序，1-based)

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

3. 插入元素

Status ListInsert(SqList *L, int i, ElemType e) {
    if(L->length == MAXSIZE) return ERROR;      // 滿
    if(i < 1 || i > L->length + 1) return ERROR; // 位置非法 (允許在尾後插入)

    // 從後向前移動，騰出位置
    for(int k = L->length - 1; k >= i - 1; k--)
        L->data[k+1] = L->data[k];
    
    L->data[i-1] = e;
    L->length++;
    return OK;
}

4. 刪除元素

Status ListDelete(SqList *L, int i, ElemType *e) {
    if(L->length == 0) return ERROR;            // 空
    if(i < 1 || i > L->length) return ERROR;    // 位置非法

    *e = L->data[i-1];
    
    // 從前向後移動，覆蓋被刪位置
    for(int k = i; k < L->length; k++)
        L->data[k-1] = L->data[k];
    
    L->length--;
    return OK;
}

5. 查找元素 (按值，回傳位序)

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

6. 遍歷輸出

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

測試主程式

int main() {
    SqList L;
    InitList(&L);

    // 測試插入
    ListInsert(&L, 1, 10);  // [10]
    ListInsert(&L, 2, 20);  // [10, 20]
    ListInsert(&L, 2, 15);  // [10, 15, 20]
    ListInsert(&L, 4, 25);  // [10, 15, 20, 25]
    printf("插入後: "); PrintList(L);

    // 測試獲取
    ElemType e;
    GetElem(L, 2, &e);
    printf("第2個元素: %d\n", e);  // 15

    // 測試查找
    printf("20 的位序: %d\n", LocateElem(L, 20));  // 3

    // 測試刪除
    ListDelete(&L, 2, &e);  // 刪除 15
    printf("刪除第2個後: "); PrintList(L);  // [10, 20, 25]

    return 0;
}

順序表 vs 鏈表對比

操作	順序表	鏈表
存取第 i 個	O(1)	O(i)
插入/刪除	O(n) 移動元素	O(1) 修改指標 (已定位)
記憶體	連續，預分配，可能浪費/不足	動態分配，無碎片，額外指標開銷
擴容	需重新分配複製	自然增長

動態順序表擴展（C++ vector 風格）

typedef struct {
    ElemType *data;   // 動態陣列
    int length;       // 當前長度
    int capacity;     // 當前容量
} DynSqList;

Status InitDynList(DynSqList *L, int init_cap) {
    L->data = (ElemType*)malloc(init_cap * sizeof(ElemType));
    if(!L->data) return ERROR;
    L->length = 0;
    L->capacity = init_cap;
    return OK;
}

Status DynListInsert(DynSqList *L, int i, ElemType e) {
    if(i < 1 || i > L->length + 1) return ERROR;
    if(L->length == L->capacity) {
        int new_cap = L->capacity * 2;
        ElemType *new_data = (ElemType*)realloc(L->data, new_cap * sizeof(ElemType));
        if(!new_data) return ERROR;
        L->data = new_data;
        L->capacity = new_cap;
    }
    // 同順序表移動邏輯...
    return OK;
}