串类型的定义串的表示和实现串的模式匹配算法.ppt

《串类型的定义串的表示和实现串的模式匹配算法.ppt》由会员分享，可在线阅读，更多相关《串类型的定义串的表示和实现串的模式匹配算法.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 第第4 4章章 串串串类型的定义串的表示和实现串的模式匹配算法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望 2 第第4 4章章 串串重点:(1)ADT串的设计、实现方法和基本操作；(2)串的简单模式匹配算法，KMP算法。难点:串的模式匹配算法中的KMP算法。本章重点难点3 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4 第第4 4章章 串串4.1串类型的定义串类型的定义 串是由零个或多个字符组成的有限序列。记为：s=”a1a2

2、an”(n0)其中，s是串的名，用双引号括起来的字符序列是串的值。(1)串的长度:串中字符的数目n。(2)空串(Null string):长度为零的串。(3)子串:串中任意个连续的字符组成的子序列。p 串的有关术语p 串(String)的定义 5 第第4 4章章 串串4.1串类型的定义串类型的定义 (4)主串 包含子串的串相应地称为主串。(5)串相等 只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。(6)空格串(空白串)(blank string)由一个或多个空格组成的串。要和“空串”区别，空格串有长度就是空格的个数。p 串的有关术语 6 第第4 4章章 串串4.1串类型的定

3、义串类型的定义 (1)串数据对象约束为字符集。(2)基本操作的对象不同，线性表以“单个元素”为操作对象；串以“串的整体”为操作对象，操作的一般都是子串。p 串与一般线性表的区别 7 第第4 4章章 串串ADTString数据对象数据对象：数据关系数据关系：基本操作：基本操作：ADTStringp串的ADT定义见下页见下页Dai|aiCharacterSet,i=1,2,.,n,n0R1|ai-1,aiD,i=2,.,n4.1串类型的定义串类型的定义 8 第第4 4章章 串串p基本操作：StrAssign(&T,chars)/根据串常量根据串常量chars生成串生成串TStrCopy(&T,S)

4、/把串把串S中内容拷贝到中内容拷贝到T串串DestroyString(&S)/销毁串销毁串SStrEmpty(S)/判断串是否空判断串是否空StrCompare(S,T)/比较串比较串S和和TStrLength(S)/求串长求串长Concat(&T,S1,S2)/连接串连接串4.1串类型的定义串类型的定义 9 第第4 4章章 串串p基本操作：SubString(&Sub,S,pos,len)/求子串求子串Index(S,T,pos)/子串定位子串定位ClearString(&S)/清空串清空串SStrDelete(&S,pos,len)/删除子串删除子串Replace(&S,T,V)/把串把串

5、S中符合中符合T的子串替换的子串替换StrInsert(&S,pos,T)/插入子串插入子串4.1串类型的定义串类型的定义 10 第第4 4章章 串串4.2 串的表示和实现4.2.1、定长顺序存储表示4.2.2、堆分配存储表示4.2.3、串的块链存储表示 11 第第4 4章章 串串4.2.1定长顺序存储表示定长顺序存储表示#defineMAXSTRLEN255/用户可在用户可在255以内定义最大串长以内定义最大串长typedefunsignedcharSstringMAXSTRLEN+1;/0号单元存放串的长度号单元存放串的长度SstringS;p串的顺序存储C语言实现 12 第第4 4章章

