信息論與編碼課程設(shè)計

1、<p>　　信息論與編碼課程設(shè)計 </p><p><b>　　報</b></p><p><b>　　告</b></p><p><b>　　書</b></p><p>　　學(xué) 院： 電氣工程與自動化 </p><p>

2、　　專業(yè)班級： </p><p>　　指導(dǎo)老師： </p><p>　　團(tuán)隊成員： </p><p>　　本案作者： </p><p>　　學(xué) 號

3、： </p><p>　　完成日期： 2013年3月26日 </p><p><b>　　摘要</b></p><p>　　信息是從人類出現(xiàn)以來就存在于這個世界上，人類社會的生存和發(fā)展都離不開信息的獲取、傳遞、處理、再生、控制和處理。而信息論正是一門把信息作為研究對象

4、，以揭示信息的本質(zhì)特性和規(guī)律為基礎(chǔ)，應(yīng)用概率論、隨即過程和數(shù)理統(tǒng)計等方法來研究信息的存儲、傳輸、處理、控制、和利用等一般規(guī)律的學(xué)科。主要研究如何提高信息系統(tǒng)的可靠性、有效性、保密性和認(rèn)證性，以使信息系統(tǒng)最優(yōu)化。在信息論的指導(dǎo)下，信息技術(shù)得到飛速發(fā)展，這使得信息論滲透到自然科學(xué)和社會科學(xué)的所有領(lǐng)域，并且應(yīng)用與眾多領(lǐng)域：編碼學(xué)、密碼學(xué)與密碼分析、數(shù)據(jù)壓縮、數(shù)據(jù)傳輸、檢測理論、估計理論等。信息論的主要基本理論包括：信息的定義和度量；各類離散信

5、源和連續(xù)信源的信源熵；有記憶，無記憶離散和連續(xù)信道的信道容量，平均互信息；無失真信源編碼相關(guān)理論。</p><p>　　求離散性信源熵也是信息論課程實踐學(xué)習(xí)中必須要經(jīng)歷，在了解常規(guī)的求解方式的同時，利用計算機(jī)語言進(jìn)行實踐編程。</p><p>　　用預(yù)先規(guī)定的方法將文字、數(shù)字或其他對象編成數(shù)碼，或?qū)⑿畔ⅰ?shù)據(jù)轉(zhuǎn)換成規(guī)定的電脈沖信號。編碼在電子計算機(jī)、電視、遙控和通訊等方面廣泛使用。其中哈夫

6、曼編碼有廣泛的應(yīng)用,通過本次實驗,了解編碼的具體過程,通過編程實現(xiàn)編碼。本次實驗所使用的機(jī)器語言均為C語言。</p><p>　　關(guān)鍵字：信息論 離散和連續(xù)信源熵 哈夫曼編碼 C語言編程設(shè)計</p><p>　　第一章 課程設(shè)計概述及意義</p><p>　　本課程設(shè)計是在學(xué)習(xí)了《信息論與編碼》和相關(guān)開發(fā)的軟件課程后，讓我們通過實際的操作來熟悉信源編碼微機(jī)實現(xiàn)

7、，培養(yǎng)我們能夠獨(dú)立的完成對相關(guān)課題或者項目的分析能力、設(shè)計能力和調(diào)試能力。本課程設(shè)計是銜接在C課程、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之后的，運(yùn)用程序思想來完成的，聯(lián)系信息論與編碼所學(xué)內(nèi)容，要求有獨(dú)立的操作界面。在這次的課程設(shè)計中，著重培養(yǎng)的是我們的自學(xué)能力，以及獨(dú)立分析互聯(lián)網(wǎng)上和圖書館里的各種資料，來豐富自己的知識并且提高對數(shù)學(xué)公式的計算機(jī)實現(xiàn)、VC++等軟件的實際操作能力。通過這次的課程設(shè)計，能夠使我們對已經(jīng)學(xué)習(xí)過的信息論與編碼課程的進(jìn)一步的掌握，能

8、夠?qū)χR進(jìn)行最大程度的消化融匯。因此這次的課程設(shè)計對我們有著非常重要的意義。 本課程設(shè)計中用VC編寫出基于visual studio2010界面的簡單軟件以實現(xiàn)壓縮信源熵求解及哈夫曼編碼的目的。經(jīng)過比較系統(tǒng)合理的編程操作，實現(xiàn)可視化的窗口以方便用戶使用。通過簡單校驗確保信源正確性，保證軟件的可靠性。最終將結(jié)果保存為文檔方便記錄編碼結(jié)果。 通過讓完成具體編碼算法的程序設(shè)計和調(diào)試工作，達(dá)到提高編程能力和深刻理解編碼理論及信源

