数据结构串的实验报告

《数据结构》实验报告班号：1906姓名：吴晓坤学号：191030257设计日期：2020.7.1上机环境：Windows10+devcpp1．实验题目：实现顺序串的各种模式匹配算法2．实验项目目的：掌握串的模式匹配算法即BF和KMP算法设计。3．实验项目的程序结构（程序中的函数调用关系图）：4．实验项目包含的各个文件中的函数的功能描述：5．算法描述或流程图：开始；创建串s=abcabcdabcdeabcdefabcdefg；创建串t=abcdeabcdefab；调用简单匹配算法Index求t在s中的位置；由模式串t求出next值；由模式串t求出nextval值；输出过程中next值和nextval值的变化；结束；6．实验数据和实验结果分析：实验数据：串s=abcabcdabcdeabcdefabcdefg；串t=abcdeabcdefab实验结果：结果分析：结果正确，与预期符合。7．实验体会：简单匹配算法相对简单，只需要理解指针的运用，KMP算法及改进后的KMP算法引入了新的值来消除指针不必要的回溯，用一个数组保存记录t中连续相同字符的最后的下标，从而提高算法效率。改进后的KMP算法不明白为什么提高了算法效率。8.程序清单：#includestdio.h#includestring.h#defineMaxSize100typedefstruct{chardata[MaxSize];//定义可容纳MaxSize个字符的空间intlength;//标记当前实际串长}SqString;voidStrAssign(SqString&s,charcstr[])//s为引用型参数{inti;for(i=0;cstr[i]!='\0';i++)s.data[i]=cstr[i];s.length=i;}voidStrCopy(SqString&s,SqStringt)//s为引用型参数{inti;for(i=0;it.length;i++)s.data[i]=t.data[i];s.length=t.length;}boolStrEqual(SqStrings,SqStringt){boolsame=true;inti;if(s.length!=t.length)//长度不相等时返回0same=false;elsefor(i=0;is.length;i++)if(s.data[i]!=t.data[i])//有一个对应字符不相同时返回0{same=false;break;}returnsame;}intStrLength(SqStrings){returns.length;}SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.length=s.length+t.length;for(i=0;is.length;i++)//将s.data[0..s.length-1]复制到strstr.data[i]=s.data[i];for(i=0;it.length;i++)//将t.data[0..t.length-1]复制到strstr.data[s.length+i]=t.data[i];returnstr;}SqStringSubStr(SqStrings,inti,intj){SqStringstr;intk;str.length=0;if(i=0||is.length||j0||i+j-1s.length)returnstr;//参数不正确时返回空串for(k=i-1;ki+j-1;k++)//将s.data[i..i+j]复制到strstr.data[k-i+1]=s.data[k];str.length=j;returnstr;}SqStringInsStr(SqStrings1,inti,SqStrings2){intj;SqStringstr;str.length=0;if(i=0||is1.length+1)//参数不正确时返回空串returnstr;for(j=0;ji-1;j++)//将s1.data[0..i-2]复制到strstr.data[j]=s1.data[j];for(j=0;js2.length;j++)//将s2.data[0..s2.length-1]复制到strstr.data[i+j-1]=s2.data[j];for(j=i-1;js1.length;j++)//将s1.data[i-1..s1.length-1]复制到strstr.data[s2.length+j]=s1.data[j];str.length=s1.length+s2.length;returnstr;}SqStringDelStr(SqStrings,inti,intj){intk;SqStringstr;str.length=0;if(i=0||is.length||i+js.length+1)//参数不正确时返回空串returnstr;for(k=0;ki-1;k++)//将s.data[0..i-2]复制到strstr.data[k]=s.data[k];for(k=i+j-1;ks.length;k++)//将s.data[i+j-1..s.length-1]复制到strstr.data[k-j]=s.data[k];str.length=s.length-j;returnstr;}SqStringRepStr(SqStrings,inti,intj,SqStringt){intk;SqStringstr;str.length=0;if(i=0||is.length||i+j-1s.length)//参数不正确时返回空串returnstr;for(k=0;ki-1;k++)//将s.data[0..i-2]复制到strstr.data[k]=s.data[k];for(k=0;kt.length;k++)//将t.data[0..t.length-1]复制到strstr.data[i+k-1]=t.data[k];for(k=i+j-1;ks.length;k++)//将s.data[i+j-1..s.length-1]复制到strstr.data[t.length+k-j]=s.data[k];str.length=s.length-j+t.length;returnstr;}voidDispStr(SqStrings){inti;if(s.length0){for(i=0;is.length;i++)printf(%c,s.data[i]);printf(\n);}}externvoidStrAssign(SqString&,char[]);//在algo4-1.cpp文件中externvoidDispStr(SqString);intIndex(SqStrings,SqStringt)//简单匹配算法{inti=0,j=0;while(is.length&&jt.length){if(s.data[i]==t.data[j])//继续匹配下一个字符{i++;//主串和子串依次匹配下一个字符j++;}else//主串、子串指针回溯重新开始下一次匹配{i=i-j+1;//主串从下一个位置开始匹配j=0;//子串从头开始匹配}}if(j=t.length)return(i-t.length);//返回匹配的第一个字符的下标elsereturn(-1);//模式匹配不成功}voidGetNext(SqStringt,intnext[])//由模式串t求出next值{intj,k;j=0;k=-1;next[0]=-1;while(jt.length-1){if(k==-1||t.data[j]==t.data[k])//k为-1或比较的字符相等时{j++;k++;next[j]=k;}elsek=next[k];}}intKMPIndex(SqStrings,SqStringt)//KMP算法{intnext[MaxSize],i=0,j=0;GetNext(t,next);while(is.length&&jt.length){if(j==-1||s.data[i]==t.data[j]){i++;j++;//i,j各增1}elsej=next[j];//i不变,j后退}if(j=t.length)return(i-t.length);//返回匹配模式串的首字符下标elsereturn(-1);//返回不匹配标志}voidGetNextval(SqStringt,intnextval[])//由模式串t求出nextval值{intj=0,k=-1;nextval[0]=-1;while(jt.length){if(k==-1||t.data[j]==t.data[k]){j++;k++;if(t.data[j]!=t.data[k])nextval[j]=k;elsenextval[j]=nextval[k];}elsek=nextval[k];}}intKMPIndex1(SqStrings,SqStringt)//修正的KMP算法{intnextval[MaxSize],i=0,j=0;GetNextval(t,nextval);while(is.length&&jt.length){if(j==-1||s.data[i]==t.data[j]){i++;j++;}elsej=nextval[j];}if(j=t.length)return(i-t.length);elsereturn(-1);}intmain(){intj;intnext[MaxSize],nextval[MaxSize];SqStrings,t;StrAssign(s,abcabcdabcdeabcdefabcdefg);StrAssign(t,abcdeabcdefab);printf(串s:);DispStr(s);printf(串t:);DispStr(t);printf(简单匹配算法:\n);printf(t在s中的位置=%d\n,Index(s,t));GetNext(t,next);//由模式串t求出next值GetNextval(t,nextval);//由模式串t求出nextval值printf(j);for(j=0;jt.length;j++)printf(%4d,j);printf(\n);printf(t[j]);for(j=0;jt.length;j++)printf(%4c,t.data[j]);printf(\n);printf(next);for(j=0;jt.length;j++)printf(%4d,next[j]);printf(\n);printf(nextval);for(j=0;jt.length;j++)printf(%4d,nextval[j]);printf(\n);printf(KMP算法:\n);printf(t在s中的位置=%d\n,KMPIndex(s,t));printf(改进的KMP算法:\n);printf(t在s中的位置=%d\n,KMPIndex1(s,t));return0;}