第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.-