太原理工大学软件工程课程设计汇本实验.doc

《太原理工大学软件工程课程设计汇本实验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、文本文件单词的检索与计数专业：软件工程班级：1227班：王晓春学号：2012005774同组人：王晓春闫瑞娟泽磊组长：王晓春完成日期：2014.6.25一．【问题描述】串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串变量与其他变量（如整型、实型等）一样，可以进行各种运算。然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实现串的处理，就必须熟悉串的存储结构及其基本运算。本课程设计的目的就是熟悉串类型的实现方法和文本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理技术。本课程设计分两步

2、：首先，设计出串定位算法（即模式匹配算法）及其实现；然后，再利用串定位算法设计文本文件的检索及单词的计数等操作。二．【设计需求及分析】1.设计要求1.1串模式匹配算法的设计要求在串的基本操作中，在主串中查找模式串的模式匹配算法——即求子串位置的函数Index(S,T)，是文本处理中最常用、最重要的操作之一。所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字

3、符位置开始比较，而且需要从主串的任一给定位置检索匹配字符串，所以，首先要给出两个算法：1．标准的朴素模式匹配算法2．给定位置的匹配算法1.2文本文件单词的检索与计数的设计要求要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及

4、在该行中的相应位置。1．建立文本文件2．给定单词的计数3．检索单词出现在文本文件中的行号、次数及其位置4．主控菜单程序的结构2.概要设计示例如下：2.6算法设计朴素模式匹配算法该算法的基本思想是：设有三个指针——i,j,k，用i指示主串S每次开始比较的位置；指针j,k分别指示主串S和模式串T中当前正在等待比较的字符位置；一开始从主串S的第一个字符（i=0;j=1）和模式T的第一个字符（k=0）比较，若相等，则继续逐个比较后续字符（j++,k++）。否则从主串的下一个字符（i++）起再重新和模式串（j=0）的字符开始比较。依此类推，直到模式T中的所有字符都比较完，而且一直相等，则称匹配成功，并

5、返回位置i；否则返回-1，表示匹配失败。顺序串的模式匹配算法如下：intindex(SStringS,SStringT){//求子串T在主串S中首次出现的位置inti,j,k,m,n;m=T.length;//模式串长度赋mn=S.length;//目标串长度赋nfor(i=0;i<=n-m;i++){j=0;k=i;//目标串起始位置i送入kwhile(j<=m&&s.ch[k]==t.ch[j]){k++;j++;}//继续下一个字符的比较if(j==m)//若相等，则说明找到匹配的子串，返回匹配位置i，//否则从下一个位置重新开始比较returni;}//endforreturn-1;

6、}//endIndex给定位置的串匹配算法该算法要求从串S1（为顺序存储结构）中第k个字符起，求出首次与字符串S2相同的子串的起始位置。该算法与上面介绍的模式匹配算法类似，只不过上述算法的要从主串的第一个字符开始，该算法是上述算法的另一种思路：从第k个元素开始扫描S1，当其元素值与S2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到S2结束为止。若都相同，则返回当前位置值；否则继续上述过程，直至S1扫描完为止，其实现算法如下：IntPartPosition(SStringS1,SStringS2,intk){inti,j;i=k-1;//扫描s1的下标，因为c中数组下标是从0开

7、始，串中序号相差1j=0;//扫描s2的开始下标while(i=s2.length)returni-s2.length;//表示s1中存在s2，返回