数据结构版全集课件第4章串

11第四章串

课前索引

【学习目标】

1.理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。

2.理解串类型的各种存储表示方法。

3.理解串匹配的各种算法。22【重点和难点】

相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。33

串的类型定义、串的存储表示、串匹配、KMP算法。【学习指南】

虽然目前各常用的高级语言中都已经实现了串类型，但由于它是通过软件实现的，因此作为一个软件工作者还是应该了解串的实现方法。本章没有必须完成的算法设计题，如果有兴趣可以试试以下几个题:4.10，4.13，4.17，4.23，4.28,4.30。其中前2个是练习串的基本操作的应用，后2个是和KMP算法相关的练习。【知识点】44【课前思考】1."串就是线性表"的结论是否正确？

从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。

2.串和线性表的主要差别是什么？

希望你带着这个问题开始这一章的学习，并能在学完这一章的内容之后能得出正确的结论。554.1串的抽象数据类型的定义4.2串的表示和实现4.3 串的模式匹配算法第四章串664.1串的抽象数据类型的定义一、串和基本概念串(String或称字符串

)是零个或多个字符组成的有限序列。一般记作S=‘a1a2a3…an’

（n≥0），S是串名，单引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数n称为该串的长度。空串(EmptyString)：长度为零的串，它不包含任何字符。空格串(BlankString)：将仅由一个或多个空格组成的串。用符号“Φ”表示“空格串"。注意：空串和空格串的不同，例如‘

’和‘’分别表示长度为1的空格串和长度为0的空串。77一、串和基本概念（续）串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，假设有如下4个串：a=“BEI”，b=“JING”，c=“BEIJING”，d=“BEIJING”串a、b、c、d的长度分别为：3、4、7、8。串a、b是串c、d的子串。子串a、b在主串c中的位置分别为1、4。特别地，空串是任意串的子串，任意串是其自身的子串。88串相等：当且仅当两个串的值相等，即只有当两个串的长度相等，并且各对应位置的字符都相等时才相等。试看下例2个串：

a=“BEIJING”，b=“BEIJING”c=“BEIJING”，d=“BEIJING”一、串和基本概念（续）通常在程序中使用的串可分为两种：串变量和串常量。串常量与整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能引用不能修改。串变量和其它类型的变量一样，其取值是可以改变的。99二、串的抽象数据类型的定义如下：ADT

String{

数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}串是有限长的字符序列，由一对单引号相括，如:astring1010

基本操作：

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)pare(S,T)

StrLength(S)

Concat(&T,S1,S2)1111SubString(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)

ClearString(&S)}ADT

String1212

StrAssign(&T,chars)

初始条件：chars是字符串常量。

操作结果：把chars赋为T的值。StrCopy(&T,S)

初始条件：串S存在。

操作结果：由串S复制得串T。

DestroyString(&S)

初始条件：串S存在。

操作结果：串S被销毁。1313StrEmpty(S)

初始条件：串S存在。

操作结果：若S为空串，则返回TRUE，

否则返回FALSE。

表示空串，空串的长度为零。1414pare(S,T)

初始条件：串S和T存在。

操作结果：若ST，则返回值0；

若ST，则返回值0；

若ST，则返回值0。例如：pare(data,state)<0pare(cat,case)>01515StrLength(S)

初始条件：串S存在。

操作结果：返回S的元素个数，

称为串的长度。1616Concat(&T,S1,S2)

初始条件：串S1和S2存在。

操作结果：用T返回由S1和S2

联接而成的新串。例如：

Concat(T,man,kind)

求得T=mankind1717

SubString

(&Sub,

S,pos,len)初始条件：

串S存在，1≤pos≤StrLength(S)

且0≤len≤StrLength(S)-pos+1。

//pos+len-1<=StrLength(S)操作结果：用字符串变量Sub

返回串S中的

第pos个字符起长度为len的子串。1818

SubString(sub,commander,4,

3)

求得sub=man；

SubString(sub,commander,4,7)sub=？

SubString(sub,comman,7,2)sub=？例如：SubString(sub,student,5,0)=起始位置和子串长度之间存在上述约束关系，即

pos+len-1<=StrLength(S)长度为0的子串为“合法”串1919

Index(S,T,pos)

初始条件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。

操作结果：若主串S中存在和串T值相同

的子串,则返回它在主串S中第pos个

字符之后第一次出现的位置；

否则函数值为0。

主串S可能存在多个子串，本算法要求从主串中指定位置第pos个字符开始，依次向后查看子串在主串中第一次出现的位置。2020假设S=abcaabcaaabc,T=bca

