模式匹配KMP算法数据结构课设

课程设计--------数据结构课程设计报告姓名：liuj学号：14专业班级：计算机113班日期：2013.01.28目录单词检索统计程序一．需求分析需求分析----------------------------------------------------------------------------------------------------------1二．程序设计目标1.设计思路----------------------------------------------------------------------------------------------------------12.数据结构----------------------------------------------------------------------------------------------------------4三．概要设计1.概要分析-----------------------------------------------------------------------------------------------------------52.函数流程图-------------------------------------------------------------------------------------------------------63.详细设计-----------------------------------------------------------------------------------------------------------7四．源程序代码1.源程序C++实现代码-----------------------------------------------------------------------------------------8五．调试结果及运行结果1.运行结果截图--------------------------------------------------------------------------------------------------13六．程序小结1.心得体会---------------------------------------------------------------------------------------------------------14七．参考书籍1.参考书籍-------------------------------------------------------------------------------------------14一．需求分析给定一个文本文件，要求统计给定单词在文本中出现的总次数，并检索输出某个单词出现在文本中的行号，在该行中出现的次数以及位置单词计数功能用到模式匹配算法，而KMP算法是对一般模式匹配算法的改进，其改进过程在于：每当一趟匹配过程出现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配结果将模式串向右滑动一段距离后，继续进行比较。滑动的这段距离用到函数next[]，KMP算法的最大特点就是不需回溯指针，整个匹配过程中，无需主串从头至尾扫描一遍。二．程序设计目标1.设计思路此程序的设计要求可以分为三部分来实现：其一，建立一个文本文件，文件名有用户用键盘输入；其二，给定单词计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定的单词，输入一个单词，检索并输出该单词所在的行号，该行中出现的次数以及在该行中的相应位置。给定单词计数的实现思路：该功能需要用到模式匹配算法，逐行扫描文本文件，匹配一个，计数器加1，直到整个文件扫描结束，然后输出单词出现的次数。串是非数值处理中的主要对象，在串的基本操作中，模式匹配或串匹配就是求子串在主串中首次出现的位置。朴素模式匹配算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与主串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符开始比较，而且要从主串的任何位置检索匹配字符串。其实现过程如下：(1).输入要检索的文本文件名，打开相应文件；(2).输入要检索统计的单词；(3).循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数，其描述如下：While(不是文件结束){读入一行并到串中；求出串长度；模式匹配函数计数；}(4).关闭文件，输出统计结果。检索单词在文本文件中的行号，次数及其位置的实现思路是：(1).输入要检索的文本文件名，打开相应的文件；(2).输入要检索统计的单词；(3).行计数器置初值0；While(不是文件结束){读入一行到指定串中；求出串长度；行单词计数器0；调用模式匹配函数匹配单词定位，该行匹配单词计数：行号计数器加一；If（行单词计数器！=0）输出行号，该行有匹配单词的个数以及相应的位置}2.数据结构串的定长顺序存储表示：#defineMAXSTRLEN255//用户可在255以内定义最大串长TypedefunsignedcharSString[MAXSTRLEN+1];求子串SubString(&sub,S,pos,len)过程即为复制字符序列的过程，将串S中第pos个字符开始长度为len的字符序列复制到串Sub中去，当参数非法时，返回ERRORStatusSubString(Sstring&Sub,SstringS,intpos,intlen)//用Sub返回串s第pos个字符起长度为len的子串0=len=StrLength(S)-pos+1If(pos=0||lenS[0]-pos+1)returnERRORSub[l...len]=S[pos....pos+len+1];Sub[0]=len;ReturnOK;}//endofSubString;由此可见，在顺序存储结构中，实现串的原操作为“字符序列的复制”，操作时间复杂度基于复制的字符序列的长度。三．概要设计1.概要分析对该KMP算法，串的抽象数据类型的定义如下：ADTString{数据对象：D={ai|ai¢CharacterSet,i=1,2.......,n,n=0}数据关系：R1={ai-1,ai|ai-1,i=1,2,.....,n}基本操作：StrAssign(&T,chars)初始条件：chars是字符串常量；操作结果：生成一个其值等于chars的串t;StrCopy(&T,S)初始条件：串S存在；操作结果：由串S复制得串t；StrEmpty(S)初始条件：串S存在；操作结果：若串s为空串，则返回true,否则返回false；StrCompare(S,T)初始条件：串s和t存在；操作结果：若ST,则返回0,若ST，则返回0,若S=T,则返回=0；StrLength(S)初始条件：串s存在；操作结果：返回s的元素个数，即为串的长度；ClearString(&S)初始条件：串s存在；操作结果：将s清为空串；Concat(&T,s1,s2)初始条件：串s1和s2存在；操作结果：用T返回由s1和s2连接而成的新串；SubString(&Sub,S,pos,len)初始条件：串s存在，1=pos=StrLength(S);Index(S,T,pos)初始条件：串s和t存在，t是非空串操作结果：若主串s中存在和串t值相同的子串，则返回它在主串s中第pos个字符之后长度为第一次出现的位置，否则函数值为0；}ADTString2.函数流程图3.详细设计求模式串的模式值GetNext()函数用KMP模式匹配算法，当主串和模式串匹配不相等时，模式串应向右移动一段距离，此时要得到模式串的next函数值.如何求next函数，可用递归方法求得next函数值,在当前的匹配过程中，已有Pj-k+1=P1,Pj-k+2=P2,........Pj-1=Pk-1,则当Pj!=Pk时应将模式向右滑动至第next[k]个字符和第j个字符相比较，若next[k]=k’,且Pj=Pk’，则说明在主串中第j+1个字符之前存在一个长度为k’的最长子串，和模式串中从首字符起长度为k’的子串相等，即’p1......pk’=’Pj-k+1.........Pj’。也就是说，next[j+1]=k’+1,即next[j+1]=next[k]+1,同理，若Pj!=Pk，则将模式继续向右滑动直至将模式中第next[k’]个字符和Pj对齐，...........以此类推，直至Pj和模式中某个字符匹配成功或不存在任何k’满足’p1......pk’=’Pj-k+1.........Pj’，则next[j+1]=1求next函数值过程的伪码算法如下：voidGetNext(charT[MAXSTRLEN],int(&next)[64],intm){inti,j;i=0;next[0]=-1;for(j=1;jm;j++){i=next[j-1];while(T[j]!=T[i+1]&&i=0)i=next[i];if(T[j]==T[i+1])next[j]=i+1;elsenext[j]=-1;}for(j=0;j=m;j++){printf(next[%d]=%-3d,j,next[j]);if((j+1)%5==0)printf(\n);}coutendl;}模式匹配KMP实现在求得模式匹配的next函数值后，指针i,j分别表示主串和模式串正待比较的字符，i的初值为pos，j的初值为1，若在匹配过程中Si=Pj，则i,j分别增1，否则，i不变，j退到next[j]继续比较，若相等，则i,j都增1，否则j再退到下一个next值的位置，，以此类推，有两种可能：一是j退到某个next值时字符比较相等，则指针各自增1，继续匹配；另一种是，j退到值为0，则此时将模式串再向右滑动一个位置，重新开始匹配。IndexKMP伪代码算法如下：intIndexKMP(charS[MAXSTRLEN],charT[MAXSTRLEN],int(&next)[64]){inti,j,n,m;i=j=1;n=(int)S[0];m=(int)T[0];while((in||jm)&&T[j]!='\0'&&S[i]!='\0')if(j==0||S[i]==T[j]){++i;++j;}elsej=next[j];if(j=m)returni+1-m;elsereturn0;}四．源程序实现代码C++实现代码：#includeiostream#includeiomanip#includestdio.h#includestdlib.h#includestring.h#defineMAXSTRLEN64usingnamespacestd;//如果next[j]=0,则主串的指针i不变，而且将指针j移动到next[j]的位置继续匹配voidGetNext(charT[MAXSTRLEN],int(&next)[64])//int(&next)[64]表示定义一个数组指针，next指向含有64个元素的一维数组{inti,j;i=1;next[1]=j=0;while(i(int)T[0])if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];for(j=1;j(int)T[0];j++){printf(next[%d]=%-3d,j,next[j]);if((j)%5==0)printf(\n);}coutendl;}voidGetNext(charT[MAXSTRLEN],int(&next)[64],intm){inti,j;i=0;nex