单词的检索与计数教材

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

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

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

4、S,T) ，是文本 数据结构课程设计报告 处理中最常用、最重要的操作之一。 所谓子串的定位就是求子串在主串中首次出现的位置， 又称为模式匹配或串匹配。 模式匹配的算法很多， 在这里只要求用最简单的朴素模式匹配算法。该算法的基本思路是将给定子串与主串从第一个字符开始比 较，找到首次与子串完全匹配的子串为止，并记住该位置。但为了实现统计子串出现的个数，不仅需要从主 串的第一个字符位置开始比较，而且需要从主串的任一给定位置检索匹配字符串，所以，首先要给出两个算 法： 1标准的朴素模式匹配算法 2给定位置的匹配算法 3.2 文本文件单词的检索与计数的设计要求 要求编程建立一个文本文件，每个单词不包含空

5、格且不跨行，单词由字符序列构成且区分大小写；统计 给定单词在文本文件中出现的总次数； 检索输出某个单词出现在文本中的行号、 在该行中出现的次数以及位 置。 该设计要求可分为三个部分实现：其一，建立文本文件，文件名由用户用键盘输入；其二，给定单词的 计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数；其三，检索给定单词，输入一个单 词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。 1建立文本文件 2给定单词的计数 3检索单词出现在文本文件中的行号、次数及其位置 4主控菜单程序的结构 二 概要设计 2 1 建立文本文件 定义一个串变量 ，定义文本文件， 输入文件

6、名，打开该文件 ， 循环读入文本行，写入文本文件， 关闭文 件。 2 2 给定单词的计数 逐行扫描文本文件。匹配一个，计数器加 1，直到整个文件扫描结束；然后输出单词的次数 23 检索单词出现在文本文件中的行号、次数及其位置 逐行扫描文本文件。扫描一个单词，单词数加1，匹配一个， 计数器加 1，输出该单词数，行数到底 ，以此， 行数加 1，单词数清零，直到整个文件扫描结束；然后输出单词的次数，行号，第几个单词。 三 详细设计 朴素模式匹配算法 该算法的基本思想是：设有三个指针 i,j,k ，用 i 指示主串 S 每次开始比较的位置；指针 j,k 分别指示 主串 S和模式串 T 中当前正在等待比

7、较的字符位置；一开始从主串 S的第一个字符（ i=0;j=1 ）和模式 T 的 第一个字符（ k=0）比较，若相等，则继续逐个比较后续字符（j+,k+ ）。否则从主串的下一个字符（ i+ ） 起再重新和模式串（ j=0 ）的字符开始比较。依此类推，直到模式T 中的所有字符都比较完，而且一直相等， 数据结构课程设计报告 则称匹配成功，并返回位置 i ；否则返回 -1，表示匹配失败。 顺序串的模式匹配算法如下： int index(SString S, SString T) /求子串 T 在主串 S 中首次出现的位置 int i,j,k,m,n; m=T.length; /模式串长度赋 m n=S

