线性表之串、数组和广义表 - part06
串：内容受限的线性表。
数组和广义表：线性结构的推广，严格来说非线性了。
串
串的定义
1.定义：String。零个或多个任意字符组成的有限序列。
S=“a1a2…an” (n>=0)
2.案例引入
病毒感染检测
串的类型定义
串的存储结构
顺序串、链串
1.串的顺序存储结构（更常用，因为一般不需要插入删除）
2.串的链式存储结构
块链结构：同样要根据字符串结点类型来定义字符串块链结构类型。
串的模式匹配算法（BF、KMP）
目的：确定主串中所含子串（模式串）第一次出现的位置（定位）。
应用：搜索引擎、拼写检查、语言翻译、数据压缩
种类：BF算法（Brute-Force）、KMP算法（特点：速度快）
1.BF算法：也叫简单匹配算法，采用穷举的思路。
匹配失败i回溯：j移了多少格，i就回退多少格，然后+1得到下一个匹配位置。即i-(j-1)+1=i-j+2。
匹配成功返回位置：i-t.length
算法过程：
时间算法复杂度：
2.KMP算法
i不必回溯，j不必从头。j是因为模式串中可能存在部分匹配，即字符串尾部和头部会有相等情况，在上一次尾部已经匹配好了，则下一次就从这个(与尾部相等的头部)位置的下一位开始比较即可。
next函数求next值（代码不太懂…）
根据next值求nextval值：（nextval是改进的next //模式串重复的字符太多时可优化）
当前字符与其next指向的字符不同，则nextval取next值即可。
当前字符与其next指向的字符相同，则再继续朝着next方向走。当遇到下一个与当前的字符不同时，初始字符的nextval就取当前字符的next值。
数组
数组的定义
定义：按一定格式排列起来的具有相同类型的数据元素的集合。
声明格式：数据类型 变量名称[长度]
一维数组：线性结构。
二维数组：非线性结构—每个数据元素既在一个行表中又在一个列表中。
线性结构（定长线性表）—该线性表中每个数据元素也是一个定长线性表。
数组的类型定义
n维数组的前驱结点有n个，后继节点也是n个。
数组的存储结构
因为数组结构固定，一般不做插入删除操作。一般采用顺序存储结构来表示。
由于存储数据元素的内存单元地址是一维的，因此要解决多维关系映射到一维关系的问题。
数据元素单位是字节或叫空间，一个空间就指一个字节，一个字节为8位。
就是求当前这个元素前面有多少个元素，从而得到当前的位置。如果i、j从0开始，则他们前面的元素数等于当前位置i、j。
1.一维数组：a+i*L
2.二维数组m×n：a+[(i×n+j]×L
3.三维数组m×n×k：a+[i×m×n+i×n+i]×L
按页/行/列存放，页优先存储。
4.n维数组：
5.特殊矩阵的压缩存储
[1].对称矩阵
只存储下/上三角的数据元素，共占用n(n+1)/2元素空间。
a+[i(i-1)/2+j-1]×L //注意此处i、j从1开始
[2].三角矩阵
+1是因为有一个空间存储常数C。
上三角矩阵中，尾项为n+1-(i-1)=n-i+2。因为行数和行中元素数总和为n+1。
[3].对角矩阵
用二维数组存储：
[4].稀疏矩阵
顺序存储结构——三元组顺序表
用三元组（i, j, a）顺序表+矩阵行列数+非零数总数，来压缩存储。
缺点是找元素的话得从表头开始找。
链式存储结构——十字链表
每个非零结点包含五个数据内容，并且有行头结点与列头结点。
广义表
定义：
广义表（LS）中的每个ai可能是原子或者广义表，把表内元素的意义拓宽了。
性质：
广义表结构相当灵活，可以兼容线性表、数组、树和有向图等各种常用数据结构。
基本运算：
求表头GetHead(L)，可能为原子也可能为表。
求表尾GetTail(L)，一定是表。
因为广义表每个空间都不一定，不用顺序表（数组）存储，一般用链表存储。
案例分析
用模式匹配方法。