数据结构--串、数组、广义表-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构--串、数组、广义表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

串

定义

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

也叫字符串

案例引用

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

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

抽象类型定义

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

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

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

顺序存储结构

数据结构--串、数组、广义表,数据结构
为了方便一些操作，通常串的数组的第一个位置不放元素，而是从ch【1】开始存放元素

链式存储结构

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

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

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

实际上第二个结构体定义只是对第一个结构体里面的第二个重命名（也就是*Queueptr）做一个拓展本质上还是第一个结构体即可第二个结构体均属于指向第一个结构体的指针类型没有第二个结构体的话在程序里仍然可以定义指向第一个结构体的指针

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

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算法

设计思想

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

对字串的回溯进行了优化

数据结构--串、数组、广义表,数据结构
对于第一个max 其中的条件是模式串中 j前面的字符串该字符串的前缀==后缀那么就可以得到k

当字串第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