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

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

第四章 串（String）

4.1 串的基本概念

4.1.1 串的定义

• 串是受限的线性表：组成串的元素只能为字符
• 串的特点：
  • 操作位置受限
  • 元素类型受限（只能是字符）
  • 是线性表的推广和受限形式

4.1.2 串的基本操作

• 串比较
• 连接
• 求子串
• 模式匹配等

4.1.3 串的存储方式

1. 定长顺序串
2. 堆串
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数组计算示例：

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数组计算示例：

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;

快速转置算法：

1. 统计每列非零元素个数：num[]
2. 计算每列第一个非零元素在转置矩阵中的位置：pos[]
3. 按行扫描原矩阵，依次放置元素

算法示例：

• 原矩阵的三元组按行序排列
• 转置后按列序排列
• 利用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

总结

重要知识点回顾

1. 串的模式匹配

   • BF算法：简单但效率低，时间复杂度O(n×m)
   • KMP算法：利用next数组避免回退，时间复杂度O(n+m)
   • KMP改进：利用nextval数组进一步优化

2. 数组地址计算

   • 掌握一维、二维、三维数组的地址计算公式
   • 注意下标起始位置（0或1）

3. 特殊矩阵压缩存储

   • 对称矩阵：存储下三角，地址映射关系
   • 带状矩阵：根据带宽确定存储方式
   • 稀疏矩阵：三元组表示法，转置算法

4. 广义表

   • 理解表头、表尾概念
   • 掌握head、tail函数的使用

考试重点

• next数组和nextval数组的计算
• 各种矩阵的地址计算公式
• 稀疏矩阵的转置算法
• 广义表的基本操作