信息論課程設(shè)計(jì)

1、目錄目錄I摘要III前言IV1課題背景11.11.2需求分析1.3 意義21.4 文獻(xiàn)綜述22 設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述32.1 設(shè)計(jì)簡(jiǎn)介32.2 設(shè)計(jì)方案論述33 詳細(xì)設(shè)計(jì)53.1 結(jié)構(gòu)體定義53.2 統(tǒng)計(jì)字符53.3 霍夫曼編碼63.4 費(fèi)諾編碼73.5 普通編碼93.6 輸出信息103.7 轉(zhuǎn)碼103.8 解碼114 設(shè)計(jì)結(jié)果及分析134.1 測(cè)試結(jié)果134.2 測(cè)試分析15165總結(jié)致謝18參考文獻(xiàn)19附錄程序代碼20摘要本課題主要是運(yùn)用VC6.0,開發(fā)基于控制臺(tái)下的霍夫曼、費(fèi)諾與普通編碼程序。本文較詳細(xì)地介紹了這一程序的設(shè)計(jì)思想，功能結(jié)構(gòu)以及算法與數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和某些功能函數(shù)的設(shè)計(jì)。本

2、文還給出了對(duì)這一程序的測(cè)試情況以及對(duì)測(cè)試結(jié)果的分析。關(guān)鍵詞：霍夫曼嗎，費(fèi)諾碼，普通碼，算法與數(shù)據(jù)結(jié)構(gòu)。刖百本文詳細(xì)介紹了編碼程序的設(shè)計(jì)與開發(fā)。全文共5章。第1章介紹了編碼程序的背景，以及它所要實(shí)現(xiàn)的基本功能。并根據(jù)這些進(jìn)行了必要的需求分析，從而確定了該程序應(yīng)實(shí)現(xiàn)了一些基本功能。本章中，還簡(jiǎn)要地介紹了該程序開發(fā)的意義以及在整個(gè)開發(fā)過(guò)程中，我們所查閱并借用的一些參考文獻(xiàn)的主要內(nèi)容。第2章主要介紹了編碼程序中各功能模塊的總體框圖，主要類的設(shè)計(jì)以及各類之間的相互關(guān)系，這是全文的核心部分。第3章是編碼程序的詳細(xì)設(shè)計(jì)，由于文章篇幅的限制，我們僅給出了主要類的設(shè)計(jì)，關(guān)鍵函數(shù)設(shè)計(jì)，包括結(jié)點(diǎn)定義、編碼定義、霍夫

3、曼編碼、費(fèi)諾編碼、普通編碼以及轉(zhuǎn)碼和解碼，并給出了其程序代碼。第4章是對(duì)編碼程序的運(yùn)行測(cè)試和分析。通過(guò)我們對(duì)輸入字符串的測(cè)試，檢驗(yàn)程序是否達(dá)到了預(yù)定的設(shè)計(jì)要求。第5章是編碼程序開發(fā)過(guò)程的總結(jié)。總結(jié)了本次課程設(shè)計(jì)的意義，以及測(cè)試中所發(fā)現(xiàn)的一些問(wèn)題，有待進(jìn)一步改進(jìn)的地方。重點(diǎn)還談到了我在本次課程設(shè)計(jì)中的收獲與感想。全文的最后是致謝、參考文獻(xiàn)和程序的全部源代碼。胡哲袁琪張小柯2014-06-16于武漢工程大學(xué)理學(xué)院2課題背景2.1月樂(lè)信源編碼主要可分為無(wú)失真信源編碼和限失真信源編碼。無(wú)失真信源編碼主要適用于離散信源或數(shù)字信號(hào)，如文本、表格及工程圖紙等信源，它們要求進(jìn)行無(wú)失真地?cái)?shù)據(jù)壓縮，要求完全能夠無(wú)

4、失真地可逆恢復(fù)。限失真信源編碼主要適用于波形信源或波形信號(hào)(及模擬信號(hào))，如語(yǔ)音、電視圖像、彩色靜止圖像等信號(hào)，它們不要求完全可逆地恢復(fù)，而是允許在一定限度內(nèi)可以有失真的壓縮。無(wú)論是無(wú)失真還是限失真的信源編碼，具目的都是為了用較少的碼率來(lái)傳送同樣多的信息，增加單位時(shí)間內(nèi)傳送的信息量，從而提高通信系統(tǒng)的有效性。香農(nóng)信息理論一一香農(nóng)第一定理和香農(nóng)第三定理是信源編碼的理論基礎(chǔ)，它們分別從理論上給出了進(jìn)行無(wú)失真信源壓縮和限失真信源壓縮的理論極值，而且還論證與指出了理想最佳信源編碼是存在的。但是并沒(méi)有給出信源編碼的實(shí)際構(gòu)造方法和實(shí)用碼的結(jié)構(gòu)。為此，隨著科學(xué)技術(shù)的發(fā)展和需求，人們廣泛地致力于對(duì)各種文本、圖

