數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告---利用hash技術(shù)統(tǒng)計單詞的頻度

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告</p><p><b>　　一.課程設(shè)計題目：</b></p><p>　　利用Hash技術(shù)統(tǒng)計單詞的頻度</p><p><b>　　二．具體要求：</b></p><p>　　利用Hash技術(shù)統(tǒng)計某個C源程序中的關(guān)鍵字出現(xiàn)的頻度</p>

2、<p>　　掃描C源程序，用HASH表存儲該程序中出現(xiàn)的關(guān)鍵字，并統(tǒng)計該程序中的關(guān)鍵字出現(xiàn)的頻度，用線性探測法解決沖突，設(shè)HASH函數(shù)為：</p><p>　　Hash(key)=[(key的第一個字母序號)*100+（key的最后一個字母序號）] mod 41</p><p><b>　　三.算法思想:</b></p><p>

3、<b>　　1、數(shù)據(jù)結(jié)構(gòu)設(shè)計</b></p><p><b>　　①關(guān)鍵字表的結(jié)構(gòu)</b></p><p>　　struct data1</p><p><b>　　{</b></p><p>　　char words[10]; //關(guān)鍵字</p><

4、;p>　　int exist; //位置是否為空標(biāo)記</p><p>　　int hashnum; //假設(shè)不沖突計算出的key值,調(diào)試用 </p><p><b>　　};</b></p><p>　?、贖ash表中的結(jié)點(diǎn)結(jié)構(gòu)</p><p>　　struct data2&l

5、t;/p><p><b>　　{</b></p><p>　　char words[10];</p><p>　　int exist; //位置是否為空標(biāo)記 </p><p>　　int freq;

6、 //頻度</p><p>　　int clash_count; //沖突次數(shù)</p><p><b>　　};</b></p><p><b>　　2、功能設(shè)計</b&

7、gt;</p><p><b>　　具體算法:</b></p><p>　　1.先對給定的關(guān)鍵字用hash技術(shù)建一個hash表;</p><p>　　2.從一個大字符串中分解單詞;計算該單詞的key值;</p><p>　　單詞：由非字母分隔開的連續(xù)字母串</p><p>　　3.識別是否是關(guān)鍵詞

8、, </p><p>　　到關(guān)鍵字Hash表查找 //關(guān)鍵字表沖突越少.效率越高</p><p>　　是則插入hash表,不是繼續(xù)讀取數(shù)據(jù)</p><p>　　4.插入Hash表，或調(diào)整Hash表項(xiàng)中的頻度</p><p>　　5 文件讀取完畢則執(zhí)行6,否則轉(zhuǎn)至2;</p><p>　　6輸出Hash表，關(guān)鍵

9、詞總數(shù)，沖突次數(shù);</p><p><b>　　3.函數(shù)申明:</b></p><p>　　1.void List();</p><p>　　掃描關(guān)鍵字文件.新建一個關(guān)鍵字hash表;</p><p><b>　　關(guān)鍵字hash表:</b></p><p>　　***利用ha

10、sh技術(shù)存儲c語言關(guān)鍵字******</p><p>　　case038</p><p>　　switch11</p><p>　　enum20</p><p>　　near33</p><p>　　cdecl44</p&g

11、t;<p>　　huge55</p><p>　　extern61</p><p>　　int738</p><p>　　union82</p><p>　　continue938</p><p>　　asm

12、1010</p><p>　　void1110</p><p>　　volatile1211</p><p>　　struct1313</p><p>　　char1410</p><p>　　double1515&l

13、t;/p><p>　　const1612</p><p>　　typedef1717</p><p>　　short1813</p><p>　　interrupt1938</p><p>　　signed2038</p&

14、gt;<p><b>　　0</b></p><p><b>　　0</b></p><p>　　for2323</p><p>　　if2424</p><p>　　float2525</p><p&

15、gt;　　break2626</p><p>　　do2725</p><p>　　far2823</p><p>　　while2929</p><p>　　default3030</p><p>　　return3

16、130</p><p><b>　　320</b></p><p>　　pascal3333</p><p>　　else3433</p><p>　　register3534</p><p>　　unsigned36

17、33</p><p>　　static3737</p><p>　　goto3838</p><p>　　long3938</p><p>　　sizeof4040</p><p>　　2.void File_func();</p&g

18、t;<p>　　掃描目標(biāo)文件.建立hash表.統(tǒng)計關(guān)鍵字出現(xiàn)的頻度,沖突次數(shù);</p><p><b>　　比如2.txt</b></p><p>　　關(guān)鍵字表及其出現(xiàn)頻度</p><p>　　關(guān)鍵字出現(xiàn)頻度在hash表中的位置沖突次數(shù)</p><p>　　switch11

19、0</p><p>　　char6100</p><p>　　void4114</p><p>　　struct4130</p><p>　　typedef1170</p><p>　　fo

20、r3230</p><p>　　if9240</p><p>　　do1250</p><p>　　break7260</p><p>　　while3290</p><p

21、>　　return6300</p><p>　　else3330</p><p>　　int10380</p><p>　　case7397</p><p>　　sizeof5400<

22、;/p><p>　　關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p><b>　　70</b></p><p>　　Mod 40時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　Mod 41 時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　1170</p&

23、gt;<p>　　Mod 42時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　1770</p><p>　　Mod 43時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　1870</p><p>　　Mod 60時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p

24、><p>　　970</p><p>　　Mod 61時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　670</p><p>　　Mod 77時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　1170</p><p>　　Mod 9

25、9時關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　1170</p><p><b>　　4.變量申明:</b></p><p>　　char Temp_word[10]; //存放掃描到的單詞</p><p>&

26、lt;b>　　算法圖示</b></p><p><b>　　四.技術(shù)討論：</b></p><p>　　1.掃描的文件不一樣.hash表各項(xiàng)的次序也不一樣.</p><p>　　2..考察多個C源程序文件，計算當(dāng)關(guān)鍵詞總數(shù)約為1000時，沖突次數(shù)的總次數(shù)依原文件而定;會有較大差別;</p><p>　　

27、3. 對于提供的7個測試文件;</p><p>　　0.txt , 1.txt, 2.txt, 3.txt, 4.txt, 5.txt, 6.txt;</p><p>　　0.txt中只包含幾個單純的字母.沒有關(guān)鍵字;</p><p>　　1.txt包含源文件和所有的關(guān)鍵字;</p><p>　　關(guān)鍵字沖突總字?jǐn)?shù)135

