文本文件单词的检索与计数

1、 程序设计课程设计 报 告 学 院：软件学院 专业班级：软件 班 学 号： 姓 名： 指导教师： 时 间： 2012年 6月29日文本文件单词的检索与计数专业：软件工程 班级： 1.1【问题描述】串是非数值处理中的主要对象，如在信息检索、文本编辑、符号处理等许多领域，得到越来越广泛的应用。在高级语言中也引入了串数据类型概念，并且串变量与其他变量如整型、实型等一样，可以进行各种运算。然而，在各种不同类型的应用中，所处理的串有不同的特点，要想有效地实现串的处理，就必须熟悉串的存储结构及其根本运算。本课程设计的目的就是熟悉串类型的实现方法和文本模式匹配方法，熟悉如何利用模式匹配算法实现一般的文本处理

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

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

4、次数以及在该行中的相应位置。1建立文本文件2给定单词的计数3检索单词出现在文本文件中的行号、次数及其位置4主控菜单程序的结构3【设计功能的实现】用C或C+语言描述详细设计朴素模式匹配算法该算法的根本思想是：设有三个指针i,j,k，用i指示主串S每次开始比拟的位置；指针j,k分别指示主串S和模式串T中当前正在等待比拟的字符位置；一开始从主串S的第一个字符i=0;j=1和模式T的第一个字符k=0比拟，假设相等，那么继续逐个比拟后续字符j+,k+。否那么从主串的下一个字符i+起再重新和模式串j=0的字符开始比拟。依此类推，直到模式T中的所有字符都比拟完，而且一直相等，那么称匹配成功，并返回位置i；否

5、那么返回-1，表示匹配失败。顺序串的模式匹配算法如下：int index(SString S, SString T) /求子串T在主串S中首次出现的位置int i,j,k,m,n;m=T.length; /模式串长度赋mn=S.length; /目标串长度赋nfor (i=0; i<=n-m; i+) j=0; k=i; / 目标串起始位置i送入k while (j<=m && s.chk=t.chj) k+; j+; /继续下一个字符的比拟 if (j=m) /假设相等，那么说明找到匹配的子串，返回匹配位置i，/否那么从下一个位置重新开始比拟 return i;

6、/endforreturn -1; /endIndex给定位置的串匹配算法该算法要求从串S1为顺序存储结构中第k个字符起，求出首次与字符串S2相同的子串的起始位置。该算法与上面介绍的模式匹配算法类似，只不过上述算法的要求是从主串的第一个字符开始，该算法是上述算法的另一种思路：从第k个元素开始扫描S1，当其元素值与S2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到S2结束为止。假设都相同，那么返回当前位置值；否那么继续上述过程，直至S1扫描完为止，其实现算法如下：Int PartPosition(SString S1, SString S2, int k)int i, j;i=k

