数据结构课程设计(3)

1、数据结构题专学文本文件单词的检索与计数课 程设计 报告书网络工程131007137学生姓名 指导教师 完成日期张钦昆王初阳2014/6/71.1题目与要求.错误!未定义书签。1.2知识点21.3输入输出分析21.4测试数据分析22概要设计.错误!未定义书签。2.1结构体类型及函数声明 错误!未定义书签。2.2主程序流程32.3模块流程说明43详细设计83.1数据类型实现83.2程序代码94调试分析174.1问题分析与回顾174.2算法时空分析 错误!未定义书签。4.3算法改进.错误!未定义书签。4.4经验和体会.错误!未定义书签。5测试结果.错误!未定义书签。参考文献241设计任务书错误!未定

2、义书签。24评分标准1设计任务书1.1 题目与要求题目：文本文件单词的检索与计数。要求：编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构 成且区分大小写；统计给定单词在文本文件中出现的总次数； 检索输出某个单词出现在 文本中的行号、在该行中出现的次数以及位置。 建立文本文件，文件名由用户用键盘输 入；给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数； 检索给定单词，输入一个单词，检索并输出该单词所在的行号、 该行中出现的次数以及 在该行中的相应位置。1.2 知识点串的应用、文件、结构体、指针、数组、函数、函数的调用、循环语句、选择语 句、输入输出控制、

3、自定义类型等。1.3输入输出分析（1）普通输入在文本文件的建立中，需要先定义串变量和文本文件，从而建立文本文件；根据实 际情况，将单词的长度定义为20，规定每行最多输入110个字符。（2）对话式输入为便于转换及比较，对话式输入采用字符数组进行存储.为保障程序的健壮性，同时限制对话式输入的格式，对于非法的会话式输入则提示用户操作失败的原因。（3）程序输出为了能让程序输出时更加美观，程序输出主要以整齐为主，使得输出的程序结果均 整齐输出。1.4测试数据分析在建立文本文件名时，要求键盘输入所建立的文本文件的名称， 如果所输入的文本 文件名称超过所给定的字符，将提示输入错误，请重新输入。在第二次输入文

4、本文件名称以供在此文本文件中查找所给定的单词，如果用户输入的文本文件名称与第一次不符或输入为空，系统将提示输入错误，请重新输入。在主控程序中，要求输入执行指令14,如果输入非14字符，系统将提示 输入错误，请重新选择概要设计2.1结构体类型及函数声明(1)结构体1. typedef struct/*定义顺序串类型 */char chMaxStrSize;in t le ngth; stri ng;2. typedef struct /*统计单词出现的次数*/char wordWORD_LEN;int count; elem_t ype;3. typ edef struct elem_t ype

5、 *elem; int len gth; int listsize; sqlist;/*存储空间基址*/*当前长度*/*当前分配的存储容量*/函数：1. 建立文件：void creat_text_file()2. 单词统计：void sqlist_add(sqlist *sq, elem_type *et, char *word)3. 文本文件中单词的总汇：void substrsum()4. 单词的定位：void substrcou nt()5. 主函数：int main()2.2主程序流程(1) 主程序调用模块图主程序利用switch()语句实现各个模块的调用，主函数调用如图1所示。主程序

6、根据不同数值调用函数I1建立文本文件2给 定 单 词 计 数13检索单词在文本中的位置图1主程序调用模块图2.3 模块流程说明主函数对各主要模块进行调用，各个主要模块又分别调用其他子模块。下面用简要 流程图对各主要模块进行说明。(1) 建立文本文件主模块如图2所示，建立文本文件模块。首先定义一个串变量，然后调用voidcreat_text_file()函数，定义文本文件，键盘输入文件名，打开该文件，循环读入文本行， 写入文本文件，最后关闭文件。图2建立文本文件模块(2) 给定单词的计数主模块如图3所示为给定单词计数程图。 其实现过程如下；首先输入要检索的文本文件 名，打开相应的文件，然后输入要

7、检索统计的单词，循环读文本文件，读入一行，将其 送入定义好的串中，并求该串的实际长度，调用串匹配函数进行计数。数最后关闭文件, 输出统计结果图3单词计数模块(3) 主控程序模块如图4为中控程序流程图。过程如下：输入头文件使用循环语句输出一下4个执行指令:1. 建立文本文档2. 文本单词汇总3. 给定单词定位4. 退出如输入非14的指令，系统将提示，输入错误请重新输入。 结束。图4主控程序模块3详细设计3.1数据类型实现结构体:1. typedef struct/*定义顺序串类型 */char chMaxStrSize;in t le ngth; stri ng;2. typedef struc

