数据结构--串、数组、广义表

串

定义

也叫字符串

案例引用

串的类型定义以及存储结构

抽象类型定义

存储结构(顺序表较为常用)

顺序存储结构

为了方便一些操作，通常串的数组的第一个位置不放元素，而是从ch【1】开始存放元素

链式存储结构

如果一个结点的数据域只放一个字符，那么会导致存储密度异常的底，解决这个问题：在数据域放更多的字符数据

上面的结构体定义结点结构，下面定义链表结构

可以得知，对于好多功能的链式表示都是定义两个结构：一个是结点、一个是链表自己
定义链表时：先定义第二个结构体的对象，创建出链表，如果要创建新的结点，那么要用到第一个结构体，进行插入即可

串的模式匹配算法（查找主串中是否有某个字串）

BF算法

如果匹配失败，那么需要对两个串的下标进行回溯，从而重新比较下一组

对于主串，先回溯到原始位置：i=i-(j-1)
因为对于串的第一个下标都是1，所以，j移动的格数是j-1，而i与j同步移动，所以，回溯到原始位置是i-(j-1)
之后，因为要进行下一组比较，所以，i回到原始位置之后，还需要后移一位，所以i=i-(j-1)+1

对于字串，直接回到第一个位置即可：j=1

由于第一个位置下标为1，方便了这里字串位置的计算，直接i-T.length即可

while循换条件：当主串的下标或者字串的下标有一个出界，那就代表匹配结束，最后要么匹配成功（j>=T.length）要么匹配失败，循环继续的条件是二者都没有出界，一旦有一个出界，那么结果为假，那么整体为假，&&一假则假

最好情况是o（1）
最坏情况是o（n*m）

综合平均：o（n*m）

KMP算法

设计思想

对字串的回溯进行了优化

当字串第j个元素失配，需要回溯到的下标位置，放入数组next【j】中

第一个元素失配，那么需要回溯到0，但是由于没有0位置，所以实际上的操作是i++，j仍然是1
之后的元素 想看是否满足其前面的首位子集是否相等，例如j=5时，前四个元素，先看1、4，二者相等，所以k-1=1，那么k=2，之后再看12、34，再看123、234，如果有更大的k，那么就取最大的k为最终值，注意不能全部包含 例如1234，这样是不可以的

如果这种情况也不满足，就是其他情况，next【j】=1

代码

kmp算法：

next【j】的算法：

对next【j】进行优化

按照上述标黄的语句，进行分析即可，开头两位一般是01 或者00
之后 如果回溯位置的元素与自身相同，那么val值与回溯位置的next值一样，如果不同 ，那么仍然是自己的next值
最后要注意标黄的第四种情况，也就是如果相同，每次要判断到第一位为止

总结来说 不同为自身，相同做替换，不同则停止，相同则到底

改进后的next【j】：

数组

类型

一维数组

二维数组

二维数组可以是非线性结构，也可以是特殊的线性结构

特殊的线性结构：将一行看成一个线性结构，该行的每个元素是一个列向量

分开定义，实际上就是对特殊的线性结构的代码解释

数组一旦定义，那么长度固定，所以一般只是做取元素和修改元素操作

抽象类型定义

顺序存储结构

因为内存单元只能是线性的，但是数组有多维，所以要想办法将多维关系映射到一维关系，接下来通过找指定元素的地址来反映这个关系，接下来就是解决这个问题

已知首元地址，求某个元素的地址（该元素第一个字节的地址）

一维数组

二维数组

也就是（第一维下标*列数+第二维下标）*一个元素所占字节数+首元地址=目标元素的地址
（本质上，是要求该元素的前面有几个元素，但是因为下标都是从0开始，所以根据数学关系，下标的数就是该元素之前有几个元素的多少）

三维数组

n维

案例

注意这里假设元素占用一个空间，先利用第一个条件求出列数，之后利用公式，求出答案

特殊矩阵的压缩存储

对称矩阵

只存上三角或者下三角，元素位置：i*（i-1）/2+j 这就是目标元素前面的元素个数

三角矩阵

带状矩阵

稀疏矩阵

顺序结构

链式结构

每行每列都有许多头指针，负责该行或者该列

每个非零元素都有一个结点，该结点包括行数、列数、值、指向下方的结点、指向右方的结点，

广义表

简介

这里注意 表尾：1.是除了第一个元素之外的所有元素组成的表
2.一定是一个表，所以求表尾第一步：先写一个括号，之后看去掉表头之后，剩什么就直接填入括号里

例如 第二题 表头是第一个元素，第一个元素就是一个空括号 所以就是：（）
表尾 先写一个空括号（），之后看除去表头之后 什么也没有了 就是空，所以 括号里什么都不写 所以还是（）

第三题 表头：a
表尾：先写一个空括号，之后，将除去表头的剩下的元素填入空表中，也就是（（b，c））

性质

基本运算

案例

循环m（模式串的长度）次，就可以将所有可能的情况都取得了