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

课程设计 --------数据结构课程设计报告 姓名： liuj 学号： 14 专业班级：计算机113班 日期：2013.01.28 目录 单词检索统计程序 一．需求分析 需求分析----------------------------------------------------------------------------------------------------------1 二．程序设计目标 1.设计思路----------------------------------------------------------------------------------------------------------1 2.数据结构----------------------------------------------------------------------------------------------------------4 概要设计 1.概要分析-----------------------------------------------------------------------------------------------------------5 2.函数流程图-------------------------------------------------------------------------------------------------------6 3.详细设计-----------------------------------------------------------------------------------------------------------7 四．源程序代码 1.源程序C++实现代码-----------------------------------------------------------------------------------------8 五．调试结果及运行结果 1.运行结果截图--------------------------------------------------------------------------------------------------13 六．程序小结 1.心得体会---------------------------------------------------------------------------------------------------------14 七．参考书籍 1.参考书籍-------------------------------------------------------------------------------------------14 一．需求分析 给定一个文本文件，要求统计给定单词在文本中出现的总次数，并检索输出某个单词出现在文本中的行号，在该行中出现的次数以及位置 单词计数功能用到模式匹配算法，而KMP算法是对一般模式匹配算法的改进，其改进过程在于：每当一趟匹配过程出现字符比较不相等时，不需回溯i指针，而是利用已经得到的部分匹配结果将模式串向右滑动一段距离后，继续进行比较。滑动的这段距离用到函数next[ ]，KMP算法的最大特点就是不需回溯指针，整个匹配过程中，无需主串从头至尾扫描一遍。 二．程序设计目标 1.设计思路 此程序的设计要求可以分为三部分来实现：其一，建立一个文本文件，文件名有用户用键盘输入；其二，给定单词计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定的单词，输入一个单词，检索并输出该单词所在的行号，该行中出现的次数以及在该行中的相应位置。 ?给定单词计数的实现思路： 该功能需要用到模式匹配算法，逐行扫描文本文件，匹配一个，计数器加1，直到整个文件扫描结束，然后输出单词出现的次数。 串是非数值处理中的主要对象，在串的基本操作中，模式匹配或串匹配就是求子串在主串中首次出现的位置。朴素模式匹配算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与主串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符开始比较，