文档介绍：Forpersonaluseonlyinstudyandresearch;mercialuse莆蚃数据结构肁课程设计报告聿膈螆设计题目:模式匹配中的KMP算法的实现膁蒀薆专业:计算机科技蒅院系:计算机学院芁姓名:xxxxxxxx袁学号:xxxxxxx芈芄莁时间:2013年9月22日节螅芇蒁莈蒇目录肅薁1需求分析 3袄2概要设计 3蚁3详细设计 ()函数输出串。 - []函数 : 7荿4测试与分析 7蚆5总结 9螀6附录:源程序清单 9螈参考文献 ***KMP算法是对一般模式匹配算法的改进,由同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为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(){芆 //通过标准输入设备输入串以链式存储存储数据并返回链的头指针。膅 LSt