文档介绍：数据结构实验报告评分满分——5分学号:98姓名:许明华专业:计算机科学与技术知识范畴:字符串完成日期:2017年4月14日实验题目:基于改进KMP算法的字符文件子串查找实验内容及要求:从键盘输入字符文件名以及子串,用改进KMP算法在字符文件中实现子串查找。要求程序输出子串的改进nextval数组元素值以及子串在文件中成功匹配的次数(查找失败输出成功匹配次数为0)。实验目的:掌握子串查找的KMP算法。数据结构设计简要描述:序言:这是本学期第四个实验,本实验是要求我们将一个文件中的字符串读取出来,并自己从键盘上输入一个字符串来进行匹配,并用kmp算法来进行字符串的匹配查找;数据结构简单设计:本实验主要可分为三大模块,第一,从文件中读取出主串,并将其保存在一个字符数组中;第二,通过我们从键盘上输入的字符串来获得改进的nextval数组,而在改进的nextval数组求值算法中,变量还是跟踪的是next数组的值;第三,利用kmp算法来进行主串(char*s)和模式子串(char*t)的匹配,并求出成功匹配的次数;算法设计简要描述:1,求nextval数组的值,我们将不需要用到next数组就可以直接求出nextval数组的值,使nextval得出示值为-1,即nextval[0]=k=-1;将子串下标j初始化为1,然后通过t[j]和t[k]的值变化来获得nextval数组的值,其中的要点是,k值跟踪的仍然是未改进的next[j]的值;2,利用kmp算法来进行主串和模式子串的匹配,定义一个记录匹配的变量c=0,主串下标为i=0,子串下标j=0,当主串和子串第一个元素匹配成功后,进行i++和j++操作,都遍历到下一个元素;当进行一次成功匹配时,将子串的下标回溯到初始位置,记录变量c++,此时主串下标已经到达匹配成功的下一个元素,再继续进行匹配,知道主串到达末尾,结束匹配。输入/输出设计简要描述:1,输入:输入存储主串的文件名,输入子串;2,输出:当输入文件名后,会打印输出主串;当输入子串后,会打印输出nextval数组的值以及匹配成功的次数值c。编程语言说明:编程软件,;代码均用C语言实现;输入输出采用C语言的printf和scanf函数;程序注释采用C/C++规范;主要函数说明:voidwrite(char);//读取主串函数voidget_nextval(char,int);//获得nextval数组函数intindex_kmp(char,char,int);//kmp算法函数voidprint_nextval(int,int);//输出nextval数组函数程序测试简要报告:见截图:1,2,源程序代码:#include<>#include<>#include<>intnextval[32]={-999};//定义一个nextval数组,并进行初始化//函数声明voidwrite(chars[]);//读取主串函数voidget_nextval(char,int);//获得nextval数组函数intindex_kmp(char,char,int);//kmp算法函数voidprint_nextval(int,int);//输出nextval数组函数//从文件中将主串读出来并保存在s[]数组中voidwrite(chars[256]){charfilename[10];FILE*fp;printf("请输入文件名:\n");scanf("%s",filename);if((fp=fopen(filename,"r"))==NULL){printf("cannotopenthefile!\n");exit(0);}while(!feof(fp)){fscanf(fp,"%s",s);//将读取的主串保存在s数组中}printf("主串为:\n%s",s);//将主串输出到屏幕上fclose(fp);}//求得nextval数组的值voidget_nextval(char*t,intnextval[]){intj=1;intk=-1;nextval[0]=k;while(t[j])if((k==-1)||(t[j-1]==t[k]))if(t[++k]==t[j])nextval[j++]=nextval[k];elsenextval[j++]=k;elsek=nextval[k];}intindex_kmp(chars[],chart[],intnext[]){intc=0;inti=0,j=0;while(1){while(s[i]&&(j==-1||t[j]))//当主串s[i]不为空并且子串t[j]不为空if((j==-1)||(s[i]==t[j]))//如果