C 語言動態順序表完整實現：增容、排序、二分查找

數據結構定義

typedef int DataType;
typedef struct {
    DataType *array;
    size_t size;
    size_t capacity;
} SeqList;

核心操作實現

初始化與增容

void init(SeqList *s) {
    s->array = malloc(4 * sizeof(DataType));
    s->capacity = 4;
    s->size = 0;
}

void ensureCapacity(SeqList *s) {
    if (s->size == s->capacity) {
        s->capacity *= 2;
        s->array = realloc(s->array, s->capacity * sizeof(DataType));
    }
}

尾插/尾刪

void pushBack(SeqList *s, DataType x) {
    ensureCapacity(s);
    s->array[s->size++] = x;
}
void popBack(SeqList *s) {
    if (s->size) s->size--;
}

冒泡排序（升序）

void bubbleSort(SeqList *s) {
    for (size_t i = 0; i < s->size; ++i) {
        int swapped = 0;
        for (size_t j = 0; j + 1 < s->size - i; ++j)
            if (s->array[j] > s->array[j+1]) {
                DataType t = s->array[j];
                s->array[j] = s->array[j+1];
                s->array[j+1] = t;
                swapped = 1;
            }
        if (!swapped) break;
    }
}

選擇排序（降序，雙向）

void selectSort(SeqList *s) {
    size_t l = 0, r = s->size - 1;
    while (l < r) {
        size_t min = l, max = r;
        for (size_t i = l; i <= r; ++i) {
            if (s->array[i] < s->array[min]) min = i;
            if (s->array[i] > s->array[max]) max = i;
        }
        // 換到兩端
        DataType t = s->array[l]; s->array[l] = s->array[min]; s->array[min] = t;
        if (max == l) max = min; // 若最大值在 l，已被換走
        t = s->array[r]; s->array[r] = s->array[max]; s->array[max] = t;
        ++l; --r;
    }
}

二分查找（前提：已排序）

int binarySearch(SeqList *s, DataType x) {
    size_t l = 0, r = s->size;
    while (l < r) {
        size_t m = l + (r - l) / 2;
        if (s->array[m] < x) l = m + 1;
        else r = m;
    }
    return (l < s->size && s->array[l] == x) ? l : -1;
}

測試主程序

int main() {
    SeqList s; init(&s);
    pushBack(&s, 1); pushBack(&s, 4); pushBack(&s, 3); pushBack(&s, 2);
    pushBack(&s, 9); pushBack(&s, 6); pushBack(&s, 7); pushBack(&s, 5);
    bubbleSort(&s);  // 1 2 3 4 5 6 7 9
    selectSort(&s);  // 9 7 6 5 4 3 2 1
    printf("Index of 2: %d\n", binarySearch(&s, 2)); // 需先升序
    return 0;
}

內存管理

程序結束前務必 free(s.array)，避免洩漏。生產代碼建議封裝 destroy(SeqList*)。