串类型的定义串的表示和实现串的模式匹配算法教学ppt课件

1、1 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的方式匹配算法 2 第第4 4章章 串串重点重点: 1ADT串的设计、实现方法和根串的设计、实现方法和根本操作；本操作；2串的简单方式匹配算法，串的简单方式匹配算法，KMP算法。算法。 难点难点:串的方式匹配算法中的串的方式匹配算法中的KMP算法。算法。 本章重点难点3 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的方式匹配算法 4 第第4 4章章 串串4.1 串类型的定义串类型的定义 串是由零个或多个字符组成的有限序列。串是由零个或多个字符组成的有限序列。 记为：记为：s=a1a2an n0 其中，其中，s是串的名，用双

2、引号括起来的字符序列是串是串的名，用双引号括起来的字符序列是串的值。的值。 1 串的长度串的长度:串中字符的数目串中字符的数目n。 2 空串空串Null string:长度为零的串。长度为零的串。 3 子串子串:串中恣意个延续的字符组成的子序列。串中恣意个延续的字符组成的子序列。p 串的有关术语串的有关术语p 串String的定义 5 第第4 4章章 串串4.1 串类型的定义串类型的定义 4 主串主串 包含子串的串相应地称为主串。包含子串的串相应地称为主串。 5 串相等串相等 只需当两个串的长度相等，并且各个对应位置的只需当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。字符都相等

3、，称两串相等。 6 空格串空白串空格串空白串blank string 由一个或多个空格组成的串。要和由一个或多个空格组成的串。要和“空串区别，空串区别，空格串有长度就是空格的个数。空格串有长度就是空格的个数。p 串的有关术语 6 第第4 4章章 串串4.1 串类型的定义串类型的定义 1 串数据对象约束为字符集。串数据对象约束为字符集。 2 根本操作的对象不同，线性表以根本操作的对象不同，线性表以“单个单个元素为操作对象；串以元素为操作对象；串以“串的整体为操作对串的整体为操作对象，操作的普通都是子串。象，操作的普通都是子串。p 串与普通线性表的区别 7 第第4 4章章 串串ADT String

4、 数据对象：数据对象： 数据关系：数据关系： 根本操作：根本操作： ADT String p 串的ADT定义见下页见下页D ai |aiCharacterSet,i=1,2,.,n, n0 R1 | ai-1, ai D, i=2,.,n 4.1 串类型的定义串类型的定义 8 第第4 4章章 串串p 根本操作： StrAssign &T, chars /根据串常量根据串常量chars生成串生成串T StrCopy &T, S /把串把串S中内容拷贝到中内容拷贝到T串串 DestroyString&S /销毁串销毁串S StrEmpty S /判别串能否空判别串能否空 S

5、trCompare S, T /比较串比较串S和和T StrLengthS /求串长求串长 Concat &T, S1, S2 /衔接串衔接串4.1 串类型的定义串类型的定义 9 第第4 4章章 串串p 根本操作： SubString &Sub, S, pos, len /求子串求子串 Index S, T, pos /子串定位子串定位 ClearString &S /清空串清空串S StrDelete &S, pos, len /删除子串删除子串 Replace &S, T, V /把串把串S中符合中符合T的子串交的子串交换换 StrInsert &a

6、mp;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 定长顺序存储表示定长顺序存储表示 #define MAXSTRLEN 255 / 用户可在用户可在255以内定义最大串长以内定义最大串长 typedef unsigned char SstringMAXSTRLEN+1; / 0号单元存放串的长度号单元存放串的长度Sstring S;p 串的顺序存储C言语实现 12 第第4 4章章 串串 Status

7、 ConcatSString 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 串的衔接算法 13 第第4 4章章 串串 Status Conc

8、atSString 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 串的衔接算法 14 第第4 4章章 串串 Status

9、 ConcatSString S1, SString S2, SString &T / 用用T前往由前往由S1和和S2联接而成的新串。假设未截断联接而成的新串。假设未截断, 那么前往那么前往TRUE，否那么，否那么FALSE。 . return uncut; / Concat else / 截断仅取截断仅取S1 T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; 4.2.1 定长顺序存储表示定长顺序存储表示p 串的衔接算法 15 第第4 4章章 串串 Status StrDelete SSstring

10、&S, int pos, int len if posS0|len=S0 S0=pos-1; else fori=pos+len;i=S0;i+ Si-len=Si; S0=S0-len; return OK;4.2.1 定长顺序存储表示定长顺序存储表示p 子串的删除算法 16 第第4 4章章 串串4.2 串的表示和实现4.2.1、定长顺序存储表示4.2.2、堆分配存储表示4.2.3、串的块链存储表示 17 第第4 4章章 串串4.2.2 堆分配存储表示堆分配存储表示 typedef struct char *ch; / 假设是非空串，那么按串长分配存储区，假设是非空串，那么按串长分配

11、存储区， / 否那么否那么ch为为NULL int length; / 串长度串长度 HString;p 堆分配存储表示的C言语实现 18 第第4 4章章 串串Status ConcatHString &T, HString S1, HString S2 / 用用T前往由前往由S1和和S2联接而成的新串联接而成的新串 if T.ch freeT.ch; / 释放旧空间释放旧空间 if !T.ch = char * mallocS1.length+S2.length*sizeofchar exit OVERFLOW; T.ch0.S1.length-1 = S1.ch0.S1.lengt

