1、 數據結構課程設計報告 題目：利用哈希技術統計C源程序關鍵字出現頻度 學生姓名： 於 金 娥 學 號： 班 級： 指導教師： 高 永 平 2012年 6 月 16 日目 錄一、 需求分析2二、 總體設計3三、 詳細設計4五、 程序測試12六、 總結151.問題：152.收獲：15利用哈希技術統計C源程序關鍵字出現頻度1、 需求分析1.題目內容：利用Hash技術統計某個C源程序中的關鍵字出現的頻度。2.基本要求：掃描一個C源程序，用Hash表存儲該程序中出現的關鍵字，并統計該程序中的關鍵字出現的頻度。用線性探測法解決Hash沖突。設Hash函數為：Hash(key)(key的第一個字母序號)*1

2、00+(key的最后一個字母序號) MOD 413. 需求：（1） 首先要用一個二維數組存儲C源程序中的32個關鍵字。（2） 建立Hash表。（3） 在Hash表中找到相應的位置存放關鍵字。（4） 讀取某個C文件，并統計出現的每個關鍵字在Hash表中存放的位置及在文件中出現的次數。（5） 輸入文件中出現的任意一個關鍵字，顯示在Hash表中存放的位置及在文件中出現的次數。（6） 顯示C源程序中所有關鍵字在Hash表中的位置。（7） 顯示所有沖突關鍵字列表。2、 總體設計3、 詳細設計1.創建一個哈希表類HashTable和一個類模板HASH： HashTable: char keywordMAX

3、LEN; int count; int num; HASH: void Show(int key); int CreatHX(char *keyword); int GetFreePos(int key); void ResetHX(); int GetKey(char *keyword); int isKeyWords(char *word); int Read(char *filename); int isLetter(char ch); int FindHX(char *keyword) int key; char *keyword; char *word; char ch; 2.構造二

4、維數組存儲32個關鍵字：KeyWordsTOTALMAXLEN= char, double, enum, float, int, long, short, signed, struct, union, unsigned, void, break, case, continue, default, do, else, for, goto, if, return, switch, while, auto, extern, register, static, const, sizeof, typedef, volatile3.各個數據成員及成員函數的功能：數據成員： keywordMAXLEN 存放

5、關鍵字； count 關鍵字出現次數； num 沖突次數； key 關鍵字在哈希表中的下標； *keyword 指向關鍵字的首字母指針； *word 指向文件中單詞的指針； ch 關鍵字的每一個字母；成員函數： Show(int key)輸出關鍵字：若輸入正確，輸出關鍵字在哈希表中的存儲位置及其在指定的文件中出現的次數；否則，提示出錯（關鍵字不存在）。 CreatHX(char *keyword)建立哈希表：先計算哈希值，再判斷關鍵字表中該位置是否存在關鍵字，如果存在，再判斷哈希表中該位置的關鍵字是否相同，若相同，count加一；若不相同，繼續查找，直到將關鍵字插入哈希表；如果該位置為空，直接

6、將關鍵字插入該位置中。 GetFreePos(int key)在哈希表中給關鍵字找個位置插進去：先找后面的位置，從下標為key+1的位置開始查找，若該位置為空，則將關鍵字放到此位置（即沒有沖突），否則（發生沖突，用線性探測法解決沖突），依次往后查找，直到有空位，如果到哈希表的表尾仍無空位，則重新從哈希表的第一個位置依次往后查找，直到將關鍵字插入到哈希表中。 ResetHX()重置哈希表。 GetKey(char *keyword)哈希函數：Hash(Key)=(Key的首字母序號)*100+(Key的尾字母序號) Mod 41。 isKeyWords(char *word) 判斷是否關鍵字：是

7、關鍵字就返回1，否則返回0值。 Read(char *filename)讀取文件：若打開文件不成功，提示錯誤；否則，讀取文件前先清空哈希表，利用文件結束檢測函數feof(),如果沒有結束,返回值是0,結束了是1。一個一個字符依次讀取，如果不是字母的話接著讀取，如果是字符，超過關鍵字長度將跳過當前識別區域,讀取后一單詞，若沒有超過關鍵字長度，將連續讀取的字母存在數組里，組成一個單詞，直到字符數組的結束，提示文件讀取成功。 isLetter(char ch)判斷是否是字母：關鍵字是英文單詞，由字母組成，是字母就返回1，否則返回0值。 FindHX(char *keyword)查找哈希表：先利用哈希

8、函數GetKey(keyword)計算出關鍵字在哈希表中應存放的位置，看看是否是該關鍵字，若是（即不存在沖突），返回此哈希表的位置，否則（存在沖突），依次往后查找，直到找到相應的關鍵字，如果到哈希表的表尾仍未找到該關鍵字，則重新從哈希表的第一個位置依次往后查找，直到找到為止。 4、 實現部分#include #include#include #include using namespace std; const int TOTAL=32; const int MAXLEN=10; const int HASHLEN=41; int cont=0; class HashTable public:

9、char keywordMAXLEN;int count; int num; ; HashTable HSHASHLEN;char KeyWordsTOTALMAXLEN= char, double, enum, float, int, long, short, signed, struct, union, unsigned, void, break, case, continue, default, do, else, for, goto, if, return, switch, while, auto, extern, register, static, const, sizeof, ty

