串（字符串）和數組是數據結構中的兩個重要分支，它們在程序設計中承擔著不同但互補的角色。串專門處理字符數據，而數組則提供了多維數據的存儲和訪問機制。本文將深入探討這兩種數據結構的理論基礎、實現方法和核心算法。
文章目錄
- 1.串的基本概念
- 串的抽象數據類型定義
- 串的核心特性
- 2.串的存儲實現
- 順序存儲結構
- 鏈式存儲結構
- 索引存儲結構
- 帶長度的索引表
- 帶末指針的索引表
- 帶特征位的索引表
- 3.串的核心算法實現
- 串連接運算
- 求子串運算
- 4.模式匹配算法
- 簡單模式匹配算法
- 鏈式存儲的模式匹配
- KMP算法優化
- 5.數組的抽象數據類型
- 多維數組的地址計算
- 6.特殊矩陣的壓縮存儲
- 稀疏矩陣
- 稀疏矩陣轉置
- 快速轉置算法
- 7.存儲效率對比
- 不同存儲方式的空間復雜度
- 算法效率分析
- 8.應用場景與選擇策略
- 串的應用領域
- 數組的應用領域
- 選擇指導原則
- 9.總結
1.串的基本概念
串是由零個或多個字符組成的有限序列，是一種特殊的線性表，其數據元素僅由字符構成。串在文本處理、編譯器設計、生物信息學等領域有著廣泛應用。
串的抽象數據類型定義
ADT String {數據對象: D = {c? | c? ∈ CharacterSet, i = 1,2,...,n, n ≥ 0}數據關系: R = {<c?,c???> | c?,c??? ∈ D, i = 1,2,...,n-1}操作集合:StrAssign(&T, chars) // 串賦值StrCopy(&T, S) // 串復制 StrEmpty(S) // 判空StrCmp(S, T) // 串比較StrLength(S) // 求串長StrCat(&T, S) // 串連接SubStr(&Sub, S, pos, len) // 求子串StrIndex(S, T, pos) // 子串定位Replace(&S, T, V) // 串替換StrInsert(&S, pos, T) // 串插入StrDelete(&S, pos, len) // 串刪除
} ADT String
這個定義包含了串的11種基本運算，涵蓋了字符串處理的所有核心操作。
串的核心特性
- 有限性：串的長度是有限的
- 有序性：字符在串中的位置是有意義的
- 同質性：所有元素都是字符類型
- 可為空：空串（長度為0）是有效的串
2.串的存儲實現
順序存儲結構
順序存儲是串最常用的存儲方式，將字符依次存放在連續的存儲單元中。
#define MAXSIZE 100typedef struct {char ch[MAXSIZE]; // 存放串值的字符數組int length; // 串的實際長度
} SeqString;
優點：
- 隨機訪問效率高，時間復雜度O(1)
- 存儲密度高，沒有額外指針開銷
- 實現簡單，便于理解和調試
缺點：
- 需要預先分配固定大小的存儲空間
- 插入和刪除操作可能需要移動大量字符
- 存在空間浪費或溢出風險
鏈式存儲結構
鏈式存儲將每個字符存儲在單獨的節點中，通過指針連接。
typedef struct linknode {char data; // 字符數據域struct linknode *next; // 指向下一個字符的指針
} LinkString;
特點分析：
- 存儲靈活：動態分配，無固定長度限制
- 插入刪除高效：在已知位置插入刪除為O(1)
- 空間開銷大：每個字符需要額外的指針空間
- 訪問效率低：隨機訪問需要O(n)時間
索引存儲結構
索引存儲適用于管理多個串的場景，通過索引表記錄串的元數據。
帶長度的索引表
#define MAXSIZE 1024typedef struct {char name[MAXSIZE]; // 串名稱int length; // 串長度char *start_addr; // 串值起始地址
} LengthNode;
帶末指針的索引表
typedef struct {char name[MAXSIZE];char *start_addr, *end_addr; // 起始和結束地址
} EndNode;
帶特征位的索引表
typedef struct {char name[MAXSIZE];int tag; // 特征位：0-短串直接存儲，1-長串存儲地址union {char *start_addr; // 長串地址char value[4]; // 短串直接存儲} uval;
} TagNode;
這種設計優化了短串的存儲效率，避免了指針的額外開銷。
3.串的核心算法實現
串連接運算
串連接是將兩個串依次拼接成一個新串的操作。
SeqString *StrCat(SeqString *s, SeqString *t) {SeqString *r = (SeqString*)malloc(sizeof(SeqString));// 檢查長度溢出if (s->length + t->length >= MAXSIZE) {printf("串長度溢出\n");free(r);return NULL;}int i;// 復制第一個串for (i = 0; i < s->length; i++) {r->ch[i] = s->ch[i];}// 連接第二個串for (i = 0; i < t->length; i++) {r->ch[s->length + i] = t->ch[i];}r->ch[s->length + t->length] = '\0'; // 添加字符串結束符r->length = s->length + t->length;return r;
}
時間復雜度：O(m + n)，其中m、n分別為兩個串的長度
空間復雜度：O(m + n)，需要分配新的存儲空間
求子串運算
從主串中提取指定位置和長度的子串。
SeqString *SubStr(SeqString *s, int pos, int len) {// 參數合法性檢查if (pos < 0 || pos >= s->length || len < 0 || pos + len > s->length) {printf("參數超出有效范圍\n");return NULL;}SeqString *t = (SeqString*)malloc(sizeof(SeqString));if (t == NULL) {printf("內存分配失敗\n");return NULL;}// 提取子串for (int k = 0; k < len; k++) {t->ch[k] = s->ch[pos + k];}t->ch[len] = '\0';t->length = len;return t;
}
關鍵點：
- 位置索引從0開始
- 需要嚴格檢查邊界條件
- 返回的是新分配的串對象
4.模式匹配算法
模式匹配是在主串中查找模式串位置的核心算法，是串處理的重點內容。
簡單模式匹配算法
也稱為樸素算法或暴力匹配算法。
int SimpleIndex(SeqString *s, SeqString *t) {int i = 0, j = 0;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; // 匹配成功，返回起始位置} else {return -1; // 匹配失敗}
}
性能分析：
- 最好情況：O(n)，第一次就匹配成功
- 最壞情況：O(mn)，每次都在最后一個字符失配
- 平均情況：接近O(n)
鏈式存儲的模式匹配
LinkString *LinkIndex(LinkString *s, LinkString *t) {LinkString *first = s; // 記錄主串起始比較位置LinkString *sptr = first; // 主串當前比較位置LinkString *tptr = t; // 模式串當前比較位置while (sptr && tptr) {if (sptr->data == tptr->data) {sptr = sptr->next; // 字符匹配，繼續比較tptr = tptr->next;} else {first = first->next; // 回溯到下一個起始位置sptr = first;tptr = t;}}return (tptr == NULL) ? first : NULL;
}
KMP算法優化
KMP算法通過預處理模式串，避免了不必要的回溯，顯著提高了匹配效率。
// 計算next數組
void GetNext(SeqString *t, int next[]) {int i = 0, j = -1;next[0] = -1;while (i < t->length - 1) {if (j == -1 || t->ch[i] == t->ch[j]) {i++;j++;next[i] = j;} else {j = next[j]; // 利用已計算的next值}}
}// KMP模式匹配
int KMPIndex(SeqString *s, SeqString *t) {int next[t->length];GetNext(t, next);int i = 0, j = 0;while (i < s->length && j < t->length) {if (j == -1 || s->ch[i] == t->ch[j]) {i++;j++;} else {j = next[j]; // 模式串智能移動}}return (j == t->length) ? i - t->length : -1;
}
KMP算法優勢：
- 時間復雜度：O(m + n)，其中m為主串長度，n為模式串長度
- 空間復雜度：O(n)，用于存儲next數組
- 無回溯：主串指針不回退，提高了效率
5.數組的抽象數據類型
數組是相同數據類型元素的集合，支持多維索引訪問。
ADT Array {數據對象: D = {a????...?? | 0 ≤ i? < bound?, j = 1,2,...,n}數據關系: R = {相鄰關系由下標序偶確定}操作集合:InitArray(&A, n, bound1, ..., boundn) // 構造數組DestroyArray(&A) // 銷毀數組 Value(A, &e, index1, ..., indexn) // 取元素Assign(&A, e, index1, ..., indexn) // 賦值元素
} ADT Array
多維數組的地址計算
以二維數組為例，假設數組A[m][n]：
行優先存儲：
Address(A[i][j]) = BaseAddress + (i × n + j) × sizeof(ElementType)
列優先存儲：
Address(A[i][j]) = BaseAddress + (j × m + i) × sizeof(ElementType)
6.特殊矩陣的壓縮存儲
稀疏矩陣
稀疏矩陣是大部分元素為零的矩陣，使用三元組表示法可以大大節省存儲空間。
#define MAXSIZE 100typedef struct {int row, col; // 行號和列號int value; // 元素值
} Triple;typedef struct {int rows, cols, nums; // 行數、列數、非零元個數Triple data[MAXSIZE]; // 三元組數組
} SparseMatrix;
稀疏矩陣轉置
SparseMatrix *TransposeMatrix(SparseMatrix *a) {SparseMatrix *b = (SparseMatrix*)malloc(sizeof(SparseMatrix));b->rows = a->cols;b->cols = a->rows; b->nums = a->nums;if (a->nums == 0) {return b;}int currentB = 0;// 按列號順序轉置for (int col = 0; col < a->cols; col++) {for (int p = 0; p < a->nums; p++) {if (a->data[p].col == col) {b->data[currentB].row = a->data[p].col;b->data[currentB].col = a->data[p].row;b->data[currentB].value = a->data[p].value;currentB++;}}}return b;
}
算法分析：
- 時間復雜度：O(n × t)，其中n為原矩陣列數，t為非零元個數
- 空間復雜度：O(t)，與非零元個數成正比
- 適用性：當非零元個數遠小于矩陣總元素數時，壓縮效果顯著
快速轉置算法
通過預先計算每列的元素個數和起始位置，實現O(n + t)的轉置。
SparseMatrix *FastTranspose(SparseMatrix *a) {SparseMatrix *b = (SparseMatrix*)malloc(sizeof(SparseMatrix));int colSize[a->cols]; // 每列非零元個數int colStart[a->cols]; // 每列在轉置矩陣中的起始位置b->rows = a->cols;b->cols = a->rows;b->nums = a->nums;if (a->nums == 0) return b;// 統計每列非零元個數for (int col = 0; col < a->cols; col++) {colSize[col] = 0;}for (int t = 0; t < a->nums; t++) {colSize[a->data[t].col]++;}// 計算每列起始位置colStart[0] = 0;for (int col = 1; col < a->cols; col++) {colStart[col] = colStart[col-1] + colSize[col-1];}// 執行轉置for (int p = 0; p < a->nums; p++) {int col = a->data[p].col;int q = colStart[col];b->data[q].row = a->data[p].col;b->data[q].col = a->data[p].row;b->data[q].value = a->data[p].value;colStart[col]++;}return b;
}
7.存儲效率對比
不同存儲方式的空間復雜度
| 存儲方式 | 空間復雜度 | 適用場景 |
|---|---|---|
| 完全存儲 | O(m×n) | 密集矩陣 |
| 三元組 | O(t) | 稀疏矩陣(t<<m×n) |
| 十字鏈表 | O(t) | 動態稀疏矩陣 |
| 壓縮存儲 | O(n) | 對角、三角矩陣 |
算法效率分析
| 操作 | 完全存儲 | 三元組存儲 |
|---|---|---|
| 隨機訪問 | O(1) | O(t) |
| 矩陣轉置 | O(m×n) | O(n×t) |
| 矩陣加法 | O(m×n) | O(t1+t2) |
| 矩陣乘法 | O(m×n×k) | O(t1×t2×k) |
8.應用場景與選擇策略
串的應用領域
- 文本處理：編輯器、搜索引擎
- 編譯器：詞法分析、語法分析
- 生物信息學：DNA序列分析
- 網絡安全：模式匹配、入侵檢測
數組的應用領域
- 科學計算：數值分析、圖像處理
- 圖形學：矩陣變換、3D渲染
- 機器學習：特征矩陣、權重存儲
- 數據庫：索引結構、關系存儲
選擇指導原則
串存儲選擇：
- 順序存儲：長度相對固定，需要高效隨機訪問
- 鏈式存儲：長度變化頻繁，插入刪除操作多
- 索引存儲：管理大量不同長度的串
數組存儲選擇：
- 完全存儲：元素密集，需要頻繁隨機訪問
- 壓縮存儲：具有特殊模式（對稱、三角等）
- 稀疏存儲：大部分元素為零或默認值
9.總結
串和數組作為基礎數據結構，各自具有獨特的特點和應用價值：
串的核心價值：
- 專門處理字符數據，支持豐富的文本操作
- KMP等高效模式匹配算法在文本處理中不可或缺
- 為編譯器、搜索引擎等系統提供基礎支撐
數組的核心價值：
- 提供多維數據的統一存儲和訪問機制
- 壓縮存儲技術大幅提高空間效率
- 為科學計算、圖形處理等領域提供基礎設施
理解這兩種數據結構的設計思想和實現技巧，不僅有助于提高程序設計能力，更為學習更復雜的數據結構和算法奠定了堅實基礎。在實際應用中，應根據具體的數據特征和操作需求，選擇合適的存儲方式和算法實現。