8、.length; / 目标串长度赋 n for (i=0; i=n-m; i+) j=0; k=i; / 目标串起始位置 i 送入 k while (j=m j+; / 继续下一个字符的比较 if (j=m) / 若相等，则说明找到匹配的子串，返回匹配位置 /否则从下一个位置重新开始比较 return i; /endfor return -1; /endIndex 给定位置的串匹配算法 该算法要求从串 S1(为顺序存储结构) 中第 k 个字符起， 求出首次与字符串 S2 相同的子串的起始位置。 该算法与上面介绍的模式匹配算法类似， 只不过上述算法的要求是从主串的第一个字符开始， 该算法是 上述

9、算法的另一种思路：从第 k 个元素开始扫描 S1，当其元素值与 S2 的第一个元素的值相同时，判定它们 之后的元素值是否依次相同，直到 S2 结束为止。若都相同，则返回当前位置值；否则继续上述过程，直至 S1 扫描完为止，其实现算法如下： Int PartPosition(SString S1, SString S2, int k) int i, j; i=k-1; /扫描 s1的下标，因为 c 中数组下标是从 0 开始，串中序号相差 1 j=0;/扫描 s2 的开始下标 while (is1.length /表示 s1 中存在 s2，返回其起始位置 else return -1;/ 表示 s

10、1 中不存在 s2， 返回 -1 / 函数结束 说明：以上两个算法可统一为一个算法，即在子串定位算法Index(S,T) 的参数中增加一个起始位置参数 即可。 数据结构课程设计报告 建立文本文件 建立文件的实现思路是： （1）定义一个串变量； （2）定义文本文件； （3）输入文件名，打开该文件； （4）循环读入文本行，写入文本文件，其过程如下： While （ 不是文件输入结束 ） 读入一文本行至串变量； 串变量写入文件； 输入是否结束输入标志； （ 5）关闭文件。 给定单词的计数 该功能需要用到前一节中设计的模式匹配算法，逐行扫描文本文件。匹配一个，计数器加1，直到整个 文件扫描结束；然后输

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

12、不是文件结束 ） 读入一行到指定串中； 求出串长度； 行单词计数器置 0； 调用模式匹配函数匹配单词定位、该行匹配单词计数； 行号计数器加 1； If （ 行单词计数器 !=0） 输出行号、该行有匹配单词的个数以及相应的位置； 数据结构课程设计报告 运行主控程序 主控菜单程序的结构要求内容如下： （ 1）头文件包含； （2）菜单选项包括： 1建立文件 2单词计数 3单词定位 4退出程序 （3）选择 14 执行相应的操作，其他字符为非法。 四 调试分析与测试结果 4.1 未输入文件前的页面 4.2 输入文本文件 5 数据结构课程设计报告 4.3 文本单词汇总 4.4 单词定位 6 数据结构课程设

13、计报告 五 用户手册 该软件界面简洁，操作简单，运行程序后根据提示就可完成相关操作。 六 附录（源程序清单） #include #include #include #define LIST_INIT_SIZE 500 #define LISTINCREMENT 10 #define FILE_NAME_LEN 20 #define WORD_LEN 20 #define MaxStrSize 256 #define llength 110 #define MaxStr 258 #define WORD 21 /* 线性表存储空间的初始分配量 */ /* 线性表存储空间的分配增量 */ /* 文

14、件名长度 */ /* 单词长度 */ /* 规定一行有 110 个字节 */ typedef struct char chMaxStr; int length; /* ch 是一个可容纳 256 个字符的字符数组 */ 7 数据结构课程设计报告 string; /* 定义顺序串类型 */ typedef struct char wordWORD; /* 存储单词，不超过 20个字符 */ int count; /* 单词出现的次数 */ elem_type; typedef struct elem_type *elem; /* 存储空间基址 */ int length; /* 当前长度 */

15、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+) /* 当前单词与加入的单词相同，直接统计，不做插入 */ if (strcmp(eti.word, word) = 0) eti.count+; return 0; if

16、(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); 数据结构课程设计报告 sq-length+; strcpy(eti.word, word); eti.count = 1; return 0; int sqlist_count(sqlist *sq, elem_type *et) int i

17、, 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; /* 输入结束标志初值 */ while(yn=n|yn=N) printf( gets(w.word); gets(w.word); s.length=strlen

18、(w.word); fwrite( fprintf(fp,%c,10); printf( 请输入一行文本： ); /* 是输入换行 */ 结束输入吗？ y or n ： );yn=getchar(); fclose(fp); printf( /* 关闭文件 */ 建立文件结束 !n); return 0; int substrsum() 数据结构课程设计报告 char 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_SI

19、ZE; sqlist sq; sqlist_init( 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( fclose(fp); printf( 单词个数 n); for (i = 0; i =0;w-) if(eti.wordw90 for(w=0;w%s的单词总数为 %d个 n,file_name,j); printf(n%

20、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 else return -1;/* 表示 s1 中不存在 s2 ，返回 -1 */ /*表示 s1 中存在 s2 ，返回其起始位置 */ /* 函数结束 */ int substrcount() FILE *fp

21、; 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); while(!feof(fp) memset(s.ch,0,110); fgets(s.ch,110,fp); s.length=strlen(s.ch); k=0; /* 初始化开始检索位置 */ 11 数据结构课程设计报告 while(ks.leng

22、th-1) /* j=partposition(s,t,k); if(j0 ) break; 检索整个主串 S */ /* 调用串匹配函数 */ else i+; /* 单词计数器加 1 */ k=j+t.length; /* 继续下一字串的检索 */ printf(n单词%s在文本文件 %s中共出现 %d次n,t.ch,fname,i); return 0; /* 统计单词出现的个数 */ int substrint() FILE *fp; string s,t; /* 定义两个串变量 */ char fname10; int i,j,k,l,m; int wz20; /* 存放一行中字串匹

23、配的多个位置 */ 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(s.ch,0,110); fgets(s.ch,110,fp); s.length=strlen(s.ch); l+;/*行计数器自增 1 */ k=0;/*初始化开始检索位置 */ i=0;/*初始化单词计数器 */ while(k

24、s.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 个字节为一行 nn); return 0; /* 检索单词出现在文本文件中的行号、次数及其位置 */ int substrio() int substrcount(),substrint(); char t; /while(1) / prin

25、tf(=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, switch(t) case a: substrcount();break; case b: substrint();break; default: return 0; / return 0; int main(void) 13 数据结构课程设计报告 int creat_text_file(),substrsum(),