9、熵求解的目的。培養(yǎng)</p><p>　　第二章 設(shè)計任務(wù)與要求</p><p><b>　　1、設(shè)計目的</b></p><p>　　1.1深刻理解信源熵的計算方法；</p><p>　　1.2深刻理解信源編碼的基本思想與目的；</p><p>　　1.3理解哈夫曼編碼方法的基本過程與特點；<

10、;/p><p>　　1.4提高綜合運(yùn)用所學(xué)理論知識獨(dú)立分析和解決問題的能力；</p><p>　　1.5提高使用C語言或其他語言進(jìn)行編程的能力，以及visual studio 軟件的應(yīng)用能力。</p><p><b>　　2．設(shè)計內(nèi)容</b></p><p>　　首先對拖入文件中的字符總個數(shù)進(jìn)行統(tǒng)計 ，然后從文本頭開始查找同

11、一字符個數(shù)，并計算 其概率 最后由得出的字符概率求得信源熵 </p><p>　　假設(shè)已知一個信源的各符號概率，編寫適當(dāng)函數(shù)，對其進(jìn)行哈夫曼編碼，得出M進(jìn)制碼字，平均碼長和編碼效率，總結(jié)此編碼方法的特點和應(yīng)用。</p><p><b>　　3．設(shè)計要求</b></p><p>　　1、編寫的函數(shù)要有通用性；</p><p&g

12、t;　　2 學(xué)生可獨(dú)立完成，或組隊共同完成。每隊人數(shù)不多于4人。</p><p>　　3、提交一份獨(dú)立完成的課程設(shè)計報告（紙質(zhì)和電子版），做5分鐘PPT匯報，并演示程序。每隊選擇1人匯報和演示程序，其他人答辯。</p><p>　　4、課程設(shè)計報告包括設(shè)計任務(wù)與要求、設(shè)計思路、設(shè)計流程圖、程序運(yùn)行及結(jié)果、心得體會、參考文獻(xiàn)、附錄（源程序）等內(nèi)容。</p><p>

13、<b>　　4．設(shè)計條件</b></p><p>　　1、計算機(jī)、C語言或其他語言環(huán)境</p><p>　　2、設(shè)計軟件 visual studio2010</p><p><b>　　5．設(shè)計思路</b></p><p>　　信源熵的定義：信源各個離散消息的自信息量的數(shù)學(xué)期望 </p>

14、;<p>　　首先對拖入文件中的字符總個數(shù)進(jìn)行統(tǒng)計，然后從文本頭開始查找同一字符個數(shù)，并計算其概率，最后由得出的字符概率求得信源熵。 </p><p>　　假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為(W1*L1)+(W2*L2)+…+(Wi*Li)。若將此對應(yīng)到二叉樹上，Wi為葉結(jié)點，Li為根結(jié)點到葉結(jié)點的路徑長度。那么，(W1*L1)+(W2*L2)

15、+…+(Wi*Li)恰好為二叉樹上帶權(quán)路徑長度。 因此，設(shè)計電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹</p><p>　　6.離散平穩(wěn)信源熵求解說明</p><p>　　離散平穩(wěn)信源也是一種非常重要的信源。不同時刻信源輸出符號的概 率分布完全相同，則稱為一維離散平穩(wěn)信源。二維離散平穩(wěn)信源就是信源輸出的隨機(jī)序列…，X1,X2,…,Xi，…，滿足其一維和二維

16、概率分布與時間起點無關(guān)。這種各維聯(lián)合概率分布均勻與時間起點無關(guān)的完全平穩(wěn)信源稱離散平穩(wěn)信源。</p><p>　　二維離散平穩(wěn)信源的聯(lián)和熵為：，此值表示原來信源X輸出任意一對可能的消息的共熵，即描述信源X輸出長度為2的平均不確定性，或所含的信息量，因此可用作為二維離散平穩(wěn)信源的信息熵的近似值。</p><p>　　在通信系統(tǒng)的各種信源中，離散隨機(jī)信源是最基本的一種信源，信源輸出是單個的符號

