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

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