課程設(shè)計報告---關(guān)鍵字統(tǒng)計程序

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告</p><p>　　——利用Hash技術(shù)和二分查找技術(shù)統(tǒng)計某個c程序中關(guān)鍵字出現(xiàn)的頻度</p><p><b>　　班級：06級5班</b></p><p><b>　　目錄</b></p><p>　　1．題目----------------------

2、--------------------- -3</p><p>　　2．算法思想----------------------------------------3</p><p>　　3．程序結(jié)構(gòu)----------------------------------------3 </p><p>　　4．測試結(jié)果--------------------------

3、--------------6 </p><p>　　5．收獲與體會--------------------------------------7 </p><p><b>　　題目</b></p><p>　　掃描c源程序，利用hash技術(shù)和二分查找技術(shù)統(tǒng)計該源程序中的關(guān)鍵字出現(xiàn)的頻度，并比較各自查找的次數(shù)。</p><p

4、>　?。?）、先用Hash表存儲c語言中32個關(guān)鍵字，再掃描c源程序取出每個單詞，利用Hash查找技術(shù)統(tǒng)計該程序中的關(guān)鍵字出現(xiàn)的頻度。發(fā)生Hash沖突用線性探測法解決。設(shè)Hash函數(shù)為：</p><p>　　Hash（key）=[(key的第一個字母序號)*100+(key的最后一個字母序號)] MOD 41。</p><p>　?。?）、用順序表存儲c語言中的關(guān)鍵字，把c源程序取出

5、每個單詞利用二分查找技術(shù)統(tǒng)計該程序中的關(guān)鍵字的出現(xiàn)頻度。</p><p><b>　　算法思想</b></p><p><b>　　Hash表的建立</b></p><p>　　首先按照c語言中關(guān)鍵字（共32個），根據(jù)Hash函數(shù)：Hash（key）=[(key的第一個字母序號)*100+(key的最后一個字母序

6、號)] MOD 41，申請一個類數(shù)組，長度為41，類中有一個string型 用來存儲關(guān)鍵字和int類型用來存儲出現(xiàn)的頻率，并初始化為0。</p><p><b>　　Hash沖突解決</b></p><p>　　用線性探測法解決。把整個數(shù)組看成一個循環(huán)的數(shù)組，當發(fā)生沖突時，從發(fā)生沖突的位置的下一個位置起，依次尋找空的散列地址,再把關(guān)鍵字存入。</p>&

7、lt;p><b>　　順序表的建立</b></p><p>　　二分查找要求所查的關(guān)鍵字必須有序，所以按照關(guān)鍵字的大小從小到大排列（用string類型直接比較）。c語言中關(guān)鍵字共32個，故定數(shù)組長度為32。排序方法采用插入排序。</p><p><b>　　文件的讀入</b></p><p>　　要從文件中讀取單詞是

8、非常關(guān)鍵的一步，其中要考慮的因素很多。，如“//…….”,“/*….*/”,“”…..”” 注釋符號內(nèi)出現(xiàn)的關(guān)鍵字不算，甚至?xí)霈F(xiàn)注釋符號嵌套，還有關(guān)鍵字和數(shù)字、下劃線、大寫字母相連，故應(yīng)特殊考慮。具體查看代碼。</p><p><b>　　程序結(jié)構(gòu)</b></p><p><b>　　程序中的一些變量：</b></p><p

9、>　　KeyHash KeysHashList[41] 存放關(guān)鍵字的Hash表，用于Hash查找</p><p>　　int HashCount=0 記錄Hash查找的比較次數(shù)</p><p>　　KeyBin KeysBinList[32] 存放關(guān)鍵字的順序表，用于二分查找</p><p>　　int BinCount=0

10、 記錄二分查找的次數(shù)</p><p>　　class KeyHash Hash存儲關(guān)鍵字的類</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　KeyHash() { freq=0; }初始化此關(guān)鍵字出現(xiàn)的頻率

11、為0</p><p>　　string kw; 記錄此關(guān)鍵字</p><p>　　int freq; 記錄此關(guān)鍵字出現(xiàn)的頻率</p><p><b>　　};</b></p><p>　　class KeyBin 順序存儲關(guān)鍵字的類</p>

12、<p><b>　　{</b></p><p><b>　　public:</b></p><p>　　KeyBin() { freq=0; }初始化此關(guān)鍵字出現(xiàn)的頻率為0</p><p>　　string kw; 記錄此關(guān)鍵字</p><p>　　int freq; 記

13、錄此關(guān)鍵字出現(xiàn)的頻率</p><p><b>　　};</b></p><p><b>　　程序中的函數(shù)：</b></p><p>　　1、main.cpp文件：</p><p>　　main()函數(shù)，為主函數(shù)，調(diào)用其他函數(shù)。</p><p>　　2、Hash.h文件:包含關(guān)

14、于hash查找統(tǒng)計的功能</p><p>　　createHash();建立hash表</p><p>　　HashSearch();讀入文件，進行hash查找統(tǒng)計</p><p>　　Print_HSR();輸出Hash查找統(tǒng)計的結(jié)果</p><p>　　Hash_BackToOrigin();//在重新讀入文件時，把Hash表狀態(tài)回到最初

15、狀態(tài)</p><p>　　3、Binary.h文件: 包含關(guān)于二分查找統(tǒng)計的功能</p><p>　　createBin();建立順序表</p><p>　　BinSearch();讀入文件，進行二分查找統(tǒng)計</p><p>　　Print_BSR();輸出二分查找統(tǒng)計的結(jié)果</p><p>　　Bin_BackToO

16、rigin();//在重新讀入文件時，把順序表狀態(tài)回到最初狀態(tài)</p><p><b>　　程序結(jié)構(gòu)圖:</b></p><p><b>　　程序中的函數(shù)關(guān)系:</b></p><p><b>　　測試結(jié)果</b></p><p>　　用program.txt測試結(jié)果：<

17、/p><p>　　Hash查找統(tǒng)計 </p><p><b>　　二分查找統(tǒng)計</b></p><p>　　用program2.txt測試結(jié)果：</p><p><b>　　Hash查找統(tǒng)計</b></p><p><b>　　二分查找統(tǒng)計</b><

18、;/p><p><b>　　收獲與體會</b></p><p>　　通過這次課程設(shè)計讓我對Hash查找技術(shù)和二分查找技術(shù)有了更加深刻的認識和理解。</p><p>　　Hash技術(shù)把關(guān)鍵碼通過散列函數(shù)計算出Key，直接得到關(guān)鍵碼的存儲地址，大大提高了查找效率。但它也并非完美，用Hash表存儲關(guān)鍵碼時容易產(chǎn)生沖突，盡管用線性探測法可以解決，但隨之產(chǎn)生

19、了堆積，堆積會大大的降低查找效率，甚至效率會大大的低于二分查找。找到一個好的Hash函數(shù)，使得元素在hash表里分布更均勻，這樣才能減少沖突的產(chǎn)生，進而提高Hash查找的效率。而二分查找要求順序表中的關(guān)鍵碼必須排列有序，只能應(yīng)用于靜態(tài)查找。</p><p>　　可以說兩種查找技術(shù)各有優(yōu)缺，具體看應(yīng)用的環(huán)境，盡量揚長避短。</p><p>　　其次通過此次課程設(shè)計我也發(fā)現(xiàn)了自己寫程序上的一些