串的操作與KMP模式匹配算法

1、重慶大學根底性實踐環(huán)節(jié)實踐報告實踐課程名稱數(shù)據(jù)結構開課實驗室數(shù)統(tǒng)學院LD104學院數(shù)統(tǒng)學院年級2021級專業(yè)班理科實驗班數(shù)學類01學生姓名學號開課時間2021至2021學年第一學期總成績教師簽名數(shù)統(tǒng)學院制課程名稱數(shù)據(jù)結構實驗題目用的根本操作與KMP心匹配算法實踐目的掌握用的操作實踐環(huán)境C+算法描述1 .米用堆分配存儲與表示串2 .串的連接3 .串的截取4 .next數(shù)組記錄失配后重新比擬的位置#include<stdio.h>#include<stdlib.h># defineTRUE1# defineFALSE0# defineOK1# defineERROR0# d

2、efineINFEASIBLE-1# defineOVERFLOW-2# defineMAXQSIZE5/Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)碼typedefintStatus;typedefstructchar*ch;/假設是非空用,那么按用長分配存儲區(qū),否那么ch為NULLintlength;/字符串長度HString;/生成一個其值等于用常量chars的用TStatusStrAssign(HString&S,char*chars)inti;for(i=0;charsi;i+).if(S.ch)/free(S.ch);/S.ch=NULL;/)if(!i)S.ch=NULL

3、;S.length=0;elseS.ch=(char*)malloc(i*sizeof(char);/i?if(!S.ch)exit(OVERFLOW);S.length=i;for(intj=0;j<i;j+)S.chj=charsj;returnOK;/返回用長度ntStrLength(HString&S)returnS.length;/比擬大小,假設S>T返回值>0.相等返回0,否那么返回<0ntStrCompare(HStringS,HStringT)for(inti=0;i<S.length&&i<T.length;i+)i

4、f(S.chi!=T.chi)returnS.chi-T.chi;returnS.length-T.length;/return?/清空用S為空用,并釋放所占空間StatusClearString(HString&S)if(S.ch)free(S.ch);S.ch=NULL;S.length=0;returnOK;/連接兩個字符串,生成一個新的字符串StatusConcat(HString&T,HStringS1,HStringS2)/if(T.ch)free(T.ch);T.ch=(char*)malloc(S1.length+S2.length)*sizeof(char);

5、if(!T.ch)exit(OVERFLOW);T.length=S1.length+S2.length;for(inti=0;i<S1.length;i+)T.chi=S1.chi;for(i=0;i<S2.length;i+)T.chi+S1.length=S2.chi;returnOK;/字符串截取,返回截取的申StatusSubString(HString&sub,HStringS,intpos,intlen)if(pos<1|pos>S.length|len<0|(S.length-pos+1)<len)returnERROR;/if(su

6、b.ch)free(sub.ch);sub.ch=(char*)malloc(len*sizeof(char);if(!sub.ch)exit(OVERFLOW);for(inti=0;i<len;i+)sub.chi=S.chi+pos-1;sub.length=len;returnOK;/*StatusIndexString(Hstring&S,Hstring&T)if(T.length>S.length)returnERROR;elsefor(i=0;i<S.length;i+)for(j=0;j<T.length;j+)S.chi+j=T.chj

7、;7voidget_next(HString&T,int*next)inti,j;i=1;j=0;next1=0;while(i<T.length)if(j=0|T.chi-1=T.chj-1)i+;j+;nexti=j;else/假設字符不相同,那么j值回溯j=nextj;printf("模式用的nex數(shù)組:n");for(i=1;i<=T.length;i+)printf("next%d=%dn",i,nexti);voidget_next1(HString&T,int*next1)inti,j;i=1;j=0;next1

8、1=0;while(i<T.length)if(j=0|T.chi-1=T.ch-1)i+；j+；if(T.chi-1!=T.chj-1)next1i=j;elsenext1i=next1j;else/假設字符不相同,那么j值回溯j=next1j;for(i=1;i<=T.length;i+)printf("next1%d=%dn",i,next1i);StatusIndex_KMP(HString&S,HString&T)inti=1;/j用于子用T中當前位置下標值intj=1;定義next數(shù)組intnext255;對用T作分析,得到next數(shù)

9、組get_next(T,next);/假設i小于S的長度且j小于T的長度時,循環(huán)繼續(xù)while(i<=S.length&&j<=T.length)/兩字母相等那么繼續(xù),相對于樸素算法增加了/j=0判斷if(j=0|S.chi-1=T.chj-1)i+;j+;/指針后退重新開始匹配else/j退回適宜的位置,i值不變j=nextj;if(j>T.length)returni-T.length;elsereturn0;voidprintV(HString&S)for(inti=0;i<S.length;i+)printf("地址：%p,&q

10、uot;心S.chi);printf("值：%cn",S.chi);voidprints(HString&S)for(inti=0;i<S.length;i+)printf("%c",S.chi);printf("%sn","");voidmain()HStringS1,S2;char*c1,*c2;charstr150,str250;intx,k;截取請按2n模式匹printf("用的操作應用：n連接請按1配(KMP)請按3n");scanf("%d",&am

11、p;x);if(x=1)printf("請輸入第一個字符串S1：n");scanf("%s",str1);c1=str1;printf("請輸入第二個字符串S2：n");scanf("%s",str2);c2=str2;StrAssign(S1,c1);StrAssign(S2,c2);HStringT;Concat(T,S1,S2);printf("%s","T:");prints(T);elseif(x=2)intm;intn;printf("請輸字符串T：n&

12、quot;);scanf("%s",str1);c1=str1;printf("請輸入截取的初始位置m:n");scanf("%d",&m);printf("請輸入截取的長度n：n");scanf("%d",&n);/ClearString(S1);StrAssign(S1,c1);HStringsub;SubString(sub,S1,m,n);if(SubString(sub,S1,m,n)=0)printf("ERROR'n");elseprin

13、tf("子用:");prints(sub);elseif(x=3)printf("請輸入主用S1:n");scanf("%s",str1);c1=str1;printf("請輸入模式用S2：n");scanf("%s",str2);c2=str2;intnext20;/intnext120;StrAssign(S1,c1);StrAssign(S2,c2);k=Index_KMP(S1,S2);if(k=0)printf("不匹配n");elseprintf("匹配

14、開始位置:%dn",k);/*ClearString(SI);c="hell"StrAssign(S1,c);printf("%s","S1:");prints(S1);printV(S1);HStringS2;c="China"StrAssign(S2,c);printf("%s","S2:");prints(S2);printV(S2);HStringT;Concat(T,S1,S2);printf("%s","T:");

15、prints(T);printV(T);HStringsub;SubString(sub,T,1,3);printf("%s","sub:");prints(sub);printV(sub);*/1 .用的連接:截取請按2串的操作應用;連接請按1模式即配附請按31請輸入第一個字符串SLfw4gff2運行結果請輸入第：個字符串S2：4535gfdfdT:fw4gff24535gfdfdPressanykeytocontinue.2 .截取:I串的操作應用;連接請按1截取請按2模式匹配(KMP)請按32請輸字符串T：ygyugyng清輸入假取的初始位置叱2請輸入低取的長度n:6于串：gyugyuPressanykeytocontinue3 .KMP模式匹配;不匹配：連接請按1截取請旅膜式匹配(KMP)請按33請輸入主串Shfghvhgv43bJ23