ch4字符串.ppt

《ch4字符串.ppt》由会员分享，可在线阅读，更多相关《ch4字符串.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、主要内容：一、主要内容：1、串类型的定义 2、串的表示和实现 3、串操作的应用举例二、基本要求：二、基本要求：了解串的应用；掌握串的基本概念、顺序和链式存储结构；掌握串的各种基本运算；熟练掌握顺序存储结构上串的各种操作。第四章第四章 字符串字符串目录目录4.1串的类型和定义4.2串的表示和实现4.3 串的模式匹配算法4.1 4.1 串类型的定义串类型的定义一、串和基本概念一、串和基本概念非数值处理的对象基本上是字符串数据串(string)(或称字符串)-由零个或多个字符组成的有限序列记为:s=“a1a2.an”(n=0)ai(1=i=0数据关系：R1=ai-1.,aj|ai属于D,i=2,

2、.n。基本操作：StrAssign(&T,chars);StrCopy(&T,S);StrEmpty(S);StrCompare(S,T);StrLength(S);ClearString(&S);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);DestroyString(&S)ADT String三、三、串的基本运算概述串的基本运算概述为为描描述述方方便便，假假定定用用大大写写字字母母表表示示串串名名，小小写写

3、字字母母表表示组成串的字符。示组成串的字符。1.串复制 StrCpy(&S,T)表示将T串的值赋给S串。2.联接 Concat(&S,T1,T2)表示将T1串和T2串联接起来，返回到S串中。3.求串长度 StrLen(T)求T串的长度。4.子串 substring(&S,T,i,len)表示截取S串中从第i个字符开始连续len个字符，作为S的一个子串，存入T串。5串比较大小 StrCmp(S,T)比较S串和T串的大小，若ST，函数值为正。6.串插入 SInsert(&S,i,T)在S串的第i个位置插入T串。7.串删除 SDelete(&S,i,len)删除串S中从第i个字符开始连续len个字符

4、。8.求子串位置 index(S,T)求T子串在S主串中首次出现的位置，若T串不是S串的子串，则位置为零。9.串替换 Replace(&S,T,V)将S串中出现所有与T相等的子串，用V串替换。利用上述九种基本运算还可以组合成字符串的其他有关操作.4.2 4.2 串的表示和实现串的表示和实现顺序表示4.2.1 定长顺序表示4.2.2 堆分配存贮表示链式表示4.2.3 块链存贮表示用一组连续的存储单元存储串值的字符序列.在 C语 言 中,用 字 符“0”表 示 串 的 终 结,“0”不计入串长.另一种方法是定长数组表示一个串:#define MAXSTRLEN 255 /串的长度最大为串的长度最大

5、为255typedef unsigned char SStringMAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度,其最大值刚好是其最大值刚好是255.b当超出255个字符时,串的多余内容被舍去,叫做“截断”b以下用串联结和求子串为例介绍这种存储4.2.1 定长顺序存储表示定长顺序存储表示 对串长有两种表示方法：对串长有两种表示方法：（1 1）可使用一个不会出现在串中的特殊字符在）可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，串值的尾部来表示串的结束。例如，C C语言中语言中以字符以字符00表示串值的终结表示串值的终结，这就是为什，这就是为什么在上述定义中

6、，串空间最大值么在上述定义中，串空间最大值maxstrlenmaxstrlen为为256256，但最多只能存放，但最多只能存放255255个字符的原因，因个字符的原因，因为必须留一个字节来存放为必须留一个字节来存放00字符。字符。（2 2）可用下标为零的数据元素来存储串的长度可用下标为零的数据元素来存储串的长度。如：如：PASCALPASCAL语言中的串类型就采用这种方法。语言中的串类型就采用这种方法。分分析析：进行串连接时，由于存储空间有限，连接后的串的长度不确定，所以存在三种情况存在三种情况：（1）两个串的长度之和小于最大存储量两个串的长度之和小于最大存储量：将两个串进行连接。（2）两个串

7、的长度之和大于最大存储值两个串的长度之和大于最大存储值，但第一个串但第一个串的长度比最大存储值要小的长度比最大存储值要小：将第二个串的部分进行连接，长出的部分采用截尾法截尾法处理。（3）连接时第一个串连接时第一个串就已将存储空间用完就已将存储空间用完：不进行连接。v算法4.2：Concat(&T,S1,S2)串联结 实现算法：实现算法：/用T返回S1和S2联接成的新串，若未截断，返回TRUE，否则返回FALSEStatus Concat(SString T,SString S1,SString S2)L1=strLength(S1);L2=strLength(S2);if(strLength(

8、S1)+strLength(S2)=MAXSTRLEN)T0,L1 1 =S1 0,L1-1;TL1,L1+L2 1 =S2 0,L2 1;T L1+L2 =0;return TRUE;else if(L1 MAXSTRLEN)T 0,L1 1 =S1 0,L1 1;T L1,MAXSTRLEN 1 =S2 0,MAXSTRLEN L1-1;T MAXSTRLEN =0;elseT0,L1 =S10,L1;return FALSE;Concat(&T,S1,S2)的算法示意图S1S2T0 maxstrlen0 maxstrlenS10+S20 MAXSTRLEN 时截断部分 分析：分析：求s中

