數據結構進階 - 串、數組和廣義表
第四章 串（String）
4.1 串的基本概念
4.1.1 串的定義
- 串是受限的線性表：組成串的元素只能為字符
- 串的特點：
- 操作位置受限
- 元素類型受限（只能是字符）
- 是線性表的推廣和受限形式
4.1.2 串的基本操作
- 串比較
- 連接
- 求子串
- 模式匹配等
4.1.3 串的存儲方式
- 定長順序串
- 堆串
- 塊鏈串
4.2 模式匹配算法
4.2.1 BF算法（暴力匹配算法）
算法思想：逐個字符進行匹配，匹配失敗時回退到主串的下一個位置重新開始匹配。
int StrIndex(SString s, SString t) {int i, j;if (t.len == 0) return(0);i = 0; j = 0;while (i < s.len && j < t.len) {if (s.ch[i] == t.ch[j]) {i++; j++;} else {// 匹配失敗，i、j回退i = i - j + 1;j = 0;}}if (j == t.len) return i - j;else return -1;
}
時間復雜度分析：
- 最壞情況：S = ‘AAAAAAAAAAAAAAAAAAAAAAA’（長度為n），T = ‘AAAAAAAB’（長度為m）
- 時間復雜度：T(n) = O(n×m)
算法示例：
- 主串 s = “ababcabcacbab”
- 模式串 t = “abcac”
4.2.2 KMP算法
算法來由分析：
當匹配失敗時，不需要完全回退，而是利用已經匹配的信息，跳過一些不可能匹配成功的位置。
核心思想：
- 找到模式串T[0]~T[j-1]的最長相同前綴和后綴子串
- 當匹配失敗時，j指針移動到合適的位置，i指針不回退
字符串的前綴和后綴：
- 如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就稱B為A的前綴
- 例如："Harry"的前綴包括 {“H”, “Ha”, “Har”, “Harr”}
- 同理"Potter"的后綴包括 {“otter”, “tter”, “ter”, “er”, “r”}
- 注意：字符串本身并不是自己的前綴或后綴
next數組定義：
next[j]：模式串[0~j-1]的最長相同前綴和后綴的長度
next數組計算示例：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 模式串 | a | b | a | a | b | c | a | c |
| next[j] | -1 | 0 | 0 | 1 | 1 | 2 | 0 | 1 |
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 模式串 | A | B | C | D | A | B | D |
| next[j] | -1 | 0 | 0 | 0 | 0 | 1 | 2 |
KMP算法實現：
while (i < s.len && j < t.len) {if (j == -1 || s[i] == t[j]) {i++; j++;} else {// i不需要回溯了j = next[j]; // j回到指定位置}
}
if (j == t.len) return i - j;
else return -1;
時間復雜度：T(n) = O(n+m)
4.2.3 KMP算法的改進（修正）
問題分析：
在某些情況下，KMP算法仍存在不必要的比較。例如：
- S：AAABAAAAAAABA
- T：AAAABA
- next[]：-1 0 1 2 3 0
當s(3)、t(2)匹配失敗后，又從s(3)、t(1)開始匹配，匹配再次失敗后從s(3)、t(0)開始匹配，依舊匹配失敗。這個過程存在沒有必要的回退，因為t[3]=t[2]=t[1]=t[0]=‘A’，都注定了匹配會失敗。
nextval數組定義：
nextval[j]中存放模式串t中，t[j]位置前最長相同前綴和后綴且滿足后續字符不同的子串長度。
next→nextval轉換規則：
- nextval[0] = -1
- 當t[j] = t[next[j]]時：nextval[j] = nextval[next[j]]
- 當t[j] ≠ t[next[j]]時：nextval[j] = next[j]
nextval數組計算示例：
| j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 模式串 | a | a | b | a | a | b |
| next | -1 | 0 | 1 | 0 | 1 | 2 |
| nextval | -1 | -1 | 1 | -1 | -1 | 1 |
4.3 課堂練習題解析
題目1：采用KMP算法在某主串S中進行模式串t='ababaaababaa’的模式匹配，next[]數組為（）（下標從0開始）
答案：-1 0 0 1 2 3 1 1 2 3 4 5
題目2：采用KMP算法進行模式匹配，模式串t='ababaababaa’的next[]數組為（）
答案：-1 0 0 1 2 3 1 1 2 3 2 3
第五章 數組和廣義表
5.1 數組
5.1.1 數組的基本概念
- 數組定義：數組可以看成是一般線性表的擴充
- 一維數組即為線性表
- 二維數組可以定義為"其數據元素為一維數組(線性表)"的線性表
- 多維數組依次類推
5.1.2 數組的基本操作
- 獲取指定位置元素
- 修改指定位置元素
5.1.3 數組的存儲方式
- 順序存儲：可按行或按列存儲
5.1.4 數組元素地址計算
一維數組：
- 數組A[1…n]，每個元素占k個字節
Loc(A[i]) = Loc(A[1]) + (i-1) × k
二維數組：
- 數組A[1…m][1…n]，每個元素占k個字節
- 按行存儲：
Loc(A[i][j]) = Loc(A[1][1]) + ((i-1) × n + j-1) × k - 按列存儲：
Loc(A[i][j]) = Loc(A[1][1]) + ((j-1) × m + i-1) × k
三維數組：
- 數組A[1…m][1…n][1…r]，每個元素占k個字節
- 按行-列-縱存儲：
Loc(A[i][j][k]) = Loc(A[1][1][1]) + ((i-1) × n × r + (j-1) × r + k-1) × k
5.1.5 練習題解析
題目1：設二維數組A[6][10]，每個數組元素占4個存儲單元，若按行優先順序存放的數組元素A[3][5]的存儲地址是1000，則A[0][0]的存儲地址為（）。
解答：
- A[3][5]在數組中的位置：第3行第5列（從0開始）
- 從A[0][0]到A[3][5]共有：3×10 + 5 = 35個元素
- 地址差：35 × 4 = 140
- A[0][0]的地址 = 1000 - 140 = 860
答案：860
5.2 特殊矩陣的壓縮存儲
5.2.1 基本概念
特殊矩陣：元素分布有規律或非零元素很多(2/3以上)的矩陣
- 上三角矩陣
- 下三角矩陣
- 對稱矩陣
- 帶狀矩陣
- 稀疏矩陣
壓縮原則：
- 值相同的元素且分布有規律的元素只分配一個空間
- 零元素不分配空間
5.2.2 對稱矩陣
對于n×n的對稱矩陣，只需存儲下三角部分（含對角線）：
- 存儲空間：n(n+1)/2個單元
- 地址計算（下標從1開始）：
- 當i ≥ j時：
k = i(i-1)/2 + j-1 - 當i < j時：
k = j(j-1)/2 + i-1
- 當i ≥ j時：
5.2.3 帶狀矩陣
對角帶狀矩陣（d為半個帶狀寬度）：
- 非零元素總個數：(2d+1)×n - (1+d)×d
- 地址計算：需要根據具體的帶狀寬度來確定
5.2.4 稀疏矩陣
三元組表示法：
typedef struct {int row, col; // 行號、列號int value; // 元素值
} Triple;
快速轉置算法：
- 統計每列非零元素個數：num[]
- 計算每列第一個非零元素在轉置矩陣中的位置：pos[]
- 按行掃描原矩陣，依次放置元素
算法示例：
- 原矩陣的三元組按行序排列
- 轉置后按列序排列
- 利用num[]和pos[]數組實現一次定位
5.3 廣義表
5.3.1 廣義表的定義
廣義表：特殊的線性表，其特殊性在于廣義表中的元素既可以是單個元素，還可以是一個廣義表。
5.3.2 廣義表的基本概念
- 表頭：廣義表中的第一個元素
- 表尾：除了第一個元素外，其余元素構成的廣義表
5.3.3 廣義表的存儲結構
- 頭尾鏈表存儲
- 同層結點鏈存儲
5.3.4 練習題解析
題目1：廣義表((a,b,c,d))的表尾是（）。
答案：( )（空表）
題目2：已知廣義表LS=((a,b,c),(d,e,f))，運用head和tail函數取出LS中原子e的運算是（）。
答案：head(tail(head(tail(LS))))
分析：
- tail(LS) = ((d,e,f))
- head(tail(LS)) = (d,e,f)
- tail(head(tail(LS))) = (e,f)
- head(tail(head(tail(LS)))) = e
總結
重要知識點回顧
-
串的模式匹配
- BF算法：簡單但效率低，時間復雜度O(n×m)
- KMP算法：利用next數組避免回退，時間復雜度O(n+m)
- KMP改進：利用nextval數組進一步優化
-
數組地址計算
- 掌握一維、二維、三維數組的地址計算公式
- 注意下標起始位置（0或1）
-
特殊矩陣壓縮存儲
- 對稱矩陣：存儲下三角，地址映射關系
- 帶狀矩陣：根據帶寬確定存儲方式
- 稀疏矩陣：三元組表示法，轉置算法
-
廣義表
- 理解表頭、表尾概念
- 掌握head、tail函數的使用
考試重點
- next數組和nextval數組的計算
- 各種矩陣的地址計算公式
- 稀疏矩陣的轉置算法
- 廣義表的基本操作
)