12、h-1; T.length = S1.length + S2.length; T.chS1.lengthT.length-1 = S2.ch0.S2.length-1;return OK; / Concat4.2.2 堆分配存储表示堆分配存储表示p 堆分配存储表示的串衔接算法 19 第第4 4章章 串串 Status SubStringHString &Sub, HString S, int pos, int len if pos S.length | len S.length-pos+1 return ERROR; if Sub.ch free Sub.ch; / 释放旧空释放旧空间

13、间 if !len Sub.ch = NULL; Sub.length = 0; / 空子串空子串 else . / 完好子串完好子串 return OK; / SubString4.2.2 堆分配存储表示堆分配存储表示p 堆分配存储表示的求子串算法 20 第第4 4章章 串串 Sub.ch = char *malloclen*sizeofchar; Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len;4.2.2 堆分配存储表示堆分配存储表示p 堆分配存储表示的求子串算法接上页接上页 21 第第4 4章章 串串4.2.3 串的块链存储表示串的块

14、链存储表示字符串本身就是一个线性表，可以用链表存储。字符串本身就是一个线性表，可以用链表存储。存储密度存储密度 = 数据元素所占存储位数据元素所占存储位实践分配的存储位实践分配的存储位存储密度存储密度 = 840=20% p 链表存储字符串的讨论假设每个结点存储一个字符，如采用假设每个结点存储一个字符，如采用32位地位地址，字符按址，字符按8位记，那么存储密度是多少？位记，那么存储密度是多少？ 22 第第4 4章章 串串4.2.3 串的块链存储表示串的块链存储表示结论：采用普通链表存储字符串，存储密度非常结论：采用普通链表存储字符串，存储密度非常低，浪费空间严重。低，浪费空间严重。p 链表存储

15、字符串的讨论处理方法：一个结点存储多个字符。这就是串的处理方法：一个结点存储多个字符。这就是串的块链存储。块链存储。 23 第第4 4章章 串串 #define CHUNKSIZE 80 typedef struct Chunk / 结点构造结点构造 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表构造串的链表构造 Chunk *head, *tail; / 串的头和尾指针串的头和尾指针 int curlen; / 串的当前长度串的当前长度 LString;4.2.3 串的块链存储表示串的块链存储表示p 串的块链

16、存储的C言语实现 24 第第4 4章章 串串4.3 串的方式匹配算法4.3.1 方式匹配简单算法4.3.2 方式匹配KMP算法 25 第第4 4章章 串串4.3 串的方式匹配算法串的方式匹配算法初始条件：串初始条件：串S和和T存在，存在，T是非空串，是非空串， 1posStrLengthS。INDEX S, T, posp 串匹配查找的定义操作结果：假设主串操作结果：假设主串S中存在和串中存在和串T值一样的子串前往值一样的子串前往它它在主串在主串S中第中第pos个字符之后第一次出现的位置；否那个字符之后第一次出现的位置；否那么么函数值为函数值为0。 26 第第4 4章章 串串4.3.1 方式匹

17、配简单算法int IndexSString S, SString T, int pos i = pos; j = 1; while i = S0 & j T0 return i-T0; else return 0; / Index 27 第第4 4章章 串串 讨论下面这种情况的时间复杂性，设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 时间复杂性分析 假设从第假设从第i个位置匹配胜利，前个位置匹配胜利，前i-1次共比较了次共比较了i-1次。次。 第第i次比较了次比较了m次次,共

18、比较了共比较了i+m-1次。次。 i从从1到到n-m+1,共共n+mn-m+1/2 平均需比较平均需比较n+m/2 最好的情况平均时间复杂度为最好的情况平均时间复杂度为On+m 28 第第4 4章章 串串 讨论下面这种情况的时间复杂性，设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

19、到到n-m+1 共比较了共比较了n-m+2n-m+1m/2 平均比较次数平均比较次数n-m+2m/2 最坏的情况时间复杂度为最坏的情况时间复杂度为Onmp 时间复杂性分析 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，继续比较，分析在这种情况下，这样做有没有

20、意义？结论：没有意义。结论：没有意义。p 事例讨论 31 第第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 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

21、 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 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 9ij

22、p 事例讨论结论：可以i不动，j回到4。如以以下图。p KMP算法的思想主串指针不回溯，方式串向后滑动至某个位置上。 34 第第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 子串游标滑动到k必需满足的条件结论：可以i不动，j回到4。如以以下图。与原来的与原来的比较图进比较图进展对比，展对比，看有什么看有什么发现？发现？a b c d a b c fj 35 第第4 4章章 串串假设假设j滑动到滑动到k,假设比较有意义假设比较有意义:必需满

23、足必需满足: “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必需满足的条件 36 第第4 4章章 串串 max k|1kj, max k|1kj,且且“t1tk-1t1tk-1= =“tj-k+1tj-1tj-k+1tj-1 当

24、此集合非空时当此集合非空时 0 0 当当j=1j=1时时 1 1 其他情况其他情况nextj=阐明当方式中第阐明当方式中第j个字符与主串中相应字符个字符与主串中相应字符“失配时，在失配时，在方式中需重新和主串中该字符进展比较的字符的位置。方式中需重新和主串中该字符进展比较的字符的位置。4.3.1 方式匹配方式匹配KMP算法算法p nextj函数 37 第第4 4章章 串串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算法 38 第第4 4章章