第四章 串.ppt

1、第四章 串,4.1 串类型的定义 4.2 串的表示和实现4.2.1 定长顺序存储表示4.2.2 堆分配存储表示4.2.3 串的块链存储表示 4.3 串的模式匹配,一、串及串的基本概念串(String) 即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,记为： S =a1a2an (n0 ),串名,串值（用 括起来）,隐含结束符/0 ，即ASCII码NULL,4.1 串类型的定义,串长：串中字符个数（n0）. n=0 时称为空串，记 。 空格串：由一个或多个空格符组成的串。 子串：串S中任意个连续的字符序列叫S的子串; S叫主串。 子串位置：子串的第一个字符在主串中

2、的序号。 串相等：串长度相等，且对应位置上字符也相等。,术语：,1.空串和空格串有无区别？有区别。空串(Null String)是指长度为零的串；而空格串(Blank String)是指包含一个或多个空格的字符串. 2.现有以下4个字符串：a =BEI b =JING c = BEIJING d = BEI JING 问： 他们各自的长度？ b是哪个串的子串？它在主串中的位置是多少？,例：,ADT String 数据对象: D=ai | ai CharacterSet, i=1, 2,，n, n0 数据关系: R= | ai-1,ai D, i=2, ，n 基本操作：/ 有13个,二、串的抽象

