数据结构学习笔记——串---枉凝眉

1.定义 串（String）是由零个或多个字符组成的有限序列，又名叫字符串。 一般记为s = “a1a2……an”(n>=0)。 串中的字符数目n称为串的长度，定义中谈到的“有限”是指长度n是一个有限的数值。 零个字符的串称为空串（null string）。 区分几个概念 1.空格串：是只包含空格的串。注意它与空串的区别，空格串是有内容有长度的，而且可以不止一个空格。 2.子串与主串：串中任意字数的连续字符组成的子序列称为该串的子串，相应地，包含子串的串称为主串。 子串再主串中的位置就是子串的第一个字符在主串中的序号。 串的比较 事实上，串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。 2.串的抽象数据类型 1.StrAssign(T, *chars)：生成一个其值等于字符串常量chars的串T。 2.StrCopy(T, S)：串S存在，由串S复制得串T。 3.ClearString(S)：若串S存在，将串清空。 4.StringEmpty(S)：若串S为空，返回true，否则返回false。 5.StrLength(S)：返回串S得元素个数，即串得长度。 6.StrCompare(S, T)：若S>T，返回值>0，若S=T，返回0，若S<T，返回值<0。 7.Concat(T, S1, S2)：用T返回由S1和S2联接而成得新串。 8.SubString(Sub, S, pos, len)：串S存在，1<=pos<=StrLength(S)，且0<=len<=StrLength(S)-pos+1，用sub返回串S的第pos个字符起长度为len的子串。 9.Index(S, T, pos)：若串S和T存在，T是非空串，1<=pos<=StrLength(S)。若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0. 10.Replace(S, T, V)：串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T不重叠的子串。 11.StrInsert(S, pos, T)：串S和T存在，1<=pos<=StrLength(S)+1。在串的第pos个字符之前插入串T。 12.StrDelete(S, pos, len)：串S存在，1<=pos<=StrLength(S)-len-1。从串S中删除第pos个字符起长度为len的子串。 像C++或者Java这样的高级语言中都已经封装了String类，用来实现对字符串的上述操作，非常的方便，但C语言还没有实现这样的功能，所以需要我们自行实现。 3.串的存储结构 （1）串的顺序存储结构 串的顺序存储结构是用一组地址连续的存储空间来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量氛围一个固定长度的存储区。一般是用定长数组来定义。 （2）串的链式存储结构 对于串的链式存储结构，与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用"#"或其他非串值字符补全。 但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。 4.字符串匹配算法 （1）朴素的模式匹配算法 模式匹配：子串的定位操作通常称做串的模式匹配，应该算是串中最重要的操作之一。 朴素的模式匹配算法简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。 下面是朴素的模式匹配算法的实现代码

//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0 //T非空，1<=pos<=StrLength int Index(String S, String T, int pos){ int i = pos; //i用于子串S中当前位置下标，若pos不为1，则从pos位置开始匹配 int j = 1; //j用于子串T中当前位置下标值 while(i <= S[0] && j <= T[0]){ //若i小于S长度且j小于T的长度时循环 if(S[i] == T[j]){ //两字母相等时则继续 ++i; ++j; } else{ //指针后退重新开始匹配 i = i - j + 2; //i退回到上次匹配首位的下一位 j = 1; //j退回到子串T的首位 } } if(j > T[0]) return i - T[0]; else return 0; }

最坏情况的时间复杂度为O[[n-m+1]*m]。 （2）KMP模式匹配算法 很多年前我们的科学家们，觉得像这种有多个0和1重复字符的字符串，模式匹配需要挨个遍历的算法是非常糟糕的，于是有三位前辈，D.E.Knuth、J.H.Morris和V.R.Pratt（其中Knuth和Pratt共同研究，Morris独立研究）发表一个模式匹配算法，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 下面是KMP算法的实现代码

//通过计算返回子串T的next数组 void get_next(String T, int *next){ int i = 1; int j = 0; next[1] = 0; while(i < T[0]){ //此处T[0]表示T串的长度 if(j == 0 || T[i] == T[j]){ //T[i]表示后缀的单个字符 i++; //T[j]表示前缀的单个字符 j++; if(T[i] != T[j]) //若当前字符与前缀字符不同 next[i] = j; //则当前的j为next在i位置的值 else next[i] = next[j]; //如果与前缀字符相同，则将前缀字符的next值赋给next在i位置的值 } else{ j = next[j]; //若字符不相等，则j值回溯 } } } //返回子串T在主串在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0 //T非空，1<=pos<=StrLength(S) void Index_KMP(String S, String T, int pos){ int i = pos; //i用于主串S当前位置下标值，若pos不为1则从pos位置开始匹配 int j = 1; //j用于子串T中当前位置下标值 int next[255]; //定义一个next数组 get_next(T, next); //对串T作分析，得到next数组 while(i < S[0] || j < T[0]){ //若i小于S的长度且j小于T的长度时，循环继续 if(T[i] == S[j] || j == 0){ //两字母相等则继续，相对于朴素算法增加了j=0判断 i++; j++; } else{ //指针后退重新开始匹配 j = next[i]; //j退回合适的位置，i值不变 } } if(j > T[0]){ return i - T[0]; } else{ return 0; } }

关于KMP算法的实现原理，我们工作室有一个学算法的大佬学长曾专门撰文讲解，我看了后受益匪浅，下面将学长的博客附上

KMP算法及其本质详细讲解

---来自腾讯云社区的---枉凝眉