利用哈希技術(shù)統(tǒng)計C源程序關(guān)鍵字出現(xiàn)頻度報告

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

2、00+(key的最后一個字母序號) MOD 413. 需求：（1） 首先要用一個二維數(shù)組存儲C源程序中的32個關(guān)鍵字。（2） 建立Hash表。（3） 在Hash表中找到相應(yīng)的位置存放關(guān)鍵字。（4） 讀取某個C文件，并統(tǒng)計出現(xiàn)的每個關(guān)鍵字在Hash表中存放的位置及在文件中出現(xiàn)的次數(shù)。（5） 輸入文件中出現(xiàn)的任意一個關(guān)鍵字，顯示在Hash表中存放的位置及在文件中出現(xiàn)的次數(shù)。（6） 顯示C源程序中所有關(guān)鍵字在Hash表中的位置。（7） 顯示所有沖突關(guān)鍵字列表。2、 總體設(shè)計3、 詳細(xì)設(shè)計1.創(chuàng)建一個哈希表類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.構(gòu)造二

4、維數(shù)組存儲32個關(guān)鍵字：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.各個數(shù)據(jù)成員及成員函數(shù)的功能：數(shù)據(jù)成員： keywordMAXLEN 存放

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

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

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

8、函數(shù)GetKey(keyword)計算出關(guān)鍵字在哈希表中應(yīng)存放的位置，看看是否是該關(guān)鍵字，若是（即不存在沖突），返回此哈希表的位置，否則（存在沖突），依次往后查找，直到找到相應(yīng)的關(guān)鍵字，如果到哈希表的表尾仍未找到該關(guān)鍵字，則重新從哈希表的第一個位置依次往后查找，直到找到為止。 4、 實現(xiàn)部分#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關(guān)鍵字不存在!endl;return;if(strlen(HSkey.keyword)=0)cout哈希表位置：key 記錄是空的endl;return ;cout哈希表位置: key 關(guān)鍵字: HSkey.keyword 出現(xiàn)次數(shù) 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文件不存在,請確認(rèn)好再輸入!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讀取成功，文件中關(guān)鍵字已經(jīng)存入hash表

18、，請繼續(xù)操作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關(guān)鍵字總數(shù)為：contendl; coutword; coutendl;hash.Show(hash.FindHX(word); cout C語言中的關(guān)鍵字和其在哈希表的位置: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沖突關(guān)鍵字列表endl; for(i=0;i0)key=hash.GetKey(HSi.keyword);if(key!=i)count+;coutsetiosflags(ios:left)setw(14) t關(guān)鍵 字:HSi.keywordsetiosflags(ios:left) setw(20)t哈希表當(dāng)前位置:

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