41串类型的定义42串的表示和实现43串的模式匹配算法课件.pptx

1、重点:(1)ADT串的设计、实现方法和基本操作；(2)串的简单模式匹配算法，KMP算法。难点:串的模式匹配算法中的KMP算法。本章重点难点 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法4.1 串类型的定义 串是由零个或多个字符组成的有限序列。记为：s=”a1a2an”(n0)其中，s是串的名，用双引号括起来的字符序列是串的值。(1)串的长度:串中字符的数目n。(2)空串(Null string):长度为零的串。(3)子串:串中任意个连续的字符组成的子序列。p 串的有关术语p 串(String)的定义4.1 串类型的定义 (4)主串 包含子串的串相应地称为主串。(5)串

2、相等 只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。(6)空格串(空白串)(blank string)由一个或多个空格组成的串。要和“空串”区别，空格串有长度就是空格的个数。p 串的有关术语4.1 串类型的定义 (1)串数据对象约束为字符集。(2)基本操作的对象不同，线性表以“单个元素”为操作对象；串以“串的整体”为操作对象，操作的一般都是子串。p 串与一般线性表的区别ADT String 数据对象数据对象：数据关系数据关系：基本操作：基本操作：ADT String p 串的ADT定义见下页D ai|aiCharacterSet,i=1,2,.,n,n0 R1|ai-1,a

3、i D,i=2,.,n 4.1 串类型的定义p 基本操作：StrAssign(&T,chars)/根据串常量根据串常量chars生成串生成串T StrCopy(&T,S)/把串把串S中内容拷贝到中内容拷贝到T串串 DestroyString(&S)/销毁串销毁串S StrEmpty(S)/判断串是否空判断串是否空 StrCompare(S,T)/比较串比较串S和和T StrLength(S)/求串长求串长 Concat(&T,S1,S2)/连接串连接串4.1 串类型的定义p 基本操作：SubString(&Sub,S,pos,len)/求子串求子串 Index(S,T,pos)/子串定位子串定

4、位 ClearString(&S)/清空串清空串S StrDelete(&S,pos,len)/删除子串删除子串 Replace(&S,T,V)/把串把串S中符合中符合T的子串替换的子串替换 StrInsert(&S,pos,T)/插入子串插入子串4.1 串类型的定义4.2 串的表示和实现4.2.1、定长顺序存储表示4.2.2、堆分配存储表示4.2.3、串的块链存储表示4.2.1 定长顺序存储表示定长顺序存储表示#define MAXSTRLEN 255 /用户可在用户可在255以内定义最大串长以内定义最大串长 typedef unsigned char SstringMAXSTRLEN+1;

