C#中HashTable和快速排序的用法，從單詞頻率統計小程序寫起

先瞎扯點別的。進入這個神聖的地方總需要些鞭策，阿西巴，我是被鞭策進來擺攤的程序猿。軟件工程老師說，寫程序，發博客，就來博客園。這是個號召力很強的口號。最近看網絡營銷 搜索引擎優化的書多一些，只能說王老師真的很厲害，至少在這一周因為這個作業的原因，我們學校的程序猿們對各大程序網站訪問猛然驟增，網站流量，點擊價值當然也是不菲，不過流量轉化率就不好說了，當然了，三年多了都這樣。再插一句，Google確實比百度做得好（其實只有中國用百度），SEO優化做的很到位，最近推出的“蜂鳥算法”也很棒，因為關鍵詞明顯好找麼。   　　         好了，言歸正傳了。   　　　   　　題目主要是寫一個程序，分析一個文本文件（英文文章）中各個詞出現的頻率，並且把頻率最高的10個詞打印出來。　   　　自從周四拿到題目以後，發現又要用到萬惡的數據結構了，不得不說這是我的短板，所有上周20號到22號一直在看數據結構的書，當然還有google，在看書的期間確定了這個小程序編碼的思路。   　　1.首先進行文本文件的讀取，將一個一個的單詞分離出來，並對單詞進行統計；   　　2.然後對單詞出現的次數進行排序；   　　3.最後把頻率最高的10個詞打印出來。       　　整理好思路以後，在23號的中午我終於准備拯救世界了，當然，我們宿捨的其他三位大神已經寫完。。好了，不提我傷心的事了~~             經過分析後，主要就是解決兩個算法的問題，   　　（1）.查找問題：統計出所有出現的單詞以及他們出現的次數，這個方法挺多的，這次主要用了Hashtable，速度快，方便。   　　在.NET Framework中，Hashtable是System.Collections命名空間提供的一個容器，用於處理和表現類似keyvalue的鍵值對，其中key通常可用來快速查找，同時key是區分大小寫；value用於存儲對應於key的值。Hashtable中keyvalue鍵值對均為object類型，所以Hashtable可以支持任何類型的keyvalue鍵值對.    　　下面的代碼getAllWords和CountWord分別統計出了所有出現的單詞以及他們出現的次數。並且用控制台和文件輸出兩種方式輸出。   1.首先是計算單詞的次數。   這裡主要用到Hashtable 中各元素的虛擬子組存儲桶，每一存儲桶都與一個哈希代碼關聯，該哈希代碼是使用哈希函數生成的並基於該元素的鍵key.並且把分割的所有的單詞存放到一個名為List<WordInfo>的集合類中，最後用allWordInfos.Add(new WordInfo(key, (int)allWords[key]));在哈希表中添加了一個keyvalue鍵值對，為每一唯一鍵生成唯一哈希代碼的哈希函數使得搜索性能更佳。   復制代碼  1 public void CountWord(string inputFilePath, string outputFilePath)  2         {  3             Hashtable allWords = getAllWords(inputFilePath);  4             List<WordInfo> allWordInfos = new List<WordInfo>();  5             foreach (string key in allWords.Keys)  6             {  7                 allWordInfos.Add(new WordInfo(key, (int)allWords[key]));  8             }  9             qucikSort(allWordInfos, 0, allWordInfos.Count - 1); 10             writeToFile(allWordInfos, outputFilePath); 11         } 復制代碼     2.然後是統計出了所有出現的單詞   在分析過程中發現還需要特別注意' ', ',', ';', '.', '!', '"'這些符號，所以在讀取字節的時候用到了StreamReader的方法，主要是使其以一種特定的編碼從字節流中讀取字節。然後將讀出來的字符串做處理，分成一個個的單詞，然後就把所有英文單詞對象添加到 Hashtable 的存儲桶中，該存儲桶與匹配該對象的哈希代碼的哈希代碼關聯。在 Hashtable 內搜索一個值時，將為該值生成哈希代碼，並且搜索與該哈希代碼關聯的存儲桶。使得搜索效率變得很高。   復制代碼  1 private Hashtable getAllWords(string filePath)  2         {  3             Hashtable allWords = new Hashtable(10240);  4             using (StreamReader sr = new StreamReader(filePath, Encoding.Default))  5             {  6                 string line = null;  7                  8                 char[] seperators = new char[] { ' ', ',', ';', '.', '!', '"' };  9                 string[] words = null; 10                 while ((line = sr.ReadLine()) != null) 11                 { 12                     line = line.ToLower(); 13                     words = line.Split(seperators, StringSplitOptions.RemoveEmptyEntries); 14                     if (words != null && words.Length > 0) 15                     { 16                         for (int i = 0; i < words.Length; i++) 17                         { 18                             if (allWords.ContainsKey(words[i])) 19                             { 20                                 allWords[words[i]] = (int)allWords[words[i]] + 1; 21                             } 22                             else 23                             { 24                                 allWords.Add(words[i], 1); 25                             } 26                         } 27                     } 28                 } 29             } 30             return allWords; 31         } 復制代碼     這個程序第二個問題就是   （2）排序問題，在這裡用到了快速排序。   具體思路就是   1.分別設置low、hight指向序列的最左端、最右端；從序列中選一個進行排序（通常選最左端的值low指向的值），存入到value； 2.從hight端開始，查找比value小的，找到後講該值放入到low指向的存儲位中；同時將hight指向當前查到的值所在的位； 3.從low端開始，查找比value大的，找到後將該值放入到hight指向的存儲為中，同時low指向當前查到的值所在位； 4.若low位小於hight位，返回2步；否則，將tmp值存入到空出來的low+1指向的位置，退出，返回low所在的位置lposition。 5.以lposition為界，將序列分成兩部分，分別對兩部分進行排序。   找了圖，呵呵O(∩_∩)O~  神一樣的圖~~       復制代碼  1 private void qucikSort(List<WordInfo> allWordInfos, int low, int high)  2         {  3             if (low >= high)  4             {  5                 return;  6             }  7             int pLow = low;  8             int pHigh = high;  9             WordInfo value = allWordInfos[low]; 10             while (pLow < pHigh) 11             { 12                 while ((WordInfo.Compare(allWordInfos[pHigh], value) <= 0) && pHigh > pLow) 13                 { 14                     pHigh--; 15                 } 16                 if (WordInfo.Compare(allWordInfos[pHigh], value) > 0) 17                 { 18                     allWordInfos[pLow] = allWordInfos[pHigh]; 19                     allWordInfos[pHigh] = value; 20                     pLow++; 21                 } 22                 while ((WordInfo.Compare(allWordInfos[pLow], value) >= 0) && pHigh > pLow) 23                 { 24                     pLow++; 25                 } 26                 if (WordInfo.Compare(allWordInfos[pLow], value) <0) 27                 { 28                     allWordInfos[pHigh] = allWordInfos[pLow]; 29                     allWordInfos[pLow] = value; 30                     pHigh--; 31                 } 32             } 33             System.Diagnostics.Trace.Assert(pLow == pHigh); 34             qucikSort(allWordInfos, low, pLow - 1); 35             qucikSort(allWordInfos, pLow + 1, high); 36         } 復制代碼 此次快速排序可以將英文單詞出現的頻率全部從高到低排序出來存儲在哈希表的存儲桶裡。       小插曲：在解決快速排序算法的時候，要感謝我們宿捨的各位親們，編碼抓狂的時候有你們足以O(∩_∩)O~ @我編程我快樂 @韓亞華 @FakerWang    最後再解決一些小問題   （3）控制台輸出，文本輸入輸出，以及遍歷出頻率最高的10個詞打印出來等問題。   復制代碼  1 private void writeToFile(List<WordInfo> allWordInfos, string outputFilePath)  2         {  3             using (StreamWriter sw = new StreamWriter(outputFilePath, false, Encoding.Default))  4             {  5                 int i = 0;  6                 sw.WriteLine("單詞頻率最高的10個詞統計如下");  7                 foreach (WordInfo wi in allWordInfos)  8                 {  9                         sw.WriteLine("{0}:{1}", wi.Word, wi.Count);//輸出到文本文件 10                         Console.WriteLine("{0}:{1}", wi.Word, wi.Count);//輸出到控制台 11                         i++; 12                         if (i == 10) break; 13                 } 14             } 15         }