数据结构 4串

1、1数据结构课程的内容数据结构课程的内容2第第4章章 串（串（String）4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配算法串的模式匹配算法1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式4.1 4.1 串类型的定义串类型的定义3记为：记为： s = a1 , a2 , . , an (n0 ) 串名串名串值（用串值（用 括起来）括起来）串中字符个数（串中字符个数（n0n0）. n=0 . n=0 时称为空串时称为空串 。由一个或多个空格符组成的串。由一个或多个空格符组成的串。串串s s中任意个连续的字符序列叫中任

2、意个连续的字符序列叫s s的子串的子串; S; S叫叫主串主串。子串的第一个字符的序号。子串的第一个字符的序号。字符在串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。串长度相等，且对应位置上字符相等。 串串即字符串，是由零个或多个字符组成的有限序列，是数据即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。元素为单个字符的特殊线性表。4.1 4.1 串类型的定义串类型的定义若干术语：若干术语： 串长：串长： 空白串：空白串： 子串：子串：子串位置：子串位置：字符位置：字符位置： 串相等：串相等：隐含结束符隐含结束符/0 ，即即ASCII码码NUL4练练

3、1：串是由串是由 字符组成的序列，一般记字符组成的序列，一般记为为 。练练2：现有以下现有以下4个字符串：个字符串：a =BEI b =JING c = BEIJING d = BEI JING问：问： 他们各自的长度？他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1练练3：空串和空白串有无区别？空串和空白串有无区别？答：答：有区别。空串有区别。空串(Null String)(Null String)是指长度为零的串；而空白是指长度为零的串；

4、而空白串串(Blank String),(Blank String),是指包含一个或多个空白字符是指包含一个或多个空白字符 ( (空空格键格键) )的字符串的字符串. .0个或多个个或多个S=a1a2an5ADT StringObjects: D=ai | aiCharacterSet, i=1, 2,，n, n0Relations: R1= | ai-1,ai D, i=2, ，nfunctions: / 有有1313种之多种之多StrAssign(&T, chars) / 串赋值，生成值为串赋值，生成值为charschars的串的串T TStrCompare(S,T) / 串比较，若串比较

5、，若STST，返回值大于，返回值大于0 0 StrLength(S) / 求串长，即返回求串长，即返回S S的元素个数的元素个数 Concat(&T, S1, S2) / 串连接，用串连接，用T T返回返回S1S1S2S2的新串的新串SubString(&Sub, S, pos, len) / 求求S S中中pospos起长度为起长度为lenlen的子串的子串Index(S, T, pos) / 返回子串返回子串T T在在pospos之后的位置之后的位置 Replace(&S, T,V) / 用子串用子串V V替换子串替换子串T TADT String串的抽象数据类型定义（串的抽象数据类型定义

6、（参见教材参见教材P71）最最小小操操作作子子集集6 设设 s =I AM A STUDENT, t =GOOD, q=WORKER。求：。求：练习：练习： StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A)= Index(s, t)=Replace(s, STUDENT,q)=144STUDENTO30 （ s中没有中没有t！）！）I AM A WORKER再问：再问：Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ？ 见本章自测题，或

7、见严题集见本章自测题，或见严题集4.3 74.2串的表示和实现串的表示和实现 定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列符序列 堆分配存储表示堆分配存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列符序列, ,但存储空间是在程序执行过程中动态但存储空间是在程序执行过程中动态分配而得。分配而得。 串的块链存储表示串的块链存储表示链式方式存储链式方式存储串有三种机内表示方法：串有三种机内表示方法：顺序顺序存储存储链式链式存储存储 A B C I NULLhead8定长顺序存储特点：定长顺序存储特

