数据结构第四章

4 串、数组和广义表

4.1 串的定义——几个术语

串(String)——由零个或多个任意字符组成的有限序列

子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串
- 真子串，不包含自身的所有子串
字符位置：字符在序列中的序号为该字符在串中的位置
子串位置：子串第一个字符在主串中的位置
空格串：由一个或多个空格组成的串，与空串不同
- 计算他们的长度时，要包括空格
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串才是相等的。

4.2 案例引入

“串的应用非常广泛，计算机上的非数值处理的对象大部分是字符串数据，例如：文字编辑、符号处理、各种信息处理系统等等。”

4.2.1 病毒感染检测

研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列（字符串的匹配）

4.3 串的类型定义、存储结构及运算

4.3.1 串的抽象类型定义

4.3.2 串的存储结构

4.3.2.1 串的顺序存储结构

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN+1];
    int length;
}SString;

顺序存储结构用的更多一些

4.3.2.2 串的链式存储结构

如果是普通的链式存储的话，虽然方便操作，但是存储密度较低，所以在这里，我们将多个字符存放在一个结点中，以克服其缺点。

我们称之为——块链结构

#define CHUNKSIZE BO 					//可由用户定义的块大小
typedef struct Chunk{
    char ch [CHUNKSIZE];
	struct Chunk *next;
})Chunk;
typedef struct{ 
	Chunk *head,*tail; 					//串的头指针和尾指针
	int length; 						//串的当前长度	
) LString;								//字符串的块链结构

4.3.3 串的模式匹配算法

算法目的：
- 确定主串中所含子串（模式串）第一次出现的位置（定位）
算法应用：
- 搜索引擎、拼写检查、语言翻译、数据压缩
算法种类：
- BF算法（暴力破解，朴素的、穷举的）
- KMP算法（速度快）

4.3.3.1 BF算法

匹配失败：
- $\large i=(i-j+1)+1=i-j+2$(i和j走的路程是一样的，i-j表示退回原位，而模式串是从下标1开始计算的，则要+1，这个时候才是真正退回了原位，再+1，就是原位的下一位了)
- $\large j=i$
匹配成功：
- $\large i=7$
- $\large j=5$
- 返回$\large i-t.length=3$
index(S,P,pos)
- 将主串的第pos个字符和模式串的第一个字符比较。
- 若相等，继续这个比较后续字符
- 若不等，就从主串的下一字符起，重新逐个比较
- 直到发现一个连续子串序列与模式串相等，返回值为S中与T匹配的子序列第一个字符的序号即匹配成功
- 否则匹配失败，返回0

int Index_BF(SString S,SString T){
    int i=1,j=1:
    while(i<=S.length && j<=T.length){
        if(s.ch[i]==t.ch[j]){++i.++j:}
        else {i=i-j+2;j=1;}
    }
    if (j>=T.length)return i-T.length			//返回匹配的第一个字符的下标
}

4.3.3.1.1 BF算法的时间复杂度

4.3.3.2 KMP算法

这种改进算法是由 Knuth 、 Morris 和 Pratt 同时设计实现的，因此简称 KMP 算法。

利用已经部分匹配的结果而加快模式串的滑动速度
且主串S的指针i不必回溯！可提速到O(N+M)！

为此，定义next[j]函数，表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置

第四个这里是1因为比较的时候不包括末尾元素但包括首元素

$\large k-1=最大公共前后缀的长度$

int Index_KMP(SString S,SString T,int pos){
    i=pos;j=l;
    while (i<S.length && j<T.length) {
        if 
            <j==o||s.ch[i]==T.ch[j]){ ++i;++j;}			//继续比较后继字符
        else 
            j=next[i]; 									//i不变，j后退
    }
	if 
        (j>T.length)return i-T.length;					//匹配成功
	else 
        return 0; 										//匹配失败
}

根据next值求nextval值的方法

4.4 数组

栈和队列是操作受限的线性表。串是内容受限的线性表。数组和广义表是对线性表的推广。

4.4.1 数组的类型定义

