C語言順序表(動態數組)完整實現：創建、增刪改查與擴容機制

編輯：關於C語言

順序表 ADT 定義


typedef int DataType; // 元素類型，可泛化為 void*

typedef struct {
    DataType *element; // 動態數組基址
    int MAXNUM;        // 當前分配容量
    int n;             // 當前元素個數 (長度)
} SeqList, *PSeqList;

核心操作實現

1. 創建空表 (指定初始容量)


PSeqList CreateNullList_seq(int m) {
    if (m <= 0) m = 10; // 默認最小容量
    PSeqList L = malloc(sizeof(SeqList));
    if (!L) return NULL;
    L->element = malloc(m * sizeof(DataType));
    if (!L->element) { free(L); return NULL; }
    L->MAXNUM = m;
    L->n = 0;
    return L;
}

2. 判空


int IsEmpty_seq(PSeqList L) { return L->n == 0; }

3. 查找 (返回首個匹配下標，失敗 -1)


int Locate_seq(PSeqList L, DataType x) {
    for (int i = 0; i < L->n; i++)
        if (L->element[i] == x) return i;
    return -1;
}

4. 插入 (指定位置前插入，支持自動擴容)


int Insert_seq(PSeqList L, int pos, DataType x) {
    // pos 合法性：0 <= pos <= n (pos==n 相當於尾插)
    if (pos < 0 || pos > L->n) return 0;
    
    // 滿了 -> 擴容 (2倍)
    if (L->n >= L->MAXNUM) {
        int newCap = L->MAXNUM * 2;
        DataType *newArr = realloc(L->element, newCap * sizeof(DataType));
        if (!newArr) return 0; // 擴容失敗
        L->element = newArr;
        L->MAXNUM = newCap;
    }
    
    // 後移騰位
    for (int i = L->n - 1; i >= pos; i--)
        L->element[i + 1] = L->element[i];
    
    L->element[pos] = x;
    L->n++;
    return 1;
}

5. 刪除 (按位置刪除)


int DeletePos_seq(PSeqList L, int pos) {
    if (pos < 0 || pos >= L->n) return 0;
    for (int i = pos; i < L->n - 1; i++)
        L->element[i] = L->element[i + 1];
    L->n--;
    // 可選：縮容策略 (如 n < MAXNUM/4 則縮半)
    return 1;
}

6. 刪除 (按值刪除首個匹配)


int DeleteVal_seq(PSeqList L, DataType x) {
    int pos = Locate_seq(L, x);
    if (pos == -1) return 0;
    return DeletePos_seq(L, pos);
}

7. 獲取/修改元素


DataType Get_seq(PSeqList L, int pos) {
    if (pos < 0 || pos >= L->n) exit(1); // 或返回錯誤碼
    return L->element[pos];
}

void Set_seq(PSeqList L, int pos, DataType x) {
    if (pos >= 0 && pos < L->n) L->element[pos] = x;
}

8. 銷毀釋放


void Destroy_seq(PSeqList L) {
    if (L) {
        free(L->element);
        free(L);
    }
}

測試驅動


int main() {
    PSeqList L = CreateNullList_seq(5); // 小容量觸發擴容演示
    Insert_seq(L, 0, 10); // [10]
    Insert_seq(L, 1, 20); // [10,20]
    Insert_seq(L, 1, 15); // [10,15,20]
    Insert_seq(L, 3, 30); // [10,15,20,30]
    Insert_seq(L, 0, 5);  // [5,10,15,20,30] 滿
    Insert_seq(L, 6, 40); // 觸發擴容 -> [5,10,15,20,30,40]
    
    printf("Length: %d, Capacity: %d\n", L->n, L->MAXNUM);
    for (int i = 0; i < L->n; i++) printf("%d ", Get_seq(L, i));
    printf("\n");
    
    DeletePos_seq(L, 0); // 刪 5
    DeleteVal_seq(L, 30); // 刪 30
    printf("After delete: ");
    for (int i = 0; i < L->n; i++) printf("%d ", Get_seq(L, i));
    
    Destroy_seq(L);
    return 0;
}