1、 年 月 日答辩教师评语及成绩教研室意见总成绩： 室主任签名：注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。课程设计任务书20112012学年第一学期专业： 计算机科学与技术 学号： * 姓名： 高虹 课程设计名称： 数据结构课程设计 设 计 题 目： 模式匹配中的KMP算法的实现 完 成 期 限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周设计内容：用C/C+编写一个程序实现字符串的查找。要求使用KMP匹配算法，从键盘输入一段文本和待查找文本，若文本中含有待查找文本，则程序能够自动找出待查找文本的位置，若没有则给出提示。设计要求:1）问题分
2、析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具
3、体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；以上要求中前三个阶段的任务完成
4、后，先将设计说明数的草稿交指导老师面审，审查合格后方可进入后续阶段的工作。设计工作结束后，经指导老师验收合格后将设计说明书打印装订，并进行答辩。指导教师（签字）： 教研室主任（签字）：批准日期： 2011年 8月 29 日摘 要本次课程设计通过使用KMP算法将模式匹配算法进行了简化。这种算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特莫里斯普拉特操作（简称为算法）。此算法可以在（）的时间数量级上完成串的模式匹配操作。通过使用KMP匹配算法，从键盘输入一段文本和待查找文本，若文本中含有待查找文本，则程序能够自动找出待查找文本的位置，若没有则给出提
5、示。关键字：KMP算法；模式匹配；待查找文本1课题描述字符串子串在原串中的定位操作通常称为字符串的模式匹配，是各种传处理系统中最重要的操作之一。字符串定位字串的方法比较多，这里实现用KMP算法来实现模式穿的匹配，给出模式串，要求程序求出其Nextj。KMP匹配算法高效的部分就是此次匹配失败后下次比较开始位置的确定，这样每次平均移动的字符就不止一个，大大减少了循环的次数，而且比较指针没有回调，提高了效率。设计思想：这个算法的关键在于,当某个位置的匹配不成功的时候,应该从模式字符串的哪一个位置开始新的比较.假设这个值存放在一个next数组中,其中next数组中的元素满足这个条件:nextj = k
6、,表示的是当模式字符串中的第j + 1个发生匹配不成功的情况时,应该从模式字符串的第k + 1个字符开始新的匹配。2问题定义和任务分析本课设要求使用KMP匹配算法，从键盘输入一段文本和待查找文本，若文本中含有待查找文本，则程序能够自动找出待查找文本的位置，若没有则给出提示。KMP算法是模式匹配的一种模式匹配算法的升级。其改进在于每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。3逻辑设计通过对课题的分析设计，画出程序流程图，如图1.1所示。图1.1 程序流程图在此程序中调用了Index_KMP（S,T
7、,x）函数，Index_KMP（S,T,x）函数的流程图如图1.2所示。图1.2 Index_KMP（S,T,x）函数流程图在Index_KMP（S,T,x）函数的流程图中又调用了GetNext（T,next）函数，GetNext（T,next）函数流程图如图1.3所示。图1.3 GetNext（T,next）函数流程图4详细设计在模式匹配中的KMP算法的实现的函数中主函数先定义主串S、模式串T和x，并设两字符串的长度为为s和t，赋值为0，再分别求得两字符串的长度，最后调用Index_KMP（S,T,x）函数，求得匹配位置。在Index_KMP（S,T,x） 函数中，先定义next200数组，
8、定义i、j并赋值为0，接下来调用GetNext（T,next）函数，通过循环判断条件is&j=t条件判断语句，如果成立，执行x=i-t+1；如果不成立，则执行x=-1。函数GetNext（T,next）的作用是求得模式串T的next函数值并存入数组next。先定义j和k，并给j赋值为0,k赋值为-1,next0赋值为-1，再通过循环判断jt-1条件进入while循环，假如if判断条件k = -1|Tj = Tk，如果条件成立，则执行j+，k +并继续进行if判断，符合条件Tj!=Tk就执行nextj=k，不符合条件就执行nextj=nextk；如果条件k = -1|Tj = Tk不成立，则执行
9、k=nextk。5程序编码模式匹配中的KMP算法的实现程序代码如下所示：#include stdlib.hstringconio.h#include#define MAX 200using namespace std;char SMAX,TMAX;int s = 0,t = 0;void GetNext（char *T,int *next）/求模式串T的next函数值并存入数组next int j,k; j = 0,k = -1,next0 = -1; while（jt-1） if（k = -1|Tj = Tk） j +; k +; if（Tj!=Tk） nextj = k; else nex
10、tj = nextk; else k = nextk; int Index_KMP（char *S,char *T,int &x）/利用模式串T的next函数求T在主串S中第x个字符之后的位置的KMP算法。其中T非空，1xstrlen（S）。 int next200; int i,j; i = 0;j = 0; GetNext（T,next）; while（i=t）/匹配成功 x = i-t+1; else x = -1; return 1;int main（）/主函数 int x; printf（Please Input The String Of S:n）; gets（S）;Please
11、Input The String Of T: gets（T）; s = strlen（S）; t = strlen（T）; Index_KMP（S,T,x）;The String Start at %dn,x）; system（pause return 0;6程序调试与测试（1）在Index_KMP函数中，要返回利用return返回一个有用的值，如图2.1所示。图2.1 return返回值当删除return返回值，则程序出错，如图2.2所示。图2.2 删除return返回值（2）在GetNext函数中，给数组next中的next0赋值为-1，如图2.3所示。图2.3 next0赋值为-1当其改
12、为0时，出现函数无法运行的结果，如图2.4所示。图2.4 改后程序运行结果7结果分析运行模式匹配中的KMP算法的实现的程序，当找到匹配的字符串的位置时，运行结果如图3.1所示。图3.1 找到匹配字符位置运行模式匹配中的KMP算法的实现的程序，当没找到匹配的字符串的位置时，返回值为-1，运行结果如图3.2所示。图3.2 没有找到匹配位置8总结通过此次模式匹配中的KMP算法的实现的课设，我认识到自己在以前的课程学习中还有很多的不足。在课设中，我了解到各种算法对软件设计的重要性，它能帮助程序设计者设计出更好的程序为人们的日常生活提供了更大的帮助。本次课设在平时的字符的查找中发挥了重要作用。这次课设让我对C语言又复习了一遍。此次课设已经结束，但我不会结束对数据结构和C语言的学习。很高兴能和同学们一起完成模式匹配中的KMP算法的实现的课设，谢谢老师的帮助，也谢谢我的同学们。参考文献1 严蔚敏,吴伟民. 数据结构（C语言版）. 北京：清华大学出版, 20082 朱素英, KMP模式匹配算法的探讨.浏览网,20073 侯识忠,数据结构算法.北京：中国水利水电出版社,20054 胡明,模式匹配KMP算法中求next数组的算法.长春工业大学计算机科学与工程学院,20075 张海藩.软件工程（第五版）.北京:人民邮电出版社，2010
