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

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

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

3、<b>　　1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</b></p><p><b>　?、訇P(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è)不沖突計(jì)算出的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è)計(jì)</b&

7、gt;</p><p><b>　　具體算法:</b></p><p>　　1.先對(duì)給定的關(guān)鍵字用hash技術(shù)建一個(gè)hash表;</p><p>　　2.從一個(gè)大字符串中分解單詞;計(jì)算該單詞的key值;</p><p>　　單詞：由非字母分隔開的連續(xù)字母串</p><p>　　3.識(shí)別是否是關(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)鍵字文件.新建一個(gè)關(guān)鍵字hash表;</p><p><b>　　關(guān)鍵字hash表:</b></p><p>　　***利用ha

10、sh技術(shù)存儲(chǔ)c語(yǔ)言關(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)計(jì)關(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時(shí)關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　Mod 41 時(shí)關(guān)鍵字沖突總字?jǐn)?shù)關(guān)鍵字總數(shù)</p><p>　　1170</p&

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

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

25、9時(shí)關(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..考察多個(gè)C源程序文件，計(jì)算當(dāng)關(guān)鍵詞總數(shù)約為1000時(shí)，沖突次數(shù)的總次數(shù)依原文件而定;會(huì)有較大差別;</p><p>　　

27、3. 對(duì)于提供的7個(gè)測(cè)試文件;</p><p>　　0.txt , 1.txt, 2.txt, 3.txt, 4.txt, 5.txt, 6.txt;</p><p>　　0.txt中只包含幾個(gè)單純的字母.沒(méi)有關(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是和原來(lái)關(guān)鍵字表相同的文本</p><p>　　關(guān)鍵字總數(shù)38 總沖突次數(shù)112</p><p>　　5.txt只

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

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

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

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

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