PAGE/NUMPAGES实验四串[实验目的]1、掌握串的存储
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示与基本操作；2、掌握串的两种模式匹配算法：BF和KMP。3、了解串的应用。[实验学时]2学时[实验预习]回答以下问题：1、串和子串的定义串的定义：串是由零个或多个任意字符组成的有限序列。子串的定义：串中任意连续字符组成的子序列称为该串的子串。2、串的模式匹配串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,从主串s的第start个字符开始查找等于子串t的过程称为模式匹配,如果在S中找到等于t的子串,则称匹配成功,函数返回t在s中首次出现的存储位置〔或序号〕；否则,匹配失败,返回0。[实验容和要求]1、按照要求完成程序exp4_1.c,实现串的相关操作。调试并运行如下测试数据给出运行结果：求"Thisisaboy"的串长；比较"abc3"和"abcde"；表示空格比较"english"和"student"；比较"abc"和"abc"；截取串"white",起始2,长度2；截取串"white",起始1,长度7；截取串"white",起始6,长度2；连接串"asddffgh"和"12344"；#include
#include#defineMAXSIZE100#defineERROR0#defineOK1/*串的定长顺序存储表示*/typedefstruct{chardata[MAXSIZE];intlength;}SqString;intstrInit;/*初始化串*/intstrCreate;/*生成一个串*/intstrLength;/*求串的长度*/intstrCompare;/*两个串的比较*/intsubString;/*求子串*/intstrConcat;/*两个串的连接*//*初始化串*/intstrInit{s->length=0;s->data[0]='\0';returnOK;}/*strInit*//*生成一个串*/intstrCreate{printf<"inputstring:">;getsdata>;s->length=strlendata>;returnOK;}/*strCreate*//*〔1〕---求串的长度*/intstrLength{returns->length;}/*strLength*//*〔2〕---两个串的比较,S1>S2返回>0,s1{inti;forlength&&ilength;i++>{ifdata[i]>s2->data[i]>{return1;}ifdata[i]data[i]>{return-1;}}return0;}/*strCompare*//*〔3〕---求子串,sub为返回的子串,pos为子串的起始位置,len为子串的长度*/intsubString{inti;ifs->length||len<0||len>s->length-pos+1>{returnERROR;}sub->length=0;for{sub->data[i]=s->data[i+pos-1];sub->length++;}sub->data[i]='\0';returnOK;}/*subString*//*〔4〕---两个串连接,s2连接在s1后,连接后的结果串放在t中*/intstrConcat{inti=0,j=0;whilelength>{t->data[i]=s1->data[i];i++;}whilelength>{t->data[i++]=s2->data[j++];}t->data[i]='\0';t->length=s1->length+s2->length;returnOK;}/*strConcat*/intmain<>{intn,k,pos,len;SqStrings,t,x;do{printf<"\n---String---\n">;printf<"1.strLentgh\n">;printf<"2.strCompare\n">;printf<"3.subString\n">;printf<"4.strConcat\n">;printf<"0.EXIT\n">;printf<"\n---String---\n">;printf<"\ninputchoice:">;scanf<"%d",&n>;getchar<>;switch{case1:printf<"\n***showstrLength***\n">;strCreate<&s>;printf<"strLengthis%d\n",strLength<&s>>;break;case2:printf<"\n***showstrCompare***\n">;strCreate<&s>;strCreate<&t>;k=strCompare<&s,&t>;/*〔5〕---调用串比较函数比较s,t*/ifprintf<"twostringequal!\n">;elseifprintf<"firststring;elseprintf<"firststring>secondstring!\n">;break;case3:printf<"\n***showsubString***\n">;strCreate<&s>;printf<"inputsubstringpos,len:">;scanf<"%d,%d",&pos,&len>;if>printf<"subStringis%s\n",t.data>;elseprintf<"posorlenERROR!\n">;break;case4:printf<"\n***showsubConcat***\n">;strCreate<&s>;strCreate<&t>;if>/*〔6〕---调用串连接函数连接s&t*/printf<"Concatstringis%s",x.data>;elseprintf<"ConcatERROR!\n">;break;case0:exit<0>;default:break;}}while;return0;}2、按照要求完成程序exp4_2.c,实现BF&KMP串的模式匹配算法。调试与测试数据并给出结果：应用BF算法求子串"JING"在主串"BEIJING"中的位置,测试起始位置分别为1和5的情况；应用KMP算法求子串"abaabcac"在主串"acabaabaabcacaabc"中的位置,测试起始位置分别为1,10的情况,并写出子串的next[]值；exp4_2.c部分代码如下：#include#include#defineMAXSIZE100#defineERROR0#defineOK1/*串的定长顺序存储表示*/typedefstruct{chardata[MAXSIZE];intlength;}SqString;intstrCreate;intindexBf;/*串的模式匹配BF*/voidgetNext;/*KMP求next值*/intindexKmp;/*串的模式匹配KMP*//*生成一个串*/intstrCreate{printf<"inputstring:">;getsdata>;s->length=strlendata>;returnOK;}/*strCreate*//*〔1〕---串的模式匹配BF*/intindexBf{inti=pos-1,j=0;whilelength&&jlength>{ifdata[i]==t->data[j]>{i++;j++;}else{i=i-j+1;j=0;}}if=t->length>{returni-t->length+1;}else{return0;}}/*index_bf*//*〔2〕---KMP求next值*/voidgetNext{inti=0,j=-1;next[0]=-1;whilelength>{if<||data[i]==t->data[j]>>{j++;i++;next[i]=j;}else{j=next[j];}}}/*getNext*//*〔3〕---KMP模式匹配*/intindexKmp{inti=start-1,j=0;whilelength&&jlength>{ifdata[i]==t->data[j]>{i++;j++;}else{j=next[j];}}if=t->length>{returni-t->length+1;}else{return0;}}/*index_kmp*/intmain<>{intn,i,pos,next[MAXSIZE];SqStrings,t;do{printf<"\n---String---\n">;printf<"1.Index_BF\n">;printf<"2.INdex_KMP\n">;printf<"0.EXIT\n">;printf<"\n---String---\n">;printf<"\ninputchoice:">;scanf<"%d",&n>;getchar<>;switch{case1:printf<"\n***showIndex_BF***\n">;printf<"s:">;strCreate<&s>;printf<"t:">;strCreate<&t>;printf<"inputstartposition:">;scanf<"%d",&pos>;printf<"BF:indexis%d\n",indexBf<&s,&t,pos>>;break;case2:printf<"\n***showIndex_KMP***\n">;printf<"s:">;strCreate<&s>;printf<"t:">;strCreate<&t>;printf<"inputstartposition:">;scanf<"%d",&pos>;getNext<&t,next>;printf<"KMP:\n">;printf<"next[]:">;forprintf<"%3d",next[i]+1>;printf<"\n">;printf<"indexis%d\n",indexKmp<&s,&t,pos,next>>;break;case0:exit<0>;default:break;}}while;return0;}[实验小结]
浙公网安备 33021202002483