---

🔤 一，串的定義

串（String），又稱字符串，是由零個或多個字符組成的有限序列。通常記為 S = "a?a?…a?"（n≥0），其中：

• S 是串名；
• 雙引號（或單引號）是串的定界符，不屬于串的內容；
• a?（1≤i≤n）是單個字符，稱為串的元素；
• n 是串的長度，當 n=0 時稱為空串（記為 “”）。

串的核心特點是元素的同質性——所有元素都是字符，且元素間存在明確的順序關系。例如，“Hello” 是長度為5的串，由字符 ‘H’、‘e’、‘l’、‘l’、‘o’ 組成。

需要注意的是：

• 空串（“”）與空格串（" "）不同，空格串的長度為空格的個數（如 " " 長度為2）；
• 串中任意連續的字符組成的子序列稱為該串的子串，包含子串的串稱為主串。例如，“abc” 是 “abcdef” 的子串，起始位置為1（通常從1開始計數）。

🌰 二，案例引入

場景1：文本編輯器中的查找替換

在 Word 或記事本中，當你使用“查找替換”功能，將文檔中所有“數據結構”替換為“Data Structure”時：

• 程序需要先在主串（文檔內容）中定位子串“數據結構”的所有位置（模式匹配）；
• 再將這些位置的子串替換為新內容。
  這一過程的效率直接取決于串的模式匹配算法性能。

場景2：用戶手機號驗證

注冊賬號時，系統需驗證輸入的手機號是否為11位數字：

• 本質是檢查串的長度是否為11，且每個字符是否屬于 ‘0’~‘9’。
  這一過程依賴串的基本操作（長度判斷、字符遍歷）。

這些案例表明，串是處理文本數據的基礎結構，其存儲方式和算法設計直接影響文本處理的效率。

📚 三，串的類型定義、存儲結構及其運算

（一）串的抽象類型定義

串的抽象數據類型（ADT）定義如下，包含數據集合及核心操作：

ADT String {數據：由n（n≥0）個字符組成的有限序列S = "a?a?…a?"，字符具有相同類型。操作：1. StrAssign(&T, chars)：將字符串常量chars賦值給T。2. StrCopy(&T, S)：將串S復制到串T。3. StrEmpty(S)：判斷串S是否為空，空則返回TRUE，否則返回FALSE。4. StrLength(S)：返回串S的長度n。5. StrCompare(S, T)：比較S和T，若S>T返回正數，S=T返回0，S<T返回負數。6. StrConcat(&T, S1, S2)：將S1和S2拼接為新串T（T = S1 + S2）。7. SubString(&Sub, S, pos, len)：從S的第pos個字符開始，截取長度為len的子串Sub。8. StrIndex(S, T, pos)：從S的第pos個字符開始，查找T首次出現的位置，未找到返回0。9. StrReplace(&S, T, V)：將S中所有與T相等的非重疊子串替換為V。10. StrDestroy(&S)：銷毀串S，釋放內存。
}

（二）串的存儲結構

1. 順序存儲（定長順序串）

用固定長度的字符數組存儲串，數組下標表示字符位置，另設變量記錄串的實際長度（避免依賴 ‘\0’ 等結束符）。

• 存儲表示（C語言）：

  #define MAXLEN 255  // 最大長度
  typedef struct {char ch[MAXLEN + 1];  // 存儲字符（+1預留結束符位置）int length;           // 實際長度
  } SString;
  

• 優勢：隨機訪問效率高（通過下標直接獲取字符）；

• 劣勢：長度固定，超過MAXLEN時會截斷（如存儲長文本可能溢出）。

2. 堆分配存儲（動態順序串）

用動態數組存儲串，長度可根據需要動態調整（通過malloc和realloc分配內存）。

• 存儲表示（C語言）：

  typedef struct {char *ch;  // 指向動態分配的字符數組int length; // 實際長度
  } HString;
  

• 初始化示例：

  void InitString(HString *S) {S->ch = NULL;S->length = 0;
  }void StrAssign(HString *T, char *chars) {if (T->ch) free(T->ch); // 釋放原有空間int len = strlen(chars);if (len == 0) {T->ch = NULL;T->length = 0;} else {T->ch = (char*)malloc((len + 1) * sizeof(char));strcpy(T->ch, chars); // 復制字符T->length = len;}
  }
  

