单词的检索与计数.docx

《单词的检索与计数.docx》由会员分享，可在线阅读，更多相关《单词的检索与计数.docx（19页珍藏版）》请在三一办公上搜索。

1、单词的检索与计数 内江师范学院计算机科学学院 数据结构课程设计报告 课题名称： 文本文件单词的检索与计数 姓 名： 学 号： 专业班级： 软 件 工 程 系 ： 计 算 机 科 学 学 院 设计时间： 20XX 年 X 月 X日 设计地点： 成 绩： 数据结构课程设计报告 1课程设计目的 (1).训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 (2).初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； (3).提高综合运用所学的理论知识和方法独立分析和解决问题的能力； (4).训练用系统的观点和软件开发一般规范进行软件开

2、发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 2课程设计任务与要求： 文本文件单词的检索与计数软件 任务：编写一个文本文件单词的检索与计数软件, 程序设计要求： 1）建立文本文件，文件名由用户键盘输入 2）给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数 要求： (1)、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标

3、准函数，加大代码的重用率。 (2)、设计的题目要求达到一定工作量，并具有一定的深度和难度。 (3)、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释; (4)、每位同学需提交可独立运行的程序； (5)、每位同学需独立提交设计报告书，要求编排格式统一、规范、内容充实，不少于8页； (6)、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书 一 需求分析 3.1 串模式匹配算法的设计要求 在串的基本操作中，在主串中查找模式串的模式匹配算法即求子串位置的函数Index(S,T)，是文本1 数据结构课程设计报告 处理中最常用、最重要的操作之一。 所谓子串的定位就是

4、求子串在主串中首次出现的位置，又称为模式匹配或串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给定子串与主串从第一个字符开始比较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主串的第一个字符位置开始比较，而且需要从主串的任一给定位置检索匹配字符串，所以，首先要给出两个算法： 1标准的朴素模式匹配算法 2给定位置的匹配算法 3.2 文本文件单词的检索与计数的设计要求 要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写；统计给定单词在文本文件中出现的总次数；检索输出某个单词出现在文

5、本中的行号、在该行中出现的次数以及位置。 该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。 1建立文本文件 2给定单词的计数 3检索单词出现在文本文件中的行号、次数及其位置 4主控菜单程序的结构 二 概要设计 21建立文本文件 定义一个串变量 ，定义文本文件， 输入文件名，打开该文件 ， 循环读入文本行，写入文本文件， 关闭文件 。 22给定单词的计数 逐行扫描文本文件。匹配一个，计数器加

6、1，直到整个文件扫描结束；然后输出单词的次数 23检索单词出现在文本文件中的行号、次数及其位置 逐行扫描文本文件。扫描一个单词，单词数加1，匹配一个，计数器加1，输出该单词数，行数到底 ，以此，行数加1，单词数清零，直到整个文件扫描结束；然后输出单词的次数，行号，第几个单词。 三 详细设计 朴素模式匹配算法 该算法的基本思想是：设有三个指针i,j,k，用i指示主串S每次开始比较的位置；指针j,k分别指示主串S和模式串T中当前正在等待比较的字符位置；一开始从主串S的第一个字符和模式T的第一个字符比较，若相等，则继续逐个比较后续字符。否则从主串的下一个字符起再重新和模式串的字符开始比较。依此类推，

7、直到模式T中的所有字符都比较完，而且一直相等，2 数据结构课程设计报告 则称匹配成功，并返回位置i；否则返回-1，表示匹配失败。 顺序串的模式匹配算法如下： int index(SString S, SString T) /求子串T在主串S中首次出现的位置 int i,j,k,m,n; m=T.length; /模式串长度赋m n=S.length; /目标串长度赋n for (i=0; i=n-m; i+) j=0; k=i; / 目标串起始位置i送入k while (j=m & s.chk=t.chj) k+; j+; /继续下一个字符的比较 if (j=m) /若相等，则说明找到匹配的子

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

9、, SString S2, int k) int i, j; i=k-1; /扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1 j=0; /扫描s2的开始下标 while (is1.length & j=s2.length) return i- s2.length; /表示s1中存在s2，返回其起始位置 else return -1; /表示s1中不存在s2， 返回-1 /函数结束 说明：以上两个算法可统一为一个算法，即在子串定位算法Index(S,T)的参数中增加一个起始位置参数即可。 3 数据结构课程设计报告 建立文本文件 建立文件的实现思路是： 定义一个串变量； 定义文本文件；

10、 输入文件名，打开该文件； 循环读入文本行，写入文本文件，其过程如下： While ( 不是文件输入结束) 读入一文本行至串变量； 串变量写入文件； 输入是否结束输入标志； 关闭文件。 给定单词的计数 该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个文件扫描结束；然后输出单词出现的次数。 其实现过程如下： 输入要检索的文本文件名，打开相应的文件； 输入要检索统计的单词； 循环读文本文件，读入一行，将其送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。具体描述如下： While (不是文件结束) 读入一行并到串中； 求出串长度； 模式匹配函数

11、计数； 关闭文件，输出统计结果。 检索单词出现在文本文件中的行号、次数及其位置 这个设计要求与上一个类似，但要相对复杂一些。其实现过程描述如下： 输入要检索的文本文件名，打开相应的文件； 输入要检索统计的单词； 行计数器置初值0； while (不是文件结束) 读入一行到指定串中； 求出串长度； 行单词计数器置0； 调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加1； If (行单词计数器!=0) 输出行号、该行有匹配单词的个数以及相应的位置； 4 数据结构课程设计报告 运行主控程序 主控菜单程序的结构要求内容如下： 头文件包含； 菜单选项包括： 1建立文件 2单词计数 3单词定