Index(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=0；

“子串在主串中的位置”意指子串在主串中首次出现时，子串的第一个字符在主串中的位序。Index(S,T,pos)算法是求从主串中指定的位置开始，子串在主串中首次出现时的位置。2121

Replace(&S,T,V)

初始条件：串S,T和V均已存在，

且T是非空串。

操作结果：用V替换主串S中出现

的所有与（模式串）T

相等的不重叠的子串。2222例如：假设S=abcaabcaaabca，T=bca若V=

x，则经置换后得到

S=axaxaax若V=bc，则经置换后得到

S=abcabcaabc，而不是S=abcbcabc2323StrInsert(&S,pos,T)

初始条件：串S和T存在，

1≤pos≤StrLength(S)＋1。

操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到

S=character2424StrDelete(&S,pos,len)

初始条件：串S存在，且

1≤pos≤StrLength(S)-len+1。

操作结果：从串S中删除第pos个字符

起长度为len的子串。

例如：S=chater，则执行StrDelete(S,4,2)之后得到

S=char2525ClearString(&S)

初始条件：串S存在。

操作结果：将S清为空串。

2626

对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。

gets(str)输入一个串；

puts(str)

输出一个串；

strcat(str1,str2)串联接函数；

strcpy(str1,str2,k)串复制函数；

strcmp(str1,str2)串比较函数；

strlen(str)求串长函数；例如：C/C++语言函数库中提供下列串处理函数：2727在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较pare、求串长StrLength、串联接Concat、求子串SubString等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。2828例如，可利用串比较、求串长和求子串等操作实现子串定位函数Index(S,T)。

即查看在母串S中是否存在和T匹配的子串,若存在，则返回它在主串S中第一次出现的位置，否则返回0。

假设S=‘abcaabda’

，T=‘abda’

如何实现？算法思想：从母串S中的第一个字符开始的Length（T）个字符与子串T比较，若相等，则返回1；否则再从S中第二个字符开始的Length（T）个字符与子串T比较，如此反复，直到匹配成功或主串S中的字符已被取尽。这个算法可以用求子串函数SubString(&Sub,S,pos,len)和串比较函数pare(S,T)配合很容易实现。2929变化：子串定位函数Index(S,T)

→

Index(S,T,pos)实现Index(S,T,pos)算法的基本思想为：从主串S中取“从第i个字符起、长度和串T相等的子串”与串T比较，若相等，则求得函数值为i，否则i值增1直至找到和串T相等的子串或者串S中不存在和T相等的子串为止。即求使下列等式

pare(SubString(sub，S,i,StrLength(T))，T)==0

成立的i值。i的初值应为pos，在找不到的情况下，i的终值应该是n-m+1，其中，n为S串的长度，m为T串的长度（n-i+1≥m长度不等，串不等，不用再比较）。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回03030

利用串比较、求串长和求子串等操作实现

子串定位函数Index(S,T,pos)。

pare(SubString(S,i,StrLength(T)),T)?0

S串T串

T串iposn-m+1算法的基本思想为：演示

T串3131intIndex(StringS,StringT,intpos){4-1-1//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，//则返回第一个这样的子串在S中的位置，否则返回0if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);//取得从第i个字符起长度为m的子串if(pare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;//S中不存在与T相等的子串}//Index3232串的置换函数Replace(&S,T,V)

：

实现“置换”操作的基本思想为：由S和V生成一个新的串news。首先将它初始化为一个空串，然后重复下列两步直至“查找不成功”为止：

1)自pos(=1)位置起在串S中查找和T相同的子串；

2)将S中不被置换的子串（即从pos起到和T相同子串在S中的位置之前的字符序列）和V相继联接到news串上。

最后尚需将S中不被置换的字符序列联接到news串中，并将所得的新串赋给串S。

4-1-2

用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。3333voidreplace(String&S,StringT,StringV)

{//以串V替代串S中出现的所有和串T相同的子串

n=StrLength(S);m=StrLength(T);

StrAssign(news,NullStr);

//初始化news串为空串

pos=1;i=0;

while(pos<=n-m+1)//pos+m-1<=n

{i=Index(S,T,pos);

//从pos指示位置起查找串T

if(i!=0){

SubString(sub,S,pos,i-pos);//取不被置换的子串[pos,i-1]

Concat(news,news,sub);//联接S串中不被置换部分

Concat(news,news,V);

//联接V串

pos=i+m;

//pos移至继续查询的起始位置

}//if

}//while

SubString(sub,S,pos,n-pos+1);//剩余串[pos,n]

Concat(S,news,sub);

//联接剩余子串并将新的串赋给S}3434

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别。

在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。3535

在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。4.2串的表示和实现3636一、串的定长顺序存储表示二、串的堆分配存储表示三、串的块链存储表示3737//一般的实现方法

#defineMAXSTRLEN255

//用户可在255以内定义最大串长

typedef

unsignedchar

Sstring[MAXSTRLEN+1];

//定义Sstring为串数据类型，是一个无符号的一维字符数组。

//相当于unsignedchar

s[MAXSTRLEN+1];

0号单元存放串的长度

//Sstrings;一、串的定长顺序存储表示用定长数组

//简单的实现方法：#defineMAX255chars[M]；注：C语言中，字符串以“\0”作为结束标志，占一字符Sstring类型的串的最大长度为MAXSTRLEN-13838

按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。

串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”。特点:3939StatusConcat(SString&T

，SStringS1,SStringS2){//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。

returnuncut;}//Concat例如：串的联接算法中需分三种情况处理：4-1

T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;

}