17、的消息，并且消息之間是兩兩互不相容的。我們知道，事件發(fā)生的不確定性與事件發(fā)生的概率有關(guān)：事件的發(fā)生概率越小，不確定性就越大，事件發(fā)生的概率越大，不確定性就越小，對于發(fā)生概率為1的必然事件就不存在不確定性。設(shè)一離散信源的概率空間為：</p><p><b>　　... </b></p><p><b>　　... </b></p>

18、<p>　　即，如果知道已發(fā)生，則該事件所含有的信息量稱自信息，表達(dá)式為：</p><p>　　上面的自信息是指某一信源發(fā)出某一消息所含的信息量，但所發(fā)消息不同，它們所含信息量也就不同，所以自信息不能作為整個信源的信息測度，我們定義平均自信息量，即對每個事件各自所攜帶的信息量做一個加權(quán)平均，也稱信息熵，表示如下：</p><p>　　信息熵具有一些基本的性質(zhì)，比如，對稱性，確

19、定性，非負(fù)性，擴(kuò)展性，可加性等等。這里面有一個最大離散熵定理，表明:離散信源情況下，對于具有q個符號的離散信源，只有在q個信源符號等可能出現(xiàn)的情況下，信源熵才能達(dá)到最大值，這樣也表明等概率分布信源的平均不確定性為最大。</p><p>　　7.哈夫曼編碼編程方式說明</p><p>　　哈夫曼編碼(Huffman Coding)是一種編碼方式，也是可變字長編碼(VLC)的一種。這種方法完全

20、依據(jù)字符出現(xiàn)的概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫作哈夫曼編碼。對于M進(jìn)制哈弗曼編碼，為了提高編碼效率，就要使長碼的符號數(shù)量盡量少、概率盡量小，所以應(yīng)使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。</p><p>　　在這個信息量爆炸的時代，凡是能載荷一定信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變長碼。為此，必須將概率大的

21、信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字最短。能獲得最佳碼的編碼方法主要有：香農(nóng)（Shannon）、費(fèi)諾（Fano）、哈夫曼（Huffman）編碼等。</p><p>　　哈夫曼(Huffman)編碼是一種常用的壓縮編碼方法，是Huffman于1952年為壓縮文本文件建立的。它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。</p>

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

23、字的平均長度；其次，更為重要的是，解碼器需要知道哈夫曼編碼樹的結(jié)構(gòu)，因而編碼器必須為解碼器保存或傳輸哈夫曼編碼樹。對于小量數(shù)據(jù)的壓縮而言，這是很大的開銷。因而，應(yīng)用哈夫曼編碼的關(guān)鍵是如何降低哈夫曼編碼樹的存儲空間。目前流行的很多壓縮方法都是用了該技術(shù)，如GZIB、ZLIB、PNC等。</p><p>　　對于多進(jìn)制哈夫曼編碼，為了提高編碼效率，就要是長碼的符號數(shù)量盡量少、概率盡量小，所以信源符號數(shù)量最好滿足n=

24、(m-1)*k+r,其中m為進(jìn)制數(shù)，k為縮減的次數(shù)。</p><p><b>　　設(shè)計步驟如下：</b></p><p>　　[1]將信源符號按概率從大到小的順序排列，令</p><p>　　p(x1)≥ p(x2)≥…≥ p(xn)</p><p>　　[2]給兩個概率最小的信源符號p(xn-1)和p(xn)各分配一個

25、碼位“0”和“1”，將這兩個信源符號合并成一個新符號，并用這兩個最小的概率之和作為新符號的概率，或者在新添加一個信源符號，令其概率為0，則個分配一個碼位“0”、“1”和“2”，將其合并，結(jié)果得到一個只包含(n－1)個信源符號的新信源。稱為信源的第一次縮減信源，用S1表示。</p><p>　　[3]將縮減信源S1的符號仍按概率從大到小順序排列，此后每次合并3個信源符號，得到只含(n－3)個符號的縮減信源S2。&l

26、t;/p><p>　　[4]重復(fù)上述步驟，直至最后，此時所剩符號的概率之和必為1。然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼字。</p><p>　　第三章 設(shè)計流程圖</p><p>　　1.信源熵編程計算設(shè)計流程圖</p><p>　　2.哈夫曼編碼程序設(shè)計流程圖</p><p>&l

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

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

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

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

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

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

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

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

