数据结构(4):串

只需要掌握小题，在考纲中占比不大

1 串的定义

1.1 基本定义

字符串

数据结构三要数：逻辑结构、存储结构、运算

子串必须是连续的！ 空格也是一个字符！每个空格字符占1B

1.2 串和线性表

2 串的基本操作

比值的操作！：就是按照字母表的顺序排列！

只有当两个串完全相同时，才相等！

字符串编码表ASCII

a存的是：【高四位】0110【低四位】0001【这样的二进制】

结果就是：

空格这个字符对应的二进制数是：00010000 占8bit位置

一个字母占一个字节1B ，一个字节等于8比特

软件的解码方式出现了错误！

3 串的存储结构

串是特殊的线性表

3.1 顺序存储

malloc申请的空间是一个堆区域，堆区的空间需要手动free

优点：随机存取 缺点：插入删除很困难

不同的方案数：

方案二的缺点：char[0]存储的还是一个字节的大小，占8个比特位，也就是说只能表示0到255之间的数字，则字符串的长度不能超过255.

方案四可以有所有的优点！

3.2 链式存储

一个字符1B(字节)，一个指针4B(字节)，这样造成的存储密度低的问题可以通过每个结点存储多个字符解决！！！如果最后一个结点存不满的话就可以用特殊的字符代替，这里式#也可以是/0这样子。

优缺点：增加删除元素很简单但是不具备随机存储的特性！

3.2.2 求子串

sub返回内容

3.2.3 比较两个串的大小

3.2.4 定位操作

一直找新的长度为3的子串！

4 字符串匹配！！！！！！

4.1 朴素模式匹配算法

朴素模式匹配算法可以看作是 暴力解决！  思想：找出所有长度为6的子串和模式串对比！

一共有n-m+1个子串，最多对比n-m+1个子串

4.1.1 用index

取子串、对比两个字符串的操作

4.1.2 不使用基本操作

i= i-j+2   i-j会使指针指向这个子串的前面一个位置 +2之后就指向了下一个子串的起始位置！

停止的条件：j>T.length reture i-j+1  或者 i-T.length

代码实现：

时间复杂度

暴力解法：把所有有可能的都遍历一遍！

前面的都匹配只有最后一个元素不匹配

4.2 KMP算法

利用模式串本身的信息 和已经扫描过的信息

当模式串进行失配的时候应该跳到什么样的位置。

所以只要是总结模式串的信息！！！！！

当模式串很短 但是主串很长的时候KMP就会后高效！

可以用数组表示这些信息：当在某个位置发生失配的时候会成什么局面！

在进行匹配之前要对模式串进行预处理得到next数组！！

不需要子串的那个指针变化，只变化模式串的

时间复杂度

手动的求next数组！！！

求next数组【一】

注意模式串的位序是从1开始的，0表示的是模式串第一个元素的前面一个元素！

1：next【1】=0 在任何的模式串中都一样！

2：next【2】=1在任何的模式串中都一样！

3：其他的画出分界线后 一步一步挪动然后填表！

使用next数组：

过程：

1：i=6 j=6 不匹配 j = next[6]=1 

2：i=6 j=1 不匹配 j = next[1] = 0

3：j=0时特殊处理》》j++,i++

4：i=7 j=1 匹配成功

5：i = 11 j=5 不匹配 j = next[5] = 2

6：i=11，j=2 匹配成功

自己算一下

KMP算法的进一步优化

对next数组进行优化！变成nextval数组！！！逻辑没有改变！

优化思路：

可以直接将next[3]=0 

因为此时i的位置一定不是a 所以一定和j=1不匹配，因此直接将指针置为0

next[5]=1  但并不是所有的next数组都可以进行优化！

思路：看失配的字符和所指的字符是否相等，如果相等的话没必要再回到这个位置了，直接回到这个位置的前一个位置即可！！！！

通过next数组求nextval数组

next[1]无脑写0

直接跳到后一步就可以！

nextval【j】 = nextval【next【j】】