5、片、圖形、語(yǔ)言、聲音、活動(dòng)圖像和影視信號(hào)等實(shí)際信源進(jìn)行了實(shí)用壓縮方法和技術(shù)的研究，使信源的數(shù)據(jù)壓縮技術(shù)得以蓬勃發(fā)展和逐漸走向成熟。2.2需求分析根據(jù)上節(jié)所描述，用戶需要設(shè)計(jì)一個(gè)關(guān)于對(duì)信息能夠進(jìn)行編碼壓縮以及解碼的程序，使需要對(duì)文件進(jìn)行壓縮的用戶，可以通過(guò)輸入文本，便可對(duì)文件進(jìn)行編碼以及解碼。另外，該程序還要實(shí)現(xiàn)以下功能：(i)能夠用霍夫曼編碼方式進(jìn)行編碼、解碼；(2)能夠用費(fèi)諾編碼方式進(jìn)行編碼、解碼；(3)能夠用普通方式進(jìn)行編碼、解碼；(4)能夠直觀地看出三種編碼方式的差別。2.3 意義通過(guò)編碼的實(shí)例可以看出，我們編寫的二元霍夫曼碼具有以下三個(gè)特點(diǎn)：第一，霍夫曼碼的編碼方式保證了概率大的符號(hào)對(duì)

6、應(yīng)短碼，概率小的符號(hào)對(duì)應(yīng)長(zhǎng)碼，即PjAPk,有l(wèi)jMlk,而且短碼得到充分利用。第二，每次縮減信源的最后兩個(gè)碼字總是最后一位碼元不同，前面各位碼元相同（二元編碼情況）。第三，每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)。這三個(gè)特點(diǎn)保證了所得的霍夫曼碼一定是最佳碼。費(fèi)諾編碼方法屬于概率匹配編碼，這種編碼方法稍不同于前述的霍夫曼編碼，它不是最佳的編碼方法，但有時(shí)也可得到最加碼的性能。費(fèi)諾碼的編碼方法實(shí)際上是構(gòu)造碼樹的一種方法，所以費(fèi)諾碼是即時(shí)碼。費(fèi)諾碼也考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)能對(duì)應(yīng)碼長(zhǎng)短的碼字。顯然，費(fèi)諾碼仍是一種相當(dāng)好的編碼方法。但是這種編碼方法不一定能使短碼得到充分利用。尤其當(dāng)信

7、源符號(hào)較多，并有一些符號(hào)概率分布很接近時(shí)，分兩大組的組合方法就會(huì)很多?？赡苣撤N分大組的結(jié)果，會(huì)出現(xiàn)后面小組的“概率和”相差較遠(yuǎn)，因而使平均碼長(zhǎng)增加。普通編碼方式放在此例中僅用于對(duì)比作用。2.4 文獻(xiàn)綜述文獻(xiàn)1較詳細(xì)地介紹了數(shù)據(jù)結(jié)構(gòu)的一些基本知識(shí)，它對(duì)于我們了解和運(yùn)用用數(shù)據(jù)結(jié)構(gòu)知識(shí)有非常直接的幫助。文獻(xiàn)2信息編碼的專業(yè)知識(shí)，幫助我們了解編碼的相關(guān)原理，流程，以及及算法，是保證我們進(jìn)行編程的理論基礎(chǔ)。3設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述3.1 設(shè)計(jì)簡(jiǎn)介根據(jù)需求分析，我們將設(shè)計(jì)兩個(gè)結(jié)構(gòu)體：Node（樹結(jié)點(diǎn)結(jié)構(gòu)體）和CodeNode（即編碼結(jié)構(gòu)體）。其主要功能模塊有：輸入字符串、篩選概率、霍夫曼編碼、費(fèi)諾編碼、普

