數據結構課程設計報告---利用hash技術統計單詞的頻度

1、<p>　　《數據結構》課程設計報告</p><p><b>　　一.課程設計題目：</b></p><p>　　利用Hash技術統計單詞的頻度</p><p><b>　　二．具體要求：</b></p><p>　　利用Hash技術統計某個C源程序中的關鍵字出現的頻度</p>

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

3、<b>　　1、數據結構設計</b></p><p><b>　?、訇P鍵字表的結構</b></p><p>　　struct data1</p><p><b>　　{</b></p><p>　　char words[10]; //關鍵字</p><

4、;p>　　int exist; //位置是否為空標記</p><p>　　int hashnum; //假設不沖突計算出的key值,調試用 </p><p><b>　　};</b></p><p>　?、贖ash表中的結點結構</p><p>　　struct data2&l

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

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

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

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

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

10、sh技術存儲c語言關鍵字******</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>　　掃描目標文件.建立hash表.統計關鍵字出現的頻度,沖突次數;</p><p><b>　　比如2.txt</b></p><p>　　關鍵字表及其出現頻度</p><p>　　關鍵字出現頻度在hash表中的位置沖突次數</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>　　關鍵字沖突總字數關鍵字總數</p><p><b>　　70</b></p><p>　　Mod 40時關鍵字沖突總字數關鍵字總數</p><p>　　Mod 41 時關鍵字沖突總字數關鍵字總數</p><p>　　1170</p&

23、gt;<p>　　Mod 42時關鍵字沖突總字數關鍵字總數</p><p>　　1770</p><p>　　Mod 43時關鍵字沖突總字數關鍵字總數</p><p>　　1870</p><p>　　Mod 60時關鍵字沖突總字數關鍵字總數</p

24、><p>　　970</p><p>　　Mod 61時關鍵字沖突總字數關鍵字總數</p><p>　　670</p><p>　　Mod 77時關鍵字沖突總字數關鍵字總數</p><p>　　1170</p><p>　　Mod 9

25、9時關鍵字沖突總字數關鍵字總數</p><p>　　1170</p><p><b>　　4.變量申明:</b></p><p>　　char Temp_word[10]; //存放掃描到的單詞</p><p>&

26、lt;b>　　算法圖示</b></p><p><b>　　四.技術討論：</b></p><p>　　1.掃描的文件不一樣.hash表各項的次序也不一樣.</p><p>　　2..考察多個C源程序文件，計算當關鍵詞總數約為1000時，沖突次數的總次數依原文件而定;會有較大差別;</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中只包含幾個單純的字母.沒有關鍵字;</p><p>　　1.txt包含源文件和所有的關鍵字;</p><p>　　關鍵字沖突總字數135

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

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

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

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

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

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