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

河南工程学院数据结构与算法课程设计成果报告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 (is.len & 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 (jt.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 (is.len & 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 (jt.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 (is.len & 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算法，通过调用函数对测试数据进行检测，并输出结果。按照编程思想，实现相应的程序，程序流程图如图2-5：图2-5 程序流程图2.5 测试程序说明程序测试：根据自己的程序，在主程序中设定相应的函数操作，通过函数接口调用相应的函数对自己建立的KMP算法匹配，并在屏幕显示相应的结果。void main() int nextMaxSize,nextvalMaxSize; SqString s,t; StrAssign(s,abcabcdabcdeabcdefabcdefg); StrAssign(t,abcdeabcdefab); printf(串 s:);DispStr(s); /* 串S*/ printf(串 t:);DispStr(t); /*串t*/ print(s,t); /*输出匹配模式还有next值和nextval值*/ printf(简单匹配 P 算法:n); printf( t 在s 中的位置=%dn,Index(s,t); /*简单匹配算法*/ GetNext(t,next); /*由模式串t求出 next 值*/ GetNextval(t,nextval); /*由模式串t求出 nextval值*/ printf(KMP 算法:n); printf( t 在s 中的位置=%dn,KMPIndex(s,t); /*KMP算法*/ printf(改进的 KMP算法:n); printf( t 在s 中的位置=%dn,KMPIndex1(s,t); /*改进的KMP算法*/3 程序清单#include #define MaxSize 100 /*最多的字符个数*/ typedef struct char chMaxSize; /*定义可容纳 MaxSize个字符的空间*/ int len; /*标记当前实际串长*/ SqString; void StrAssign(SqString &str,char cstr) /*str为引用型参数*/ int i; for (i=0;cstri!=0;i+) str.chi=cstri; str.len=i; void StrCopy(SqString &s,SqString t) /*s为引用型参数*/ int i; for (i=0;it.len;i+) s.chi=t.chi; s.len=t.len; int StrEqual(SqString s,SqString t) int same=1,i; if (s.len!=t.len) /*长度不相等时返回 0*/ same=0; else for (i=0;is.len;i+) if (s.chi!=t.chi) /*有一个对应字符不相同时返回 0*/ same=0; return same; int StrLength(SqString s) return s.len; SqString Concat(SqString s,SqString t) SqString str; int i; str.len=s.len+t.len; for (i=0;is.len;i+) /*将 s.ch0s.chs.len-1复制到 str*/ str.chi=s.chi; for (i=0;it.len;i+) /*将t.ch0t.cht.len-1复制到 str*/ str.chs.len+i=t.chi; return str; SqString SubStr(SqString s,int i,int j) SqString str; int k; str.len=0; if (is.len | js.len) printf(参数不正确n); return str; /*参数不正确时返回空串*/ for (k=i-1;ki+j-1;k+) /*将 s.chis.chi+j复制到 str*/ str.chk-i+1=s.chk; str.len=j; return str; SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.len=0; if (is1.len+1) /*参数不正确时返回空串*/ printf(参数不正确n); return s1; for (j=0;ji-1;j+) /*将 s1.ch0s1.chi-2复制到 str*/ str.chj=s1.chj; for (j=0;js2.len;j+) /*将 s2.ch0s2.chs2.len-1复制到 str*/ str.chi+j-1=s2.chj; for (j=i-1;js1.len;j+) /*将 s1.chi-1s.chs1.len-1复制到 str*/ str.chs2.len+j=s1.chj; str.len=s1.len+s2.len; return str; SqString DelStr(SqString s,int i,int j) int k; SqString str; str.len=0; if (is.len | i+js.len+1) /*参数不正确时返回空串*/ printf(参数不正确n); return str; for (k=0;ki-1;k+) /*将 s.ch0s.chi-2复制到 str*/ str.chk=s.chk; for (k=i+j-1;ks.len;k+)/*将 s.chi+j-1chs.len-1复制到 str*/ str.chk-j=s.chk; str.len=s.len-j; return str; SqString RepStr(SqString s,int i,int j,SqString t) int k; SqString str; str.len=0; if (is.len | i+j-1s.len) /*参数不正确时返回空串*/ printf(参数不正确n); return str; for (k=0;ki-1;k+) /*将 s.ch0s.chi-2复制到 str*/ str.chk=s.chk; for (k=0;kt.len;k+) /*将t.ch0t.cht.len-1复制到 str*/ str.chi+k-1=t.chk; for (k=i+j-1;k0) for (i=0;istr.len;i+) printf(%c,str.chi); printf(n); int Index(SqString s,SqString t) /*简单匹配算法*/ int i=0,j=0,k; while (is.len & j=t.len) k=i-t.len; /*返回匹配的第一个字符的下标*/ else k=-1; /*模式匹配不成功*/ return k; void GetNext(SqString t,int next) /*由模式串 t 求出next 值*/ int j,k; j=0;k=-1;next0=-1; while (jt.len-1) if (k=-1 | t.chj=t.chk) j+;k+; nextj=k; else k=nextk; void GetNextval(SqString t,int nextval) /*由模式串t 求出 nextval 值*/ int j=0,k=-1; nextval0=-1; while (jt.len) if (k=-1 | t.chj=t.chk) j+;k+; if (t.chj!=t.chk) nextvalj=k; else nextvalj=nextvalk; else k=nextvalk; int KMPIndex(SqString s,SqString t) /*KMP算法*/ int nextMaxSize,i=0,j=0,v; GetNext(t,next); while (is.len & j=t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1; /*返回不匹配标志*/ return v; int KMPIndex1(SqString s,SqString t) /*改进的 KMP算法*/ int nextvalMaxSize,nextMaxSize,i=0,j=0,v; GetNextval(t,next); GetNextval(t,nextval); while (is.len & j=t.len) v=i-t.len; /*返回匹配模式串的首字符下标*/ else v=-1; return v; void print(SqString s,SqString t)int j,nextMaxSize,nextvalMaxSize;GetNext(t,next); GetNextval(t,nextval);printf( j ); for (j=0;jt.len;j+) printf(%4d,j); printf(n); printf( tj ); for (j=0;jt.len;j+) printf(%4c,t.chj); printf(n); printf( next ); for (j=0;jt.len;j+) printf(%4d,nextj); printf(n); printf( nextval); for (j=0;jt.len;j+) printf(%4d,nextvalj); printf(n); void main() int nextMaxSize,nextvalMaxSize; SqString s,t; StrAssign(s,abcabcdabcdeabcdefabcdefg); StrAssign(t,abcdeabcdefab); printf(串 s:);DispStr(s); printf(串 t:);DispStr(t); print(s,t); printf(简单匹配 P 算法:n); printf( t 在s 中的位置=%dn,Index(s,t); GetNext(t,next); /*由模式串t求出 next 值*/ GetNextval(t,nextval); /*由模式串t求出 nextval值*/ printf(KMP 算法:n); printf( t 在s 中的位置=%dn,KMPIndex(s,t); printf(改进的 KMP算法:n); printf( t 在s 中的位置=%dn,KMPIndex1(s,t); 4 测试4.1 测试数据主串：abcabcdabcdeabcdefabcdefg子串：abcdeabcdefab4.2 测试结果运行主程序后结果显示如图4-1。图4-1子串匹配正确5 总结在这次课程设计中，我做的一个简单的模式匹配的KMP的算法，该算法是对一般算法的改进，KMP算法仅当模式与主串之间存在部分匹配时才比一般模式匹配算法快。其次该算法的最大特点是，指示主串的指针不需回溯，整个匹配过程中，对主串仅需要从头到尾扫描一遍，这时处理从外设输入的庞大文件有很大的效果，可以边输入边匹配，而无需回头读。不过通过具体的上机实验，我自己发现了自己在编程中的许多问题，也发现了自己在学习中的问题所在，通过老师的指导和同学的帮助，自己完成了老师所布置的任务，更在具体的实现过程中，复习了数据结构的排序算法基础知识，填补了自己在平时学习中的漏洞。参考文献1吴伟民.数据结构（C语言版）.清华大学出版社2吴永辉等.数据结构编程实验（第二版）.机械工业出版社3徐子珊.算法设计、分析与实现（第三版）.人民邮电出版社4刘振宇.数据结构（C语言版）.东软电子出版社5张乃孝.算法与数据结构（第二版）.高等教育出版社#include #define MaxSize 100 /*最多的字符个数*/ typedef struct char chMaxSize; /*定义可容纳 MaxSize个字符的空间*/ int len; /*标记当前实际串长*/ SqString; void StrAssign(SqString &str,char cstr) /*str为引用型参数*/ int i; for (i=0;cstri!=0;i+) str.chi=cstri; str.len=i; void StrCopy(SqString &s,SqString t) /*s为引用型参数*/ int i; for (i=0;it.len;i+) s.chi=t.chi; s.len=t.len; int StrEqual(SqString s,SqString t) int same=1,i; if (s.len!=t.len) /*长度不相等时返回 0*/ same=0; else for (i=0;is.len;i+) if (s.chi!=t.chi) /*有一个对应字符不相同时返回 0*/ same=0; return same; int StrLength(SqString s) return s.len; SqString Concat(SqString s,SqString t) SqString str; int i; str.len=s.len+t.len; for (i=0;is.len;i+) /*将 s.ch0s.chs.len-1复制到 str*/ str.chi=s.chi; for (i=0;it.len;i+) /*将t.ch0t.cht.len-1复制到 str*/ str.chs.len+i=t.chi; return str; SqString SubStr(SqString s,int i,int j) SqString str; int k; str.len=0; if (is.len | js.len) printf(参数不正确n); return str; /*参数不正确时返回空串*/ for (k=i-1;ki+j-1;k+) /*将 s.chis.chi+j复制到 str*/ str.chk-i+1=s.chk; str.len=j; return str; SqString InsStr(SqString s1,int i,SqString s2) int j; SqString str; str.len=0; if (is1.len+1) /*参数不正确时返回空串*/ printf(参数不正确n); return s1; for (j=0;ji-1;j+) /*将 s1.ch0s1.chi-2复制到 str*/ str.chj=s1.chj; for (j=0;js2.len;j+) /*将 s2.ch0s2.chs2.len-1复制到 str*/ str.chi+j-1=s2.chj; for (j=i-1;js1.len;j+) /*将 s1.chi-1s.chs1.len-1复制到 str*/ str.chs2.len+j=s1.chj; str.len=s1.len+s2.len; return str; SqString DelStr(SqString s,int i,int j) int k; SqString str; str.len=0; if (is.len | i+js.len+1) /*参数不正确时返回空串*/ printf(参数不正确n); return str; for (k=0;ki-1;k+) /*将 s.ch0s.chi-2复制到 str*/ str.chk=s.chk; for (k=i+j-1;ks.len;k+)/*将 s.chi+j-1chs.len-1复制到 str*/ str.chk-j=s.chk; str.len=s.len-j; return str; SqString RepStr(SqString s,int i,int j,SqString t) int k; SqString str; str.len=0; if (is.len | i+j-1s.len) /*参数不正确时返回空串*/ printf(参数不正确n); return str; for (k=0;ki-1;k+) /*将 s.ch0s.chi-2复制到 str*/ str.chk=s.chk; for (k=0;kt.len;k+) /*将t.ch0t.cht.len-1复制到 str*/ str.chi+k-1=t.chk; for (k=i+j-1;k0) for (i=0;istr.len;i+) printf(%c,str.chi); printf(n); int Index(SqString s,SqString t) /*简单匹配算法*/ int i=0,j=0,k; while (is.len & j=t.len) k=i-t.len; /*返回匹配的第一个字符的下标*/ else k=-1; /*模式匹配不成功*/ return k; void GetNext(SqString t,int next) /*由模式串 t 求出next 值*/ int j,k; j=0;k=-1;next0=-1; while (jt.len-1) if (k=-1 | t.chj=t.chk) j+;k+; nextj=k; else k=nextk; void GetNextval(SqString t,int nextval) /*由模式串t 求出 nextval 值*/ int j=0,k=-1; nextval0=-1; while (jt.len) if (k=-1 | t.chj=t.chk) j+;k+; if (t.chj!=t.chk) nextvalj=k; else nextvalj=nextv