C++ 串的定長順序存儲結構完整實現與操作詳解

定長順序存儲表示

用一組地址連續的存儲單元存放字符序列，類似線性表的順序結構。固定最大長度 MAX_STRING_SIZE，字符數組末尾不存 '\0'，長度單獨記錄或通過伴隨結構管理。

核心操作接口設計

#define MAX_STRING_SIZE 8
typedef char SString[MAX_STRING_SIZE + 1]; // +1 可選，便於調試

// 基本操作
int Length(SString s);                          // 串長
bool StringConcat(SString T, SString s1, SString s2); // 連接 s1+s2 → T
void PrintString(SString T);                    // 輸出
bool StringAssign(SString T, const char str[]); // 由字符串常量賦值
bool StrCopy(SString T, SString s);             // 複製
bool StrEmpty(SString T);                       // 判空
int StrCompare(SString T, SString T1);          // 比較
void ClearString(SString T);                    // 清空
bool SubString(SString T, SString S, int pos, int len); // 取子串
bool StrInsert(SString S, int pos, SString T);  // 插入
bool StrDelete(SString S, int pos, int len);    // 刪除
// Replace() 與 Index() 待補全

關鍵函數實現細節

1. 串長 Length

int Length(SString s) {
    return strlen(s); // 假設以 '\0' 結尾，或維護單獨長度字段
}

2. 連接 StringConcat

bool StringConcat(SString T, SString s1, SString s2) {
    int len1 = Length(s1), len2 = Length(s2);
    if (len1 + len2 <= MAX_STRING_SIZE) {
        strcpy(T, s1);
        strcat(T, s2);
        return true;
    } else if (len1 < MAX_STRING_SIZE) {
        strcpy(T, s1);
        strncat(T, s2, MAX_STRING_SIZE - len1); // 截斷
        return false; // 發生截斷
    } else {
        strncpy(T, s1, MAX_STRING_SIZE);
        T[MAX_STRING_SIZE] = '\0';
        return false;
    }
}

3. 比較 StrCompare

int StrCompare(SString T, SString T1) {
    int i = 0;
    while (T[i] && T1[i] && T[i] == T1[i]) ++i;
    if (!T[i] && !T1[i]) return 0;
    if (!T[i]) return -1;
    if (!T1[i]) return 1;
    return (T[i] > T1[i]) ? 1 : -1;
}

4. 插入 StrInsert

bool StrInsert(SString S, int pos, SString T) {
    if (pos < 1 || pos > Length(S) + 1) return false;
    int lenS = Length(S), lenT = Length(T);
    if (lenS + lenT <= MAX_STRING_SIZE) {
        // 後移
        for (int i = lenS; i >= pos - 1; --i)
            S[i + lenT] = S[i];
        // 複製
        for (int i = 0; i < lenT; ++i)
            S[pos - 1 + i] = T[i];
        S[lenS + lenT] = '\0';
        return true;
    } else if (lenS < MAX_STRING_SIZE) {
        // 部分插入並截斷
        int canInsert = MAX_STRING_SIZE - lenS;
        for (int i = lenS; i >= pos - 1; --i)
            S[i + canInsert] = S[i];
        for (int i = 0; i < canInsert; ++i)
            S[pos - 1 + i] = T[i];
        S[MAX_STRING_SIZE] = '\0';
        return false; // 發生截斷
    }
    return false; // 無空間
}

5. 刪除 StrDelete

bool StrDelete(SString S, int pos, int len) {
    if (pos < 1 || pos > Length(S) || len < 0) return false;
    int lenS = Length(S);
    if (pos > lenS - len + 1) { // 刪除到末尾
        S[pos - 1] = '\0';
    } else {
        for (int i = pos + len - 1; i < lenS; ++i)
            S[i - len] = S[i];
        S[lenS - len] = '\0';
    }
    return true;
}

測試用例

#include "String.h"
int main() {
    SString T, s1 = "hello", s2 = "world";
    StrInsert(s1, 2, s2); PrintString(s1); // hworldello
    SubString(T, s1, 1, 6); PrintString(T); // hworld
    StringConcat(T, s1, s2); PrintString(T);
    StrCopy(T, s1); PrintString(T);
    StringAssign(T, "bit"); PrintString(T);
    StrDelete(s2, 1, 1); PrintString(s2); // orld
    return 0;
}

待完善功能

• Replace(S, T, V)：將 S 中所有 T 替換為 V。
• Index(S, T, pos)：從 pos 起查找 T 在 S 中首次出現位置（可用 KMP 優化）。

總結

定長順序存儲實現簡單，適合最大長度固定、操作頻率不極高的場景。關鍵在於邊界檢查與截斷處理的規範化。若需頻繁插刪或長度變化大，鏈式存儲或動態數組更合適。