7、-1; /扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1j=0; /扫描s2的开始下标while (i<s1.length && j<s2.length)if (s1.chi=s2.chj) i+; j+; /继续使下标移向下一个字符位置else i=i-j+1; j=0; /使i下标回溯到原位置的下一个位置，使j指向s2的第一个字符，再重新比拟if (j>=s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置else return -1; /表示s1中不存在s2， 返回-1 /函数结束说明：以上两个

8、算法可统一为一个算法，即在子串定位算法Index(S,T)的参数中增加一个起始位置参数即可。建立文本文件建立文件的实现思路是：1定义一个串变量；2定义文本文件；3输入文件名，翻开该文件；4循环读入文本行，写入文本文件，其过程如下： While ( 不是文件输入结束) 读入一文本行至串变量；串变量写入文件；输入是否结束输入标志；5关闭文件。给定单词的计数该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个文件扫描结束；然后输出单词出现的次数。其实现过程如下：1输入要检索的文本文件名，翻开相应的文件；2输入要检索统计的单词；3循环读文本文件，读入一行

9、，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。具体描述如下：While (不是文件结束) 读入一行并到串中； 求出串长度； 模式匹配函数计数；4关闭文件，输出统计结果。 检索单词出现在文本文件中的行号、次数及其位置这个设计要求与上一个类似，但要相对复杂一些。其实现过程描述如下：1输入要检索的文本文件名，翻开相应的文件；2输入要检索统计的单词；3行计数器置初值0；4while (不是文件结束) 读入一行到指定串中； 求出串长度； 行单词计数器置0； 调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加1； If (行单词计数器!=0) 输出行号、该行有匹配单词的个

10、数以及相应的位置；运行主控程序主控菜单程序的结构要求内容如下：1头文件包含；2菜单项选择项包括： 1建立文件 2单词计数 3单词定位 4退出程序3选择14执行相应的操作，其他字符为非法。程序代码：#include <stdio.h>#include <stdlib.h>>#define LIST_INIT_SIZE 500 /*线性表存储空间的初始分配量*/#define LISTINCREMENT 10 /*线性表存储空间的分配增量*/#define FILE_NAME_LEN 20 /*文件名长度*/#define WORD_LEN 20 /*单词长度*/#d

11、efine MaxStrSize 256#define llength 110 /*规定一行有110个字节*/typedef struct char chMaxStr; /* ch是一个可容纳256个字符的字符数组 */ int length; string;/* 定义顺序串类型 */typedef struct char wordWORD; /*存储单词，不超过20个字符*/ int count; /*单词出现的次数*/ elem_type;typedef struct elem_type *elem; /*存储空间基址*/ int length; /*当前长度*/ int listsize

12、; /*当前分配的存储容量*/ sqlist;void sqlist_init(sqlist *sq, elem_type *et) sq->elem = et; sq->length = 0;void sqlist_add(sqlist *sq, elem_type *et, char *word) int i; int j; for (i = 0; i < sq->length; i+) /*当前单词与参加的单词相同，直接统计，不做插入 */ if (strcmp(eti.word, word) = 0) eti.count+; return ; if (strcm

13、p(eti.word, word) > 0) break; if (sq->length = LIST_INIT_SIZE) printf("空间缺乏，单词%s插入失败n", word); return; for (j = sq->length; j > i; j-) memcpy(et+j, et+j-1, sizeof(elem_type); sq->length+; strcpy(eti.word, word); eti.count = 1;int sqlist_count(sqlist *sq, elem_type *et) int i

14、; int j=0; for(i=0;i<sq->length;i+) j=j+eti.count; return j;void creat_text_file() elem_type w; sqlist s; char file_nameFILE_NAME_LEN + 1,yn; FILE *fp; printf("输入要建立的文件名："); scanf("%s",file_name); fp=fopen(file_name,"w"); yn='n'/* 输入结束标志初值 */ while(yn='

15、;n'|yn='N') printf("请输入一行文本："); gets(w.word); gets(w.word); s.length=strlen(w.word); fwrite(&w,s.length,1,fp); fprintf(fp,"%c",10);/* 是输入换行 */ printf("结束输入吗？y or n ：");yn=getchar(); fclose(fp);/* 关闭文件 */ printf("建立文件结束!n"); void substrsum() cha

16、r file_nameFILE_NAME_LEN + 1; char wordWORD_LEN+1; FILE *fp; int i; int j,q=0; int w,x,y=0; elem_type etLIST_INIT_SIZE; sqlist sq; sqlist_init(&sq, et); printf("请输入文件名："); scanf("%s", file_name); fp = fopen(file_name, "r"); if (fp = NULL) printf("翻开文件失败!n"

17、); return; while (fscanf(fp, "%s", word) != EOF) sqlist_add(&sq, et, word); fclose(fp); printf(">>>>>>>>>>>>>>>>单词<<<>>>>个数<<<<<<<<<<<n"); for (i = 0; i < sq.length; i+) x

18、=strlen(eti.word); for(w=x-1;w>=0;w-) if(eti.wordw<65|(eti.wordw>90&&eti.wordw<97)|eti.wordw>122) eti.wordw=' ' for(w=0;w<x;w+) if (eti.wordw=' ') y+; if(y=x) eti.count=0; y=0; else y=0; if(eti.count!=0) printf("%20s%10dn", eti.word, eti.count); el

19、se q+; j=sqlist_count(&sq, et); printf("n>>>>>>>>>>>>>>>>>>%s的单词总数为%d个n",file_name,j); printf("n>>>>>>>>>>>>>>>>>>%s的非单词个数为%d种n",file_name,q); printf("n"); in

20、t partposition (string s1,string s2,int k) int i,j; i=k-1; /* 扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1 */ j=0;/* 扫描s2的开始下标 */ while(i<s1.length && j<s2.length) if(s1.chi=s2.chj) i+;j+; /* 继续使下标移向下一个字符位置 */ else i=i-j+1; j=0; if (j>=s2.length) return i-s2.length; else return -1;/* 表示s1中不存在s2，返回

21、-1 */ /* 表示s1中存在s2，返回其起始位置 */ /* 函数结束 */ void substrcount() FILE *fp; string s,t;/* 定义两个串变量 */ char fname10; int i=0,j,k; printf("输入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r"); printf("输入要统计计数的单词："); scanf("%s",t.ch); t.length=strlen(t.ch); whil

22、e(!feof(fp) memset(s.ch,'0',110); fgets(s.ch,110,fp); s.length=strlen(s.ch); k=0; /* 初始化开始检索位置 */ while(k<s.length-1) /* 检索整个主串S */ j=partposition(s,t,k);/* 调用串匹配函数 */ if(j<0 ) break; else i+;/* 单词计数器加1 */ k=j+t.length;/* 继续下一字串的检索 */ printf("n单词%s在文本文件%s中共出现%d次n",t.ch,fname,

23、i); /* 统计单词出现的个数 */ void substrint() FILE *fp; string s,t; /* 定义两个串变量 */ char fname10; int i,j,k,l,m; int wz20; /* 存放一行中字串匹配的多个位置 */ printf("输入文本文件名："); scanf("%s",fname); fp=fopen(fname,"r"); printf("输入要检索的单词："); scanf("%s",t.ch); t.length=strlen(t.

24、ch); l=0; /* 行计数器置0 */ while(!feof(fp) /* 扫描整个文本文件 */ memset(s.ch,'0',110); fgets(s.ch,110,fp); s.length=strlen(s.ch); l+; /* 行计数器自增1 */ k=0;/* 初始化开始检索位置 */ i=0; /* 初始化单词计数器 */ while(k<s.length-1) /* 检索整个主串S */ j=partposition(s,t,k); /* 调用串匹配函数 */ if(j<0) break; else i+;/* 单词计数器加1 */ w

25、zi=j;/* 记录匹配单词位置 */ k=j+t.length;/* 继续下一字串检索 */ if(i>0) printf("行号：%d,次数：%d,位置分别为：",l,i); for(m=1;m<=i;m+) printf("第%4d个字符",wzm+1); printf("n"); printf("n本软件自定义110个字节为一行nn");/* 检索单词出现在文本文件中的行号、次数及其位置 */void substrio() void substrcount(),substrint(); char t; while(1) printf("=n"); printf("|文本文件单词字串的定位统计及定位|n"); printf("|=|n"); printf("| a. 单词出现次数 |n"); printf("| |n&quo