《第4章 串》习题解答

第4章 串存储与基本操作的实现

第四章 串存储与基本操作的实现

本章学习要点

◆熟悉串的相关概念以及串与线性表的关系

◆重点掌握串的定长存储、堆分配存储的表示方法与基本操作的实现

◆了解串的各种存储结构，能根据需要合理选用串的存储结构解决实际问题

“串”(string)，是字符串的简称，它是一种特殊的线性表，其特殊性在于组成线性表的数据元素是单个字符。字符串在计算机处理实际问题中使用非常广泛，比如人名、地名、商品名、设备名等均为字符串。同样在文字编辑、自然语言理解和翻译、源程序的编辑和修改等方面，都离不开对字符串的处理。

4.1串的基本概念

4.1.1串的概念

1．串的定义

串(string) 是由n个字符组成的有限序列，记为：S=”a0a1a2…an-1” (n≥0)。

其中，S是串的名字，字符序列a0a1a2…an-1是串的值，ai(0≤i≤n-1)可以是字母、数字或其他字符元素；由于在C语言系统中数组元素的下标是从0开始的，所以串中所含元素的序号等于该元素的下标值加1；串中所含字符的个数n称为该串的长度，长度为0的字符串称为空串（null string）。

从串的定义可以看出，串实际上是数据元素为字符的特殊的线性表。 例如：

（1）A=“X123” (长度为4的串) （2）B=“12345654321” (长度为11的串) （3）C=“Bei Jing” (长度为8的串) （4）D=“” (长度为0的空串) （5）E=“This is a string” (长度为16的串) （6）F=“ is a ” (长度为6的串)

2．子串、主串和位置

串中任意连续的字符组成的子序列称为该串的子串；相应地，包含子串的串称为主串。串中的字符在串序列中的序号称为该字符在该串中的位置；子串的第一个字符在主串中的位置称为子串在主串中的位置。显然，串为其自身的子串，并规定空串为任何串的子串。显然，在不考虑空子串的情况下，一个长度为n的字符串具有n(n+1)/2个子串。 例如：

在上例的(6)中串F就是(5)中串E的子串，且子串F在主串E中的位置是5。由于空格符也是一个字符，所以在串G=“abc defghne”中包含有子串“c def”,而串 “cdef”不是串G的子串。串G中第一个字符?e?的位置是6，第二个字符?e?的位置是11。

3．串的比较

如果两个串的长度相等且对应位置上的字符相同，则称这两个串相等。两个串A、B的比较过程是：从前往后逐个比较对应位置上的字符的ASCII码值，直到不相等或有一个字符串

-.71.-

第4章 串存储与基本操作的实现

结束为止，此时的情况有以下几种：

（1）两个串同时结束，表示A等于B；

（2）A中字符的ASCII码值大于B中相应位置上字符的ASCII码值或B串结束，表示A大于B；

（3）B中字符的ASCII码值大于A中相应位置上字符的ASCII码值或A串结束，表示A小于B。 例如：

“abc”=“abc”，“abc”<“abcd”，“abxy”>“abcdefg”，“132”>“123456”，“ABab”<“abAB”，“3+2”>“2+3”。

4．空格串

由一个或多个空格字符组成的串称为空格串，空格串的长度为串中所含空格字符的个数。在串操作中不要将空格串和空串混淆。

4.1.2串的基本操作

尽管串的定义和线性表极为相似，但是串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，比如对线性表的查找、访问、插入、删除和排序等；而在串的基本操作中，通常以串整体或串的一部分（子串）作为操作对象，比如子串的查找、截取子串、删除一个子串、插入子串和子串替换等操作。

串的基本操作主要有：

（1）初始化串StrAssign(&T,chars) 由字符串常量chars生成字符串T的操作。 （2）串复制StrCopy(&T,S) 由串S复制生成串T的操作。

（3）串比较StrCompare(S,T) 若S=T返回0，S>T返回正数，S

（5）串连接Concat(&T,S1,S2) 将串S1和S2连接起来生成串T的操作。

（6）求子串SubString(&Sub,S,pos,len) 以串S中pos位置开始的len个字符生成子串Sub的操作。

（7）串查找Index(S,T,pos) 返回子串T在S中pos个字符以后出现的位置。 （8）串替换Replace(&S,T,V) 将串S中所有不重叠子串T替换为串V的操作。 （9）串插入StrInsert(&S,pos,T) 在串S中第pos个字符前插入串T的操作。 （10）删除子串StrDelete(&S,pos,len) 删除串S中第pos个字符开始的len个字符的操作。

4.2串的存储表示与实现

既然串是线性表的特例，所以线性表的两种存储结构对于串也是适用的。在应用中具体选用何种存储结构与串的操作有关，比如对串进行插入和删除操作运算时选用链存储结构较好，对串进行查找和求子串运算时选用顺序存储结构较好。

本章主要介绍串的3种存储表示方法： （1）串的定长顺序存储表示法 （2）串的堆分配存储表示法 （3）串的块链式存储表示法

4.2.1串的定长顺序存储表示

-.72.-

第4章 串存储与基本操作的实现

串的定长顺序存储表示是用一组地址连续的存储单元来存储串中的字符序列。在串的定长顺序存储表示中，按照预定义的大小，为每个定长的串变量分配一个固定长度的存储区，所以可以用定长字符数组来表示。

1．定长顺序存储结构

在C++运行环境中，定长顺序结构定义为： #include\#include\

#define MAXLEN 255 //定义串的最大长度为255 typedef char SString[MAXLEN+1]; //定义定长顺序存储类型SString 2．基本操作的C++程序实现

