哈希表的應用-英語單詞頻率統計

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