數(shù)據(jù)結(jié)構(gòu)串實(shí)驗(yàn)報告

1、實(shí)驗(yàn)報告課程數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)名稱實(shí)驗(yàn)三串學(xué)號姓名實(shí)驗(yàn)日期：實(shí)驗(yàn)三串實(shí)驗(yàn)?zāi)康模菏煜ご愋偷膶?shí)現(xiàn)方法，了解簡單文字處理的設(shè)計(jì)方法；熟悉C語言的字符和把字符串處理的原理和方法；熟悉并掌握模式匹配算法。實(shí)驗(yàn)原理：順序存儲結(jié)構(gòu)下的關(guān)于字符串操作的基本算法。模式匹配算法BF、KMP實(shí)驗(yàn)內(nèi)容：4-19.在4.4.3節(jié)例4-6的基礎(chǔ)上，編寫比較Brute-Force算法和KMP算法比較次數(shù)的程序。4-20.設(shè)串采用靜態(tài)數(shù)組存儲結(jié)構(gòu)，編寫函數(shù)實(shí)現(xiàn)串的替換Replace(S,start，T，V)，即要求在主串S中，從位置start開始查找是否存在字串T。若主串S中存在子串T,則用子串V替換子串T,且函數(shù)返回1；若主串

2、S中不存在子串T,則函數(shù)返回0；并要求設(shè)計(jì)主函數(shù)進(jìn)行測試。一個測試?yán)訛椋篠=“Iamastudent”,T=“student”,V=“teacher”。程序代碼：4-19的代碼：/*靜態(tài)存儲結(jié)構(gòu)*/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;/*依次后移數(shù)據(jù)元素*/for(i=0;istrpos+i=T.stri;/*插入*/S-length=S-length+T.length;/*產(chǎn)生新的串長度值*/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;/*依次前移數(shù)據(jù)元素*/S-length=S-length-len;/*產(chǎn)生新的串長度值*/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中的開始字符下標(biāo)，否則返回-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中的首字符下標(biāo)，*/*否則返回-1*/*數(shù)組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值并存放于數(shù)組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)算法累計(jì)次數(shù)*/intBFIndexC(StringS,intstart,StringT)/*查找主串S從start開始的子串T,找到返回T在S中的開始字符下標(biāo)，否則返回-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中的首字符下標(biāo)，*/*否則返回-1*/*數(shù)組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;測試主函數(shù)：#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算法比較次數(shù)：%dn,count);GetNext(T,next);count=KMPIndexC(S,0,T,next);printf(從S中查找T的KMP算法比較次數(shù)：%dn,count);count=BFIndexC(S1,0,T1);printf(”從si中查找T1的Brute-Force算法比較次數(shù)：%dn,count);GetNext(T1,next);count=KMPIn

11、dexC(S1,0,T1,next);printf(從si中查找T1的KMP算法比較次數(shù)：%dn,count);count=BFIndexC(S2,0,T2);printf(”從S2中查找T2的Brute-Force算法比較次數(shù)：%dn,count);GetNext(T2,next);count=KMPIndexC(S2,0,T2,next);printf(從S2中查找T2的KMP算法比較次數(shù)：%dn,count);4-20的部分代碼：Replace函數(shù)：/*從主串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;測試主函數(shù)：#defineMaxSize80#include#include#includeSString.hintmain(void)intv;StringS=Iamastudent.,T=student,V=teacher;v=Replace(S,0,T,V);printf(返回dn,v);實(shí)驗(yàn)結(jié)果：4-19程序調(diào)式結(jié)果:，葉乂算法比較次數(shù)24妝E匸丁查找丫的脳皿&一卩葉曲算法比較次數(shù)：攸曲查莪T的時算法比較次數(shù)，葉乂算法比較次數(shù)24隨1口查我T1的Brute-Fi就鼻法比較次數(shù)S0知匸丁查溺T1的KHF算法比較次數(shù)