3、数据类型定义,StrCopy (&T, S)初始条件：串 S 存在。操作结果：由串 S 复制得串 T。,二、串的抽象数据类型定义,StrAssign (&T, chars)初始条件：chars 是字符串常量。操作结果：生成一个值为 chars的串 T 。,StrEmpty(S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。,二、串的抽象数据类型定义,DestroyString (&S)初始条件：串 S 存在。操作结果：串 S 被销毁。,例如：StrCompare(data, state) 0,StrCompare (S, T) 初始条件：串 S 和

4、T 存在。 操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。,二、串的抽象数据类型定义,StrLength(S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数,称为串的长度。,二、串的抽象数据类型定义,Concat(&T,S1,S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2联接而成的新串。 或Concat(S1,S2) 用S1返回由 S1 和 S2联接而成的新串。,例如：S1= man , S2= kindConcat( T，S1， S2)求得 T = mankind或Concat( S1, S2)求得

5、S1 = mankind,二、串的抽象数据类型定义,SubString (&Sub, S, pos, len) 初始条件：串 S 存在，1posStrLength(S)且0lenStrLength(S)-pos+1。 操作结果：用 Sub 返回串 S 的第 pos 个字符起长 度为 len 的子串。,例如： SubString( sub, commander, 4, 3)求得 sub = man ;,二、串的抽象数据类型定义,Index (S, T, pos) /求子串序号 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同

6、的子串, 则返回T在主串 S 中第pos个字符之后第一次出现的位置; 否则函数值为0。,假设 S = abcaabcaaabc, T = bca,Index(S, T, 1) = 2;,Index(S, T, 3) = 6;,Index(S, T, 8) = 0;,二、串的抽象数据类型定义,Replace (&S, T, V) 初始条件：串S, T和 V 均已存在，且 T 是非空串。 操作结果：用V替换主串S中出现的所有与串T相等的 不重叠的子串。,假设 S = abcaabcaaabca, T = bca,若 V = x, 则经置换后得到S = axaxaax,若 V = bc, 则经置换后

7、得到S = abcabcaabc,二、串的抽象数据类型定义,StrInsert (&S, pos, T) 初始条件：串S和T存在，1posStrLength(S)1。 操作结果：在串S的第pos个字符上插入串T。,例如：S = chater，T = rac，则执行 StrInsert(S, 4, T)之后得到S = character,二、串的抽象数据类型定义,StrDelete (&S, pos, len) 初始条件：串S存在1posStrLength(S)-len+1。 操作结果：从串S中删除第pos个字符起长度为len的子串。,ClearString (&S) 初始条件：串S存在。 操作

8、结果：将S清为空串。 end String,二、串的抽象数据类型定义,对于串的基本操作集可以有不同的定义方法。 在上述抽象数据类型定义的13种操作中，串赋值 StrAssign、串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString等五种操作构成串类型的最小操作子集，这些操作不可能利用其它串操作来实现. 其它串操作可在这个最小操作子集上实现。,二、串的抽象数据类型定义,int Index (String S, String T, int pos) if (pos 0) n = StrLength(S); m = StrLength(T); i =

9、 pos;while ( i = n-m+1) SubString (sub, S, i, m);if (StrCompare(sub,T) != 0) +i ;else return i ; / while / ifreturn 0; / S中不存在与T相等的子串 / Index,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。,4.2 串的表示和实现,定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列堆分配存储表示 用一组地址

10、连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储表示 链式方式存储,串有三种表示方法：,顺序存储,链式存储,用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。,例如：#define MAXSTRLEN 255 /用户可用的最大串长typedef unsigned char SStringMAXSTRLEN1 ;SString S; /S是一个可容纳255个字符的顺序串。,一、定长顺序存储,一般用SString0来存放串长信息； C语言约定在串尾加结束符 0，但不计入串长； 若字符串超过MAXSTRLEN,

11、 则自动截断（因为静态数组存不进去）。,算法描述,两串连接Concat(&T,S1,S2) (算法4.2) 用T返回S1和S2连接成的新串.,Status Concat(SString / Concat,串的联接算法中需分三种情况处理：,T1S10 = S11S10;TS10+1S10+S20 = S21S20;T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) / 未截断,else if (S10 MAXSTRLEN / 截断,else / 截断(仅取S1),T1S10 = S11S10; TS10+1MAXSTRLEN =S21MAX

12、STRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,T0MAXSTRLEN = S10MAXSTRLEN;uncut = FALSE; ,求子串 SubString(&Sub,S,pos,len) 将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中（注：串Sub的预留长度与S一样）,求子串函数SubString(&Sub, S, pos, len),Status SubString(SString ,讨论：想存放超长字符串怎么办？静态数组有缺陷！,改用动态分配的一维数组,“堆”！,思路：利用malloc函数合理预设串长空间。 特点： 若在操作中

13、串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。,Typedef struct char *ch; / 若非空串,按串长分配空间; 否则 ch = NULLint length; /串长度 HString,仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。,二、堆分配存储,Status StrInsert ( HString /StrInsert,例：用“堆”实现串插入操作(教材P75),Status StrAssign(HString /StrAssign,附：堆分配存储表示,直到终值为“假”停止，串尾特征是 /0NULL=0,讨论：方法1存储密度为

14、 ；方法2存储密度为 ；,若数据元素很多，用方法2存储更优称为块链结构,三、链式存储：用链表存储串值，易插入和删除。,方法1：链表结点（数据域）大小取1,方法2：链表结点（数据域）大小取n(例如n=4),1/5,1/2,#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk /首先定义结点类型char ch CHUNKSIZE ; /结点中的数据域struct Chunk * next ; /结点中的指针域 Chunk;,块链类型定义：,typedef struct /其次定义用链式存储的串类型Chunk *head; /头指针Chunk *

15、tail; /尾指针int curLen; /串的当前长度 LString;,算法目的：确定主串中所含子串第一次出现的位置（定位）即如何实现 Index(S,T,pos)函数,4.3 串的模式匹配算法,模式匹配(Pattern Matching) 即子串定位运算（Index函数）。,注：S称为被匹配的串，T称为模式串。若S包含串T，则称“匹配成功”,否则称 “匹配不成功” 。,BF算法 (又称古典或经典的、朴素的、穷举 的)KMP算法（特点：速度快）,算法种类：,S=a b a b c a b c a c b a b,T=a b c a c,pos=5,4.3 串的模式匹配算法,返回值为6,

16、设计思想： 将主串的第pos个字符和模式串的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。,直到主串的一个连续子串字符序列与模式串相等 。返回值为S中与T匹配的子串中第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0 .,一.BF算法, BF算法的实现,讨论：BF匹配算法最坏的情况下需要比较字符的总次数,例：S=aaaaaaab , T=aab , pos=1n=8,m=3,最坏情况是：主串前面8-3个位置都部分匹配到子串的最后一位，即这5位比较了3次，最后3位也各比较了一次，还要加上3！ 比较字符的次数为：5*3+3=18次,若n

17、为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为,(n-m+1)*mO(n*m),最坏情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还要加上m！,BF匹配算法的最坏时间复杂度,但一般情况下BF算法的时间复杂度为O(n+m),二、KMP算法（特点：速度快）, KMP算法设计思想 KMP算法的推导过程 KMP算法的实现 （关键技术:计算nextj） KMP算法的时间复杂度,主串S的指针i不必回溯！模式T的指针k向前滑动。可提速到O(n+m)！, KMP算法设计思想,S=a b a b c a b c a

18、c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,Index_kmp的返回值应为i=6,需要解决的问题：如何由“记忆”结果计算出主串S第i个字符应该与模式T中哪个字符再比较？即确定模式T中的新比较起点k.,a b a,a b c, KMP算法的推导过程,解释: 设主串为S=S1S2 Sn,模式串为T=T1T2Tm S1S2 Si-j+1Si-j+2Si-k+1Si-j+kSi-j+k+1Si-2 Si-1 Si Si+1,T1 T2 Tj-k+1

19、 Tk Tk+1 Tj-2 Tj-1 Tj,T1 Tk-(j-k) Tk-(j-k-1) Tk-2 Tk-1Tk,S1S2 Si-j+1Si-j+2Si-k+1Si-j+kSi-j+k+1. Si-2 Si-1 Si Si+1,所以T1T2 Tk-1 = Tj-k+1Tj-k+2 Tj-1,Si与 Tj 处失配,设T 向前滑动j-k, Si与Tk 比较, KMP算法的推导过程(续）：,根据模式串T的规律： T1Tk-1=Tj-(k-1) Tj-1 和已知的当前失配位置j ，可以归纳出计算新起点 k的表达式。 令 next j =k，则nextj表明当第j个字符与主串中相应字符“失配”时，在模式

20、中需要重新和主串中字符进行比较的字符的位置。,next j ,0 当j1时 max k |1kj 且T1Tk-1=Tj-(k-1) Tj-1 1 其他情况,例： 模 式 串 T： a b a a b c a c可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 nextj :,0,1,1,2,2,3,1,2,讨论：,j=1时, next j 0；因为属于“j=1”;,刚才已归纳：,j=3时, k=2，只需查看T1=T2；因不满足，属于其他情况,j=4时, k=2,3，k=2时查看T1=T3 ,k=3时查看T1T2= T2 T3,j=5时, k=2,3,4， k=2时查看T1=T4 (满

21、足) k=3时查看 T1T2=T3T4(不满足)k=4时查看T1T2T3=T2 T3T4,j=2时, next j 1；因为属于“其他情况”；,例： 模 式 串 T： a b a b a a c a可能失配位 j： 1 2 3 4 5 6 7 8 新匹配位 nextj :,0,1,1,2,3,4,1,1,讨论：,j=1时, next j 0；因为属于“j=1”; j=2时, next j 1；因为属于“其他情况”；,j=3时, k=2，只需查看T1=T2；属于其他情况,j=4时, k=2,3，要查看T1=T3, T1 T2=T2T3,j=5时, k=2,3,4，要查看T1=T4,T1 T2=T

22、3T4,T1T2T3 =T2T3T4,j=6时, k=2,3,4,5，要查看T1=T5 、T1T2=T4T5 、T1T2T3=T3T4T5, T1T2T3T4=T2T3T4T5,计算nextj的算法如下,void get_next(SString T, int / get_next,计算nextj的时间为O(m),演示程序,第一步，先把模式T所有可能的失配点j所对应的nextj计算出来； 第二步：执行定位函数index_kmp （与BF算法模块非常相似）, KMP算法的实现即Index( )操作的实现 （见教材P82）,Int Index_KMP(SString S, SString T, i

23、nt pos) i=pos; j=1;while ( iT0) return i-T0; /子串结束，说明匹配成功else return 0; /Index_KMP,演示程序,next函数的改进算法,前面定义的next函数在某些情况下还是有缺陷 例如：模式aaaab与主串aaabaaaab匹配情况：,S: a a a b a a a a b,T: a a a a b,i: 1 2 3 4 5 6 7 8 9,a a a a b,a a a a b,a a a a b,a a a a b,当Pj=Pnextj时，则,如果Si != Pj，= Si != Pnextj,因此，Si 没有必要继续与

24、Pnextj进行比较， 而应该直接和Pnextj的下一个字符Pnextnextj 进行比较。,因此，在计算next函数时， 如果出现Pj=Pnextj = Pk 则nextj=nextk=nextnextj,此时效率不高的原因为：,nextvalj: 0 0 0 0 3,S: a a a b a a a a b,T: a a a a b,i: 1 2 3 4 5 6 7 8 9,a a a a b,Nextval4=0,i+,j+,例,void get_nextval(SString T, int / get_nextval, KMP算法的时间复杂度,因为计算nextj的时间为O(m); 且I

25、ndex_KMP函数（没有回溯）的匹配时间为O(n); 所以KMP算法的总时间耗费为： O(n+m)注意：由于BF算法在一般情况下的时间复杂度也是O(n+m)，所以至今仍被采用。,因为主串指针i不必回溯，所以从外存输入文件时可以做到边读入边查找，“流式”作业！,KMP算法的用途：,本章小结,熟悉串的五种基本操作的定义、并能利用这些基本操作实现串的其它各种操作的方法； 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法； 理解串匹配的KMP算法，熟悉next函数的定义，掌握手工计算给定模式串的next函数值和改进的next函数值； 理解串操作的应用方法和特点。,作 业,书面作业:p28: 4.4题，4.7题，4.8题p29: 4.23题 上机作业: 串基本操作的实现(p119),