王道数据结构第四章串_思维导图模板

王道数据结构第四章串

作者：旺柴.

0浏览2022-08-23 13:48:56

下载

使用模板已被用52次

第四章串

串

定义

串，即字符串(String)是由零个或多个字符组成的有限序列

术语:串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置

串[VS]线性表

串的数据对象限定为字符集

串的基本操作大多以“子串”为操作对象

基本操作

lndex(S,T)，定位操作,找到串T在主串S中的位置

StrCompare(S,T):比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S

其他...

字符集编码

字符集

英文字符―—ASClI字符集

中英文―—Unicode字符集

每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小

串的存储结构

顺序存储

静态数组

动态数组

malloc、free

链式存储

可让每个结点存多个字符，没有字符的位置用'#'或'\O'补足

王道教材采用静态数组

基于顺序存储实现基本操作

求子串: bool SubString(SString &Sub,SString S, int pos, int len)

串的比较:int StrCompare(SString S, SString T)

求串在主串中的位置:int Index(sString S, SString T)

串的模式匹配

朴素模式匹配算法

原理：暴力破解

算法思想

主串长度n,模式串长度m

将主串中所有长度为m的子串与模式串比对

找到第一个与模式串匹配的子串，并返回子串起始位置

若所有子串都不匹配，则返回0

最坏时间复杂度=O(nm)

KMP算法

不匹配的字符之前，一定是和模式串一致的

依赖于模式串，与主串没有关系

主要优点：主串指针不回溯

用一个next数组存储模式串指针

算法思想

根据模式串T，求出next数组

利用next数组进行匹配（主串指针不回溯）

对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }

求next数组

next数组的作用：当模式串的第j个字符失配时，从模式串的第next[j]的继续向后匹配

next[1]无脑写0

next[2]无脑写1

其他next：在不匹配的位置前，划一根美丽的分界线
模式串一步一步往后退，直到分界线之前全部匹配，或模式串完全跨过分界线为止。此时j指向哪儿,next数组值就是多少

最坏时间复杂度=O(m+n)

KMP算法的优化

求nextval数组

先求next数组

若next数组所对应位置的字符和当前字符相等，将对应位置的next数组赋值到当前位置的nextval数组

子主题3