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

1、重庆大学根底性实践环节实践报告实践课程名称数据结构开课实验室数统学院LD104学院数统学院年级2021级专业班理科实验班数学类01学生姓名学号开课时间2021至2021学年第一学期总成绩教师签名数统学院制课程名称数据结构实验题目用的根本操作与KMP心匹配算法实践目的掌握用的操作实践环境C+算法描述1 .米用堆分配存储与表示串2 .串的连接3 .串的截取4 .next数组记录失配后重新比拟的位置#include<stdio.h>#include<stdlib.h># defineTRUE1# defineFALSE0# defineOK1# defineERROR0# d

2、efineINFEASIBLE-1# defineOVERFLOW-2# defineMAXQSIZE5/Status是函数的类型,其值是函数结果状态码typedefintStatus;typedefstructchar*ch;/假设是非空用,那么按用长分配存储区,否那么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数组: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数组intnext255;对用T作分析,得到next数

9、组get_next(T,next);/假设i小于S的长度且j小于T的长度时,循环继续while(i<=S.length&&j<=T.length)/两字母相等那么继续,相对于朴素算法增加了/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