《数据结构之KMP算法实验报告武汉大学》由会员分享,可在线阅读,更多相关《数据结构之KMP算法实验报告武汉大学(4页珍藏版)》请在金锄头文库上搜索。
1、程序构实验 4.3.cpp 文件包含的函数及其功能如下: strassign(sqstring &str,char cstr) /创建串 dispstr(sqstring s) /输出串 simple (sqstring s,sqstring t)getnext(sqstring t,int next )/模式串求 next 的值 kmpindex(sqstring s,sqstring t)/kmp 算法getnextval(sqstring t,int nextval)得至U nextval 的值Main():根据输入的字符串的字符建立目标串和模式串,调用一 系列子函数实现题目的要求五:算
2、法描述#include#include #define maxsize 100typedef struct char chmaxsize;int len; sqstring;void strassign(sqstring & str,char cstr)/ 仓 U建串 int i;for (i=0;cstri!=0;i+)str.chi=cstri;str.len=i;void dispstr(sqstring s) 输出串 int i;if (s.len0) for (i=0;is.len;i+)printf (%c,s.chi);printf (n);int simple (sqstrin
3、g s,sqstring t) int i=0,j=0,k; while (is.len&j=t.len) k=i-t.len;elsek=-l; return k;void getnext(sqstring t,int next )/模式串求 next 的值 int j ,k;j=0;k=-l;next0=-l;while (jt.len-l) if (k=-l|t.chj=t.chk)j+;k+; nextj=k; else k=nextk;int kmpindex(sqstring s,sqstring t)/kmp 算法 int next maxsize,i=0,j=0,v; getn
4、ext(t,next);while (is.len&j=t.len) v=i-t.len;elsev=-1;return v;void getnextval(sqstring t,int nextval)得到 nextval 的值int j=0,k=-1;nextval0=-1;while (jt.len) if (k=-1|t.chj=t.chk) j+;k+;if (t.chj!=t.chk) nextvalj=k;else nextvalj=nextvalk;else k=nextvalk;int main ()int i,j;int next maxsize,nextval maxsi
5、ze; sqstring s,t;strassign (s,abcabcdabcdeabcdefabcdefg); strassign (t,abcdeabcdefab);printf (串 S:);dispstr(s); printf (串 t:);dispstr(t);getnext (t,next); getnextval(t,nextval); printf ( i ); for (i=0;it.len;i+) printf (%4d,i);printf(n);printf(ti );for (i=0;it.len;i+)printf (%4c,t.chi); printf(n);pr
6、intf(next );for (i=0;it.len;i+)printf (%4d,nexti); printf(n); printf(nextval);for (i=0;it.len;i+)printf (%4d,nextvali); printf(n);printf (kmp 算法: ); j=kmpindex(s,t);f (j=-1) printf (串匹配失败 n); else printf (t 在 s 中的位置dn,j); printf (简单算法: ); j=simple(s,t);f (j=-1) printf (串匹配失败 n); else printf (t 在 s 中的位置%dn,j); system(pause);六:实验数据与实验结果:7810eenexttextual 繍犍继续.a-1七在吕中的位鬻匕在w中知质7乌Sabcabcdabcdeabcdefabodefg 串 t-abcdeabcdef ab1g D 哈工丈馨程 devest码 4.3 .exe程序盘:详见源文件