摘 要 该程序研究的主要内容是以Visual C++为开发工具构造一个系统。该系统的功能是给定一个英文段落(单词个数<100),利用哈希表(表长最大为20)统计单词出现的频度,并能根据要求显示出给定单词在段落中出现的位置。执行程序时由用户在键盘上输入程序中规定的运算命令;相应的输入数据和运算结果显示在其后。 该系统的实现是通过哈希函数的建立和查找分析,用线性探测再散列来处理冲突,从而得到哈希表并实现哈希表的查找。哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。 关键字 哈希表 ;频度 ; haxilist 目录 1 概述 5 2 系统可行性分析 7 2.1技术可行性 7 2.2需求可行性 7 3 需求分析 8 4 概要设计 9 4.1本程序包含四个模块: 9 4.2单词文本串文件类型: 9 4.3 算法实现及哈希表类型: 11 5 详细设计 12 5.1 构造哈希函数 12 5.2 读取数据: 12 5.3 产生哈希表: 14 5.4 主函数 16 6 系统测试 17 7 结束语 18 参考文献 19 附录1源程序清单 20 附录2 用户手册 26
1 概述
该系统的功能是给定一个英文段落(单词个数<100),利用哈希表(表长最大为20)统计单词出现的频度,并能根据要求显示出给定单词在段落中出现的位置。执行程序时由用户在键盘上输入程序中规定的运算命令;相应的输入数据和运算结果显示在其后。 该系统的实现是通过哈希函数的建立和查找分析,用线性探测再散列来处理冲突,从而得到哈希表并实现哈希表的查找。该文章对哈希函数的应用方法是使用除留余数法构造,使用链地址法进行冲突处理。 本系统的开发工具是Visual C++。 C语言是一种开发语言,有很多厂商都开发了自己的C语言工具,目前常用的包括Visual C++和C++ Builder等。每个厂商都遵从一定标准,所以一般的C语言程序都可以在这些系统中编译,但是厂商也都增加了自己的一些特色功能,而这些特色功能可能是彼此不兼容的。 当然,Visual C++除了可以编译C语言的程序,它还可以编译C++程序,而C语言程序和C++程序的区别就大了。 C语言与VC++的区别有很多: 全新的程序程序思维,C语言是面向过程的,而VC++是面向对象的。 C语言有标准的函数库,它们松散的,只是把功能相同的函数放在一个头文件中;而VC++对于大多数的函数都是有集成的很紧密,特别是C语言中没有的VC++6.0中的API是对Window系统的大多数API有机的组合,是一个集体。但你也可能单独调用API。 特别是VC++中的图形处理,它和语言的图形有很大的区别。C语言中的图形处理函数基本上是不能用在中VC++中的。主持人注:C语言标准中不包括图形处理。这里的C语言的图形处理指的是DOS下的C语言。 C和VC++中都有结构的概念,但是在C语言中结构只有成员变量,而没成员方法,而在VC++中结构中,它可以有自己的成员变量和成员函数。但是在C语言中结构的成员是公共的,什么想访问它的都可以访问;而在VC++中它没有加限定符的为私有的。 C语言可以写很多方面的程序,但是VC++可以写得更多更好,VC++可以写基于DOSr程序,写DLL,写控件,写系统。 C语言对程序的文件的组织是松散的,几乎是全要程序处理;而vc++对文件的组织是以工程,各文件分类明确。 VC++中的IDE很智能,和VB一样,有的功能可能比VB还强。 VC++对可以自动生成你想要的程序结构使你可以省了很多时间。有很多可用的工具如加入MFC中的类的时候,加入变量的时候等等。 VC++中的附加工具也有很多,可以进行系统的分析,可以查看API;可以查看控件。 调试功能强大,并且方法多样。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。哈希表又叫做散列表,分为"开散列" 和"闭散列"。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。 2 系统可行性分析 2.1技术可行性 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。 哈希查找的操作步骤: 用给定的哈希函数构造哈希表; 根据选择的冲突处理方法解决地址冲突; 在哈希表的基础上执行哈希查找。 2.2需求可行性 世界上的事物都是有发展的,企图跨越阶段或者停滞,一切生命就都没有存在的理由了。频率就是一个既动态又静态的东西,我们能肯定的是很多古词和今词是不一样的,今日被淘汰了,也就是说,今天的频率的统计是一定有确定的结论的。也有一些古词仍在今日用着,或者在淘汰之中,所以频率难以确定。我们知道黑天和白天是有区别的,但它们的交界点,却不是那么容易分辨了,恐怕需要经过科学家的精密研究。交界点不容易确定,并不意味着事物之间没有区别。世界上的事物都是有区别又有联系的。有些人读书读傻了,钻了牛角尖,他弄不清两个事物之间的区别应该划在哪里,后来就连两个事物之间有区别也不敢认定了。频率的统计是为了区别常用词和非常用词,方法可能不准确,但不至于否定常用词和非常用词之间的区别吧。我们应该使统计精密起来。火车今天不用火了,但如果当初也不用,就没有今天的“火车”了。事物的变化是不可能停止的,但总还有个静态的定位,否则人们就无法认识任何事物了。频率虽然是个复杂的问题,但科学的研究是必要的。
3 需求分析
给定一个英文段落(单词个数<100),利用哈希表(表长最大为20)统计单词出现的频度,并能根据要求显示出给定单词在段落中出现的位置。 执行程序时由用户在键盘上输入程序中规定的运算命令;相应的输入数据和运算结果显示在其后。 测试数据:给定一个英文段落 显示出不同英文单词的出现频度。 给定一个英文单词,判断段落中是否含有该单词,如有,依次显示出该单词在段落中出现的位置。 基本要求:哈希函数使用除留余数法构造,使用链地址法进行冲突处理。 4 概要设计 4.1本程序包含四个模块: 主程序模块:void main() 构造哈希表函数:void initial( ) 读取英文段落函数void input (ElemType **ST,int n ) 查找函数:void insert( char* w,int length) 各模块之间的调用关系如下: main() void initial( ) void input (ElemType **ST,int n ) void insert( char* w,int length) 4.2单词文本串文件类型: ADT TextString{ 数据对象: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为查询结果。} ADT TextString5.1 算法实现及哈希表类型: ADT HashTable{ 数据对象: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。}ADT HashTable
4.3 算法实现及哈希表类型: ADT HashTable{ 数据对象: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。}ADT HashTable
5 详细设计 5.1 构造哈希函数 void initial() //哈希表的初始化{ for(int i(0); i<100; i++) { haxilist[i].head=NULL; haxilist[i].tail= NULL; } cout<<"哈希表初始化完成,准备读入文件,请将需要操作的文件命名为file.txt放到文件夹中"<<endl;} 5.2 读取数据: void input() //读入文件{ cout<<"开始读入文件..."<<endl; fstream infile;infile.open("file.txt",ios::in); if(!infile) { cout<<"File can't be open"<<endl; //读入失败 abort(); } //cout<<"the input is called "<<endl; char c[size]; while(!infile.eof()) { char h; infile.get(h); //cout<<h<<endl; while( !('A'<=h && h<='Z'||'a'<=h && h<='z')) //只读英语单词 { if(infile.eof()) return; infile.get(h); //cout<<h<<endl; } int i; 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'; // cout<<endl; char*s ; s=new char[i]; strncpy(s,c,i); //cout<<s; //cout<<endl; insert(s,i); } infile.close(); //结束读入 }
5.3 产生哈希表: void insert( char* w,int length) //哈希表的操作:搜索和插入 { int k; k=0; for(int i(0);i<length && w[i]!='\0';i++) { k+=w[i]; } //cout<<"insert is called"<<endl; k=k%100; cout<<k<<" "; //完成插入操作 if(haxilist[k].head==NULL) //此时哈希表为空, { //cout<<"is blank insert"<<endl; haxilist[k].head=new word; 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=new word; haxilist[k].tail=haxilist[k].tail->next; haxilist[k].tail->frequency++; haxilist[k].tail->str=w; haxilist[k].tail->next=NULL; } else { delete w; templ->frequency++; } } }
5.4 主函数 void main () //主函数 { cout<<" ******************************************"<<endl; cout<<" * *"<<endl; cout<<" * 哈希表应用--英语单词频度统计 *"<<endl; cout<<" * *"<<endl; cout<<" **************************************************"<<endl; initial(); input(); cout<<endl; cout<<"文件读入完毕!"; cout<<endl; int n=0; for(int i(0);i<100;i++) { if(haxilist[i].head!=NULL) { n++; cout<<"单词 "<<haxilist[i].head->str<<"频度为 "; cout<<haxilist[i].head->frequency<<endl; } } cout<<" 在读入的文件中共搜索到"<<n<<"个不同的单词"<<endl; } 6 系统测试
在程序运行时,根据界面提示,会得到以下结果:
7 结束语 通过对本课题的研究和系统的详细设计,再到系统开发运行,使我对应用系统的开发流程有了深刻的认识,成功完成系统的开发首先必须要对系统进行规划,对系统流程进行分析,对各个模块的功能进行设计。在编写该程序时,主要是哈希函数的建立和查找分析,用线性探测再散列来处理冲突,从而得到哈希表并实现哈希表的查找。发现运行结果中出现了乱码,而且是个别单词的统计结果返回时才出现乱码,怀疑是标点符号的原因,去掉标点后还是如此;又怀疑是回车符的原因,去掉回车符仍然如此。依然没有解决;希望老师给我找到原因。 经过三个星期的努力,在克服了许许多多的困难之后,终于完成了课程设计,其主要的目标和任务基本上都实现了。这几个星期是对我们大学所学知识,技能的一次真正、全面的考验,是锻炼我们动手能力、分析能力、创新能力的一次难得机会。这个学期是我大学最为繁忙的一个学期,但也是最有意义、过得最充实的一个学期。由于时间短暂,设计之中还有许多不足之处,有待于今后进一步的完善。在这期间中,我得到了肖晓丽老师的帮助和指导,在此向老师表示衷心的感谢。因为水平有限,我的工作还有许多不足之处,希望老师指正。 最后,向肖晓丽老师和所有给予我关心和帮助的人们表示最诚挚的感谢,谢谢他们的帮助关心和指导! 参考文献
1. 数据结构与C++高级教程 (美)Frank M.Carrano,(美)Janet J.Prichard著;田玉敏译;田玉敏译.清华大学出版社. 2004年6月 2. C++沉思录 (美)Andrew Koenig,(美)Barbara Moo著;黄晓春译. 人民邮电出版社.2002年 3. Visual C++程序设计 秦勇,张克强编著 .北京大学出版社. 1994年6月 4. 数据结构: 使用C 语言 朱战立,刘天时编著. 西安交通大学出版社. 2000年
附录1源程序清单 源程序代码:#include<iostream.h>#include<string.h>#include<fstream.h>#include<stdlib.h>#define size 20struct word{ int frequency; //单词出现的频度 char* str; //关键字 word* next;};struct aword //不设首结点{ word* head; word* tail;};#define max 100 //定义短文的最大长度 struct aword haxilist[100]; //哈希表 /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ void initial() //哈希表的初始化{ for(int i(0); i<100; i++) { haxilist[i].head=NULL; haxilist[i].tail= NULL; } cout<<"哈希表初始化完成,准备读入文件,请将需要操作的文件命名为file.txt放到文件夹中"<<endl;} /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ void insert( char* w,int length) //哈希表的操作:搜索和插入{ int k; k=0; for(int i(0);i<length && w[i]!='\0';i++) { k+=w[i]; } //cout<<"insert is called"<<endl; k=k%100; cout<<k<<" "; //完成插入操作 if(haxilist[k].head==NULL) //此时哈希表为空, { //cout<<"is blank insert"<<endl; haxilist[k].head=new word; 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=new word; haxilist[k].tail=haxilist[k].tail->next; haxilist[k].tail->frequency++; haxilist[k].tail->str=w; haxilist[k].tail->next=NULL; } else { delete w; templ->frequency++; } }} /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ void input() //读入文件{ cout<<"开始读入文件..."<<endl; fstream infile;infile.open("file.txt",ios::in); if(!infile) { cout<<"File can't be open"<<endl; //读入失败 abort(); } //cout<<"the input is called "<<endl; char c[size]; while(!infile.eof()) { char h; infile.get(h); //cout<<h<<endl; while( !('A'<=h && h<='Z'||'a'<=h && h<='z')) //只读英语单词 { if(infile.eof()) return; infile.get(h); //cout<<h<<endl; } int i; 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'; // cout<<endl; char*s ; s=new char[i]; strncpy(s,c,i); //cout<<s; //cout<<endl; insert(s,i); } infile.close(); //结束读入 } /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ void main () //主函数{ cout<<" **********************************************************************"<<endl; cout<<" * *"<<endl; cout<<" * 哈希表应用--英语单词频度统计 *"<<endl; cout<<" * *"<<endl; cout<<" **********************************************************************"<<endl; initial(); input(); cout<<endl; cout<<"文件读入完毕!"; cout<<endl; int n=0; for(int i(0);i<100;i++) { if(haxilist[i].head!=NULL) { n++; cout<<"单词 "<<haxilist[i].head->str<<"频度为 "; cout<<haxilist[i].head->frequency<<endl; } } cout<<" 在读入的文件中共搜索到"<<n<<"个不同的单词"<<endl; }