数据结构实验报告

学号：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。

编程语言说明：

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

#include<string.h>

int nextval[32] = {-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 s[256])

{

char filename[10];

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;

nextval[0] = k;

while(t[j])

if((k == -1) || (t[j-1] == t[k]))

if(t[++k] == t[j])

nextval[j++] = nextval[k];

else

nextval[j++] = k;

else

k = nextval[k];

}

int index_kmp(char s[], char t[], int next[])

{

int c = 0;

int i = 0,j = 0;

while(1)

{

while(s[i] && (j == -1 || t[j]))//当主串s[i]不为空并且子串t[j]不为空

if((j == -1) || (s[i] == t[j]))//如果主串的第一个元素和子串的第一个元素匹配上之后，主串和子串下标均向后移一位

{

i++;//主串循环到下一个

j++;//子串循环到下一个

}

else

j = nextval[j];

if(!t[j])//如果子串完成一次成功的匹配，

{

i = i - j + 1;//每一次主串的下标i回溯到初始位置的下一个，这样就能避免匹配漏掉；

j = 0; //就将子串下标回溯到初始位置

c++;//将记录成功匹配的次数的值加1，还有，此时主串下标已经向前移动一位，所以这里不需要再进行i++

}

if(!s[i])//如果主串到达末尾，说明遍历完成，则退出循环

break;

}

return c;//返回成功匹配的次数

}

//输出next或者nextval数组的值

void print_nextval(int nextval[], int n)

{

for(int i = 0 ; i < n ; i ++)

{

printf("%d ",nextval[i]);

}

}

//主函数调用

int main()

{

int index;//定义一个成功匹配的次数的值

char s[256],t[256];//定义两个字符串数组，来保存主串和子串

write(s);//将主串中的数据读取到s数组中

printf("\n子串为：\n");

scanf("%s",t);//输出主串

get_nextval(t,nextval);//得到nextval数组的值

printf("改进nextval数组元素值为：\n");

print_nextval(nextval,strlen(t));//将nextval数组的值输出到屏幕上

index = index_kmp(s,t,nextval);//将成功匹配的次数的值存储到index中

printf("\n成功匹配次数为：\n");

printf("%d",index);//输出成功匹配的次数的值

return 0;

}

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