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

《模式匹配KMP算法数据结构课设.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计--------数据结构课程设计报告姓名：liuj学号：14专业班级：计算机113班日期：2013.01.28目录单词检索统计程序一．需求分析需求分析----------------------------------------------------------------------------------------------------------1二．程序设计目标1.设计思路----------------------------------------------------------------------------------------

2、------------------12.数据结构----------------------------------------------------------------------------------------------------------4三．概要设计1.概要分析-----------------------------------------------------------------------------------------------------------52.函数流程图-----------------------------

3、--------------------------------------------------------------------------63.详细设计-----------------------------------------------------------------------------------------------------------7四．源程序代码1.源程序C++实现代码--------------------------------------------------------------------------------

4、---------8五．调试结果及运行结果1.运行结果截图--------------------------------------------------------------------------------------------------13六．程序小结1.心得体会---------------------------------------------------------------------------------------------------------14七．参考书籍1.参考书籍----------------------------

5、---------------------------------------------------------------14一．需求分析给定一个文本文件，要求统计给定单词在文本中出现的总次数，并检索输出某个单词出现在文本中的行号，在该行中出现的次数以及位置单词计数功能用到模式匹配算法，而KMP算法是对一般模式匹配算法的改进，其改进过程在于：每当一趟匹配过程出现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配结果将模式串向右滑动一段距离后，继续进行比较。滑动的这段距离用到函数next[]，KMP算法的最大特点就是不需回溯指针，整个匹配过程中，无需主串从头

6、至尾扫描一遍。二．程序设计目标1.设计思路此程序的设计要求可以分为三部分来实现：其一，建立一个文本文件，文件名有用户用键盘输入；其二，给定单词计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定的单词，输入一个单词，检索并输出该单词所在的行号，该行中出现的次数以及在该行中的相应位置。给定单词计数的实现思路：该功能需要用到模式匹配算法，逐行扫描文本文件，匹配一个，计数器加1，直到整个文件扫描结束，然后输出单词出现的次数。串是非数值处理中的主要对象，在串的基本操作中，模式匹配或串匹配就是求子串在主串中首次出现的位置。朴素模式匹配算法的基本思路是将给

7、定子串与主串从第一个字符开始比较，找到首次与主串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符开始比较，而且要从主串的任何位置检索匹配字符串。其实现过程如下：(1).输入要检索的文本文件名，打开相应文件；(2).输入要检索统计的单词；(3).循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数，其描述如下：While(不是文件结束){读入一行并到串中；求出串长度；模式匹配函数计数；}(4).关闭文件，输出统计结果。检索单词在文本文件中的行号，次数及其位置的实