if

(S1[0]+S2[0]<=MAXSTRLEN)

{//未截断elseif

(S1[0]<MAXSTRSIZE){//截断else{//截断(仅取S1)T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1…MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;

}

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];

//T[0]==S1[0]==MAXSTRLENuncut=FALSE;

}4040算法的描述与其对应的C/C++语句T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];for（intj=0;j<=S1[0];j++）

T[j]=S1[j];for（intj=0;j<=S2[0];j++）

T[S1[0]+j]=S1[j];4141二、串的堆分配存储表示

在C和C++语言中，提供一个称之为“堆”的共享空间，可以在程序运行过程中，系统利用函数malloc()和free()动态地申请或释放一块连续空间。由于在C和C++语言中可以用指针对数组进行访问和操作，在串的存储和操作上也可以充分利用上述特性。串的堆分配存储就是为存储串值的数组空间可以进行动态分配，而不是静态分配的。4242

typedef

structhstring{char*ch;//若是非空串，则按串长分配存储区，否则ch为NULL

intlength;//串长度

}HString;//HString为堆分配存储时串的数据类型堆分配存储结构的串定义如下：说明：由于串仍然是以数组存储的字符序列表示，因此此类串的操作是先为新生成的串分配一个存储空间，然后进行“字符序列的复制”。

4343

Status

Concat(HString&T,HStringS1,HStringS2)

{//用T返回由S1和S2联接而成的新串，对比定长串操作

if(T.ch)free(T.ch);//释放旧空间

if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW);//对比

T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];//联S1T.length=S1.length+S2.length;

T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];];//联S2returnOK;}//Concat4444

Status

SubString(HString&Sub,HStringS,intpos,intlen)

{

//用Sub返回串S的第pos个字符起长度为len的子串

1≤pos≤StrLength(S)，且0≤len≤StrLength(S)-pos+1。

if(pos<1||pos>S.length||len<0||len>S.length-pos+1)

returnERROR;

if(Sub.ch)free(Sub.ch);

//释放旧空间

if

(!len)

{

Sub.ch=NULL;Sub.length=0;

}//空子串

else{Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;}//

完整子串

return

OK;}//SubString4545三、串的块链存储表示

也可用链表来存储串值，由于串的特殊性（每个数据元素是一个字符），因此用链表存储时，存在一个存储密度的问题(即存在一个“结点大小”的问题)，即一个结点可以存一个元素，也可存多个；通常一个结点中存放的不是一个字符，而是一个子串，最后一个结点可能没占满，常用“#”填充。结点大小CHUNKSIZE为4的串的链式结构

为了便于进行诸如串的联接等操作，链表中还附设有尾指针，并且由于串的长度不一定是结点大小的整数倍（链表中最后一个结点中的字符并非都是有效字符），因此还需要一个指示串长的域。称如此定义的存储结构为串的块链存储结构。Datanext单链表结点结构（32位机）4646

#defineCHUNKSIZE80

//可由用户定义的块大小

typedefstructChunk{//结点结构

charch[CUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串的链表结构

Chunk*head,*tail;//串的头和尾指针

intcurlen;//串的当前长度

}LString;串的块链存储结构定义如下：4747串的块链存储密度

在以链表存储串值时，结点大小的选择直接影响串处理的效率。存一个元素，操作方便，但浪费空间，存多个操作不方便。折中处理：定义串的存储密度为存储密度

=数据元素所占存储位实际分配的存储位48484.3 串的模式匹配算法

子串定位运算又称为模式匹配(PatternMatching)或串匹配(StringMatching)，这是串的一种重要操作，应用非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。4949初始条件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串，返回它在主串S中第pos个字符之后第一次出

现的位置；否则函数值为0。

首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)5050

在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设：

S=‘s1s2…sn’T=‘t1…tm’

串的匹配实际上是对于合法的位置0≦pos≦n-m+1依次将目标串中的子串s[pos..pos+m-1]和模式串T[1..m]进行比较，若s[pos..pos+m-1]=T[1..m]，则称从位置pos开始的匹配成功，亦称模式串T在目标s中出现；若

