電文的編碼和譯碼

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告課程設(shè)計題目：電文的編碼和譯碼姓 名：*專 業(yè)：信息管理與信息系統(tǒng)學(xué) 號：*班 級：*指導(dǎo)教師：* 2014年6月東華理工大學(xué)課程設(shè)計評分表學(xué)生姓名：* 班級：* 學(xué)號：*課程設(shè)計題目：電文的編碼與譯碼項目內(nèi)容滿分實 評選題能結(jié)合所學(xué)課程知識、有一定的能力訓(xùn)練。符合選題要求 （5人一題）10工作量適中，難易度合理10能力水平能熟練應(yīng)用所學(xué)知識，有一定查閱文獻及運用文獻資料能力10理論依據(jù)充分，數(shù)據(jù)準(zhǔn)確，公式推導(dǎo)正確10能應(yīng)用計算機軟件進行編程、資料搜集錄入、加工、排版、制圖等10能體現(xiàn)創(chuàng)造性思維，或有獨特見解10成果質(zhì)量總體設(shè)計正確、合理，各項技術(shù)指標(biāo)符合要求。10說明書

2、綜述簡練完整，概念清楚、立論正確、技術(shù)用語準(zhǔn)確、結(jié)論嚴(yán)謹(jǐn)合理；分析處理科學(xué)、條理分明、語言流暢、結(jié)構(gòu)嚴(yán)謹(jǐn)、版面清晰10設(shè)計說明書欄目齊全、合理，符號統(tǒng)一、編號齊全。格式、繪圖、表格、插圖等規(guī)范準(zhǔn)確，符合國家標(biāo)準(zhǔn)10有一定篇幅，字符數(shù)不少于500010總 分100指導(dǎo)教師評語： 指導(dǎo)教師簽名： 年 月 日一、需求分析1二設(shè)計內(nèi)容11）問題描述12）設(shè)計要求13)分析與實現(xiàn)14）功能要求25）概要設(shè)計2三. 調(diào)試61）建立哈夫曼樹62）編碼73）譯碼8四. 實驗心得體會8一、需求分析 當(dāng)今社會的一些領(lǐng)域，電文仍然被應(yīng)用著，編寫一個電文編碼和譯碼系統(tǒng)還是有必要的，哈夫曼編碼是廣泛用于數(shù)據(jù)文件壓縮的十

3、分有效的編碼方法。其壓縮通常在20%90%之間。哈夫曼編碼算法使用字符在文件中出現(xiàn)的頻率表來建立一個用0,1串表示各字符的最優(yōu)表示方式。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條分支上路徑上的“0”或“1”的序列作為各個葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。該設(shè)計是對輸入的一串電文字符實現(xiàn)哈夫曼編碼，或?qū)蚵幋a生成的代碼串進行譯碼，輸出電文字符串。二設(shè)計內(nèi)容1）問題描述 從鍵盤接收一串電文字符，輸出對應(yīng)的哈夫曼編碼。同時能翻譯有哈夫曼

4、編碼生成的代碼串，輸出對應(yīng)的電文字符串。2）設(shè)計要求（1）構(gòu)造一顆Huffman樹。（2）實現(xiàn)Huffman編碼，并用Huffman編碼生成的代碼串進行譯碼。（3）程序中字符和權(quán)值時可變的，實現(xiàn)程序的靈活性。3)分析與實現(xiàn) 在電報通信中，電文是以二進制代碼傳送的。在發(fā)送時，需要將電文中的字符轉(zhuǎn)換成二進制代碼串，即編碼；在接收時，要將收到的二進制代碼轉(zhuǎn)化為對應(yīng)的字符序列，即譯碼。我們知道，字符集中的字符被使用的頻率是非均勻的。在傳送電文時，要想使電文總長盡可能短，就需要讓使用頻率高的編碼長度盡可能的短。因此，若對某字符集進行不等長編碼的設(shè)計，則要求任意一個字符的編碼都不是其他字符編碼的前綴，這種

