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

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

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

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

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

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

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

8、非常關(guān)鍵的一步，其中要考慮的因素很多。，如“//…….”,“/*….*/”,“”…..”” 注釋符號(hào)內(nèi)出現(xiàn)的關(guān)鍵字不算，甚至?xí)霈F(xiàn)注釋符號(hào)嵌套，還有關(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存儲(chǔ)關(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 順序存儲(chǔ)關(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)計(jì)的功能</p><p>　　createHash();建立hash表</p><p>　　HashSearch();讀入文件，進(jìn)行hash查找統(tǒng)計(jì)</p><p>　　Print_HSR();輸出Hash查找統(tǒng)計(jì)的結(jié)果</p><p>　　Hash_BackToOrigin();//在重新讀入文件時(shí)，把Hash表狀態(tài)回到最初

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

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

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

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

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