6、串串StatusConcat(SStringS1,SStringS2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，否则，否则FALSE。.returnuncut;/ConcatT1.S10=S11.S10;TS10+1S10+S20=S21S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断未截断4.2.1定长顺序存储表示定长顺序存储表示p串的连接算法 13 第第4 4章章 串串StatusConcat(SStringS1,SStringS2,SString&T)/

7、用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，否则，否则FALSE。.returnuncut;/Concatelseif(S10MAXSTRSIZE)/截断截断T1.S10=S11.S10;TS10+1MAXSTRLEN=S21MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;4.2.1定长顺序存储表示定长顺序存储表示p串的连接算法 14 第第4 4章章 串串StatusConcat(SStringS1,SStringS2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串

8、。若未截断,则返回则返回TRUE，否则，否则FALSE。.returnuncut;/Concatelse/截断截断(仅取仅取S1)T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLENuncut=FALSE;4.2.1定长顺序存储表示定长顺序存储表示p串的连接算法 15 第第4 4章章 串串StatusStrDelete(SSstring&S,intpos,intlen)if(posS0|len=S0)S0=pos-1;elsefor(i=pos+len;i=S0;i+)Si-len=Si;S0=S0-len;returnOK;4.2.1定长顺序存储表示定长顺

9、序存储表示p子串的删除算法 16 第第4 4章章 串串4.2 串的表示和实现4.2.1、定长顺序存储表示4.2.2、堆分配存储表示4.2.3、串的块链存储表示 17 第第4 4章章 串串4.2.2堆分配存储表示堆分配存储表示typedefstructchar*ch;/若是非空串，则按串长分配存储区，若是非空串，则按串长分配存储区，/否则否则ch为为NULLintlength;/串长度串长度HString;p堆分配存储表示的C语言实现 18 第第4 4章章 串串StatusConcat(HString&T,HStringS1,HStringS2)/用用T返回由返回由S1和和S2联接而成的新串联接

10、而成的新串if(T.ch)free(T.ch);/释放旧空间释放旧空间if(!(T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char)exit(OVERFLOW);T.ch0.S1.length-1=S1.ch0.S1.length-1;T.length=S1.length+S2.length;T.chS1.lengthT.length-1=S2.ch0.S2.length-1;returnOK;/Concat4.2.2堆分配存储表示堆分配存储表示p堆分配存储表示的串连接算法 19 第第4 4章章 串串StatusSubString(HStri

11、ng&Sub,HStringS,intpos,intlen)if(posS.length|lenS.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);/释放旧空间释放旧空间if(!len)Sub.ch=NULL;Sub.length=0;/空子串空子串else./完整子串完整子串returnOK;/SubString4.2.2堆分配存储表示堆分配存储表示p堆分配存储表示的求子串算法 20 第第4 4章章 串串Sub.ch=(char*)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2;Su

12、b.length=len;4.2.2堆分配存储表示堆分配存储表示p堆分配存储表示的求子串算法接上页接上页 21 第第4 4章章 串串4.2.3串的块链存储表示串的块链存储表示字符串本身就是一个线性表，可以用链表存储。存储密度存储密度=数据元素所占存储位数据元素所占存储位实际分配的存储位实际分配的存储位存储密度存储密度=840=20%p链表存储字符串的讨论如果每个结点存储一个字符，如采用32位地址，字符按8位记，则存储密度是多少？22 第第4 4章章 串串4.2.3串的块链存储表示串的块链存储表示结论：采用普通链表存储字符串，存储密度非常低，浪费空间严重。p链表存储字符串的讨论解决办法：一个结点

13、存储多个字符。这就是串的块链存储。23 第第4 4章章 串串#defineCHUNKSIZE80typedefstructChunk/结点结构结点结构charchCUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构串的链表结构Chunk*head,*tail;/串的头和尾指针串的头和尾指针intcurlen;/串的当前长度串的当前长度LString;4.2.3串的块链存储表示串的块链存储表示p串的块链存储的C语言实现 24 第第4 4章章 串串4.3 串的模式匹配算法4.3.1 模式匹配简单算法4.3.2 模式匹配KMP算法 25 第第4 4

14、章章 串串4.3串的模式匹配算法串的模式匹配算法初始条件：串S和T存在，T是非空串，1posStrLength(S)。INDEX(S,T,pos)p串匹配(查找)的定义操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。26 第第4 4章章 串串4.3.1 模式匹配简单算法intIndex(SStringS,SStringT,intpos)i=pos;j=1;while(i=S0&jT0)returni-T0;elsereturn0;/Index 27 第第4 4章章 串串讨论下面这种情况的时间复杂性，设S串长为n，T串长为m。S：ab

15、cdefghjkllkcdeT：jkl4.3.1模式匹配简单算法模式匹配简单算法p时间复杂性分析假设从第i个位置匹配成功，前i-1次共比较了i-1次。第i次比较了m次,共比较了i+m-1次。i从1到n-m+1,共(n+m)(n-m+1)/2平均需比较(n+m)/2最好的情况平均时间复杂度为O(n+m)28 第第4 4章章 串串讨论下面这种情况的时间复杂性，设S串长为n，T串长为m。S：0000000000000000001T：00000014.3.1模式匹配简单算法模式匹配简单算法若第i趟比较成功，共比较了多少次？前i-1趟比较每次都比较m次，第i趟也比较m次共im次，i从1到n-m+1共比较

16、了(n-m+2)(n-m+1)m/2平均比较次数(n-m+2)m/2最坏的情况时间复杂度为O(n m)p时间复杂性分析 29 第第4 4章章 串串4.3 串的模式匹配算法4.3.1 模式匹配简单算法4.3.2 模式匹配KMP算法 30 第第4 4章章 串串主串S：子串T：4.3.1模式匹配模式匹配KMP算法算法a b c d c c d d e例例a b c d e1 2 3 4 5 6 7 8 9ij下图中主串游标i指向5，子串中游标j指向5，按照简单模式匹配算法两处不相等时j回到1，i回到2，继续比较，分析在这种情况下，这样做有没有意义？结论：没有意义。p事例讨论 31 第第4 4章章 串

17、串主串S：子串T：4.3.1模式匹配模式匹配KMP算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ij结论：j回到1，i回到2没有意义。例例下图中主串游标i指向8，子串中游标j指向8，按照简单模式匹配算法两处不相等时j回到1，i回到2，继续比较，分析在这种情况下，这样做有没有意义？在什么情况下才有意义？p事例讨论 32 第第4 4章章 串串主串S：子串T：4.3.1模式匹配模式匹配KMP算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ijp事例讨论

18、结论：只有i回到5，j回到1才有意义。如下图。主串S：子串T：a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ij与原来的比较图进行对比，看有什么发现？33 第第4 4章章 串串主串主串S：子串子串T：4.3.1模式匹配模式匹配KMP算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ijp事例讨论结论：可以i不动，j回到4。如下图。pKMP算法的思想主串指针不回溯，模式串向后滑动至某个位置上。34 第第4 4章章 串串主串S：子串T：4.3.1模式匹配模式匹

19、配KMP算法算法a b c d a b c d a b c f ea b c d a b c f1 2 3 4 5 6 7 8 9ijp子串游标滑动到k必须满足的条件结论：可以i不动，j回到4。如下图。与原来的比较图进行对比，看有什么发现？a b c d a b c fj 35 第第4 4章章 串串假如j滑动到k,如果比较有意义:必须满足:“t1t2tk-1”=“si-k+1si-k+2si-1”“tj-k+1tj-k+2tj-1”=“si-k+1si-k+2si-1”（部分匹配）“t1t2tk-1”=“tj-k+1tj-k+2tj-1”(真子串）主串主串S：Si-jSi-j+1Si-j+2S

20、i-2Si-1SiSi+1子串子串T：t1t2tj-2tj-1tj4.3.1模式匹配模式匹配KMP算法算法p子串游标滑动到k必须满足的条件 36 第第4 4章章 串串 maxk|1kj,且且“t1tk-1”=“tj-k+1tj-1”当此集合非空时当此集合非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。4.3.1模式匹配模式匹配KMP算法算法pnextj函数 37 第第4 4章章 串串intIndex_KMP(SStringS,SStringT,intpos)i=pos,

21、j=1;while(i=S0&jt0)returni-t0;/匹配成功匹配成功elsereturn0;/返回不匹配标志返回不匹配标志4.3.1模式匹配模式匹配KMP算法算法pKMP算法 38 第第4 4章章 串串(1)next1=0;表明主串从下一字符表明主串从下一字符si+1起和模式串起和模式串重新开始匹配。重新开始匹配。i=i+1;j=1;4.3.1模式匹配模式匹配KMP算法算法p求next函数值(2)设设nextj=k，则，则nextj+1=?若若tk=tj，则有，则有“t1tk-1tk”=“tj-k+1tj-1tj”，如果在如果在j+1发生不匹配发生不匹配:说明说明nextj+1=k+

22、1=nextj+1。若若tktj，可把求，可把求next值问题看成是一个模式值问题看成是一个模式匹配问题，整个模式串既是主串，又是子串。匹配问题，整个模式串既是主串，又是子串。39 第第4 4章章 串串求求nextj+1,如果如果tj=tk;则则nextj+1=k+1;如果如果tjtk若若tk=tj，则有，则有“t1tk”=“tj-k+1tj”，nextj+1=k+1=nextk+1=nextnextj+1.若若tk”=tj，则有，则有“t1tk”=“tj-k”+1tj”，nextj+1=k”+1=nextk+1=nextnextk+1.nextj+1=1.4.3.1模式匹配模式匹配KMP算法算法p求next函数值 40 第第4 4章章 串串voidget_next(SStringT,intnext)inti=1,j=0;next1=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;j=nextj;4.3.1模式匹配模式匹配KMP算法算法p求next函数算法 41 第第4 4章章 串串本章小结本章小结 熟练掌握：(1)串的定义、性质和特点；(2)ADT串的设计、实现方法和基本操作；(3)朴素模式匹配算法；