8、通編碼，以及轉(zhuǎn)碼和解碼，并計(jì)算平均碼長(zhǎng)和編碼效率。具類結(jié)構(gòu)見圖2-1。圖2-1程序的功能結(jié)構(gòu)3.2 設(shè)計(jì)方案論述該程序大致包含以下功能：輸入字符串，設(shè)置一個(gè)結(jié)束符，例如#，只有輸入結(jié)束符或字符長(zhǎng)度超過(guò)定義的字符容量時(shí)，才會(huì)結(jié)束。接著會(huì)把字符串中的每個(gè)字符統(tǒng)計(jì)起來(lái)，并幾率這些字符各自相應(yīng)的概率?；舴蚵幋a：保證出現(xiàn)概率最小的字符碼長(zhǎng)最大。費(fèi)諾編碼：保證概率平均分配。普通編碼：按字符出現(xiàn)的先后順序按二進(jìn)制編碼。轉(zhuǎn)碼：將字符串中的每個(gè)字符轉(zhuǎn)化成相應(yīng)的編碼。解碼：將轉(zhuǎn)碼的編碼翻譯成字符。4詳細(xì)設(shè)計(jì)4.1 結(jié)構(gòu)體定義1 .定義結(jié)點(diǎn)結(jié)構(gòu)體：structNodeintsuffix;floatweight;/

9、權(quán)值charstr;intleft,right,parent;/分別指向該節(jié)點(diǎn)的左孩子，右孩子，和雙親節(jié)點(diǎn);2 .定義編碼結(jié)構(gòu)體structCodeNodecharstr;doubleweight;/權(quán)值intlength;/編碼長(zhǎng)度charcodeL;/編碼字符;4.2 統(tǒng)計(jì)字符voidSearchStr（chars口,Nodea口）/查找字符串中字符的個(gè)數(shù)和每個(gè)字符出現(xiàn)的次數(shù)inti,j,k=0;for(i=0;i<N;i+)/初始化每個(gè)字符出現(xiàn)的次數(shù)ai.weight=0;i=0;do(for(j=0;j<k;j+)/在str中查找是否有該字符if(aj.str=si)aj.

10、weight+;break;if(j=k)/在str中無(wú)該字符，將其存入最后一個(gè)單元ak.str=si;ak+.weight+;i+;while(si!='0');ak.str='0'/將字符串結(jié)尾置"0"Len=k;/不同字符數(shù)SumL=i;/總字符數(shù)4.3 霍夫曼編碼voidHuffCode(Nodea,CodeNodecd,intn)/霍夫曼編碼inti,k,f,strlen;chartempN;for(i=0;i<n;i+)strlen=0;for(k=i,f=ai.parent;f!=-1;k=f,f=af.parent)if

11、(af.left=k)tempstrlen='0'/左分枝取0strlen+;elsetempstrlen='1'/右分枝取1strlen+;cdi.str=ai.str;/第i個(gè)葉結(jié)點(diǎn)字符cdi.weight=ai.weight;/第i個(gè)葉結(jié)點(diǎn)權(quán)值cdi.length=strlen;/第i個(gè)葉結(jié)點(diǎn)的編碼長(zhǎng)/將存放在temp中的碼值，依逆序方式導(dǎo)入cdi.codecdi.codestrlen='0'/字符數(shù)組的最后一位設(shè)置為空值strlen-;k=0;while(strlen>=0)cdi.codek+=tempstrlen-;4.4 費(fèi)諾

12、編碼intGroup(CodeNodeFC口,intlow,inthigh)/*一次分組(一分為二)并編碼*/floatMinSum=FClow.weight,MaxSum=FChigh.weight;FClow.codeFClow.length+='0'FChigh.codeFChigh.length+='1'while(low+1<high)if(MinSum>MaxSum)MaxSum+=FC-high.weight;FChigh.codeFChigh.length+='1'/編碼力口1elseMinSum+=FC+low.we

13、ight;FClow.codeFClow.length+='0'編碼加0returnlow;/返回分組的第一部分的上界voidFanoEncoding(CodeNodeFC,ints,intt)/*遞歸進(jìn)行費(fèi)諾編碼*/if(s<t)intpivotloc=Group(FC,s,t);if(s<t-1)FanoEncoding(FC,s,pivotloc);FanoEncoding(FC,pivotloc+1,t);4.5 普通編碼voidCommCoding(Nodea,CodeNodecd)/對(duì)普通碼的每個(gè)字符進(jìn)行編碼inti,j,ibak;for(i=0;i&l

14、t;Len;i+)ibak=i;cdi.weight=ai.weight;cdi.str=ai.str;cdi.length=L;for(j=0;j<L;j+)if(ibak%2=0)cdi.codeL-1-j='0'elsecdi.codeL-1-j='1'ibak=ibak/2;)4.6 輸出信息voidDisCode(CodeNodecd,intn)cout<<"字符t"<<"概率t"<<"碼長(zhǎng)t"<<"編碼t"<&l