10、pedef, volatile;template class HASHpublic:void Show(int key); int CreatHX(char *keyword); int GetFreePos(int key); void ResetHX(); int GetKey(char *keyword); int isKeyWords(char *word); int Read(char *filename); int isLetter(char ch); int FindHX(char *keyword);private:int key;char *keyword;char *wor

11、d;char ch;template void HASH:Show(int key)if(key=HASHLEN)cout關鍵字不存在!endl;return;if(strlen(HSkey.keyword)=0)cout哈希表位置：key 記錄是空的endl;return ;cout哈希表位置: key 關鍵字: HSkey.keyword 出現次數 HSkey.countendl;cont+;template int HASH:CreatHX(char *keyword) int key;if(!isKeyWords(keyword) return -1; key=GetKey(keywo

12、rd); if(strlen(HSkey.keyword)0) if(strcmp(HSkey.keyword,keyword)=0) HSkey.count+;return 1;key=FindHX(keyword); if(key0)key=GetFreePos(GetKey(keyword);if(key0) return -1;strcpy(HSkey.keyword,keyword); if(key0) return -1;HSkey.count+;else strcpy(HSkey.keyword,keyword);HSkey.count+;return 1;template in

13、t HASH:GetFreePos(int key) int find,tem=0;if(key=HASHLEN) return -1;for(find=key+1;findHASHLEN;find+) tem+;if(strlen(HSfind.keyword)=0)HSfind.num=tem;return find; for(find=0;findkey;find+) tem+;if(strlen(HSfind.keyword)=0)HSfind.num=tem;return find; return -1; template void HASH:ResetHX() int i;for(

14、i=0;iHASHLEN;i+)strcpy(HSi.keyword,); HSi.count=0;HSi.num=0; template int HASH:GetKey(char *keyword) return ( keyword0*100+keywordstrlen(keyword)-1 ) % 41; template int HASH:isKeyWords(char *word) int i;for(i=0;iTOTAL;i+)if(strcmp(word,KeyWordsi)=0) return 1; return 0;template int HASH:isLetter(char

15、 ch) if( (ch=a&ch=A&ch=Z) ) return 1;else return 0; template int HASH:FindHX(char *keyword) int key,find,tem=0;if(!isKeyWords(keyword) return -1;key=GetKey(keyword); if(strcmp(HSkey.keyword,keyword)=0) return key;for(find=key+1;findHASHLEN;find+)tem+; if(strcmp(HSfind.keyword,keyword)=0)HSfind.num=t

16、em;return find; for(find=0;findkey;find+)tem+;if(strcmp(HSfind.keyword,keyword)=0)HSfind.num=tem;return find; return -1; template int HASH:Read(char *filename) char wordMAXLEN,ch;int i;FILE *read; fstream myfile; myfile.open(filename);if(!myfile) cout文件不存在,請確認好再輸入!endl;return -1;ResetHX(); while(!fe

17、of(read) i=0;ch=fgetc(read); while(isLetter(ch)=0 & feof(read)=0 ) ch=fgetc(read);while(isLetter(ch)=1 & feof(read)=0 )if(i=MAXLEN)while(isLetter(ch)=1& feof(read)=0)ch=fgetc(read);i=0;break;else wordi+=ch;ch=fgetc(read);wordi=0; if(isKeyWords(word)CreatHX(word);fclose(read);cout讀取成功，文件中關鍵字已經存入hash表

18、，請繼續操作endl;return 1; void main()HASH hash; char filename128,wordMAXLEN;int i=0,count=0;int key;char j,y;coutfilename;coutendl;hash.Read(filename); for(i=0;iHASHLEN;i+)hash.Show(i); getchar(); cout關鍵字總數為：contendl; coutword; coutendl;hash.Show(hash.FindHX(word); cout C語言中的關鍵字和其在哈希表的位置:endl;for(i=0;iTO

19、TAL;i+)coutsetiosflags(ios:left)setw(2)hash.GetKey(KeyWordsi)setiosflags(ios:left)setw(11)KeyWordsi;if(i+1)%4=0) coutendl;coutj;if(j=y) cout沖突關鍵字列表endl; for(i=0;i0)key=hash.GetKey(HSi.keyword);if(key!=i)count+;coutsetiosflags(ios:left)setw(14) t關鍵 字:HSi.keywordsetiosflags(ios:left) setw(20)t哈希表當前位置:

20、 isetiosflags(ios:left) setw(20)t沖突次數: HSi.numendl; if(count=0) cout沒有沖突endl;elsecoutt沖突關鍵字共:count個endl;elsecout不顯示沖突關鍵字列表，但已存在！endl;return;5、 程序測試1. 先輸入要讀取的文件名，按Enter鍵提示文件讀取成功后繼續按Enter鍵，顯示哈希表的各個位置及其所存放的關鍵字和該關鍵字在此文件中出現的次數，如下圖：2.輸入想要查找的關鍵字，顯示該關鍵字在哈希表中的位置及其出現的次數，并顯示出所有C語言中的關鍵字和其在哈希表中的位置（每行4個，共32個），同時提示是否顯示沖突