数据结构进阶 - 串、数组和广义表
第四章 串（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数组的计算
- 各种矩阵的地址计算公式
- 稀疏矩阵的转置算法
- 广义表的基本操作
)
