课程设计
--------数据结构课程设计报告
姓名： 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，直到整个文件扫描结束，然后输出单词出现的次数。
串是非数值处理中的主要对象，在串的基本操作中，模式匹配或串匹配就是求子串在主串中首次出现的位置。朴素模式匹配算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与主串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符开始比较，而且要从主串的任何位置检索匹配字符串。
其实现过程如下：
(1).输入要检索的文本文件名，打开相应文件； (2).输入要检索统计的单词；
(3).循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数，其描述如下： While(不是文件结束) { 读入一行并到串中； 求出串长度；
模式匹配函数计数； }
(4).关闭文件，输出统计结果。
?检索单词在文本文件中的行号，次数及其位置的实现思路是：
(1).输入要检索的文本文件名，打开相应的文件； (2).输入要检索统计的单词； (3).行计数器置初值0； While(不是文件结束) {
读入一行到指定串中； 求出串长度； 行单词计数器0；
调用模式匹配函数匹配单词定位，该行匹配单词计数： 行号计数器加一；
If（行单词计数器！=0）输出行号，该行有匹配单词的个数以及相应的位置 }
2.数据结构
串的定长顺序存储表示：
#define MAXSTRLEN 255 //用户可在255以内定义最大串长 Typedef unsigned char SString [MAXSTRLEN+1];
求子串SubString(&sub,S,pos,len) 过程即为复制字符序列的过程，将串S中第pos个字符开始长度为len的字符序列复制到串Sub中去，当参数非法时，返回ERROR
Status SubString(Sstring &Sub , Sstring S , int pos , int len) //用Sub返回串s第pos个字符起长度为len的子串 0<=len<=StrLength(S)-pos+1
If(pos=0 || lenS[0]-pos+1) return ERROR Sub[l...len]=S[pos....pos +len +1]; Sub[0]=len; Return OK;
}//end of SubString;
由此可见，在顺序存储结构中，实现串的原操作为“字符序列的复制”，操作时间复杂度基于复制的字符序列的长度。