英文词汇统计.doc

数据结构课程设计报告（英文词汇的统计）题目:对英语范文中词汇的统计一.需求分析(1).程序将读取C盘根目录下的一个名为test.txt的文本文件,然后循环输入文件中的字符.程序只会处理大写或者小写的英文字符,对其余的任何字符会进行输入,但是不会进行任何处理.当遇到文件结束符EOF后停止输入并显示出对所有单词的统计.最后程序会要求输入需要查询的单词个数及需要查询的单词.查询完毕后程序结束.(2).程序在执行后先输出对文本中所有单词的统计,之后会提示用户输入需要查询的单词数量N,再提示N次输入需要查询的单词,每次输入完毕后输出查询结果.(3).本程序能对文本中所出现的英文单词及单词出现的次数进行统计,最后提供给用户查询.(4).测试数据(1).(在文本中输入) abc abc acb bca bcc.bca,./;bac acb /bcc输出:abc:2 acb:2 bca:2 bcc:2 bac:1若C盘跟目录下没有名称为test.txt的文本文件.则输出”文件不存在”后程序自动结束,若文本为空,程序会输出文本为空的提示后自动结束.二.概要设计 为了实现上述功能,应使用链表储存每一个得到的新单词.所以需要一个抽象数据类型:有序表.1.有序表的抽象数据类型定义为：ADT word 数据对象：D=ai|ai=0数据关系：R1=|ai-1,aiD,ai-1next=head-next;head-next=p; /使用头插法插入新节点p- vocabulary=d; /给新节点数据域赋值p-num=1;Int findwords(word *head,d)Find=(word *)malloc(sizeof(word);Find=head;If(find- vocabulary=p) Return 0; /查找到,返回1Else Return 0; /未找到.返回0Void printwords(word *head)P=head;If(p!=NULL) Printf(p- vocabulary); /输出每个节点的数据域 Printf(p-num); P=p-next;Void searchwords(word *head,d)Find=(word *)malloc(sizeof(word);Find=head-next;If(find- vocabulary=d) Printf(find-num); /输出找到的节点数据域的值 Break; /跳出循环Else Find=find-next; /查找下一节点3. 函数的调用关系图反映了演示程序的层次结构:Main Findords Newords Printwords Searchwords四.调试分析1.由于对线性表的算法了解不足,在第一次尝试建立线性表的时候头节点未与其后部分链接起来.2.在写findwords函数的时候忘记在查找成功后使用break语句退出循环,这样每次查找都要遍历链表,导致程序运行效率低下.3.字符串处理部分在程序写好后才想起使用strcmp,strcpy等字符串处理函数提高效率.4.本程序的模块划分比较合理,不同功能的实现有对应的函数,使程序代码简单易懂,同时也方便调试.其中字符串处理部分未独立为函数的原因是在若函数中处理好字符串再返回主函数时使用指针容易导致错误,所以在主函数中处理好再使用.头节点在主函数中定义好也方便新建节点函数反复调用以完成头插建立链表的过程.5. 算法的时空分析1). 基于有序链表实现的有续集的各种运算和操作的时间复杂度分析如下:构造和插入有序表算法中,有序表的长度为n,所以此算法的时间复杂度为O(n).同时,输出线性表的时间复杂度也为O(n).查找线性表的时间复杂度也为O(n).2). 在对字符串的处理部分中,设文本长度为n,由于字符串是全部被输入,非字母部分将被排除,设字母长度为m,所以此部分的时间复杂度为O(m+n).3). 在线性表建立部分,头节点和新的建立只需要建立一个,所以空间复杂度为O(1).在字符串处理部分,需要建立一个字符串保存,一个字符串传递所得到的单词,每建立一个节点需要一个,所以空间复杂度为O(n+1).6. 本专业设计习题将结构体,有续表和字符串处理放在一起进行考察,在了解所有部分的使用的同时,也使我们在调试程序的时候更加熟悉了所有工具的用法,确实得到了一次良好的程序设计训练.五,用户手册1. 本程序的运行环境为任何Windows操作系统,执行文件为:词汇统计.exe2. 执行程序前,要在系统C盘根目录下新建一个文本文档,并且命名为test.txt,同时将测试文本输入文档.3. 执行程序,先会显示出所有单词的统计结果,之后将提示用户输入需要查询的单词个数,如下图:之后输入一个数字n(比如示例中输入2),程序将循环n次提示输入一个单词,输入单词后,将输出对此单词的查询结果,若查询到输出此单词出现个数,若未找到则提示没有此单词查询完毕,按任意键即退出.六.测试结果在文本中输入一句话:Hello word! This is my first program!程序执行后输出:program:1 first:1 my:1 is:1 This:1 word:1 Hello:1若附带的测试文档中没有任何英文字符,(包括只有符号和数字的概况)程序会提示将英文文本输入,且不会有任何输出.若测试文档不存在于指定位置下,则程序报错后自动退出.总的来说,程序的设计很好的完成了既定任务,由于时间紧迫,所以程序还不是很完善,以下问题亟需日后改善:本程序是通过识别一个英文字母开始输入单词,以连续英文字符后的非英文字符作为单词的结束.这样的判定方式虽然在大部分时候可以实现功能,但还是有它的局限性,例如在输入”Its”这样的组合词时会判定为两个单词It和S保存及输出,另外对于相同单词的不同语法形式也无法判断,例如”use”及”used”也会作为两个单词处理.以上这些问题,都需要在将来花更多时间创造更加智能的程序去解决.七.附录程序源代码:#include stdio.h#include stdlib.h#include string.hstruct word /定义储存单词及出现次数的结构体char vocabulary25;int num;word *next;void main ()int findwords(word *head,char d); /声明比较单词的函数void newwords(word *head,char d); /声明创建新单词节点的函数void printwords(word *head); /声明节点打印函数void searchwords(word *head,char str); /声明节点查找函数char c,d25,str25;int i=0,flag=0,sum,n;word *head;FILE *fp;fp=fopen(c:/test.txt,r); /打开文本文件if(fp=NULL)printf(文本不存在，请在C盘根目录下重建test.txt文件！n); /若文件不存在exit(0);head=(word *)malloc(sizeof(word); /创建头节点if(head=NULL)printf(内存不足，无法开辟头节点！n);exit(0);head-next=NULL;while(fscanf(fp,%c,&c)!=EOF) /在文件结束前循环读取字符if(c=65&c=97&cnext=NULL) /若文本为空或没有英文字符printf(文本为空或不存在任何英文字符，请重新输入！n);exit(0);printwords(head); /文章输入完毕，打印所有单词及其出现次数printf(n请输入需要查询的单词个数：n);scanf(%d,&n);getchar(); /忽略掉一个回车符printf(n);for(i=0;ivocabulary,d)=0) /若查找到相同单词，节点计数器加一find-num+;p=1;return 1;elsefind=find-next; /当前节点没有找到，寻找下一节点if(p=0)return 0; /没有找到匹配单词，返回0void newwords(word *head,char d) /定义节点创建函数word *p;p=(word *)malloc(sizeof(word);if(p=NULL)printf(内存不足，无法保存数据！);exit(0);strcpy(p-vocabulary,d); /把新单词赋给p所指向节点的数据域p-num=1; /此节点单词计数器为1p-next=head-next; /用头插法插入节点head-next=p;void printwords(word *head) /定义节点打印函数word *p;int i=0;p=head-next;while(p!=NULL)printf(%s:,p-vocabulary);printf(%d ,p-num);if(i!=0&i%5=0) /每五个单词一行printf(n);p=p-next;i+;void searchwords(word *head,char str) /定义节点查