• 優勢：長度靈活，適合存儲不確定長度的串；

• 劣勢：動態分配可能產生內存碎片。

3. 鏈式存儲（串的鏈表表示）

用單鏈表存儲串，每個節點存儲一個或多個字符（通常存儲多個以提高效率，稱為“塊鏈”）。

• 存儲表示（每個節點存4個字符，C語言）：

  #define CHUNKSIZE 4  // 每個節點存儲的字符數
  typedef struct Chunk {char ch[CHUNKSIZE];struct Chunk *next;
  } Chunk;typedef struct {Chunk *head, *tail;  // 頭指針和尾指針int length;          // 串的總長度
  } LString;
  

• 優勢：插入刪除方便，適合頻繁修改的場景；

• 劣勢：存儲密度低（需額外存儲指針），隨機訪問效率差。

（三）串的模式匹配算法

模式匹配是指在主串 S 中查找子串 T（模式串）首次出現的位置，是串的核心操作。

1. 樸素模式匹配算法（BF算法）

思路：從主串 S 的第 pos 個字符開始，逐個與模式串 T 的字符比較：

• 若匹配成功，繼續比較下一個字符；
• 若匹配失敗，主串回溯到上一次開始位置的下一個字符，模式串回溯到第一個字符，重新比較。

示例：在 S=“ababcabcacbab” 中查找 T=“abcac”

• 初始從 pos=1 開始，S[1]=‘a’ 與 T[1]=‘a’ 匹配，繼續比較；
• 直到 S[4]=‘b’ 與 T[4]=‘c’ 不匹配，主串回溯到 S[2]，模式串回溯到 T[1]；
• 重復過程，最終在 S[6] 處匹配成功，返回位置6。

代碼實現：

int Index_BF(SString S, SString T, int pos) {int i = pos;  // 主串當前位置（從1開始）int j = 1;    // 模式串當前位置while (i <= S.length && j <= T.length) {if (S.ch[i] == T.ch[j]) {i++; j++;  // 繼續匹配下一個字符} else {i = i - j + 2;  // 主串回溯j = 1;          // 模式串回溯}}if (j > T.length) return i - T.length;  // 匹配成功，返回起始位置else return 0;  // 匹配失敗
}

時間復雜度：最壞情況 O(n×m)（n為主串長度，m為模式串長度），適合短模式串場景。

2. KMP算法

思路：通過預處理模式串 T，得到一個“部分匹配表”（next數組），避免主串回溯，僅移動模式串：

• next[j] 表示 T 中前 j-1 個字符的最長相等前后綴長度；
• 匹配失敗時，模式串直接跳到 next[j] 位置，主串不回溯。

優勢：時間復雜度優化為 O(n + m)，適合長文本匹配（如論文查重、DNA序列比對）。

🔢 四，數組

（一）數組的類型定義

數組是由相同類型的數據元素組成的有序集合，每個元素由唯一的下標（或索引）標識。

• 一維數組：元素按線性順序排列（如 int a[5]）；
• 二維數組：元素按行和列排列（如 int matrix[3][4]，3行4列）；
• 多維數組：更高維度的擴展（如三維數組可表示立方體）。

數組的抽象數據類型定義核心操作包括：初始化、取元素（根據下標訪問）、修改元素等。

（二）數組的順序存儲

數組在內存中采用順序存儲，即元素按一定次序存放在連續的內存空間中，通過下標計算元素地址。

1. 一維數組

設數組 a[n] 的基地址為 LOC(a[0])，每個元素占用 size 字節，則 a[i] 的地址為：
LOC(a[i]) = LOC(a[0]) + i × size

2. 二維數組

有兩種存儲方式：

• 行優先順序（C語言采用）：先存第0行，再存第1行……第i行第j列元素 a[i][j] 的地址為：
  LOC(a[i][j]) = LOC(a[0][0]) + (i × n + j) × size（n為列數）。
• 列優先順序（Fortran語言采用）：先存第0列，再存第1列……地址公式為：
  LOC(a[i][j]) = LOC(a[0][0]) + (j × m + i) × size（m為行數）。

