串的定义及基本运算课件_第1页
串的定义及基本运算课件_第2页
串的定义及基本运算课件_第3页
串的定义及基本运算课件_第4页
串的定义及基本运算课件_第5页
已阅读5页,还剩26页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

串的定义及基本运算56、极端的法规,就是极端的不公。——西塞罗57、法律一旦成为人们的需要,人们就不再配享受自由了。——毕达哥拉斯58、法律规定的惩罚不是为了私人的利益,而是为了公共的利益;一部分靠有害的强制,一部分靠榜样的效力。——格老秀斯59、假如没有法律他们会更快乐的话,那么法律作为一件无用之物自己就会消灭。——洛克60、人民的幸福是至高无个的法。——西塞罗串的定义及基本运算串的定义及基本运算56、极端的法规,就是极端的不公。——西塞罗57、法律一旦成为人们的需要,人们就不再配享受自由了。——毕达哥拉斯58、法律规定的惩罚不是为了私人的利益,而是为了公共的利益;一部分靠有害的强制,一部分靠榜样的效力。——格老秀斯59、假如没有法律他们会更快乐的话,那么法律作为一件无用之物自己就会消灭。——洛克60、人民的幸福是至高无个的法。——西塞罗4.1串的定义及基本运算4.2串的存储结构4.3模式匹配算法的实现4.4小结与习题第四章串2串(字符串)是一种特殊的线性表,它的数据元素仅由一个字符组成,计算机非数值处理的对象经常是字符串数据,在事物处理程序中,一般也是作为字符串处理的。4.1串的定义及基本运算一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作:S=“a1a2a3…an”其中S是串名,双引号括起来的字符序列是串值;ai(1≦i≦n)可以是字母、数字或其它字符;串中所包含的字符个数称为该串的长度。长度为零的串称为空串(EmptyString),它不包含任何字符。3三、串的基本运算1.求串长StrLength(s):操作条件:串s存在;操作结果:求出串s的长度。2.串赋值StrAssign(s1,s2)操作条件:s1是一个串变量,s2或者是一个串常量,或者是一个串变量(通常s2是一个串常量时称为串赋值,是一个串变量称为串拷贝)。操作结果:将s2的串值赋值给s1,s1原来的值被覆盖掉。63.连接操作:StrConcat(s1,s2,s)或StrConcat(s1,s2)操作条件:串s1,s2存在。操作结果:两个串的联接就是将一个串的串值紧接着放在另一个串的后面,连接成一个串。前者是产生新串s,s1和s2不改变;后者是在s1的后面联接s2的串值,s1改变,s2不改变。4.求子串SubStr(s,i,len):

操作条件:串s存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。

操作结果:返回从串s的第i个字符开始的长度为len的子串。len=0得到的是空串。75.串比较StrCmp(s1,s2)

操作条件:串s1,s2存在。操作结果:若s1==s2,操作返回值为0;若s1<s2,返回值<0;若s1>s2,返回值>0。6.子串定位StrIndex(s,t):找子串t在主串s中首次出现的位置操作条件:串s,t存在。操作结果:若t∈s,则操作返回t在s中首次出现的位置,否则返回值为-1。88.串删除StrDelete(s,i,len)操作条件:串s存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。操作结果:删除串s中从第i个字符开始的长度为len的子串,s的串值改变。7.插入StrInsert(s,i,t)

操作条件:串s,t存在,1≤i≤StrLength(s)+1。

操作结果:将串t插入到串s的第i个字符位置上。9.串替换StrRep(s,t,r)操作条件:串s,t,r存在,t不为空。操作结果:用串r替换串s中出现的所有与串t相等的不重叠的子串,s的串值改变。94.2串的存储结构4.2.1串的定长顺序存储类似于顺序表,用一组地址连续的存储单元存储串值中的字符序列,所谓定长是指按预定义的大小,为每一个串变量分配一个固定长度的存储区,如:1.类似顺序表,用一个指针来指向最后一个字符,这样表示的串描述如下:typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;10nedutSMAXSIZE-1…543210s.datas.curlen2.在串尾存储一个不会在串中出现的特殊字符作为串的终结符,以此表示串的结尾。比如C语言中处理定长串的方法就是这样的,它是用'\0'来表示串的结束。3.设定长串存储空间:chars[MAXSIZE+1];用s[0]存放串的实际长度,串值存放在s[1]~s[MAXSIZE],字符的序号和存储位置一致,应用更为方便。114.2.2定长顺序串的基本运算