35、譯程序的功能，那么這項工作是由誰來完成的呢？是CL，是NMAKE，和其他許許多多命令行程序，這些我們看不到的程序才是構(gòu)成Visual Studio的基石。</p><p>　　第三章 程序運(yùn)行及結(jié)果</p><p>　　1.計算信源熵結(jié)構(gòu)截圖</p><p>　　2.哈夫曼樹編程截圖結(jié)果</p><p>　　3.設(shè)計內(nèi)容舉例結(jié)果分析<

36、/p><p>　　例：對如下單符號離散無記憶信源編三進(jìn)制哈夫曼碼。</p><p>　　這里：m=3，n=8</p><p>　　令k=3，m+k(m－1)=9，則 s=9－n=9－8=1</p><p>　　所以第一次取m－s=2個符號進(jìn)行編碼。</p><p><b>　　由計算可得：</b>&l

37、t;/p><p><b>　　平均碼長為：</b></p><p><b>　?。?.1）</b></p><p><b>　　信息率為：</b></p><p><b>　?。?.2）</b></p><p><b>　　編

38、碼效率為：</b></p><p><b>　?。?.3）</b></p><p>　　可見：哈夫曼的編碼效率相當(dāng)高，對編碼器的要求也簡單得多。</p><p><b>　　編碼過程如下：</b></p><p><b>　　表1 哈夫曼編碼</b></p&g

39、t;<p><b>　　圖2 哈夫曼樹</b></p><p>　　第五章 課程設(shè)計心得體會</p><p>　　此次課程設(shè)計，受益頗多。將書本上的理論知識應(yīng)用到實例中，進(jìn)一步掌握了信源熵與與哈夫曼編碼的相關(guān)知識點，也更熟悉的掌握了C語言編碼。在課程設(shè)計的過程中，也遇到了一些問題，但這也正是課程設(shè)計的目的所在，發(fā)現(xiàn)自身的不足。我們深刻意識到自己在學(xué)習(xí)

40、中的弱點，同時也找到了克服這些弱點的方法，這是在此活動中得到的一筆很大的財富。在以后的時間中，我們應(yīng)該利用更多的時間去上機(jī)實驗，多編寫程序，相信不久后我們的編程能力都會有很大的提高。同時也感謝老師給我們這次機(jī)會，發(fā)現(xiàn)自身存在的缺點與不足，從而在以后的大學(xué)生活中更好的提升和完善自我。</p><p><b>　　附錄 </b></p><p><b>　　1.

41、參考文獻(xiàn)</b></p><p>　　[1]曹雪虹，張宗橙.信息論與編碼.北京：清華大學(xué)出版社，2007.</p><p>　　[2]王慧琴.數(shù)字圖像處理.北京：北京郵電大學(xué)出版社，2007.</p><p>　　[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）。北京：清華大學(xué)出版社，2009.</p><p>　　[4]賈宗璞，許合利

42、.C語言程序設(shè)計：人民郵電出版社,2010.</p><p>　　2.哈幅曼樹調(diào)試程序</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　

43、　#include <ctype.h></p><p>　　#include <math.h></p><p>　　#define KongJian 200</p><p>　　typedef struct Hafuman</p><p><b>　　{</b></p><p&

44、gt;　　char ZiMu;</p><p>　　double weight;</p><p>　　int parent,</p><p><b>　　lchild,</b></p><p><b>　　rchild;</b></p><p>　　}HTNode, *Haf