28、2 關(guān)鍵字總數(shù)752</p><p>　　2.txt和3.txt是隨機(jī)找的源文件;</p><p>　　關(guān)鍵字總數(shù)70 沖突次數(shù)11 關(guān)鍵字總數(shù)93 沖突字?jǐn)?shù)27</p><p>　　4.txt是和原來關(guān)鍵字表相同的文本</p><p>　　關(guān)鍵字總數(shù)38 總沖突次數(shù)112</p><p>　　5.txt只

29、含有2個關(guān)鍵字,但是他們是沖突的;</p><p>　　關(guān)鍵字總數(shù)659 總沖突次數(shù) 660</p><p>　　6.txt含有5個關(guān)鍵字.但是不沖突;</p><p>　　關(guān)鍵字總數(shù)0 總沖突次數(shù) 2178</p><p><b>　　*可以改進(jìn)的地方 </b></p><p>　　1.找

30、到一個字符串.如何判斷是不是關(guān)鍵字?</p><p>　　把給定的關(guān)鍵字先建一個hash表..然后拿新掃描到的字符串與其相同key值的關(guān)鍵字進(jìn)行比較,</p><p>　　后來發(fā)現(xiàn) 如果能找到一個完全沒有沖突的關(guān)鍵字hash表 ,查找效率最高 </p><p>　　相對次點(diǎn)的方法是開放較多的空間..雖然不能保證關(guān)鍵字hash表完全沒有沖突,但是沖突次數(shù)少..多數(shù)關(guān)

31、鍵字之間有空擋..查找效率也較一般的方法高;</p><p>　　2.因?yàn)槭怯瞄_放地址法,</p><p>　　每次找到一個關(guān)鍵字就插入一次.雖然關(guān)鍵字不多,但是可能造成沖突次數(shù)很多;</p><p>　　后來有人想到給他的關(guān)鍵字?jǐn)?shù)組增加一個域,用來標(biāo)記該關(guān)鍵字在新的hash中的位置.下次判斷出是這個關(guān)鍵字的話.直接存放到新hash表它所在的位置,使得每種關(guān)鍵字的開

32、放地址的工作只做了一次..大大提高了效率;</p><p><b>　　收獲與體會。</b></p><p>　　原來看到這個題目.覺得很簡單.需要用到的查找和建立hash表的方法以前都是學(xué)過的,應(yīng)該沒什么難度,但是真正做的時候總會做一點(diǎn),觀點(diǎn)改變一點(diǎn).最后把自己的觀點(diǎn)幾乎全部推翻</p><p>　　直到中期檢查,老師一句話把我一直自以為有不

33、錯算法的想法給打破了,我先建一個hash表,遇到是關(guān)鍵字的的確可以很快的識別.但是如果遇到不是關(guān)鍵字的字符串(其實(shí)程序中大部分不是關(guān)鍵字)必須查找一整圈,降低了匹配效率; 也是老師的一句話,又把我先前的掃興給消除的一干二凈; 如果我適當(dāng)放大空間; 找到一個完全沒有沖突的hash表來做為查找表;</p><p>　　每次只需要比較一次,但是后來發(fā)現(xiàn)這個方法不可以用.因?yàn)殛P(guān)鍵字里面有幾個的key值是相同的; 但是我想