信息論編碼課程設(shè)計(jì)--霍夫曼碼研究與設(shè)計(jì)

1、<p><b>　　《信息理論與編碼》</b></p><p><b>　　課程論文</b></p><p>　　題目： 霍夫曼碼研究與設(shè)計(jì) </p><p>　　學(xué)生姓名：　 　　　　　</p><p>　　學(xué)　　號：　 　 </p><p><b

2、>　　系　　別：　　 </b></p><p>　　專　　業(yè)：　 通信工程 </p><p>　　任課教師：　　 　 </p><p>　　2013年 6月 19 日</p><p><b>　　目 錄</b></p><p><b&g

3、t;　　摘 要1</b></p><p><b>　　1論文課題描述2</b></p><p>　　2霍夫曼設(shè)計(jì)原理2</p><p><b>　　3 設(shè)計(jì)過程3</b></p><p><b>　　3.1軟件介紹3</b></p><

4、p>　　3.1.1 Visual C++ 6.0簡介3</p><p>　　3.1.2主要部分4</p><p><b>　　3.2設(shè)計(jì)內(nèi)容5</b></p><p>　　4編碼程序及其分析7</p><p><b>　　總 結(jié)15</b></p><p>&

5、lt;b>　　參考文獻(xiàn)16</b></p><p><b>　　摘 要</b></p><p>　　哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對應(yīng)的字符的編

6、碼，這就是哈夫曼編碼。 </p><p>　　哈夫曼編碼(Huffman Coding)是一種編碼方式，也是可變字長編碼(VLC)的一種。這種方法完全依據(jù)字符出現(xiàn)的概率來構(gòu)造異字頭的平均長度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作哈夫曼編碼。對于M進(jìn)制哈弗曼編碼，為了提高編碼效率，就要使長碼的符號數(shù)量盡量少、概率盡量小，所以應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分

7、利用短碼。</p><p>　　本文將采用三進(jìn)制哈夫曼編碼作為例子來詮釋M進(jìn)制哈夫曼編碼。</p><p>　　在三進(jìn)制哈夫曼編碼中，得出碼字、平均碼長和編碼效率，構(gòu)造哈夫曼樹，沿著根節(jié)點(diǎn)到葉節(jié)點(diǎn)從左到右依次為0、1、2，保證平均碼長最小。在本文中采用Visual C++6.0進(jìn)行編程，此程序中具有輸入字符集大小和權(quán)值大小，構(gòu)造哈夫曼樹，并對用戶輸入的字符串進(jìn)行編碼等功能。</p&g

8、t;<p>　　關(guān)鍵詞：哈弗曼編碼；信源；哈夫曼樹；Visual C++6.0；</p><p><b>　　1論文課題描述</b></p><p>　　哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相

9、同。</p><p>　　哈夫曼壓縮是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個(gè)體符號用一個(gè)特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。</p><p>　　哈夫曼編碼是哈夫曼樹的一個(gè)應(yīng)用，是一種最優(yōu)的前綴技術(shù)，然而其存在的不足卻制約了它的直接應(yīng)用。首先，其解碼時(shí)間為O(lav

10、g)，其中l(wèi)avg為碼字的平均長度；其次，更為重要的是，解碼器需要知道哈夫曼編碼樹的結(jié)構(gòu)，因而編碼器必須為解碼器保存或傳輸哈夫曼編碼樹。對于小量數(shù)據(jù)的壓縮而言，這是很大的開銷。因而，應(yīng)用哈夫曼編碼的關(guān)鍵是如何降低哈夫曼編碼樹的存儲空間。目前流行的很多壓縮方法都是用了該技術(shù)，如GZIB、ZLIB、PNC等。</p><p><b>　　2霍夫曼設(shè)計(jì)原理</b></p><

11、p>　　對于多進(jìn)制哈夫曼編碼，為了提高編碼效率，就要是長碼的符號數(shù)量盡量少、概率盡量小，所以信源符號數(shù)量最好滿足n=(m-1)*k+r,其中m為進(jìn)制數(shù)，k為縮減的次數(shù)。</p><p><b>　　設(shè)計(jì)步驟如下：</b></p><p>　　[1]將信源符號按概率從大到小的順序排列，令</p><p>　　p(x1)≥ p(x2)≥…≥

