大话数据结构——串

大家好，欢迎来到IT知识分享网。

一、串的定义

串（string）是由零个或多个字符组成的有限序列，又叫字符串。一般记为s=“$a_1$$a_2$···$a_n$”$（n\ge 0）$，其中s是串的名称，用双引号（有的也用单引号）括起来的字符序列是串的值，此时的引号不属于串的内容。$a_i（1\le i\le n）$可以是字母、数字或其它字符，i是该字符在串中的位置。串中的字符数目n称为串的长度，“有限序列”指长度n是一个有限的数值。零个字符的串称为 空串（null string），它的长度为0可以直接用双引号““””表示，也可用希腊字母“Φ”来表示。所谓的序列，说明串的相邻字符具有前驱和后继的关系。
空格串，是包含空格的串。与空串不一样，空格串是有内容有长度的，而且可以不止一个空格。
字串和主串，串中任意个数的连续字符组成的子序列称为该串的子串，相应地，包含字串的串称为主串。

二、串的比较

串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。计算机中常用的字符是使用标准的ASCII编码，从7位二进制表示一个字符扩展到8位二进制，总共可以表示256个字符，但是仍然有许多特殊符号。因此后来有了Unicode编码，用16位二进制数表示一个字符，即可以表示$2^{16}$个字符，约6.5万多个字符，足够表示世界上所有语言的字符了。ASCII和Unicode的前256个字符完全相同。

三、串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，串的基本操作和线性表有很大区别，线性表更关注的是单个元素的操作，而串更多的是查找子串位置、得到指定位置子串、替换字串等操作。

/*T是非空串,若主串S中存在和串T相同的子串， 则返回它在主串S中的第pos个字符之后第一次出现的位置，否则返回0*/ int Index(String S, String T, int pos) { 
    int n, m, i; String sub; if (pos > 0) { 
    n = StrLength(S); m = StrLength(T); i = pos; while (i <= n - m + 1) { 
    SubString(sub, S, i, m); if (StrCompare(sub, T) != 0) ++i; else return i; } } return 0; } 

当中用到了StrLength、SubString、StrCompare等基本操作来实现。

四、串的存储结构

1、串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。一般用定长数组来定义。既然是定长的，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置。如下图。

有的编程语言不想存个数字占空间，就规定在串值后面加一个不计入串长度的结束标记字符，比如“\0”来表示串值得终结，这个时候要知道串长度就需要遍历，如下图。

对于串得顺序存储方式，可能会出现串的长度超过了数组的长度MAXSIZE，所以串值的存储空间可在程序执行过程中动态分配。比如计算机中存在一个自由存储区，“堆”。这堆可由C语言的动态分配函数malloc()和free()来管理。

2、串的链式存储结构

五、朴素的模式匹配算法

子串的定位操作通常称作串的模式匹配。
假设要从下面的主串S=“goodgoogle”中查找T=“google”这个子串，对于朴素的模式匹配通常需要下面的步骤。

/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则返回0 其中，T非空，1≤pos≤StrLength(S)*/ int Index(String S, String T, int pos) { 
    int i = pos; /*i用于主串S中当前位置下标，从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退回到子串的首位*/ } } if (j > T[0]) return i - T[0]; else return 0; } 

显然这种模式匹配有时候会很低效，例如主串S=“00000000000000000000000000000000000000000000000001”，有50个字符，子串T=“0000000001”有10个字符，直到最后第41位置才匹配成功，期间进行了（50-10+1）×10次操作。

六、KMP模式匹配算法

有三位前辈，D.E.Knuth、J.H.Morris和V.R.Pratt发表了一个模式匹配算法，可以大大避免重复遍历的情况，称之为克努特-莫里斯-普拉特算法，简称KMP算法。

1、KMP匹配算法原理

那么如果T串后面也含首字符“a”怎么办？

2、next数组值的推导

(2)T=“ababaaaba”

3、KMP模式匹配算法的实现

计算当前要匹配的串T 的next数组 

/*通过计算返回子串T的next数组*/ void get_next(String T, int* next) { 
    int k, j; j = 1; k = 0; next[1] = 0; while (j < T[0]) /*此处T[0]表示子串T的长度*/ { 
    if (k == 0 || T[j] == T[k]) { 
    ++j; ++k; next[j] = k; } else k = next[k]; /*若字符不相同，则k值回溯*/ } } 

KMP匹配查找 

/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则返回0 其中，T非空，1≤pos≤StrLength(S)*/ int Index_KMP(Sring S, String T, int pos) { 
    int i = pos; /*i用于主串S中当前位置下标值，从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 (j == 0 || S[i] == T[j]) /*两字母相等则继续，与朴素匹配相比增加了j=0的判断*/ { 
    ++i; ++j; } else /*指针后退重新开始匹配 */ { 
    j = next[j]; /*j退回合适的位置，i值不变*/ } if (j > T[0]) return i - T[0]; else return 0; } } 

4、KMP模式匹配算法的改进

/*求模式串T的next函数修正值并存入nextval数组*/ void get_nextval(String T, int* nextval) { 
    int k, i; i = 1; k = 0; nextval[1] = 0; while (i < T[0]) /*此处T[0]表示子串T的长度*/ { 
    if (k == 0 || T[i] == T[k]) /*T[i]表示后缀的单个字符，T[k]表示前缀的单个字符*/ { 
    ++i; ++k; if (T[i] != T[k]) /*若当前字符与前缀字符不相同*/ nextval[i] = k; /*则当前的k为nextval在i位置的值*/ else nextval[i] = nextval[k]; /*如果与前缀字符相同，将前缀字符的nextval值 赋值给nextval在i位置的值*/ } else k = nextval[k]; /*若字符不相同，则k值回溯*/ } 

5、nextval数值的推导

总结改进过的KMP算法，计算出next的同时，如果a位字符与它的next值指向的b位字符相等，则该a位的nextval就是指向b位的nextval值，如果不等，则该a位的nextval值是它自己a位的next的值。