數據結構：串（String）的多種存儲結構與堆分配實現

數據結構：串（String）的多種存儲結構與堆分配實現

串是字符序列的有限序列，可視為特殊的線性表。本文系統梳理串的三大類存儲表示（順序、鏈式、索引），並以最靈活的堆分配順序串（動態數組）為基礎，給出完整的 C 語言基本操作實現：初始化、賦值、複製、連接、比較、求子串、查找、插入、刪除、輸出等。

一、串的存儲結構分類

1. 順序存儲

• 定長數組：#define MAXSIZE 100; typedef char SString[MAXSIZE]; 固定長度，易溢出。
• 帶長度數組：typedef struct { char ch[MAXSIZE]; int length; } SqString; 避免每次遍歷求長。
• 堆分配（動態數組）：typedef struct { char* ch; int length; } HString; 按需分配，靈活擴容，推薦用於通用庫實現。

2. 鏈式存儲

• 字符鏈表：每結點存一字符，空間利用率極低，教學演示用。
• 塊鏈：每結點存字符數組（如 3-4 字符），折中方案，適合大文本編輯器。

3. 索引存儲

• 建立索引表記錄串名、長度、起始地址（可選終止地址），用於大量串的快速檢索管理。

二、堆分配順序串（HString）完整實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char* ch;     // 動態數組基址，空串為 NULL
    int length;   // 串長度
} HString;

// 初始化空串
void Str_Init(HString* S) {
    S->ch = NULL;
    S->length = 0;
}

// 銷毀/清空串
void Str_Clear(HString* S) {
    if (S->ch) {
        free(S->ch);
        S->ch = NULL;
    }
    S->length = 0;
}

// 判空
int Str_IsEmpty(const HString* S) {
    return S->length == 0;
}

// 獲取長度
int Str_GetLength(const HString* S) {
    return S->length;
}

// 賦值：從 C 字符串複製
void Str_Assign(HString* S, const char* chars) {
    Str_Clear(S);
    int len = strlen(chars);
    if (len == 0) return;
    S->ch = (char*)malloc((len + 1) * sizeof(char));  // +1 存 '\0' 方便輸出
    if (!S->ch) exit(EXIT_FAILURE);
    strcpy(S->ch, chars);
    S->length = len;
}

// 複製：T -> S
void Str_Copy(HString* S, const HString* T) {
    Str_Clear(S);
    S->length = T->length;
    if (S->length) {
        S->ch = (char*)malloc((S->length + 1) * sizeof(char));
        strcpy(S->ch, T->ch);
    }
}

// 連接：T 接到 S 後
void Str_Concat(HString* S, const HString* T) {
    if (T->length == 0) return;
    char* newCh = (char*)malloc((S->length + T->length + 1) * sizeof(char));
    if (!newCh) exit(EXIT_FAILURE);
    if (S->length) strcpy(newCh, S->ch);
    strcpy(newCh + S->length, T->ch);
    Str_Clear(S);
    S->ch = newCh;
    S->length += T->length;
}

// 比較：S > T 返回正，= 返回 0，< 返回負
int Str_Compare(const HString* S, const HString* T) {
    int minLen = S->length < T->length ? S->length : T->length;
    for (int i = 0; i < minLen; ++i) {
        if (S->ch[i] != T->ch[i]) return S->ch[i] - T->ch[i];
    }
    return S->length - T->length;
}

// 求子串：從 pos 開始長 len，存入 Sub
void Str_GetSub(const HString* S, int pos, int len, HString* Sub) {
    Str_Clear(Sub);
    if (pos < 1 || pos > S->length || len < 0 || len > S->length - pos + 1) {
        fprintf(stderr, "Invalid pos/len\n");
        return;
    }
    if (len == 0) return;
    Sub->ch = (char*)malloc((len + 1) * sizeof(char));
    strncpy(Sub->ch, S->ch + pos - 1, len);
    Sub->ch[len] = '\0';
    Sub->length = len;
}