12、p(xn)</p><p>　　[2]給兩個(gè)概率最小的信源符號p(xn-1)和p(xn)各分配一個(gè)碼位“0”和“1”，將這兩個(gè)信源符號合并成一個(gè)新符號，并用這兩個(gè)最小的概率之和作為新符號的概率，或者在新添加一個(gè)信源符號，令其概率為0，則個(gè)分配一個(gè)碼位“0”、“1”和“2”，將其合并，結(jié)果得到一個(gè)只包含(n－1)個(gè)信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。</p><p>　　

13、[3]將縮減信源S1的符號仍按概率從大到小順序排列，此后每次合并3個(gè)信源符號，得到只含(n－3)個(gè)符號的縮減信源S2。</p><p>　　[4]重復(fù)上述步驟，直至最后，此時(shí)所剩符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。</p><p><b>　　3 設(shè)計(jì)過程</b></p><p>

14、<b>　　3.1軟件介紹</b></p><p>　　3.1.1 Visual C++ 6.0簡介</p><p>　　Visual C++ 6.0，簡稱VC或者VC6.0，是微軟推出的一款C++編譯器，將“高級語言”翻譯為“機(jī)器語言（低級語言）”的程序。Visual C++是一個(gè)功能強(qiáng)大的可視化軟件開發(fā)工具。自1993年Microsoft公司推出Visual C+

15、+1.0后，隨著其新版本的不斷問世，Visual C++已成為專業(yè)程序員進(jìn)行軟件開發(fā)的首選工具。Visual C++6.0由Microsoft開發(fā), 它不僅是一個(gè)C++ 編譯器，而且是一個(gè)基于Windows操作系統(tǒng)的可視化集成開發(fā)環(huán)境（integrated development environment，IDE）。Visual C++6.0由許多組件組成，包括編輯器、調(diào)試器以及程序向?qū)ppWizard、類向?qū)lass Wizard等

16、開發(fā)工具。 這些組件通過一個(gè)名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。Microsoft的主力軟件產(chǎn)品。Visual C++是一個(gè)功能強(qiáng)大的可視化軟件開發(fā)工具。</p><p>　　Visual C++6.0以擁有“語法高亮”，自動編譯功能以及高級除錯(cuò)功能而著稱。比如，它允許用戶進(jìn)行遠(yuǎn)程調(diào)試，單步執(zhí)行等。還有允許用戶在調(diào)試期間重新編譯被修改的代碼，而不必重新啟動正在調(diào)試的程序。其編譯及創(chuàng)建預(yù)

17、編譯頭文件(stdafx.h)、最小重建功能及累加連結(jié)(link)著稱。這些特征明顯縮短程序編輯、編譯及連結(jié)的時(shí)間花費(fèi)，在大型軟件計(jì)劃上尤其顯著。</p><p><b>　　3.1.2主要部分</b></p><p>　　[1]Developer Studio</p><p>　　圖1 Developer Studio環(huán)境</p>

18、<p>　　這是一個(gè)集成開發(fā)環(huán)境，我們?nèi)粘９ぷ鞯?9%都是在它上面完成的，再加上它的標(biāo)題赫然寫著“Microsoft Visual C++”，所以很多人理所當(dāng)然的認(rèn)為，那就是Visual C++了。其實(shí)不然，雖然Developer Studio提供了一個(gè)很好的編輯器和很多Wizard，但實(shí)際上它沒有任何編譯和鏈接程序的功能，真正完成這些工作的幕后英雄后面會介紹。我們也知道，Developer Studio并不是專門用于VC

19、的，它也同樣用于VB，VJ，VID等Visual Studio家族的其他同胞兄弟。所以不要把Developer Studio當(dāng)成Visual C++， 它充其量只是Visual C++的一個(gè)殼子而已。這一點(diǎn)請切記！ </p><p><b>　　[2]MFC</b></p><p>　　從理論上來講，MFC也不是專用于Visual C++，Borland C++，C+

20、+Builder和Symantec C++同樣可以處理MFC。同時(shí)，用Visual C++編寫代碼也并不意味著一定要用MFC，只要愿意，用Visual C++來編寫SDK程序，或者使用STL，ATL，一樣沒有限制。不過，Visual C++本來就是為MFC打造的，Visual C++中的許多特征和語言擴(kuò)展也是為MFC而設(shè)計(jì)的，所以用Visual C++而不用MFC就等于拋棄了Visual C++中很大的一部分功能。但是，Visual C

