数据结构第4章(新)

数据结构0第4章串4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法数据结构14.1串类型的定义1.基本概念串(字符串)String：是零个或多个字符组成的有限序列。一般记为：S=‘a1a2...an’(n≥0)

栈、队列：操作受限的线性表。串：取值范围受限的线性表，数据对象约束为字符集。其中S是串的名字,用单引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。串的长度：串中字符的个数n。空串(NullString)：n=0时的串称为空串，用符号“

”表示。数据结构2下面是一些串的例子：

（1）a=‘LIMING’

（2）b=‘PEJINGUNIUERCITY’

（3）c=‘DATASTRUCTURE’

（4）d=‘’

（5）e=‘’

说明：串中包含的字符个数，称为串的长度。

长度为0的串称为空串，它不包括任何字符，上面（4）中的串d是空串,，(5)中的e是包含一个空格符的空格串；串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。另外,通常以字符在序列中的序号为该字符在串中的位置数据结构3子串：串中任意个连续的字符组成的子序列称为该串的子串。“

”为任意串的子串。主串：包含子串的串相应地称为主串。

S为一长度为n的串，其中的字符各不相同，则S的所有子串的个数：

S中互异的非平凡子串（非空且不同于S本身）的个数：特别地，空串是任意串的子串，任意串是其自身的子串。数据结构4位置：字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

A=‘ChinaBeijing’,B=‘Beijing’,C=‘China’,则它们的长度分别为13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。串相等：当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。空格串：由一个或多个空格组成的串。与空串不同。数据结构52.串的基本运算:

串赋值StrAssign(&T,chars)

初始条件:chars是字符串常量。操作结果:生成一个值等于chars的串T。串比较StrCompare(S,T)

初始条件:串S和T存在。操作结果:若S>T,则返回值>0;如S=T,则返回值=0;

若S<T,则返回值<0。"串值大小"是按"词典次序"进行比较的;只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。

数据结构6求串长StrLength(S)

初始条件:串S存在。操作结果:返回串S的长度,即串S中的元素个数。串联接Concat(&T,S1,S2)

初始条件:串S1和S2存在。操作结果:将T返回由S1和S2联接而成的新串。"串联接"操作的结果是生成一个新的串，其值是"将第二的串的第一个字符紧接在第一个串的最后一个字符之后"得到的字符序列。

数据结构7求子串SubString(&Sub,S,pos,len)

初始条件:串S存在,1≤pos≤StrLength(S)且

1≤len≤StrLength(S)-pos+1。操作结果:用Sub返回串S的第pos个字符起长度为len的子串。"子串"指串中任意个连续的字符组成的子序列。如：操作SubString(Sub,"commander",4,3)得到的结果是Sub="man"。显然必须在满足初始条件中规定的"起始位置"和"长度"之间的约束关系时才能求得一个合法的子串。允许len的下限为0是由于空串也是合法串，但实际上求长度为0的子串是没有意义的。数据结构8定位函数intIndex(StringS,StringT,intpos)//T为非空串。若主串S中第pos个字符之后存在与T相等的子//串，则返回第一个这样的子串在S中的位置，否则返回0。{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;elsereturni;}}return0;}数据结构94.2串的表示和实现1.定长顺序存储表示（定长顺序串）＃defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];定长顺序串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似,用一组地址连续的存储单元存储串的字符序列。串长的表示：①以下标为0的数组分量存放串的实际长度；②串值后加入一个不计入串长的结束标记字符，C中“\0”表串值的终结，其ASCⅡ码值为0。超出予定义长度的串值被舍去，称之为“截断”。数据结构10串联接Concat(SString&T,SString

S1,SString

S2)S1[0]+S2[0]≤MAXSTRLEN，T是正确的结果。S1[0]<MAXSTRLEN，而S1[0]+S2[0]>MAXSTRLE

则S2会有部分字符被舍弃。(3)S1[0]=MAXSTRLEN，则S2的全部字符被舍弃，T与S1相等。思考:课本是否有错误,是否遗漏了S1[0]>MAXSTRLEN数据结构11StatusConcat(SString&T,SStringS1,SStringS2){//S1,S2联接后成为新串送入T,0下标变量存

//放串的长度。if(s1[0]+s2[0]<=MAXSTRLEN){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;}

S1S2

TT[0]MAXSTRLEN1558?数据结构12elseif(s1[0]<MAXSTRLEN){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}

S1S2

TMAXSTRLEN1058?数据结构13else{T[1..MAXSTRLEN]=S1[1..MAXSTRLEN];T[0]=MAXSTRLEN;uncut=FALSE;}returnuncut;}//Concat高级语言中，可以观察到串在存储空间不够时会自动截取，并不报错，故这里并不扩展空间。T

S1S2

MAXSTRLEN:558?数据结构14求子串Status

