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