C 語言陣列實現線性表完整教程：從基礎操作到插入排序

編輯：關於C語言

線性表是資料結構中最基礎的結構之一。本文示範如何在 C 語言中使用動態陣列實現線性表，包含初始化、增刪改查、遍歷、倒置與插入排序等完整操作，代碼結構清晰，適合初學者理解動態記憶體管理與線性表邏輯。

一、資料結構設計

定義結構體 `Arr` 封裝動態陣列的三大核心屬性：

struct Arr {
    int *pBase;  // 動態陣列首地址
    int len;     // 陣列總容量
    int cnt;     // 當前元素個數
};

二、核心操作實現

1. 初始化：動態分配記憶體

void init_arr(struct Arr *pArr, int length) {
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if (NULL == pArr->pBase) {
        printf("動態記憶體分配失敗!\n");
        exit(-1);
    }
    pArr->len = length;
    pArr->cnt = 0;
}

關鍵點：檢查 `malloc` 返回值，失敗時終止程式；初始化計數器為 0。

2. 追加元素：尾部插入

bool append_arr(struct Arr *pArr, int val) {
    if (pArr->cnt < pArr->len) {
        pArr->pBase[pArr->cnt] = val;
        pArr->cnt++;
        return true;
    }
    printf("陣列已滿\n");
    return false;
}

3. 插入元素：指定位置插入（1-based 索引）

bool insert_arr(struct Arr *pArr, int index, int val) {
    if (pArr->cnt < pArr->len && index <= pArr->cnt) {
        // 從後向前搬移元素騰出位置
        for (int i = pArr->cnt - 1; i >= index - 1; i--) {
            pArr->pBase[i + 1] = pArr->pBase[i];
        }
        pArr->pBase[index - 1] = val;
        pArr->cnt++;
        return true;
    }
    printf("插入失敗\n");
    return false;
}

注意：索引轉換 `index-1` 對應 0-based 陣列下標。

4. 刪除元素：指定位置刪除並返回值

bool delete_arr(struct Arr *pArr, int pos, int *pVal) {
    if (is_empty(pArr) || pos < 1 || pos > pArr->cnt) return false;
    *pVal = pArr->pBase[pos - 1];
    // 前移元素覆蓋被刪除位置
    for (int i = pos; i < pArr->cnt; i++) {
        pArr->pBase[i - 1] = pArr->pBase[i];
    }
    pArr->cnt--;
    return true;
}

5. 判斷空/滿、獲取元素、遍歷

bool is_empty(struct Arr *pArr) { return pArr->cnt == 0; }
bool is_full(struct Arr *pArr) { return pArr->cnt == pArr->len; }

int get(struct Arr *pArr, int index) {  // 0-based 索引
    if (index >= 0 && index < pArr->cnt) return pArr->pBase[index];
    return -1; // 或錯誤處理
}

void show_arr(struct Arr *pArr) {
    if (is_empty(pArr)) { printf("陣列為空\n"); return; }
    for (int i = 0; i < pArr->cnt; i++) printf("%d ", pArr->pBase[i]);
    printf("\n");
}

6. 倒置陣列：雙指針交換

void inversion_arr(struct Arr *pArr) {
    int i = 0, j = pArr->cnt - 1, t;
    while (i < j) {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        i++; j--;
    }
}

三、直接插入排序實現

採用「單步插入」函數配合外層迴圈，將無序區元素逐個插入有序區。

核心邏輯：單步插入

void one_sort(int *sqList, int val, int len) {
    int pos = len;
    int temp = val;
    // 從右向左尋找插入位置
    while (val < sqList[pos - 1] && pos > 0) {
        sqList[pos] = sqList[pos - 1]; // 向右搬移
        pos--;
    }
    sqList[pos] = temp; // 插入
}

排序驅動函數

void straisort(struct Arr *pArr) {
    for (int i = 1; i < pArr->cnt; i++) {
        one_sort(pArr->pBase, pArr->pBase[i], i);
    }
}

複雜度：時間 O(n²)，空間 O(1)，穩定排序，適合小規模或近乎有序資料。

四、主程式測試範例

int main(void) {
    struct Arr arr;
    init_arr(&arr, 6);  // 容量 6

    append_arr(&arr, 3);
    append_arr(&arr, 2);
    append_arr(&arr, 9);
    insert_arr(&arr, 2, 7); // 在第 2 位插入 7

    printf("操作後陣列: ");
    show_arr(&arr); // 輸出: 3 7 2 9

    // 測試排序
    straisort(&arr);
    printf("排序後陣列: ");
    show_arr(&arr); // 輸出: 2 3 7 9

    return 0;
}