




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、河南工程学院数据结构与算法课程设计成果报告KMP算法的实现学生学号: 学生姓名: 学 院: 计算机学院 专业班级: 软件工程1342 专业课程: 数据结构与算法 指导教师: 2014 年 12 月 29 日题 目KMP算法的实现考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总 评 成 绩
2、指导教师评语: 日期: 年 月 日目 录1 设计KMP算法的目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 KMP算法的基本思想22.2 概要描述22.3 存储结构设计32.4 算法描述32.5 程序流程图72.6 测试程序说明83 程序清单94 测试134.1 测试数据134.2 测试结果分析145 总结15参考文献161 设计KMP算法的目标与任务要完成查找替换功能就需要用到字符串匹配算法。字符串匹配的算法有很多,最著名的字符串匹配算法有:KMP算法,Boyer-Moore(BM)算法等。如果要我们自己去实现字符串匹配功能,当然,最容易想到的方法就是人们常说
3、的蛮力匹配法。但是更希望通过效率高,结构简单,以及可行性强的方法来进行匹配。显然,KMP算法正好符合这些要求。1.1 课程设计目标通过本次对KMP算法的课程设计,使自己在软件设计的综合训练,包括问题分析,总体结构设计用户界面设计,以及程序设计基本技能和技巧等各方面得到锻炼:(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法;(2)通过上机实习,验证自己设计的算法的正确性,学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改;(3)培养算法分析能力,分析所设计算法的时间复杂度和空间复杂度,进
4、一步提高程序设计水平;(4)尽可能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来,获得算法的直观感受。1.2 课程设计任务KMP算法效率高,结构简单,可行性强,而且易于对主串进行多模式的匹配。因此,我们需要更进一步的对KMP算法做更深一步的了解。于是设计KMP算法的相关函数库,以便在程序设计中调用,要求:(1)对输入的任意子串,实现KMP算法;(2)最好能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与
5、设计一般来说,用计算机解决一个具体的问题时,大致需要经过下列几个步骤:首先要从具体问题抽象出一个适当的数据模型,然后设计一个解此数学模型的算法,最后编出程序,进行测试、调整直至最终解答。2.1 KMP算法的基本思想KMP算法的关键在于设定一个next()函数,next()函数取决于模式本身而和主串无关,函数本身包含了局部的匹配信息。在设定了next()函数之后,匹配可如何进行:假设i和j分别为指示主串和模式串中正在比较的字符的当前位置,并对i 和j 赋初值0。在匹配的过程中,若si=tj,则i和j分别增加1,继续进行比较,否则,i不变,而j退回到nextj的位置进行新一轮的比较。如此递推下去,
6、直到出现下列两种情况:当j退回到某个值nextj值时,匹配成功,则i和j分别增加1继续匹配;当j退回到值为0时,即nextj=0,说明主串的当前字符匹配失败,这时将主串向右滑动一个位置,即从i+1处重新开始新一轮的匹配,此时j=0。2.2 概要描述KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特莫里斯普拉特操作(简称KMP算法)。KMP算法的核心思想是通过空间效率来换时间效率,它在进行字符串A和B匹配之前,需要先计算出B的一些特性,然后根据这些特性来优化匹配算法。对该KMP算法,定义的抽象数据类型如下:ADT S
7、tring数据对象:D=ai|aiCharacterSet,i=1,2,3,n,n0数据关系:R1=|ai-1,aiD,i=2,n基本操作: StrAssign(&T,chars)初始条件:chars是字符串常量。操作结果:生成一个其值等于chars的串T。 StrCopy(S)初始条件:串S存在。操作结果:若S为空串,则返回TRUE,否则返回FALSE。 StrLength(S)初始条件:串S存在。操作结果:返回S元素的个数,成为串的长度。 Index(S,T,pos)初始条件:串S和T存在,T是非空串,1posStrLength(S).操作结果:若主串S中存在和串T相同的子串,则返回他在主
8、串S中的第pos个字符之后第一次出现的位置;否则函数值为0。 DestoryString(&S)初始条件:串S存在。操作结果:串S被销毁。ADT String2.3 存储结构设计该KMP算法是对串进行操作的,对串的存储结构用线性表的链式存储结构表示:typedef struct LString char data; struct LString *next; LString; 2.4 算法描述先设置输入函数,利用Input()函数输入主串和模式串。其代码如下:LString *Input()/通过标准输入设备输入串以链式存储存储数据并返回链的头指针。LString *head, *tail,
9、*p; int curlen=0; char ch; head=(LString*)malloc(sizeof(LString);/建立头指针。 if(!head) printf(存储分配失败); exit(0); /存储分配失败。 scanf(%c,&ch); while(ch!=n) p=(LString*)malloc(sizeof(LString); if(!p) printf(存储分配失败); exit(0); /存储分配失败。 p-data=ch; p-next=NULL; if(curlen=0) head-next=p; else tail-next=p; tail=p; +c
10、urlen; head-data=curlen;/用头指针存储串的长度 scanf(%c,&ch); return head;/Inpute有输入当然就有输出,对应的把输出函数Output()给编写出来。其代码如下:void Output(LString *T) /在标准输出设备上输出串T。 LString *p; p=T-next; while(p!= NULL) printf(%c,p-data); p=p-next; printf(n); /OutputLength()函数求的各串的长度,利用一个while循环语句,为后面的函数做好准备工作;其代码如下:int Length(LStrin
11、g *T) /求串T的长度并返回其值。int n=0;LString *head;head=T;if(head) n=head-data; return n; /LengthKMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。其代码如下:void Get_next(SString T,int next)/求模式串T的next函数并存入数组next。 i = 1;next1 = 0; j = 0; while (it0) if(j= =0 | ti = = tj) +i; +j; n
12、exti = j; else j= nextj; /Get_next最后,应该利用Index_KMP()函数实现主串和模式串的匹配。其代码如下:int Index_KMP(SString S,SString T,int pos,int next) / 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 / KMP算法。其中,T非空。,1posStrLength(S)。 i = pos; j = 1; while (i = S0& j t0) return i-t0; / 匹配成功 else return 0; / Index_KMP2.5 程序流程图该算法分为五个模块:第一模块
13、Input( )函数(利用该函数输入主串和模式串);第二模块Output( )函数利用该函数输出串)。第三模块Length()(利用该函数求各串的长度);第四模块Get_next( )函数(利用该函数求出模式串的next函数值);第五模块Index_KMP()函数(利用该函数进行主串和模式串之间的匹配);各个模块之间的调用关系如下图所示:图1是对整个函数的流程图。开始输入A,B,pos调用Get_next()函数调用Index_KMP()函数。调用Input()函数计算输入串的长度调用Output()函数,输出A,B,pos和next结束 图1 程序的流程图2.6 测试程序说明根据程序的提示,
14、输入主串,然后以Enter键结束。其运行结果如下图2: 图2 主串的输入再输入模式串,同样以Enter键结束。其运行结果如下图3:图3 模式串的输入然后输入主串开始匹配的位置,便可执行主串与模式串的匹配。3 程序清单#include #include #include typedef struct LString /串的链式存储表示。char data;struct LString *next;LString;LString *Input()/通过标准输入设备输入串以链式存储存储数据并返回链的头指针。LString *head, *tail, *p; int curlen=0; char ch
15、; head=(LString*)malloc(sizeof(LString);/建立头指针。 if(!head) printf( 存储分配失败); exit(0); /存储分配失败。 scanf(%c,&ch); while(ch!=n) p=(LString*)malloc(sizeof(LString); if(!p) printf( 存储分配失败); exit(0); /存储分配失败。 p-data=ch; p-next=NULL; if(curlen=0) head-next=p; else tail-next=p; tail=p; +curlen; head-data=curlen
16、;/用头指针存储串的长度 scanf(%c,&ch); return head;/Inputevoid Output(LString *T)/在标准输出设备上输出串T。 LString *p; p=T-next; while(p!= NULL) printf(%c,p-data); p=p-next; printf(n); /Outputint Length(LString *T)/求串T的长度并返回其值。int n=0;LString *head;head=T;if(head) n=head-data; return n; /Length void Get_next(LString *T,i
17、nt next) /求模式串T的next函数并存入数组next。 int i=1; int j=0; int k; char t100; LString *p; p=T;for(k=0;kdata; p=p-next; next1=0; while (it0) if(j=0 | ti= tj) +i; +j; nexti = j; else j= nextj; nexti+1=n;/Get_nextint Index_KMP(LString *S, LString *T,int pos,int next) / 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 / KMP算法。
18、其中,T非空。,1posStrLength(S)。 int i = pos; int j = 1; int k; LString *p,*q; char s255,t255; p=S; q=T; for(k=0;kdata; p=p-next; for(k=0;kdata; q=q-next; while (i = Length(S) & j t0) return i-t0; / 匹配成功 else return 0; / Index_KMPvoid main() int Loc, Next255, pos=0,i=1,j=1; LString *A,*B; printf( 输入执行KMP算法
19、主串A并以ENTER键结束:n主串:); A=Input();/从标准输入设备接收主串。 printf( 输入执行KMP算法的模式串B并以ENTER键结束:n模式串:); B=Input();/从标准输入设备接收模式串。 printf(n); printf( 输入执行KMP算法从主串开始的位置并以ENTER键结束:npos=); scanf(%d,&pos);/从标准输入设备接收在主串执行KMP算法的开始位置。 while(pos1)/判断输入是否正确。 printf( 输入错误请重新输入执行KMP算法的位置:npos=); scanf(%d,&pos); printf(nn 匹配结果如下:n
20、);/将结果输出到标准输出设备上。 printf(匹配结果3nn); Get_next(B,Next);/调用Get_next函数。 Loc=Index_KMP(A,B,pos,Next);/调用Index_KMP函数并用Loc接收其函数值。 printf( 对B执行Next函数的值:nttt);/将next输出到标准输出设备上。 for(i=1;Nexti!=n;i+) printf(%d ,Nexti); if(Loc!=0) printf(n 模式串在主串的第%d位置:nn,Loc); printf(ttt); Output(A); printf(ttt); while(jLoc) pr
21、intf( ); +j; Output(B); else printf( ttt 匹配失败nn); if(Loc=0) printf(ttt匹配失败n); else printf(ttt匹配成功n);/main4 测试经历了将问题抽象成一个适当的数学模型,设计一个解此数学模型的算法,编出程序,最终再做最后的测试与调整。4.1 测试数据首先,根据测试程序说明输入主串,模式串以及开始匹配的位置。如下图4: 图4 输入图最后,以Enter键结束就可以获得匹配的结果。其结果如下图5:图5 匹配结果4.2 测试结果分析经历了多次的测试与调整,我们最终调试出了KMP算法的程序代码。对结果进行分析,其KMP
22、算法与一般的匹配算法的不同在于:每当一趟匹配过程中出现字符比较不等时,不需回溯i指针,而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。如下图6:a b a b c d e f s a a d a d w g t l第一趟匹配 a b c此处不同a b a b c d e f s a a d a d w g t l第二趟匹配 a b c匹配成功图6 匹配过程然而在反复的测试和调试的过程中,这个KMP算法程序并没有想象的那么成功,在调试的过程中多多少少会出现了一些小问题。例如,在输入匹配的起始位置时,输入超出范围的数字。虽然可以运行程序,但不符合常规逻辑。
23、所以,仍然还是要在主函数中插入一个while语句,先判断输入的pos是否合理。其代码如下:while(pos1)/判断输入是否正确。 printf( 输入错误请重新输入执行KMP算法的位置:npos=); scanf(%d,&pos); 5 总结通过这一周的课程设计,克服了层层的阻碍,最终调试出了KMP算法的程序。在此过程中发现自己在算法的设计与实现方面思路闭塞,并且对数据结构的理解不够深以及知识点的运用够不灵活。虽然发现很多不足,但也算喜有所获。在此次课程设计的过程中,自己对串的模式匹配以及链式存储结构又有了更深的理解,并且也进一步提高了自己的逻辑思维能力。而且,自己在课程设计中,更喜欢自己
24、动手去完成设计,虽然有诸多不懂得地方,但通过查阅资料以及寻求老师和同学的帮助,都已经得到了解决。总而言之,在此次课程设计中,收货颇丰,无论是课程设计的逻辑思维能力,还是在软件工作所需要的动手能力都得到了综合的发展。并且,在日后的日子中,会继续保持自己的优点,通过日常上机积累来弥补自己的不足。参考文献1严蔚敏等.数据结构(C语言版).清华大学出版社2谭浩强.C语言程序设计(第三版).清华大学出版社3LinDen,P.V.D(林登)C专家编程.人民邮电出版社#include #include #include typedef struct LString /串的链式存储表示。char data;s
25、truct LString *next;LString;LString *Input()/通过标准输入设备输入串以链式存储存储数据并返回链的头指针。LString *head, *tail, *p; int curlen=0; char ch; head=(LString*)malloc(sizeof(LString);/建立头指针。 if(!head) printf( 存储分配失败); exit(0); /存储分配失败。 scanf(%c,&ch); while(ch!=n) p=(LString*)malloc(sizeof(LString); if(!p) printf( 存储分配失败)
26、; exit(0); /存储分配失败。 p-data=ch; p-next=NULL; if(curlen=0) head-next=p; else tail-next=p; tail=p; +curlen; head-data=curlen;/用头指针存储串的长度 scanf(%c,&ch); return head;/Inputevoid Output(LString *T)/在标准输出设备上输出串T。 LString *p; p=T-next; while(p!= NULL) printf(%c,p-data); p=p-next; printf(n); /Outputint Lengt
27、h(LString *T)/求串T的长度并返回其值。int n=0;LString *head;head=T;if(head) n=head-data; return n; /Length void Get_next(LString *T,int next) /求模式串T的next函数并存入数组next。 int i=1; int j=0; int k; char t100; LString *p; p=T; for(k=0;kdata; p=p-next; next1=0; while (it0) if(j=0 | ti= tj) +i; +j; nexti = j; else j= nextj; nexti+1=n;/Get_nextint Index_KMP(LString *S, LString *T,int pos,int next) / 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 / KMP算法。其中,T非空。,1posStrLength(S)。 int i = pos; int j = 1; int k; LString *p,*q; char s255,t25
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论