文档介绍：数据结构实验报告
评分
满分——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,即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。
编程语言说明:
编程软件,Code Blocks ;
代码均用C语言实现;
输入输出采用C语言的printf和scanf函数;
程序注释采用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<>
#include<>
int nextval[32] = {-999};//定义一个nextval数组,并进行初始化
//函数声明
void write(char s[]);//读取主串函数
void get_nextval(