数据结构之串

??数据结构是程序设计的重要基础，它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。
??数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的 逻辑结构，数据元素及元素之间关系的存储称为 存储结构(或物理结构)。数据结构按照逻辑关系的不同分为 线性结构和 非线性结构两大类，其中，非线性结构又可分为树结构和图结构。
??线性结构是一种基本的数据结构，主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系，即元素“一个接一个排列”。
??串(字符串)是一种特殊的线性表，其数据元素为字符。计算机中非数值问题处理的对象经常是字符串数据，例如，在汇编和高级语言的编译程序中，源程序和目标程序都是字符串；在事处理程序中，姓名、地址等一般也是作为字符串处理的。串具有自身的特性，运算时常常把一个串作为一个整体来处理。这里介绍串的定义、基本运算、存储结构及串的模式匹配算法。

1、串的定义及基本运算

??（1）串的定义
??串是仅由字符构成的有限序列，是一种线性表。一般记为 S=‘a₁a₂…a_n’，其中，S是串名，单引号括起来的字符序列是串值。
??（2）串的几个基本概念
??●空串：长度为零的串称为空串，空串不包含任何字符。
??●空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。
??●子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
??●串相等：指两个串长度相等且对应序号的字符也相同。
??●串比较：两个串比较大小时以字符的 ASCII码值(或其他字符编码集合)作为依据。实质上，比较操作从两个串的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
??（3）串的基本操作
??① 赋值操作 StrAssign(s,t)： 将串 s 的值赋给串t。
??② 连接操作 Concat(s,t)： 将串 t 接续在串 s 的尾部，形成一个新串。
??③ 求串长 StrLength(s)： 返回串 s 的长度。
??④ 串比较 StrCompares,t)： 比较两个串的大小。返回值-1、0 和1分别表示 s<t、s=t 和
s>t三种情况。
??⑤ 求子串 SubString(s,start,len)： 返回串s 中从 start 开始的、长度为 len 的字符序列。
??以上 5 种最基本的串操作构成了串的最小操作子集，利用它们可以实现串的其他运算。

2、串的存储结构

??串可以进行顺序存储或链式存储。
??（1）串的顺序存储结构。 串的顺序存储结构是指用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。
??（2）串的链式存储。当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符，此时要考虑存储密度问题。在链式存储结构中，结点大小的选择会直接影响对串的处理效率。

3、串的模式匹配

??子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。
??（1）补素的模式匹配算法
??该算法也称为布鲁特- 福斯算法，其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对字符进行后续的比较，否则从主串第二个字符起与模式串第一个字符重新比较，直到模式串中每个字符依次和主串中一个连续的字符序列相等时为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。
??【函数】以字符数组存储字符串，实现补素的模式匹配算法。

