文档介绍：膈螄数据结构肁课程设计报告羁莆膄设计题目:模式匹配中的KMP算法的实现袂螈蚈专业:计算机科技薃院系:计算机学院薂姓名:xxxxxxxx蝿学号:xxxxxxx螇芇莃时间:2013年9月22日袁羅螆肃蚈芈目录膅袃1需求分析 3薅2概要设计 3薄3详细设计 ()函数输出串。 - []函数 : 7袇4测试与分析 7蒃5总结 9螀6附录:源程序清单 9蚀参考文献 ,-莫里斯-莫拉特操作(简称为KMP算法)。肂对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是:从主串的S的第POS个字符开始起和模式的第一个字符比较之,如相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较之。以此类推,直到模式T中的每个字符依次和主串S中的一个连续字符序列相等,则称匹配成功,则函数值为和模式T中的第一个字符相等的字符在主串S中的序号,否则称匹配不成功,(n+m)的时间数量级上完成串的模式匹配操作。其改进过程在于:每当一趟匹配过程出现字符比较不相等时,不需回溯i指针,而是利用已经得到的部分匹配的结果将模式串向右滑动一段尽可能远的距离后,继续进行比较。滑动的这一段距离我们将会用到函数Next[],薀KMP算法的最大特点是指示主串的指针不须回溯,整个匹配过程中,对主串仅需从头到尾扫描一遍,这对处理从外设输入的庞大文件很有效,可以边度入边匹配,而无需回头重读。袈开发工具:。要求对于任何输入串A,实现算法求next函数值;利用next函数值,实现串A在串B中的定位;若未搜索到,就返回0。首先要从键盘输入主串B和模式串A,并采用用链式存储,再根据Next()函数求模式串的Next值,利用KMP算法进行匹配,再用输出函数输出结果!薁2概要设计羇对该kmp算法,定义的抽象数据类型如下:袄ADTString{蒂数据对象:D={ai|ai∈CharacterSet,i=1,2,3,…,n,n≥0}莈数据关系:R1={<ai-1,ai>|ai-1,ai∈D,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是非空串,1≤pos≤StrLength(S).艿操作结果:若主串S中存在和串T相同的子串,则返回他在主串S中的第pos个字符之后第一次出现的位置;否则函数值为0。羈DestoryString(&S)螆初始条件:串S存在。蒄操作结果:串S被销毁。莀}ADTString肆该算法是对串进行操作,对串的存储结构用线性表的链式存储结构表示:芅typedefstructLString{羀chardata;蒁structLString*next;葿}LString;蚅该算法分为三个模块:第一模块[Input()函数](利用该函数输入主串和模式串);第二模块[Output()函数利用该函数输出串)。第三模块[Length()](利用该函数求各串的长度);第四模块[Get_next()函数](利用该函数求出模式串的next函数值);第五模块[Index_KMP()函数](利用该函数进行主串和模式串之间的匹配);各个模块之间的调用关系如下图所示:。蚀艿薇开始肄输入A,B,pos蒁调用Input函数存储A,B芀调用Get_next函数蚆对A,B执行Length函数薃调用Index_KMP函数,膁并用Loc接收函数值莂调用Output输出A,B,输出LOC,Next肈结束羃羂腿膆蚆蚂膀蕿肅蒂羈蚇蒅膃聿螅羄袃肀膈莄蚄袈芆整个函数的流程图螃莄罿3详细设计:()函数输入主串和模式串Input()袀函数伪代码:肀LString*Input(){螇 //通过标准输入设备输入串以链式存储存储数据并返回链的头指针。袆 LString*head,*tail,*