摘 要  该程序研究的主要内容是以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;
}