15、t;endl;for(inti=0;i<n;i+)cout<<cdi.str<<"t"<<cdi.weight<<"/"<<SumL<<"t"<<cdi.length<<"t"for(intj=0;j<cdi.length;j+)cout<<cdi.codej;cout<<endl;doubleK=0,H=0,R;for(i=0;i<n;i+)K=K+(cdi.weight/Su

16、mL)*cdi.length;H+=-(cdi.weight/SumL)*log(cdi.weight/SumL);R=H/K;cout<<"平均碼長(zhǎng)為:"<<K<<endl;cout<<"編碼效率為:"<<R<<endl;4.7 轉(zhuǎn)碼voidCoding(chars,CodeNodecd,charcode)/利用哈夫曼編碼表對(duì)整個(gè)字符串進(jìn)行編碼inti,j,k,m=0;code0='0'/編碼數(shù)組初始化for(i=0;si;i+)/將每個(gè)字符在赫夫曼編碼表中對(duì)應(yīng)的編

17、碼存入存放總編碼的數(shù)組中for(j=0;j<=Len;j+)if(si=cdj.str)for(k=0;k<cdj.length;k+)codem+=cdj.codek;break;codem+=''for(i=0;i<m;i+)cout<<codei;cout<<endl;)4.8 解碼voidDeCode(charss口,CodeNodeHC口,charcode)/解碼inti,j,k,m,n=0,flag;intaM;a0='0'ss0='0'k=0;for(i=0;codei;i+)if(code

18、i!='')ak+=codei;elseak='0'for(j=0;j<Len;j+)flag=1;/表示ak=HCj.codefor(m=0;m<k;m+)if(am!=HCj.codem)flag=0;break;if(flag=1)ssn+=HCj.str;a0='0'k=0;break;for(i=0;i<SumL;i+)cout<<ssi;cout<<endl;5設(shè)計(jì)結(jié)果及分析5.1測(cè)試結(jié)果（i）任意輸入字符串EiA字符Ienoiurqiopimtuqeo41lt圖4-1輸入字符串（2）霍夫曼編

19、碼霍去曼編碼相關(guān)息,概率碼長(zhǎng)編碼34/744Bl01-16/744110072/74E1H01Q1“74411B122/74501100n2/7450110195/744lais6/7441110|B/7433B814/7449016i4/7449011a2/74581110s3/74501111u3/74511110q4/744Bl80甘3/745111113/7451B11152/74519000J“74&taoiiee2/74EiBaei1/746iwmiiU1/7461B1100t1/74G101161平均碼長(zhǎng)為：4.310B1編碼效率為:H.e«901霍夫曼轉(zhuǎn)碼為1

20、110091011001011010110001101101010B1010191101111日U00eeieaaneiiia01111aaaeeie11110san01ee39011111neeine1101ibiiielei11101010liaslemnei111aissss11011030011101100isibcinaishooeim111alias101111013nmn011maimlaanoama01an11111lonm用6問(wèn)lineUUll«)0B1111101000011111101801111011UM009101101OBU01001UUU1009110M

21、1101霍夫曼編碼解碼為：3437120979:1日uFi&niif口:iqur4817894TB51584902"4-NF油ajFqreiwiurqipwutuqBii41熊碼成功圖4-2霍夫曼碼相關(guān)信息(3)費(fèi)諾編碼舞編J碼摩1/74信息，7編碼00000001'1/747中團(tuán)嗣5日U1/7460000011.L/74699061022/7460006112/745emo2/?45800112辦6891006h.2/7。6OBI001r2/7452/74580110in3/745aatiir345BlPinn3z745siaui4B10134/7440110f4/

22、7448111i4/?441砂闌?5/744100186/7431B14&Z744new16Z7441101Ll8/743ill擊塔中.33784率為海,684717及諾發(fā)用的為二&1181166011006118111100990611801060lit01111Miei1001lionoiwi11811011I11010800116001a8S1101&&11101101111Q00111108001011110100811001011101&199L011BB10Q111B10010B110111BB1001BB0100BB81101161W111