SubString(SString&Sub,SStringS,intpos,intlen){if(pos<0||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}

“字符序列的复制”数据结构15思考：StrCopy如何实现？StatusStrCopy(SString&T,SStringS){}数据结构16S.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1为串S重新分配存储空间,并将S复制到新空间将S的第pos个字符及后面的字符后移，为插入T腾出位置插入T修改串长串插入：在串S的第pos个字符前插入串T数据结构17串插入StatusStrInsert(HString&S,intpos,HStringT)//在串S的pos个字符之前插入串T{if(pos<1||pos>S.length+1)returnERROR;//插入位置不适

if(T.length){if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];S.length+=T.length;}returnOK;}数据结构182.堆分配存储表示（堆串）在C语言中，已经有一个称为“堆”的自由存储空间，并可用malloc（）和free（）函数完成动态存储管理。typedefstruct{char*ch；

intlength；}HString；

比较：

#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];

数据结构193.串的块链存储表示（链串）＃defineCHUNKSIZE<大小>typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head;Chunk*tail;intcurlen;}LString;数据结构20存储密度大，一些操作（如插入，删除）有所不便，引起大量字符移动，适合于在串基本保持静态使用方式时采用；存储密度小，运算处理方便，但存储空间量大，若处理过程中，需大量内外存交换，会影响总效率；串的字符集的大小，也会影响串值存储方式的选取。数据结构21总结（1）空串与空格串是不相同的，空串的长度为0，空格串的长度为包含的空格个数。（2）串是有限个字符的序列，是一种取值范围受限的特殊的线性表。数据结构221.朴素模式匹配算法求子串位置的定位函数Index(S,T,pos).模式匹配：子串的定位操作通常称作串的模式匹配。目标串：主串S。模式串：子串T。匹配成功：若存在T的每个字符依次和S中的一个连续字符序列相等，则称匹配成功。返回T中第一个字符在S中的位置。匹配不成功：返回0。4.3串的模式匹配算法数据结构23第1趟 S abbabaT aba

第2趟 S abbaba T aba

第3趟

S abbaba T aba

第4趟 S abbaba Taba

穷举的模式匹配过程i=i-j+2;j=1;↑j↓i数据结构24子串定位intIndex(SStringS,SStringT,intpos){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])returni-T[0];elsereturn0;}数据结构25朴素模式匹配算法的时间复杂度主串长n；子串长m。可能匹配成功的位置（1~n-m+1)。①最好的情况下，第i个位置匹配成功，比较了（i-1+m）次，平均比较次数：最好情况下算法的平均时间复杂度O(n+m)。②最坏的情况下，第i个位置匹配成功，比较了（i*m）次，平均比较次数：设n>>m，最坏情况下的平均时间复杂度为O(n*m)。数据结构26分析算法的思想：

从主串S的第pos个字符起和模式的第一个字符比较，若相等，继续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较。以此类推，直到模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数返回T首字符在S中的位置；否则匹配不成功。问题：当主串与模式串存在多次部分匹配时，就显得效率低下。如0、1串在T=“00001”,S=“0000000000001”时，每次都有四次的多余比较，而0、1串又是普遍存在的。4.3串的模式匹配算法数据结构272.模式匹配的改进算法-KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。因p1≠p2,s2=p2,必有s2≠p1,又因p1=p3,s3=p3,所以必有s3=p1。因此,第二次匹配可直接从i=4,j=2开始。数据结构28改进：每趟匹配过程中出现字符比较不等时，不回溯主指针i，利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离，继续进行比较。数据结构29s1s2s3…si-j+1si-j+2…si-2si-1sisi+1‖‖‖‖≠

p1p2…pj-2pj-1pjpj+1(在j处匹配不成功)‖‖

p1…pk-1pkpk+1①“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”（部分匹配）②“p1p2…pk-1”=“si-k+1si-k+2…si-1”(k为下一次要与i匹配的位置)③“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”(真子串）数据结构30

max{k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1”}

当此集合非空时

0当j=1时

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

0当j=1时

Next[j]=M{k|1<k<j且‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’}1其它情况例：j12345678

模式串abaabcacnext[j]01122312练习：求下列串的next函数值串：s=“abacabaaad”

0112123422数据结构32voidget_next(charT[],intnext[])

{

//求模式串T的next函数值并存入数组next。

i=1;next[1]=0;j=0;

while(T[j]!='\0'){

if(j==0||T[i]==T[j])

{++i;++j;next[i]=j;}

elsej=next[j];

}

}//get_next

数据结构33intIndex_KMP(SStringS,SStringT,intpos){i=pos,j=1;while(i<S[0]&&j<T[0]){if(j==0||S[i]==T[j]){i++;j++;}else

j=next[j];/*i不变,j后退*/}if(j>T[0])returni-T[0];/*匹配成功*/elsereturn0; /*返回不匹配标志*/}数据结构343、模式匹配的KMP算法

i=2

第一趟主串:acabaabaabcacaabc

子串

abj=2next[2]=1i=2第二趟主串:acabaabaabcacaabc

子串aj=1next[1]=0i=3i=8第三趟主串:acabaabaabcacaabc

子串abaabcj=1j=6next[6]=3i=8i=14第四趟主串:acabaabaabcacaabc

子串abaabcacj=3j=9图4.9利用模式的next函数进行匹配的过程示例参看演示程序

j12345678模式串abaabcacnext[j]01122312数据结构35j1234567891011121314151617模式串abcaabbcabcaabdab0next[j]1112231123456712数据结构36next函数的改进j12345模式aaaabnext