数据结构:第四章 - 串 582次阅读 数据结构 2022-07-20 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 一、基础知识 串是由零个或多个字符组成的有限序列,是一种特殊的线性表,字符串中的字符之间也具有"一对一"的逻辑关系。串的最后一个字符 “ \0 ” 作为编译器识别串结束的标记。 数据结构中,根据串中存储字符的数量及特点,对一些特殊的串进行了命名: * 空串:存储 0 个字符的串,例如 S = ""(双引号紧挨着)。 * 空格串:只包含空格字符的串,例如 S = " "(双引号包含 3 个空格)。 * 子串和主串:假设有两个串 a 和 b,如果 a 中可以找到几个连续字符组成的串与 b 完全相同,则称 a 是 b 的主串,b 是 a 的子串。 > 例如,若 a = "shujujiegou",b = "shuju",由于 a 中也包含 "shuju",因此串 a 和串 b 是主串和子串的关系; > > 需要注意的是,空格串和空串不同,空格串中含有字符,只是都是空格而已。另外,只有串 b 整体出现在串 a 中,才能说 b 是 a 的子串,比如 "shujiejugou" 和 "shuju" 就不是主串和子串的关系。 ## 串存储结构的具体实现 存储一个字符串,数据结构包含以下 3 种具体存储结构: 1. 定长顺序存储:实际上就是用普通数组(又称静态数组)存储; 2. 堆分配存储:用动态数组存储字符串; 3. 块链存储:用链表存储字符串; > 第三种存储不在描述 > ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、存储结构 ## (一)定长顺序存储 串的定长顺序存储结构,可以简单地理解为采用 "固定长度的顺序存储结构" 来存储字符串,因此限定了其底层实现只能使用静态数组。 使用定长顺序存储结构存储字符串时,需结合目标字符串的长度,预先申请足够大的内存空间。 ```c typedef struct { char str[maxsize+1];//maxsize为穿的最大长度 /*串除了本身存储的数据元素外,还有最后一位的结束标记符,因此最大长度需+1*/ int length; }Str; ``` > 不同参考书对串的结构体定义有所不同。在本资料里,给串尾加上 ' \0 ' 结束标记,同时其也包含在 length 中。 ## (二)堆分配存储 即,变长分配存储(动态数组存储)。 ```c typedef struct { char *ch;//指向动态分配存储区首地址的字符指针 int length;//串长度 }Str; /*相关操作*/ Str S; S.length = L; S.ch = (char*)malloc((L+1)*sizeof(char)); S.ch[length范围内的位置] = 某字符变量; 某字符变量 = S.ch[length范围内的位置]; free(S.ch); ``` 这种存储方式在使用时,需要 malloc 和 free 函数动态申请和释放空间,在串处理应用程序中更为常用。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、串操作 ## (一)赋值操作 ```c int strAssign(Str& str, char* ch) { if(str.ch) free(str.ch);//释放原串空间 int len=0; char *c=ch; while(*c)//求ch串的长度 { ++len; ++c; } if(len==0)//如果ch为空串,则直接返回空串 { str.ch=NULL; str.length=0; return 1; } else { str.ch=(char*)malloc(sizeof(char) * (len+1)); if(str.ch==NULL) return 0; else { c=ch; for(int i=0;i<=len;++i,++c)//此处用“<=”是将‘/0’复制到新串做结束标记 str.ch[i]=*c; str.length=len; return 1; } } } /*函数使用格式*/ strassign(str,"输入的字符"); ``` ## (二)取串长度 ```c int strLength(Str str) { return str.length; } ``` ## (三)串比较 ```c /*一般比较的是ASCII码值或串长度*/ int strCompare(Str s1, Str s2) { for(int i=0;i=str.length||len<0||len>str.length-pos) return 0; if(substr.ch) { free(substr.ch); substr.ch=NULL; } if(len==0) { substr.ch=NULL; substr.length=0; return 1; } else { substr.ch=(char*)malloc(sizeof(char)*(len+1)); int i=pos; int j=0; while(i ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 四、BF 算法 普通模式匹配算法,其实现过程没有任何技巧,就是简单粗暴地拿一个串同另一个串中的字符一一比对,得到最终结果。 ``` int index(Str str,Str substr) { int i=1,j=1,k=1;//串从数组下标1位置开始存储,因此初值为1 while(i<=str.length && j<=substr.length) { if(str.ch[i] == substr.ch[j]) { ++i;++j; } else { j=1; i=++k;//匹配失败,i从主串的下一位置开始,k中记录了上一次的起始位置 } } if(j>substr.length) return k; else return 0; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 五、kmp 算法 ## (一)目的 快速的从主串找出想获取的子串。 ## (二)求 next[j]值的方法 通过消除主串指针的回溯来提高匹配效率。 > 以下两种方法,数组下标从 0 或 1 开始,建议数组下标从 1 开始。 > > * 下标从 **0**开始: > > * **next[ 0 ] = -1** > * **next[ 1 ] = 0** > * **next[ j ] = 从 1 到 j 的最大公共前后缀** > * 下标从 **1**开始: > > * **next[ 1 ] = 0** > * **next[ 2 ] = 1** > * **next[ j ] = 从 1 到 j - 1 的最大公共前后缀** ### 1、方法一 (1)在主串与模式串 t 匹配部分(相同的部分)字符串中,有 n 个相同的公共前后缀。 > 匹配部分的两端有某两个子串完全相同,分别称为前缀和后缀 (2)定义一个 **next[ j ]** 数组(1 < j < m,m 为 t 长度)。 > 作用:当 t 中第 j 个字符发生不匹配时,应从 next[ j ] 开始处的字符开始重新与主串比较。 ( j 前部分为公共前后缀) (3)将 t 以从前向后的顺序分别给出数组的下标,并输入 next[ ] 数组。 (4)当 next[ ] 中第 j 个字符发生不匹配时,找出 j 前所有字符的最大长度 L 且相同的前缀与后缀,此时 L 为 next[ j ] 的值。 记: **next[ j ] = L + 1** > 其中, > > * j:t 的下标; > * L:第 j 个字符前字符串的公共前后缀最大长度(不包括字符串本身) ### 2、方法二 本质:根据前一位进行递归比较,最后 next[j] = next[k] +1 或 next[j] = 1。 设:下标 j,字符 t,next 值,将这三位看为一组数据。 > 一组数据包含三个值。例:A 组数据:A~j~ 、A~t~ 、A~next~ (1)将第 j 位的前一位数据组作为 A,将其字符记为“ 比较字符 A~t~ ”。寻找与 A~next~值相等的数组下标的数据组,记为“ 比较组 B ”。 (2)判断 * 当 A~t~ = B~t~ ,则 next[ j ] 等于 B 组中的 next 值加 1 ,即: next[ j ] = B~next~ +1。 * 当 A~t~ != B~t~ ,则寻找与 B~next~ 相等下标的数据组,该组数据为新的比较组 C 。 * 当 A~t~ = C~t~ ,则 next[j] 等于 C 组中的 next 值加 1,即:next[ j ] = C~next~ +1。 * 当 A~t~ != C~t~ ,则再次寻找,直到寻找到一组数据 M 中 M~next~ 所对应下标数据中的字符 t 与 A~t~ 相等,则 next[ j ] = M~next~ +1 。 若找到第一位其字符 t 与 A~t~ 都不匹配,则 next[ j ] = 1。 > 在这个过程中,只有比较字符 A~t~ 不需要变动,比较组会递归地向前查询判断。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit4/DS.Unit4.%285.2.2_1%29.png) ## (三)代码 ### 1、求 next 数组 ```c void getNext(Str substr, int next[]) { int j = 1, t = 0; next[1] = 0; while(j < substr.length) { if(t==0 || substr.ch[j] == substr.ch[t]) { next[j+1] = t+1; ++t; ++j; } else t = next[t]; } } ``` ### 2、KMP 算法 ```c int KMP(Str str, Str substr, int next[]) { int i=1,j=1;//串从数组下标1位置开始存储,因此初值设1 while(i<=str.length && j<=substr.length) { if(j==0||str.ch[i]==substr.ch[j]) { ++i; ++j; } else { j=next[j]; } } if(j>substr.length) return i-substr.length; else return 0; } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 六、kmp 算法的改进 ## (一)求解 nextval 数组的一般步骤 设第 j 位的数据组作为 A ,其字符记为“ 比较字符 A~t~ ”,求其 nextval[ j ]。 寻找与 A~t~值相等的数组下标的数据组,记为“ 比较组 B ”。 1. 当 j = 1 时,nextval[ j ] = 0 ,作为特殊标记。 > 可以确定 nextval 数组的第一位与 next 数组第一位相同。 > 2. 当 j >= 2 时,比较 A~t~ 与 B~t~ 是否相同: 1. 若相同,则 nextval [ j ] 值等于 B 的 nextval 值,即:nextval [ j ] = B~nextval~ 。 2. 若不同,则 nextval [ j ] 值等于自身的 next 值,即:nextval [ j ] = A~next~ 。 > 不再进行向前方递归查询 ### 1、下标从 0 开始 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit4/DS.Unit4.%286.1.1_1%29.png) ### 2、下标从 1 开始 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit4/DS.Unit4.%286.1.2_1%29.png) ## (二)Code ```c void getNextval(Str substr, int nextval[]) { int j = 1, t = 0;//下标从1开始,所以j=1 nextval[1] = 0; while(j < substr.length) { if(t==0 || substr.ch[j]==substr.ch[t]) { if(substr.ch[j+1] != substr.ch[t+1]) nextval[j+1] = t+1; else nextval[j+1] = nextval[t+1]; ++j; ++t; } else t = nextval[t]; } } ``` ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 2 最后一次更新于2022-10-23 数据结构
0 条评论