（三）特殊矩陣的壓縮存儲

特殊矩陣（如對稱矩陣、三角矩陣、對角矩陣）中存在大量重復元素或零元素，可通過壓縮存儲減少空間浪費。

1. 對稱矩陣

若 n 階矩陣 A 滿足 A[i][j] = A[j][i]（i,j=0,1,…,n-1），則只需存儲下三角（含對角線）元素。

• 元素總數為 n(n+1)/2，按行優先順序存入一維數組 sa 中，A[i][j]（i≥j）在 sa 中的下標為：
  k = i(i+1)/2 + j。

2. 稀疏矩陣

非零元素極少且分布無規律的矩陣（如多數元素為0的系數矩陣），采用三元組表存儲：

• 每個非零元素用 (行標, 列標, 值) 表示；
• 再存儲矩陣的行數、列數和非零元素個數。

示例：矩陣 [[1,0,0],[0,2,0],[0,0,3]] 的三元組表為：
((0,0,1), (1,1,2), (2,2,3))，行數3，列數3，非零元素數3。

🌐 五，廣義表

（一）廣義表的定義

廣義表（Lists）是線性表的擴展，允許元素既可以是單個數據（原子），也可以是另一個廣義表（子表）。

• 記為 LS = (a?, a?, ..., a?)，n為長度，n=0時稱為空表。
• 示例：
  • A = ()：空表，長度0；
  • B = (e)：長度1，元素為原子e；
  • C = (a, (b, c, d))：長度2，第一個元素為原子a，第二個元素為子表 (b,c,d)；
  • D = (A, B, C)：長度3，元素均為子表。

廣義表的深度是指嵌套的最大層數（空表深度為1），例如C的深度為2，D的深度為3。

（二）廣義表的存儲結構

由于元素可能是原子或子表，需用鏈式存儲，每個節點包含標志位（區分原子或子表）：

typedef enum {ATOM, LIST} ElemTag;  // ATOM=0表示原子，LIST=1表示子表
typedef struct GLNode {ElemTag tag;  // 標志位union {       // 共用體，原子或子表二選一char atom;                // 原子值（若tag=ATOM）struct GLNode *hp;        // 子表頭指針（若tag=LIST）};struct GLNode *tp;  // 指向下一個元素（同層下一個節點）
} GLNode, *GList;

示例：廣義表 C = (a, (b, c)) 的存儲結構：

• 頭節點 tag=LIST，hp 指向第一個元素（原子a）；
• 原子a的節點 tag=ATOM，atom=‘a’，tp 指向第二個元素（子表）；
• 子表節點 tag=LIST，hp 指向子表 (b,c) 的頭節點，tp=NULL（無下一個元素）。

🛠? 案例分析與實現

案例：文本查找與替換工具

功能需求：實現一個簡單的文本處理工具，支持在長文本中查找指定單詞，并將所有匹配的單詞替換為新單詞（如將“數據結構”替換為“Data Structure”）。

核心思路

1. 數據存儲：使用堆分配串存儲主文本（文章）、模式串（待查找單詞）和替換串（新單詞），支持動態調整長度；
2. 查找邏輯：基于BF模式匹配算法，遍歷主文本定位所有模式串的起始位置；
3. 替換邏輯：對每個匹配位置，先刪除原模式串，再插入替換串，更新主文本長度和內容。