1.串联接:把两个串s1和s2首尾连接成一个新串s。intStrConcat1(s1,s2,s){inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;j=0;while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}s[i]=’\0’;return1;}122.求子串intStrSub(char*t,char*s,inti,intlen){intslen;slen=StrLength(s);if(i<1||i>slen||len<0||len>slen-i+1){printf("参数不对");return0;}for(j=0;j<len;j++)t[j]=s[i+j-1];t[j]=’\0’;return1;}nedutSMAXSIZE-1…543210s.datas.curlennedI=4,len=3t.data例2.133.串比较:若s1==s2,操作返回值为0;若s1<s2,返回值<0;若s1>s2,返回值>0。intStrComp(char*s1,char*s2){inti=0;while(s1[i]==s2[i]&&s1[i]!=’\0’&&s2[i]!=’\0’)i++;return(s1[i]-s2[i]);}144.2.3串的块链存储表示顺序串上的插入和删除操作不方便,需要移动大量的字符。因此,我们可用单链表方式来存储串值,串的这种链式存储结构简称为链串。typedefstructnode{chardata;structnode*next;}lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算,但存储空间利用率太低。sdy···string115为了提高存储密度,可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小,显然,当结点大小大于1时,串的长度不一定正好是结点的整数倍,因此要用特殊字符‘#’(‘#’不属于串的字符集)来填充最后一个结点,以表示串的终结。···headABCDTANKEND#结点大小为4的链表存储密度的概念:164.3模式匹配算法的实现4.3.1求子串位置的定位函数StrIndex(s,t)串的模式匹配(即子串定位)是一种重要的串运算。设s和t是给定的两个串,在串s中查找串t的位置,在此过程中称s为主串,t为子串。在主串s中查找子串t的过程称为模式匹配,如果查找成功,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回-1。t也称为模式。17算法思想如下:首先将主串中的第一个字符s1与子串中的第一个字符t1进行比较,若相同,继续比较两个串中的第二个字符,即s2和t2进行比较,…若这样的比较对于子串的每个字符都成立,则该趟比较的开始位置就是子串在主串中的位置(查找成功)若上面的比较在某个位置上出现对应位置字符不相同的情况,即此趟比较不成功,将主串的指针指向本趟比较开始位置的下一个字符(i=i-j+2),同时将子串的位置返回到第一个位置。进行下次比较,直到匹配成功或者主串已经结束。简单的模式匹配算法BF----穷举的模式

18

算法举例第2趟

S abbaba(i=3-j+2=2开始)T

aba

(j=1开始)第4趟

S abba

ba Ta

ba(查找成功)第1趟

S abbaba(i=3,j=3)

Taba

第3趟

S

abbaba(i=2-j+2=3)开始T

aba(j=1开始)

主串

S abbaba(初始位置i=1,j=1)

子串

Taba

19算法程序实现如下

intStrIndex_BF(char*s,char*t){inti=1,j=1;while(i<=s[0]&&j<=t[0])/*都没遇到结束符*/if(s[i]==t[j])

{i++;j++;}/*继续*/else

{i=i-j+2;j=1;}/*回溯*/if(j>t[0])return(i-t[0]);/*成功,返回存储位置*/elsereturn(–1);}20算法分析----时间复杂度(i)在最好情况下,每趟不成功的匹配都发生在第一对字符比较时例如:s="aaaaaaaaaabc"t="bc"

即最好情况下的时间复杂度是O(n+m)。(ii)在最坏的情况下,如果不成功的匹配都发生在子串(t)的最后一个字符的位置,即每趟比较都要进行m次,这样比较的趟数要n趟,因此,此情况下的时间复杂度为O(n*m)。例如:s="aaaaaaaaaab"t="aaaab"21算法分析优点:算法简单实现容易缺点:算法复杂度高;重复比较次数比较,只要不匹配的情况,要从新开始;回溯次数比较多。22算法思路:如上所述,希望某趟在si和tj匹配失败后,主串指针i不回溯,模式串t向右“滑动”至某个适当位置上,使得tk对准si继续向右进行。显然,现在问题的关键是串t“滑动”到哪个位置上?不妨设位置为k,即si和tj匹配失败后,指针i不动,模式t向右“滑动”,使tk和si对准继续向右进行比较,关键的问题是确定滑动的位置。KMP算法算法引入:分析BF算法的执行过程,造成BF算法速度慢的原因是回溯,即在某趟的匹配过程失败后,对于s串要回到本趟开始字符的下一个字符,t串要回到第一个字符。而这些回溯并不是必要的。23KMP算法中NEXT函数的介绍next函数的性质:①next[j]是一个整数,且0≤next[j]<j②为了使t的右移不丢失任何匹配成功的可能,当存在多个满足上面(4)式的k值时,应取最大的,这样向右“滑动”的距离最短,“滑动”的字符为j-next[j]个。③如果在tj前不存在满足(4)式的子串,此时若t1≠tj,则k=1;若t1=tj,则k=0;这时“滑动”的最远,为j-1个字符,即用t1和sj+1继续比较。24NEXT函数的表示Next函数的定义:设有模式串:t=“abcaababc”,则它的next函数值为:

j123456789模式串abcaababcnext[j]0111223230当j=1max{k|1≤k<j且"t1t2…tk-1"

="tj-k+1tj-k+2…tj-1"}1其它情况next[j]=25KMP算法程序实现如下:intStrIndex_KMP(char*s,char*t,intpos)

/*从串s的第pos个字符开始找首次与串t相等的子串*/{inti=pos,j=1,slen,tlen;

while(i<=s[0]&&j<=t[0])

/*都没遇到结束符*/if(j==0||s[i]==t[j]){i++;j++;}

elsej=next[j];

/*回溯*/

if(j>t[0])returni-t[0];

/*匹配成功,返回位置*/

elsereturn–1;

/*匹配不成功,返回信息*/

}

26Next函数的求法:据前述,可把求next函数值的问题看成是一个模式匹配问题,整个模式串既是主串又是模式,而当前在匹配的过程中,已有上面的(5)式成立,则当tk≠tj时应将模式向右滑动,使得第next[k]个字符和“主串”中的第j个字符相比较。若next[k]=k′,且tk′=tj,则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串,使得t1t2…tk′=tj-k′+1tj-k′+2…tj(6)因此:next[j+1]=next[k]+1(7)27同理若tk′≠tj,则将模式继续向右滑动至使第next[k′]个字符和tj对齐,依此类推,直至tj和模式中的某个字符匹配成功或者不存在任何k′(1<k′<k<…<j)满足(4.10),此时若t1≠tj+1,则有:next[j+1]=1(8)否则若t1=tj+1,则有:next[j+1]=0(9)28求Next函数的程序实现:

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论