实验四模式匹配.doc

《实验四模式匹配.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四模式匹配一、实验目的和要求掌握字符串存储结构的描述，学会字符串的模式匹配算法的应用。二、实验内容和原理C语言结构化程序设计思想，结构体及指针和字符数组的应用。三、主要仪器设备装有VisualC++/TurboC++等C程序编译软件的计算机。四、实验中程序的源码1.朴素模式匹配算法程序代码如下：#include#include#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;intindex(seqstringp,seqstringt){inti,j,succ

2、;i=0;succ=0;while((i<=t.length-p.length)&&(!succ)){j=0;succ=1;while((j<=p.length-1)&&succ)if(p.str[j]==t.str[i+j])j++;elsesucc=0;++i;}if(succ)return(i-1);elsereturn(-1);}voidmain(){seqstringt,p;intpos;scanf("%s",t.str);t.length=strlen(t.str);scanf("%s",p.str);p.length=strlen(p.str);pos=index(p,t)

3、;printf("");if(pos==-1)printf("nofound");elseprintf("thepositionis%d",pos+1);}这里写出程序源代码，见书76页算法4.102.快速模式匹配算法程序代码如下：#definemaxsize100typedefstruct{charstr[maxsize];intlength;}seqstring;voidgetnext(seqstringp,intnext[]){inti,j;next[0]=-1;i=0;j=-1;while(i

4、

5、p.str[i]==p.str[j]){+

6、+i;++j;next[i]=j;}elsej=next[j];}for(i=0;i