21、++也不等于MFC。 </p><p>　　[3]Platform SDK</p><p>　　這才是Visual C++和整個(gè)Visual Studio的精華和靈魂，雖然我們很少能直接接觸到它。大致說來，Platform SDK是以Microsoft C/C++編譯器為核心（不是Visual C++，看清楚了），配合MASM，輔以其他一些工具和文檔資料。上面說到Developer Stu

22、dio沒有編譯程序的功能，那么這項(xiàng)工作是由誰來完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。</p><p><b>　　3.2設(shè)計(jì)內(nèi)容</b></p><p>　　例：對如下單符號離散無記憶信源編三進(jìn)制哈夫曼碼。</p><p>　　這里：m=3，n=8</p&g

23、t;<p>　　令k=3，m+k(m－1)=9，則 s=9－n=9－8=1</p><p>　　所以第一次取m－s=2個(gè)符號進(jìn)行編碼。</p><p><b>　　由計(jì)算可得：</b></p><p><b>　　平均碼長為：</b></p><p><b>　?。?.1）&

24、lt;/b></p><p><b>　　信息率為：</b></p><p><b>　?。?.2）</b></p><p><b>　　編碼效率為：</b></p><p><b>　?。?.3）</b></p><p>　

25、　可見：哈夫曼的編碼效率相當(dāng)高，對編碼器的要求也簡單得多。</p><p><b>　　編碼過程如下：</b></p><p><b>　　表1 哈夫曼編碼</b></p><p><b>　　圖2 哈夫曼樹</b></p><p><b>　　4編碼程序及其分析&l

26、t;/b></p><p>　　//**哈夫曼編碼**</p><p>　　#include <iostream.h></p><p>　　#include <math.h></p><p>　　#include <string.h></p><p>　　#include &l

27、t;stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <vector> //為了使用vector容器</p><p>　　using namespace std; ///vector屬于std命名域，因此使用全局命名域方式</p>

28、<p>　　struct Huffman_InformationSource //信源類型</p><p><b>　　{</b></p><p>　　char InformationSign[10]; //信源符號</p><p>　　double Probability; //概率</p><p

29、>　　char Code[10]; //編碼結(jié)果</p><p>　　int CodeLength; //碼長</p><p><b>　　};</b></p><p>　　struct HuffNode //哈夫曼樹的節(jié)點(diǎn)類型</p><p><b&g

30、t;　　{</b></p><p>　　char InformationSign[10];</p><p>　　double Probability;</p><p>　　HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next;</p><p>　　char Code[10

31、];</p><p>　　int CodeLength;</p><p><b>　　};</b></p><p>　　class CHuffman_3 //三進(jìn)制哈夫曼編碼</p><p><b>　　{</b></p><p><b>　　publ

32、ic:</b></p><p>　　CHuffman_3() //初始化</p><p><b>　　{</b></p><p>　　ISNumber=0;</p><p>　　AvageCodeLength=0.0;</p><p>　　InformationRate=0.0

33、;</p><p>　　CodeEfficiency=0.0;</p><p><b>　　}</b></p><p>　　~CHuffman_3()</p><p><b>　　{</b></p><p>　　DestroyBTree(HuffTree);</p>

34、;<p><b>　　}</b></p><p>　　void Huffman_Input(); //輸入信息</p><p>　　void Huffman_Sort(); //排序</p><p>　　void Huffman_Tree(); //構(gòu)造哈夫曼樹</p&

35、gt;<p>　　void Huffman_Coding(); //生成哈夫曼編碼</p><p>　　void Huffman_CodeAnalyzing(); //結(jié)果分析</p><p>　　void Huffman_Display(); //顯示結(jié)果信息</p><p>　　void Destro

36、yBTree(HuffNode *TreePointer); //釋放資源</p><p><b>　　private:</b></p><p>　　vector<Huffman_InformationSource>ISarray; //聲明ISarray數(shù)組，初始時(shí)為空</p><p>　　int ISNumber;

37、 //符號個(gè)數(shù)</p><p>　　double AvageCodeLength; //平均碼長</p><p>　　double InformationRate; //信息率</p><p>　　double CodeEfficiency;