5、/0号单元存放串的长度号单元存放串的长度Sstring S;p 串的顺序存储C语言实现 Status Concat(SString S1,SString S2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，否则，否则FALSE。.return uncut;/Concat T1.S10=S11.S10;TS10+1S10+S20=S21S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断未截断4.2.1 定长顺序存储表示定长顺序存储表示p 串的连接算法 Status C

6、oncat(SString S1,SString S2,SString&T)/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，否则，否则FALSE。.return uncut;/Concat else if(S10 MAXSTRSIZE)/截断截断T1.S10=S11.S10;TS10+1MAXSTRLEN=S21MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;4.2.1 定长顺序存储表示定长顺序存储表示p 串的连接算法 Status Concat(SString S1,SString S2,SString&T)

7、/用用T返回由返回由S1和和S2联接而成的新串。若未截断联接而成的新串。若未截断,则返回则返回TRUE，否则，否则FALSE。.return uncut;/Concat else /截断截断(仅取仅取S1)T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLEN uncut=FALSE;4.2.1 定长顺序存储表示定长顺序存储表示p 串的连接算法 Status StrDelete(SSstring&S,int pos,int len)if(posS0|len=S0)S0=pos-1;else for(i=pos+len;i=S0;i+)Si-len=Si;S0=

8、S0-len;return OK;4.2.1 定长顺序存储表示定长顺序存储表示p 子串的删除算法4.2 串的表示和实现4.2.1、定长顺序存储表示4.2.2、堆分配存储表示4.2.3、串的块链存储表示4.2.2 堆分配存储表示堆分配存储表示 typedef struct char*ch;/若是非空串，则按串长分配存储区，若是非空串，则按串长分配存储区，/否则否则ch为为NULL int length;/串长度串长度 HString;p 堆分配存储表示的C语言实现Status Concat(HString&T,HString S1,HString S2)/用用T返回由返回由S1和和S2联接而成的

9、新串联接而成的新串 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;return OK;/Concat4.2.2 堆分配存储表示堆分配存储表示p 堆分配存储表示的串连接算法 Status SubString(HString&

10、Sub,HString S,int pos,int len)if(pos S.length|len S.length-pos+1)return ERROR;if(Sub.ch)free(Sub.ch);/释放旧空间释放旧空间 if(!len)Sub.ch=NULL;Sub.length=0;/空子串空子串 else ./完整子串完整子串 return OK;/SubString4.2.2 堆分配存储表示堆分配存储表示p 堆分配存储表示的求子串算法 Sub.ch=(char*)malloc(len*sizeof(char);Sub.ch0.len-1=Spos-1.pos+len-2;Sub.l

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

12、UNKSIZE 80 typedef struct Chunk /结点结构结点结构 char chCUNKSIZE;struct Chunk *next;Chunk;typedef struct /串的链表结构串的链表结构 Chunk*head,*tail;/串的头和尾指针串的头和尾指针 int curlen;/串的当前长度串的当前长度 LString;4.2.3 串的块链存储表示串的块链存储表示p 串的块链存储的C语言实现4.3 串的模式匹配算法4.3.1 模式匹配简单算法4.3.2 模式匹配KMP算法4.3 串的模式匹配算法串的模式匹配算法初始条件：串S和T存在，T是非空串，1posStr

13、Length(S)。INDEX(S,T,pos)p 串匹配(查找)的定义操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。4.3.1 模式匹配简单算法int Index(SString S,SString T,int pos)i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index 讨论下面这种情况的时间复杂性，设S串长为n，T串长为m。S：a b c d e f g h j k l l k c d e T：j k l4.3.1 模式匹配简单算法模式匹配简单算法p 时间复杂性

14、分析 假设从第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)讨论下面这种情况的时间复杂性，设S串长为n，T串长为m。S：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 T：0 0 0 0 0 0 14.3.1 模式匹配简单算法模式匹配简单算法 若第i趟比较成功，共比较了多少次？前i-1趟比较每次都比较m次，第i趟也比较m次 共im次，i从1到n-m+1 共比较了(n-m+2)(n-m+1)m/2 平均比较次数(n

15、-m+2)m/2 最坏的情况时间复杂度为O(n m)p 时间复杂性分析4.3 串的模式匹配算法4.3.1 模式匹配简单算法4.3.2 模式匹配KMP算法主串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 事例讨论主串S：子串T：4.3.1 模式匹配模式匹配KMP算法算法a b c d a b c d a b c f ea b c d a

16、b c f1 2 3 4 5 6 7 8 9ij结论：j回到1，i回到2没有意义。例下图中主串游标i指向8，子串中游标j指向8，按照简单模式匹配算法两处不相等时j回到1，i回到2，继续比较，分析在这种情况下，这样做有没有意义？在什么情况下才有意义？p 事例讨论主串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回到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

17、 4 5 6 7 8 9ij与原来的比较图进行对比，看有什么发现？主串主串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。如下图。p KMP算法的思想主串指针不回溯，模式串向后滑动至某个位置上。主串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 子串游标滑动到k必须满足的条件结论：可以i不动，j回到4。

18、如下图。与原来的比较图进行对比，看有什么发现？a b c d a b c fj假如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-j Si-j+1 Si-j+2 Si-2 Si-1Si Si+1子串子串T：t1 t2 tj-2 tj-1 tj4.3.1 模式匹配模式匹配KMP算法算法p 子串游标滑动到k必须满足的条件 max k|1kj,且且“t1tk-1”=“tj-k+1tj

19、-1”当此集合非空时当此集合非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和主串中该字符进行比较的字符的位置。4.3.1 模式匹配模式匹配KMP算法算法p nextj函数int Index_KMP(SString S,SString T,int pos)i=pos,j=1;while(i=S0&jt0)return i-t0;/匹配成功匹配成功 else return 0;/返回不匹配标志返回不匹配标志 4.3.1 模式匹配模式匹配KMP算法算法p KMP算法(1)next1=0;表明主串从下一字符si

20、+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+1=nextj+1。若tktj，可把求next值问题看成是一个模式匹配问题，整个模式串既是主串，又是子串。求求nextj+1,如果如果tj=tk;则则nextj+1=k+1;如果如果tj tk 若若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函数值void get_next(SString T,int next)int i=1,j=0;next1=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;j=nextj;4.3.1 模式匹配模式匹配KMP算法算法p 求next函数算法本章小结 熟练掌握：(1)串的定义、性质和特点；(2)ADT串的设计、实现方法和基本操作；(3)朴素模式匹配算法；