8、点：用一组连续的存储单元来存放串，用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的直接使用定长的字符数组来定义，数组的上界预先给出上界预先给出，故称为静态存储分配。故称为静态存储分配。例如：例如：#define Maxstrlen 255 /用户可用的最大串长用户可用的最大串长 typedef unsigned char SString Maxstrlen1 ; SString s; /s是一个可容纳是一个可容纳255个字符的顺序串。个字符的顺序串。注：注：一般用一般用SString0来存放串长信息；来存放串长信息；C语言约定在串尾加结束符语言约定在串尾加结束符 0，以利操作

9、加速，但不计入串长；，以利操作加速，但不计入串长；若字符串超过若字符串超过Maxstrlen 则自动截断（因为静态数组存不则自动截断（因为静态数组存不 进去）。进去）。 讨论：讨论：想存放想存放超长超长字符串怎么办？字符串怎么办？静态数组有缺陷！静态数组有缺陷！实现方式：实现方式：参见教材参见教材P73编程两例，两串连接和编程两例，两串连接和求子串求子串改用改用动态动态分配的一维数组分配的一维数组“堆堆”！9例：例：顺序存储方式下获得子串的函数顺序存储方式下获得子串的函数SubString(&Sub, S, pos, len) Status SubString(SString &Sub, SS

10、tring S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合法则告警不合法则告警 Sub1.len=Spos.pos+len-1; Sub0=len; return OK;P74P74将串将串S S中从第中从第pospos个字符开始长度为个字符开始长度为lenlen的字符序的字符序列复制到串列复制到串SubSub中中（注：串（注：串SubSub的预留长度与的预留长度与S S一样）一样）S = a1 , a2 , . , ann串长串长poslen10思路：思路：利用利用mallocmalloc函数合理预设串长空

11、间。函数合理预设串长空间。特点：特点： 若在操作中串值改变，还可以利用若在操作中串值改变，还可以利用reallocrealloc函数按新串函数按新串长度长度增加增加( (堆砌堆砌) )空间。空间。typedef struct char *ch; / 若非空串,按串长分配空间; 否则 ch = NULLint length; /串长度HString堆分配存储特点：堆分配存储特点：仍用一组连续的存储单元来存放串，仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。但存储空间是在程序执行过程中动态分配而得。约定：约定：所有按堆存储的串，其关键信息放置在：所有按堆存储的串，其关键

12、信息放置在：11Status StrInsert ( HString &S, int pos, HString T ) /在串在串S的第的第pos个字符之前（包括尾部）插入串个字符之前（包括尾部）插入串Tif (posS.length+1) return ERROR; /pos不合法则告警不合法则告警 if(T.length) /只要串只要串T不空，就需要重新分配不空，就需要重新分配S空间，以便插入空间，以便插入T if (!（S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) ) exit(OVERFLOW); for ( i

13、=S.length-1; i=pos-1; -i ) /为插入为插入T而腾出而腾出pos之后的位置之后的位置 S.chi+T.length = S.chi; /从从S的的pos位置起全部字符均后移位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入插入T，略，略/0 S.length + = T.length; /刷新刷新S串长度串长度return OK;/StrInsert例：例：用用“堆堆”实现串插入操作实现串插入操作(教材教材P75) 121 Status StrAssign(HString &T, char *chars)2

