串的模式匹配

实验四顺序串的各种模式匹配一、实验目的熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。二、实验内容由用户随意输入两个串：主串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比较复杂，任然需要时间去学习