s[pos..pos+m-1]≠T[1..m],则称从位置pos开始的匹配失败。这样，串匹配问题可简化为是找出某给定模式串T在指定目标S中首次出现的位置。

S串T串

T串iposn-m+1

T串INDEX(S,T,pos)5151

下面讨论以定长顺序结构表示串时的几种串匹配算法。一、简单算法二、首尾匹配算法三、KMP算法(D.E.Knuth,V.R.Pratt,J.H.Morris)#defineMAXSTRLEN255typedef

unsignedchar

Sstring[MAXSTRLEN+1];//定义Sstring为串数据类型，

0号单元存放串的长度5252int

Index(SStringS,SStringT,intpos)

演示

{

//返回子串T在主串S中第pos个字符之后的位置。若不存在，

//则函数值为0。其中，T非空，1≤pos≤StrLength(S)。

i=pos;j=1;while(i<=S[0]&&j<=T[0])

{//j>T[0]时，等

if(S[i]==T[j]){++i;++j;}//继续比较后继字符

else{i=i-j+2;j=1;}

//i,j指针后退重新开始匹配

}//在一次匹配失败之前，i随j同步改变,匹配失败后i=i-j+1+1

if(j>T[0])return(i-T[0]);

elsereturn0;}//Index一、简单算法教材：时间复杂度：O（n*m）

ababcabcacbababcab↓i=10↑j=5

ababcabcabababcab↓i=11↑j=65353

先比较模式串的第一个字符，

再比较模式串的最后一个字符，最后依次比较模式串中从第二个到

第m-1个字符。二、首尾匹配算法举例:假设S=‘aabdabdabda’，T=‘abda’5454

int

Index_FL(SStringS,SStringT,intpos)

{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{}}return0;}检查中间字符的匹配情况k=1;j=2;//首位字符已匹配

while(j<tLength&&S[i+k]==T[j]){++k;++j;}if(j==tLength)returni;else++i;//此次截取的子串不匹配

//重新开始下一次的匹配检测时间复杂度：O（n*m）5555KMP算法的时间复杂度可以达到O(m+n)三、KMP算法(D.E.Knuth,

J.H.Morris，V.R.Pratt,)

S串T串

T串iposn-m+1

T串是因为在匹配过程中指针i没有回溯。KMP算法的核心思想是利用已经得到的部分匹配信息，将模式串向右“滑动”尽可能远的一段距离后继续进行后面的匹配过程。5656KMP算法示意图主串

ababcabcacbab模式串

ababcaba5757ababcabcacbabi=2↓↓i=8↑j=8

ababcabaababcaba↑j=1ababcabaababcaba↓i=3KMP算法原则：i不需回溯，j要用原有的比较信息，尽量少回溯现在的问题是：既然j尽量少回溯，那么i应该与模式串中第几（k）个符号进行比较？（k=3）---KMP算法示意图无需比较？同样i=3,4,5,6,7也无需比较当匹配失败时，已比较的母串中’ab’与模式串中前缀串‘ab’等，此时只需让母串中第i个字符与模式串中第3个比较。从而达到i不需回溯，而j也尽量少回溯，提高匹配效率。方法：当模式串与主串中第i个字符匹配失败时，检查失败前已匹配的模式串中后缀串与前缀串相等时串的长度L,并令k=L+1即可。↑j=3主串S模式串T5858定义：模式串的next函数

若令next[j]=k，则next[j]表明当模式中第j个字符与主串中第i个字符“失配”时，模式串中需重新和主串中第i个字符进行比较的字符的位置。

模式串中next[j]函数的定义如下：从第j个字符之前存在一个字符串和模式串开始的一个字符串相同，这时i不需再回溯。5959‘p1p2……pk-1’=‘pj-k+1

……pj-1’当S[i]!=T[j]

时，已经得到的结果：

S[i-j+1..i-1]=T[1..j-1]→S[i-k+1..i-1]=T[j-k+1..j-1]

若已知

T[1..k-1]==T[j-k+1..j-1]

则有

S[i-k+1..i-1]==T[1..k-1]，即‘p1p2……pk-1’=‘pj-k+1……pj-1’ababcabcacbabababcabaSi-k+1Si-1iTj-k+1Tj-1jT1Tk-1k-1j=8‘p1p2’=‘ab’→k=3Si-j+16060模式串的next函数主串ababcabcacbab模式串ababcaba6161模式串的next[j]的计算举例模式串

ababcabaj=12345678Next[j]=01123123练习：模式串

abaabcacNext[j]=0112231j=12345676262

intIndex_KMP(SStringS,SStringT,intpos){//1≤pos≤StrLength(S)i=pos;j=1;

while(i<=S[0