23、»001SB11M1Bill00011UUlUUId的BillBl01dlUtiUUU1011110011111101000810110000011109800018000011110001011101010Q10111111001101ISM?:343712OT7918uFlasufoi«u1*481-3894-1851584902384-9fasjfeuoiur«iotHJUtwqeu41解碼成功圖4-3費(fèi)諾碼相關(guān)信息(4)普通編碼牌通編石明目關(guān)信息:概率不瞇編碼34/74a0S0800004h/74wuidutigeui72/740。同naw明HR16/74

24、g800806112274s。日（1品01日0H2/748seaeaiei'J5Z748A6/74s0000B111u.M/74gf4/74曲蒯醐1喇ig90001010A2Z74翱萬(wàn)2/74800801108II3/748可4/74600901110r3/748-3/74第L.2/74830010601J1Z74gl!2/74880010611P1/74部1/7480001Bl01t1/748aaaiaiia：0.371274普通碼轉(zhuǎn)碣為：。靦口砸加靦口印1函目。靦00BBQGB1S00000011豳團(tuán)g1時(shí)目B0B0Q1B1團(tuán)硼011000000010060001100800091

25、1000001110060100000B010810088101000001011060611的®UEMU1HUUUU»»lUkllUUUllUlUUblUlMlUUUUU111HUHUlblUUbSUUmillUbmUUUl3甘06011100000011000100Q00000000000Q00111000001100000000100010000060000110eooanieosiaeidieeeeaeiioeiaaedai00000111oaeoeiaeiaeeiaeiiiQaaeoaiei0001000耳wn討mb喝wn歷舊RillnnnwABin團(tuán)明

26、1?；赜胣nntiHHun。歷赫Bi時(shí)01nnmimiHfmiRRin000Q10910Q00iiieeeeeiiii060100110000100000001101sseeime00001000aseein100001110BOBBI81QBWOllfll00010100SIBISIQBEHlB0glMSIBlIB0000100BSBB11100001001100061000000900010B000011昔通碼解碼為-SOVlSWVTSlBufiasiiFoiqijr4Bl-3B,S4-18SlSB49023S4-9fasjfiireuoiuqiopwiLtuneu41解碼成功圖4-4普通

27、碼相關(guān)信息5.2測(cè)試分析表4-5比較不同編碼的平均碼長(zhǎng)和編碼效率作夫3碼費(fèi)諾碼普通碼平均碼長(zhǎng)4.3114.3388編碼效率0.6890.6850.371根據(jù)上表可知霍夫曼碼的平均碼長(zhǎng)最小，編碼效率最高；普通碼的平均碼平均碼長(zhǎng)最大，編碼效率最低5總結(jié)大二第二學(xué)期，我學(xué)習(xí)了信息論與編碼理論，初步了解了編碼理論的相關(guān)知識(shí)。對(duì)于其中的理論證明，我總是感到似曾相識(shí)，里面的一些內(nèi)容在算法與數(shù)據(jù)結(jié)構(gòu)中有所介紹，只是講解的比較基礎(chǔ)，而偏向于程序。這學(xué)期對(duì)這門課的學(xué)習(xí)真的云里霧里。由于以前的數(shù)學(xué)課程沒(méi)有學(xué)好，聽起這門課就像聽天書；看起書上一個(gè)個(gè)推理公式，頭就暈了，畏難情緒油然而生。在這門課程里，我時(shí)常能感受到郭

28、老師熱情激昂的講解與一絲不茍的推理其中的奧秘。對(duì)于數(shù)學(xué)知識(shí)海洋的高深莫測(cè)，我總是束手無(wú)策，除此之外，就是退縮與妥協(xié)。然而，課程設(shè)計(jì)就在我毫無(wú)準(zhǔn)備的情況下不期而至，留給我的就像一道天然的屏障，無(wú)法逾越，給我的挑戰(zhàn)是不言而喻的。好在我以前學(xué)的算法與數(shù)據(jù)結(jié)構(gòu)的知識(shí)還是相當(dāng)不錯(cuò)，自己數(shù)學(xué)底子還有一點(diǎn)，能夠看懂霍夫曼碼，費(fèi)諾碼，普通碼的原理，能夠了解其中的算法推理。在自己大腦中縈繞著其中的思緒，不禁信心大增，我難以阻擋突如其來(lái)的自信來(lái)面對(duì)課程設(shè)計(jì)。這些理論我理解起來(lái)還是比較輕松的，更大的挑戰(zhàn)莫過(guò)于編程了，就是用計(jì)算機(jī)實(shí)現(xiàn)其中的原理，再對(duì)霍夫曼碼、費(fèi)諾碼、普通碼的平均碼長(zhǎng)和編碼效率進(jìn)行比較。我開始了從所未

