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

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

2、是一種數(shù)組，可以用任意簡(jiǎn)單變量值來(lái)訪問其元素，這種數(shù)組叫做關(guān)聯(lián)數(shù)組，也叫哈希表。值對(duì)的集合。理想的情況下是希望不經(jīng)過(guò)任何比較，一次存儲(chǔ)就能得到所查到的記錄，那就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。基本要求：使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素?？梢栽O(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)，也叫做散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)，hash值）存在一一對(duì)應(yīng)的關(guān)系，于是用這個(gè)數(shù)組單元來(lái)存儲(chǔ)這個(gè)元素。使用hash表存儲(chǔ)關(guān)鍵字時(shí)難免會(huì)有不同的關(guān)鍵字對(duì)應(yīng)同一關(guān)鍵碼的情況，因此必須有個(gè)處理沖突的辦法。hash函數(shù)：hash(k

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

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

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

6、ternot(ch)=1&feof(read)=0)if(i=maxlength)while(letternot(ch)=1&feof(read)=0)ch=fgetc(read); /超過(guò)maxlen的長(zhǎng)度則一定不為關(guān)鍵字，把余下連一起的字母都讀取i=0;break;elsewordi+=ch; /把讀取到的字母存入word數(shù)組中ch=fgetc(read);wordi=0;if(keywordsnot(word)creathash(word);fclose(read);coutendl文件中關(guān)鍵字已經(jīng)存入表中，請(qǐng)繼續(xù)!endlendlendl;在hash表中查找關(guān)鍵字找出關(guān)鍵字位置：int

7、 findhash(char *keyword) /在hash表中查找關(guān)鍵字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否關(guān)鍵字return -1;key=gethashvalue(keyword);if(strcmp(testkey.keyword,keyword)=0)return key;for(find=key+1;findlengthofhash;find+) /線性探測(cè)法findcoll+; /findcoll統(tǒng)計(jì)沖突次數(shù)if(strcmp(testfind.keyword,keyword)=0)testfind.coll=

8、findcoll; /把沖突次數(shù)存入collreturn find;for(find=0;find0) /hash表中該位置存在關(guān)鍵字 if(strcmp(testkey.keyword,keyword)=0) /hash表中該位置的關(guān)鍵字相同 testkey.count+; /頻度加1return 1; /跳出函數(shù)key=findhash(keyword); /不相同，繼續(xù)查找if(key0) /沒有找到相等的keywordkey=insert(gethashvalue(keyword);if(key0) /hash表滿或者計(jì)算的hash值有問題return -1;strcpy(testke

9、y.keyword,keyword); /將關(guān)鍵字插入hash表if(key0)return -1;testkey.count+;else /該位置沒有關(guān)鍵字strcpy(testkey.keyword,keyword);testkey.count+;return 1;在hash表中插入關(guān)鍵字：int insert(int key) /在hash表中插入關(guān)鍵字int find,findcoll=0;if(key=lengthofhash) return -1;for(find=key+1;findlengthofhash;find+) /分塊查找后部分findcoll+;if(strlen(t

10、estfind.keyword)=0) /若這個(gè)地方為空 testfind.coll=findcoll; /把沖突的次數(shù)存入coll中 return find; for(find=0;findkey;find+) /分塊在前部分查找findcoll+;if(strlen(testfind.keyword)=0)testfind.coll=findcoll;return find;return -1; /hash表已滿四、算法的實(shí)現(xiàn)a)引用庫(kù)函數(shù)定義變量#include #include #include #include using namespace std;const int length

11、ofhash=41; /hash表長(zhǎng)度int keycount=0; /統(tǒng)計(jì)hash表中的關(guān)鍵字總數(shù)const int total=38; /38個(gè)關(guān)鍵字const int maxlength=20; char keywordstotalmaxlength= /列舉38個(gè)關(guān)鍵字bool,break,case,catch,char,class,const,continue,default,do,double,else,enum,extern,false,float,for,goto,if,int,interrupt,long,new,private,public,register,return,

12、short,signed,sizeof,static,struct,switch,typedef,union,unsigned,void,while,;b)類的構(gòu)造及類的對(duì)象class conuntnum public:int coll; /collision沖突次數(shù)int count; /出現(xiàn)次數(shù)（頻度）char keywordmaxlength; conuntnum testlengthofhash;c)函數(shù)的聲明部分void menu();void printscreen(int key);int open(char *filename); int letternot(char ch);

13、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表中查找關(guān)鍵字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否關(guān)鍵字return -1;五、源代碼#include #include #include #include usi