完整代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 堆分配串定義
typedef struct {char *ch;      // 動態字符數組int length;    // 串實際長度
} HString;// 初始化串
void InitString(HString *s) {s->ch = NULL;s->length = 0;
}// 串賦值（將字符串常量復制到串中）
void StrAssign(HString *s, const char *chars) {if (s->ch) free(s->ch);  // 釋放原有空間int len = strlen(chars);if (len == 0) {s->ch = NULL;s->length = 0;} else {s->ch = (char*)malloc((len + 1) * sizeof(char));  // +1預留結束符strcpy(s->ch, chars);s->length = len;}
}// BF模式匹配算法（返回模式串在主串中從pos開始的首次位置，1-based）
int IndexBF(HString S, HString T, int pos) {if (pos < 1 || pos > S.length || T.length == 0) return 0;  // 參數合法性檢查int i = pos - 1;  // 主串下標（0-based）int j = 0;        // 模式串下標（0-based）while (i < S.length && j < T.length) {if (S.ch[i] == T.ch[j]) {i++;  // 匹配成功，繼續比較下一個字符j++;} else {i = i - j + 1;  // 主串回溯到上一次匹配的下一位j = 0;          // 模式串重置到起點}}if (j == T.length) return i - T.length + 1;  // 匹配成功，返回1-based起始位置else return 0;  // 匹配失敗
}// 替換主串中所有非重疊的模式串為替換串
void StrReplace(HString *S, HString T, HString V) {if (T.length == 0) return;  // 模式串為空，無需替換int pos = 1;  // 從主串第1個字符開始查找while (pos <= S->length - T.length + 1) {int i = IndexBF(*S, T, pos);  // 查找模式串位置if (i == 0) break;  // 未找到更多匹配，退出循環// 步驟1：刪除主串中從i開始的模式串int delete_len = T.length;for (int j = i + delete_len - 1; j < S->length; j++) {S->ch[j - delete_len] = S->ch[j];  // 元素左移覆蓋}S->length -= delete_len;  // 更新主串長度// 步驟2：在刪除位置插入替換串int insert_len = V.length;if (insert_len > 0) {// 重新分配內存以容納插入的字符S->ch = (char*)realloc(S->ch, (S->length + insert_len + 1) * sizeof(char));// 元素右移騰出插入空間for (int j = S->length - 1; j >= i - 1; j--) {S->ch[j + insert_len] = S->ch[j];}// 插入替換串內容for (int j = 0; j < insert_len; j++) {S->ch[i - 1 + j] = V.ch[j];}S->length += insert_len;  // 更新主串長度}// 下一次查找從替換后的下一個位置開始pos = i + insert_len;}
}int main() {HString text, oldWord, newWord;InitString(&text);InitString(&oldWord);InitString(&newWord);// 初始化文本、待替換單詞和新單詞StrAssign(&text, "數據結構是計算機科學的核心，學好數據結構很重要！");StrAssign(&oldWord, "數據結構");StrAssign(&newWord, "Data Structure");// 執行替換操作StrReplace(&text, oldWord, newWord);// 輸出結果printf("替換后的文本：%s\n", text.ch); // 預期輸出："Data Structure是計算機科學的核心，學好Data Structure很重要！"// 釋放內存free(text.ch);free(oldWord.ch);free(newWord.ch);return 0;
}

代碼說明

• 存儲選擇：堆分配串解決了定長串的長度限制問題，適合處理未知長度的文本；
• 效率權衡：BF算法實現簡單，適合短文本或模式串場景；若處理長篇小說等大文本，可優化為KMP算法提升效率；
• 替換邏輯：通過“先刪除后插入”的方式實現替換，需注意內存重分配和字符移位的邊界處理。

📝 章結

串、數組和廣義表是線性表的擴展與變形，在數據處理中承擔著不同角色：

• 串作為字符的有序序列，是文本處理的基礎。其核心價值在于模式匹配算法——從樸素的BF算法到高效的KMP算法，優化的不僅是時間復雜度，更是對“避免重復比較”這一思想的體現。存儲結構的選擇（定長、堆分配、鏈式）需結合文本長度和操作頻率，例如堆分配串兼顧靈活性與訪問效率，適合多數文本場景。

• 數組通過多維下標實現結構化數據的存儲，其順序存儲特性確保了高效的隨機訪問。特殊矩陣的壓縮存儲（如對稱矩陣、稀疏矩陣）則展示了“按需存儲”的優化思想——通過減少冗余數據，顯著降低空間開銷，這在科學計算、圖像處理等領域至關重要。

• 廣義表打破了線性表的同質性限制，允許元素嵌套，是處理復雜層次數據的工具。其鏈式存儲結構靈活支持原子與子表的混合存儲，在Lisp等函數式語言、XML/JSON解析等場景中廣泛應用。

從本質上看，這些結構都是對“數據關系”的抽象：串強調字符的順序關系，數組強調多維索引關系，廣義表強調嵌套關系。理解它們的存儲規律和核心算法，不僅能解決具體問題，更能培養“根據數據特性選擇結構”的思維——這正是數據結構的核心素養。