8、t /*统计单词出现的次数*/ char wordWORD_LEN;int count; elem_t ype;/*存储空间基址*/*当前长度*/*当前分配的存储容量*/3. typ edef struct elem_t ype *elem; int len gth; int listsize; sqlist;函数：1. 建立文件：void creat_text_file()2. 单词统计： void sqlist_add(sqlist *sq, elem_t ype *et, char *word)3. 文本文件中单词的总汇：void substrsum()4. 单词的定位：void sub

9、strcou nt()5. 主函数：int mai n()3.2 程序代码#i nclude <stdio.h>#i nclude <stdlib.h>#in clude <stri ng.h>#define LIST_INIT_SIZE 500/*线性表存储空间的初始分配量*/#define LISTINCREMENT 10/*线性表存储空间的分配增量*/*文件名长度*/20/*单词长度*/256/*规定一行有110个字节*/#define 20/*存储单词，不超过20个字符*/*单词出现的次数*/*存储空间基址*/*当前长度*/*当前分配的存储容量*/#

10、defi ne WORD_LEN#defi ne MaxStrSize#defi ne lien gth 110typ edef structchar chMaxStrSize; /* ch是一个可容纳256个字符的字符数组 */ in t le ngth; string;/*定义顺序串类型*/typ edef structchar wordWORD_LEN;int count; elem_t ype;typ edef structelem_t ype *elem;int len gth;int listsize; sqlist;void sqlist_i nit(sqlist *sq, el

11、em_t ype *et)sq->elem = et; sq->le ngth = 0;void sqlist_add(sqlist *sq, elem_t ype *et, char *word)int i;int j;for (i = 0; i < sq->le ngth; i+)*/*当前单词与加入的单词相同，直接统计，不做插入if (strc mp (eti.word, word) = 0)eti.co un t+;return;if (strc mp (eti.word, word) > 0) break;if (sq->le ngth = LIS

12、T_INIT_SIZE)printf("空间不足，单词%s插入失败n", word); return;for (j = sq->le ngth; j > i; j-)memc py (et+j, et+j-1, sizeof(elem_t yp e);sq->le ngth+;strc py(eti.word, word);eti.co unt = 1;int sqlist_co un t(sqlist *sq, elem_t ype *et)int i;int j=0;for(i=0;i<sq->le ngth;i+)j=j+eti.co u

13、nt;return j;void creat_text_file()elem_t ype w;sqlist s;char + 1,y n;FILE *fp;printf("输入要建立的文件名：");scan f("%s",);fp=fo pen (,"w");yn='n'/*输入结束标志初值*/while( yn='n '| yn二二N)printf("请输入一行文本：");gets(w.word);gets(w.word);s.le ngth=strle n( w.word);fw

14、rite(&w,s.le ngth,1,fp);fprintf(fp,"%c",10);/* 是输入换行 */printf("结束输入吗？ y or n : ");yn=getchar();/*关闭文件*/fclose(fp);printf("建立文件结束!n");void substrsumOchar EN + 1;char wordWORD_LEN+1;FILE *fp;int i;int j,q=O;int w,x,y=0;elem_t ype etLIST_INIT_SIZE; sqlist sq;sqlist_i n