14、ng namespace std;const int lengthofhash=41; /hash表長(zhǎng)度int keycount=0; /統(tǒng)計(jì)hash表中的關(guān)鍵字總數(shù)const int total=38; /38個(gè)關(guān)鍵字const int maxlength=20; char keywordstotalmaxlength= /列舉38個(gè)關(guān)鍵字bool,break,case,catch,char,class,const,continue,default,do,double,else,enum,extern,false,float,for,goto,if,int,interrupt,long,ne

15、w,private,public,register,return,short,signed,sizeof,static,struct,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); int

16、 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(); cinopt;switch(opt) case 1:system(cls);

17、coutfilename;open(filename); coutendl; continue;break; case 2: system(cls);cout按回車鍵繼續(xù)顯示！endl;for(i=0;ilengthofhash;i+) printscreen(i); if(i+1)%10=0)getchar(); /10行一循環(huán) coutcpp文件中關(guān)鍵字總數(shù)為:keycountendl;coutendlendlendlendlendl;continue; system(cls); break;case 3:system(cls); cout沖突關(guān)鍵字列表:endlendl; count=0

18、; for(i=0;i0) key=gethashvalue(testi.keyword); if(key!=i) count+; coutt關(guān)鍵字testi.keyword; coutthash表當(dāng)前位置:i; coutt沖突次數(shù):testi.collendl; if(count=0) cout沒有沖突endlendlendlendlendl; else coutendlttt沖突關(guān)鍵字共:count個(gè)endl;coutendlendlendlendlendl;continue; system(cls); break; case 4:system(cls);cout輸入你想要查找的關(guān)鍵字：

19、word; coutendl; printscreen(findhash(word);coutendl;continue; system(cls); break; case 5:option=0;break;default: system(cls);int open(char *filename)char wordmaxlength,ch;int i;file *read; /指向file類的指針*read if(read=fopen(filename,r)=null) /只讀方式讀取文件，如果為空coutendl未找到要打開的文件,請(qǐng)重新輸入!;return -1; /跳出open函數(shù)whi

20、le(!feof(read) /判斷文件是否結(jié)束，到末尾函數(shù)值為“真”即非0i=0;ch=fgetc(read); /讀取一個(gè)字符while(letternot(ch)=0&feof(read)=0)ch=fgetc(read); /如果不是字母就接著讀取,關(guān)鍵字都是由字母組成的while(letternot(ch)=1&feof(read)=0)if(i=maxlength)while(letternot(ch)=1&feof(read)=0)ch=fgetc(read); /超過(guò)maxlen的長(zhǎng)度則一定不為關(guān)鍵字，把余下連一起的字母都讀取i=0;break;elsewordi+=ch; /

21、把讀取到的字母存入word數(shù)組中ch=fgetc(read);wordi=0;if(keywordsnot(word)creathash(word);fclose(read);coutendl文件中關(guān)鍵字已經(jīng)存入表中，請(qǐng)繼續(xù)!endlendl=a&ch=a&ch=z)return 1; elsereturn 0; int findhash(char *keyword) /在hash表中查找關(guān)鍵字int key,find,findcoll=0;if(!keywordsnot(keyword) /是否關(guān)鍵字return -1;key=gethashvalue(keyword);if(strcmp(

22、testkey.keyword,keyword)=0)return key;for(find=key+1;findlengthofhash;find+) /線性探測(cè)法findcoll+; /findcoll統(tǒng)計(jì)沖突次數(shù)if(strcmp(testfind.keyword,keyword)=0)testfind.coll=findcoll; /把沖突次數(shù)存入collreturn find;for(find=0;find0) /hash表中該位置存在關(guān)鍵字 if(strcmp(testkey.keyword,keyword)=0) /hash表中該位置的關(guān)鍵字相同 testkey.count+;

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

24、insert(int key) /在hash表中插入關(guān)鍵字int find,findcoll=0;if(key=lengthofhash) return -1;for(find=key+1;findlengthofhash;find+) /分塊查找后部分findcoll+;if(strlen(testfind.keyword)=0) /若這個(gè)地方為空 testfind.coll=findcoll; /把沖突的次數(shù)存入coll中 return find; for(find=0;findkey;find+) /分塊在前部分查找findcoll+;if(strlen(testfind.keyword)=0)testfind.coll=findcoll;return find;return -1; /hash表已滿int keywordsnot(char *word) /判斷是否關(guān)鍵字int i;for(i=0;itotal;i+)if(strcmp(word,keyw