当前位置：首页 > news >正文

数据结构进阶 - 第四，五章串、数组和广义表

news 2025/6/27 7:58:03

数据结构进阶 - 串、数组和广义表

第四章串（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

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函数的使用