29、有的艱難抉擇，盡管理論不難，可在計(jì)算機(jī)上實(shí)現(xiàn)時(shí)每一步都以為著可能出現(xiàn)多處錯(cuò)誤，不同錯(cuò)誤相互影響，不同錯(cuò)誤共同構(gòu)造程序編碼的神圣地位，而我注定要與之進(jìn)行持久戰(zhàn)。每當(dāng)我敲下一行代碼，都意味著這句代碼實(shí)現(xiàn)的相關(guān)作用及其如何承上啟下，充當(dāng)機(jī)器此輪中的一個(gè)零件。每當(dāng)運(yùn)行時(shí)，總會(huì)有些莫名其妙的錯(cuò)誤，總會(huì)有不如人意的地方。每當(dāng)修改一個(gè)錯(cuò)誤，就不知道會(huì)有多少錯(cuò)誤同事出現(xiàn)，這就意味著我必須要有統(tǒng)籌全局的大局觀和精益求精地把握每一個(gè)細(xì)節(jié)，不能忽視每一個(gè)細(xì)節(jié)。然而，這還不是最令人痛苦的，而是語(yǔ)法結(jié)構(gòu)沒(méi)錯(cuò)，而程序運(yùn)行結(jié)果會(huì)出現(xiàn)莫名其妙的錯(cuò)誤，而其中的錯(cuò)誤原因可能是數(shù)以萬(wàn)計(jì)的代碼中其中的一個(gè)字母或是一個(gè)符號(hào)，這就必須要

30、從頭再來(lái)，對(duì)不同函數(shù)進(jìn)行測(cè)試，找出有問(wèn)題的函數(shù)；再查詢?cè)摵瘮?shù)的每一句代碼，直至找到錯(cuò)誤位置。我曾有個(gè)結(jié)構(gòu)體定義有誤，結(jié)果卻花了四五個(gè)小時(shí)才把錯(cuò)誤找出來(lái)。我想人生最大的痛苦莫過(guò)于此，而唯有鳳凰涅槃，陣痛過(guò)后，才能領(lǐng)悟程序浴火重生的法則與萬(wàn)變不離其宗的的奧秘。功夫不負(fù)有心人，我總算完成了程序設(shè)計(jì)，實(shí)現(xiàn)了基本的功能，證明了霍夫曼碼的平均碼長(zhǎng)最小，編碼效率最局；普通碼的平均碼長(zhǎng)最大，編碼效率最低。我也對(duì)字符串進(jìn)行了轉(zhuǎn)碼，對(duì)編碼進(jìn)行解碼，就像是加密與解密。我開始領(lǐng)悟到原來(lái)我已經(jīng)開始接觸了高科技的簡(jiǎn)單原理，而要在高科技上能夠掌握熟練技術(shù)在目前看來(lái)還是可望不可即的。學(xué)習(xí)永無(wú)止境，我還需努力。這個(gè)程序依然不是

31、很滿意，主要是受到所學(xué)知識(shí)的限制，沒(méi)有實(shí)現(xiàn)更加強(qiáng)大的功能，這對(duì)于程序開發(fā)者來(lái)說(shuō)既是機(jī)遇又是挑戰(zhàn)。盡管如此，當(dāng)測(cè)試實(shí)現(xiàn)了需要的基本功能后，那種喜悅、那種振奮都化作無(wú)窮無(wú)盡的力量激勵(lì)著我繼續(xù)開始程序之門，扭動(dòng)程序的齒輪，掌握程序的力量，來(lái)改變?nèi)松能壽E。編碼比較的程序已開發(fā)完成了，它實(shí)現(xiàn)了我們?cè)谛枨蠓治鲋兴岢龅墓δ?，但它仍有許多需要改進(jìn)的地方。1、設(shè)置的數(shù)組都是靜態(tài)的，容量有限，一旦輸入字符或轉(zhuǎn)碼后超過(guò)相應(yīng)的容量，超出部分的數(shù)據(jù)就無(wú)法儲(chǔ)存，會(huì)造成信息丟失?？梢钥紤]用動(dòng)態(tài)數(shù)組,將所需處理信息的內(nèi)存進(jìn)行動(dòng)態(tài)分配。2、沒(méi)有進(jìn)行文件操作，無(wú)法將所編碼的程序進(jìn)行保存，當(dāng)程序關(guān)閉后，所有的數(shù)據(jù)就會(huì)丟失，無(wú)法

