兰州大学数据结构实验KMP算法实验报告.doc

兰州大学信息科学与工程学院数据结构实验报告 课程名称 数据结构 实验名称 数据结构试验 专业班级 通信工程二班 姓 名 学 号 实验日期 第 14 周 星期 日 三 四 节 实验地点 贺兰堂 20122013学年度第 一 学期一、实验目的1、实现KMP算法二、实验内容1、 试编写一程序，实现KMP算法，输入三组主串S和模式串P，输出模式串的Next(j)函数值，以及该P在S中的位置的定位函数值，即序号值。其中S的长度为1525,P的长度为58。三、实验环境1、硬件配置：Pentium（R） Dual-Core9 CUP E6500 2.93GHz，1.96的内存2、软件环境：Microsoft Windows XP Professional Service Pack 3，Microsoft Visual C+ 6.0四、需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入一个模式串P和三个主串2、输出的形式：输出模式串NEXT数组，和模式串在三个主串中的位置3、程序所能达到的功能：确定模式串在主串中的位置4、测试数据：首先输入模式串，以回车结束，此时输出NEXT数组的值。再输入三个主串，每输入一个主串，就会显示出模式串在主串中的位置。例如：输入模式串：ababc显示出NEXT的值为： -1 0 0 1 2输入主串：ababcjkluioababc输出模式串在主串中的位置： 0 11然后在依次输入剩下两个主串，每个主串的长度为1525，模式串的长度58五、概要设计为了实现上述操作，应以链表为存储结构。1、基本操作：（1）void getnext(char *t, int *next)初始条件：存在一个char型的数组t,和一个初始的int型数组next；操作结果：无返回值，把模式串的本身匹配的结果存入 next 数组中（2）int kmp(char *s,char *t,int *next,int *m)初始条件：存在主串s，模式串t，主串的匹配数组next，以及记录模式串在主串位置的数组m；操作结果：返回模式串在主串位置的总数k。2、本程序包含三个个模块：（1）求模式串匹配数组next；（2）实现KMP算法模块（3）主程序模块（3）模块调用图： 主程序模块求得模式串匹配数组模块实现KMP算法模块3、 流程图 主函数的流程图 定义char s125,s225,s325,t8int m10,next8,i,count屏幕上输出“请输入模式串”调用get() 函数得到模式串t调用函数getnext，求得模式串的匹配串next当i小于模式串t长度（i的初始值赋值为0）输出next数组屏幕上输出“请输入比较串:”调用函数get()，得到主串s1调用函数KMP，函数返回模式串在主串中的位置的总数k,记录位置的是int型数组mCount = k当i小于count 时（i的初始值赋值为0）输出m数组屏幕上输出“请输入比较串:”调用函数get()，得到主串s2调用函数KMP，函数返回模式串在主串中的位置的总数k,记录位置的是int型数组mCount = k当i小于count 时（i的初始值赋值为0）输出m数组屏幕上输出“请输入比较串:”调用函数get()，得到主串s3调用函数KMP，函数返回模式串在主串中的位置的总数k,记录位置的是int型数组mCount = k当i小于count 时（i的初始值赋值为0）输出m数组getnext函数流程图函数输入模式串数组t 和初始化的模式串匹配串数组nextint i=0,j=-1next0=-1当ti!=0时 j=-1)|(ti=tj是否i+j=nextjj+nexti=jkmp 函数流程图函数调用需要主串s，模式串t，模式串匹配串next，以及记录模式串在主串位置的记录串mint i=0,j=0,k=0当si!=0时j=-1)|(si=tj是否i+j=nextjj+ j=nextj是否mk+=i-strlen(t)j=-1i-return k六、详细设计1、存储类型，元素类型，结点类型：在整个程序中，三个主串和一个模式串均使用的是字符串数组类型模式串匹配数组，以及记录模式串在主串位置的记录数据用的是整形数组类型，其余用到的是整形数据类型2、每个模块的分析：（1）主程序模块：void main() char s125,s225,s325,t8;int m10,next8,i,count;printf(请输入模式串:);gets(t);/得到模式串getnext(t,next);/调用getnext函数，求得模式串匹配串nextfor (i=0;istrlen(t);i+)/输出nextprintf( %d,nexti);printf(n请输入比较串:);gets(s1);printf(n);count=kmp(s1,t,next,m);/调用kmp函数，利用m数组记录模式串位置，返回记录数据的总数for (i=0;icount;i+) printf( %d ,mi);/对m数组进行输出printf(n请输入比较串:);gets(s2);printf(n);count=kmp(s2,t,next,m);for (i=0;icount;i+) printf( %d ,mi);printf(n请输入比较串:);gets(s3);printf(n);count=kmp(s3,t,next,m);for (i=0;icount;i+) printf( %d ,mi);（2）求模式串匹配串模块void getnext(char *t, int *next) int i=0,j=-1;next0=-1;/-1意义为：模式串第一位不匹配，主串直接向后移一位，然后在从头开始比较while(ti!=0)/循环到模式串t进行到结尾 if(j=-1)|(ti=tj) i+;/继续比较后继字符j+;nexti=j;elsej=nextj;/模式串向后移动实现KMP算法模块int kmp(char *s,char *t,int *next,int *m) int i=0,j=0,k=0;while(si!=0) if (j=-1)|(si=tj)/判断是否匹配 i+;/继续比较后继字符j+;elsej=nextj;/模式串向右移动if(tj=0)/匹配成功 mk+=i-strlen(t);/确定模式串在主串中的位置j=-1;/重新初始，使模式串和主串再进行比较i-;/主串位置向前移一位return k;/返回记录位置的总数3）函数调用关系图main（）void getnext int kmp(char *s,char *t,int *next,int *m)3、完整的程序：#include stdio.h#include string.hvoid getnext(char *t, int *next) int i=0,j=-1;next0=-1;while(ti!=0) if(j=-1)|(ti=tj) i+;j+;nexti=j;elsej=nextj;int kmp(char *s,char *t,int *next,int *m) int i=0,j=0,k=0;while(si!=0) if (j=-1)|(si=tj) i+;j+;elsej=nextj;if(tj=0) mk+=i-strlen(t);j=-1;i-;return k;void main() char s125,s225,s325,t8;int m10,next8,i,count;printf(请输入模式串:);gets(t);getnext(t,next);for (i=0;istrlen(t);i+)printf( %d,nexti);printf(n请输入比较串:);gets(s1);printf(n);count=kmp(s1,t,next,m);for (i=0;icount;i+) printf( %d ,mi);printf(n请输入比较串:);gets(s2);printf(n);count=kmp(s2,t,next,m);for (i=0;icount;i+) printf( %d ,mi);printf(n请输入比较串:);gets(s3);printf(n);count=kmp(s3,t,next,m);for (i=0;icount;i+) printf( %d ,mi);七、程序使用说明及测试结果1、程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：程序会提示输入一个模式串，然后显示出next数组的值。然后提醒输入一个主串，屏幕中会显示出模式串在主串中的位置。依照上面顺序会要求再输入两个主串2、测试结果：例如：输入：ababa输出：-1 0 0 1 2输入：qweasdzxcababa输出：9输入：ababcasdababc输出：( 注：屏幕上没显示内容)输入：ababaaweababac输出：0 8程序结束3、调试中的错误及解决办法。 刚开始程序出现很多错误，开始是KMP算法不是很理解，随后解决。后面对于KMP函数实现模块的返回值，存在异议。本来想用递归调用，结果发现递归的思路不是很清新，于是换了另外一种方式。利用一个记录数据总数的变量count，再用指针的方法，传入记录位置的数组m，函数返回的是记录诗句总数的变量count，利用循环的方法进行输出，输出数组m的前count元素，通过这种方法，实现功能运行界面先输入ababa后，回车：再输入qweasdzxcababa后回车：再输入：ababcasdababc后回车最后输入：ababaaweababac后回车八、实验小结：你在编程过程中花时多少？花了近乎5,6个小