本文共 3304 字，大约阅读时间需要 11 分钟。

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

数据结构与算法_师大完整教程目录（更有python、go、pytorch、tensorflow、爬虫、人工智能教学等着你）：

一、字符串

1.1 字符串的基本概念

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

1.2 字符串类的定义

1. 略

1.3 字符串的存储及其实现

1. 顺序存储字符串：顺序串
2. 链式存储字符串：链式串

1.3.1 顺序串

1. 顺序串常用操作：

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

1.3.1.1 顺序串的存储结构

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

1.3.2 链式串

1. 链式串的常用操作：

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

1.3.2.1 链式串的存储结构

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

二、字符串的模式匹配

2.1 朴素的模式匹配算法

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

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

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

2.2.1 next数组求解

1. \(next\) 数组求解步骤：

   1. 第 \(1\) 位：\(-1\)
   2. 第 \(2\) 位：\(0\)
   3. 第 \(n\) 位：比较前 \(n-1\) 位，得出最长前后缀长度为 \(k\)，填 \(k\)

三、数组 （大纲未规定）

3.1 数组和数组元素

1. 略

3.2 数组类的定义

1. 略

3.3 数组的顺序存储及实现

1. 略

四、特殊矩阵

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

4.1 对称矩阵的压缩存储

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

4.2 三角矩阵的压缩存储

4.2.1 下三角矩阵

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

4.2.2 上三角矩阵

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

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

4.3 带状矩阵的压缩存储

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

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

五、稀疏矩阵

5.1 稀疏矩阵类的定义

1. 略

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

1. 稀疏矩阵的顺序存储方法：三元组表示法、带辅助行向量的二元组表示法、伪地址表示法

2. 三元组表示法：\((i,j,value)\)，其中 \(i\) 表示行，\(j\) 表示列，\(value\) 表示值

3. 注：三元组矩阵中第一行一般体现稀疏矩阵的行数、列数和所含非零元素的总个数

4. 稀疏矩阵顺序存储常用操作：

   1. 产生稀疏矩阵的三元组表示
   2. 稀疏矩阵三元组表示下转置运算的实现

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

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

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

1. 稀疏矩阵的链式存储方法：十字链表表示法、带行指针向量的单链表表示法、行_列表示法

2. 非零元素结点的结构中有 \(5\) 个域：行域（\(row\)）、列域（\(col\)）、数据的值域（\(val\)）、指向同一列下一个非零元素的指针域（\(down\)）、指向同一行下一个非零元素的指针域（\(right\)）

3. 表头结点的结构中有 \(5\) 个域：行域（\(row\)）默认为 \(0\)、列域（\(col\)）默认为 \(0\)、指向下一个表头的指针域（\(next\)）、指向同一列下一个非零元素的指针域（\(down\)）、指向同一行下一个非零元素的指针域（\(right\)）

4. 稀疏矩阵的链式存储常用操作：

   1. 创建稀疏矩阵的十字链表表示
   2. 稀疏矩阵十字链表的查找算法

5. 稀疏矩阵的十字链表存储方法如下图所示：

6. 图稀疏矩阵的十字链表表示法：

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]; // 指针数组，每个元素指向一个表头结点

六、算法设计题

1. 略

七、错题集

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