基于改进KMP算法的字符文件子串查找.doc

数据结构实验报告评分满分5分学号：2015111898姓名：许明华专业：计算机科学与技术知识范畴：字符串 完成日期：2017年4月14日实验题目：基于改进KMP算法的字符文件子串查找实验内容及要求：从键盘输入字符文件名以及子串，用改进KMP算法在字符文件中实现子串查找。要求程序输出子串的改进nextval数组元素值以及子串在文件中成功匹配的次数（查找失败输出成功匹配次数为0）。实验目的：掌握子串查找的KMP算法。数据结构设计简要描述：序言：这是本学期第四个实验，本实验是要求我们将一个文件中的字符串读取出来，并自己从键盘上输入一个字符串来进行匹配，并用kmp算法来进行字符串的匹配查找；数据结构简单设计： 本实验主要可分为三大模块，第一，从文件中读取出主串，并将其保存在一个字符数组中；第二，通过我们从键盘上输入的字符串来获得改进的nextval数组，而在改进的nextval数组求值算法中，变量还是跟踪的是next数组的值；第三，利用kmp算法来进行主串（char *s）和模式子串（char *t）的匹配，并求出成功匹配的次数；算法设计简要描述：1,求nextval数组的值，我们将不需要用到next数组就可以直接求出nextval数组的值，使nextval得出示值为-1，即nextval0 = k = -1;将子串下标j初始化为1，然后通过tj和tk的值变化来获得nextval数组的值，其中的要点是，k值跟踪的仍然是未改进的nextj的值；2，利用kmp算法来进行主串和模式子串的匹配，定义一个记录匹配的变量c = 0，主串下标为 i= 0，子串下标j = 0，当主串和子串第一个元素匹配成功后，进行i+和j+操作，都遍历到下一个元素；当进行一次成功匹配时，将子串的下标回溯到初始位置，记录变量c+，此时主串下标已经到达匹配成功的下一个元素，再继续进行匹配，知道主串到达末尾，结束匹配。输入/输出设计简要描述：1，输入：输入存储主串的文件名，输入子串；2，输出：当输入文件名后，会打印输出主串；当输入子串后，会打印输出nextval数组的值以及匹配成功的次数值c。编程语言说明：1， 编程软件，CodeBlocks 16.0；2， 代码均用C语言实现；3， 输入输出采用C语言的printf和scanf函数；4， 程序注释采用C/C+规范；主要函数说明：void write(char);/读取主串函数void get_nextval(char ,int);/获得nextval数组函数int index_kmp(char ,char , int);/kmp算法函数void print_nextval(int , int);/输出nextval数组函数程序测试简要报告：见截图：1， 2， 源程序代码：#include#include#includeint nextval32 = -999;/定义一个nextval数组,并进行初始化/函数声明void write(char s);/读取主串函数void get_nextval(char ,int);/获得nextval数组函数int index_kmp(char ,char , int);/kmp算法函数void print_nextval(int , int);/输出nextval数组函数/从文件中将主串读出来并保存在s数组中void write(char s256) char filename10; FILE *fp; printf(请输入文件名：n); scanf(%s,filename); if(fp = fopen(filename,r) = NULL) printf(can not open the file!n); exit(0); while(!feof(fp) fscanf(fp,%s,s);/将读取的主串保存在s数组中 printf(主串为：n%s,s);/将主串输出到屏幕上 fclose(fp);/求得nextval数组的值void get_nextval(char *t, int nextval) int j = 1; int k = -1; nextval0 = k; while(tj) if(k = -1) | (tj-1 = tk) if(t+k = tj) nextvalj+ = nextvalk; else nextvalj+ = k; else k = nextvalk;int index_kmp(char s, char t, int next) int c = 0; int i = 0,j = 0; while(1) while(si & (j = -1 | tj)/当主串si不为空并且子串tj不为空 if(j = -1) | (si = tj)/如果主串的第一个元素和子串的第一个元素匹配上之后，主串和子串下标均向后移一位 i+;/主串循环到下一个 j+;/子串循环到下一个 else j = nextvalj; if(!tj)/如果子串完成一次成功的匹配， i = i - j + 1;/每一次主串的下标i回溯到初始位置的下一个，这样就能避免匹配漏掉； j = 0; /就将子串下标回溯到初始位置 c+;/将记录成功匹配的次数的值加1，还有，此时主串下标已经向前移动一位，所以这里不需要再进行i+ if(!si)/如果主串到达末尾，说明遍历完成，则退出循环 break; return c;/返回成功匹配的次数/输出next或者nextval数组的值void print_nextval(int nextval, int n) for(int i = 0 ; i n ; i +) printf(%d ,nextvali); /主函数调用int main() int index;/定义一个成功匹配的次数的值 char s256,t256;/定义两个字符串数组，来保存主串和子串 write(s);/将主串中的数据读取到s数组中 printf(n子串为：n); scanf(%s,t);/输出主串 get_nextval(t,nextval);/得到nextval数组的值 printf(改进nextval数组元素值为：n); print_nextval(nextval,strlen(t)