資料結構實戰：C 語言實現字串順序儲存結構（HString）完整操作集

前言

字串順序儲存結構（又稱堆分配儲存）是資料結構課程核心內容。本文提供完整、可編譯運行的 HString 實現，涵蓋賦值、複製、比較、連接、子串、插入、刪除、替換、模式匹配等全部基本操作，並附帶主程式測試用例。

資料結構定義

#define MAXSTRLEN 255
typedef int Status;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef struct {
    char *ch;     // 動態陣列基址
    int length;   // 當前長度
} HString;

核心操作實現精要

1. 賦值 StrAssign

Status StrAssign(HString *T, char *chars) {
    if (T->ch) free(T->ch);
    int len = strlen(chars);
    if (!len) { T->ch = NULL; T->length = 0; return OK; }
    T->ch = (char*)malloc(len * sizeof(char));
    if (!T->ch) exit(OVERFLOW);
    memcpy(T->ch, chars, len);
    T->length = len;
    return OK;
}

關鍵：釋放舊空間 → 分配新空間 → 複製內容 → 更新長度。

2. 複製 StrCopy

Status StrCopy(HString *T, HString S) {
    if (T->ch) free(T->ch);
    T->ch = (char*)malloc(S.length * sizeof(char));
    if (!T->ch) exit(OVERFLOW);
    memcpy(T->ch, S.ch, S.length);
    T->length = S.length;
    return OK;
}

3. 比較 StrCompare

int StrCompare(HString S, HString T) {
    for (int i = 0; i < S.length && i < T.length; ++i)
        if (S.ch[i] != T.ch[i]) return S.ch[i] - T.ch[i];
    return S.length - T.length;
}

返回值語義：<0 (S0 (S>T)，符合 strcmp 慣例。

4. 連接 Concat

Status Concat(HString *T, HString S1, HString S2) {
    if (T->ch) free(T->ch);
    T->length = S1.length + S2.length;
    T->ch = (char*)malloc(T->length * sizeof(char));
    if (!T->ch) exit(OVERFLOW);
    memcpy(T->ch, S1.ch, S1.length);
    memcpy(T->ch + S1.length, S2.ch, S2.length);
    return OK;
}

5. 子串 SubString

Status SubString(HString *Sub, HString S, int pos, int len) {
    if (pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1) return ERROR;
    if (Sub->ch) free(Sub->ch);
    if (!len) { Sub->ch = NULL; Sub->length = 0; return OK; }
    Sub->ch = (char*)malloc(len * sizeof(char));
    if (!Sub->ch) exit(OVERFLOW);
    memcpy(Sub->ch, S.ch + pos - 1, len);
    Sub->length = len;
    return OK;
}

注意：pos 從 1 起算，符合教材慣例。

6. 插入 StrInsert

Status StrInsert(HString *S, int pos, HString T) {
    if (pos < 1 || pos > S->length + 1) return ERROR;
    if (T.length) {
        S->ch = (char*)realloc(S->ch, (S->length + T.length) * sizeof(char));
        if (!S->ch) exit(OVERFLOW);
        for (int i = S->length - 1; i >= pos - 1; --i)
            S->ch[i + T.length] = S->ch[i];
        memcpy(S->ch + pos - 1, T.ch, T.length);
        S->length += T.length;
    }
    return OK;
}

技巧：從尾部向前搬移資料，避免覆蓋；使用 realloc 擴容。

7. 刪除 StrDelete

Status StrDelete(HString *S, int pos, int len) {
    if (S->length < pos + len - 1) return ERROR;
    for (int i = pos - 1; i <= S->length - len; ++i)
        S->ch[i] = S->ch[i + len];
    S->length -= len;
    S->ch = (char*)realloc(S->ch, S->length * sizeof(char));
    return OK;
}

8. 替換 Replace（非重疊）

Status Replace(HString *S, HString T, HString V) {
    if (StrEmpty(T)) return ERROR;
    int i = 1;
    while (i = Index(*S, T, i)) {
        StrDelete(S, i, StrLength(T));
        StrInsert(S, i, V);
        i += StrLength(V);
    }
    return OK;
}

9. 模式匹配 Index（朴素演算法）

int Index(HString S, HString T, int pos) {
    HString sub; InitString(&sub);
    int n = StrLength(S), m = StrLength(T);
    for (int i = pos; i <= n - m + 1; ++i) {
        SubString(&sub, S, i, m);
        if (StrCompare(sub, T) == 0) return i;
    }
    return 0;
}

複雜度：O(n·m)，教學用；工程建議 KMP/BM/KMP。

測試主程式與輸出示例

int main() {
    HString t, s, r;
    InitString(&t); InitString(&s); InitString(&r);
    StrAssign(&t, "God bye!");
    StrAssign(&s, "God luck!");
    // 比較、連接、替換、子串、複製、插入、刪除、定位等綜合測試
    // ...
    return 0;
}

輸出片段：

定義了兩個串:
串t為: God bye!
串長為 : 8 串空否？0 ( 1 : 空 0 : 否)
串s為: God luck!
串s<串t
串t聯接串s產生的串r為: God bye!God luck!
把串r中和串t相同的子串用串s代替後，串r為:
God luck! luck!
...

記憶體管理檢查清單

• ✅ 所有 malloc/realloc 檢查返回值。
• ✅ 每次重新分配前 free 舊指標。
• ✅ ClearString 歸零長度並置空指標。
• ✅ 主程式結束前隱式由 OS 回收，長期運行程式需顯式釋放。

擴展建議

1. 實現 KMP GetNext/Index_KMP 提升匹配效能。
2. 增加 StrAssign 緩衝區擴容策略（倍增法），減少重分配次數。
3. 封裝為 C++ 類別 HString，利用 RAII 自動管理資源。
4. 加入單元測試框架（如 Unity/CMocka）覆蓋邊界條件。

總結

順序儲存字串結構通過動態陣列實現變長字串，核心在於「長度顯式存儲 + 記憶體自主管理」。掌握其基本操作邏輯，能深入理解標準庫 string.h、std::string 底層原理，為高效字串處理打下堅實基礎。