数据结构课程设计报告- KMP算法的程序设计与实现

河南工程学院数据结构与算法课程设计成果报告KMP算法的程序设计与实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目KMP算法的程序设计与实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计目标11.2 课程设计任务12 分析与设计22.1题目实现步骤22.2 存储结构设计22.3 算法描述22.4 程序流程图62.5 测试程序说明73 程序清单84 测试174.1 测试数据174.2 测试结果175 总结18参考文献191 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 （5）通过KMP算法掌握字符串的类型定义方法，掌握字符串的操作和应用。（6）通过数据结构串的比较等基本操作实现对子串与主串部分是否匹配的检验。（7）掌握串的模式匹配运算原则在解决实际问题中的应用 。1.2 课程设计任务（1）对输入的任意子串，实现KMP算法；（2）能借助语言环境实现图形显示功能，将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1题目实现步骤为了实现题目要求：（1）先理解程序的功能，知道并会利用算法匹配的核心算法。（2）首先设计数据的存储结构，构建程序框架，设计程序流程图。（3）实现程序的功能模块，完成程序的调试。2.2 存储结构设计定义一个结构体数组，其空间足够大，可将输入的字符串存在数组中。#define MaxSize 100 /*最多的字符个数*/ typedef struct char chMaxSize; /*定义可容纳 MaxSize个字符的空间*/ int len; /*标记当前实际串长*/ SqString; 2.3 算法描述（1）简单匹配算法首先要想实现基本的算法匹配。分别利用计数指针i、j提示主串S和匹配串T中当前正待比较的字符位置。算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。以此类推，直至模式T中的每个字符以此和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为核模式T中第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为零。int Index(SqString s,SqString t) /*简单匹配算法*/ int i=0,j=0,k; while (i<s.len && j<t.len) if (s.chi=t.chj) /*继续匹配下一个字符*/ i+;j+; else /*主串、子串指针回溯重新开始下一次匹配*/ i=i-j+1;j=0; if (j>=t.len) k=i-t.len; /*返回匹配的第一个字符的下标*/ else k=-1; /*模式匹配不成功*/ return k; （2）KMP算法对模式匹配进行改进成为KMP算法。每当一趟匹配过程中出现字符比较不等时，不许回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。若令nextj=k, 则nextj表明当模式中第i个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行比较的字符的位置。void GetNext(SqString t,int next) /*由模式串 t 求出next 值*/ int j,k; j=0;k=-1;next0=-1; while (j<t.len-1) if (k=-1 | t.chj=t.chk) j+;k+; nextj=k; else k=nextk; 在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别之时主串和模式中正待比较的字符，令i的初值为pos，j的初值为1。若再匹配过程中Si=Pi，则i和j分别增加1，否则，i不变，而j退到nextj的位置再比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，以此类推，直到下列俩种可能：一种是j退到某个next值的字符比较相等，则指针各自增1，继续进行匹配；另一种是j退到值为零（即模式的第一个字符“失配”），则此时需将模式继续向右滑动一个位置，即从主串的下一个字符Si+1起和模式重新开始匹配。int KMPIndex(SqString s,SqString t) /*KMP算法*/ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (i<s.len && j<t.len) if (j=-1 | s.chi=t.chj) i+;j+; /*i,j 各增1*/ else j=nextj; /*i 不变,j 后退*/ if (j>=t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志*/ return v; （3）优化KMP算法前面定义的next函数在某些情况下尚有缺陷。例如模式“aaaaab”在主串“aabaaaab”匹配时，当i=4、j=4时s.ch4!=t.ch4,由nextj的指示还需进行i=4、j=3，i=4、j=2，i=4、j=1这3次比较。实际上，因为模式中第1，2，3个字符和第4个字符都相等，因此不需要再和主串第4个字符相比较，而可以将模式一气向右滑动4个字符的位置直接进行i=5、j=1时的字符比较。这就是说，若按上述定义得到nextj=k，而模式中pj=pk，则当主串中字符si和pj 比较不等时，不需要再和pk进行比较，而直接和pnextk进行比较，换句话说，此时的nextj应和nextk相同。由此可得计算next函数修正值的算法。void GetNextval(SqString t,int nextval) /*由模式串t 求出 nextval 值*/ int j=0,k=-1; nextval0=-1; while (j<t.len) if (k=-1 | t.chj=t.chk) j+;k+; if (t.chj!=t.chk) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; 此时的算法匹配：int KMPIndex1(SqString s,SqString t) /*改进的 KMP算法*/ int nextvalMaxSize,nextMaxSize,i=0,j=0,v; GetNextval(t,next); GetNextval(t,nextval); while (i<s.len && j<t.len) if (j=-1 | s.chi=t.chj) i+;j+; else j=nextvalj; if (j>=t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1; return v; 2.4 程序流程图简单匹配算法Index(s,t)KMP算法KMPIndex(s,t)优化KMP算法KMPIndex1(s,t)开始输入s,t输出结果结束本设计题分为三模块：第一模块：简单匹配算法；第二模块：KMP算法，这个模块里面要有next值的方法；第三模块：优化KMP算法，这个模块里面有对next的改进nextval方法；方便在main函数中调用。设计存储结构，实现KMP算法，通过调用函数对测