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

1、 數(shù)據(jù)結構與算法課程設計報告 題目：利用哈希技術統(tǒng)計c源程序關鍵字出現(xiàn)頻度 學生姓名： 學 號： _ 班 級： _ 指導教師： _ 2012年 6 月 18 日利用哈希技術統(tǒng)計c源程序關鍵字出現(xiàn)頻度(1)題目內(nèi)容：利用hash技術統(tǒng)計某個c源程序中的關鍵字出現(xiàn)的頻度(2)基本要求：掃描一個c源程序，用hash表存儲該程序中出現(xiàn)的關鍵字，并統(tǒng)計該程序中的關鍵字出現(xiàn)的頻度。用線性探測法解決hash沖突。設hash函數(shù)為：hash(key)(key的第一個字母序號)*100+(key的最后一個字母序號) mod 41 一、對題目的分析哈希表是為了便于快速搜索而組織的值組合的集合。hash table

2、是一種數(shù)組，可以用任意簡單變量值來訪問其元素，這種數(shù)組叫做關聯(lián)數(shù)組，也叫哈希表。值對的集合。理想的情況下是希望不經(jīng)過任何比較，一次存儲就能得到所查到的記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使每個關鍵字和結構中一個唯一的存儲位置相對應?；疽螅菏褂靡粋€下標范圍比較大的數(shù)組來存儲元素。可以設計一個函數(shù)（哈希函數(shù)，也叫做散列函數(shù)），使得每個元素的關鍵字都與一個函數(shù)值（即數(shù)組下標，hash值）存在一一對應的關系，于是用這個數(shù)組單元來存儲這個元素。使用hash表存儲關鍵字時難免會有不同的關鍵字對應同一關鍵碼的情況，因此必須有個處理沖突的辦法。hash函數(shù)：hash(k

3、ey)(key的第一個字母序號)*100+(key的最后一個字母序號) mod 41 二、處理沖突的方法處理沖突的辦法線性探測法用線性探法解決沖突時，把有沖突的關鍵字往后推移直到有空位置的關鍵碼時再插入到hash表中。c語言關鍵字: c語言關鍵字是c語言的保留的一些單詞，這些單詞都有了固定的意義和用途，不可以作為變量或者自定義類型或類名來使用。其特點是都有小寫字母構成。c語言關鍵字有哪些：double int structbreakelselongswitch caseenumregistercharextern returnunionconstfloatshortunsignedcontin

4、uefor signedvoiddefaultgotosizeofvolatiledowhilestaticifautocase定義一個多維數(shù)組，數(shù)組第一行存放關鍵字，數(shù)組第二行存儲hash函數(shù)處理后關鍵字結點地址，用hash函數(shù)存儲關鍵字hash(key)=(key第一個字符在1-26個字母中的序號)*100+(key最后一個字符在1-26個字母中的序號)%41如此得到如for對應地址3，if對應于地址4，int對應地址18等等。哈希表 h(key)=keymod41 處理沖突為線性探測再散列。 三、算法設計及部分函數(shù)打開含關鍵字的cpp文件：int open(char *filename)