（1）求串长度操作int Length_SS(SString S)

操作返回串S中所含字符的个数，即串的长度；如果S为空串则返回0。 int Length_SS(SString S) { int i=0; while(S[i])i++; return(i); }

（2）串连接操作int Concat_SS(SString &T,SString S1,SString S2)

该操作将串S1、S2连接生成串T，如果在连接过程中产生了截断（即S1的长度加上S2的长度大于MAXLEN）则返回0，否则返回1。

int Concat_SS(SString &T,SString S1,SString S2) { int i,j,k; i=j=k=0; while(T[i++]=S1[j++]); i--; while(i

该操作截取串S中从第pos个字符开始的连续的len个字符生成子串Sub，如果位置pos和长度len合理则返回1，否则返回0.

int SubString_SS(SString &Sub,SString S,int pos,int len) { int i=0;

-.73.-

第4章 串存储与基本操作的实现

}

if(pos<1||len<0||pos+len>Length_SS(S)+1) return 0; /*判断位置和长度是否合理*/ while(i

（4）初始化串操作int StrAssign_SS(SString &T,char *s)

该操作用字符数组s，初始化定长顺序串T。如果不产生截断（长度合理）返回1，否则返回0。

int StrAssign_SS(SString &T,char *s) { int i=0; while(i

（6）串比较操作int StrCompare_SS(SString S,SString T)

该操作比较顺序串S、T的大小，如果S>T则返回正数,如果S=T则返回0,否则返回负数。 int StrCompare_SS(SString S,SString T) { int i=0; while(S[i]&&T[i]&&(S[i]==T[i]))i++; return (int)(S[i]-T[i]); }

（7）串的替换操作int Replace_SS(SString &S,int n,int m,SString T)

该操作将串S中从第n个字符开始的连续的m个字符替换成串T中的字符，如果n和m的选取合理则返回1，否则返回0。

int Replace_SS(SString &S,int n,int m,SString T) { SString S1; int len=Length_SS(T);

-.74.-

第4章 串存储与基本操作的实现

}

int i=n-1,j=0,k=n+m-1;

/*i为开始替换位置，j指向第一个替换字符，k为剩余字符的开始位置*/

if(n<1||m<0||n+m>Length_SS(S)+1||Length_SS(S)+len-m>MAXLEN) return(0);

/*判断位置是否合理*/ StrCopy_SS(S1,S); /*将剩余部分复制到S1中*/ while(S[i++]=T[j++]); /*替换S中指定部分的字符*/ i--;

while(S[i++]=S1[k++]); /*将剩余部分复制到S中*/ return(1);

（8）主函数演示程序main()

void main_SS() { SString s1,s2,s3,sub,T; char str1[100],str2[100]; int l1,l2,l3,pos,len,n; while(1) { cout<<\串初始化操作：\\n输入两个字符串:\\n\ cin.getline(str1,sizeof(str1));

/*表示从键盘输入一个可以含有空格字符的长度小于100的字符串到str1中，语句 “cin>>str1”不能输入空格字符（空格符表示输入结束）且对串的长度不做检查。*/

cin.getline(str2,sizeof(str2)); StrAssign_SS(s1,str1); StrAssign_SS(s2,str2); l1=Length_SS(s1); l2=Length_SS(s2);

cout<<\求串长操作：\\ns1的长度=\，s2的长度=\n=StrCompare_SS(s1,s2);

cout<<\串比较操作：\\n比较结果为: \if(n>0)cout<<\

else if(n==0)cout<<\else cout<<\Concat_SS(s3,s1,s2);

cout<<\串连接操作：\\ns1+s2=\l3=Length_SS(s3);

cout<<\的长度=\

cout<<\求子串操作：\\n输入开始位置和串长(pos len):\\n\cin>>pos>>len;

if(SubString_SS(sub,s3,pos,len)) cout<<\

-.75.-

第4章 串存储与基本操作的实现

else cout<<\位置不正确\\n\ cout<<\串替换操作：\\n输入替换的位置和字符数(pos len):\ cin>>pos>>len; cout<<\输入替换串:\\n\cin.get(); cin.getline(str1,sizeof(str1)); StrAssign_SS(T,str1); if(Replace_SS(s3,pos,len,T)) cout<<\替换结果为:\\ns3=\ else cout<<\替换不成功!\\n\ }

}（程序运行过程略） 3．定长顺序存储的特点

对于定长顺序存储的串在基本操作方面主要有以下特点：

（1）对于求串长度和串的复制操作而言，其时间复杂度依赖于字符串的长度； （2）在串删除和串插入操作时必须移动大量的字符；

（3）如果在串输入、串连接、串插入和串替换操作中串值的长度超过MAXLEN，则按约定采取“截尾”法处理，这将导致操作结果的不合理。

4.2.2串的堆分配存储表示

由于串操作基本上是以串整体的形式参与，在应用程序中串变量的长度相差较大，并且在操作中串值长度的变化也比较大。因此，事先为串变量设置固定大小空间的数组不尽合理。

用堆分配存储表示串的方法是：

在程序执行过程中，根据串变量值的大小，在堆空间中动态分配一个连续的地址空间来存储串变量中的字符，这样既可以避免产生串操作中的“截断”现象又能合理使用内存空间资源。

1．串的堆分配存储结构

在C++运行环境中，堆分配存储结构定义为 struct HString

{ char *ch; //串变量中字符数组的首地址 int length; //串的长度 };

2．在堆分配存储结构中串基本操作的C++程序实现 （1）串的赋值操作void StrAssign_HS(HString &T,char str[]) 该操作由字符串常量str生成一个HString型串T。 void StrAssign_HS(HString &T,char str[]) { int len=0,i; while(str[len])len++; //计算串的长度 T.length=len; if(!len)T.ch=NULL; //对空串进行初始化

-.76.-

第4章 串存储与基本操作的实现

}

else

{ T.ch=new char[len+1]; //在堆内存中分配相应大小的存储空间 for(i=0;T.ch[i]=str[i];i++); //将数据从str复制到T.ch中 }

（2）求串长的操作int Length_HS(HString S) 该操作返回串S的长度，如果S为空串则返回0。 int Length_HS(HString S){return(S.length); }

（3）串的比较操作int StrComp_HS(HString S,HString T) 该操作比较串S、T的大小。

int StrComp_HS(HString S,HString T) { int i; for(i=0;i

（4）串的清空操作void ClearString_HS(HString &S) 该操作清空串S所占的堆空间。 void ClearString_HS(HString &S) { if(S.ch) { delete[]S.ch; S.ch=NULL; S.length=0; } }

（5）串的连接操作void Concat_HS(HString &T,HString S1,HString S2) 该操作计算串S1、S2的连接串T。

void Concat_HS(HString &T,HString S1,HString S2) { int i,j,k; T.length=S1.length+S2.length; i=j=k=0; T.ch=new char[T.length+1]; //分配链接串的储存空间 while(T.ch[i++]=S1.ch[j++]); //将S1复制到T i--; while(T.ch[i++]=S2.ch[k++]); //将S2连接到T的末尾 }

-.77.-

第4章 串存储与基本操作的实现

（6）求子串的算法int SubString_HS(HString &Sub,HString S,int pos,int len)

该操作求串S中pos个字符开始的len个字符组成的子串Sub，如果位置合理返回1否则返回0。

int SubString_HS(HString &Sub,HString S,int pos,int len) { int i; if(pos<1||len<1||pos+len>S.length+1) return(0); //如果位置不合理时返回0值 Sub.ch=new char[len+1]; //动态分配子串的存储空间 Sub.length=len; for(i=0;i

该操作在串S的第pos个字符前面插入字符串H，如果位置合理返回1，否则返回0。 int StrInsert_HS(HString &S,int pos,HString H) { int i,j,k; HString S1; if(pos<1||pos>S.length+1) return 0; //位置不合理返回0值 S1.length=S.length+H.length; S1.ch=new char[S1.length+1]; //重新分配空间 for(i=0;i

（8）串替换操作的算法int Replace_HS(HString &S,int n,int m,HString T)

该操作将串S中第n个字符开始的m个字符替换为串T，如果位置n和字符数m合理返回1否则返回0。

int Replace_HS(HString &S,int n,int m,HString T) { int i,j,k=n+m-1; HString S1;

if(n<1||m<0||n+m>S.length+1)return(0); //长度或位置不合理

-.78.-

第4章 串存储与基本操作的实现

S1.length=S.length+T.length-m; S1.ch=new char[S1.length+1]; //重新分配储存空间 for(i=0;i

（9）主函数演示程序main()

void main_HS() { HString S1,S2,S,sub,V,T; SString ss1,ss2; int n,pos,len; while(1) { cout<<\串初始化操作：\\n输入两个字符串:\\n\ cin.getline(ss1,sizeof(ss1)); cin.getline(ss2,sizeof(ss2)); StrAssign_HS(S1,ss1); StrAssign_HS(S2,ss2);

cout<<\求串长操作：\\nlen1=\cout<<\ cout<<\串比较操作：\\n比较大小的结果为：\ n=StrComp_HS(S1,S2); if(n>0) cout<<\ else if(n<0)cout<<\ else cout<<\ Concat_HS(S,S1,S2); cout<<\串连接操作：\\n:s1+s2=\

cout<<\ cout<<\取子串操作：\\n输入取子串的位置和长度(pos len):\\n\ cin>>pos>>len; if(SubString_HS(sub,S,pos,len)) cout<<\ else cout<<\位置不对!\\n\ cout<<\串插入操作：\\n请输入插入位置:\cin>>pos;cin.get(); cout<<\输入要插入的子串V:\\n\cin.getline(ss1,sizeof(ss1)); StrAssign_HS(V,ss1); if(StrInsert_HS(S,pos,V)) cout<<\插入结果为 s=\

-.79.-

第4章 串存储与基本操作的实现

} }

else cout<<\位置不对!\\n\

cout<<\串替换操作；\\n输入替换子串的位置和长度(pos len):\\n\cin>>pos>>len;cin.get();

cout<<\输入替换串T:\\n\cin.getline(ss1,sizeof(ss1)); StrAssign_HS(T,ss1);

if(Replace_HS(S,pos,len,T)) cout<<\结果为 s=\else cout<<\位置不对!\\n\

3．堆分配存储表示的特点

从以上串基本操作的算法可以看出，堆分配存储结构的串既有顺序存储结构的特点，处

理方便，同时在操作中对串的长度又没有任何限制，更显灵活，因此该存储结构在有关字符串处理的应用程序中常被采用。

4.2.3串的块链式存储表示

1．块链式存储的概念

和线性表的链式存储结构类似，可以采用链表方式存储串。由于串中的每个数据元素是一个字符，在用链表存储串值时，存在一个“结点大小”的问题，即每个结点最多可以存放多少个串中字符。对于串“abcdefghijk”，如果采用每个结点存放一个字符的链表结构存储，其存储方式如图4.1(a)所示；如果采用每个结点存放三个字符的链表结构存储，其存储方式如图4.1(b)所示。由于串长不一定是结点大小的整数倍，所以在链表的最后一个结点不一定能被串中的字符占满，此时可补上若干个非串值字符?#?（或其它非串值字符）。

为了便于进行串的操作，当以链表存储串值时，除了头指针head外还可以附设一个指向尾结点的指针tail，并给出当前串的长度。称如此定义的串的存储结构为串的块链式存储结构。

2．块链式存储结构的表示

在C++运行环境中，可将块链式存储结构表示如下：

#define CHUNKSIZE 80 //定义每个结点的大小 struct Chunk {

char ch[CHUNKSIZE]; //块内的字符数组

Chunk* next; //指向下一个结点的指针 }; //块结构的类型定义

-.80.-

第4章 串存储与基本操作的实现

struct LString{

Chunk *head,*tail; //串的头指针和尾指针 int curlen; //串的长度

}; //块链式结构的类型定义

在一般情况下，对串的操作只需要从前向后扫描即可，故对串值不必建立双向链表。设尾指针的目的是为了便于进行串的连接操作，在串连接时需要处理第一个串尾结点中的无效字符。

3．块链式存储的存储密度

在串的块链式存储结构中，结点大小的选择很重要，它直接影响到串处理操作的效率。如果块选取的充分大时（可在一个块中存储串的所有字符）即为定长存储；如果每个块只放一个字符时即为链表存储。为了便于研究串值的存储效率我们给出如下存储密度的计算公式：

串值的存储密度?串值所占的存储位

实际分配的存储位假定next指针变量占用4个字节，每个字符占用1个字节，每个块中存放m个字符，那么串值的存储密度可以表示为ρ=m/(m+4)。显然，存储密度小（比如每个块存放1个字符时ρ=20%），运算处理方便，但是存储占用量大；存储密度大（比如每个块存放80个字符时ρ=20/21=95%），虽然存储占用量小，但是串值的运算处理（比如串的插入、删除、连接和替换等操作）不太方便。

4．块链式存储表示的特点

在一般情况下，对以块链式存储表示的串进行操作时比较麻烦，比如在串中插入一个子串时可能需要分割结点，连接两个串时，如果第一个串的最后一个结点没有填满，还需要添加其它字符。总的来说，用链表作为串的存储方式是不太实用的。因此，串的块链式存储结构不如定长顺序存储和堆分配存储结构灵活，它占用存储空间大且操作复杂。

4.3串的模式匹配

设S和T是两个给定的串，在串S中寻找串值等于T的子串的过程称为模式匹配。其中，串S称为主串，串T称为模式。如果在串S中找到等于串T的子串，则称匹配成功；否则匹配失败。模式匹配是各种串处理系统中最重要的操作之一。

模式匹配的操作记为Index(S,T,pos)，该函数的功能是，从串S的第pos个字符开始的字符序列中查找值等于T的子字符串。如果匹配成功，函数返回T在S中第pos个字符以后的串值中第一次出现的开始位置；否则函数返回0值。显然这里隐含要求模式串T不能为空串。

4.3.1串模式匹配的BF算法

在串的模式匹配算法中，最简单、最直观的算法是BF（Brute-Force,布鲁特-福斯）算法，在该算法中，分别利用指针i和指针j指示主串S和模式T中当前正待比较的字符下标。

算法的基本思想是：从主串S的第pos个字符起和模式T的第一个字符比较，若相等，则继续逐个比较后面的字符；否则从主串S的下一个字符起再重新和模式T的第一个字符开始逐个比较。以此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相

-.81.-

第4章 串存储与基本操作的实现

等，则称匹配成功，函数返回T的第一个字符在S中的位置，否则匹配不成功，函数返回0值。

BF算法表示的串查找函数int IndexBF_SS(SString S,SString T,int pos)的C++语言表示为： int IndexBF_SS(SString S,SString T,int pos=1) {//求子串T在S中从pos个位置开始首次出现的位置 int i=pos-1,j=0;

if(i<0||pos+Length_SS(T)>Length_SS(S)+1) return(0); while(S[i+j]&&T[j]) { if(S[i+j]==T[j])j++; //若字符相等，则继续比较后续字符 else {i++; j=0;} //若不相等，则重新开始新一轮比较 } if(!T[j]) return(i+1); //若匹配成功，则返回T首次出现的开始位置 else return(0); //若匹配不成功，则返回0 } 算法分析：

在一般情况下，BF算法的时间复杂度为O(m+n)，其中m,n分别为串S和T的长度。但是在有些情况下，该算法的效率很低。

例如：S=“aaaaaa??aaaaab”共有52个?a?和1个?b?,T=“aaaaaaab”共有7个?a?和1个?b?。由于每趟比较都是在最后一个字符出现不相等，此时需要将初始位置指针i回溯到i+1的位置上，并从模式的第一个字符开始重新比较。从图4.2所示的匹配过程可以直观地算出，初始位置指针i一共要回溯52-7=45次，总的比较次数为：8×(45+1)=368次。所以，在最坏的情况下BF算法的时间复杂度为O(m×n)。

4.3.2模式匹配的KMP算法

模式匹配的另一种算法是由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的，称之为克努特-莫里斯-普拉特操作，简称KMP算法，他是一种改进的模式匹配算法。此算法可使时间复杂度在O(m+n)的数量级上完成串的模式匹配操作。

1．模式的next数组

模式匹配的KMP算法是，每当一趟匹配比较过程中出现字符不相同的情况时，不需要回溯指针i,而是利用已经得到的“部分匹配”的结果将模式T向右“滑动”尽可能远的一段距离后，再继续进行比较。为此需要引入一个有关模式串T的整型数组next，其中第j个元素next[j-1]表示当模式串T中的第j个字符与主串S中相应字符匹配失败时，在模式T中需要重新和主串S中该字符进行比较的字符的下标值。

-.82.-

第4章 串存储与基本操作的实现

next数组定义为：

??1当j?0时?next[j]??max{k|0?k?j且T[0],T[1],?,T[k-1]?T[j-k],T[j-k?1],?,T[j-1]}

?0其它情况?其中next[j]=k表明，存在整数k满足条件0

“T[0]T[1]…T[k-1]”=“T[j-k]T[j-k+1]…T[j-1]”，

而对任意的整数k1(0

“T[0]T[1]…T[k1-1]”≠“T[j-k1]T[j-k1+1]…T[j-1]”

例如：

（1）模式T=“aaaaaaab”的next数组为next={-1,0,1,2,3,4,5,6} （2）模式T=“abaabcac”的next数组为next={-1,0,0,1,1,2,0,1}

（3）模式T=“ababcabcacbab”的next数组为next={-1,0,0,1,2,0,1,2,0,1,0,0,1}

2．next数组的算法实现

由定义可知，next[0]=-1,next[1]=0，假设现已求得next[0],next[1], ?,next[j],那么可以采用以下递推的方法求出next[j+1]。

令k=next[j]，

（1）如果k=-1或T[j]=T[k],则转入步骤(3) （2）取k=next[k],再重复操作(1)、(2) （3）next[j+1]=k+1;

计算next数组的算法void GetNext(char* T,int* next)用C++语言实现如下 void GetNext(char* T,int* next) { int i=0,k=-1,n=0; next[0]=-1; while(T[n])n++; //计算模式串T的长度n while(i

void main() { char p[6][50]={\

\

int next[50],i,j; for(i=0;i<6;i++) {

-.83.-

第4章 串存储与基本操作的实现

GetNext(p[i],next); //计算模式串p[i]的next数组 for(j=0;p[i][j];j++)cout<

}运行结果为：

-1 0 0 1 2 0 1 2 0 1 0 0 1 -1 0 0 1 1 2 0 1 -1 0 1 2 0 0 1 2

-1 0 0 0 1 2 3 -1 0 0 1 1 2 3 2

-1 0 0 0 1 1 2 0 1 2 3 4 2 1 1

3．KMP模式匹配算法的比较过程

假设主串为S=“aaaaaa??aaaaab”（其中共有52个?a?和1个?b?），模式串为T=“aaaaaaab”（其中共有7个?a?和1个?b?）。下面给出KMP模式匹配算法的比较过程：

首先求得模式T的next数组为next[]={-1,0,1,2,3,4,5,6}，主串与模式串的字符下标初值为i=0,j=0。

(1) 连续比较8次时，i=7,j=7，此时分别指向S的第8个?a?和T中最后的?b?；即S[i]≠T[j]。 (2) 取j为next[j]=next[7]的值6，即j=6指向T中第7个?a?(表示模式T向后滑动7-6=1个字符)。

(3) 比较S[i]和T[j]，均为?a?相同，i++,j++。

(4) 此时i的值+1,j=7，分别指向S的下一个?a?和T中最后的?b?；即S[i]≠T[j]，转入（2）继续。

(5) 重复(2)、(3)、(4)的步骤52-7=45次后，i、j均指向最后的字符?b?,即S[i]=T[j]。 (6) i++,j++操作后j=m(m为T的长度8)，循环结束，返回i-m+1。

从以上分析的比较过程可知，总的比较次数为：7+2×(52-7)+1=98次（见图4.3）

再如：主串为S=“abcdabcdabcdabcde”，模式串为T=“abcde”,则next={-1,0,0,0,0}。那么，可以算出用BF算法时的比较次数为29次。而用KMP算法的比较过程为：

(1) 比较5次后滑动模式T:j=next[4]=0,即向右滑动4个字符，此时j=0,i=4； (2) 再次连续比较5次后将模式T向右滑动4个字符，此时j=0,i=9； 以此类推，共需要比较的次数为5×4=20次（见图4.4）。

4．KMP模式匹配算法的实现

KMP模式匹配算法int Index_KMP(SString S,SString T,int pos)的C++语言实现 int Index_KMP(SString S,SString T,int pos=1)

-.84.-

第4章 串存储与基本操作的实现

{ int i=pos-1,j=0; //i指向S中第一个比较字符，j指向T中第一个字符 int m=Length_SS(T), n=Length_SS(S); int *next=new int[m]; //定义模式T的next数组 if(i<0||pos+m>n+1) return 0; //位置不合理返回0值 GetNext(T,next); //计算next while(i=m) return(i-m+1); //匹配成功 else return(0); }

void main() { SString S,T; int pos,n; cout<<\输入主串S:\\n\ cout<<\输入子串T:\\n\ cout<<\输入位置pos:\\n\ if(n=Index_KMP(S,T,pos)) cout<<\首次匹配地址为:\ else cout<<\匹配不成功!\\n\}

【例4.1】编写程序，分别计算模式匹配过程中，BF算法和KMP算法的字符比较次数。 （1）函数int IndexBF(SString S,SString T,int& num)的功能是通过BF算法返回串T在S中首次出现的位置，参数num表示匹配过程中元素的比较次数。

int IndexBF(SString S,SString T,int& num) { int i=0,j=0; num=0; if(Length_SS(T)>Length_SS(S)) return(0); while(S[i+j]&&T[j]) { num++; if(S[i+j]==T[j])j++; //若字符相等，则继续比较后续字符 else{i++; j=0;} //若不相等，则重新开始新一轮比较 } if(!T[j]) return(i+1); //若匹配成功，则返回T首次出现的开始位置 else return(0); //若匹配不成功，则返回0 } （2）函数int IndexKMP(SString S,SString T,int& num)的功能是通过KMP算法返回串T在

-.85.-

第4章 串存储与基本操作的实现

S中首次出现的位置，参数num表示匹配过程中字符元素的比较次数。

int IndexKMP(SString S,SString T,int& num) { int i=0,j=0; //i指向S中第一个比较字符，j指向T中第一个字符 int m=Length_SS(T), n=Length_SS(S); int *next=new int[m]; //定义模式T的next数组 if(m>n) return 0; //匹配不成功返回0值 GetNext(T,next); //计算next num=0; while(i=m) return(i-m+1); //匹配成功 else return(0); }

void main()

{ SString S,T; int n1,n2,num1,num2; while(1) { cout<<\ cin.getline(S,sizeof(S)); cout<<\ cin.getline(T,sizeof(T)); n1=IndexBF(S,T,num1); n2=IndexKMP(S,T,num2); cout<<\ cout<<\ } }

程序运行结果为：

input string S:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab↙ input string T: aaaaaaab↙ Index_BF: n=46,num=368 Index_KMP: n=46,num=98 input string S:

abcdabcdabcdabcde↙

input string T: abcde↙ Index_BF: n=13,num=29 Index_KMP: n=13,num=20 input string S:

ADBADABBAABADABBADADA↙ input string T:

ADABBADADA↙ Index_BF:

-.86.-

第4章 串存储与基本操作的实现

n=12,num=32 Index_KMP:

n=12,num=25

4.4应用举例

【例4.2】应用BF模式匹配函数IndexBF_SS(S,T,pos)实现算法：

int Replace_S(SString &S,SString T,SString V)

该函数的功能是，将定长存储串S中的所有子串T用定长串V来替换。如果操作成功函数返回值1，否则返回值0。 算法思想

假设模式串T的长度为lt，替换串V的长度为lv，先从pos=1的位置开始查找T在S中出现的位置n，如果操作成功，则将S中第n个开始lt个字符替换为串值V，并且pos=n+lv，继续开始下一轮的查找和替换过程，直到查找失败为止。 算法实现

int Replace_S(SString &S,SString T,SString V) { int n,pos=1; int lt=Length_SS(T),lv=Length_SS(V); while(n=IndexBF_SS(S,T,pos)) { if(!Replace_SS(S,n,lt,V))return 0; pos=n+lv; } return 1; }

【例4.3】应用BF模式匹配函数IndexBF_SS(S,T,pos)实现算法：

int Replace_H(HString &S,HString T,HString V)

该函数的功能是，将堆分配存储串S中的所有子串T用堆分配存储串V来替换。如果操作成功函数返回值1，否则返回值0。

int Replace_H(HString &S,HString T, HString V) { int n,pos=1,lt=T.length,lv=V.length; while(n=IndexBF_SS(S.ch,T.ch,pos)) { if(!Replace_HS(S,n,lt,V)) return 0; pos=n+lv; } return 1; } 演示程序代码

串替换函数Replace_S()、Replace_H()的函数调用演示程序 void main () {

-.87.-

第4章 串存储与基本操作的实现

SString S1,T1,V1; HString S2,T2,V2; cout<<\《串替换函数演示程序》:\\n\ cout<<\ cout<<\ cout<<\ StrAssign_HS(S2,S1); StrAssign_HS(T2,T1); StrAssign_HS(V2,V1); if(Replace_S(S1,T1,V1)) cout<<\定长替换结果为:\\n\ else cout<<\定长替换失败!\\n\ if(Replace_H(S2,T2,V2)) cout<<\堆分配替换结果为:\\n\ else cout<<\堆分配替换失败!\\n\}(程序运行结果略)

【例4.4】编程计算定长存储串S中所含不同字符的总数以及该串中每个字符的个数。 算法思想

首先定义结构体类型：struct num{char ch;int n;};以及该类型的数组a[]，其中ch表示字符串S中的不同字符，n表示字符出现的次数。再对串S中的每个字符ch，在数组a中逐个扫描，如果查找成功，相应的字符数加1，否则在a中添加一个新字符，其个数置为1。 算法实现

void ch_num() { SString S; struct num{char ch;int n;}; num a[MAXLEN]; int i=0,j,k=0; char ch; cout<<\输入一个字符串:\\n\ cin.getline(S,MAXLEN); while(ch=S[i++]) { for(j=0;j-.88.-

第4章 串存储与基本操作的实现

4.5习 题

一、简答题

1．串和空串有和不同？

2．两个字符串相等的充要条件是什么？ 3．串的3种存储表示方法是什么？

4．分别写出下面各个模式串的next数组：

（1）aaabcaab (2)abcabca (3)babbabab (4)abcaabbabcabaac

5．设s=”I AM A STUDENT”，t=”GOOD”，q=”WORKER”，下面各个操作的结果是什么？ (1) StrLength(s)；(2) StrLength(t)；(3) SubString(s,8,7)；(4) SubString(t,2,1)；(5) Index(s,”A”)；(6) Index(s,t)；(7) Replace(s,”STUDENT”,q)；(8) Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。 6．执行以下函数的显示结果是什么？ void demonstrate(){

StrAssign(s,”THIS IS A BOOK”);

Replace(s,SubString(s,3,7),”ESE ARE”); StrAssign(t,Concat(s,”S”));

StrAssign(u,”XYXYXYXYXYXY”); StrAssign(v,SubString(u,6,3); StrAssign(w,”W”);

Printf(“%s%s%s%s%s%s”,”t=”,t,”,v=”,v,”,u=”,Replace(u,v,w)); }

二、填空题

1．串是一种特殊的线性表，其特殊性主要体现在（ ）。

2．设有两个串P和Q，那么求Q在P中首次出现的位置的运算被称为（ ）。 3．设串S=”I AM A TEACHER”，那么S的长度为（ ）。

4．设S1=“abcdefg”，S2=“pqrst”，函数Con(x,y)返回x和y的连接串，Subs(S,i,j)返回S中从i个字符开始的j个字符组成的子串，Len(S)返回S的长度，则Con(Subs(S1,2,Len(S2)),Subs(S1,Len(S2),2))的结果是（ ）。 5．在串模式匹配的BF算法中，如果主串S=“ababcabcacbab”，模式串T=“abcac”，匹配过程中的元素比较次数为（ ）次，如果用KMP算法，其比较次数为（ ）次。 6．模式p1=”abaabcac”的next函数值序列是（ ）；模式p2=”abcaabbabcab”的next函数值序列是（ ）。 三、解答题

1．设串以堆分配方式存储，设计一个判等操作的算法Equal(S,T)，如果S与T相等则函数返回1，否则返回0值。

2．设串以定长顺序存储，设计一个串复制操作的算法CopyStr(S,T)，将T的内容复制到S。 3．编写一个算法SubsNum(S,T)，返回串T在S中重复出现的次数（子串不能重叠）。 4．编写一个算法MaxNext(T,&m,&n)，该操作计算T中出现的第一个最长重复子串的位置m及其长度n。

-.89.-

第4章 串存储与基本操作的实现

5．假定串以堆分配方式存储，编写一个实现串通配符匹配的函数Pattern_Index(S,T)，其中通配符只有???，它可以和任一个字符匹配成功。

6．设串以堆分配方式存储，设计一个串置换操作的算法Replace(S,T,X)。该操作将S中所有不重复的子串T替换为串X。

7．假定串以定长顺序存储，设计一个求最长公共子串的算法MaxSubs(S,T,&m,&n)。该操作返回S、T的最长公共子串在S中首次出现的开始位置m和长度n。

4.6 上机实验

本章上机实验的主要目的在于使学生熟悉掌握串类型数据的实现方法和文本模式匹配方法，熟悉文字处理软件的基本设计方法，以及对于较为复杂问题的分解求精方法。

实验题目 串基本操作的演示

【问题描述】

定义一个串数据类型，并在此基础上编写设计一个串的基本操作演示系统。 【基本要求】

用堆分配存储结构实现对HString串类型数据的最小操作子集，并在此基础上进一步实现关于串的其它较为复杂的操作。

利用串的基本操作函数构造一个串处理系统，该系统循环往复地处理用户输入的每一条命令，直至出现终止程序的命令为止。系统具有以下基本功能：

（1）串赋值；（2）判断两个串是否相等；（3）串联接；（4）求串的长度；（5）求子串；（6）子串定位；（7）串替换；（8）显示串内容；（9）串删除；（10）退出。

在该系统的执行过程中，如果在命令行中输入的是一个串常量，则应首先建立它。基本操作函数的结果（即函数值）如果是一个串，则应在尚未分配的区域内重新分配空间存放。 【测试数据】

由设计者自行指定。 【实现提示】

（1）串的数据类型HString应定义为： struct HString

{ char *ch; //串变量中字符数组的首地址 int length; //串的长度 };

（2）演示系统的主结构是一个串头表StrHeadList，可定义为： struct StrHeadList

{ HString StrHead[100]; //100为串数目的最大值 int CurNum; //当前系统中串的总数 };

系统在执行过程中，将各个串的头指针依次存储与串头数组StrHead中（假定串的数目不超过100）。CurNum为系统中现有的串数目，CurNum+1是可为下一个新串头指针分配的位置。

-.90.-

第4章 串存储与基本操作的实现

《习题参考答案》

一、简答题

1．空串和空格串有和不同？

2．两个字符串相等的充要条件是什么？ 3．串的3种存储表示方法是什么？

4．分别写出下面各个模式串的next数组：

（1）aaabcaab (2)abcabca (3)babbabab (4)abcaabbabcabaac （1）{-1 0 1 2 0 0 1 2}，（2）{-1 0 0 0 1 2 3}， （3）{-1 0 0 1 1 2 3 2}，（4）{-1 0 0 0 1 1 2 0 1 2 3 4 2 1 1}

5．设s=”I AM A STUDENT”，t=”GOOD”，q=”WORKER”，下面各个操作的结果是什么？ (1) StrLength(s)；(2) StrLength(t)；(3) SubString(s,8,7)；(4) SubString(t,2,1)；(5) Index(s,”A”)； (6) Replace(s,”STUDENT”,q)；(7) Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))。 6．执行以下函数的显示结果是什么？ void demonstrate(){

StrAssign(s,”THIS IS A BOOK”);

Replace(s,SubString(s,3,7),”ESE ARE”); StrAssign(t,Concat(s,”S”));

StrAssign(u,”XYXYXYXYXYXY”); StrAssign(v,SubString(u,6,3); StrAssign(w,”W”);

printf(“%s%s%s%s%s%s”,”t=”,t,”,v=”,v,”,u=”,Replace(u,v,w)); }

二、填空题

1．串是一种特殊的线性表，其特殊性主要体现在

（1）串中的元素只能是字符，而线性表中的数据元素可以是如何类型的数据； （2）串的操作对象是串和子串，而线性表的操作对象是数据元素。

2．设有两个串P和Q，那么求Q在P中首次出现的位置的运算被称为（串的模式匹配）。 3．设串S=”I AM A TEACHER”，那么S的长度为（14）。

4．设S1=“abcdefg”，S2=“pqrst”，函数Con(x,y)返回x和y的连接串，Subs(S,i,j)返回S中从i个字符开始的j个字符组成的子串，Len(S)返回S的长度，则Con(Subs(S1,2,Len(S2)),Subs(S1,Len(S2),2))的结果是（”bcdefef”）。

5．在串模式匹配的BF算法中，如果主串S=“ababcabcacbab”，模式串T=“abcac”，匹配过程中的元素比较次数为（16）次，如果用KMP算法，其比较次数为（12）次。 6．模式p1=”abaabcac”的next函数值序列是（{-1 0 0 1 1 2 0 1}）；模式p2=”abcaabbabcab”的next函数值序列是（{-1 0 0 0 1 1 2 0 1 2 3 4}）。 三、解答题

1．设串以堆分配方式存储，设计一个判等操作的算法Equal(S,T)，如果S与T相等则函数返回1，否则返回0值。

int Equal(HString S,HString T) { int i=0;

-.91.-

第4章 串存储与基本操作的实现

if(S.length!=T.length)return(0); HString S,T; while(i

2．设串以定长顺序存储，设计一个串复制操作的算法CopyStr(S,T)，将T的内容复制到S。 void CopyStr(SString &S,SString T) { for(int i=0;S[i]=T[i];i++);}

3．编写一个算法SubsNum(S,T)，返回串T在S中重复出现的次数（子串不能重叠）。 int SubsNum(SString S,SString T) int n; { SString S,T; int num=0,pos=1,len=Length_SS(T); cout<<\ while(pos=IndexBF_SS(S,T,pos)) cout<<\ { num++; pos+=len; } cout<<\ return(num); cout<<\} n=SubsNum(S,T); void main() cout<<\在S中重复出现\次.\\n\{ }

4．编写一个算法MaxNext(T,&m,&n)，该操作计算T中出现的第一个最长重复子串的位置m及其长度n。

int Max(int *next,int n)//计算数组next[n+1]的最大元素 { int m=next[0],i;

for(i=1;i<=n;i++)if(next[i]>m)m=next[i]; return(m); }

void MaxNext(SString T,int &m,int &n) {

int len=Length_SS(T),i,k,max; //len为串长

int *next=new int[len+1]; //动态分配next数组，长度=len+1 char *p,*str=new char[len+2]; //动态分配串str for(i=0;str[i]=T[i];i++); //复制T到str中

str[i++]='#'; //str中追加追加一个非零字符'#' str[i]='\\0';

GetNext(str,next); //计算str的next数组 m=1;n=Max(next,len); p=str+1;k=len-1;

for(i=2;i

-.92.-

第4章 串存储与基本操作的实现

{ GetNext(p++,next); //计算下一个next数组 max=Max(next,k); if(max>n){ m=i;n=max; } } }

void main() {

int n,m; SString S;

cout<<\cin.getline(S,sizeof(S)); cout<<\MaxNext(S,m,n);

cout<<\位置为\重复串的最大长度为\}

input string S:21345345645676789034553456 S=21345345645676789034553456 位置为5,重复串的最大长度为5. Press any key to continue

input string S:asefsdr12345sdydthf12345 S=asefsdr12345sdydthf12345

位置为8,重复串的最大长度为5.

5．假定串以堆分配方式存储，编写一个实现串通配符匹配的函数Pattern_Index(S,T)，其中通配符只有???，它可以和任一个字符匹配成功。

int Pattern_Index(HString S,HString T)//求T在S中首次出现的位置，字符???为通配符 { int i=0,j=0;

if(S.length

{ if(S.ch[i+j]==T.ch[j]||S.ch[i+j]=='?'||T.ch[j]=='?') j++; //若字符相等或有一个字符为'?'，则继续比较后续字符 else {i++; j=0;} //若不相等，则重新开始新一轮比较 }

if(j==T.length) return(i+1); //若匹配成功，则返回T首次出现的开始位置 else return(0); //若匹配不成功，则返回0 }

6．设串以堆分配方式存储，设计一个串置换操作的算法Replace(S,T,X)。该操作将S中所有不重复的子串T替换为串X。

void Replace(HString &S,HString T,HString X) { int n,pos=1,lt=T.length,lx=X.length; while(n=IndexBF_SS(S.ch,T.ch,pos)) { Replace_HS(S,n,lt,X); pos=n+lx;} }

7．假定串以定长顺序存储，设计一个求最长公共子串的算法MaxSubs(S,T,&m,&n)。该操作

-.93.-

第4章 串存储与基本操作的实现

返回S、T的最长公共子串在S中首次出现的开始位置m和长度n。 void MaxSubs(HString S,HString T, void main()

int &m,int &n) { char s1[255],s2[255];

{ int i,k=T.length,pos; HString S,T; HString sub; int m,n; m=1,n=0; cout<<\ if(k>S.length)k=S.length; cin.getline(s1,255); for(i=k;i>0;i--) cout<<\ { pos=1; cin.getline(s2,255); while(SubString_HS(sub,T,pos++,i)) StrAssign_HS(S,s1); if(m=IndexBF_SS(S.ch,sub.ch)) StrAssign_HS(T,s2); { n=i; return; } MaxSubs(S,T,m,n); } cout<<\} }

-.94.-

本文来源：https://www.bwwdw.com/article/pbjv.html