第4章字符串、数组和特殊矩阵

一、字符串
二、字符串的模式匹配
- 2.1 朴素的模式匹配算法
- 2.2 模式匹配算法（KMP算法）
  - 2.2.1 next数组求解
三、数组（大纲未规定）
四、特殊矩阵
五、稀疏矩阵
六、算法设计题
七、错题集

一、字符串

1.1 字符串的基本概念

字符串：由 \(0\) 个或多个字符构成的有限序列，元素类型为字符型的特殊线性表

1.2 字符串类的定义

1.3 字符串的存储及其实现

顺序存储字符串：顺序串
链式存储字符串：链式串

1.3.1 顺序串

顺序串常用操作：
1. 顺序串的插入算法
2. 顺序串的删除算法
3. 顺序串的连接运算算法
4. 求顺序串子串的算法

1.3.1.1 顺序串的存储结构

#define MAXSIZE 100
typedef struct{
    char str[MAXSIZE];
    int length;
} seqstring;

1.3.2 链式串

链式串的常用操作：
1. 链式串的创建算法
2. 链式串的插入算法
3. 链式串的删除算法
4. 链式串的连接算法
5. 求链式串子串的算法

1.3.2.1 链式串的存储结构

typedef struct node{
    char data;
    struct node *next; // 用于存放字符串中的每个字符
} linkstrnode; // 用于指向本字符的下一个字符对应的结点的指针
typedef linkstrnode * linkstring;

二、字符串的模式匹配

2.1 朴素的模式匹配算法

注：暴力求解，逐个匹对，时间复杂度 \(O(nm)\)，\(n\) 是正文的长度，\(m\) 是模式串的长度

2.2 模式匹配算法（KMP算法）

算法步骤（大概率不考）
图kmp模式匹配流程：

2.2.1 next数组求解

\(next\) 数组求解步骤：
1. 第 \(1\) 位：\(-1\)
2. 第 \(2\) 位：\(0\)
3. 第 \(n\) 位：比较前 \(n-1\) 位，得出最长前后缀长度为 \(k\)，填 \(k\)

三、数组（大纲未规定）

3.1 数组和数组元素

3.2 数组类的定义

3.3 数组的顺序存储及实现

四、特殊矩阵

特殊矩阵：对称矩阵、三角矩阵、带状矩阵、稀疏矩阵

4.1 对称矩阵的压缩存储

对称矩阵元素位置的计算（\(L\) 为每个元素占用存储空间的长度）：

\[address(a_{ij}) =
\begin{cases}
& address(a_{00}) + [\frac{i*(i+1)}{2}+j]*L \qquad \text{当i>=j时}\\
& address(a_{00}) + [\frac{j*(j+1)}{2}+i]*L \qquad \text{当i<j时}
\end{cases}
\]

4.2 三角矩阵的压缩存储

4.2.1 下三角矩阵

下三角矩阵元素位置的计算（\(L\) 为每个元素占用存储空间的长度）：

\[address(a_{ij}) = address(a_{00}) + [\frac{i*(i+1)}{2}+j]*L \qquad \text{当i>=j时}\\
\]

4.2.2 上三角矩阵

上三角矩阵元素位置的计算（\(L\) 为每个元素占用存储空间的长度）：

\[\begin{aligned}
address(a_{ij})
&= address(a_{00}) + [(n+(n-1)+(n-2)+\cdots+(n-(i-1)))+j-i]*L \\
&= address(a_{00}) + [i*n-\frac{(i-1)*i}{2}+j-i]*L \qquad \text{当i<=j时}
\end{aligned}
\]

注：\((n+(n-1)+(n-2)+\cdots+(n-(i-1)))\) 表示 \(a_{ij}\) 前面的 \(i\) 行所有元素占用的空间；\(j-i\) 表示 \(a_{ij}\) 所在行的 \(a_{ij}\) 前面的元素所占用的空间

4.3 带状矩阵的压缩存储

带状矩阵：除第 \(1\) 行和最后一行外，每行都分配 \(2b+1\) 个元素的空间。但是把带状区域的所有元素存储于 \(((2b+1)*n-2b)*L\) 个存储单元中
带状矩阵元素位置的计算（\(L\) 为每个元素占用存储空间的长度）：

\[\begin{aligned}
address(a_{ij})
&= address(a_{00}) + ((i*(2b+1)-b)+(j-(i-b)))*L \\
&= address(a_{00}) + (i*(2b+1)+j-i)*L \qquad \text{当|i-j|<=b时}
\end{aligned}
\]

注：\((i*(2b+1)-b)\) 表示 \(a_{ij}\) 前面的 \(i\) 行所有元素占用的空间；\((j-(i-b)))\) 表示 \(a_{ij}\) 所在行的 \(a_{ij}\) 前面的元素所占用的空间

五、稀疏矩阵

5.1 稀疏矩阵类的定义

5.2 稀疏矩阵的顺序存储及其实现

稀疏矩阵的顺序存储方法：三元组表示法、带辅助行向量的二元组表示法、伪地址表示法
三元组表示法：\((i,j,value)\)，其中 \(i\) 表示行，\(j\) 表示列，\(value\) 表示值
注：三元组矩阵中第一行一般体现稀疏矩阵的行数、列数和所含非零元素的总个数
稀疏矩阵顺序存储常用操作：
1. 产生稀疏矩阵的三元组表示
2. 稀疏矩阵三元组表示下转置运算的实现

5.2.1 稀疏矩阵顺序存储（三元组）存储结构

typedef struct {
    int data[100][100]; // 存放稀疏矩阵的二维数组
    int m, n; // 分别存放稀疏矩阵的行数和列数
} matrix;
typedef int spmatrix[100][3]; // 存放三元组

5.3 稀疏矩阵的链式存储及实现（大概率不考）

稀疏矩阵的链式存储方法：十字链表表示法、带行指针向量的单链表表示法、行_列表示法
非零元素结点的结构中有 \(5\) 个域：行域（\(row\)）、列域（\(col\)）、数据的值域（\(val\)）、指向同一列下一个非零元素的指针域（\(down\)）、指向同一行下一个非零元素的指针域（\(right\)）
表头结点的结构中有 \(5\) 个域：行域（\(row\)）默认为 \(0\)、列域（\(col\)）默认为 \(0\)、指向下一个表头的指针域（\(next\)）、指向同一列下一个非零元素的指针域（\(down\)）、指向同一行下一个非零元素的指针域（\(right\)）
稀疏矩阵的链式存储常用操作：
1. 创建稀疏矩阵的十字链表表示
2. 稀疏矩阵十字链表的查找算法
稀疏矩阵的十字链表存储方法如下图所示：
图稀疏矩阵的十字链表表示法：

5.3.1 稀疏矩阵链式存储（十字链法）存储结构

typedef struct matrixnode {
    int row, col;
    struct matrixnode *right, *down;
    union {
        int val;
        struct matrixnode *next;
    } tag;
} matrixnode;
typedef matrixnode *spmatrix;
typedef spmatrix headspmatrix[100]; // 指针数组，每个元素指向一个表头结点

六、算法设计题

七、错题集

稀疏矩阵常用的压缩存储方法有三元组顺序存储和十字链表两种
设有一个 \(10×10\) 的对称矩阵 \(A\) 采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素\(a_{00}\) 的地址为 \(1\)，每个数据元素占 \(2\) 个字节，则 \(a_{65}\) 的地址为 \(53\)（元素 \(a_{00}\) 的地址为 \(1\)，不是 \(2\)）

本文链接：https://www.cnblogs.com/nickchen121/p/13767112.html

第4章字符串、数组和特殊矩阵