数据结构串的实验报告

1、精选优质文档-倾情为你奉上数据结构实验报告班号：1906姓名：吴晓坤学号：设计日期：2020.7.1上机环境：Windows 10+ devcpp1实验题目：实现顺序串的各种模式匹配算法 2实验项目目的：掌握串的模式匹配算法即BF和KMP算法设计。3实验项目的程序结构（程序中的函数调用关系图）： 4实验项目包含的各个文件中的函数的功能描述：5算法描述或流程图：开始；创建串s = abcabcdabcdeabcdefabcdefg；创建串t= abcdeabcdefab；调用简单匹配算法Index求t在s中的位置；由模式串t求出next值；由模式串t求出nextval值；输出过程中next值和n

2、extval值的变化；结束；6实验数据和实验结果分析：实验数据：串s = abcabcdabcdeabcdefabcdefg；串t= abcdeabcdefab实验结果：结果分析：结果正确，与预期符合。 7实验体会： 简单匹配算法相对简单，只需要理解指针的运用，KMP算法及改进后的KMP算法引入了新的值来消除指针不必要的回溯，用一个数组保存记录t中连续相同字符的最后的下标，从而提高算法效率。改进后的KMP算法不明白为什么提高了算法效率。8. 程序清单：#include <stdio.h>#include <string.h>#define MaxSize 100type

3、def struct char dataMaxSize;/定义可容纳MaxSize个字符的空间 int length; /标记当前实际串长 SqString;void StrAssign(SqString &s,char cstr)/s为引用型参数int i;for (i=0;cstri!='0'i+)s.datai=cstri;s.length=i;void StrCopy(SqString &s,SqString t)/s为引用型参数int i;for (i=0;i<t.length;i+)s.datai=t.datai;s.length=t.leng

4、th;bool StrEqual(SqString s,SqString t)bool same=true;int i;if (s.length!=t.length)/长度不相等时返回0same=false;else for (i=0;i<s.length;i+)if (s.datai!=t.datai)/有一个对应字符不相同时返回0same=false;break;return same;int StrLength(SqString s)return s.length;SqString Concat(SqString s,SqString t)SqString str;int i;st

5、r.length=s.length+t.length;for (i=0;i<s.length;i+)/将s.data0.s.length-1复制到strstr.datai=s.datai;for (i=0;i<t.length;i+)/将t.data0.t.length-1复制到strstr.datas.length+i=t.datai;return str;SqString SubStr(SqString s,int i,int j)SqString str;int k;str.length=0;if (i<=0 | i>s.length | j<0 | i+j

6、-1>s.length)return str;/参数不正确时返回空串for (k=i-1;k<i+j-1;k+) /将s.datai.i+j复制到strstr.datak-i+1=s.datak;str.length=j;return str; SqString InsStr(SqString s1,int i,SqString s2)int j;SqString str;str.length=0;if (i<=0 | i>s1.length+1) /参数不正确时返回空串return str;for (j=0;j<i-1;j+) /将s1.data0.i-2复制到

7、strstr.dataj=s1.dataj;for (j=0;j<s2.length;j+)/将s2.data0.s2.length-1复制到strstr.datai+j-1=s2.dataj;for (j=i-1;j<s1.length;j+)/将s1.datai-1.s1.length-1复制到strstr.datas2.length+j=s1.dataj;str.length=s1.length+s2.length;return str;SqString DelStr(SqString s,int i,int j)int k;SqString str;str.length=0

8、;if (i<=0 | i>s.length | i+j>s.length+1) /参数不正确时返回空串return str;for (k=0;k<i-1;k+) /将s.data0.i-2复制到strstr.datak=s.datak;for (k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datak-j=s.datak;str.length=s.length-j;return str;SqString RepStr(SqString s,int i,int j,SqString t)int k;

9、SqString str;str.length=0;if (i<=0 | i>s.length | i+j-1>s.length) /参数不正确时返回空串return str;for (k=0;k<i-1;k+)/将s.data0.i-2复制到strstr.datak=s.datak;for (k=0;k<t.length;k+) /将t.data0.t.length-1复制到strstr.datai+k-1=t.datak;for (k=i+j-1;k<s.length;k+)/将s.datai+j-1.s.length-1复制到strstr.datat.

10、length+k-j=s.datak;str.length=s.length-j+t.length;return str;void DispStr(SqString s)int i;if (s.length>0)for (i=0;i<s.length;i+)printf("%c",s.datai);printf("n");extern void StrAssign(SqString &,char ); /在algo4-1.cpp文件中extern void DispStr(SqString);int Index(SqString s,

11、SqString t)/简单匹配算法int i=0,j=0;while (i<s.length && j<t.length) if (s.datai=t.dataj)/继续匹配下一个字符i+;/主串和子串依次匹配下一个字符j+;else/主串、子串指针回溯重新开始下一次匹配i=i-j+1;/主串从下一个位置开始匹配j=0; /子串从头开始匹配if (j>=t.length)return(i-t.length);/返回匹配的第一个字符的下标elsereturn(-1);/模式匹配不成功void GetNext(SqString t,int next)/由模式串t

12、求出next值int j,k;j=0;k=-1;next0=-1;while (j<t.length-1)if (k=-1 | t.dataj=t.datak) /k为-1或比较的字符相等时j+;k+;nextj=k;else k=nextk;int KMPIndex(SqString s,SqString t)/KMP算法int nextMaxSize,i=0,j=0;GetNext(t,next);while (i<s.length && j<t.length) if (j=-1 | s.datai=t.dataj) i+;j+;/i,j各增1else j

13、=nextj; /i不变,j后退if (j>=t.length)return(i-t.length);/返回匹配模式串的首字符下标elsereturn(-1);/返回不匹配标志void GetNextval(SqString t,int nextval) /由模式串t求出nextval值int j=0,k=-1;nextval0=-1;while (j<t.length)if (k=-1 | t.dataj=t.datak)j+;k+;if (t.dataj!=t.datak)nextvalj=k;elsenextvalj=nextvalk;elsek=nextvalk;int K

14、MPIndex1(SqString s,SqString t)/修正的KMP算法int nextvalMaxSize,i=0,j=0;GetNextval(t,nextval);while (i<s.length && j<t.length) if (j=-1 | s.datai=t.dataj) i+;j+;elsej=nextvalj;if (j>=t.length)return(i-t.length);elsereturn(-1);int main()int j;int nextMaxSize,nextvalMaxSize;SqString s,t;St

15、rAssign(s,"abcabcdabcdeabcdefabcdefg");StrAssign(t,"abcdeabcdefab");printf("串s:");DispStr(s);printf("串t:");DispStr(t);printf("简单匹配算法:n");printf(" t在s中的位置=%dn",Index(s,t);GetNext(t,next);/由模式串t求出next值GetNextval(t,nextval);/由模式串t求出nextval值pri

16、ntf(" j ");for (j=0;j<t.length;j+)printf("%4d",j);printf("n");printf(" tj ");for (j=0;j<t.length;j+)printf("%4c",t.dataj);printf("n");printf(" next ");for (j=0;j<t.length;j+)printf("%4d",nextj);printf("n");printf(" nextval&quo