14、 if (T.ch) free(T.ch);3 for (i=0, c=chars; c; +i, +c); /求串长度求串长度i4 if (!i) T.ch = NULL; T.length = 0; /串长串长i为为0，即空串，即空串5 else6 if (!(T.ch = (char*)malloc(i*sizeof(char)7 exit(OVERFLOW);8 T.ch0.i-1 = chars0.i-1;9 T.length =i;10 11 return OK;/StrAssign指针变量指针变量c也可以自增！也可以自增！意即每次后移一个数据意即每次后移一个数据单元。单元。附：堆

15、分配存储表示附：堆分配存储表示直到终值为直到终值为“假假”停止，串尾特征是停止，串尾特征是/0NULL=013讨论：讨论：法法1 1存储密度为存储密度为 ；法；法2 2存储密度为存储密度为 ；显然，若显然，若数据元素很多，用法数据元素很多，用法2 2存储更优存储更优称为称为块链结构块链结构链式存储特点链式存储特点 ：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。法法1 1：链表结点（数据域）大小取链表结点（数据域）大小取1 1法法2 2：链表结点（数据域）大小取链表结点（数据域）大小取n(n(例如例如n=4)n=4)9/189/189/15=3/59/15=3/5 A B C I

16、 NULLheadheadA B C D E F G H I # # # NULL14#define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk /首先定义结点类型首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域结点中的数据域 struct Chunk * next ; /结点中的指针域结点中的指针域Chunk; 块链类型定义：块链类型定义：typedef struct /其次定义用链式存储的串类型其次定义用链式存储的串类型 Chunk *head; /头指针头指针 Chunk *tail; /尾指针尾

17、指针 int curLen; /结点个数结点个数 Lstring; /串类型只用一次，前面可以不加串类型只用一次，前面可以不加Lstring15再次强调：再次强调：串与线性表的运算有所不同，是以串与线性表的运算有所不同，是以“串的整体串的整体”作作为操作对象，例如查找某子串，在主串某位置上插入一个子串为操作对象，例如查找某子串，在主串某位置上插入一个子串等。等。算法目的：算法目的：确定主串中所含子串第一次出现的位置确定主串中所含子串第一次出现的位置（定位定位） 即如何实现即如何实现 Index(S,T,pos)函数函数（见教材（见教材P79）4.3 串的模式匹配算法串的模式匹配算法模式匹配模式

18、匹配(Pattern Matching) (Pattern Matching) 即即子串定位运算子串定位运算。初始条件：初始条件：串串S S和和T T存在，存在，T T是非空串，是非空串，1posStrLength(s)1posStrLength(s)操作结果：操作结果：若主串若主串S S中存在和串中存在和串T T值相同的子串，则返回它在主值相同的子串，则返回它在主串串S S中第中第pospos个字符之后个字符之后第一次第一次出现的位置；否则函数值为出现的位置；否则函数值为0 0。注：注：S S称为称为被匹配的串被匹配的串，T T称为称为模式串模式串。若。若S S包含串包含串T T，则称，则称

19、“匹配成功匹配成功”。否则称。否则称 “匹配不成功匹配不成功” 。S=a b a b c a b c a c b a bT=T=a b c a cpos=516 BF算法设计思想算法设计思想（见教材（见教材P79） 将主串的第将主串的第pospos个字符和模式的第个字符和模式的第1 1个字符比较，个字符比较， 若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符； 若若不等不等，从主串的下一字符（，从主串的下一字符（pos+1pos+1）起，重新与第一个）起，重新与第一个字符比较。字符比较。 BF算法算法 （又称古典或经典的、朴素的、穷举的）（又称古典或经典的、朴素的、穷举的） KMP算

20、法算法（特点：速度快）（特点：速度快）算法算法种类：种类： 直到主串的一个连续子串字符序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返回值。返回值为为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 .0 .返回5S=a b a b c a b c a c b a bT=T=a b c a cIndex(S, T, 1)171 int Index(SString S, SString T, int pos) 2 i=pos; j=1;3 while ( i=S0 & jT0) r

21、eturn i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功8 else return 0;9 /Index BFBF算法的实现算法的实现即即Index（）操作的实现（）操作的实现 （见教材（见教材P79） 0号单元存放串的长度，号单元存放串的长度，P73匹配成功时匹配成功时i指向的与子串最后一个字符相等的字指向的与子串最后一个字符相等的字符符18BF算法：算法：int Index(S, T,1)i=1;j=1;while(i=s0 &jT0) return i-T0; else return 0;BFBF算法在最坏的情况下需要比较字算法在最坏的情况下需要比较字符的总次数为符的总次数

22、为(n-m+1)*mO(n*m)最糟糕的情况：最糟糕的情况：主串前面主串前面n-mn-m个位置个位置都都部分匹配部分匹配到子串的最后一位，即到子串的最后一位，即这这n-mn-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位位也各比较了一次，还要加上也各比较了一次，还要加上m m！BFBF算法的最坏时间复杂度算法的最坏时间复杂度但一般情况下但一般情况下BFBF算法的时间复算法的时间复杂度为杂度为O(n+m)BF算法的效率分析讨论：讨论：令令n n为主串长度，为主串长度，m m为子串长为子串长度。匹配最糟糕的情况是什么？度。匹配最糟糕的情况是什么？19KMP算法算法（特点：速度快）（特

23、点：速度快） KMPKMP算法设计思想算法设计思想 KMP算法的推导过程算法的推导过程 KMPKMP算法的实现算法的实现 （关键技术（关键技术: :计算计算nextjnextj） KMPKMP算法的算法的时间复杂度时间复杂度D. E. Knuth, V. R. Pratt, J. H. Morris20能否利用已经能否利用已经部分匹配部分匹配的结果而加快模式串的滑动速度？的结果而加快模式串的滑动速度？能！能！而且主串而且主串S S的指针的指针i i不必回溯不必回溯！可提速到！可提速到O(n+m)O(n+m)！例：例： KMP KMP算法设计思想：算法设计思想： ( (参见教材参见教材P80-8

24、4P80-84）S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i=6i=6需要讨论两个问题：需要讨论两个问题： 如何如何“记忆记忆”部分匹配结果？部分匹配结果？ 如何由如何由“记忆记忆”结果计算出主串结果计算出主串S S第第i i个字符应该与模式个字符应该与模式T T中中哪个字符再比较？即确定模式哪个字符再比较？即确定模式T T中的新比较起点中

25、的新比较起点k k. .i ii ii ik kk k a b aa b c演示程序演示程序21第一步，先第一步，先把模式把模式T所有可能的失配点所有可能的失配点j所对应的所对应的nextj计算出来计算出来；第二步：执行定位函数第二步：执行定位函数Index_KMP （与（与BF算法模块非常相似）算法模块非常相似） KMPKMP算法的实现算法的实现即即Index( )操作的实现操作的实现 （见教材（见教材P82） 1 int Index_KMP(SString S, SString T, int pos) 2 i=pos; j=1;3 while ( i=S0 & jT0) return i-

26、T0; /子串结束，说明匹配成功子串结束，说明匹配成功8 else return 0;9 /Index_KMP22 KMP算法的推导过程：算法的推导过程：（见教材（见教材P81）抓住部分匹配结果的两个特征：抓住部分匹配结果的两个特征：两式联立可得：两式联立可得：T1Tk-1=Tj-(k-1)j-(k-1) Tj-1注意：注意：j 为当前已知的失配位置，我们的目标是计算新起点为当前已知的失配位置，我们的目标是计算新起点 k，仅剩一个未知数仅剩一个未知数k，理论上已可解，且，理论上已可解，且k仅与模式串仅与模式串T有关！有关！ 则则S S的的i-(k-1)i-(k-1)i-1i-1位位T T的的j

27、-(k-1)j-(k-1)j-1j-1位位 即即(4-3(4-3）式含义）式含义S=a b a b c a b c a c b a bT=T=a b c a ci ik k则则T T的的1 1k-1k-1位位S S的的i-(k-1)i-(k-1)i-1i-1位位 即即(4-2(4-2）式含义）式含义i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c刚才肯定是在刚才肯定是在S的的i处和处和T的第的第j字符字符 处失配处失配设目前应与设目前应与T的第的第k字符开始比较字符开始比较23 KMP算法的推导过程算法的推导过程(续）续）：根据模式串根据模式串

28、T的规律：的规律： T1Tk-1=Tj-(k-1)j-(k-1) Tj-1和已知的当前失配位置和已知的当前失配位置j ，可以归纳出计算新起点，可以归纳出计算新起点 k的表达式。的表达式。令令k = next j ，则则next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其他情况讨论：讨论： next j 有何意义？有何意义？ 一旦失配，应从模式串一旦失配，应从模式串T中第中第next j 个字符开始与个字符开始与S的失配的失配点点i 重新匹配重新匹配! next j 怎么求？怎么求？ 后面会举例后面会举例（参见教材（参见教

29、材P81）例：例： 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位 nextj :next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其他情况0 1 1 2 2 3 1 2讨论：讨论：j=1时时, next j 0；因为属于因为属于“j=1”;j=2时时, next j 1；因为属于因为属于“其他情况其他情况”；刚才已归纳：刚才已归纳：j=3时时, k=2，只需查看，只需查看T1=T2 2。因不等，故。因不等，故“其他情其他情况况”；j=4

30、时时, k=2，3，要查看，要查看T1=T3 3 和和T1T2=T2 2 T3 3 j=5时时, k=2，3，4，要查看，要查看T1=T4 4 、T1T2=T3 3T4 和和 T1T2T3 3=T2 2T3 3T4以此类推，可得后续以此类推，可得后续nextj值。值。25讨论：讨论： next j 有何物理意义？有何物理意义？nextjnextj函数表征着模式中两段字符之间相匹配的最大子函数表征着模式中两段字符之间相匹配的最大子串的长度（除串本身外）。串的长度（除串本身外）。可见，模式中可见，模式中相似部分越多，则相似部分越多，则nextjnextj函数越大函数越大，它既，它既表示表示模式模式

31、T字符之间的相关度越高，也表示字符之间的相关度越高，也表示j j位置以前与主串位置以前与主串部部分匹配分匹配的字符数越多。的字符数越多。即：即：nextjnextj越大，模式串向右滑动得越远，与主串进行越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。比较的次数越少，时间复杂度就越低。next j max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 模式串从首位往右模式串从首位往右直到直到k-1k-1位位模式串从模式串从j j的前一位的前一位往左直到往左直到j-(k-1)j-(k-1)位位想一想：如果主串和模式均为二进制码流，用想一想：如果主

32、串和模式均为二进制码流，用KMPKMP算法算法效果如何？效果如何？26next函数的改进算法函数的改进算法前面定义的前面定义的next函数在某些情况下还是有缺陷函数在某些情况下还是有缺陷例如：模式例如：模式aaaab与主串与主串aaabaaaab匹配情况：匹配情况：模式：模式： a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4S: 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 ba a a a ba a a a ba a a a bnextvalj=nextvalk nextj=k且Tj=Tkn

33、extj其他nextvalj： 0 0 0 0 427讨论两个有关讨论两个有关next j 的问题：的问题： 怎样简捷计算怎样简捷计算nextj？ 可用递推法编程实现！可用递推法编程实现！（参见（参见P83简捷算法）简捷算法）计算计算nextj的时间为的时间为O(m)1 void get_next(SString T, int &next )2 /next函数值存入数组函数值存入数组next3 i=1; next1=0; j=0; /j是重复子串长是重复子串长4 while(iT0 )5 if(j= = 0|Ti= =Tj)+i;+j;nexti=j;6 else j=nextj;7 8/ g

34、et_next1 void get_nextval(SString T, int &nextval )2 /next函数修正值存入数组函数修正值存入数组nextval3 i=1; nextval1=0; j=0;4 while(iT0 )5 if(j= = 0|Ti= =Tj ) +i;+j;6 if(Ti!=Tj) nextvali=j;7 else nextvali=nextvalj; 8 else j=nextvalj; 9/ get_nextval next j 是否完美无缺？是否完美无缺？答：未必，例如当答：未必，例如当S=a b a a a a b,T=a a a a b时时仍有多余动作仍有多余动作（参见（参见P84改进算法改进算法, 称为称为nextval j ）28 KMPKMP算法的算法的时间复杂度时间复杂度 因为计算因为计算nextj的时间为的时间为O(m);且且Index_KMP函数（函数（没有回