12、位 4退出程序 选择14执行相应的操作，其他字符为非法。 四 调试分析与测试结果 4.1未输入文件前的页面 4.2输入文本文件 5 数据结构课程设计报告 4.3文本单词汇总 4.4 单词定位 6 数据结构课程设计报告 五 用户手册 该软件界面简洁，操作简单，运行程序后根据提示就可完成相关操作。 六 附录 #include #include #include #define LIST_INIT_SIZE 500 /*线性表存储空间的初始分配量*/ #define LISTINCREMENT 10 /*线性表存储空间的分配增量*/ #define FILE_NAME_LEN 20 /*文件名长度*

13、/ #define WORD_LEN 20 /*单词长度*/ #define MaxStrSize 256 #define llength 110 /*规定一行有110个字节*/ #define MaxStr 258 #define WORD 21 typedef struct char chMaxStr; /* ch是一个可容纳256个字符的字符数组 */ int length; 7 数据结构课程设计报告 string; /* 定义顺序串类型 */ typedef struct char wordWORD; /*存储单词，不超过20个字符*/ int count; /*单词出现的次数*/ e

14、lem_type; typedef struct elem_type *elem; /*存储空间基址*/ int length; /*当前长度*/ int listsize; /*当前分配的存储容量*/ sqlist; int sqlist_init(sqlist *sq, elem_type *et) sq-elem = et; sq-length = 0; return 0; int sqlist_add(sqlist *sq, elem_type *et, char *word) int i; int j; for (i = 0; i length; i+) /*当前单词与加入的单词相同

15、，直接统计，不做插入 */ if (strcmp(eti.word, word) = 0) eti.count+; return 0; if (strcmp(eti.word, word) 0) break; if (sq-length = LIST_INIT_SIZE) printf(空间不足，单词%s插入失败n, word); return 0; for (j = sq-length; j i; j-) memcpy(et+j, et+j-1, sizeof(elem_type); 8 数据结构课程设计报告 sq-length+; strcpy(eti.word, word); eti.c

16、ount = 1; return 0; int sqlist_count(sqlist *sq, elem_type *et) int i, j = 0; for(i=0;ilength;i+) j=j+eti.count; return j; int 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; /* 输入结束标志初值 */ whi

17、le(yn=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); return 0; int substrsum 9 数据结构课程设计报告 char file_nameFILE_NAME_LEN + 1; char wordWOR

18、D_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); return 0; while (fscanf(fp, %s, word) != EOF) sqlist_add(&sq, et, word); fclose(fp); printf

19、(单词个数n); for (i = 0; i =0;w-) if(eti.wordw90&eti.wordw122) eti.wordw= ; for(w=0;w%s的单词总数为%d个n,file_name,j); printf(n%s的非单词个数为%d种n,file_name,q); printf(n); return 0; int partposition (string s1,string s2,int k) int i,j; i=k-1; /* 扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1 */ j=0; /* 扫描s2的开始下标 */ while(is1.length

20、& j=s2.length) return i-s2.length; else return -1; /* 表示s1中不存在s2，返回-1 */ /* 表示s1中存在s2，返回其起始位置 */ /* 函数结束 */ int 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);

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

22、rn 0; /* 统计单词出现的个数 */ int 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.ch); l=0; /* 行计数器置0 */ while(!feof(fp) /* 扫描整个文本文件 */ memset(

23、s.ch,0,110); fgets(s.ch,110,fp); s.length=strlen(s.ch); l+; /* 行计数器自增1 */ k=0; /* 初始化开始检索位置 */ i=0; /* 初始化单词计数器 */ while(ks.length-1) /* 检索整个主串S */ j=partposition(s,t,k); /* 调用串匹配函数 */ if(j0) printf(行号：%d,次数：%d,起始位置分别为：,l,i); for(m=1;m=i;m+) printf(第%4d个字符,wzm+1); printf(n); printf(n本软件自定义110个字节为一行n

24、n); return 0; /* 检索单词出现在文本文件中的行号、次数及其位置 */ int substrio int substrcount,substrint; char t; /while(1) / printf(=n); printf(|文本文件单词字串的定位统计及定位|n); printf(|=|n); printf(| a. 单词出现次数 |n); printf(| |n); printf(| |n); printf(| b. 单词出现位置 |n); printf(| |n); printf(=n); printf(请输入a或b:); scanf(%c%*c,&t); switch

25、(t) case a: substrcount;break; case b: substrint;break; default: return 0; / return 0; int main(void) 13 数据结构课程设计报告 int creat_text_file,substrsum,substrio; int a; int t = 1; while(t) printf(*n); printf(*文本文件单词的检索与计数 *n); printf(*n); printf(*1.建立文本文档 *n); printf(*2.文本单词汇总 *n); printf(*3.单词定位 *n); pri

26、ntf(*4.退出 *n); printf(*n); printf(请选择(14):); scanf(%d%*c,&a); switch(a) case 1: creat_text_file;break; case 2: substrsum;break; case 3: substrio;break; case 4: return 0; default:printf(选择错误，重新选 n); return 0; 七 课程设计心得 经过几周的奋斗，这次数据结构的课程设计终于做完了。通过这次设计我也着实又感受了一次编程的乐趣，从中也学到了不少知识。 感受最深的一点是：以前用编程，只是注重如何编写函

27、数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。现在编程感觉完全不同了。在编写一个程序之前，先对这个课程设计进行了一下分析，将每个要求都花了一下算法流程图，使得自己的思路更加的清晰了 。 然后进行编程，不断的在电脑上调试程序，终于完成了此次的课程设计。 另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。 这次试验也让我看到了自己的不足，还是不太用模板类。还有许多关于C语言的一些比较具体的东西还不太懂，需要进一步了解。这次试验还让我意识到只有不断的在电脑上调试程序，自己的水平才能得到提高。 我会继续我们的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。 14