数组：按一定格式排列起来，具有相同类型的数据元素的集合
一维数组：若线性表中的数据元素为非结构的简单元素，一维数组
- 一维数组的逻辑结构：线性结构。定长的线性表。
- 声明格式：数据类型变量名称[长度]
  - 例：int num[5]={0,1,2,3,4};
二维数组：若一维数组中的数据元素又是一维数组结构，则称为二维数组。
- 二维数组的逻辑结构：
  - 非线性结构：每一个数据元素即在一个行表中，又在一个行列中
  - 线性结构：该线性表的每个数据元素也是一个定长的线性表
- 声明格式：数据类型变量名称[行数][列数];
  - 例：int num[5] [8]
n维数组：若n-1维数组中的元素又是一个一维数组结构，则称作n维数组。
结论：线性表结构是数组结构的一个特例，二数组结构又是线性表结构的拓展
数组特点：结构固定——定义后，维数和维界不再改变。
数组基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。

4.4.2 数组的顺序存储

二维数组可有两种存储方式
- 以行序为主序
- 以列序为主序

4.4.3 特殊矩阵的压缩存储

矩阵：一个由M*N个元素排成的m行n列的表。

$\large \begin{pmatrix}a_{11}&a_{12}&a_{13}&……&a_{1n}\a_{21}&a_{22}&a_{23}&……&a_{2n}\……&……&……&……&……&\a_{m1}&a_{m2}&a_{m3}&……&a_{mn}\end{pmatrix}$

矩阵的常规存储：

将矩阵描述为一个二维数组。

矩阵的常规存储的特点：

可以对其元素进行随机存取；
矩阵运算非常简单；存储密度为1

不适宜常规存储的矩阵：

值相同的元素很多且呈某种规律分布；
零元素多

矩阵的压缩存储:

为多个相同的非零元素只分配一个存储空间；
对零元素不分配空间
一些特殊的矩阵可以压缩，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵(矩阵中非零元素的个数较少，不到百分之五)等。
1. 对称矩阵：在N*N的矩阵中满足**$\large a_{ij}=a_{ji}$,存储方法，只存储上（或下）三角的数据元素，共占用N(N+1)/2**个元素空间
  
  下标k的求法为$(i-1)+(j-1)$,其中$a_{n-1}$前面行前面有$n-1$个数求和之后得到$\dfrac {n(n-1)}{2}$，列前面没有
2. 三角矩阵：对角线一下或以上的数据元素全为常数C
  1. 存储方法：重复元素c共享一个元素存储空间，共占用n（n+1)/2+1个元素空间：sa[1…n（n+1)/2+1]
3. 对角矩阵（带状矩阵）
  1. 特点：在n*n的方阵中，所有的非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为零，则称为对角矩阵，常见的有三对角矩阵，五对角矩阵，起对角矩阵。（几条对角线有数值就是几对角矩阵）
  2. 存储方法：以对角线的顺序存储
4. 稀疏矩阵
  1. 特点：设在m*n的矩阵中又t个非零元素，且t所占总体百分比小于五时称为稀疏矩阵
  2. 压缩存储原则：存各非零元素的值，行列位置和矩阵的行列数
    1. 例： $\large （i,j,a_{ij}）$
    2. 三元组顺序表又称有序的双下标
      1. 优点：便于进行依行顺序处理的矩阵运算。
      2. 缺点：不能随机存取，若按行号存取需要从头开始进行查找

4.5 广义表

广义表：又称列表Lists是n>=0个元素$a_0,a_1,……，a_{n-1}$的有限序列，其中没一个$a_i$或者是原子，或者是一个广义表
广义表通常记作：LS=$a_0,a_1,……，a_{n}$
- 其中LS为表名，n为表长，$a_i$为表的元素
- 通常用大写字母表示广义表，小写字母表示原子
- 表头：若LS非空，则其第一个元素$a_1$就是表头
  - 记作 $head（LS）=a_1$
- 表尾，除了表头的其他元素组成的表
  - 记作$tail（LS）=（a_2,……，a_{n}）$