【数据结构(初稿)】串的总结

2024-06-01 03:51| 来源: 网络整理| 查看: 265

halo~我是bay_Tong桐小白本文内容是桐小白个人对所学知识进行的总结和分享，知识点会不定期进行编辑更新和完善，了解最近更新内容可参看更新日志，欢迎各位大神留言、指点

串的总结——基本知识要点汇总(初稿）【更新日志】串的相关概念串的存储串的顺序存储串的链式存储串的模式匹配C语言库函数strstrBF算法KMP算法next值与nextval值的求解

【更新日志】

最近更新：

更新内容——BF算法代码实现（2020.7.8）内容持续更新中…… 串的相关概念定义：线性存储的一组数据（默认是字符）特殊操作集求串的长度比较两串是否相等两串相接求子串插入子串匹配子串删除子串 …… C语言中常用的串运算调用标准函数库#include 串比较，strcmp(char s1,char s2)串复制，strcpy(char s1,char s2)串连接，strcat(char s1,char s2)求串长，strlen(char s) …… 串的存储串的顺序存储

串的顺序存储描述

串的链式存储

串的链式存储描述

串的模式匹配 C语言库函数strstr 函数原型：char* strstr(char* string,char* pattern)函数参数：string为要被检索的字符串，pattern为要进行匹配的模式字符串函数返回值：函数返回在字符串string中第一次出现字符串pattern的位置，如果未匹配成功则返回NULL

举例：在字符串"This is a simple example.“中匹配字符串"simple”

#include #include #define NotFound NULL typedef char* Position; int main() { char string[] = "This is a simple example."; char pattern[] = "simple"; Position p = strstr(string, pattern); if (p == NotFound) { printf("Not Found.\n"); } else { printf("%s\n", p); } return 0; }

测试结果如下在这里插入图片描述

BF算法算法思想：朴素的穷举匹配，即将要进行检索的目标串string的第一个字符与要进行匹配的模式串的第一个字符进行匹配，若相等则继续比较string的第二个字符与pattern的第二个字符；若不相等，则将string下一个字符与pattern当前字符进行比较，依次一直进行下去，直到匹配出结果或匹配结束。算法实现（C语言）： int BF(char* str, char* substr) { int i = 1, j = 1, k = i; if (strlen(str) if (str[i] == substr[j]) { i++; j++; } else { j = 1; i = ++k; } } if (substr[j] == '\0') return k; else return 0; } KMP算法 next值与nextval值的求解

【暂时只总结求解方法，具体解释和原理后续更新】

核心思想：寻找当前字符之前的字符串中头部和尾部相等的长度最大的子串举例：默认字符元素从下标为1的数组单元开始存

数组下标为1和2的数组单元next值是一定的，分别为0和1 在这里插入图片描述接下来数组单元的next值的求解，需要寻找这个字符之前的字符串中头部和尾部相等的长度最大的子串，这个子串的长度+1即为此字符的next值，如果这个字符之前的字符串头部和尾部没有可以匹配的子串，则此字符的next值为1

例如此时数组下标为3字符b之前的字符串"aa"，头部和尾部相同的长度最大的子串为“a”，长度为1，因此它的next值为1+1=2 在这里插入图片描述数组下标为4的字符a之前的字符串"aab"，头部和尾部没有可以匹配的子串，因此它的next值为1 数组下标为5的字符a之前的字符串"aaba"，头部和尾部可以匹配的最大长度子串为“a”，因此它的next值为1+1=2 数组下标为6的字符c之前的字符串"aabaa"，头部和尾部可以匹配的最大长度子串为“aa”，因此它的next值为1+2=3 在这里插入图片描述【此处需注意，寻找字符串头部和尾部可以匹配的最大长度子串时，顺序需保持一致，如字符串"aabaa"头部和尾部长度为3的子串分别为"aab"与"baa"，二者匹配不成功】

nextval值需要根据next值求解，数组下标为1的字符nextval值是一定的，为0。在这里插入图片描述接下来数组单元的next值的求解，以它的next值为下标去访问数组单元，比较两个单元的字符是否相等，若相等则它们的nextval值也保持一致，若不相等，则此字符的nextval值与next值保持一致

例如此时数组下标为2字符a的next值为1，将其作为数组下标对应的字符为a，两者相等，则nextval值也保持一致在这里插入图片描述数组下标为3字符b的next值为2，将其作为数组下标对应的字符为a，两者不相等，则它的nextval值与next值保持一致依此继续进行求解，可完成全部求解

持续更新中…… 我是桐小白，一个摸爬滚打的计算机小白

【本文地址】

【数据结构(初稿)】串的总结

【数据结构(初稿)】串的总结

今日新闻

推荐新闻