資源描述：
《哈夫曼編碼解碼.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、Huffman編/解碼一．問題描述1.題目?jī)?nèi)容：利用Huffman編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)進(jìn)行預(yù)先編碼，在接收端進(jìn)行解碼。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/解碼系統(tǒng)。2.基本要求：一個(gè)完整的系統(tǒng)應(yīng)該具有以下功能：1.I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立Huffman樹，并將它存入hfmTree中。2.E：編碼（Encoding）。利用已經(jīng)建好的Huffman樹（如果不在內(nèi)存，則應(yīng)從文件hfmTre
2、e中讀?。瑢?duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。3.D：解碼（Decoding）。利用已經(jīng)建立好的Huffman樹將文件CodeFile中的代碼進(jìn)行解碼，結(jié)果存入TextFile中。4.P：打印代碼文件（Print）。將文件CodeFile以緊湊的格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrint中。5.T：打印Huffman樹（TreePrinting）。將已經(jīng)在內(nèi)存中的Huffman樹以直觀的形式（凹入的形式）顯示在終端上，同時(shí)將此字符形式的Huffman樹寫入文件TreePrint中。3.測(cè)試數(shù)
3、據(jù)：用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立Huffman樹，并對(duì)以下報(bào)文進(jìn)行編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161二．需求分析1.編碼結(jié)果以文本的方式存儲(chǔ)在文件CodeFile中。2.用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出（quit）。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了Q為止。3.在程序的一次執(zhí)行過程中，第一次
4、執(zhí)行I，D，C命令后，Huffman樹已經(jīng)存在在內(nèi)存中了，不必再讀入。每次執(zhí)行中不一定執(zhí)行了I命令，因?yàn)槲募fmTree可能已經(jīng)早已建好。4.測(cè)試數(shù)據(jù)的權(quán)值（頻度）應(yīng)為正整數(shù)。三．概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，需要順序棧一個(gè)抽象數(shù)據(jù)類型。1．棧的抽象數(shù)據(jù)類型定義為：ADTStack{數(shù)據(jù)對(duì)象：D={ai
5、ai∈CharSet,i=1,2..,n}數(shù)據(jù)關(guān)系:R1={
6、ai-1,ai∈D,i=2,...,n}基本操作:InitStack（&S）操作結(jié)果：構(gòu)建一個(gè)空棧S。DestroyStack(&S)操作結(jié)果：銷毀棧S。參數(shù)說明：棧S已存在。ClearStack(
7、&S)操作結(jié)果:將棧清空。參數(shù)說明：棧S已存在。StackEmpty（S）操作結(jié)果:若棧為空則返回TURE；否則返回FALSE。參數(shù)說明：棧S已存在。StackLength（S）操作結(jié)果:返回棧中的元素個(gè)數(shù)，亦即棧的長(zhǎng)度。參數(shù)說明：棧S已存在。GetTop(S,&e)操作結(jié)果:將e賦值為棧S的棧頂元素。參數(shù)說明：棧S已存在且非空。Push(&S,e)操作結(jié)果:將e插入為棧S的新的棧頂元素。參數(shù)說明：棧S已存在。Pop(&S,&e)操作結(jié)果:若棧非空，刪除棧S的棧頂元素，并將值賦給e。參數(shù)說明：棧S已存在。StackTraverse(S)操作結(jié)果:從棧低到棧頂依次輸出S的各個(gè)元素
8、。參數(shù)說明：棧S已存在。}2．程序包含三個(gè)模塊：1）主函數(shù)模塊2）初始化模塊（包括了選擇子模塊）3）編碼模塊4）解碼模塊5）打印代碼文件模塊6）打印Huffman樹模塊（包括了打印子模塊）各模塊之間調(diào)用關(guān)系如圖所示：主函數(shù)模塊編碼模塊解碼模塊打印代碼模塊打印樹模塊初始化模塊四．詳細(xì)設(shè)計(jì)1．元素類型、結(jié)點(diǎn)類型和指針類型。typedefchar**Huffmancode;／／哈夫曼編碼的類型typedefchar*Huffmanco;／／哈夫曼編碼數(shù)組元素的類型typedefstructSqStack_type{char*elem;intstacksize;inttop;}SqSt
9、ack;typedefstruct{char*elem;int*value;}SqNode,*SqNodelist;typedefstructHTNode_type{／／哈夫曼樹結(jié)點(diǎn)類型intweight;intparent,lChild,rChild;}HTNode,*HuffTree;２.主函數(shù)的偽碼算法如下：voidmain(){chara;intn=0,num=0;intflag=0;intmsize=STACK_INIT_SIZE;／／num記錄TOBETRAN中字母?jìng)€(gè)數(shù)，flag
