kmp数据结构课程设计报告

课程设计(论文)任务书

院 专 业班

一、课程设计(论文)题目 模式匹配算法的应用 二、课程设计(论文)工作自 年 月 日起至 年 月 日止。

三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．课程设计的目的

为了配合《数据结构》课程的教学，使学生能更深刻的领会《数据结构》课程的 重要性，特开设此课程设计；编写一些在特定数据结构上的算法，通过上机调试，更 好的掌握各种数据结构及其特点，培养学生综合运用所学理论知识解决复杂实际问题 的实践能力、研究性学习能力和团队合作能力。

2．课程设计的任务及要求 1）基本要求

（1）课程设计前必须选定课程设计题目，并认真进行需求分析与系统设计； （2）上机调试之前要认真准备实验程序及调试时所需的测试数据；

（3）独立思考，独立完成，严禁抄袭，调试过程要规范，认真记录调试结果； （4）上机结束后认真规范撰写课设报告，对设计进行总结和讨论。

2）课程设计论文编写要求

（1）要按照书稿的规格撰写打印课设论文

（2）论文包括任务书、目录、绪论、正文、总结、参考文献、附录等

（3）正文中要有问题描述、抽象数据类型的定义、数据的存储结构、设计的求解

算法、算法的实现、调试分析与测试结果 （4）课设论文装订按学校的统一要求完成

3）课设考核

从以下几方面来考查： （1）考勤和态度；

（2）任务的难易程度及设计思路；

（3）动手调试能力；

（4）论文撰写的水平、格式的规范性。

4）参考文献

[1] 严蔚敏, 吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社, 2007年. [2] 严蔚敏, 吴伟民. 数据结构题集（C语言版）[M]. 北京：清华大学出版社, 2007年. [3] 谭浩强. C语言程序设计[M]. 北京：清华大学出版社，2006年.

5）课程设计进度安排

内容 天数 地点 构思及收集资料 1 图书馆 程序设计与调试 3 计算机房 撰写论文 1 图书馆

6）任务及具体要求

1)英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必 工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和 出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现， 它或者从行首开始，或者前置以一个空格符。 2)模式匹配要基于KMP算法。

学生签名：

2015年01 月05 日

课程设计(论文)评审意见

（1）考勤和态度 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ） （2）任务难易及设计思路 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ） （3）动手调试能力评价 ：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ） （4）论文撰写水平及规范性评价：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）

评阅人： 职称： 讲师

年 月 日

目 录

1 绪 论 ............................................. 1

1.1模式匹配算法 ............................................ 1

1.1.2普通模式匹配算法 ................................................................................... 1 1.1.3KMP算法的改进思路及意义 ................................................................ 1 1.2编程环境 ................................................ 2

2程序设计 ........................................................................................................................ 2

2.1需求分析 ................................................ 2

2.2概要设计 ............................................... 2

2.2.1 建立和读入文本文件............................................................................... 2 2.2.2 存储结构设计 ........................................................................................... 3

2.3模块设计 ............................................... 3 2.4.子程序及功能设计 ....................................... 3

3详细设计 ....................................................................................................................... 4

3.1 数据类型定义 ........................................... 4 3.2 系统主要子程序详细设计 ................................ 4

4调试分析与结果 ........................................................................................................ 7

4.1 实验数据 ................................................ 7

4.2 程序运行截图 ............................................ 7 4.3 调试过程 ............................................... 10 4.4 待完善部分 ............................................. 10

5课设总结 .......................................................................................................................11 参考文献 ...........................................................................................................................11 附 录 ............................................................................................................................ 12

1 绪 论

1.1模式匹配算法

为了实现通过查询某些词汇在文章中出现的次数及位置来研究文学作品及作者的功能，以及基于KMP算法的要求 ，我设计了名为文学助手的小程序，该程序基于模式匹配算法中的KMP算法，KMP算法是字符串匹配中的一种，KMP算法是一种高效的模式匹配算法，复杂度可以达到O(m+n)，而普通模式匹配算法的复杂度为O(m*n)，与KMP算法相关的还有MonteCarlo随机算法 及改进的LasVegas算法，由于时间有限及课设要求下面只简绍KMP算法与普通算法。

1.1.2普通模式匹配算法