15、it(&sq, et);printf("请输入文件名：");sca nf("%s",);fp = fopen (,"广)；if (fp = NULL)printf("打开文件失败!n"); return;while (fsca nf(fp, "%s", word) != EOF) sqlist_add(&sq, et, word); fclose(fp);个数n");printf(”单词for (i = 0; i < sq.le ngth; i+) x=strle n(et

16、i.word);for(w=x-1;w>=0;w-)if(eti.wordwv65|(eti.wordw>9 0&&eti.wordwv97)|eti.wordw>122) eti.wordw='' for(w=0;w<x;w+)if (eti.wordw=-')y+;if(y=x)eti.co un t=0;y=0;else y=0;if(eti.cou nt!=0)prin tf("%20s%10dn", eti.word, eti.cou nt); else q+;j=sqlist_co unt(&

17、;sq, et);printf("n%s的单词总数为d个n",);printf("n%s的非单词个数为%d种n",);prin tf("n");int partp ositi on (stri ng s1,stri ng s2,i nt k)int i,j;i=k-1; /*扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1 */ j=0;/*扫描s2的开始下标*/while(ivs1.le ngth && j<s2.le ngth)if(s1.chi=s2.chj)i+;j+; /*继续使下标移向下一个

18、字符位置elsei=i-j+1; j=0;if (j>=s2.le ngth)return i-s2.length; /*表示s1中存在s2,返回其起始位置 */ elsereturn -1; /*表示s1中不存在s2，返回-1 */*/*函数结束*/void substrco un t()FILE *fp;stri ng s,t;char fn ame10;int i=0,j,k;printf("输入文本文件名："); sca nf("%s",fname);fp=fo pen( fname,"r"); printf("

19、;输入要统计计数的单词："); sca nf("%s",t.ch);t.le ngth=strle n(t.ch); while(!feof(fp) memset(s.ch,'0',110); fgets(s.ch,110,fp);s.le ngth=strle n( s.ch);k=0;while(k<s.le ngth-1)/*定义两个串变量*/*初始化开始检索位置*/*检索整个主串S */*单词计数器加1 */*继续下一字串的检索*/j=partpo siti on( s,t,k); if(j<0 ) break;elsei+;k

20、=j+t.le ngth;/*调用串匹配函数*/printf("n单词%s在文本文件%s中共出现d次n",t.ch,fname,i);/*统计单词出现的个数*/void substri nt()FILE *fp;stri ng s,t;char fn ame10;int i,j,k,l,m;int wz20;printf("输入文本文件名：");sca nf("%s",fname);fp=fo pen( fname,"r");printf("输入要检索的单词：");sca nf("%s

21、",t.ch);t.le ngth=strle n(t.ch);l=0;while(!feof(fp)/*定义两个串变量*/*存放一行中字串匹配的多个位置*/*行计数器置0 */*扫描整个文本文件*/memset(s.ch,'0',110); fgets(s.ch,110,fp); s.le ngth=strle n( s.ch); I+;k=0;i=0;while(k<s.le ngth-1)/*/*行计数器自增1 */*初始化开始检索位置*/初始化单词计数器*/*检索整个主串S */j=partpo siti on( s,t,k); if(jvO) brea

22、k;else/*调用串匹配函数*/i+；wzi=j；k=j+t.le ngth；/*单词计数器加1 */*记录匹配单词位置*/*继续下一字串检索*/ if(i>0)%d,位置分别为：",l,i); printf("行号：%d,次数： for(m=1;m<=i;m+)printf("第%4d 个字符",wzm+1);prin tf("n");printf("n本软件自定义110个字节为一行nn");/*检索单词出现在文本文件中的行号、次数及其位置*/void substrio()void substrco

23、 un t(),substri nt();char t;while(1)prin tf("= printf("请输入:");prin tf("|文本文件单词字串的定位统计及定位|n"); prin tf("| prin tf("| prin tf("| prin tf("| prin tf("| prin tf("|n");a.b.单词出现次数单词出现位置I|n")；l|n")；l|n")；l|n")；l|n")；l|n&qu

24、ot;)；n");prin tf("= sca nf("%c", &t); switch(t)case 'a': substrco un t(); break;case 'b': substri nt(); break;default: return;int mai n()void creat_text_file(),substrsum(),substno(); int xz;while(1)printf("printf("prin tf("|文本文件的检索、子串的统计及疋位print

25、f( ll1.prin tf("|建立文本文件prin tf("|2.单词字串的计数prin tf("|3.单词字串的定位prin tf("|4.退出整个程序请选择（1-4）nn");l|n")；=l|n");l|n");l|n");l|n");l|n");printf("sea nf("%d", &xz);switch(xz)case 1: creat_text_file(); break;case 2: substrsum(); break;c

26、ase 3: substrio();break;n");");case 4: retur n 0;default: printf（"选择错误，重新选 n"）;return 0;4调试分析4.1问题分析与回顾问题1：在语句“请输入一行文本”后边，只写一句接受语句，结果运行时，请输 入文本和结束输入吗？演示在一起，并且不能接受文本输入。解决：和同学讨论后，加入了文本接受语句，成功运行。问题2:当要检索文本时，输入为空，或输入非建立的文本文件名，系统不能正常 运行。分析：缺少判断语句。解决：当出现这种情况时，系统提示输入错误，请重新输入。4.2算法时空分析确定

27、给定单词出现的个数，需要统计文本文件中全部的单词，因此时间复杂度为O(n);确定给定单词出现的位置，需要显示其所在的行和列，时间复杂度为O(i*l);4.3算法改进此算法虽然基本实现了功能，但却仍存在许多不足，例如当当前建立的文件名与之 前相同时，没有错误提示，另如在对单词的检索方面，时间复杂度及空间复杂度仍不尽 如人意。仍需要改进代码，达到算法的高效性。4.4经验和体会通过本次数据结构的课程设计，让我对数据结构这门课有了更加深刻的认识。 数据 结构这门课程的理论性只是较强，要学好这门课程，就必要在掌握好理论知识的同时， 加强上机操作，遇到问题，解决问题，这样才会有更大的进步。我课程设计的题目

28、是文件文本的检索与计数，由于这个课题要用到串的知识。而 我对之前对串的定义却不是很明确，于是我有详细的学习了课本上的知识并查阅了很多文献。在着手作程序的过程中，经常遇到程序运行不出来，运行达不到效果等问题，尤 其是接收文本，搜索时如何定位等方面遇到了很多问题。 但我通过请教老师和同学，查 阅文献，然后基本上解决了这些问题。在这个过程中我学到了很多，我认识到了坚持不 懈的重要性，在我一遍一遍的调试下，终于成功的写出了程序。在编写此次程序时，我 学会了先用流程图对进行算法分析， 这样是自己的思路更加清晰，而不是像之前那样对 整个函数没有整体的认知，而导致常常无从下手。之前我对数据结构的各种算法都感

29、到畏惧， 感觉很抽象，而这次通过自己几周的努 力,在老师和同学们的帮助下，终于完成了此次课程设计，这对我来说无疑是极大的鼓 舞,极大的增强了我学数据结构的自信心。 而且我也充分认识到数据结构本身就是一门 实践性很强的课程，只有加强实践，才能学得更好！5测试结果(1) 输入建立文件名 如图5所示为输入建立文件测试誌据结咎淳程设计iWbuSl心文本文件的检索"字串的统计及定位S 爭定序一 文程_ 文壬于整一 立词词岀 建单黑一12 3 4请选择<14>1迤A賈建i的文件名I fanxiangf图5输入建立文件测试(2)输入一行文本测试=回MU如图6所示建立一行文本，建立文件结

30、束界面。n ' G：菽fig结噺果卮设计Df bu g 1 exe勒定序 文的的程 文壬盂 立词词出 建单量12 3 4文本文件的检索、字串的统计及定位请选择<1-4>麵AS建i鱼塞件名：fanxiang】冃输A彳匸丈本 i we are the good friends 71文本文件的检索、字串的统计及定位12 3 1S#定序文的的程isP词词出H请选择<14>图6建立文件结束测试(3) 单词字串的计数测试 如图7,单词字串的计数测试界面。恕g结吃详程设计2亡bugiM. exeliSSSr文本文件的检索、字串的统计及定位“ S一 ffsff 一文的的程 &q

31、uot;si 一文壬子鑒 二：=词词出 建单專请选扌睪"-42个数111请输入文件名I fanxiansf 单词ape fl* lendsuefanxianvK单词总数为3个亦"戟网的非单词个数为1种文本文件的检索、字串的统计及定位图7单词字串的计数测试(4) 单词字串的定位测试口图8和图9所示。百：i据结咱慄程设计LDe b ugi l.exe'Wq , # E冋匸输入5镒护txw统讦1单词備在文本文件fanxiang中共岀现i次 诵簌；茹支蒋蒂駆奩貓应麺;富商S五套莎T':wea.b.单词岀现位置文本文件的检索、字串的统计及定位第定序 文的的租 ff 文宀士盂工 立词词出 建单星12 3 4谙选择<14>图8单词字串的定位测试I 9叭徵垢结彎;怪设计2凸阳1疋灼请输入：!哎本文件单词字串的定位统计定位!:单词岀现次数b.单词岀现位置:词 Wb . 文索诙 本检 S ; 入