第四章．串
所学内容：串的抽象数据类型的定义；串的表示和实现；串的模式匹配算法
4.1串的抽象数据类型的定义
ADT String{
数据对象：
D = {a(i) | a(i) ∈CharacterSet, I=1, 2,….,n,
n>=0}
数据关系：
R(1) = {<a(I-1), a(i)> | a(I-1), a(i) ∈ D, I=2,….,n}
基本操作：
StrAssign(&T, chars)
StrCopy(&T, S)
StrLength(S)
StrEmpty(S)
StrCompare(S, T)
ConCat(&T, S1, S2)
SubString(&Sub, S, pos, len)
Index(S, T, pos)
Replace(&S, T, V)
StrInsert(&S, pos, T)
StrDelete(&S, pos, len)
串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素，求取某个元素，在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如在串中查找某个子串，求取一个子串，在串的某个位置上插入一个子串以及删除一个子串等。
例：可利用串比较、求串长和求子串等操作实现定位函数Index(S, T, pos).
算法的基本思想：在主串S中取从第I（I的初始值为pos）个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为I，否则I值增1直至串S中不存在和串T相等的子串为止。
Int Index(String S, String T, int pos)
{
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;
}
4.2串的表示和实现
1． 串的定长顺序存储表示
#define
MAXSTRLEN 255
//用户可在255以内定义最大串长
typedef unsigned
char Sstring[MAXSTRLEN + 1]
//0号单元存放串的长度
串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舌去，称之为“截断”。
2． 串的堆分配存储表示
typedef struct{
char* ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length; //串长度
}Hstring;
通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc() 和 free() 进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”，C语言中的串以一个空字符为结束符，串长是一个隐含值。
3． 串的块链存储表示
#define
CHUNKSIZE 80 //自定义块大小
typedef struct
Chunk{ //结点结构
char ch[CHUNKSIZE];
struct Chunk* next;
}Chunk;
typedef struct{
//串的链表结构
Chunk *head, *tail; //串的头和尾指针
Int curlen; //串的当前长度
}Lstring;
串值也可用链表来存储，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串，例如：在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即：同一行的串用定长结构（80个字符），行和行之间用指针连接。
4.3串的模式匹配算法
下面讨论以定长顺序结构表示串时的几种算法：
1． 简单算法：从主串S的第一个字符开始，依次往后与模式串比较，直到找到相匹配的串，否则返回0
int
Index(Sstring S, Sstring T, int pos)
{
I = pos; j=1;
While(I <=
S[0] && j<=T[0])
{
If(s[I] == T[j]) { ++I, ++j} //继续比较后继字符
Else { I = I-j+2; j =1;} //指针后退重新开始匹配
}
if(j > T[0] )
return I-T[0];
else return 0;
}
2． 首尾匹配算法
先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。
Int
Index_FL(Sstring S, Sstring T, int pos)
{
sLength = S[0];
tLength = T[0];
I =pos;
PatStartChar = T[1];
PatEndChar = T[tLength];
While(I<=sLength
– tLength +1)
{
If(S[I] != patStartChar) ++I;
//重新查找匹配起始点
Else if(S[I+tLength-1] != patEndChar) ++I; //模式串的“尾字符”不匹配
Else { //检查中间字符的匹配情况
K=1; j=2;
While(j<tLength
&& S[I+k] == T[j])
{
++k;
++j;
}
if(j == tLength) return I;
else ++I;
//重新开始下一次的匹配
}
}
return 0;
}
3． KMP算法
KMP算法的时间复杂度可以达到O（m+n），解决了上面两个算法指针回缩的问题。
Int
Index_KMP(Sstring S, Sstring T, int pos)
{
I = pos; j = 1;
While(I <=
S[0] && j<= T[0])
{
If(j =0 || S[I]
= S[j])
{
++I;
++j; //继续比较后继字符
}
else
{
j = next[j]; //模式串向右移动
}
}
if (j > T[0])
return I-T[0]; //匹配成功
else return 0;
}
计算next值：
1． Void Get_next(Sstring &T, int& next[])
{ //求模式串T的next函数值并存入数组next
I = 1; next[1] =0; j=0;
While(I <
T[0])
{
If(j = 0 || T[I] = T[j])
{
++I; ++j; next[I] = j;
}
else
{
j = next[j];
}
}
}
2． 改进的求next值的方法；
void
Get_nextval(Sstring &T, int &nextval[])
{
I = 1;
Nextval[1] = 0; j=0;
While(I <
T[0])
{
If(j = 0 || T[I]
== T[j])
{
++I; ++j;
if(T[I] != T[j]) next[I] = j;
else nextval[I] = nextval[j];
}
else j = nextval[j];
}
}
本章小结：
熟悉串的7中基本操作的定义，并能利用这些基本操作来实现串的其他各种操作的方法。
熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法
掌握串的堆存储结构以及在其上实现串操作的基本方法
理解串匹配的KMP算法，熟悉NEXT函数的定义，学会手工计算给定模式串的NEXT函数值和改进的NEXT的函数值。
