数据结构-第4章课件

第第4章章串串4.1串的定义串的定义4.2抽象数据类型串的实现抽象数据类型串的实现4.3串的应用举例：文本编辑串的应用举例：文本编辑4.1串的定义串的定义串串(String)是是零零个个或或多多个个字字符符组组成成的的有有限限序序列列。一一般般记记为为：S=a1a2.an(n0)其其中中S是是串串的的名名字字,用用单单引引号号括括起起来来的的字字符符序序列列是是串串的的值值，ai(1in)可可以以是是字字母母、数数字字或或其其它它字字符符。n是是串串中中字字符符的的个个数数,称为串的称为串的长度长度，n=0时的串称为时的串称为空串空串(NullString)。串串中中任任意意个个连连续续的的字字符符组组成成的的子子序序列列称称为为该该串串的的子子串串。包包含含子子串串的的串串相相应应地地称称为为主主串串。通通常常将将字字符符在在串串中中的的序序号号称称为为该该字字符符在在串串中中的的位位置置。子子串串在在主主串串中中的的位位置置则则以以子子串串的的第第一一个个字字符在主串中的位置来表示。符在主串中的位置来表示。假假如如有有串串A=ChinaBeijing,B=Beijing,C=China,则则它它们们的的长长度度分分别别为为13、7和和5。B和和C是是A的的子子串串,B在在A中中的的位位置置是是7,C在在A中的位置是中的位置是1。当当且且仅仅当当两两个个串串的的值值相相等等时时,称称这这两两个个串串是是相相等等的的，即即只只有有当当两两个个串串的的长长度度相相等等,并并且且每每个个对对应应位位置置的的字字符符都都相相等等时时才才相相等。等。串的抽象数据类型定义如下串的抽象数据类型定义如下:ADTString数据对象数据对象:D=ai|aiCharacterSet,i=1,2,n;n0数据关系数据关系:R=|ai-1,aiD,i=2,n;n0基本操作基本操作:(1)StrAsign(S,chars)初始条件初始条件:chars是字符串常量。是字符串常量。操作结果操作结果:生成一个值等于生成一个值等于chars的串的串S。(2)StrInsert(S,pos,T)初始条件初始条件:串串S存在存在,1posStrLength(S)+1。操作结果操作结果:在串在串S的第的第pos个字符之前插入串个字符之前插入串T。(3)StrDelete(S,pos,len)初始条件初始条件:串串S存在存在,1posStrLength(S)-len+1。操作结果操作结果:从串从串S中删除第中删除第pos个字符起长度为个字符起长度为len的子串。的子串。(4)StrCopy(S,T)初始条件初始条件:串串S存在。存在。操作结果操作结果:由串由串T复制得串复制得串S。(5)StrEmpty(S)初始条件初始条件:串串S存在。存在。操作结果操作结果:若串若串S为空串为空串,则返回则返回TRUE,否则返回否则返回FALSE。(6)StrCompare(S,T)初始条件初始条件:串串S和和T存在。存在。操操作作结结果果:若若ST,则则返返回回值值0;如如S=T,则则返返回回值值=0;若若ST,则则返返回值回值MAXLEN且且pos+LCMAXLEN且且pos+LCMAXLEN，则则B的的全全部部字字符符被被舍舍弃弃（不不需需后后移移），并并且且C在在插插入入时时也也有有部部分分字字符符被舍弃。被舍弃。与与上上述述类类似似，在在进进行行串串的的连连接接时时（假假设设原原来来串串为为A，长长度度为为LA,待待连连接接串串为为B，长长度度为为LB），也也可可能能有有三三种种情情况况：（1）连接后串长）连接后串长MAXLEN，则直接将则直接将B加在加在A的后面。的后面。（2）连连接接后后串串长长MAXLEN且且LAMAXLEN且且LA=MAXLEN，则则B的全的全部字符被舍弃（不需连接）。部字符被舍弃（不需连接）。置置换换时时的的情情况况较较为为复复杂杂，假假设设原原串串为为A、长长度度为为LA，被被置置换换串串为为B、长长度度为为LB,置置换换串串为为C、长长度度为为LC，每每次次置置换换位置为位置为pos，则每次置换有三种可能：，则每次置换有三种可能：（1）LB=LC：将将C复制到复制到A中中pos起共起共LC个字符处。个字符处。（2）LBLC：将将A中中B后后的的所所有有字字符符前前移移LB-LC个个字字符符位置，然后将位置，然后将C复制到复制到A中中pos起共起共LC个字符。个字符。（3）LBLC：将将A中中B后后的的所所有有字字符符后后移移LC-LB个个字字符符位位置置，然然后后将将C复复制制到到A中中pos起起共共LC个个字字符符，此此时时可可能能会会出出现串插入时的三种情况，现串插入时的三种情况，应按三种情况作相应处理。应按三种情况作相应处理。(1)串插入函数。串插入函数。StrInsert(s,pos,t)/*在串在串s中序号为中序号为pos的字符之前插入串的字符之前插入串t*/SString*s,t;intpos;inti;if(poss-len+1)return(0);/*插入位置不合法插入位置不合法*/if(s-len+t.lenlen+t.len-1;i=t.len+pos-1;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos-1=t.chi;s-len=s-len+t.len;elseif(pos+t.lenMAXLEN,但串但串t的字符序列可以全部插入的字符序列可以全部插入*/for(i=MAXLEN-1;it.len+pos-1;i-)s-chi=s-chi-t.len;for(i=0;ichi+pos-1=t.chi;s-len=MAXLEN;else/*串串t的部分字符序列要舍弃的部分字符序列要舍弃*/for(i=0;ichi+pos-1=t.chi;s-len=MAXLEN;return(1);【算法【算法4.1串插入函数】串插入函数】(2)串删除函数。串删除函数。StrDelete(s,pos,len)/*在串在串s中删除从序号中删除从序号pos起起len个字符个字符*/SString*s;intpos,len;inti;if(pos(s-len-len+1)return(0);for(i=pos+len-1;ilen;i+)s-chi-len=s-chi;s-len=s-len-len;return(1);【算法【算法4.2串删除函数】串删除函数】(3)串复制函数。串复制函数。StrCopy(s,t)/*将串将串t的值复制到串的值复制到串s中中*/SString*s,t;inti;for(i=0;ichi=t.chi;s-len=t.len;【算法【算法4.3串复制函数】串复制函数】(4)判空函数。判空函数。StrEmpty(s)/*若串若串s为空为空(即串长为即串长为0),则返回则返回1,否则返回否则返回0*/SStrings;if(s.len=0)return(1);elsereturn(0);【算法【算法4.4判空函数】判空函数】(5)串比较函数。串比较函数。StrCompare(s,t)/*若串若串s和和t相等相等,则返回则返回0；若；若st，则返回，则返回0；若；若st，则返回则返回0*/SStrings,t;inti;for(i=0;is.len&ilen=0;return(1);【算法【算法4.7清空函数】清空函数】(8)连接函数。连接函数。StrCat(s,t)/*将串将串t连接在串连接在串s的后面的后面*/SString*s,t;inti,flag;if(s-len+t.lenlen;ilen+t.len;i+)s-chi=t.chi-s-len;s-len+=t.len;flag=1;for(i=0;ilen-1;i+)s-chi+s-len=t.chi;elseif(s-lenlen;ichi=t.chi-s-len;s-len=MAXLEN;flag=0;elseflag=0;/*串串s的长度等于的长度等于MAXLEN,串串t不被连接不被连接*/return(flag);【算法【算法4.8连接函数】连接函数】(9)求子串函数。求子串函数。SubString(sub,s,pos,len)/*将串将串s中序号中序号pos起起len个字符复制到个字符复制到sub中中*/SString*sub,s;intpos,len;inti;if(poss.len|lens.len-pos+1)sub-len=0;return(0);elsefor(i=0;ichi=s.chi+pos-1;sub-len=len;return(1);【算法【算法4.9求子串函数】求子串函数】(10)定位函数。定位函数。StrIndex(s,pos,t)/*求串求串t在串在串s中的位置中的位置*/SStrings,t;intpos;inti,j;if(t.len=0)return(0);i=pos-1;j=0;while(is.len&j=t.len)return(i-j);elsereturn(0);【算法【算法4.10定位函数】定位函数】4.2.2堆串堆串假假设设以以一一维维数数组组heapMAXSIZE表表示示可可供供字字符符串串进进行行动动态态分分配配的的存存储储空空间间，并并设设intfree指指向向heap中中未未分分配配区区域域的的开开始始地地址址(初初始始化化时时free=0)。在在程程序序执执行行过过程程中中，当当生生成成一一个个新新串串时时，就就从从free指指示示的的位位置置起起，为为新新串串分分配配一一个个所所需需大大小小的的存存储储空空间间，同同时时建建立立该该串串的的描描述述。这这种种存存储储结结构构称称为为堆堆结结构构。此时，堆串可定义如下：此时，堆串可定义如下：typedefstructintlen；intstart；HeapString；其其中中len域域指指示示串串的的长长度度，start域域指指示示串串的的起起始始位位置置。借借助助此此结结构构可可以以在在串串名名和和串串值值之之间间建建立立一一个个对对应应关关系系，称称为为串串名名的的存存储储映象。系统中所有串名的存储映象构成一个符号表。映象。系统中所有串名的存储映象构成一个符号表。图图4.1是是一一个个堆堆存存储储及及符符号号表表，其其中中a=aprogram，b=string，c=process图图4.1堆串的存储映象示例堆串的存储映象示例a ap pr ro og gr ra amms st tr ri in ng gp pr ro oc ce es ss sHeapMAXSIZEFree=23符号名符号名lenlenStartStarta a9 90 0b b7 79 9c c7 71616符号表在在C语语言言中中，已已经经有有一一个个称称为为“堆堆”的的自自由由存存储储空空间间，并并可可用用malloc（）和和free（）函函数数完完成成动动态态存存储储管管理理。因因此此，我我们们可可以以直直接接利利用用C语语言言中中的的“堆堆”实实现现堆堆串串。此此时时，堆堆串串可可定义如下：定义如下：typedefstructchar*ch；intlen；HString；(1)串赋值函数。串赋值函数。StrAssign(s，tval)/*将字符常量将字符常量tval的值赋给串的值赋给串s*/HString*s;char*tval;intlen，i=0;if(s-ch!=NULL)free(s-ch);while(tvali!=0)i+;len=i;if(len)s-ch=(char*)malloc(len);if(s-ch=NULL)return(0);for(i=0;ichi=tvali;elses-ch=NULL;s-len=len;return(1);【算法【算法4.11串赋值函数】串赋值函数】(2)串插入函数。串插入函数。StrInsert(s，pos，t)/*在串在串s中序号为中序号为pos的字符之前插入串的字符之前插入串t*/HString*s，t;intpos;inti;char*temp;if(poss-len|s-len=0)return(0);temp=(char*)malloc(s-len+t.len);if(temp=NULL)return(0);for(i=0;ichi;for(i=0;it.len;i+)tempi+pos=t.chi;for(i=pos;ilen;i+)tempi+t.len=s-chi;s-len+=t.len;free(s-ch);s-ch=temp;return(1);【算法【算法4.12串插入函数】串插入函数】(3)串删除函数。串删除函数。StrDelete(s，pos，len)/*在串在串s中删除从序号中删除从序号pos起的起的len个字符个字符*/HString*s;intpos，len;inti;char*temp;if(pos(s-len-len)return(0);temp=(char*)malloc(s-len-len);if(temp=NULL)return(0);for(i=0;ichi;for(i=pos;ilen-len;i+)tempi=s-chi+len;s-len=s-len-len;free(s-ch);s-ch=temp;return(1);【算法【算法4.13串删除函数】串删除函数】(4)串复制函数。串复制函数。StrCopy(s，t)/*将串将串t的值复制到串的值复制到串s中中*/HString*s，t;inti;s-ch=(char*)malloc(t.len);if(s-ch=NULL)return(0);for(i=0;ichi=t.chi;s-len=t.len;return(1);【算法【算法4.14串复制函数】串复制函数】(5)判空函数。判空函数。StrEmpty(s)/*若串若串s为空为空(即串长为即串长为0)，则返回，则返回1，否则返回，否则返回0*/HStrings;if(s.len=0)return(1);elsereturn(0);【算法【算法4.15判空函数】判空函数】(6)串比较函数。串比较函数。StrCompare(s，t)/*若若串串s和和t相相等等，则则返返回回0；若若st，则则返返回回1；若若st，则返回则返回-1*/HStrings，t;inti;for(i=0;is.len&ich!=NULL)free(s-ch);s-ch=NULL;s-len=0;return(1);【算法【算法4.18清空函数】清空函数】(9)连接函数。连接函数。StrCat(s，t)/*将串将串t连接在串连接在串s的后面的后面*/HString*s，t;inti;char*temp;temp=(char*)malloc(s-len+t.len);if(temp=NULL)return(0);for(i=0;ilen;i+)tempi=s-chi;for(i=s-len;ilen+t.len;i+)tempi=t.chi-s-len;s-len+=t.len;free(s-ch);s-ch=temp;return(1);【算法【算法4.19连接函数】连接函数】(10)求子串函数。求子串函数。SubString(sub，s，pos，len)/*将串将串s中序号中序号pos起的起的len个字符复制到个字符复制到sub中中*/HString*sub，s;intpos，len;inti;if(sub-ch!=NULL)free(sub-ch);if(poss.len|lens.len-pos)sub-ch=NULL;sub-len=0;return(0);elsesub-ch=(char*)malloc(len);if(sub-ch=NULL)return(0);for(i=0;ichi=s.chi+pos;sub-len=len;return(1);【算法【算法4.20求子串函数】求子串函数】(11)定位函数。定位函数。StrIndex(s，pos，t)/*求串求串t在串在串s中的位置中的位置*/HStrings，t;intpos;inti，j;if(s.len=0|t.len=0)return(0);i=pos;j=0;while(is.len&j=t.len)return(i-j);elsereturn(0);【算法【算法4.21定位函数】定位函数】模式匹配模式匹配 串的模式匹配即子串定位是一种重要的串运算。设串的模式匹配即子串定位是一种重要的串运算。设s和和t是给定的两是给定的两个串，个串，在主串在主串s中找到等于子串中找到等于子串t的过程称为模式匹配的过程称为模式匹配，如果在，如果在s中找到中找到等于等于t的子串，则称匹配成功，函数返回的子串，则称匹配成功，函数返回t在在s中的首次出现的存储位置中的首次出现的存储位置(或序号或序号)，否则匹配失败，返回，否则匹配失败，返回-1。t也称为模式。为了运算方便，设也称为模式。为了运算方便，设字符串的长度存放在字符串的长度存放在0号单元，串值从号单元，串值从1号单元存放，这样字符序号与存号单元存放，这样字符序号与存储位置一致。储位置一致。补充：补充：简单的模式匹配算法算法思想如下算法思想如下：首先将s1与t1进行比较，若不同，就将s2与t1进行比较，.，直到s的某一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本趟开始字符的下一个字符，即si-j+2，t返回到t1，继续开始下一趟的比较，重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是i-j+1或i-t.len，否则，匹配失败。设主串设主串s=“ababcabcacbab”s=“ababcabcacbab”，模式，模式t=“abcac”t=“abcac”，匹配过程如下图所示：，匹配过程如下图所示：第一趟第一趟 第二趟第二趟 第三趟第三趟 第四趟第四趟 第五趟第五趟 第六趟第六趟 简单模式匹配的匹配过程简单模式匹配的匹配过程 依据这个思想，算法描述如下依据这个思想，算法描述如下:intStrIndex_BF(char*s,char*t)(char*s,char*t)/*/*从串从串s s的第一个字符开始找首次与串的第一个字符开始找首次与串t t相等的子串相等的子串*/*/inti=1,j=1;while(i=s.len&jt.len)return(i-t.len);/*/*匹配成功，返回存储位置匹配成功，返回存储位置*/*/elsereturn1;该算法简称为该算法简称为BFBF算法。分析它的时间复杂度，设串算法。分析它的时间复杂度，设串s s长度为长度为n n，串，串t t长度为长度为m m。匹配成功的情况下，考虑两种极端情况：匹配成功的情况下，考虑两种极端情况：在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：在最好情况下，每趟不成功的匹配都发生在第一对字符比较时：例如：例如：s=s=aaaaaaaaaabcaaaaaaaaaabct=bcbc设设匹匹配配成成功功发发生生在在s si处处，则则字字符符比比较较次次数数在在前前面面i-1i-1趟趟匹匹配配中中共共比比较较了了i-1i-1次次，第第i i趟趟成成功功的的匹匹配配共共比比较较了了m m次次，所所以以总总共共比比较较了了i-1+mi-1+m次次，所所有有匹匹配配成成功功的的可可能能共共有有n-m+1n-m+1种种，设设从从s si开开始始与与t t串串匹匹配配成成功功的的概概率率为为p pi，在在等等概概率率情情况况下下p pi=1/(n-m+1)，因此最好情况下平均比较的次数是：，因此最好情况下平均比较的次数是：即最好情况下的时间复杂度是即最好情况下的时间复杂度是O(n+m)O(n+m)。在最坏情况下，每趟不成功的匹配都发生在在最坏情况下，每趟不成功的匹配都发生在t t的最后一个字符：的最后一个字符：例如：例如：s=s=aaaaaaaaaaabaaaaaaaaaaabt=aaabaaab设设匹匹配配成成功功发发生生在在s si处处，则则在在前前面面i-1i-1趟趟匹匹配配中中共共比比较较了了(i-1)*m(i-1)*m次次，第第i i趟趟成成功功的的匹匹配配共共比比较较了了m m次次，所所以以总总共共比比较较了了i*mi*m次次，因因此此最最坏坏好好情情况况下下平平均均比比较较的的次数是：次数是：即最坏情况下的时间复杂度是即最坏情况下的时间复杂度是O(n*m)O(n*m)。上述算法中匹配是从上述算法中匹配是从s s串的第一个字符开始的，有时算法要求从指定位置开始，串的第一个字符开始的，有时算法要求从指定位置开始，这时算法的参数表中要加一个位置参数这时算法的参数表中要加一个位置参数pospos：StrIndex(shar*s,int pos,char*t)StrIndex(shar*s,int pos,char*t)，比较的初始位置定位在，比较的初始位置定位在pospos处。处。改进后的模式匹配算法改进后的模式匹配算法BF算法简单但效率较低，一种对算法简单但效率较低，一种对BFBF算法做了很大改进的模式匹配算法是克努特算法做了很大改进的模式匹配算法是克努特(Knuth)(Knuth)，莫里斯，莫里斯(Morris)(Morris)和普拉特和普拉特(Pratt)(Pratt)同时设计的，简称同时设计的，简称KMPKMP算法。算法。（1）KMPKMP算法的思想：算法的思想：分析分析上面上面算法的执行过程算法的执行过程,造成造成BFBF算法速度慢的原因是回溯，即在某趟的匹配算法速度慢的原因是回溯，即在某趟的匹配过程失败后，对于过程失败后，对于s s串要回到本趟开始字符的下一个字符，串要回到本趟开始字符的下一个字符，t t串要回到第一个字串要回到第一个字符。而这些回溯并不是必要的。如上图所示的匹配过程，在第三趟匹配过程中，符。而这些回溯并不是必要的。如上图所示的匹配过程，在第三趟匹配过程中，s s3s6和和t t1t4是匹配成功的，是匹配成功的，s s7t t5匹配失败，因此有了第四趟，其实这一趟是匹配失败，因此有了第四趟，其实这一趟是不必要的：由图可看出，因为在第三趟中有不必要的：由图可看出，因为在第三趟中有s s4=t2，而，而t t1t t2，肯定有，肯定有t t1s s4。同。同理第五趟也是没有必要的，所以从第三趟之后可以直接到第六趟，进一步分析理第五趟也是没有必要的，所以从第三趟之后可以直接到第六趟，进一步分析第六趟中的第一对字符第六趟中的第一对字符s s6和和t t1的比较也是多余的，因为第三趟中已经比过了的比较也是多余的，因为第三趟中已经比过了s s6和和t t4，并且，并且s s6=t4，而，而t t1=t4，必有，必有s s6=t1，因此第六趟的比较可以从第二对字符，因此第六趟的比较可以从第二对字符s s7和和t t2开始进行，这就是说，第三趟匹配失败后，指针开始进行，这就是说，第三趟匹配失败后，指针i i不动，而是将模式串不动，而是将模式串t t向右向右“滑动滑动”，用，用t t2“对准对准”s s7继续进行，依此类推。这样的处理方法指针继续进行，依此类推。这样的处理方法指针i i是无是无回溯的。回溯的。综综上上所所述述，希希望望某某趟趟在在s si和和t tj匹匹配配失失败败后后，指指针针i i不不回回溯溯，模模式式t t向向右右“滑滑动动”至至某某个个位位置置上上，使使得得t tk对对准准 s si继继续续向向右右进进行行。显显然然，现现在在问问题题的的关关键键是是串串t t“滑滑动动”到到哪哪个个位位置置上上？不不妨妨设设位位置置为为k k，即即s si和和t tj匹匹配配失失败败后后，指指针针i i不不动动，模模式式t t向向右右“滑滑动动”，使使t tk和和s si对对准继续向右进行比较，要满足这一假设，就要有如下关系成立：准继续向右进行比较，要满足这一假设，就要有如下关系成立：t t1t2tk-1 =s si-k+1si-k+2si-1 (1)(1)式左边是式左边是t tk前面的前面的k-1k-1个字符，右边是个字符，右边是s si前面的前面的k-1k-1个字符。个字符。而本趟匹配失败是在而本趟匹配失败是在s si和和t tj之处，已经得到的部分匹配结果是：之处，已经得到的部分匹配结果是：t t1t2tj-1 =s si-j+1si-j+2s si-1 (2)因为因为kjkj，所以有：，所以有：t tj-k+1tj-k+2tj-1 =s si-k+1si-k+2s si-1 (3)(3)式左边是式左边是 t tj前面的前面的k-1k-1个字符，右边是个字符，右边是s si前面的前面的k-1k-1个字符，个字符，通过通过(4.1)(4.1)和和(4.3)(4.3)得到关系：得到关系：t t1t2tk-1 =t tj-k+1tj-k+2tj-1 (4)结论：某趟在结论：某趟在s si和和t tj匹配失败后，如果模式串中有满足关系匹配失败后，如果模式串中有满足关系(4)(4)的子串存在，即：的子串存在，即：模式中的前模式中的前k-1k-1个字符与模式中个字符与模式中t tj字符前面的字符前面的k-1k-1个字符相等时，模式个字符相等时，模式t t就可以向右就可以向右“滑动滑动”至使至使t tk和和s si对准，继续向右进行比较即可。对准，继续向右进行比较即可。（2 2）nextnext函数函数模模式式中中的的每每一一个个t tj都都对对应应一一个个k k值值，由由(4)(4)式式可可知知，这这个个k k值值仅仅依依赖赖与与模模式式t t本本身身字字符符序序列列的的构构成成，而而与与主主串串s s无无关关。我我们们用用nextjnextj表表示示t tj对对应应的的k k值，根据以上分析，值，根据以上分析，nextnext函数有如下性质：函数有如下性质：nextjnextj是一个整数，且是一个整数，且0 0nextjjnextjj；为了使为了使t t的右移不丢失任何匹配成功的可能，当存在多个满足的右移不丢失任何匹配成功的可能，当存在多个满足(4)(4)式的式的k k 值时，值时，应取最大的，这样向右应取最大的，这样向右“滑动滑动”的距离最短，的距离最短，“滑动滑动”的字符的字符为为j-nextjj-nextj个；个；如如果果在在t tj j前前不不存存在在满满足足(4.4)(4.4)式式的的子子串串，此此时时若若t t1 1t tj j，则则k=1;k=1;若若t t1 1=t=tj j，则，则k=0;k=0;这时这时“滑动滑动”的最远，为的最远，为j-1j-1个字符即用个字符即用t t1 1 和和s sj+1j+1继续比较。继续比较。因此，因此，nextnext函数定义如下函数定义如下 ：设有模式串：设有模式串：t=t=abcaababcabcaababc，则它的，则它的nextnext函数值为：函数值为：j123456789模式串abcaababcnextj011021311(3)KMP算法算法 在求得模式的在求得模式的nextnext函数之后，匹配可如下进行：假设以指针函数之后，匹配可如下进行：假设以指针i i和和j j分别指分别指示主串和模式中的比较字符，令示主串和模式中的比较字符，令i i的初值为的初值为pospos，j j的初值为的初值为1 1。若在匹配过。若在匹配过程中程中s sittj，则，则i i和和j j分别增，若分别增，若s sittj匹配失败后，则匹配失败后，则i i不变，不变，j j退到退到nextjnextj位置再比较，若相等，则指针各自增，否则位置再比较，若相等，则指针各自增，否则j j再退到下一个再退到下一个nextnext值的位置，依此类推。直至下列两种情况：一种是值的位置，依此类推。直至下列两种情况：一种是j j退到某个退到某个nextnext值时字符值时字符比较相等，则比较相等，则i i和和j j分别增继续进行匹配分别增继续进行匹配;另一种是另一种是j j退到值为零（即模式退到值为零（即模式的第一个字符失配），则此时的第一个字符失配），则此时i i和和j j也要分别增，表明从主串的下一个字也要分别增，表明从主串的下一个字符起和模式重新开始匹配。符起和模式重新开始匹配。设主串设主串s=“acabaabaabcacaabc”s=“acabaabaabcacaabc”，子串，子串t=“abaabcac”t=“abaabcac”，下图是一个利，下图是一个利用用nextnext函数进行匹配的过程示意图。函数进行匹配的过程示意图。在假设已有在假设已有nextnext函数情况下，函数情况下，KMPKMP算法如下：算法如下：intStrIndex_KMP(char*s,char*t,intpos)/*从串s的第pos个字符开始找首次与串t相等的子串*/inti=pos,j=1,slen,tlen;while(i=s.len&jt.len)returni-t.len;/*匹配成功，返回存储位置*/elsereturn1;(4)如何求如何求nextnext函数函数由以上讨论知，nextnext函数值仅取决于模式本身而和主串无关函数值仅取决于模式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。由定义知：next1=0(4.5)设nextj=k，即有：t1t2tk-1=tj-k+1tj-k+2tj-1(4.6)(4.6)nextj+1=?可能有两种情况：第一种情况：若tktj则表明在模式串中t1t2tk=tj-k+1tj-k+2tj (4.7)这就是说nextj+1=k+1，即nextj=nextj+1(4.8)第二种情况：若tktj则表明在模式串中t1t2tktj-k+1tj-k+2tj (4.9)此时可把求此时可把求nextnext函数值的问题看成是一个模式匹配问题，整个模式串既是主串又函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有是模式，而当前在匹配的过程中，已有(4.6)(4.6)式成立，则当式成立，则当t tkt tj时应将模式向右时应将模式向右滑动，使得第滑动，使得第nextknextk个字符和个字符和“主串主串”中的第中的第j j个字符相比较。若个字符相比较。若nextk=knextk=k，且且t tkt tj，则说明在主串中第，则说明在主串中第j+1j+1个字符之前存在一个最大长度为个字符之前存在一个最大长度为k k的子串，使的子串，使得得t t1t2tk =t tj-k+1+1tj-k+2+2 tj (4.10)因此：因此：nextj+1=nextk+1(4.11)同理若同理若t tk t tj，则将模式继续向右滑动至使第，则将模式继续向右滑动至使第nextknextk 个字符和个字符和t tj对齐，依此对齐，依此类推，直至类推，直至t tj和模式中的某个字符匹配成功或者不存在任何和模式中的某个字符匹配成功或者不存在任何 k(1 k(1 kk j)k j)满足满足(4.10)(4.10)，此时若，此时若t t1t tj+1，则有：则有：nextj+1=1nextj+1=1（4.12）否则若否则若t t1=tj+1，则有：，则有：nextj+1=0nextj+1=0(4.13)综上所述，求综上所述，求nextnext函数值过程的算法如下：函数值过程的算法如下：voidGetNext(char*t,intnext)/*求模式求模式t t的的nextnext值并寸入值并寸入nextnext数组中数组中*/*/int i=1,j=0;int i=1,j=0;next1=0;while(i0&ti!=tj)j=nextj;i+;j+;if(ti=tj)nexti=nextj;elsenexti=j;4.2.3块链串块链串由由于于串串也也是是一一种种线线性性表表，因因此此也也可可以以采采用用链链式式存存储储。由由于于串串的的特特殊殊性性（每每个个元元素素只只有有一一个个字字符符），在在具具体体实实现现时时，每每个个结结点点既既可可以以存存放放一一个个字字符符，也也可可以以存存放放多多个个字字符符。每每个个结结点点称称为为块块，整整个个链链表表称称为为块块链链结结构构，为为了了便便于于操操作作，再再增增加一个尾指针。块链结构可定义如下：加一个尾指针。块链结构可定义如下：defineBLOCK-SIZEtypedefstructBlockcharchBLOCK#-SIZE;structBlock*next;Block;typedefstructBlock*head;Block*tail;intlength;BLString;4.3串的应用举例：文本编辑串的应用举例：文本编辑文文本本编编辑辑程程序序用用于于源源程程序序的的输输入入和和修修改改，公公文文书书信信、报报刊刊和和书书籍籍的的编编辑辑排排版版等等。常常用用的的文文本本编编辑辑程程序序有有Edit、WPS、Word等等。文文本本编编辑辑的的实实质质是是修修改改字字符符数数据据的的形形式式和和格格式式，虽虽然然各各个个文文本本编编辑辑程程序序的的功功能能不不同同，但但基基本本操操作作是是一一样样的的，都都包包括括串串的的查查找找、插插入入和和删删除除等等。为为了了编编辑辑方方便便，可可以以用用分分页页符符和和换换行行符符将将文文本本分分为为若若干干页页，每每页页有有若若干干行行。我我们们把把文文本本当当作作一一个个字字符符串串，称称为为文文本本串串，页页是是文文本本串串的的子子串串，行行是是页的子串。页的子串。我我们们采采用用堆堆存存储储结结构构来来存存储储文文本本，同同时时设设立立页页指指针针、行行指指针针和和字字符符指指针针，分分别别指指向向当当前前操操作作的的页页、行行和和字字符符，同同时时建建立立页表和行表存储每一页、每一行的起始位置和长度。页表和行表存储每一页、每一行的起始位置和长度。假设有如下假设有如下PASCAL源程序：源程序：FUNCmax(x，y：integer)：integer;VARz：integer;BEGINIFxyTHENz:=x;ELSEz:=y;RETURN(z);END;图4.2文本格式示例结束语结束语我们还在路上，余晖消失之前都不算终点。Thankyouforcoming,sendthissentencetoyou,wearestillontheroad,beforetheafterglowdisappearsarenottheend.为方便温习本节课程内容，本课件可在下载完成后进行查阅Thankyouforlistening.Fortheconvenienceofreviewingthecontentofthiscourse,thiscoursewarecanbeviewedafterdownloading