您好,欢迎访问三七文档
实验四顺序串的各种模式匹配一、实验目的熟悉串的有关概念,掌握串的存储结构及串的模式匹配算法。二、实验内容由用户随意输入两个串:主串S和模式串T,设S=‘s1s2…sn’,T=‘t1t2…tm’,且0m=n。1(必做)、用简单模式匹配算法判断模式串T是否在主串S中,若在,则输出模式串在主串的第一匹配位置,否则,匹配失败,返回零值。2(选做)、用KMP模式匹配算法判断模式串T是否在主串S中,若在,则输出模式串在主串的第一匹配位置,否则,匹配失败,返回零值。三、算法思想与算法描述单链表是线性表的链式存储结构的一种形式,它用一组地址任意的存储单元存放线性表的各个元素。四、实验步骤与算法实现#includeiostream#includemalloc.husingnamespacestd;typedefstructtaglin{intdata;taglin*next;}lin;voidinitlin(lin*&L,inte){lin*p=L,*s;while(p-next!=NULL)p=p-next;s=(lin*)malloc(sizeof(lin));s-data=e;s-next=p-next;p-next=s;}voidmain(){intnum,e,x,y,count=-1,c=0,e1,t=-2147483648;boolmark=false;lin*L,*tx,*p,*q;L=(lin*)malloc(sizeof(lin));L-next=NULL;cout输入个数=2endl;cinnum;if(num2){cout输入比2小的值_错误endl;getchar();getchar();}cout输入num个非递减整形数字endl;for(inti=0;inum;i++){cine;initlin(L,e);if(c==0){e1=e;c++;}if(et){cout输入的值比前一个值小_错误endl;getchar();getchar();}t=e;}cout输入xyendl;cinxy;if(y=e)mark=true;if(e1x)x=e1;tx=L-next;for(;tx-data=x;tx=tx-next);p=L-next;for(;p!=NULL&&p-next!=tx;p=p-next);q=p;if(!mark){for(;p!=NULL&&p-data=y;p=p-next)count++;p=q;q=q-next;for(;count0;count--){p-next=q-next;q=q-next;}for(p=L,q=p-next;p-next!=NULL;p=p-next){if(p-next-data==x)p-next=q-next;q=q-next;}}else{if(e1x){p=L;for(;p-next!=tx&&p-next!=NULL;p=p-next);p-next=NULL;}elseL-next=NULL;}cout_____________endl;for(p=L-next;p!=NULL;p=p-next)coutp-dataendl;getchar();getchar();}五、实验测试及结果六、总结与体会理解了模式匹配基本方法,但kmp比较复杂,任然需要时间去学习
本文标题:串的模式匹配
链接地址:https://www.777doc.com/doc-5005566 .html