5、char wordmaxlength,ch;int i;file *read; /指向file類的指針*read if(read=fopen(filename,"r")=null) /只讀方式讀取文件，如果為空cout<<endl<<"未找到要打開的文件,請重新輸入!"return -1; /跳出open函數(shù)while(!feof(read) /判斷文件是否結束，到末尾函數(shù)值為“真”即非0i=0;ch=fgetc(read); /讀取一個字符while(letternot(ch)=0&&feof(read)=0)c

6、h=fgetc(read); /如果不是字母就接著讀取,關鍵字都是由字母組成的while(letternot(ch)=1&&feof(read)=0)if(i=maxlength)while(letternot(ch)=1&&feof(read)=0)ch=fgetc(read); /超過maxlen的長度則一定不為關鍵字，把余下連一起的字母都讀取i=0;break;elsewordi+=ch; /把讀取到的字母存入word數(shù)組中ch=fgetc(read);wordi='0'if(keywordsnot(word)creathash(word)

7、;fclose(read);cout<<endl<<"文件中關鍵字已經(jīng)存入表中，請繼續(xù)!"<<endl<<endl<<endl;在hash表中查找關鍵字找出關鍵字位置：int findhash(char *keyword) /在hash表中查找關鍵字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否關鍵字return -1;key=gethashvalue(keyword);if(strcmp(testkey.keyword,keyword)=0)return

8、key;for(find=key+1;find<lengthofhash;find+) /線性探測法findcoll+; /findcoll統(tǒng)計沖突次數(shù)if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll; /把沖突次數(shù)存入collreturn find;for(find=0;find<key;find+) /后面的找不到再從前面開始找findcoll+;if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll;return find;return -

9、1;建立hash表：int creathash(char *keyword) /建立hash表,keyword是一個數(shù)組int key;if(!keywordsnot(keyword) /判斷是否關鍵字return -1; key=gethashvalue(keyword); /計算hash值if(strlen(testkey.keyword)>0) /hash表中該位置存在關鍵字 if(strcmp(testkey.keyword,keyword)=0) /hash表中該位置的關鍵字相同 testkey.count+; /頻度加1return 1; /跳出函數(shù)key=findhash(

10、keyword); /不相同，繼續(xù)查找if(key<0) /沒有找到相等的keywordkey=insert(gethashvalue(keyword);if(key<0) /hash表滿或者計算的hash值有問題return -1;strcpy(testkey.keyword,keyword); /將關鍵字插入hash表if(key<0)return -1;testkey.count+;else /該位置沒有關鍵字strcpy(testkey.keyword,keyword);testkey.count+;return 1;在hash表中插入關鍵字：int insert(i

11、nt key) /在hash表中插入關鍵字int find,findcoll=0;if(key<0|key>=lengthofhash) return -1;for(find=key+1;find<lengthofhash;find+) /分塊查找后部分findcoll+;if(strlen(testfind.keyword)=0) /若這個地方為空 testfind.coll=findcoll; /把沖突的次數(shù)存入coll中 return find; for(find=0;find<key;find+) /分塊在前部分查找findcoll+;if(strlen(tes

12、tfind.keyword)=0)testfind.coll=findcoll;return find;return -1; /hash表已滿四、算法的實現(xiàn)a)引用庫函數(shù)定義變量#include <iostream.h> #include <string>#include <iomanip.h>#include <conio.h>using namespace std;const int lengthofhash=41; /hash表長度int keycount=0; /統(tǒng)計hash表中的關鍵字總數(shù)const int total=38; /38個

13、關鍵字const int maxlength=20; char keywordstotalmaxlength= /列舉38個關鍵字"bool","break","case","catch","char","class","const","continue","default","do","double","else","enum",&qu

14、ot;extern","false","float","for","goto","if","int","interrupt","long","new","private","public","register","return","short","signed","sizeof&

15、quot;,"static","struct","switch","typedef","union","unsigned","void","while",;b)類的構造及類的對象class conuntnum public:int coll; /collision沖突次數(shù)int count; /出現(xiàn)次數(shù)（頻度）char keywordmaxlength; conuntnum testlengthofhash;c)函數(shù)的聲明部分void

16、menu();void printscreen(int key);int open(char *filename); int letternot(char ch);int keywordsnot(char *word);int findhash(char *keyword);int creathash(char *keyword);int insert(int key);int gethashvalue(char *keyword);d)在hash表中分塊查找int findhash(char *keyword) /在hash表中查找關鍵字int key,find,findcoll=0;if(

17、!keywordsnot(keyword) /是否關鍵字return -1;五、源代碼#include <iostream.h> #include <string>#include <iomanip.h>#include <conio.h>using namespace std;const int lengthofhash=41; /hash表長度int keycount=0; /統(tǒng)計hash表中的關鍵字總數(shù)const int total=38; /38個關鍵字const int maxlength=20; char keywordstotalm

18、axlength= /列舉38個關鍵字"bool","break","case","catch","char","class","const","continue","default","do","double","else","enum","extern","false","float&

19、quot;,"for","goto","if","int","interrupt","long","new","private","public","register","return","short","signed","sizeof","static","struct",&q

20、uot;switch","typedef","union","unsigned","void","while",;class conuntnum public:int coll; /collision沖突次數(shù)int count; /出現(xiàn)次數(shù)（頻度）char keywordmaxlength; conuntnum testlengthofhash;/先聲明后使用void menu();void printscreen(int key);int open(char *filename);

21、int letternot(char ch);int keywordsnot(char *word);int findhash(char *keyword);int creathash(char *keyword);int insert(int key);int gethashvalue(char *keyword);void main() char opt; int option=1,i,count,key,has;char filename50,wordmaxlength; while(option) menu(); cin>>opt;switch(opt) case '

22、;1':system("cls"); cout<<"請輸入文件名:"cin>>filename;open(filename); cout<<endl; continue;break; case '2': system("cls");cout<<"按回車鍵繼續(xù)顯示！"<<endl;for(i=0;i<lengthofhash;i+) printscreen(i); if(i+1)%10=0)getchar(); /10行一循環(huán)

23、cout<<"cpp文件中關鍵字總數(shù)為:"<<keycount<<endl;cout<<endl<<endl<<endl<<endl<<endl;continue; system("cls"); break;case '3':system("cls"); cout<<"沖突關鍵字列表:"<<endl<<endl; count=0; for(i=0;i<length

24、ofhash;i+) if(strlen(testi.keyword)>0) key=gethashvalue(testi.keyword); if(key!=i) count+; cout<<"t關鍵字"<<testi.keyword; cout<<"thash表當前位置:"<<i; cout<<"t沖突次數(shù):"<<testi.coll<<endl; if(count=0) cout<<"沒有沖突"<<

25、;endl<<endl<<endl<<endl<<endl; else cout<<endl<<"ttt沖突關鍵字共:"<<count<<"個"<<endl;cout<<endl<<endl<<endl<<endl<<endl;continue; system("cls"); break; case '4':system("cls")

26、;cout<<"輸入你想要查找的關鍵字： "<<endl; cin>>word; cout<<endl; printscreen(findhash(word);cout<<endl;continue; system("cls"); break; case '5':option=0;break;default: system("cls");int open(char *filename)char wordmaxlength,ch;int i;file *read

27、; /指向file類的指針*read if(read=fopen(filename,"r")=null) /只讀方式讀取文件，如果為空cout<<endl<<"未找到要打開的文件,請重新輸入!"return -1; /跳出open函數(shù)while(!feof(read) /判斷文件是否結束，到末尾函數(shù)值為“真”即非0i=0;ch=fgetc(read); /讀取一個字符while(letternot(ch)=0&&feof(read)=0)ch=fgetc(read); /如果不是字母就接著讀取,關鍵字都是由字母組成

28、的while(letternot(ch)=1&&feof(read)=0)if(i=maxlength)while(letternot(ch)=1&&feof(read)=0)ch=fgetc(read); /超過maxlen的長度則一定不為關鍵字，把余下連一起的字母都讀取i=0;break;elsewordi+=ch; /把讀取到的字母存入word數(shù)組中ch=fgetc(read);wordi='0'if(keywordsnot(word)creathash(word);fclose(read);cout<<endl<<

29、"文件中關鍵字已經(jīng)存入表中，請繼續(xù)!"<<endl<<endl<<endl;int letternot(char ch) /判斷是否是字母if(ch>='a'&&ch<='z')|(ch>='a'&&ch<='z')return 1; elsereturn 0; int findhash(char *keyword) /在hash表中查找關鍵字int key,find,findcoll=0;if(!keywordsnot

30、(keyword) /是否關鍵字return -1;key=gethashvalue(keyword);if(strcmp(testkey.keyword,keyword)=0)return key;for(find=key+1;find<lengthofhash;find+) /線性探測法findcoll+; /findcoll統(tǒng)計沖突次數(shù)if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll; /把沖突次數(shù)存入collreturn find;for(find=0;find<key;find+) /后面的找不到再從

31、前面開始找findcoll+;if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll;return find;return -1;int creathash(char *keyword) /建立hash表,keyword是一個數(shù)組int key;if(!keywordsnot(keyword) /判斷是否關鍵字return -1; key=gethashvalue(keyword); /計算hash值if(strlen(testkey.keyword)>0) /hash表中該位置存在關鍵字 if(strcmp(testke

32、y.keyword,keyword)=0) /hash表中該位置的關鍵字相同 testkey.count+; /頻度加1return 1; /跳出函數(shù)key=findhash(keyword); /不相同，繼續(xù)查找if(key<0) /沒有找到相等的keywordkey=insert(gethashvalue(keyword);if(key<0) /hash表滿或者計算的hash值有問題return -1;strcpy(testkey.keyword,keyword); /將關鍵字插入hash表if(key<0)return -1;testkey.count+;else /該

33、位置沒有關鍵字strcpy(testkey.keyword,keyword);testkey.count+;return 1;int insert(int key) /在hash表中插入關鍵字int find,findcoll=0;if(key<0|key>=lengthofhash) return -1;for(find=key+1;find<lengthofhash;find+) /分塊查找后部分findcoll+;if(strlen(testfind.keyword)=0) /若這個地方為空 testfind.coll=findcoll; /把沖突的次數(shù)存入coll中

34、return find; for(find=0;find<key;find+) /分塊在前部分查找findcoll+;if(strlen(testfind.keyword)=0)testfind.coll=findcoll;return find;return -1; /hash表已滿int keywordsnot(char *word) /判斷是否關鍵字int i;for(i=0;i<total;i+)if(strcmp(word,keywordsi)=0)return 1;return 0;void printscreen(int key) if(key<0|key>=lengthofhash)cout<<"關鍵字不存在!"<<endl