1、實(shí)驗(yàn)六串的模式匹配.實(shí)驗(yàn)?zāi)康?1)利用順序結(jié)構(gòu)存儲(chǔ)串，并實(shí)現(xiàn)串的匹配算法。掌握簡(jiǎn)單模式匹配思想、熟悉KMP算法。.實(shí)驗(yàn)內(nèi)容(1)用鍵盤(pán)輸入初始化目標(biāo)串和模式串，通過(guò)簡(jiǎn)單模式匹配算法實(shí)現(xiàn)串的模式匹配，匹配成功后要求輸出模式串在目標(biāo)串中的位置。設(shè)計(jì)并調(diào)試KMP算法，并與簡(jiǎn)單模式匹配算法進(jìn)行比較。.實(shí)驗(yàn)要求(1)根據(jù)實(shí)驗(yàn)內(nèi)容編寫(xiě)程序，上機(jī)調(diào)試并獲得運(yùn)行結(jié)果(2)撰寫(xiě)實(shí)驗(yàn)報(bào)告.關(guān)鍵操作思路與算法本次實(shí)驗(yàn)將會(huì)使用兩種方法進(jìn)行模式匹配，分別是簡(jiǎn)單的模式匹配算法和更加快速的模式匹配算法(KMP算法)。定義串結(jié)構(gòu)并創(chuàng)建串這里定義串使用線(xiàn)性結(jié)構(gòu)創(chuàng)建，串結(jié)構(gòu)包含data數(shù)組與長(zhǎng)度len，創(chuàng)建串時(shí)首先輸入串的長(zhǎng)度，