32、保證數(shù)據(jù)的回收。3、沒(méi)有響應(yīng)的數(shù)據(jù)庫(kù)系統(tǒng)，處理的數(shù)據(jù)量較小。4、進(jìn)行轉(zhuǎn)碼時(shí)設(shè)置了一個(gè)空格符號(hào)，專門用來(lái)辨別編碼長(zhǎng)度，這樣會(huì)使處理信息量增加。致謝一份課程設(shè)計(jì)的總結(jié)，一份對(duì)郭老師的感謝。雖然我們課程設(shè)計(jì)程序代碼在這學(xué)期開始的時(shí)候已經(jīng)有了，但是在明天即將給郭老師的時(shí)刻，程序代碼也發(fā)生了許多變化，功能也逐漸提高；一些變化，一些收獲。老師說(shuō)過(guò)：“道雖遠(yuǎn)，不行不至；事雖難，不為不成。”這專業(yè)真的很累,老師們累，學(xué)生們也累，謝謝老師們和我們一起堅(jiān)持著。明天結(jié)果如何是無(wú)法知道的，而今天我們都努力過(guò)。參考文獻(xiàn)1江世宏.算法與數(shù)據(jù)結(jié)構(gòu)M.武漢：武漢工程大學(xué)出版社,2012.2傅祖蕓.信息論M.北京：北京大學(xué)出版

33、社,2010.附錄程序代碼#include<iostream>#include<cmath>#include<string>usingnamespacestd;#defineM10000/定義字符串最大長(zhǎng)度#defineN128/定義葉子節(jié)點(diǎn)個(gè)數(shù)#defineL8/定義編碼最大長(zhǎng)度intLen=0,SumL=0;/哈夫曼結(jié)點(diǎn)定義structNode/定義樹結(jié)點(diǎn)結(jié)構(gòu)體intsuffix;floatweight;/權(quán)值charstr;intleft,right,parent;/分別指向該節(jié)點(diǎn)的左孩子，右孩子，和雙親結(jié)點(diǎn);structCodeNode/定義哈弗曼編

34、碼編碼結(jié)構(gòu)體charstr;doubleweight;/權(quán)值intlength;/編碼長(zhǎng)度charcodeL;/編碼字符;voidSearchStr(chars,Nodea)/查找字符串中字符的個(gè)數(shù)和每個(gè)字符出現(xiàn)的次數(shù)inti,j,k=0;for(i=0;i<N;i+)/初始化每個(gè)字符出現(xiàn)的次數(shù)ai.weight=0;i=0;dofor(j=0;j<k;j+)/在str中查找是否有該字符if(aj.str=si)aj.weight+;break;if(j=k)/在str中無(wú)該字符，將其存入最后一個(gè)單元ak.str=si;ak+.weight+;i+;while(si!='0

35、');ak.str='0'/將字符串結(jié)尾置"0"Len=k;/不同字符數(shù)SumL=i;/總字符數(shù)voidInitialTree(Nodea,intn)for(inti=0;i<n;i+)/初始化哈夫曼數(shù)組前半部分ai.suffix=i;ai.left=-1;ai.right=-1;ai.parent=-1;)for(i=n;i<2*n-1;i+)初始化哈夫曼數(shù)組前半部分ai.suffix=i;ai.weight=0;ai.left=-1;ai.right=-1;ai.parent=-1;)voidselectKeySort(Nodea,i

36、ntm,intn)inti,j,pos,flag;intmin;Nodetemp;for(i=m;i<=n-1;i+)min=ai.weight;pos=i;flag=0;for(j=i+1;j<=n;j+)if(aj.weight<min)min=aj.weight;pos=j;flag=1;if(flag=1)temp=ai;ai=apos;apos=temp;voidselectSuffixSort(Nodea,intn)inti,j,pos,min,flag;Nodetemp;for(i=0;i<=n-2;i+)min=ai.suffix;pos=i;flag=

37、0;for(j=i+1;j<=n-1;j+)if(aj.suffix<min)min=aj.suffix;pos=j;flag=1;if(flag=1)temp=ai;ai=apos;apos=temp;voidCreateHuffmanTree(Nodea,intn)inti,j;for(i=0;i<n;i+)/將n個(gè)非葉子結(jié)點(diǎn)合并成擴(kuò)充的二叉樹j=2*i;/確定選擇排序的起始位置if(j+2<2*n-1)/當(dāng)剩下兩個(gè)棵之上棵時(shí)，進(jìn)行合并selectKeySort(a,j,n+i-1);an+i.weight=aj.weight+aj+1.weight;an+i.le

