Hash沖突并統(tǒng)計關(guān)鍵字的頻率.doc

Hash沖突并統(tǒng)計關(guān)鍵字的頻率數(shù)據(jù)結(jié)構(gòu)實驗報告一、 問題掃描一個C源程序，用Hash表存儲該程序中出現(xiàn)的關(guān)鍵字，并統(tǒng)計該程序中的關(guān)鍵字出現(xiàn)頻度。用線性探測法解決Hash沖突。設(shè)Hash函數(shù)為：Hash(key)=(key的第一個字母序號)*100+(key的最后一個字母序號) MOD 41二、 算法思想描述.c文件提取單詞查找統(tǒng)計顯示1. 總體思路圖1 總體思路2. 細節(jié)描述(1) 創(chuàng)建Hash表所有的關(guān)鍵字已經(jīng)寫入了名為guanjianzi.txt的文件中，通過提取單詞，將所有的關(guān)鍵字插入Hash表中。本程序采用開放地址法解決Hash沖突。關(guān)鍵字共有32個：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, volatile(2) 掃描某C文件在a.c文件中提取出單詞，判斷是否為關(guān)鍵字，若是則統(tǒng)計加一，直至文件結(jié)束。提取單詞：根據(jù)單詞都是由連在一起的字母組成這一原理，用語句while( (cz) & (c!=EOF) ) c=fgetc(ft); 跳過非字母的字符。當讀到字母時，用while( c=a & c=z )st.chi=c;c=fgetc(ft);i+;將所有連在一起的字母存在st.ch數(shù)組中，在進行下一步操作。在提取單詞時，為了實現(xiàn)在注釋內(nèi)的關(guān)鍵字不計，用以下代碼實現(xiàn)：if(c=/) c=fgetc(ft);if(c=/) / /后的不計doc=fgetc(ft);while(c!=10);if(c=*)doc=fgetc(ft);if(c=*) / /* */后的不計c=fgetc(ft);if(c=/)break;else continue;while(1);(3) 顯示Hash表通過循環(huán)顯示出a.c文件中所包含的關(guān)鍵字，及其哈希地址和出現(xiàn)頻度。輸出時過濾沒有出現(xiàn)的（頻度為0）的關(guān)鍵字。3. 流程圖判斷是否為關(guān)鍵字SearchHash(.)Y統(tǒng)計加1 開 始讀文件guanjianzi.txt文件是否結(jié)尾N 提取關(guān)鍵字單詞插入關(guān)鍵字至Hash表InsertHash(.)掃描a.c文件文件是否結(jié)尾YNY提取單詞N輸出Hash表結(jié) 束Create()Scan()PrintHash()main()圖2 流程圖三、 程序結(jié)構(gòu)1. 數(shù)據(jù)結(jié)構(gòu)typedef struct char ch10; /關(guān)鍵字int num; /該關(guān)鍵字出現(xiàn)次數(shù)HSTable;HSTable HTMAXSIZE;HT 為一維數(shù)組表示的哈希表。2. 函數(shù)調(diào)用層次結(jié)構(gòu)main函數(shù)Create函數(shù)Scan函數(shù)PrintHash函數(shù)InsertHash函數(shù)SearchHash函數(shù)調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用H函數(shù)（求Hash地址）調(diào)用圖3 函數(shù)調(diào)用層次結(jié)構(gòu)3. 函數(shù)功能說明Create函數(shù)：創(chuàng)建Hash表Scan函數(shù)：掃描某文件，統(tǒng)計其中各關(guān)鍵字出現(xiàn)次數(shù)PrintHash函數(shù)：顯示Hash表InsertHash函數(shù)：將一個單詞作為關(guān)鍵字插入Hash表中SearchHash函數(shù)：在Hash表中查找是否包含某個單詞，即查找該單詞是否為關(guān)鍵字。H函數(shù)：計算某單詞的Hash地址。依據(jù)函數(shù)Hash(key)=(key的第一個字母序號)*100+(key的最后一個字母序號) MOD 41四、 測試結(jié)果與分析上述程序在Visual C+ 6.0環(huán)境下加以實現(xiàn)。經(jīng)過多次測試，程序運行正確。例如：輸入C程序 a.c，運行結(jié)果如圖4所示，圖中顯示了文件a.c所包含的關(guān)鍵字及其個數(shù)。圖4 運行結(jié)果五、 收獲與體會通過這次課程設(shè)計:1. 我又進一步鞏固了C語言的基礎(chǔ)，尤其是文件那部分。2. 通過程序加深了對Hash查找方面知識的認識。更深一層次了解了Hash查找的優(yōu)缺點。3. 做課程設(shè)計達