// 查找子串：在 S 中 pos 位置後找 Sub 首次出現，返回 1-based 索引，失敗返回 -1
int Str_GetSubIndex(const HString* S, const HString* Sub, int pos) {
    if (pos < 1 || pos > S->length) return -1;
    if (Str_IsEmpty(S)) return -1;
    if (Str_IsEmpty(Sub)) return 0;  // 空串是任意串子串
    
    for (int i = pos - 1; i <= S->length - Sub->length; ++i) {
        int j;
        for (j = 0; j < Sub->length; ++j) {
            if (S->ch[i + j] != Sub->ch[j]) break;
        }
        if (j == Sub->length) return i + 1;  // 1-based
    }
    return -1;
}

// 插入子串：在 S 的 pos 位置前插入 T
void Str_Insert(HString* S, int pos, const HString* T) {
    if (pos < 1 || pos > S->length + 1) return;
    if (T->length == 0) return;
    
    char* newCh = (char*)malloc((S->length + T->length + 1) * sizeof(char));
    strncpy(newCh, S->ch, pos - 1);
    strcpy(newCh + pos - 1, T->ch);
    strcpy(newCh + pos - 1 + T->length, S->ch + pos - 1);
    Str_Clear(S);
    S->ch = newCh;
    S->length += T->length;
}

// 刪除子串：從 pos 刪除 len 個字符
void Str_DeleteSub(HString* S, int pos, int len) {
    if (pos < 1 || pos > S->length || len < 0 || len > S->length - pos + 1) return;
    if (len == 0) return;
    
    char* newCh = (char*)malloc((S->length - len + 1) * sizeof(char));
    strncpy(newCh, S->ch, pos - 1);
    strcpy(newCh + pos - 1, S->ch + pos - 1 + len);
    Str_Clear(S);
    S->ch = newCh;
    S->length -= len;
}

// 輸出串
void Str_Print(const HString* S) {
    if (Str_IsEmpty(S)) {
        printf("(empty)\n");
    } else {
        printf("%s\n", S->ch);
    }
}

三、測試示例

int main() {
    HString s1, s2, sub;
    Str_Init(&s1); Str_Init(&s2); Str_Init(&sub);
    
    Str_Assign(&s1, "Hello");
    Str_Assign(&s2, "World");
    Str_Concat(&s1, &s2);        // "HelloWorld"
    Str_Insert(&s1, 6, &s2);     // "HelloWorldWorld" (pos=6 插入)
    Str_GetSub(&s1, 1, 5, &sub); // "Hello"
    Str_Print(&sub);
    printf("Index of 'World': %d\n", Str_GetSubIndex(&s1, &s2, 1)); // 6
    Str_DeleteSub(&s1, 6, 5);    // 刪除第一個 World
    Str_Print(&s1);              // "HelloWorld"
    
    Str_Clear(&s1); Str_Clear(&s2); Str_Clear(&sub);
    return 0;
}

四、關鍵實現細節避坑

1. 分配 +1 空間存 '\0'：雖然結構體有 length，但以 '\0' 結尾可直接配合 printf("%s")、strcpy/strcat 等標準庫函數，極大簡化代碼。
2. 每次修改長度前先 Str_Clear：避免內存洩漏，統一內存管理邏輯。
3. 位置參數採用 1-based：符合教材習慣，內部轉為 0-based 運算。
4. 錯誤處理：示例中簡化為打印錯誤返回，生產代碼應返回錯誤碼或設置全局錯誤標誌。
5. 原文代碼問題：malloc(3*sizeof(char)) 硬編碼長度、Str_Assign 重複遍歷求長、Str_Concat 臨時變量用法繁瑣，已在上文優化修正。

五、總結

掌握堆分配順序串的動態內存管理模式——修改前清空、按需分配、拷貝數據、更新長度、賦值指針，是實現高性能、安全字符串庫的核心基礎。現代 C++ std::string、C 語言第三方庫（如 SDS、CString）皆是此思想的工業級封裝。