int Index(char S[], char T[], int pos)
/*查找并返回模式串T在主串S中从pos 开始的位置(下标)，若T不是S的子串，则返回-1*/
/*模式串T和主S第一个字符的下标为0*/
{
	int  i, j, slen, tlen;
	i=pos; j=0;								/*i、j分别用于指出主串字符和模式串字符的位置*/
	slen = strlen(S); tlen = strlen(T);		/*计算主串和模式串的长度*/
	while (i < slen && j< tlen){
		if(S[i == T[j]){i++; j++;}
		else {
			i=i-j+1;						/*主串字符的位置指针回退*/
			j=0;
		}
	}/*while*/
	if (j >= tlen) return i - tlen;
	return -1;
}/*Index*/

??假设主串和模式串的长度分别为 n 和 m，位置序号从0开始计算，下面分析朴素模式匹配算法的时间复杂度。设从主串的第 i 个位置开始与模式串匹配成功，且在前 i 趟匹配中(位置0 ~ i-1)，每趟不成功的匹配都是模式串的第一个字符与主串中相应的字符不相同，则在前 i 趟匹配中，字符的比较共进行了 i 次，而第 i+1 趟(从位置 i 开始)成功匹配的字符比较次数为m，所以总的字符比较次数为 i+m(0≤i≤n-m)。若在主串的 n-m 个起始位置上匹配成功的概率相同，则在最好情况下，匹配成功时字符间的平均比较次数为
$${\Sigma }_{i=0}^{n?m}{P}_i(i+m)=\frac{1}{n?m+1}{\Sigma }_{i=0}^{n?m}(i+m)=\frac{1}{2}(n+m)$$
??因此，在最好情况下匹配算法的时间复杂度为 O(n+m)。
??而在最坏情况下，每一趟不成功的匹配都是模式串的最后一个字符与主串中相应的字符不相等，则主串中新一趟匹配过程的起始位置为 i-m+2。设从主串的第 i 个字符开始匹配时成功，则在前 i 趟不成功的匹配中，每趟都比较了 m 次，总共比较了i×m 次，第 i+1 趟的成功匹配也比较了 m 次。因此，最坏情况下的平均比较次数为
$${\Sigma }_{i=0}^{n?m}{P}_i((i+1)\times m)=\frac{m}{n?m+1}{\Sigma }_{i=0}^{n?m}(i+1)=\frac{1}{2}m(n?m+2)$$
??通常情况下，由于n>>m，所以该算法在最环情况下的时间复杂度为 O(nXm)。
??（2）改进的模式匹配算法
??改进的模式匹配算法又称为 KMP 算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回退主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。
??设模式串为”p₀…p_m-1”，KMP 匹配算法的思想是：当模式串中的字符 p_j 与主串中相应的字符 S_i 不相等时，因其前 j 个字符(“p₀…p_j-1”)已经获得了成功的匹配，所以若模式串中的”p₀…p_k-1”与"p_j-k…p_j-1"相同，这时可令 P_k 与 S_i 进行比较，从而使 i 无须回退。
??在KMP算法中，依据模式串的next函数值实现子串的滑动。若令 next[j]=k，则next[j] 表示当模式串中的 p_j 与主串中相应字符不相等时，令模式串的 P_next[j]与主串的相应字符进行比较。
??next函数的定义如下：

??【函数】求模式串的next函数

void Get_next(char *p, int next[])	/*求模式串p的next函数值并存入数组 next*/
{
	int i, j, slen;
	slen = strlen(p); i= 0;
	next[0]=-1; j=-1;
	while(i < slen){
		if(j=-l || p[i] ==p[j]) {++i; ++j; next[i] =j;}
		else j= next[i];
	}/*while*/
}/*Get_next*/

??【函数】KMP 模式匹配算法，设模式串第一个字符的下标为 0

int Index_KMP(char *s, char *p,int pos, int next[] )
/*利用模式串p的next 函数，求p在主串s中从第pos个字符开始的位置*/
/*若匹配成功，返回模式串在主串中的位置(下标)，否则返回-1*/
{
	int i, j, slen, plen;
	i= pos-1;
	i=-1;
	slen = strlen(s);plen = strlen(p);
	while (i < slen &&j< plen ) {
		if(j==-1 || s[i]==p[j]) {++i;++j;}
		else j = next[j];
	}/*while*/
	if (j>=plen) return i - plen;
	else return -1;
}/*Index_KMP*/

??例如，设主串为“abacbcabababbcbc”，模式串为“abababb”，且模式串的 next 函数值如下表所示，则KMP 算法的匹配过程如下图所示。其中，i 是主串字符的下标，j 是模式串字符的下标。

j	0 ?? 1 ?? 2 ?? 3 ?? 4 ?? 5	? 6 ?
模式串	a ?? b ?? a ?? b ?? a ?? b	b
next[j]	-1 ?? 0 ?? 0 ?? 1 ?? 2 ?? 3	4

??第一趟匹配从 S[0]与 P[0]开始。由于 S[0] == P[0]、S[1]==P[1]、S[2]==P[2]，所以接下来比较S[3]与P[3]，由于S[3]与 P[3]不相等，所以第一趟结束，要进行第二趟匹配，令j=next [3] (即j=1)。第二趟从 S[3]与 P[1]开始比较，仍不相等，因此第二趟结束，要进行第三趟匹配，所以令 j = next[1] (即j=0)。 第三趟从 S[3]与 P[0]开始比较，如上图 (a) 所示。由于 S[3]与P[0]不相等，所以令j=next[0] (即j= -1)， 此时满足条件“j == -1”，显然不能令S[3]与 P[-1]进行比较，说明主串中从i=3 开始的子串不可能与模式串相同，因此需要将 i 的值递增后再继续进行匹配过程，即令 i++、j++，然后下一趟从 S[4] 与 P[0] 开始比较，如上图 (b)所示，继续匹配过程。直到某一趟匹配成功，或者由于在主串中找不到模式串而以失败结束。