38、ft=aj.suffix;an+i.right=aj+1.suffix;aj.parent=aj+1.parent=an+i.suffix;voidHuffCode(Nodea,CodeNodecd,intn)/霍夫曼編碼inti,k,f,strlen;chartempN;for(i=0;i<n;i+)strlen=0;for(k=i,f=ai.parent;f!=-1;k=f,f=af.parent)if(af.left=k)tempstrlen='0'/左分枝取0strlen+;elsetempstrlen='1'/右分枝取1strlen+;cdi.s

39、tr=ai.str;/第i個(gè)葉結(jié)點(diǎn)字符cdi.weight=ai.weight;/第i個(gè)葉結(jié)點(diǎn)權(quán)值cdi.length=strlen;/第i個(gè)葉結(jié)點(diǎn)的編碼長(zhǎng)/將存放在temp中的碼值，依逆序方式導(dǎo)入cdi.codecdi.codestrlen='0'/字符數(shù)組的最后一位設(shè)置為空值strlen-;k=0;while(strlen>=0)cdi.codek+=tempstrlen-;intGroup(CodeNodeFC,intlow,inthigh)/*一次分組（一分為二）并編碼*/floatMinSum=FClow.weight,MaxSum=FChigh.weight;

40、FClow.codeFClow.length+='0'FChigh.codeFChigh.length+='1'while(low+1<high)if(MinSum>MaxSum)MaxSum+=FC-high.weight;FChigh.codeFChigh.length+='1'/編碼加1elseMinSum+=FC+low.weight;FClow.codeFClow.length+='0'/編碼加0returnlow;/返回分組的第一部分的上界voidFanoEncoding(CodeNodeFC,ints,i

41、ntt)/*遞歸進(jìn)行費(fèi)諾編碼*/if(s<t)intpivotloc=Group(FC,s,t);if(s<t-1)FanoEncoding(FC,s,pivotloc);FanoEncoding(FC,pivotloc+1,t);voidCommCoding(Nodea口,CodeNodecd)/對(duì)普通碼的每個(gè)字符進(jìn)行編碼inti,j,ibak;for(i=0;i<Len;i+)ibak=i;cdi.weight=ai.weight;cdi.str=ai.str;cdi.length=L;for(j=0;j<L;j+)if(ibak%2=0)cdi.codeL-1-j

42、='0'elsecdi.codeL-1-j='1'ibak=ibak/2;voidDisCode(CodeNodecd,intn)(cout<<"字符t"<<"概率t"<<"碼長(zhǎng)t"<<"編碼t"<<endl;for(inti=0;i<n;i+)(cout<<cdi.str<<"t"<<cdi.weight<<"/"<<

43、SumL<<"t"<<cdi.length<<"t"for(intj=0;j<cdi.length;j+)cout<<cdi.codej;cout<<endl;doubleK=0,H=0,R;for(i=0;i<n;i+)K=K+(cdi.weight/SumL)*cdi.length;H+=-(cdi.weight/SumL)*log(cdi.weight/SumL);R=H/K;cout<<"平均碼長(zhǎng)為:"<<K<<endl

44、;cout<<"編碼效率為:"<<R<<endl;voidCoding(chars,CodeNodecd,charcode)/利用哈夫曼編碼表對(duì)整個(gè)字符用進(jìn)行編碼inti,j,k,m=0;code0='0'/編碼數(shù)組初始化for(i=0;si;i+)/將每個(gè)字符在赫夫曼編碼表中對(duì)應(yīng)的編碼存入存放總編碼的數(shù)組中for(j=0;j<=Len;j+)if(si=cdj.str)for(k=0;k<cdj.length;k+)codem+=cdj.codek;break;codem+=''for(i=0

45、;i<m;i+)cout<<codei;cout<<endl;voidDeCode(charss口,CodeNodeHC口,charcode)/解碼inti,j,k,m,n=0,flag;intaM;a0='0'ss0='0'k=0;for(i=0;codei;i+)if(codei!='')ak+=codei;elseak='0'for(j=0;j<Len;j+)flag=1;/表示ak=HCj.codefor(m=0;m<k;m+)if(am!=HCj.codem)flag=0;break;if(flag=1)ssn+=HCj.str;a0='0'k=0;break;)for(i=0;i<SumL;i+)cout<<ssi;cout<<