5、編碼稱做前綴編碼。由哈夫曼樹求得的編碼是最優(yōu)前綴碼，也叫做Huffman編碼。給出字符集和各個字符的概率分布，構(gòu)造哈夫曼樹，將哈夫曼樹種每個分支點的左分支標(biāo)為0，右分支標(biāo)為1，將根到每個葉子路徑上的標(biāo)號連起來，就是該葉子所代表字符的編碼。4）功能要求（1）初始化，鍵盤輸入字符集大小你，n個字符和n個權(quán)值，建立哈夫曼樹。（2）編碼，利用建好的哈夫曼樹生成Huffman編碼。（3）輸出編碼。（4）譯碼功能。（5）字符頻度如下：字符ABCDEFGHIJKLM頻度18664132232103211547571232字符NOPQRSTUVWXYZ頻度205763151485180238181165）概要

6、設(shè)計(1)關(guān)系以及功能 程序由以下模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個模塊的功能： avoid main() b. int HuffmanCreate(HuffNode * ht) /生成huffman樹/ cvoid Encoding(HuffNode ht,HuffCode hcd,int n) /編碼部分/ d. void Decoding(HuffNode ht,HuffCode hcd,int n) /譯碼部分/main（）其流程圖如下:輸入待編碼字符函數(shù)編碼函數(shù)譯碼函數(shù)初始化函數(shù)(2) 主要模塊程序流程圖a. 函數(shù)流程圖 結(jié)束 哈夫曼譯碼 哈夫曼編碼 建立哈夫曼樹

7、統(tǒng)計字符種類及頻率字符總數(shù)n 打開文件？ 開始 否 是 流程圖解釋： 該圖比較簡單，主要是調(diào)用各個函數(shù)模塊，首先打開已經(jīng)存在的文件，然后統(tǒng)計總的字符數(shù)以及出現(xiàn)的各個字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基礎(chǔ)上對其進行編碼，編碼之后才是譯碼。最后輸出結(jié)束。 b. 構(gòu)造哈夫曼樹 開始 第i個節(jié)點權(quán)值 i=n？ 否 是 第i個根節(jié)點 i=2*n-1 否 是 創(chuàng)建哈夫曼樹 輸出字符統(tǒng)計情況 i=n？否 是 結(jié)束 流程圖注釋： 該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入n個葉結(jié)點的權(quán)值，當(dāng)i=n 是循環(huán)結(jié)束。然后進行哈夫曼樹的構(gòu)建，當(dāng)i=2*n-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計情況。c.

8、 哈夫曼編碼 開始 d.start=n+1，cd-d.start=0htf.left=c?是 否d.cd-d.start=1d.cd-d.start=0i<=n? 是 否 結(jié)束流程圖解釋： 該流程圖表示哈夫曼編碼情況。首先初始化，d.start=n+1,d.cdd.start=0；然后進行編碼，即當(dāng)htf.left=c時，d.cdd.start=0，當(dāng)htf.left!=c時，d.cd-d.start=1。這個編碼循環(huán)一直到i=n時結(jié)束。（3）相關(guān)函數(shù)解釋 a. 生成huffman樹 【 int HuffmanCreate(HuffNode * ht) 】 哈夫曼樹的建立由哈夫曼算法的定

9、義可知，初始森林中共有n棵只含有根節(jié)點的二叉樹。然后將當(dāng)前森林中的兩棵根節(jié)點權(quán)值最小的二叉樹htp1和p2（用p1和p2指示這兩個節(jié)點在數(shù)組中的位置），合并成一棵新的二叉樹hti，使得htp1和htp2成為hti的左右孩子，而且hti的權(quán)值為htp1和htp2的權(quán)值之和。每合并一次，森林中就減少一棵樹，產(chǎn)生一個新節(jié)點。顯然要運行n-1次合并，所以共產(chǎn)生n-1個新節(jié)點。它們都是具有兩個孩子的分支節(jié)點。由此可知，最終求得的哈夫曼樹中一共有2n-1個節(jié)點，其中n個節(jié)點是初始森林的n個孤立節(jié)點。由此可知，我們可以利用一個大小為2n-1的一維數(shù)組來存儲哈夫曼樹中的節(jié)點。b. 編碼 【void Encod