38、 //編碼效率</p><p>　　HuffNode * HuffTree; //哈夫曼樹</p><p><b>　　private:</b></p><p>　　void Huffman_Code(HuffNode *TreePointer);</p><p><b>　

39、　};</b></p><p><b>　　//輸入信源信息</b></p><p>　　void CHuffman_3::Huffman_Input()</p><p><b>　　{</b></p><p>　　Huffman_InformationSource temp1={&qu

40、ot;A",0.40,"",0};</p><p>　　ISarray.push_back(temp1);</p><p>　　Huffman_InformationSource temp2={"B",0.18,"",0};</p><p>　　ISarray.push_back(temp2);&

41、lt;/p><p>　　Huffman_InformationSource temp3={"C",0.10,"",0};</p><p>　　ISarray.push_back(temp3);</p><p>　　Huffman_InformationSource temp4={"D",0.10,"&

42、quot;,0};</p><p>　　ISarray.push_back(temp4);</p><p>　　Huffman_InformationSource temp5={"E",0.07,"",0};</p><p>　　ISarray.push_back(temp5);</p><p>　　H

43、uffman_InformationSource temp6={"F",0.06,"",0};</p><p>　　ISarray.push_back(temp6);</p><p>　　Huffman_InformationSource temp7={"G",0.05,"",0};</p>&l

44、t;p>　　ISarray.push_back(temp7);</p><p>　　Huffman_InformationSource temp8={"H",0.04,"",0};</p><p>　　ISarray.push_back(temp8);</p><p>　　ISNumber=ISarray.size();

45、</p><p><b>　　}</b></p><p>　　//按概率“從大到小”排序：</p><p>　　void CHuffman_3::Huffman_Sort()</p><p><b>　　{</b></p><p>　　Huffman_InformationS

46、ource temp;</p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<ISNumber-1;i++)</p><p>　　for(j=i+1;j<ISNumber;j++)</p><p>　　if(ISarray[i].Probability<ISarr

47、ay[j].Probability)</p><p><b>　　{</b></p><p>　　temp=ISarray[i];</p><p>　　ISarray[i]=ISarray[j];</p><p>　　ISarray[j]=temp;</p><p><b>　　}<

48、;/b></p><p><b>　　}</b></p><p>　　//基于ISarray數(shù)組構(gòu)造哈夫曼樹</p><p>　　void CHuffman_3::Huffman_Tree()</p><p><b>　　{</b></p><p><b>　

49、　int i;</b></p><p>　　HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2;</p><p>　　//（1）：基于數(shù)組，創(chuàng)建單向鏈表</p><p>　　ptr1=new HuffNode;</p><p>　　strcpy(ptr1->InformationSi

50、gn,ISarray[0].InformationSign);</p><p>　　ptr1->Probability=ISarray[0].Probability;</p><p>　　strcpy(ptr1->Code,ISarray[0].Code); </p><p>　　ptr1->LeftSubtree=NULL;</p>

51、<p>　　ptr1->middleSubtree =NULL;</p><p>　　ptr1->RightSubtree=NULL;</p><p>　　ptr1->Next=NULL; </p><p>　　HuffTree=ptr1; //賦給數(shù)據(jù)成員HuffTree</p><p&

52、gt;　　for(i=1;i<ISNumber;i++)</p><p><b>　　{</b></p><p>　　ptr2=new HuffNode;</p><p>　　strcpy(ptr2->InformationSign,ISarray[i].InformationSign);</p><

53、;p>　　ptr2->Probability=ISarray[i].Probability;</p><p>　　strcpy(ptr2->Code,ISarray[i].Code); </p><p>　　ptr2->LeftSubtree=NULL;</p><p>　　ptr2->middleSubtree =NULL;</

54、p><p>　　ptr2->RightSubtree=NULL;</p><p>　　ptr2->Next=ptr1;</p><p>　　ptr1=ptr2;</p><p><b>　　}</b></p><p>　　//結(jié)果：鏈表的表頭為數(shù)組的最小元素。</p><

55、;p>　　HuffTree=ptr1; //使HuffTree指向鏈表頭</p><p>　　//（2）：基于鏈表，構(gòu)造哈夫曼樹</p><p>　　int k; //樹的層次</p><p>　　int s; //需要添加的無用符號的數(shù)目。