2、再依次根據(jù)長(zhǎng)度來(lái)輸入串的內(nèi)容，這里用到了新知識(shí)fflush(stdin)函數(shù)，這個(gè)函數(shù)的作用是清除緩存區(qū)，因?yàn)槊看屋斎胫蠖紩?huì)按一次空格，如果不加這個(gè)或者是加getchar()那個(gè)空格字符就會(huì)被下一次的scanf()所接受typedefstructdatatypedataMAXNUM;intlen;SString；/創(chuàng)建一個(gè)串voidSStringCreate(SString*t)inti,j;charc;printf(請(qǐng)輸入串的長(zhǎng)度：”)；scanf(%d,&j);t-len=j;for(i=0;ilen;i+)printf(請(qǐng)輸入第4個(gè)字符：，(i+1);fflush(stdin);sca

3、nf(%c,&c);t-datai=c; .5.源代碼#include#include#include#include#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR-1#defineINFEASIBLE-1#defineMAXNUM100typedefintdatatype;typedefstructdatatypedataMAXNUM;intlen;String;建立串voidStringCreate(String*s)inti,j;charc;printf(請(qǐng)輸入字符串長(zhǎng)度：”)

4、；scanf(%d,&j);for(i=0;idatai=c;s-datai=0;38.39.s-len=j;/輸出串voidStringPrint(String*s)TOC o 1-5 h zinti;for(i=0;ilen;i+)printf(%c”,s-datai);printf(n);判斷是否為空字符串intStringIsEmpty(String*s)if(s-len=0)TOC o 1-5 h zreturnTRUE;elsereturnERROR;求字符串長(zhǎng)度intStringLenth(String*s)printf(字符串長(zhǎng)度為:%dn,s-len);return(s-le

5、n);復(fù)制串voidStringCopy(String*s,String*t)將串t的值復(fù)制到串s中74.inti;75.for(i=0;ilen;i+)76.77.s-datai=t-datai;s-len=t-len;串比較intStringCompare(String*s,String*t)若串s=t，則返回0;若st,則返回正數(shù)，若st,則返回負(fù)數(shù)127.127.TOC o 1-5 h zinti;for(i=0;ilen&ilen;i+)if(s-datai!=t-datai)return(s-datai-t-datai);return(s-len-t-len);/串連接intStr

6、ingconcat(String*s,String*t)/將串t連接到串s的后面97.inti,flag;98.if(s-len+t-lenlen;ilen+t-len;i+)101.102.s-datai=t-datai-s-len;103.104.s-len+=t-len;105.flag=TRUE;106.107.else108.109.if(s-lenlen;idatai=t-datai-s-len;114.115.s-len=MAXNUM;116.flag=FALSE;117.118.else串s的長(zhǎng)度等于MAXNUM,串t不能被連接119.120.flag=0;121.122.12

7、3.returnflag;/插入串intStringInsert(String*s,intpos,String*t)128.inti;129.if(poss-len)/130.131.returnERROR;132.133.if(s-len+t-lenlen+t-len-1;ilen+pos;i-136.137.s-datai=s-datai-t-len;138.139.for(i=0;ilen;i+)140.141.s-datai+pos=t-datai;142.143.s-len=s-len+t-len;47.else148.149.if(pos+t-lent-l

8、en+pos-1;i-)152.153.s-datai=s-datai-t-len;154.155.for(i=0;ilen;i+)156.157.s-datai+pos=t-datai;158.159.s-len=MAXNUM;160.161.162.else163.164.for(i=0;idatai+pos=t-datai;167.168.s-len=MAXNUM;169.170.171.-)95

9、.00014.215.returnOK;/刪除串intStringDelete(String*s,intpos,intlen)inti;if(pos(s-len-len)returnFALSE;for(i=pos+len-1;ilen;i+)s-datai-len=s-datai;s-len-=len;returnTRUE;簡(jiǎn)單模式匹配算法()intStringBF(String*s,String*t)inti=0,j=0;while(ilen-1)&jl

10、en-1)if(s-datai=t-dataj)i+;j+;elsei=i-j+1;j=0;if(j(t-len-1)return(i-t-len+1);elsereturnFALSE;/KMP模式匹配算法()/1.計(jì)算子串的next()voidGetNext(intnext,String*t)216.inti=1,j=0；217.next0=-1;218.next1=0;219.while(ilen)220.221.if(j=0|t-datai=t-dataj)222.223.+i;224.+j;225.nexti=j;226.227.else228.j=nextj;229.230.231.

11、2.通過(guò)next值來(lái)計(jì)算子串出現(xiàn)的具體位置232.intIndexKmp(String*s,String*t,intpos,intnext)233.234.inti=pos,j=1;235.while(ilen-1&jlen-1)236.237.if(j=0|s-datai=t-dataj)238.239.+i;240.+j;241.242.else243.j=nextj;244.245.if(jt-len-1)246.return(i-t-len+1);247.else248.returnFALSE;249.250./主函數(shù)251.intmain()252.253.intnext100;25

12、4.String*s,*t;255.s=(String*)malloc(sizeof(String);256.t=(String*)malloc(sizeof(String);257.intchoice,begin,end,len,a,pos,i;258.while(TRUE)259.260.printf（t請(qǐng)輸入操作數(shù)：n）；261.262.printf(t1、建立串；n);printf(t2、輸出串；n);263.264.printf（t3、求串長(zhǎng)度；n）;printf（t4、刪除部分字符串；n）;265.266.printf（t5、簡(jiǎn)單的BF模式匹配算法n）;printf（t6、效率更高

13、的KMP模式匹配算法n）;267.268.269.printf(t7、退出；n);scanf(%d”,&choice);switch(choice)270.271.case1:272.273.StringCreate(s);break;case2:274.275.StringPrint(s);break;case3:276.277.StringLenth(s);break;case4:278.279.printf（請(qǐng)輸入刪除起始位置：）；scanf（%d”,&begin）;280.281.printf（請(qǐng)輸入刪除末尾位置：“）；scanf（%d”,&end）;282.283.len=end-b

14、egin+1;StringDelete(s,begin,len);284.285.printf(新串為：)；StringPrint(s);286.287.break;case5:288.289./建立子串StringCreate(t);290.a=StringBF(s,t);291.292.293.printf(匹配位置為：%dn,a);break;case6:294.295.296./建立子串StringCreate(t);GetNext(next,t);297.298.for(i=0;ilen;i+)printf(t%d,nexti);299.300.printf(n);pos=0;301

15、.a=IndexKmp(s,t,pos,next);302.303.printf(匹配位置為：%dn,a);break;case7:return0;TOC o 1-5 h zgetchar();return0;6.測(cè)試圖psE:vscodec&:加總式楊正宇8dMext總nsicin八rts-v&sdjqkifg/lk,Me-stdaut=Microstrft-MlEi)gine-out-zli5hzlzc.Oyg*1-stderrExe=c：mingw64birigdb,exe1iiiterpreterni1請(qǐng)輸入操作數(shù),1、建立串；L輸出串；不求串長(zhǎng)度;取刪除部分字符串；5、簡(jiǎn)單的B喉式兀

16、配算法入效率更高的KMP模式匹配算法7.退出;1請(qǐng)輸入字符用長(zhǎng)度:5請(qǐng)痂入第1個(gè)字符1請(qǐng)痂入第2個(gè)字符2靖輸入第士個(gè)字符3請(qǐng)輸入第4個(gè)字符4靖輸入第5個(gè)字符5請(qǐng)輸入操作數(shù);lx建立串；3輸出串；3.求串長(zhǎng)度；4、刪除部分字符串；5、簡(jiǎn)單的E喉式匹配算法6、效率更高的KMP模式匹配算法7、退出；212545請(qǐng)輸入操作數(shù)二1.建立串；2、輸出串73、求串長(zhǎng)度；4刪除部分字符串；5”簡(jiǎn)單的BF模式匹配算法6效率更高的KMP模式匹配算法7、退出；字符串長(zhǎng)度為二5請(qǐng)輸入操作數(shù)；1.建立串；2、輸出率；3“求串長(zhǎng)度：4、刪除部分字符串,5、簡(jiǎn)單的SF模式匹配算法6效率更高的心1P模式匹配算法7“退出：請(qǐng)輸入刪除起始位置：2請(qǐng)輸入刪除末尾位