第四章 串.ppt
《第四章 串.ppt》由会员分享,可在线阅读,更多相关《第四章 串.ppt(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第4章章串串1.串及其基本运算串及其基本运算 2.串的顺序存储及基本运算串的顺序存储及基本运算3.串的堆存储结构串的堆存储结构4.串的链式存储结构串的链式存储结构5.文本编辑文本编辑串操作应用串操作应用【教学目的教学目的】掌握串的定义、逻辑结构、存储结构及操作掌握串的定义、逻辑结构、存储结构及操作实现以及串的应用实现以及串的应用【教学重点教学重点】串的顺序、链式、堆存储结构及串的操作的串的顺序、链式、堆存储结构及串的操作的实现实现【教学难点教学难点】串的模式匹配算法工作原理、经典的模式匹串的模式匹配算法工作原理、经典的模式匹配端法、配端法、KMP算法和改进的算法和改进的KMP算法算法4.1串
2、及其基本运算串及其基本运算 一、串的基本概念一、串的基本概念串串:是由零个或多个任意字符组成的有限序列。是由零个或多个任意字符组成的有限序列。一般记作:一般记作:s=“s1s2sn”s是是串名串名;“s1s2sn”为为串值串值,引号本身不属于串的内容;,引号本身不属于串的内容;si:串中的任一个,称为串中的任一个,称为串的元素串的元素,是构成串的基本单,是构成串的基本单位,位,i是它在整个串中的序号是它在整个串中的序号(位置位置);n为串的为串的长度长度,表示串中所包含的字符个数,表示串中所包含的字符个数当当n=0时,称为时,称为空串空串,通常记为,通常记为。子串与主串:子串与主串:串中任意连
3、续的字符组成的子序列称为该串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。串的子串。包含子串的串相应地称为主串。子串的位置:子串的位置:子串的第一个字符在主串中的序号称为子子串的第一个字符在主串中的序号称为子串的位置。串的位置。例:例:s1=“WelcometoBeijing”s2=“Welcome”s3=“Bei”s4=“Welcometo”s5=“Jing”串相等:串相等:当且仅当串值相等,即两个串的长度相等且对当且仅当串值相等,即两个串的长度相等且对应字符都相等。应字符都相等。二、串的基本操作二、串的基本操作1.求串长求串长StrLength(s)操作条件:串操
4、作条件:串s存在存在操作结果:求出串操作结果:求出串s中的字符的个数。中的字符的个数。2.串赋值串赋值StrAssign(s1,s2)操作条件:操作条件:s1是一个串变量,是一个串变量,s2或者是一个串常量,或者是一个串变量。或者是一个串常量,或者是一个串变量。操作结果:将操作结果:将s2的串值赋值给的串值赋值给s1,s1原来的值被覆盖掉。原来的值被覆盖掉。3.连接操作连接操作:StrConcat(s1,s2,s)或或StrConcat(s1,s2)操作条件:串操作条件:串s1,s2存在。存在。操作结果:两个串的联接就是将一个串的串值紧接着放在操作结果:两个串的联接就是将一个串的串值紧接着放在
5、另一个串的后面,连接成一个串。另一个串的后面,连接成一个串。4.求子串求子串SubStr(t,s,i,len):操作条件:串操作条件:串s存在存在操作结果:产生一个新串操作结果:产生一个新串t。5.串比较串比较StrCmp(s1,s2)操作条件:串操作条件:串s1,s2存在。存在。操作结果:若操作结果:若s1=s2,操作返回值为,操作返回值为1;否则返回值为;否则返回值为0。6.子串定位子串定位StrIndex(s,t)或或StrIndex(s,t,p)操作条件:串操作条件:串s,t存在。存在。操作结果:若操作结果:若ts,则操作返回,则操作返回t在在s中首次出现的位置,中首次出现的位置,否则
6、返回值为否则返回值为-1。7.串插入串插入StrInsert(s,i,t)操作条件:串操作条件:串s,t存在,存在,1iStrLength(s)+1。操作结果:将串操作结果:将串t插入到串插入到串s的第的第i个字符位置上个字符位置上8.串删除串删除:StrDelete(s,i,len)操作条件:串操作条件:串s存在。存在。操作结果:删除串操作结果:删除串s中从第中从第i个字符开始的长度为个字符开始的长度为len的子的子串。串。9.串替换串替换StrRep(s,t,r)操作条件:串操作条件:串s,t,r存在,存在,t不为空。不为空。操作结果:用串操作结果:用串r替换串替换串s中出现的所有与串中出
7、现的所有与串t相等的不重相等的不重叠的子串。叠的子串。4.2串的顺序存储与操作串的顺序存储与操作 一、串的定长顺序存储一、串的定长顺序存储类似于顺序表,用一组地址连续的存储单元存储串值中类似于顺序表,用一组地址连续的存储单元存储串值中的字符序列,所谓定长是指按预定义的大小,为每一个串变量的字符序列,所谓定长是指按预定义的大小,为每一个串变量分配一个固定长度的存储区,如:分配一个固定长度的存储区,如:#defineMAXSIZE256charsMAXSIZE;则串的最大长度不能超过则串的最大长度不能超过256。如何标识实际长度?如何标识实际长度?1.类似顺序表,串描述如下:类似顺序表,串描述如下
8、:typedefstructchardataMAXSIZE;intLength;/*串的长度串的长度*/SeqString;定义一个串变量:定义一个串变量:SeqStrings;2、在串尾存储一个不会在串中出现的特殊字符作为串的终结、在串尾存储一个不会在串中出现的特殊字符作为串的终结符,以此表示串的结尾。比如符,以此表示串的结尾。比如C语言中处理定长串的方法就是语言中处理定长串的方法就是这样的,它是用这样的,它是用0来表示串的结束。这种存储方法不能直来表示串的结束。这种存储方法不能直接得到串的长度,是用判断当前字符是否是接得到串的长度,是用判断当前字符是否是0来确定串是来确定串是否结束,从而求
9、得串的长度。否结束,从而求得串的长度。charsMAXSIZE;012345678910.MAXSIZE-1abcdefghijk03、在串首存储串长。比如、在串首存储串长。比如Pascal语言中处理定长串的方法。语言中处理定长串的方法。charsMAXSIZE1;s0:存放串长:存放串长s1.ss0:存放串值:存放串值012345678910.MAXSIZE9abcdefghi.1、求串长、求串长intStrLength(chars)inti=0;while(si!=0)i+;returni;return(s0)2、串赋值、串赋值voidStrAssign(chars1,char*s2)in
10、ti;for(i=0;s2i!=0;i+)s1i=s2i;s1i=0;for(i=0;s2i!=0;i+)s1i+1=s2i;s10=i;串拷贝:串拷贝:for(i=0;iMAXSIZE-1)return0;for(j=0;s1j!=0;j+,i+)si=s1j;for(j=0;s2j!=0;j+,i+)si=s2j;si=0;return1;for(j=1,i=1;j=s10;j+,i+)si=s1j;for(j=1;j=s20;j+,i+)si=s2j;s0=s10+s20;4、求子串、求子串intSubStr(chart,chars,inti,intlen)/用用t返回串返回串s中第个中
11、第个i字符开始的长度为字符开始的长度为len的子串的子串intslen;slen=StrLength(s);if(islen|lenslen-i+1)printf(参数不对参数不对);return0;for(j=0;jlen;j+)tj=si-1+j;tj=0;return1;for(j=1;j=len;j+)tj=si-1+j;t0=len;5、串比较、串比较intStrCmp(chars1,chars2)/串串s1与串与串s2若相等则返回若相等则返回1,否则返回,否则返回0inti=0;while(s1i!=0&s2i!=0&s1i=s2i)i+;return(s1i=s2i);C:ret
12、urn(s1i-s2i);6、子串定位、子串定位StrIndex(s,t):模式匹配:模式匹配串的模式匹配即子串定位是一种重要的串运算。串的模式匹配即子串定位是一种重要的串运算。设设s和和t是给定的两个串,在主串是给定的两个串,在主串s中找到等于子串中找到等于子串t的过程称为的过程称为模式匹配,如果在模式匹配,如果在s中找到等于中找到等于t的子串,则称匹配成功,函数的子串,则称匹配成功,函数返回返回t在在s中的首次出现的存储位置中的首次出现的存储位置(或序号或序号),否则匹配失败,否则匹配失败,返回返回-1。t称为模式串,称为模式串,s称为主串。为了运算方便,设字符串称为主串。为了运算方便,设
13、字符串的长度存放在的长度存放在0号单元,串值从号单元,串值从1号单元存放,这样字符序号与号单元存放,这样字符序号与存储位置一致。存储位置一致。算法思想如下:算法思想如下:首先将首先将s1与与t1进行比较,若不同,就将进行比较,若不同,就将s2与与t1进行比进行比较较,.,直到,直到s的某一个字符的某一个字符si和和t1相同,再将它们之后的相同,再将它们之后的字符进行比较,若也相同,则如此继续往下比较,当字符进行比较,若也相同,则如此继续往下比较,当s的的某一个字符某一个字符si与与t的字符的字符tj不同时,则不同时,则s返回到本趟开始字符返回到本趟开始字符的下一个字符,即的下一个字符,即si-
14、j+2,t返回到返回到t1,继续开始下一趟的,继续开始下一趟的比较,重复上述过程。若比较,重复上述过程。若t中的字符全部比完,则说明本中的字符全部比完,则说明本趟匹配成功,本趟的起始位置是趟匹配成功,本趟的起始位置是i-j+1或或i-t0,否则,匹配,否则,匹配失败。失败。简单模式匹配过程简单模式匹配过程设主串设主串s=ababcabcacbab,模式,模式t=abcac,匹配过程,匹配过程:ababcabcacbababcacij依据这个思想,简单的模式匹配算法(依据这个思想,简单的模式匹配算法(BF)描述如下)描述如下:intStrIndex_BF(char*s,char*t)/从串从串s
15、的第一个字符开始找首次与串的第一个字符开始找首次与串t相等的子串相等的子串inti=1,j=1;while(i=s0&jt0)return(i-t0);/匹配成功,返回存储位置匹配成功,返回存储位置elsereturn1;简单的模式匹配算法(简单的模式匹配算法(BF)时间复杂度分析)时间复杂度分析:设串设串s长度为长度为n,串,串t长度为长度为m,在匹配成功的情况下,在匹配成功的情况下考虑两种极端情况:考虑两种极端情况:(1)在最好情况下,每趟不成功的匹配都发生在第一对字符)在最好情况下,每趟不成功的匹配都发生在第一对字符比较时:比较时:例如:例如:s=“aaaaaaaaaabc”t=bc设匹
16、配成功发生在设匹配成功发生在si处,则字符比较次数在前面处,则字符比较次数在前面i-1趟匹趟匹配中共比较了配中共比较了i-1次,第次,第i趟成功的匹配共比较了趟成功的匹配共比较了m次,所以总共次,所以总共比较了比较了i-1+m次,所有匹配成功的可能共有次,所有匹配成功的可能共有n-m+1种,设从种,设从si开开始与始与t串匹配成功的概率为串匹配成功的概率为pi,在等概率情况下,在等概率情况下pi=1/(n-m+1),因此最好情况下平均比较的次数是:因此最好情况下平均比较的次数是:简单的模式匹配算法(简单的模式匹配算法(BF)时间复杂度分析)时间复杂度分析:设串设串s长度为长度为n,串,串t长度
17、为长度为m,在匹配成功的情况下,在匹配成功的情况下考虑两种极端情况:考虑两种极端情况:(2)在最坏情况下,每趟不成功的匹配都发生在在最坏情况下,每趟不成功的匹配都发生在t的最后一的最后一个字符:例如:个字符:例如:s=“aaaaaaaaaaab”t=aaab设匹配成功发生在设匹配成功发生在si处,则在前面处,则在前面i-1趟匹配中共比较了趟匹配中共比较了(i-1)*m次,第次,第i趟成功的匹配共比较了趟成功的匹配共比较了m次,所以总共比较了次,所以总共比较了i*m次,因此最坏的情况下平均比较的次数是:次,因此最坏的情况下平均比较的次数是:因此:因此:BF算法的时间复杂度为算法的时间复杂度为O(
18、mn)简单的模式匹配算法(简单的模式匹配算法(BF)说明)说明:上述算法中匹配是从上述算法中匹配是从s串的第一个字符开始的,有时算法要串的第一个字符开始的,有时算法要求从指定位置开始,这时算法的参数表中要加一个位置参数求从指定位置开始,这时算法的参数表中要加一个位置参数pos:StrIndex(shar*s,intpos,char*t),比较的初始位置定位,比较的初始位置定位在在pos处也可以。上面的算法是处也可以。上面的算法是pos=1的情况。的情况。同理第五趟也是没有必要的,所以从第三趟之后可以直接到第同理第五趟也是没有必要的,所以从第三趟之后可以直接到第六趟,进一步分析第六趟中的第一对字
19、符六趟,进一步分析第六趟中的第一对字符s6和和t1的比较也是多的比较也是多余的,因为第三趟中已经比过了余的,因为第三趟中已经比过了s6和和t4,并且,并且s6=t4,而,而t1=t4,必有,必有s6=t1,因此第六趟的比较可以从第二对字符,因此第六趟的比较可以从第二对字符s7和和t2开开始进行,这就是说,第三趟匹配失败后,指针始进行,这就是说,第三趟匹配失败后,指针i不动,而是将不动,而是将模式串模式串t向右向右“滑动滑动”,用,用t2“对准对准”s7继续进行,依此类推。继续进行,依此类推。这样的处理方法指针这样的处理方法指针i是无回溯的。是无回溯的。一、改进的快速模式匹配算法(一、改进的快速
20、模式匹配算法(KMP)12345678910 11 12 13ababcabcacbababcac12345ij算法思想如下:分析算法思想如下:分析BF算法的执行过程算法的执行过程,造成造成BF算法速度慢算法速度慢的原因是回溯,即在某趟的匹配过程失败后,对于的原因是回溯,即在某趟的匹配过程失败后,对于s串要回到串要回到本趟开始字符的下一个字符,本趟开始字符的下一个字符,t串要回到第一个字符。而这些串要回到第一个字符。而这些回溯并不是必要的。在匹配过程中,在第三趟匹配过程中,回溯并不是必要的。在匹配过程中,在第三趟匹配过程中,s3s6和和t1t4是匹配成功的,是匹配成功的,s7t5匹配失败,因此
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四章 第四
限制150内