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

一、字符串
- 1.1 字符串的基本概念
- 1.2 字符串类的定义
- 1.3 字符串的存储及其实现
  - 1.3.1 顺序串
    - 1.3.1.1 顺序串的存储结构
  - 1.3.2 链式串
    - 1.3.2.1 链式串的存储结构
二、字符串的模式匹配
- 2.1 朴素的模式匹配算法
- 2.2 模式匹配算法（KMP算法）
  - 2.2.1 next数组求解
三、数组（大纲未规定）
- 3.1 数组和数组元素
- 3.2 数组类的定义
- 3.3 数组的顺序存储及实现
四、特殊矩阵
- 4.1 对称矩阵的压缩存储
- 4.2 三角矩阵的压缩存储
  - 4.2.1 下三角矩阵
  - 4.2.2 上三角矩阵
- 4.3 带状矩阵的压缩存储
五、稀疏矩阵
- 5.1 稀疏矩阵类的定义
- 5.2 稀疏矩阵的顺序存储及其实现
  - 5.2.1 稀疏矩阵顺序存储（三元组）存储结构
- 5.3 稀疏矩阵的链式存储及实现（大概率不考）
  - 5.3.1 稀疏矩阵链式存储（十字链法）存储结构
六、算法设计题
七、错题集

一、字符串

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\)）

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