用c 解決統(tǒng)計字母頻率并編碼的問題

用C++解決統(tǒng)計字母頻率并編碼的問題摘要本次課程主要解決如何統(tǒng)計一段英文中各字母出現(xiàn)的頻率，并用哈夫曼樹進行編碼的問題。在課程設計中，系統(tǒng)開發(fā)平臺為WindowsXP，程序設計語言采用VisualC++，程序運行平臺為WindowsXP。在本程序中，任意輸入一段長度有限的英文，程序將自動統(tǒng)計其中各字母出現(xiàn)的次數(shù)并計算其在整個英文中的頻率。然后應用哈夫曼樹原理對各字母及相應的頻率進行優(yōu)化編碼。在設計過程中，采用了面向對象的設計方案解決問題的方法。在編碼完成后，程序通過調(diào)試運行，初步實現(xiàn)了設計目標，基本上達到了設計要求。并且經(jīng)過適當完善后，可以應用到其它關鍵領域。關鍵詞程序設計；數(shù)據(jù)結構；統(tǒng)計次數(shù)；頻率；哈夫曼；C++；編碼1引言針對當前我國高等教育的發(fā)展形勢以及為了適應21世紀人才培養(yǎng)的需要，培養(yǎng)具有特色的計算機人才，學生在校期間的課程設計項目已變成一個重要的教育手段。學生在課程設計的過程中，既可以學到新的知識，又可以增加本身的動手能力，以學生自己的求學，代替老師的講學。因此，課程設計對于深化我國高等學校的教學改革是一件十分有意義的事。這次的課程設計主要解決如何統(tǒng)計一段英文中各字母出現(xiàn)的頻率，并用哈夫曼樹進行編碼的問題。在程序設計的初期，構思用何種數(shù)據(jù)結構保存數(shù)據(jù)，用什么算法進行統(tǒng)計計算是一個非常重要的問題。經(jīng)過反復思考篩選，得到本程序的數(shù)據(jù)結構。在程序開發(fā)設計過程中，本人選擇系統(tǒng)開發(fā)平臺為WindowsXP,程序運行平臺為WindowsXP.設計語言采用VisualC++。在程序開發(fā)中期，如何進行函數(shù)之間的參數(shù)傳遞，采用何種方式傳遞，怎樣精程序實現(xiàn)步驟，也耗費了開發(fā)者相當長的時間。最后的調(diào)試運行，是最艱難的工作。選擇邊緣數(shù)據(jù)進行調(diào)試是調(diào)試程序的一般方法，該程序也采用此方法。經(jīng)過初步的調(diào)試運行，基本實現(xiàn)要設計要求。并且在得到適當?shù)耐晟坪?，可以運用于其它關鍵領域。計算機在進行編碼時，有等長編碼和不等長編碼兩種。等長編碼對于使用頻率相同的字符來說，具有節(jié)省空間的好處。如果字符的使用頻率大不相同，則使用不等長編碼。哈夫曼樹對于不等長編碼，具有非常大的優(yōu)勢，對于出現(xiàn)頻率高的字符，盡量采用長度短的編碼，對于出現(xiàn)頻率較高的字符，可適當采用較長的編碼。這樣，會獲得很好的空間效率。這個思想是今天廣泛使用的文件壓縮技術的核心。在程序中主要設計的兩個基本功能，分別為統(tǒng)計功能和編碼功能。任意輸入一段長度有限的英文，程序中會自動統(tǒng)計其中各個字母出現(xiàn)的次數(shù)，并計算其在整個英文中的頻率。然后將計算結果傳遞給編碼函數(shù)，編碼函數(shù)根據(jù)哈夫曼樹原理對各個字母及其相應的頻率進行優(yōu)化編碼。最終結果保存在程序設計初期設計的數(shù)據(jù)結構數(shù)組中，便于文件壓縮保存。本程序經(jīng)規(guī)劃、設計、編碼到運行實現(xiàn)，無一不滲透著制作者辛勞的汗水。但由于本人經(jīng)驗和學識有限，定有很多不足之處，希望能得到各位老師以及其他高手的指教修訂，使程序不斷完善。2設計思路與方案2.1課程設計目的在進行程序設計或者通信時，經(jīng)常通過給每一個字符標記一個單獨的代碼來表示一組字符，我們稱之為編碼。例如，標準ASCII碼把每個字符分別用一個7位的二進制數(shù)表示，這種方法使用最少的位表示了所有ASCII碼中的128個字符。假設所有代碼都等長，則表示n個不同的字符需要[log2n]位，這稱之為等長編碼。如果每個字符的使用頻率相等，等長編碼是空間效率最高的方法。如果字符出現(xiàn)頻率不同，則等長編碼則會浪費大部分的空間。為了能更好地節(jié)資源及空間，可以采用不等長編碼。本課程采用的是哈夫曼樹編碼2.2課程設計原理對于不等長編碼，如果設計得不合理，可能出現(xiàn)多種譯碼方式，會給譯碼帶來困難。因此，設計不等長編碼時，還必須考慮譯碼的惟一性。如果一組編碼中任一編碼都不是其他任何一個編碼的前綴，我們稱這組編碼為前綴編碼(prefixcode).前綴編碼保證了編碼被解時不會有多種可能。哈夫曼樹可用于構造最短的不等長編碼方案，具體做法如下：設需要編碼的字符集合為{d1，d2，…，dn}，它們在字符串中出現(xiàn)的頻率為{w1,w2,…,wn},以d1，d2，…，dn作為葉子結點，w1,w2,…,wn作為葉子結點的權值，構造一棵哈夫曼編碼樹，規(guī)定只夫曼編碼樹的左分支代表0，右分支代表1，則從根結點到每個葉子結點所經(jīng)過的路徑組成的0和1的序列便成為該葉子結點對應字符的編碼，稱為哈夫曼編碼。在哈夫曼編碼樹中，樹的帶權路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和，所以采用哈夫曼樹構造的編碼是一種能便字符串的編碼總長度最短的的不等長編碼。由于哈夫曼編碼樹的每個字符結點都是葉子結點，它們不可能在根結點到其它字符結點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的惟一性。2.3課程設計內(nèi)容本次的課程設計涉及的內(nèi)容主要是：用鍵盤任意輸入一段長度有限的英文字母；用數(shù)據(jù)結構的相關方法統(tǒng)計其中各個字母在文中出現(xiàn)的頻率；將各字母及相應的頻率按一定的算法進行哈夫曼編碼；將編碼后的具體信息輸出，使程序功能更加清晰明了；2.4設計預計耗費時間本次課程設計從9月1日開始，預計：用兩天的時間進行數(shù)據(jù)結構的構思；用三天的時間進行功能函數(shù)的規(guī)劃；用三天時間進行具體編碼；用七天時間進行程序的調(diào)試運行；總計耗時一十五天。如果不出意外，可以在規(guī)定時間內(nèi)完成任務。3詳細設計與實現(xiàn)3.1需求分析本課程設計要解決三個問題：如何統(tǒng)計一段英文中各字母的出現(xiàn)頻率；如何用哈夫曼編碼樹對上述頻率進行編碼；如何將進行哈夫曼編碼結點的具體信息輸出。3.2設計程序在設計程序初期，必須構思適合上述需求的數(shù)據(jù)結構進行存儲。在本程序中，設置了一個數(shù)組huff[2n-1]用來保存哈夫曼樹中各結點的信息，數(shù)組元素的結點數(shù)據(jù)類型如圖2-1所示：weightlchildrchildparent圖3-1哈夫曼樹的結點結構其中，weight是權值域，保存該結點的權值；lchild是指針域（游標），保存該結點的左孩子結點在數(shù)組中的下標；rchild是指針域（游標），保存該結點的右孩子結點在數(shù)組中的下標；parent是指針域（游標），保存該結點的雙親結點在數(shù)組中的下標。為了判定一個結點是否已經(jīng)加入到哈夫曼樹中，可通過parent域的值來確定。初始parent域的值為-1，當某結點加入到樹中時，該結點parent域的值為其雙親結點在數(shù)組中的下標。設計完所需的數(shù)據(jù)類型，中期的任務是聲明實現(xiàn)需求功能的函數(shù)，在程序定義的statistic類中，聲明了五個成員函數(shù)，其具體名稱和功能如表2-1所示：表3-1實現(xiàn)統(tǒng)計編碼的函數(shù)函數(shù)聲明功能聲明voidhufftree(intn)數(shù)據(jù)初始化，并將保存哈夫曼樹結點的數(shù)組中所有元素的游標值賦為-1；voidhuffcombine(intn)將選出的兩個最小權值的結點進行合并，共進行2n-1次；intaccount(charenglish[])根據(jù)輸入的英文統(tǒng)計各字母出現(xiàn)頻率；voidoutput(intn)輸出各結點具體信息；intsearch(intn)尋找當前未合并的結點中權值最小的結點。對于如何實現(xiàn)這些函數(shù)的功能，是本程序設計的關鍵。首先是進行字母統(tǒng)計。在intaccount(charenglish[])中，采用switch程序分支的方法，將在數(shù)組中讀到的各字母進行分類統(tǒng)計，并相加得出總數(shù)。然后根據(jù)公式letter[locate2]*100/sum計算出各字母的出現(xiàn)頻率，將結果保存在數(shù)組frequency[locate1]中。統(tǒng)計完各字母的出現(xiàn)頻率后，要對其頻率進行哈夫曼編碼。在函數(shù)voidhuffcombine(intn)中，調(diào)用intsearch(intn)函數(shù)將初始化后的各結點進行最小權值搜尋，將得到的兩個結點進行合并得到一個新結點，其權值為當前兩個最小權值結點的權值之和，并賦予他們父子關系?？偣策M行2n-1次。設葉子結點的權值集合為W={2，3，4，5}的哈夫曼樹的構造過程如圖2-2所示：345523455254543232(a)第一步(b)第二步1414953295325943254559432545(c)第三步(d)第四步圖3-2哈夫曼樹的建立過程將合并后形成的哈夫曼樹各結點的主要信息輸出，調(diào)用intsearch(intn)函數(shù)，用setiosflags(ios::left)成員函數(shù)讓輸出數(shù)據(jù)左對齊，并設字段寬度為10，可達到整齊的輸出效果。3.3編碼通過數(shù)據(jù)結構和函數(shù)原型的設計，已基本上完成了對程序的架構和功能的分析描述。具體的編碼是一個比較繁瑣的過程。本程序定義了一個頭文件statistic.h、一個函數(shù)定義文件statistic.cpp以及一個主程序執(zhí)行文件statisticmain.cpp。在頭文件中定義了huffnode數(shù)據(jù)結構和statistic類（類中函數(shù)聲明見表2-1）。statistic.cpp文件則對類中的函數(shù)進行了具體功能的定義。最后由主程序statisticmain.cpp調(diào)用功能函數(shù)，完成了程序設計初期的功能要求。4程序調(diào)試運行程序的調(diào)試運行是程序設計中耗時最長且難度最大的一個環(huán)節(jié)。程序調(diào)試的效率要根據(jù)程序開發(fā)者的開發(fā)經(jīng)驗而定。本人在該程序的開發(fā)過程中，也遇到了一系列棘手的問題，主要如下：根據(jù)設計編碼后，編譯通過，但是連接出個很多錯誤，經(jīng)觀察，錯誤個數(shù)和定義的函數(shù)個數(shù)相同，猜測這不是函數(shù)內(nèi)部語法問題，而是外部問題。根據(jù)之前的編程經(jīng)驗，在頭文件中定義的數(shù)據(jù)結構和類之前增加了模板。編譯時發(fā)生一個錯誤，找到錯誤后將它先進行注釋，編譯通過，連接通過。如圖3-1所示：Structhuffnode{Intweight;Intlchild,rchild,parent;};Template<classT>Structhuffnode{Intweight;Intlchild,rchild,parent;}圖4-1調(diào)試過程（2）定義了一個含有模板的數(shù)據(jù)結構后，在接下聲明的類中定義變量時發(fā)生編譯錯誤，在查閱相關書籍后發(fā)現(xiàn)，在數(shù)據(jù)類型后要標記<T>符號。如圖3-2所示：huffnodehuff[]huffnode<T>huff[]圖4-2(3)至此，程序的編譯和連接都已經(jīng)通過。運行程序，按提示輸入一段英文后，程序非法中斷。由此判斷，程序的算法存在錯誤的地方。在程序的第一個函數(shù)前標注，使程序由此一步一步運行。通過一遍遍地運行調(diào)試，發(fā)現(xiàn)在哈夫曼樹結點權值的賦值上存在很大的不足，竟將頻率為0的值也賦了進來，當即改正過來。編譯連接，運行程序，程序仍然非法中斷。仍按上述方法進行調(diào)試，發(fā)現(xiàn)在最小權值的搜尋上也存在著錯誤，修正后，程序正常運行。（4）在程序設計之前，我并沒有想到設計有關哈夫曼樹結點的信息輸出。但在程序調(diào)試運行成功之后，發(fā)現(xiàn)無法讓用戶明白程序運行先后的差別，無法得知程序是否得到了正確的結果。于是，本課程設計結束之前，又添加了顯示編碼后哈夫曼樹結點具體信息這個功能。使程序更加人性化，明了化。（5）程序運行界面如圖4-3所示：圖4-3運行界面5異常處理程序在執(zhí)行時經(jīng)常會出現(xiàn)一些違反設計期望的異常情況（如除零），過去的解決方法是利用操作系統(tǒng)中斷代為處理。由于這種解決方法強行中止了應用程序的運行，一些大型的應用系統(tǒng)的開發(fā)人員提出，可以在允許的范圍內(nèi)由應用程序自身來處理一般性的程序運行錯誤。C++語言異常處理由三個部分構成。異常檢測的觸發(fā)、異常檢測的捕獲和異常檢測的處理。它們分別對應了“try”、“throw”和“catch”三個關鍵字。這三者的關系如圖4-1所示。圖5-1C++異常處理流程圖被throw語句扔出的數(shù)據(jù)實際上被壓入了相應層的catch語句所對應的堆棧內(nèi)，最后才被catch語句捕獲到的。當try語句出現(xiàn)嵌套時，情況可能會更加復雜。在本程序中，try語句為：statistic<int>pra;//定義statistic類對象；intlength;length=pra.account(english);//得到不同出現(xiàn)頻率字母的個數(shù); pra.hufftree(length);//數(shù)據(jù)初始化，游標初始化；pra.huffcombine(length-1);//進行2n-1次合并；cout<<"-------pleaseoutputeverynodeinformation:--------"<<endl;pra.output(length);//輸出各結點信息；當(strlen(english))>maxsize，即輸入的英文長度超過定義的最大長度時，拋出異常throw0，程序跳出try范圍，否則繼續(xù)處理。當運行到catch(int)時跳過繼續(xù)執(zhí)行其后的語句；catch(int)在捕獲異常消息的類型后，對其進行處理。處理語句為：cout<<"theparagraphisoverlong!"<<endl;異常處理完畢后，程序不會自動終止，而是繼續(xù)處理catch子句之后的語句，本程序在返回主函數(shù)類型后，結束程序。6結束語這次的課程設計，從9月1日開始初期的規(guī)劃，到9月13日程序順利地通過運行，歷時13天。比預估計的時間15天，提前了兩天完成。在這期間，前期的數(shù)據(jù)結構及函數(shù)功能的規(guī)劃耗費了一定長的時間，但主要的時間是用在了程序最后的調(diào)試運行上。通過這個程序設計，不難發(fā)現(xiàn)，面向對象的程序設計方法思路和人們?nèi)粘Ｉ钪刑幚韱栴}的思路是相似的。運用面向對象的程序設計方法，設計者的任務包括兩個方面：一是設計所需的各種類和對象，即決定把哪些數(shù)據(jù)和操作封裝在一起；二是考慮看樣子向有關對象發(fā)送消息，以完成所需的任務。在本程序中，設計了一個數(shù)據(jù)類型huffnode和一個模板類statistic，在類中聲明了五個功能函數(shù)，并將這些函數(shù)及相應的數(shù)據(jù)成員封裝在一起，形成了一個黑盒，用戶不需要知道盒子里面的構造，只需知道如何調(diào)用這些函數(shù)，以實現(xiàn)其需求。程序通過參數(shù)的形式向各個成員函數(shù)發(fā)送用戶消息，成員在函數(shù)接收到消息后，對實參進行相應運算，返回運算結果。最后，輸出用戶所要的具體信息。在這次在課程設計中，我遇到了很多困難，其中不乏一些極其微末的細節(jié)問題。比如模板的格式問題等等。它們消耗了我大量的時間和精力去尋找問題所在。在困難面前，我曾一度地想要放棄，但最終在查閱了大量書籍和相關資料后，找到問題的關鍵，解決了難題。總結經(jīng)驗，吸取教訓，我在這次的課程設計中學到了很多，解決了之前一直不曾明白的問題，親自動手能力也得到了大大的增強。在此，我非常感謝一直在身邊幫助我的同學們，當然還有我們數(shù)據(jù)結構的指導老師的敦敦教誨。由于本人能力有限，因此本程序還有很多的不足之處，希望大家不吝賜教，使它更加完善。參考文獻[1] 譚浩強.C++程序設計.北京：清華大學出版社，2006[2] 王紅梅，胡明，王濤.數(shù)據(jù)結構(C++版).北京：清華大學出版社,2007[3] F.BrokkenandK.Kubat.C++Annotations.Version4.4.0m，ICCE，UniversityofGroningen，Netherlands，1990.250～[4] 周曉聰，李文軍，李師賢.面向對象程序設計——實踐與提高.中山大學計算機科學學院講義，1999[5] 粟利民，孫強.如何用VC++和VisualFoxpro進行ActiveX數(shù)據(jù)通訊.程序太平洋網(wǎng)站，/Info/38/Info15372/：2005-5-28附錄：結構化設計源程序列表//程序名稱：統(tǒng)計編碼//程序功能：采用結構化方法設計程序，實現(xiàn)統(tǒng)計一段英文中各字母的出現(xiàn)頻率，并對//其進行哈夫曼樹編碼的功能。//程序作者：林魁//最后修改日期：2008-9-13//頭文件，函數(shù)聲明；#ifndefstatistic_h#definestatistic_h#include<cstring>#include<iostream>#include<iomanip>usingnamespacestd;//////////////////////////////////////////////////////////////////////////////////////////////constintmaxsize=500;//宏定義///////////////////////////////////////////////////////////////////////////////////////////////////template<classT>//定義哈夫曼結點數(shù)據(jù)結構;structhuffnode{intweight;//權值intparent,lchild,rchild;//光標,指向數(shù)組下標;};//////////////////////////////////////////////////////////////////////////////////////////////template<classT>classstatistic{public:voidhufftree(intn); //初始化哈夫曼樹結點的游標；;voidhuffcombine(intn); //合并形成哈夫曼樹;intaccount(charenglish[]); //計算各英文字母的出現(xiàn)次數(shù)以及出現(xiàn)頻率;voidoutput(intn);//輸出各結點信息;private:huffnode<T>huff[51]; //保存哈夫曼樹結點;intsearch(intn); //尋找數(shù)組中兩個最小權值的結點下標;intfrequency[26]; //保存字母出現(xiàn)頻率;};///////////////////////////////////////////////////////////////////////////////////////////////////////////////#endif//函數(shù)定義文件#include"statistic.h"http:///////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>intstatistic<T>::account(charenglish[]){if((strlen(english))>maxsize)throw0;//如果輸入英文超出最大長度,拋出異常;intletter[26]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};intlocate=0,locate1=0,locate2=0;intsum=0,zero=0;//字母出現(xiàn)總次數(shù)及出現(xiàn)為0的次數(shù)賦初值0；while(english[locate]!='\0'&&locate<maxsize)//當不超過總長度和實際長度時；{switch(english[locate])//統(tǒng)計各英文字母的出現(xiàn)次數(shù);{case'a':letter[0]++;break;case'b':letter[1]++;break;case'c':letter[2]++;break; case'd':letter[3]++;break; case'e':letter[4]++;break; case'f':letter[5]++;break; case'g':letter[6]++;break; case'h':letter[7]++;break; case'i':letter[8]++;break; case'j':letter[9]++;break; case'k':letter[10]++;break; case'l':letter[11]++;break; case'm':letter[12]++;break; case'n':letter[13]++;break; case'o':letter[14]++;break; case'p':letter[15]++;break; case'q':letter[16]++;break; case'r':letter[17]++;break; case's':letter[18]++;break; case't':letter[19]++;break; case'u':letter[20]++;break; case'v':letter[21]++;break; case'w':letter[22]++;break; case'x':letter[23]++;break; case'y':letter[24]++;break; case'z':letter[25]++;break; default:break;//其它字符不納入計算；}locate++;}for(locate=0;locate<26;locate++){sum=sum+letter[locate];//統(tǒng)計各字母出現(xiàn)的總次數(shù);}for(;locate2<26;locate1++,locate2++){frequency[locate1]=letter[locate2]*100/sum;//計算各字母出現(xiàn)的頻率;if(frequency[locate1]==0){zero++;//統(tǒng)計出現(xiàn)次數(shù)為0的字母的個數(shù);locate1--; //當字母頻率為0時不納入統(tǒng)計編碼范圍;}}return26-zero;//返回實際出現(xiàn)不同字母的個數(shù);}/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>voidstatistic<T>::hufftree(intn){inti;for(i=0;i<2*n-1;i++)//初始化哈夫曼數(shù)組中各元素的光標值;{huff[i].parent=-1;huff[i].lchild=-1;huff[i].rchild=-1;}for(i=0;i<n;i++){huff[i].weight=frequency[i];//給哈夫曼結點數(shù)組中前N個元素的權置給定權值;}}///////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>intstatistic<T>::search(intn){inti,p,min;p=n+1;//將當前哈夫曼數(shù)組的最后一個元素的下一個地址賦給p;while(huff[n].parent!=-1&&n>=0)//當結點已合并時,跳到下一個;{n--;}if(n<0)return100;//查找失敗時返回100;else{min=n;//給min下標賦初值n;for(i=n-1;i!=-1;i--){if(huff[i].parent==-1){if(huff[i].weight<huff[min].weight)min=i;//如果當前結點的權值比huff[min]中的權值小,則將當前結點的下標賦給min;}}huff[min].parent=p;//指定當前結點父親結點的下標;returnmin;//返回最小權值結點的下標;}}////////////////////////////////////////////////////////////////////////////////////////////////////////////////template<classT>voidstatistic<T>::huffcombine(intn){inti,j;i=search(n);//取當前最小權值結點的下標；j=search(n);//同上；if(j!=100){huff[n+1].weight=huff[i].weight+huff[j].weight;//兩個最小權值結點的權值相加,得到父親結點的權值;huff[n+1].lchild=i;huff[n+1].rchild=j;n++;huffcombine(n);//進行下一輪合并;}else{huff[i].parent=-1;//保證根結點的父親結點下標為-1;cout<<"combineend"<<endl;//合并結束標志；}}///////////////////////////////////////////////////////////////////////////////////////////////////////////////////