串、数组和广义表的介绍

• 串是内容受限的线性表。
• 数组和广义表是线性表的推广，严格意义讲数组和广义表是非线性结构的。

串的定义

• 定义：零个或多个任意字符组成的有限序列。

• 相关术语：
  1、子串：串中任意个连续字符组成的子序列(含空串)称为该串的子串。
  例如，“abcde” 的子串有：“”、“a”、“ab”、“abc”、“abcd"和"abcde” 等
  2、真子串：是指不包含自身的所有子串。
  3、主串：包含子串的串相应地称为主串。
  4、字符位置：字符在序列中的序号为该字符在串中的位置
  5、子串位置：序串第一个字符在主串中的位置。
  6、空格串：由一个或多个空格组成的串，与空串不同。
  7、串相等：当且仅当两个串的长度相等并且各个对应
  位置上的字符都相同时，这两个串才是相等的。
  所有空串是相等的。
  

串的类型定义

ADT String{
	数据对象：D={ai|ai∈CharaterSet,i=1,2,…,n,n≥0}
	数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}
	基本操作：
	（1）StrAssign(&T,chars)//串赋值
	（2）StrCompare(S,T)//串比较
	（3）StrLength(S)//求串长
	（4）Concat(&T,S1,S2)//串连结
	（5）SubString(&Sub,S,pos,len)//求子串
	（6）StrCopy(&T,S)//串拷贝
	（7）StrEmpty(S)//串判空
	（8）ClearString(&S)//清空串
	（9）Index(S,T,pos)//字串的位置
	（10）Replace(&S,T,V)//串替换
	（11）StrInsert(&S,pos,T)//字串插入
	（12）StrDelete(&S,pos,len)//字串删除
	（13）DestroyString(&S)//串销毁
}ADT String

串的存储结构

串中元素逻辑关系与线性表的相同，串可以采用与线性表相同的存储结构。

串的顺序存储结构

#define MAXLEN 255
typedef struct{
	char ch[MAXLEN+1];//存储串的一维数组
	int length;//串的当前长度
}SString;

串的链式存储结构

• 块链结构

#define CHUNKSIZE 80//块的大小可由用户定义
typedef struct Chunk{
	char ch[CHUNKSIZE];
	struck Chunk *next;
}Chunk;
typedef struct{
	Chunk *head,*tail;//串的头指针和尾指针
	int curlen;//串的当前长度
}LString;//字符串的块链结构

串的模式匹配算法

• 算法目的：确定主串中所含子串(模式串)第一次出现的位置(定位)
• 算法应用：搜索引擎、拼写检查、语言翻译、数据压缩
• 算法种类：
  BF算法(Brute-Force，又称古典的、经典的、朴素的、穷举的)
  KMP算法(特点：速度快)

BF算法

Brute- Force简称为BF算法，亦称简单匹配算法。采用穷举法的思路。

Index(S,T,pos)
【算法思想】
① 将主串的第pos个字符和模式串的第一个字符比较；
② 若相等，继续逐个比较后续字符；
③ 若不等，从主串的下一字符起，重新与模式串的第一个字符比较；
④ 直到主串的一个连续子串字符序列与模式串相等。返回值为S中与T匹配的子序列第一个字符的序号即匹配成功；
⑤ 否则，匹配失败，返回值0。

int Index_BF(SString S,SString T){
	int i=1,j=1;
	while(i<=S.length&&j<=T.length){
		if(s.ch[i]==t.ch[j]//主串和子串依次匹配下一个字符
			++i;
			++j;
		else//主串、子串指针回溯重新开始下一次匹配
			i=i-j+2;
			j=1;
	}
	if(j>=T.length)
		return i-T.length;//返回匹配的第一个字符的下标
	else
		return 0;//模式匹配不成功
}

时间复杂度：O(m*n)

KMP算法

利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针不必回溯！可提速到O(n+m)！

为此，定义next[j]函数，表明当模式中第j个字符与主串中相应字行“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。

void get_next(SString T,int &next[]){
	i=1;
	next[1]=0;
	j=0;
	while(i<T.length){
		if(j==0||T.ch[i]==T.ch[j])
			++i;
			++j;
		else
			j=next[j];
	}
}
int Index_KMP(SString S,SString T,int pos){
	i=pos,j=1;
	while(i<=S.length&&j<=T.length){
		if(j==0||S.ch[i]==T.ch[j]
			i++;
			j++;
		else
			j=next[j];//i不必，j后退
	}
	if(j>T.length)
		return i-T.length;//返回匹配的第一个字符的下标
	else
		return 0;//模式匹配不成功
}

时间复杂度：O(m+n)