C 語言實作動態字串陣列：從 malloc/realloc 到完整封裝庫

編輯：關於C語言

一、設計目標與資料結構

實現類似 C++ vector<string> 的功能：動態增刪改查、排序、記憶體自動擴縮。核心結構：

typedef struct {
    char *str;      // 字串內容 (堆上分配)
    size_t len;     // 長度 (含結束符)
} StringNode;

typedef struct {
    StringNode *nodes; // 連續記憶體區
    size_t count;      // 當前元素數
    size_t capacity;   // 當前容量
} StringArray;

二、核心操作實作精要

1. 容量自動成長策略

static int ensureCapacity(StringArray *arr, size_t need) {
    if (arr->capacity >= need) return 0;
    size_t newCap = arr->capacity ? arr->capacity * 2 : 4;
    while (newCap < need) newCap *= 2;
    StringNode *newNodes = realloc(arr->nodes, newCap * sizeof(StringNode));
    if (!newNodes) return -1; // 分配失敗
    arr->nodes = newNodes;
    arr->capacity = newCap;
    return 0;
}

2. 新增元素 (尾端)

int sa_push(StringArray *arr, const char *src) {
    if (!arr || !src) return -1;
    if (ensureCapacity(arr, arr->count + 1)) return -1;
    
    size_t len = strlen(src) + 1;
    char *copy = malloc(len);
    if (!copy) return -1;
    memcpy(copy, src, len);
    
    arr->nodes[arr->count].str = copy;
    arr->nodes[arr->count].len = len;
    arr->count++;
    return 0;
}

3. 依值刪除 (首次匹配)

int sa_remove(StringArray *arr, const char *target) {
    if (!arr || !target) return -1;
    for (size_t i = 0; i < arr->count; i++) {
        if (strcmp(arr->nodes[i].str, target) == 0) {
            free(arr->nodes[i].str);
            // 後續元素前移覆蓋
            for (size_t j = i; j < arr->count - 1; j++)
                arr->nodes[j] = arr->nodes[j+1];
            arr->count--;
            return 0;
        }
    }
    return -1; // 未找到
}

4. 指定位置插入 (核心難點：realloc 後指標失效)

int sa_insert(StringArray *arr, size_t index, const char *src) {
    if (!arr || !src) return -1;
    if (index > arr->count) index = arr->count; // 邊界修正
    
    // 記錄舊指標用於修正插入位置
    StringNode *oldBase = arr->nodes;
    if (ensureCapacity(arr, arr->count + 1)) return -1;
    // realloc 可能移動記憶體，需重新計算插入位置指標
    StringNode *pos = arr->nodes + index;
    
    size_t len = strlen(src) + 1;
    char *copy = malloc(len);
    if (!copy) return -1;
    memcpy(copy, src, len);
    
    // 從尾端向前搬移騰出空位
    for (size_t i = arr->count; i > index; i--)
        arr->nodes[i] = arr->nodes[i-1];
    
    pos->str = copy;
    pos->len = len;
    arr->count++;
    return 0;
}

5. 排序：冒泡 vs 快排

int sa_sort(StringArray *arr, int ascending) {
    if (!arr || arr->count < 2) return 0;
    // 簡易冒泡 O(n^2) - 教學用
    for (size_t i = 0; i < arr->count - 1; i++) {
        for (size_t j = 0; j < arr->count - 1 - i; j++) {
            int cmp = strcmp(arr->nodes[j].str, arr->nodes[j+1].str);
            if ((ascending && cmp > 0) || (!ascending && cmp < 0)) {
                StringNode tmp = arr->nodes[j];
                arr->nodes[j] = arr->nodes[j+1];
                arr->nodes[j+1] = tmp;
            }
        }
    }
    return 0;
    // 生產環境建議用 qsort(arr->nodes, arr->count, sizeof(StringNode), cmpWrapper);
}

三、完整封裝庫標頭檔

// str_array.h
#ifndef STR_ARRAY_H
#define STR_ARRAY_H

typedef struct StringArray StringArray;

StringArray *sa_create(void);
void sa_destroy(StringArray *arr);
int sa_push(StringArray *arr, const char *str);
int sa_insert(StringArray *arr, size_t index, const char *str);
int sa_remove(StringArray *arr, const char *str);
const char *sa_get(StringArray *arr, size_t index);
int sa_set(StringArray *arr, size_t index, const char *str);
size_t sa_size(StringArray *arr);
int sa_sort(StringArray *arr, int ascending);
int sa_find(StringArray *arr, const char *str); // 回傳索引或 -1

#endif

四、測試驗證主程式

#include "str_array.h"
#include 

int main() {
    StringArray *sa = sa_create();
    
    sa_push(sa, "delta");
    sa_push(sa, "alpha");
    sa_push(sa, "epsilon");
    sa_insert(sa, 1, "beta");  // alpha, beta, delta, epsilon
    sa_remove(sa, "delta");    // alpha, beta, epsilon
    
    printf("Count: %zu\n", sa_size(sa));
    for (size_t i = 0; i < sa_size(sa); i++)
        printf("[%zu] %s\n", i, sa_get(sa, i));
    
    sa_sort(sa, 1); // 升序
    puts("\nAfter sort:");
    for (size_t i = 0; i < sa_size(sa); i++)
        printf("[%zu] %s\n", i, sa_get(sa, i));
    
    sa_destroy(sa);
    return 0;
}