设计题目统计英文单词数姓名学号专业班级“程序设计基础”课程设计报告(一)需求和规格说明该系统的功能是给定一个英文段落(单词个数100),利用哈希表(表长最大为20)统计单词出现的频度,并能根据要求显示出给定单词在段落中出现的位置。执行程序时由用户在键盘上输入程序中规定的运算命令;相应的输入数据和运算结果显示在其后。该系统的实现是通过哈希函数的建立和查找分析,用线性探测再散列来处理冲突,从而得到哈希表并实现哈希表的查找。该文章对哈希函数的应用方法是使用除留余数法构造,使用链地址法进行冲突处理。2.1技术可行性哈希查找是通过计算数据元素的存储地址进行查找的一种方法。哈希查找的操作步骤:用给定的哈希函数构造哈希表;根据选择的冲突处理方法解决地址冲突;在哈希表的基础上执行哈希查找。2.2需求可行性世界上的事物都是有发展的,企图跨越阶段或者停滞,一切生命就都没有存在的理由了。频率就是一个既动态又静态的东西,我们能肯定的是很多古词和今词是不一样的,今日被淘汰了,也就是说,今天的频率的统计是一定有确定的结论的。也有一些古词仍在今日用着,或者在淘汰之中,所以频率难以确定。我们知道黑天和白天是有区别的,但它们的交界点,却不是那么容易分辨了,恐怕需要经过科学家的精密研究。交界点不容易确定,并不意味着事物之间没有区别。世界上的事物都是有区别又有联系的。有些人读书读傻了,钻了牛角尖,他弄不清两个事物之间的区别应该划在哪里,后来就连两个事物之间有区别也不敢认定了。频率的统计是为了区别常用词和非常用词,方法可能不准确,但不至于否定常用词和非常用词之间的区别吧。我们应该使统计精密起来。火车今天不用火了,但如果当初也不用,就没有今天的“火车”了。事物的变化是不可能停止的,但总还有个静态的定位,否则人们就无法认识任何事物了。频率虽然是个复杂的问题,但科学的研究是必要的。3需求分析给定一个英文段落(单词个数100),利用哈希表(表长最大为20)统计单词出现的频度,并能根据要求显示出给定单词在段落中出现的位置。执行程序时由用户在键盘上输入程序中规定的运算命令;相应的输入数据和运算结果显示在其后。测试数据:给定一个英文段落显示出不同英文单词的出现频度。给定一个英文单词,判断段落中是否含有该单词,如有,依次显示出该单词在段落中出现的位置。基本要求:哈希函数使用除留余数法构造,使用链地址法进行冲突处理。(二)设计构造哈希函数voidinitial()//哈希表的初始化{for(inti(0);i100;i++){haxilist[i].head=NULL;haxilist[i].tail=NULL;}cout哈希表初始化完成,准备读入文件,请将需要操作的文件命名为file.txt放到文件夹中endl;}读取数据:voidinput()//读入文件{cout开始读入文件...endl;fstreaminfile;infile.open(file.txt,ios::in);if(!infile){coutFilecan'tbeopenendl;//读入失败abort();}//couttheinputiscalledendl;charc[size];while(!infile.eof()){charh;infile.get(h);couthendl;while(!('A'=h&&h='Z'||'a'=h&&h='z'))//只读英语单词{if(infile.eof())return;infile.get(h);//couthendl;}inti;i=0;while('A'=h&&h='Z'||'a'=h&&h='z'){if(h'a'){h=h-'A'+'a';//将大写字母转化为小写}c[i++]=h;infile.get(h);}c[i]='\0';coutendl;char*s;s=newchar[i];strncpy(s,c,i);couts;coutendl;insert(s,i);}infile.close();//结束读入}产生哈希表:voidinsert(char*w,intlength)//哈希表的操作:搜索和插入{intk;k=0;for(inti(0);ilength&&w[i]!='\0';i++){k+=w[i];}coutinsertiscalledendl;k=k%100;coutk;//完成插入操作if(haxilist[k].head==NULL)//此时哈希表为空{coutisblankinsertendl;haxilist[k].head=newword;haxilist[k].head-next=NULL;haxilist[k].head-frequency=0;haxilist[k].head-frequency++;haxilist[k].head-str=w;haxilist[k].tail=haxilist[k].head;}else{//此时哈希表不为空,搜索关键字word*templ;for(templ=haxilist[k].head;!(strcmp(w,templ-str))&&templ-next!=NULL;templ=templ-next);//搜索完毕if(!strcmp(templ-str,w)){//没有找到关键字haxilist[k].tail-next=newword;haxilist[k].tail=haxilist[k].tail-next;haxilist[k].tail-frequency++;haxilist[k].tail-str=w;haxilist[k].tail-next=NULL;}else{deletew;templ-frequency++;}}}主函数voidmain()//主函数{cout******************************************endl;cout**endl;cout*哈希表应用--英语单词频度统计*endl;cout**endl;cout**************************************************endl;initial();input();coutendl;cout文件读入完毕!;coutendl;intn=0;for(inti(0);i100;i++){if(haxilist[i].head!=NULL){n++;cout单词haxilist[i].head-str频度为;couthaxilist[i].head-frequencyendl;}}cout在读入的文件中共搜索到n个不同的单词endl;}(三)用户手册本程序包含四个模块:主程序模块:voidmain()构造哈希表函数:voidinitial()读取英文段落函数voidinput(ElemType**ST,intn)查找函数:voidinsert(char*w,intlength)单词文本串文件类型:ADTTextString{数据对象:D={ai|ai属于字母字符集,i为正整数}数据关系:D中字符被“换行符”分割成若干行,每一行的字符间满足下类关系:R1={ai-1,ai|ai-1,ai属于D,i为正整数}基本操作:Initiation(&f)初始条件:文件f已存在。操作结果:打开文件f,设定文件指针指向第一行第一个字符。GetAWord(f,&w)初始条件:文件f打开。操作结果:从文件指针所指字符起提取一个“单词w”。ExtractWord(f,&H)初始条件:文件f已打开,文件指针指向文件f中某一行的第一个字符。操作结果:提取该行中所有单词,并构成单词的哈希表H;本操作结束时,文件指针指向文件f中下一行的第一个字符。Match(f,pat,&Result)初始条件:文件已打开,文件指针指向文件f中某一行的第一个字符;pat为包含所有待查询单词的哈希表。操作结果:Result为查询结果。}ADTTextStringADTHashTable{数据对象:D={ai|ai属于AWord,i为正整数}数据关系:R1={ai-1,ai|ai-1,ai属于D,i为正整数}基本操作:InitialHash(HashTable&)操作结果:初始化哈希表。PrintHash(HashTable)初始条件:哈希表H已存在。操作结果:显示哈希表H中的所有元素。SearchHash(HashTable,int,int&)初始条件:哈希表H已存在。操作结果:在哈希表H中查找元素,成功返回1,否则返回0。InsertHash(HashTable&,Record)初始条件:哈希表H已存在。操作结果:在哈希表H中插入元素,成功返回1,否则返回0。DeleteHash(HashTable&,Record)初始条件:哈希表H已存在。操作结果:在哈希表H中删除元素,成功返回1,否则返回0。}ADTHashTable算法实现及哈希表类型:ADTHashTable{数据对象:D={ai|ai属于AWord,i为正整数}数据关系:R1={ai-1,ai|ai-1,ai属于D,i为正整数}基本操作:InitialHash(HashTable&)操作结果:初始化哈希表。PrintHash(HashTable)初始条件:哈希表H已存在。操作结果:显示哈希表H中的所有元素。SearchHash(HashTable,int,int&)初始条件:哈希表H已存在。操作结果:在哈希表H中查找元素,成功返回1,否则返回0。InsertHash(HashTable&,Record)初始条件:哈希表H已存在。操作结果:在哈希表H中插入元素,成功返回1,否则返回0。DeleteHash(HashTable&,Record)初始条件:哈希表H已存在。操作结果:在哈希表H中删除元素,成功返回1,否则返回0。}ADTHashTable(四)调试及测试在程序运行时,根据界面提示,会得到以下结果:(五)运行实例:(六)心得体会通过对本课题的研究和系统的详细设计,再到系统开发运行,使我对应用系统的开发流程有了深刻的认识,成功完成系统的开发首先必须要对系统进行规划,对系统流程进行分析,对各个模块的功能进行设计。在编写该程序时,主要是哈希函数的建立和查找分析,用线性探测再散列来处理冲突,从而得到哈希表并实现哈希表的查找。发现运行结果中出现了乱码,而且是个别单词的统计结果返回时才出现乱码,怀疑是标点符号的原因,去掉标点后还是如此;又怀疑是回车符的原因,去掉回车符仍然如此。依然没有解决;希望老师给我找到原因。经过三个星期的努力,在克服了许许多多的困难之后,终于完成了课程设计,其主要的目标和任务基本上都实现了。这几个星期是对我们大学所学知识,技能的一次真正、全面的考验,是锻炼我们动手能力、分析能力、创新能力的一次难得机会。这个学期是我大学最为繁忙的一个学期,但也是最有意义、过得最充实的一个学期。由于时间短暂,设计之中还有许多不足之处,有待于今后进一步的完善。在这期间中,我得到了老师的帮助和指导,在此向老师表示衷心的感谢。因为水平有限,我的工作还有许多不足之处,希望老师指正。(七)附录源程序(1)#includeiostream#includestring.h#includemalloc.h#includestdio.h#includetime.husingnamespacestd;#defineCLOCKS_PER_SEC((time_t)1000)typedefstruct_link//定义该链表是为了存储不重复出现的单词{char*ch;intnum;_link*next;}link;intmain(){clock_tt_st