数据结构串实验报告

1、实验报告课程数据结构实验名称实验三串学号姓名实验日期：实验三串实验目的：熟悉串类型的实现方法，了解简单文字处理的设计方法；熟悉C语言的字符和把字符串处理的原理和方法；熟悉并掌握模式匹配算法。实验原理：顺序存储结构下的关于字符串操作的基本算法。模式匹配算法BF、KMP实验内容：4-19.在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。4-20.设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start，T，V)，即要求在主串S中，从位置start开始查找是否存在字串T。若主串S中存在子串T,则用子串V替换子串T,且函数返回1；若主串

2、S中不存在子串T,则函数返回0；并要求设计主函数进行测试。一个测试例子为：S=“Iamastudent”,T=“student”,V=“teacher”。程序代码：4-19的代码：/*静态存储结构*/typedefstructcharstrMaxSize;intlength;String;/*初始化操作*/voidInitiate(String*S)S-length=0;/*插入子串操作*/intInsert(String*S,intpos,StringT)/*在串S的pos位置插入子串T*/inti;if(posS-length)printf(Theparameterposiserror!n

3、);return0;elseif(S-length+T.lengthMaxSize)printf(Thespaceofthearrayisnotenough!n);return0;elsefor(i=S-length-1;i=pos;i-)S-stri+T.length=S-stri;/*依次后移数据元素*/for(i=0;istrpos+i=T.stri;/*插入*/S-length=S-length+T.length;/*产生新的串长度值*/return1;/*删除子串操作*/intDelete(String*S,intpos,intlen)/*删除串S的从pos位置开始长度为len的子串

4、值*/inti;if(S-length=0)printf(Noelementsdeleting!n);return0;elseif(pos0|lenS-length)printf(Theparametersposandlenarenotcorrect!n);return0;elsefor(i=pos+len;ilength-1;i+)S-stri-len=S-stri;/*依次前移数据元素*/S-length=S-length-len;/*产生新的串长度值*/return1;/*取子串操作*/intSubString(StringS,intpos,intlen,String*T)/*取串S的从

5、pos位置开始长度为len的子串值赋给子串T*/inti;if(pos0|lenS.length)printf(Theparametersposandlenarenotcorrect!n);return0;elsefor(i=0;istri=S.strpos+i;/*给子串T赋值*/T-length=len;/*给子串T的长度域赋值*/return1;/*查找子串BF(Brute-Force)操作*/intBFIndex(StringS,intstart,StringT)/*查找主串S从start开始的子串T,找到返回T在S中的开始字符下标，否则返回-1*/inti=start,j=0,v;w

6、hile(iS.length&jT.length)if(S.stri=T.strj)i+;j+;elsei=i-j+1;j=0;if(j=T.length)v=i-T.length;elsev=-1;returnv;/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/intKMPIndex(StringS,intstart,StringT,intnext)/*查找主串S从start开始的子串T,找到返回T在S中的首字符下标，*/*否则返回-1*/*数组Next中存放有模式串T的nextj值*/inti=start,j=0,v;while(iS.length

7、&jT.length)if(S.stri=T.strj)i+;j+;elseif(j=0)i+;elsej=nextj;if(j=T.length)v=i-T.length;elsev=-1;returnv;/*求模式串nextj值的操作*/voidGetNext(StringT,intnext)/*求子串T的nextj值并存放于数组next中*/intj=1,k=0;next0=-1;next1=0;while(jT.length)if(T.strj=T.strk)nextj+1=k+1;j+;k+;elseif(k=0)nextj+1=0;j+;elsek=nextk;/*查找子串BF(B

8、rute-Force)算法累计次数*/intBFIndexC(StringS,intstart,StringT)/*查找主串S从start开始的子串T,找到返回T在S中的开始字符下标，否则返回-1*/inti=start,j=0,t=0;while(iS.length&jT.length)if(S.stri=T.strj)i+;j+;elsei=i-j+1;j=0;t+;returnt;/*查找子串KMP(D.E.Knuth-J.H.Morris-V.R.Pratt)操作*/intKMPIndexC(StringS,intstart,StringT,intnext)/*查找主串S从start开

9、始的子串T,找到返回T在S中的首字符下标，*/*否则返回-1*/*数组Next中存放有模式串T的nextj值*/inti=start,j=0,t=0;while(iS.length&jT.length)if(S.stri=T.strj)i+;j+;elseif(j=0)i+;elsej=nextj;t+;returnt;测试主函数：#include#defineMaxSize100#includeSString.h#includeBFandKMP.hvoidmain(void)StringS=cddcdc,6,T=abcde,5;StringS1=aaaaaaaa,8,T1=aaaab,5;S

10、tringS2=aaaaaaaaaaaaaaaaad,18,T2=aaaab,5;intnext20,count;count=BFIndexC(S,0,T);printf(”从S中查找T的Brute-Force算法比较次数：%dn,count);GetNext(T,next);count=KMPIndexC(S,0,T,next);printf(从S中查找T的KMP算法比较次数：%dn,count);count=BFIndexC(S1,0,T1);printf(”从si中查找T1的Brute-Force算法比较次数：%dn,count);GetNext(T1,next);count=KMPIn

11、dexC(S1,0,T1,next);printf(从si中查找T1的KMP算法比较次数：%dn,count);count=BFIndexC(S2,0,T2);printf(”从S2中查找T2的Brute-Force算法比较次数：%dn,count);GetNext(T2,next);count=KMPIndexC(S2,0,T2,next);printf(从S2中查找T2的KMP算法比较次数：%dn,count);4-20的部分代码：Replace函数：/*从主串S中查找字串T,若存在，并用串V替换串T并返回1,否则，返回0*/intReplace(StringS,intstart,Stri

12、ngT,StringV)inti,v;Initiate(&S);Initiate(&T);Initiate(&V);for(i=0;istrlen(S.str);i+)S.length=S.length+1;for(i=0;istrlen(T.str);i+)T.length=T.length+1;for(i=0;istrlen(V.str);i+)V.length=V.length+1;i=BFIndex(S,0,T);if(i!=-1)if(Delete(&S,i,T.length)Insert(&S,i,V);for(i=0;iS.length;i+)printf(%c,S.stri);

13、printf(n);returnv=1;elseprintf(主串S中不存在串Tn)；returnv=0;测试主函数：#defineMaxSize80#include#include#includeSString.hintmain(void)intv;StringS=Iamastudent.,T=student,V=teacher;v=Replace(S,0,T,V);printf(返回dn,v);实验结果：4-19程序调式结果:，叶乂算法比较次数24妝E匸丁查找丫的脳皿&一卩叶曲算法比较次数：攸曲查莪T的时算法比较次数，叶乂算法比较次数24隨1口查我T1的Brute-Fi就鼻法比较次数S0知匸丁查溺T1的KHF算法比较次数