45、umanTree;</p><p>　　typedef char* *HafumanCode;</p><p>　　void initial(HafumanTree &HT, int n)</p><p><b>　　{</b></p><p>　　for(int i = 0; i < 2 * n - 1;

46、i++)</p><p><b>　　{</b></p><p>　　HT[i].lchild = 0;</p><p>　　HT[i].rchild = 0;</p><p>　　HT[i].parent = 0;</p><p><b>　　}</b></p>

47、<p><b>　　}</b></p><p>　　int input(HafumanTree &HT, double* H)</p><p><b>　　{</b></p><p>　　printf("哈夫曼編碼、信源熵及編碼效率\n");</p><p>

48、;　　HT = (HafumanTree)malloc( KongJian * sizeof(HTNode));</p><p>　　if( HT == NULL )</p><p><b>　　return 0;</b></p><p>　　int i = 0;</p><p>　　double sum = 0.0;&

49、lt;/p><p>　　for( sum = 0.0; sum != 1.0; i++)</p><p><b>　　{</b></p><p>　　if(sum>1.0)</p><p>　　printf("輸入有錯誤，請關(guān)閉命令窗重新運(yùn)行\(zhòng)n");</p><p><

50、;b>　　else</b></p><p>　　printf("\n請輸入第%d個符號:",i+1);</p><p>　　scanf(" %c",&HT[i].ZiMu);</p><p>　　printf("\n 請輸入 %c的概率:",(HT+i)->ZiMu);<

51、;/p><p>　　scanf(" %lf",&HT[i].weight);</p><p>　　sum += (HT+i)->weight ;</p><p>　　*H = *H + ( - log(HT[i].weight) * HT[i].weight ) /log(2.0);</p><p>　　HT[i

52、].lchild = HT[i].rchild = i;</p><p><b>　　}</b></p><p>　　printf("\n實驗結(jié)果如下：\n");</p><p>　　initial(HT, i);</p><p><b>　　return i;</b></

53、p><p><b>　　}</b></p><p>　　void select(HafumanTree s, int n, int* a, int* b)</p><p><b>　　{</b></p><p>　　double min = 1.0;</p><p>　　for(

54、int i = 0; i < n ; i++)</p><p><b>　　{</b></p><p>　　if( ( min > (s+i)->weight ) && (s+i)->parent == 0 )</p><p><b>　　{</b></p><p

55、>　　min = (s+i)->weight;</p><p><b>　　*a = i;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　min = 1.0;</p><p>　　

56、for(int i = 0; i < n; i++)</p><p><b>　　{</b></p><p>　　if( i == *a )</p><p><b>　　continue;</b></p><p>　　if( min > (s+i)->weight &&am

57、p; (s+i)->parent == 0 )</p><p><b>　　{</b></p><p>　　min = (s+i)->weight;</p><p><b>　　*b = i;</b></p><p><b>　　}</b></p>&

58、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　void creatHafumanTree(HafumanTree &HT, int n)</p><p><b>　　{</b></p><p>　　int s1 =

59、0,</p><p><b>　　s2 = 0;</b></p><p>　　for( int i = n; i < 2 * n - 1; i++)</p><p><b>　　{</b></p><p>　　select(HT, i, &s1, &s2);</p>

60、;<p>　　HT[s1].parent = i;</p><p>　　HT[s2].parent = i;</p><p>　　HT[i].lchild = s1;</p><p>　　HT[i].rchild = s2;</p><p>　　HT[i].weight = HT[s1].weight + HT[s2].weig

61、ht;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int cmp(const void* a, const void* b)</p><p><b>　　{</b></p><p>　　retur

62、n -1;</p><p><b>　　}</b></p><p>　　int creatHafumanCode(HafumanTree HT, HafumanCode &HC, int n, double* CL)</p><p><b>　　{</b></p><p>　　if( (HC

63、 = (HafumanCode)malloc( n * sizeof(char*))) == NULL)</p><p><b>　　return 0;</b></p><p>　　char* code = NULL;</p><p>　　int num_1 = 0,</p><p><b>　　j = 0,&

64、lt;/b></p><p>　　start = 0,</p><p>　　number = 0;</p><p>　　for (int i=0; i < n; i++)</p><p><b>　　{</b></p><p>　　if( (code = (char*)malloc(

65、n * sizeof(char) ) ) == NULL )</p><p><b>　　return 0;</b></p><p>　　start = 0;</p><p>　　num_1 = HT[i].parent;</p><p><b>　　j = i;</b></p>&l

66、t;p>　　while ( num_1 != 0 )</p><p><b>　　{</b></p><p>　　if( HT[num_1].lchild == j )</p><p>　　code[start++] = '0';</p><p><b>　　else</b>&

67、lt;/p><p>　　code[start++] = '1';</p><p>　　number += 1;</p><p>　　j = num_1;</p><p>　　num_1 = HT[j].parent;</p><p><b>　　}</b></p><

68、;p>　　qsort(code, start, sizeof(char), cmp);</p><p>　　*(code+start) = '\0';</p><p>　　HC[i] = code;</p><p><b>　　}</b></p><p>　　*CL = (double)number

69、/(double)n;</p><p><b>　　}</b></p><p>　　void print(HafumanTree HT, HafumanCode HC, int n, double H, double CL)</p><p><b>　　{</b></p><p>　　for( in

70、t i = 0; i < n; i++)</p><p><b>　　{</b></p><p>　　printf("\n%c的編碼是: ",HT[i].ZiMu);</p><p>　　puts(HC[i]);</p><p><b>　　}</b></p>

71、<p>　　printf("\n 信源熵是：%f.",H);</p><p>　　printf("\n 編碼效率為：%f%%.",(H/CL)*100);</p><p><b>　　}</b></p><p>　　int main(void)</p><p><

72、b>　　{</b></p><p>　　HafumanTree string = NULL;</p><p>　　HafumanCode code_string = NULL;</p><p>　　double CL = 0.0;</p><p>　　double H = 0.0;</p><p>　

73、　int length = 0;</p><p>　　length = input(string, &H);</p><p>　　creatHafumanTree(string, length);</p><p>　　creatHafumanCode(string, code_string,length, &CL);</p><p

74、>　　print(string, code_string, length, H, CL);</p><p>　　printf("\n\n本次試驗成功!\n");</p><p>　　free(string);</p><p>　　free(code_string);</p><p><b>　　return

75、 0;</b></p><p><b>　　}</b></p><p>　　3.信源熵計算調(diào)試程序</p><p>　　#include<stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <

76、ctype.h></p><p>　　#include<math.h></p><p>　　int check(char* s);</p><p>　　void initial(void);</p><p>　　struct Shuju</p><p><b>　　{</b>&l

77、t;/p><p>　　long int cishu;</p><p>　　double gl;</p><p>　　char data;</p><p><b>　　}Jc[256];</b></p><p>　　int main(void)</p><p><b>

78、　　{</b></p><p>　　FILE* fp = NULL;</p><p>　　char* filename = NULL;</p><p>　　if( ( filename = (char*)malloc(500*sizeof(char)) )</p><p><b>　　==NULL )</b>

79、</p><p><b>　　{</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　do{</b></p><p>　　printf("請拖

80、入一個以字母命名的文件：");</p><p>　　gets(filename);</p><p>　　}while( ! check(filename) );</p><p>　　if( (fp = fopen(filename, "r") )== NULL )</p><p><b>　　{<

81、/b></p><p>　　printf("文件名為：'filename' 的文件不存在");</p><p><b>　　return 0;</b></p><p>　　fclose(fp);</p><p><b>　　}</b></p>

82、<p>　　printf("\n開始讀入文件內(nèi)容");</p><p>　　initial();</p><p>　　long int number = 0L;</p><p>　　double Xys = 0.0;</p><p>　　char ch = '0';</p><

83、p>　　while( !feof(fp) )</p><p><b>　　{</b></p><p>　　ch = fgetc(fp);</p><p>　　if( ch <= 255 && ch >=0)</p><p><b>　　{</b></p>

84、<p>　　ch=(ch<='Z'&&ch>='A')? (ch+32):ch;</p><p>　　Jc[ch].cishu += 1;</p><p>　　Jc[ch].data = ch;</p><p>　　number += 1;</p><p><b&

85、gt;　　}</b></p><p><b>　　}</b></p><p>　　for(int i = 0; i < 256 ;i++)</p><p><b>　　{</b></p><p>　　if( Jc[i].cishu == 0 )</p><p&g

86、t;<b>　　continue;</b></p><p>　　Jc[i].gl = static_cast<double>(Jc[i].cishu) / static_cast<double>(number);</p><p>　　Xys = Xys + ( - log(Jc[i].gl) * Jc[i].gl ) /log(2.0);<

87、;/p><p>　　printf("\n其中 %c 字符的個數(shù)為：%d ，概率是：%4.5f。",Jc[i].data,Jc[i].cishu,Jc[i].gl);</p><p><b>　　}</b></p><p>　　printf("\n該信源的熵是:%.4f.",Xys);</p>&

88、lt;p>　　printf("\n本次試驗正常運(yùn)行\(zhòng)n");</p><p>　　fclose(fp);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void initial(void)</p&g

89、t;<p><b>　　{</b></p><p>　　for(int i = 0;i<256;i++)</p><p><b>　　{</b></p><p>　　Jc[i].cishu = 0;</p><p><b>　　}</b></p>

90、<p><b>　　}</b></p><p>　　int check(char* s)</p><p><b>　　{</b></p><p>　　int i = 0;</p><p>　　while( *(s+i) != '\0')</p><p

91、><b>　　i++;</b></p><p>　　if( *(s+i-4) == '.'</p><p>　　&& *(s+i-3) == 't'</p><p>　　&& *(s+i-2) == 'x'</p><p>　　&

92、;& *(s+i-1) == 't')</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　return 0;</b&g