从主串的第一个字符（或者给定的第pos个字符）开始和子串的第一个字符开始比较，若相等，则继续比较后面的字符。若不相等，则从主串本次开始比较的字符的下一个字符开始，与子串的第一个字符进行比较（即主串需要回退到本次比较开始字符的下一字符，模式串回退到首字符，主串与子串都需要回退）。

匹配成功的标志：比较到子串的’\0’

匹配失败的标志：比较到主串的’\0’，且此时子串的比较位不等于’\0’。算法复杂度：O(m*n）

1.1.3KMP算法的改进思路及意义

在普通匹配算法中子串与模式串都需要回溯，但这些回溯不是必要的。因为当某一位发生失配时，可以根据已匹配的结果进行判断。该算法问题可以理解为，当模式串中的第k位与主串的第i位比较时发生不匹配时，需要将模式串向右滑动到哪里继续与主串的第i位进行比较，避免了不必要的主串回溯，减少了模式串回溯的位数，从而使算法复杂度提升到O(m+n）。

1.2编程环境

本次课设编程是在VC6.0与cfree等系统中进行编写调试及运行的。

2程序设计

2.1需求分析

一个有趣的文字查询程序可以让枯燥的工作产生简单的快乐，实现了有趣味且有效的文字查询功能，一个友好的人性化的界面及一个高效的算法自然就变得尤为重要，而且为我们所需要。整个程序利用KMP算法作为主体思想。通过各个功能模块，使用命令行形式的界面与用户互动交流。

1、首先需要一个友好有趣味的菜单界面和用户交流 2、设计账号及彩色界面提高程序的有趣度及个性化 3、需要相关函数去读取键盘键入的内容

4、读入数据内容之后需要一定的方式去存储内容 5、需要将存储的内容通过相关函数输出出

6、程序具有基本异常处理功能，以免出现错误用户不知所措在分析了程序所需要的其他功能后，开始着手程序设计工作。

2.2概要设计

该设计可分为三个部分实现；第一，建立文本文件，文件名由用户通过键盘输入；第二，检索给定单词：输入一个单词，检索并输出该单词所在的行号和列号；第三，给定单词的计数：输入一个单词，统计输出该单词在文本中的出现次数。可从3个方面着手设计。

2.2.1 建立和读入文本文件

建立和读入文件的实现步骤如下：

（1）定义一个串变量； （2）定义文本文件；

（3）输入文件名，打开该文件；

（4）循环读入文本行，写入文本文件，其过程如下： While(不是文件输入结束符) {读入一文本行至串变量；串变量写入文件；输入是否结束输入标志； }

2.2.2 存储结构设计

主串和模式串都采用定长顺序存储表示，其0号单元存放串的长度： #define MAXSTRLEN 255 //最大串长

Typedef char SString[MAXSTRLEN+1];//定长顺序存储表示 2.2.3字符串的模式匹配问题

本系统使用改进的KMP匹配算法实现字符串的模式匹配问题。匹配可如下进行：假设以指针i和j分别指示主串和模式中的比较字符，令i的初值为pos,j的初值为1.若在匹配过程中si=sj,则i和j分别增1，若si≠sj匹配失败后，则i不变，j退到next[j]位置再比较，若相等，则指针各自增1 ，否则j再退到下一个next值的位置，依次类推。直至下列两种情况：一种是j退到某个next值时字符比较相等，则i和j分别增1继续进行匹配；另一种是j退到值为零（即模式的第一个字符失败），则此时i和j也要分别增1，表明从主串的下一个字符起和模式重新开始匹配。

2.3模块设计

本程序包含3个模块：主程序模块，查找模块，功能模块，账号匹配模块。其调用关系如下所示。

账号匹配模块---主程序模块---查找模块---功能模块

2.4.子程序及功能设计

本系统共设置6个子程序，各子程序的函数名及功能说明如下。 （1）Void get_next(SString T,int next[]) //求模式串T的next函数值并存入数组next

（2）Int Index(SString S,SString T,int pos）//KMP匹配函数

（3）Int lenth(SString str) //取串str的长度

（4）Void find(char name[],SString keys) //查找函数，对于输入的每一个要查找的关键字，从文本文件中逐行读取字符串查找。 //调用(1),(2),(3)

（5）Void main() //主函数，负责系统的输入和输出。调用(4) （6）strcmp(s,zhanghao) //账号匹配函数，负责系统的进入。

3详细设计

3.1 数据类型定义

(1)定长顺序存储串类型的定义 #define MAXSTRLEN 255 //最大串长

typedef char SString[MAXSTRLEN+1];//串的定长顺序存储表示，0号单元存放串的长度

typedef char SString[MAXSTRLEN+1]; char zhanghao[7]="888888"; //定义初始密码

（2）全局变量的定义

int next[MAXSTRLEN] //KMP算法中用到的next数组

3.2 系统主要子程序详细设计

（1）主函数模块设计，负责系统的输入输出工作，调用查找函数。void main()

{ 输入包含路径的文本文件名； 输入要查找的关键字个数； 一次性输入要查找的关键字；

对于每一个关键字，循环调用find函数进行查找统计； }

（2）查找模块设计

void find(char name[],SString keys) { SString text;

int i=1,j=0,k,q=0; //i用于存放行号，j用于存放列号,k用于输出格式的控制,q用于统计出现次数 FILE *fp;

if (!(fp=(fopen(name,"r")))) //打开小说文件 { printf("打开文件出错!\n"); exit(0); }

keys[0]=lenth(keys); //求关键字的长度 printf("\n%s\n",&keys[1]); //打印关键字

while (!feof(fp)) //如果还没到小说文件末尾，则继续循环

{ k=0; fgets(&text[1],MAXSTRLEN,fp); //从小说文件中读取一行字符串，存入text串中

text[0]=lenth(text); //求读入的串的长度

j=Index(text,keys,j+1); //调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (j!=0)

{printf("行=%d,列=%d",i,j); k++;} //若匹配成功则打印行号和列号

while(j!=0) //若该行找到了关键字，则继续寻找看是否还能匹配成功

{ j=Index(text,keys,j+1); //调用KMP算法从刚找到的列号后一字符起匹配 if (j!=0)

{printf(",%d",j);k++;} //若匹配成功，则打印列号 }

i++; //行号加1，在下一行中寻找

q+=k; //累加k 以统计关键字出现次数 if (k) printf("\n"); //输出格式控制 }

printf("%s出现%d次。\n",&keys[1],q); //打印关键字出现次数 }

（3）求next函数值

void get_next(SString T,int next[]) { int j=1,k=0; next[1]=0; while(j<T[0])

{ if(k==0||T[k]==T[j])

{ ++j; ++k; if(T[j]!=T[k]) next[j]=k;

else next[j]=next[k]; } } }

（4）KMP匹配函数

int Index(SString S,SString T,int pos)

{ //利用模式串T的next函数球T主串S中第POS个字符之后的位置的KMP算法 int i=pos,j=1; while(i<=S[0]&&j<=T[0])

{ if(j==0||S[i]==T[j]) //继续比较后继字符{ ++i; ++j; }

else j=next[j]; //模式串向右移动 } if(j>T[0])

return (i-T[0]); //匹配成功 else return 0; //匹配失败主程序模块

（5）账号匹配函数 { char s[8]; int n=3; int flag=0;

do{ printf("请输入6位数的软件账号:\n"); scanf("%s",s);

if(!strcmp(s,zhanghao)) /*账号匹配验证*/ { printf("账号输入正确，请输入密码\n\n\n"); flag=1; break; } else{ printf("账号输入不正确，验证失败，请重新输入:\n"); n--; } }

while(n>0); if(!flag)

{printf("你已输入3次均不成功!是否忘记账号，请与工作人员联系，工作人员将尽快为你解决\n"); /*已输入3次*/

exit(0); /*自动退出*/ } char c[8]; int l=3;

do{ printf("请输入6位数的软件密码:\n"); scanf("%s",c);

if(!strcmp(c, password)) /*密码匹配验证*/ { printf("信息匹配成功，正在飞速进入界面\n\n\n"); flag=1; break; } else{ printf("密码输入不正确，验证失败，请重新输入:\n"); l--; } }

while(l>0);

if(!flag)

{printf("你已输入3次均不成功!是否忘记密码，请与工作人员联系，工作人员将尽快为你解决\n"); /*已输入3次*/

exit(0); /*自动退出*/ }

（6）界面颜色设计 在main函数中添加 int a1=6;

system("color a1"); 将界面设置成绿色

4调试分析与结果

最终程序调试完成，输入相应数据，程序运行的结果如下所示。

4.1 实验数据

使用本程序代码WENJIAN.cpp作为实验数据

4.2 程序运行截图

图 3.1验证账号信息启动程序

图3.2进入程序界面

图3.3 输入文档及查询内容

图3.4 输出查询结果

图3.5 继续查询或退出程序

4.3 调试过程

在程序运行的过程中，曾经出现了输入数据发生死循环问题，最终发现是一个for循环判断的逻辑出现了错误，导致将正确的数据判断成了错误的数据，并反复在循环内判断造成了不良后果。最终在排查错误的时候，检查到了错误，并解决。一个中英文字符的不同就造成了程序报错， 经过排查，也得到了解决。所以说细心和一个良好的编写习惯很重要。

4.4 待完善部分

本程序在使用的时候仍然有很多不尽人意的地方：

1、该程序的算法不是最高效的，出现错误的概率理论上还不是较小，有更好的

2、程序没有实现读取电脑上任意磁盘中任意文件的功能，。

5课设总结

在程序编写时由于个人电脑系统兼容性，不能使用VC，只好在cfree上进行编写，过程中了解了一些编程系统间的不同，就比如cfree要求把main改成整型，而在VC中又应该是void，还有有些头文件在不同系统中编写也不一样，而且有一些头文件不能找到，只能报错或程序闪退，过程中反反复复改了不知道几次，终于成功运行了，为了改变界面单调的背景，我在网上查询了颜色函数的使用，想要深入可是又有太多没学过，因为大幅提升界面，要涉及到Windows系统，只能现学现卖，学艺不精只能改背景颜色，不过绿色界面好挺好看的，也算是有进步。

通过本次的课程设计，我对于模式匹配算法有了更深刻的认识。KMP算法是一种最基本最常用的一种数据结构。有比它好的也有比它差的算法，该程序基于模式匹配算法中的KMP算法，KMP算法是字符串匹配中的一种，KMP算法是一种高效的模式匹配算法，复杂度可以达到O(m+n)，而普通模式匹配算法的复杂度为O(m*n)，与KMP算法相关的还有MonteCarlo随机算法 及改进的LasVegas算法，由于时间问题不能全面系统的掌握各种模式匹配算法的应用及优劣性，只能用学到的一点皮毛完成这次课设，但重要的是，知道不知道，比不知道不知道更好，因为这样才能学到新知识，才能成长，也会激励我更加努力的学习这门课程的知识。

感谢陈红丽老师平时对我们孜孜不倦的教诲，陈老师不但工作认真负责， 我为有这样一位老师而感到很荣幸。我希望能在今后的学习中付出更多的努力，取得更优异的成绩。

参考文献

[1] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社, 2007. [2] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月 [3] 许卓群，杨东青. 数据结构与算法 北京：高等教育出版社， 2006年

[4] 徐孝凯， 贺桂英. 数据结构（C语言描述） 清华大学出版社数据结构与算法 北 ， 2006年

[5] 齐景嘉 . 数据结构（含实训） 东南大学出版社， 2006年

附 录

程序源代码与注释如下： #include <stdio.h> #include <stdlib.h> #include <string.h>

#define MAXSTRLEN 255

typedef char SString[MAXSTRLEN+1]; char zhanghao[7]="888888"; /*定义初始密码*/

char password[7]="666666"; int next[MAXSTRLEN];

int Index(SString S,SString T,int pos) { int i=pos,j=1;

while(i<=S[0]&&j<=T[0])

{ if(j==0||S[i]==T[j]) {++i;++j;} else j=next[j]; }

if (j>T[0]) return (i-T[0]); else return 0; }

int lenth(SString str) { int i=1;

while(str[i]) i++; return(i-1); }

void find(char name[],SString keys) { SString text;

int i=1,j=0,k,q=0; //i用于存放行号，j用于存放列号,k用于输出格式的控制,q用于统计出现次数 FILE *fp;

if (!(fp=(fopen(name,"r")))) //打开小说文件 { printf("打开文件出错!\n"); exit(0); }

keys[0]=lenth(keys); //求关键字的长度 printf("\n%s\n",&keys[1]); //打印关键字

while (!feof(fp)) //如果还没到小说文件末尾，则继续循环

{ k=0; fgets(&text[1],MAXSTRLEN,fp); //从小说文件中读取一行字符串，存入text串中

text[0]=lenth(text); //求读入的串的长度

j=Index(text,keys,j+1); //调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0 if (j!=0)

{printf("行=%d,列=%d",i,j); k++;} //若匹配成功则打印行号和列号

while(j!=0) //若该行找到了关键字，则继续寻找看是否还能匹配成功

{ j=Index(text,keys,j+1); //调用KMP算法从刚找到的列号后一字符起匹配 if (j!=0)

{printf(",%d",j);k++;} //若匹配成功，则打印列号 }

i++; //行号加1，在下一行中寻找

q+=k; //累加k 以统计关键字出现次数 if (k) printf("\n"); //输出格式控制 }

printf("%s出现%d次。\n",&keys[1],q); //打印关键字出现次数 }

int main() { char s[8]; int n=3; int flag=0;

do{ printf("请输入6位数的软件账号:\n"); scanf("%s",s);

if(!strcmp(s,zhanghao)) /*账号匹配验证*/ { printf("账号输入正确，请输入密码\n\n\n"); flag=1; break; } else{ printf("账号输入不正确，验证失败，请重新输入:\n"); n--; } }

while(n>0); if(!flag)

{printf("你已输入3次均不成功!是否忘记账号，请与工作人员联系，工作人员将尽快为你解决\n"); /*已输入3次*/

exit(0); /*自动退出*/ } char c[8];

int l=3;

do{ printf("请输入6位数的软件密码:\n"); scanf("%s",c);

if(!strcmp(c, password)) /*密码匹配验证*/ { printf("信息匹配成功，正在飞速进入界面\n\n\n"); flag=1; break; } else{ printf("密码输入不正确，验证失败，请重新输入:\n"); l--; } }

while(l>0); if(!flag)

{printf("你已输入3次均不成功!是否忘记密码，请与工作人员联系，工作人员将尽快为你解决\n"); /*已输入3次*/

exit(0); /*自动退出*/ } int a1=6;

system("color a1");

char name[50]; //存储输入的小说路径字符串

SString words[10];//定义字符串数组，用于存储输入的关键字 int m,g,i;

printf("-----------辞海无涯谁相伴，别担心，文学助手帮你忙，纵横辞海谁可挡--------------\n");

printf("-----------------------亲爱的用户欢迎使用文学研究助手-------------------------\n"); printf("使用说明:\n");

printf("1:待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成;\n");

printf("2:程序的输出结果是每个词的出现次数和出现位置所在的行的行号;\n");

printf("3:待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置以一个空格符.\n");

printf("-------------------文学研究助手伴你步入文学研究的海洋------------------------\n");

while(1) //不停循环，直至完成查询或者退出服务

{printf("大王是否需要小的马上为您提供特殊服务：\n"); //询问是否需要服务

printf("大王您很急切，输入1；大王您没兴趣，输入0,\n"); scanf("%d",&m); //输入判断是否需要服务

if(m==0) //不需要服务时执行 break;

do //需要服务时执行

{ printf("输入你想查询的文档名字:\n"); scanf("%s",name); //输入文件名

printf("输入查询字符串的个数：\n"); scanf("%d",&g); //输入查询字符串个数 printf("输入你要查询的字符串:\n"); for (i=0;i<g;i++)

scanf("%s",&words[i][1]); //用户一次性输入要查找的关键字，words[i][0]用于存放字符串的长度 for (i=0;i<g;i++)

find(name,words[i]);//对于每一个关键字，调用查找函数进行查找统计

printf("大王你意犹未尽，还想要，输入1；大王您已找到欲寻的她了，不用奴才伺候了，输入0,\n");

scanf("%d",&m); //输入判断是否需要服务 break; } while(m);

if(m==0) //不需要服务时执行

{ printf("小的告退，小的期待与您的再会\n") ; printf("制作人；xxxxx\n") ; printf("指导老师；xxxxx\n") ; break; } } }

本文来源：https://www.bwwdw.com/article/26li.html