56、</p><p>　　k=ceil((double)(ISNumber-3)/(3-1)); //“3”：表示三進(jìn)制</p><p>　　//ceil函數(shù)：向上取整；</p><p>　　//floor函數(shù)：向下取整</p><p>　　s=3+k*(3-1)-ISNumber;</p><p>　　if

57、(s==1) //第一次取m-s=3-1=2個(gè)符號</p><p><b>　　{</b></p><p>　　//合并概率最小的二個(gè)節(jié)點(diǎn)ptr1、ptr2，生成一個(gè)新節(jié)點(diǎn)ptr4：</p><p>　　ptr2=ptr1->Next;</p><p>　　ptr4=n

58、ew HuffNode;</p><p>　　strcpy(ptr4->InformationSign,"*");//新節(jié)點(diǎn)的符號為“*”</p><p>　　ptr4->Probability=ptr1->Probability+ptr2->Probability; //新節(jié)點(diǎn)的概率為二者之和</p><p>　

59、　strcpy(ptr4->Code,""); </p><p>　　ptr4->LeftSubtree =NULL;</p><p>　　ptr4->middleSubtree=ptr1; //最小的節(jié)點(diǎn)ptr1成為ptr4的“中”子樹，將來賦予碼元“1”</p><p>　　ptr4->RightSubtree

60、=ptr2;//次小的節(jié)點(diǎn)ptr2成為ptr4的“右”子樹，將來賦予碼元“0”</p><p>　　HuffTree=ptr2->Next; //指向下一個(gè)節(jié)點(diǎn)</p><p><b>　　//重新排序：</b></p><p>　　temp1=HuffTree;</p><p&g

61、t;　　while(temp1&&(ptr4->Probability>temp1->Probability))</p><p><b>　　{</b></p><p>　　temp2=temp1;</p><p>　　temp1=temp1->Next;</p><p><

62、b>　　}</b></p><p>　　ptr4->Next=temp1; //插在當(dāng)前節(jié)點(diǎn)temp1之前</p><p>　　if(temp1==HuffTree)</p><p>　　HuffTree=ptr4;</p><p><b>　　else </b>&

63、lt;/p><p>　　temp2->Next=ptr4; //插在temp2節(jié)點(diǎn)之后</p><p>　　ptr1=HuffTree;</p><p><b>　　}</b></p><p>　　while(ptr1->Next)</p><p><b

64、>　　{</b></p><p>　　//合并概率最小的三個(gè)節(jié)點(diǎn)ptr1、ptr2，生成一個(gè)新節(jié)點(diǎn)ptr4：</p><p>　　ptr2=ptr1->Next;</p><p>　　ptr3=ptr2->Next;</p><p>　　ptr4=new HuffNode;</p><p>

65、;　　strcpy(ptr4->InformationSign,"*");//新節(jié)點(diǎn)的符號為“*”</p><p>　　ptr4->Probability=ptr1->Probability+ptr2->Probability</p><p>　　+ptr3->Probability; //新節(jié)點(diǎn)的概率為三者之

66、和</p><p>　　strcpy(ptr4->Code,""); </p><p>　　ptr4->LeftSubtree=ptr1;//最小的節(jié)點(diǎn)ptr1成為ptr4的“左”子樹，將來賦予碼元“2”</p><p>　　ptr4->middleSubtree=ptr2//次小的節(jié)點(diǎn)ptr2成為ptr4的“中”子樹，將來賦

67、予 “1”</p><p>　　ptr4->RightSubtree=ptr3;//次次小的節(jié)點(diǎn)ptr3成為ptr4的“右”子樹，將來賦予 “0”</p><p>　　HuffTree=ptr3->Next;</p><p>　　temp1=HuffTree;</p><p>　　while(temp1&&(ptr

68、4->Probability>temp1->Probability))</p><p><b>　　{</b></p><p>　　temp2=temp1;</p><p>　　temp1=temp1->Next;</p><p><b>　　}</b></p>

69、<p>　　ptr4->Next=temp1; //插在當(dāng)前節(jié)點(diǎn)temp1之前</p><p>　　if(temp1==HuffTree)</p><p>　　HuffTree=ptr4;</p><p><b>　　else </b></p><p>　　temp2-&g

70、t;Next=ptr4; //插在temp2節(jié)點(diǎn)之后</p><p>　　ptr1=HuffTree;</p><p><b>　　}</b></p><p><b>　　//釋放：</b></p><p>　　ptr1=NULL;</p><p>　

