電文的編碼和譯碼

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

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

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

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

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

6、設(shè)計(jì)(1)關(guān)系以及功能 程序由以下模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個(gè)模塊的功能： 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)計(jì)字符種類及頻率字符總數(shù)n 打開文件？ 開始 否 是 流程圖解釋： 該圖比較簡單，主要是調(diào)用各個(gè)函數(shù)模塊，首先打開已經(jīng)存在的文件，然后統(tǒng)計(jì)總的字符數(shù)以及出現(xiàn)的各個(gè)字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基礎(chǔ)上對其進(jìn)行編碼，編碼之后才是譯碼。最后輸出結(jié)束。 b. 構(gòu)造哈夫曼樹 開始 第i個(gè)節(jié)點(diǎn)權(quán)值 i=n？ 否 是 第i個(gè)根節(jié)點(diǎn) i=2*n-1 否 是 創(chuàng)建哈夫曼樹 輸出字符統(tǒng)計(jì)情況 i=n？否 是 結(jié)束 流程圖注釋： 該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入n個(gè)葉結(jié)點(diǎn)的權(quán)值，當(dāng)i=n 是循環(huán)結(jié)束。然后進(jìn)行哈夫曼樹的構(gòu)建，當(dāng)i=2*n-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計(jì)情況。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；然后進(jìn)行編碼，即當(dāng)htf.left=c時(shí)，d.cdd.start=0，當(dāng)htf.left!=c時(shí)，d.cd-d.start=1。這個(gè)編碼循環(huán)一直到i=n時(shí)結(jié)束。（3）相關(guān)函數(shù)解釋 a. 生成huffman樹 【 int HuffmanCreate(HuffNode * ht) 】 哈夫曼樹的建立由哈夫曼算法的定

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

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

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

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

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