10、ing(HuffNode ht,HuffCode hcd,int n)】 該函數(shù)實現(xiàn)對哈夫曼樹的編碼，先申請一個能存儲字符編碼的臨時空間cd，編碼從哈夫曼樹的葉子節(jié)點hti開始，找到其父母節(jié)點htf，然后根據(jù)父母節(jié)點判斷孩子節(jié)點的左右位置，左邊置代碼0，右邊置代碼1，代碼存放在cdstrat中，然后把htf作為出發(fā)點，重復(fù)上述過程直到找到根節(jié)點為止。并將0,1這樣的代碼從后往前逆序存放在cd中，用變量start指示編碼在數(shù)組cd中的起始位置，start的初始位置為n，生成一個代碼后，start的值就減1。c. 譯碼 【void Decoding(HuffNode ht,HuffCode hcd

11、,int n)】 譯碼時，先輸入一串由0和1組成的二進制代碼串，并將單個字符依次存放在數(shù)組ch中，以#為結(jié)束標(biāo)志。然后將代碼與原先生成的哈夫曼編碼表相比較，若為0，則轉(zhuǎn)向左子樹；若為1，則轉(zhuǎn)向右子樹，直到葉節(jié)點結(jié)束。三. 調(diào)試1）建立哈夫曼樹A-Z 26個字母的哈夫曼樹 2）編碼3）譯碼四. 實驗心得體會 通過這次的課程設(shè)計，我實在獲益匪淺。數(shù)據(jù)結(jié)構(gòu)是本學(xué)期開展的一門學(xué)科，學(xué)習(xí)好這門學(xué)科是非常重要的，在以后的程序設(shè)計方面這門學(xué)科能給我們很大的幫助。同時，學(xué)習(xí)這門學(xué)科也是艱辛的，因為它比較難懂，這不僅需要我們要發(fā)揮我們的聰明才志，還需要我們在不斷的實踐中領(lǐng)悟。這次的程序設(shè)計對我來說無疑是一個具大

12、的考驗，從接起課題后，我就一直為實現(xiàn)程序而努力，翻閱相關(guān)書籍、在網(wǎng)上查找資料。因為開始時基礎(chǔ)不是很好，過程中遇到了不少的阻礙，編寫程序的進度也比較慢。雖然如此，但是通過自己的努力與老師的指導(dǎo)，我對這次實驗的原理有了一定的理解，并最終運行出了結(jié)果。本次課程設(shè)計不但使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。而且許多的錯誤讓我明白了一個道理-細(xì)心是非常重要的。同時，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r候和同學(xué)一起交流探討是一個十分好的學(xué)習(xí)機會。請教老師也很重要，因為畢竟我們是新手，對于某些問題很難弄清楚。而且，某些錯誤對于我

13、們來說有時候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時間。 作為信息管理專業(yè)的學(xué)生，我們應(yīng)該很好的掌握這門學(xué)科。在課堂上，我們能夠?qū)W到許多的理論知識，但我們很少有過自己動手實踐的機會！課程設(shè)計就是為解決這個問題提供了一個平臺。在課程設(shè)計過程中，我們每個人或者幾個人選擇一個課題，認(rèn)真研究，根據(jù)課堂講授內(nèi)容，借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強我們的獨立思考能力和動手能力；通過編寫實驗代碼和調(diào)試運行，我們可以逐步積累調(diào)試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。在課程設(shè)計過程中，我們不但有自己的獨立思考，還借助各種參考文獻來幫助我們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強了交流，在對問題的認(rèn)識方面可以交換不同的意見。同時，師生之間的互動也隨之改善，我們可以通過具體的實例來從老師那學(xué)到更多的實用的知識。 數(shù)據(jù)結(jié)構(gòu)課程具有比較強的理論性，同時也具有較強的可應(yīng)用性和實踐性。課程設(shè)計是