串的匹配运算_第1页
串的匹配运算_第2页
串的匹配运算_第3页
串的匹配运算_第4页
串的匹配运算_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

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

文档简介

1、串的匹配运算 数 据 结 构串串的匹配运算串的匹配运算,就是判断某串是否是另一个已知串的子串,如是其子串,则给出该子串的起始点(即从已知串的哪个字符开始),故此运算又称为子串定位运算。设已知串r1和r2,要求判断r2是否是r1的子串,如果是其子串则给出起始点。显然r2是r1的子串的一个必要条件是,r2的长度Lr2一定要小于或等于r1的长度Lr1,即Lr2Lr1。假定串r1或r2都采用每结点存一个字符的链接存储结构。 串一种最简单的匹配算法首先将r2的第1个字符与r1的第1个字符比较,如二者匹配,则将r2的第二个字符与r1的第二个字符比较,这样比较下去,若直至r2的末尾一个字符都与r1的相应字符

2、匹配,则整个运算结束,返回子串的起始位置为1;当进行中遇到两串的相应字符不匹配时,则返回来将r2的第一个字符与r1的第二个比较,将r2的第二个字符与r1的第三个字符进行比较,若整个r2的各个字符都与r1的相应字符匹配,则运算结束,返回子串的起始位置为2; 串以此类推,如出现不匹配,再返回来将r2的第一个字符与r1的第三个字符比较。如此逐轮做下去,直至匹配成功,给出子串的起始位置或失败返回起始位置为0。例:r1=abafabcgw r2=abc 子串r2在r1中的起始位置为5。 串匹配算法int position ( linkstring *r1,*r2) linkstring *p,*p1,*

3、q,*q1; int i=0; p=r1; while(p!=NULL) /*循环扫描r1每结点*/ q=r2; while(q!=NULL) /*依次扫描r2每结点*/ if (p-ch=q-ch) /*是否与r1当前结点相等*/ /*相等,判定后面元素是否相同*/ p1=p-link; q1=q-link; while(p1-ch=q1-ch)串匹配算法续 p1=p1-link; q1=q1-link; if (q1=NULL) return i; /*返回子串起始位置*/ else q=q-link; p=p-link; i+; 串匹配算法分析与改进该匹配算法比较简单,但效率不高。算法的

4、时间复杂性为O(Lr1Lr2)。作两项改进,可以提高平均情况的运算速度: 1) 先检查r2的首尾两字符在r1中是否匹配,这两对字符都匹配了,再检查中间的字符; 2) 当后面一些轮r1中剩下的字符数已小于r2的长度时停止运算,因为这种情况匹配已不可能成功了。 返回串例4.1把顺序存储的两个串r1和r2首尾相连成一个串r,其中r1在前r2在后。解:在顺序存储结构中,实现串的连接操作,只要进行相应的“串复制”操作即可,只是如果在操作中出现两串长度之和大于上界maxlen时,做溢出处理。串例4.1算法void concat ( orderstring *r1, *r2, *r) int i; prin

5、tf(“r1=%s,r2=%sn”,r1-vec,r2-vec); if (r1-len+r2-lenmaxlen) printf(“上溢出n”); /*溢出处理*/ else for(i=1;ilen;i+) r-veci=r1-veci; /*将r1串传给r*/ for(i=1;ilen;i+) r-vecr1-len+i=r2-veci; /*r2传给r */ r-vecr1-len+i+1= 0; r-len=r1-len+r2-len; 串例4.2把两个以链接方式存储的串r1和r2首尾连成一个串r,其中r1在前,r2在后。linkstring *concat ( linkstring

6、 *r1, *r2) node *p,*q,*s,*r; r=(linkstring *)malloc(sizeof(linkstring); r-ch=r1-ch; q=r; p=r1-link; while(p!=NULL) 串例4.2算法续 s=(linkstring *)malloc(sizeof(linkstring); s-ch=p-ch; q-link=s; q=s; p=p-link;p=r2;while(p!=NULL) s=(linkstring *)malloc(sizeof(linkstring); 串例4.2算法续 s-ch=p-ch; q-link=s; q=s;

7、p=p-link; q-link=NULL; return (r); 串例4.3从链接存储的串r1中的第i个字符开始,把连续j个字符组成的子串赋给r。 linkstring *substring (linkstring *r1,int i,j) int k; linkstring *p, *q, *s, *r; p=r1; k=1; while(klink; k+; 串例4.3算法续if(p=NULL) printf(“出错n”);else r=(linkstring *) malloc(sizeof(linkstring); q=r; k=1; while(kch=p-ch; q-link=s; /

温馨提示

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

评论

0/150

提交评论