71、　ptr2=NULL;</p><p>　　ptr3=NULL;</p><p>　　ptr4=NULL;</p><p>　　temp1=NULL;</p><p>　　temp2=NULL;</p><p><b>　　//設(shè)置根節(jié)點(diǎn)：</b></p><p>　　st

72、rcpy(HuffTree->Code,"");</p><p>　　HuffTree->CodeLength=0;</p><p><b>　　}</b></p><p><b>　　//生成哈夫曼碼：</b></p><p>　　void CHuffman_3::

73、Huffman_Code(HuffNode *TreePointer)</p><p><b>　　{</b></p><p>　　if (TreePointer == NULL)</p><p><b>　　return;</b></p><p>　　char tempstr[10]="

74、";</p><p>　　if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree</p><p>　　&&!TreePointer->RightSubtree)</p><p><b>　　{</b></p>&

75、lt;p>　　for(int i=0;i<ISNumber;i++)</p><p>　　if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0)</p><p><b>　　{</b></p><p>　　strcpy(ISarray[i].

76、Code,TreePointer->Code);</p><p>　　ISarray[i].CodeLength=TreePointer->CodeLength;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>

77、;　　return;</b></p><p><b>　　}</b></p><p>　　if(TreePointer->LeftSubtree)</p><p><b>　　{</b></p><p>　　//生成左子樹編碼：</p><p>　　strc

78、py(tempstr,TreePointer->Code);</p><p>　　strcat(tempstr,"2");</p><p>　　strcpy(TreePointer->LeftSubtree->Code,tempstr);</p><p>　　TreePointer->LeftSubtree->Cod

79、eLength=TreePointer->CodeLength+1;</p><p>　　Huffman_Code(TreePointer->LeftSubtree);</p><p><b>　　}</b></p><p>　　if(TreePointer->middleSubtree)</p><p&g

80、t;<b>　　{</b></p><p>　　//生成中子樹編碼：</p><p>　　strcpy(tempstr,TreePointer->Code);</p><p>　　strcat(tempstr,"1");</p><p>　　strcpy(TreePointer->midd

81、leSubtree->Code,tempstr);</p><p>　　TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1;</p><p>　　Huffman_Code(TreePointer->middleSubtree);</p><p><b&g

82、t;　　}</b></p><p>　　if(TreePointer->RightSubtree)</p><p><b>　　{</b></p><p>　　//生成右子樹編碼：</p><p>　　strcpy(tempstr,TreePointer->Code);</p>&l

83、t;p>　　strcat(tempstr,"0");</p><p>　　strcpy(TreePointer->RightSubtree->Code,tempstr);</p><p>　　TreePointer->RightSubtree->CodeLength=TreePointer->CodeLength+1;</p&g

84、t;<p>　　Huffman_Code(TreePointer->RightSubtree);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void CHuffman_3::Huffman_Coding()</p><p>

85、;<b>　　{</b></p><p>　　Huffman_Code(HuffTree);</p><p><b>　　}</b></p><p><b>　　//編碼結(jié)果分析</b></p><p>　　void CHuffman_3::Huffman_CodeAnalyz

86、ing()</p><p><b>　　{</b></p><p>　　//(1):平均碼長</p><p>　　for(int i=0;i<ISNumber;i++)</p><p>　　AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength;&

87、lt;/p><p><b>　　//(2):信息率</b></p><p>　　int L=1; //單符號時(shí)，L=1</p><p>　　int m=3; //三進(jìn)制編碼，m=3</p><p>　　InformationRate=AvageCodeLengt

88、h/L*(log(m)/log(2));</p><p>　　//(3):編碼效率</p><p>　　double Hx=0;</p><p>　　for(int j=0;j<ISNumber;j++) //求信源熵</p><p>　　Hx+=-ISarray[j].Probability*log(ISarray[j

89、].Probability)/log(2);</p><p>　　CodeEfficiency=Hx/InformationRate;</p><p><b>　　}</b></p><p><b>　　//顯示結(jié)果</b></p><p>　　void CHuffman_3::Huffman_Di