9、从第pos个字符开始长度为len的子串。需判定所给的pos(pos=1&pos=0&len=s.len-pos+1)范围是否合法。实现算法：实现算法：Status SubString(SString Sub，SString S，int pos，int len)/用Sub返回串S的第pos个字符起长度为len的子串。/其中，1posStrLength(S)且0lenStrLength(S)-pos+1。if(pos1|posS0|len0|lenS0-pos+1)return ERROR；Sub1lenSpospos+len-1；Sub0len；return 0K；/SubStrlng2.求子串

10、SubString(&Sub，S，pos，len)算法4.3SSub1 poslen也是用一组连续的存储单元存储串值的字符序列.但存储空间是在程序执行过程中动态分配得到的-动动态态存储分配的顺序表存储分配的顺序表.在C语言中,用字符“0”表示串的终结,“0”不计入串长.typedef struct char*ch;/若是非空串,则按实际长度分配,否则为NULL;int length;/串长度 HString;4.2.2 堆分配存储表示堆分配存储表示HString s;s.ch=NULL;s.length=0;堆分配存贮表示_初始化lengthchsStatus StrInsert(HStrin

11、g&S,int pos,HString T)/1=pos=StrLength(S)+1。在串S的第pos个字符之前插入串T。if(pos S.length)return ERROR;/pos 不合法 if(T.length)/T 非空,则要重新分配空间,插入T if(!(S.cj=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)exit(OVERFLOW);for(i=S.length-1;i=pos-1;-i)/为插入T而腾出位置 S.chi+T.length=S.chi;S.chpos-1.pos+T.length-2=T.ch0.T

12、.length-1;/插入T S.length+=T.length;/if return OK;/StrInsertv算法4.4：StrInsert(&S,pos,T)串插入 Status Concat(HString&T,HString S1,HString S2)if(T.pChar)free(T.pChar);/若T非空，则释放空间/申请空间T.pChar=(char*)malloc(S1.nLength+S2.nLength)*sizeof(char);if(!T.pChar)return OVERFLOW;/计算长度T.nLength=S1.nLength+S2.nLength;/C

13、opy T.pChar 0,S1.nLength-1 =S1.pChar0,S1.nLength 1;T.pChar S1.nLength,T.nLength 1 =S2.pChar 0,S2.nLength 1;return OK;/Concatv算法：Concat(&T,S1,S2)串连接/生成一个值等于串常量s的串T，其中s采用的是标准C的表示法，T采用/是数据结构课程中的表示法。Status StrAssign(HString&T,char*s)if(T.pChar)/若T非空，释放原有的空间free(T.pChar);/取s的长度，没有使用strlen(s);for(i=0,c=s;

14、*c;i+,c+);if(!i)T.pChar=NULL;T.nLength=0;v算法：StrAssign(HString&T,char*s)串赋值 elseT.pChar=(char*)malloc(i*sizeof(char);if(!T.pChar)return OVERFLOW;T.nLength=i;T.pChar0,i 1 =s0,i-1;return OK;Status SubString(HString Sub、HString S，int pos，int len)/用Sub返回串S的第pos个字符起长度为len的子串/其中LposStrLength(s)且0lenStrLen

15、gth(s)-pos+1。if(pos1|posS.Length|len0|lenS.Length-pos+1)return ERROR：if(Sub.ch)free(Sub.ch)；/释放旧空间 if(！len)Sub.chNULL；Sub.length0；/空子串 else Sub.ch (char*)malloc(len*sizeof(char)；/完整子串 Sub.ch0len-1=Spos-1pos+len-2；Sub.lengthlen；return OK;/SubStringv算法：SubString(Sub,S，pos，len)求子串求子串4.2.3 4.2.3 串的链式存储结

16、构串的链式存储结构串作为一种特殊的线性表（数据元素为字符），使用顺序表示时，做插入和删除运算，运算量很大，不方便。链式存贮结构：typedef struct node char data;struct node*next;lstring;直接使用线性链表来存贮字符串：效率太低：一个结点(包括：数据域1字节，指针4字节）适当扩：一个结点的数据域不仅放一个数据元素（字符），而是放多个数据元素块链的引入链式存贮结构定义：块链逻辑结构示意块链逻辑结构示意:IamaC hes eni#.块链存储类型定义：块链存储类型定义：#define nodesize 80typedef struct node ch

17、ar datanodesize;struct node*next;lstring;块链的效率块链的效率每个结点中数据域越大，效率越高。存贮密度：串所占的存贮位存贮密度=实际分配的存贮位4.3 模式匹配操作模式匹配操作 模式匹配操作模式匹配操作就是在主串在主串s s中定位子串中定位子串t t的操作的操作，即在主串s中找到第一个与子串t相等的子串，通常把主串s称为目标串目标串，把子串t称为模式串模式串。模模式匹配成功式匹配成功是指在s中找到一个；不成功则指s中不存在t。串的模式匹配：最重要的运算就是子串的定位。模式匹配操作的实现算法：BruteForceBruteForce算法(BF算法,又称古典

18、或经典又称古典或经典的、朴素的、穷举的）的、朴素的、穷举的）Knuth-Morris-PrattKnuth-Morris-Pratt算法（KMPKMP算法）（特（特点：速度快）点：速度快）BruteForce算法：算法：BFBF算法设计思想：算法设计思想：将主串的第将主串的第pospos个字符和模式的第个字符和模式的第1 1个字符比较，个字符比较，若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符；若若不等不等，从主串的下一字符（，从主串的下一字符（pos+1pos+1）起，重新与第一个起，重新与第一个字符比较。字符比较。结果：结果：直到主串的一个连续子串字符序列与模式相等直到主串的一

19、个连续子串字符序列与模式相等 。返回值。返回值为为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0.0.Int Index(SString S,SString T,int pos)i=pos-1;j=0;m=strlen(S);n=strlen(T);while(im&j=n)return i-n+1;/子串结束，说明匹配成功子串结束，说明匹配成功 else return 0;/IndexBFBF算法的实现算法的实现即即Index（）（）操作的实现操作的实现S=“a b a b c a b

20、c a c b a b”T=T=“a b c a c”pos=5相当于子串向右滑动一个字符位置相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。配的首个字符位置。i ij j简单匹配算法的匹配过程示例例如 T=“abcac”;S=“ababcabcacbab”第一趟匹配 a b a a b c a b c a c b a b (i=3)a b c c (j=3)第二趟匹配 a b b a b c a b c a c b a b (i=2)a a (j=1)第三趟匹配 a b a b c a b b c a c b

21、 a b (i=7)a b c a c c (j=5)第四趟匹配 a b a b b c a b c a c b a b (i=4)a a (j=1)第五趟匹配 a b a b c c a b c a c b a b (i=5)a (j=1)第六趟匹配 a b a b c a b c a c b b a b (i=11)a b c a c (j=6)成功!模式匹配的一种改进算法(KMP算法)KMP算法的改进在于:每一趟匹配过程中出现字符比较不等时,不需要回朔i指针只要利用已经“部分匹配”结果,调整j指针,即将模式向右滑动尽可能远的一段距离,来提高算法效率.上例的KMP算法匹配过程示意如下第一趟

22、匹配 a ba b a b c a b c a c b a b (i=3)a ba b c (j=3)第二趟匹配 a b a a b c a b c a b c a c b a b (i=3-7)a ba b c a c a c (j=1-5)第三趟匹配 a b a b c a b c a cb c a c b a b (i=7-11)(a)b c a c b c a c (j=2-6)显然算法复杂度为O(n+m)KMP算法的基本思想(二)一般情况下,模式串的next函数的定义如下:0 当j=1时nextj=maxk|1kj且“t1.tk-1”=“tj-k+1.tj-1”1 其他情况如:j 1

23、 2 3 4 5 6 7 8 模式串 a b a a b c a c nextj 0 1 1 2 2 3 1 2 KMP算法int Index_KMP(SString S,SString T,int pos)/利用模式串T的next函数求T在主串 /S中第pos个字符之后第一次出现的位置；否则返回。i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功 else return 0;/匹配不成功 /Index_KMP求模式串的next值的算法思想用递推方法求next函数值:next1=0;设nextj=k,则有关系:“t1.tk-1”=“tj-k+1.tj-1”其

24、中1kk 使上述关系成立.那么nextj+1=?,有两种情况:(1)若tk=tj,则表明:“t1.tk”=“tj-k+1.tj”并且不可能存在 kk 使上述关系成立.这就是说 nextj+1=k+1 或 nextj+1=nextj+1(2)若tk tj,则表明:“t1.tk”“tj-k+1.tj”此时求next的问题可看成模式匹配的问题;递推 k=nextk,直到Tk=Tj或k=0;此时 nextj+1=nextk+1 KMP算法仅当模式与主串之间存在许多存在许多“部分部分匹配匹配”的情况的情况下才显得比Brute-Force算法快。Brute-Force算法的时间复杂度为O O（n nm m），但在一般情况下，实际的执行时间近似于实际的执行时间近似于O O（n+mn+m），因此至今仍被采用。KMP算法的最大特点是指示主串的指针不需回指示主串的指针不需回溯溯。BruteForce算法算法 和和KMP算法的比较：算法的比较：改进的算法：改进的算法：KMP算法算法（特点：速度快）（特点：速度快）串匹配算法过程演示串匹配算法过程演示