90、splay()</p><p><b>　　{</b></p><p>　　cout<<"編碼結(jié)果："<<endl;</p><p>　　for(int i=0;i<ISNumber;i++)</p><p><b>　　{</b></p>

91、;<p>　　cout<<"\'"<<ISarray[i].InformationSign<<"\'"<<": "<<ISarray[i].Code<<endl;</p><p><b>　　}</b></p>&l

92、t;p>　　cout<<endl;</p><p>　　cout<<"平均碼長："<<AvageCodeLength<<endl<<endl;</p><p>　　cout<<"信息率 ："<<InformationRate<<endl<&l

93、t;endl;</p><p>　　cout<<"編碼效率："<<CodeEfficiency<<endl<<endl;</p><p><b>　　}</b></p><p><b>　　//釋放資源</b></p><p>　　

94、void CHuffman_3::DestroyBTree(HuffNode *TreePointer)</p><p><b>　　{</b></p><p>　　if (TreePointer!= NULL)</p><p><b>　　{</b></p><p>　　DestroyBTree(

95、TreePointer->LeftSubtree);</p><p>　　DestroyBTree(TreePointer->middleSubtree);</p><p>　　DestroyBTree(TreePointer->RightSubtree);</p><p>　　delete TreePointer;</p><

96、p>　　TreePointer = NULL;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//主函數(shù)：</b></p><p>　　void main()</p><p><b

97、>　　{</b></p><p>　　CHuffman_3 YYY;</p><p>　　YYY.Huffman_Input();</p><p>　　YYY.Huffman_Sort();</p><p>　　YYY.Huffman_Tree();</p><p>　　YYY.Huffman_Cod

98、ing();</p><p>　　YYY.Huffman_CodeAnalyzing();</p><p>　　YYY.Huffman_Display();</p><p><b>　　}</b></p><p><b>　　圖3 程序運(yùn)行結(jié)果</b></p><p><

99、;b>　　總 結(jié)</b></p><p>　　通過一周的課程設(shè)計(jì)使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。 </p><p>　　首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無法找到文件”的錯(cuò)誤讓我束手無策，最后還是屏蔽了定義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我

100、又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式編寫。許多的錯(cuò)誤讓我明白了一個(gè)道理---細(xì)心是非常重要的。同時(shí)，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會。請教老師也很重要，因?yàn)楫吘刮覀兪切率?，對于某些問題很難弄清楚。而且，某些錯(cuò)誤對于我們來說有時(shí)候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。 </p>

101、<p>　　這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識，還學(xué)會了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，學(xué)會了如何截圖，學(xué)會了如何更好的畫流程圖，明白了做事情只有認(rèn)真才能真正做得更好！ </p><p>　　這段時(shí)間里，可謂是酸甜苦辣都嘗過。有時(shí)，為了一個(gè)錯(cuò)誤而焦頭爛額；有時(shí)，連吃飯都是匆匆了事；但一旦程序運(yùn)行成功，總會讓我興奮不已。 </p><p>　　通過這次課程設(shè)計(jì)，我

102、看清楚了自己的編程功底和動手能力還不如人意，這主要是平時(shí)實(shí)踐太少的緣故。我想，在未來的暑假中，我會努力嘗試編寫一些程序。雖然我們信息管理專業(yè)的學(xué)生，但現(xiàn)在編程的能力太差了，畢竟多精通一門技術(shù)總是好事。 </p><p>　　在這個(gè)程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識別，更不用說是任意的ASCⅡ碼字符了。由于時(shí)間問題，暫時(shí)不能實(shí)現(xiàn)了。我想在暑假里好好研究這個(gè)問題。

103、</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]曹雪虹，張宗橙.信息論與編碼.北京：清華大學(xué)出版社，2007.</p><p>　　[2] 傅祖蕓.信息論基礎(chǔ).北京：電子工業(yè)出版社，1989</p><p>　　[3] R W漢明.朱雪龍譯.編碼和信息理論.北京：科學(xué)出版社，1984</p

104、><p>　　[4] 王育民，梁傳甲.信息與編碼理論.西安：西安電子科技大學(xué)出版社，1986</p><p>　　[5] 周炯槃.信息理論基礎(chǔ).北京：人民郵電出版社，1983</p><p>　　[6] 鐘義信.信息科學(xué)原理.北京：北京郵電大學(xué)出版社，1996</p><p>　　[7]楊永國，張冬明.Visual C++6.0實(shí)用教程.北京：清