哈夫曼編碼報告

1、實驗項目：哈夫曼編碼1.問題描述：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這 要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（解碼）。對于 雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站設(shè)計一個哈夫曼編/譯碼系統(tǒng)。. 一個完整的系統(tǒng)應(yīng)具有以下功能：1）初始化（Initialzation ）。讀入字符及每個字符的權(quán)值，建立哈夫曼樹 HuffTree ;2）編碼（Encoding ）。用已建好的哈夫曼樹，對輸入的文本進行編碼形成報文，將報文顯示出來；3）譯碼（Decoding）。

2、利用已建好的哈夫曼樹，對輸入的代碼進行解碼形成原文，并將結(jié)果顯示；4）輸出（Output ）:輸出出現(xiàn)的字符以及各字符出現(xiàn)的頻度（或概率）；輸出各個字符的編碼，輸 出代碼譯出的原文；.實驗?zāi)康模豪斫夤蚵鼧涞奶卣骷捌鋺?yīng)用；在對哈夫曼樹進行理解的基礎(chǔ)上，構(gòu)造哈夫曼樹，并用構(gòu)造的哈夫 曼樹進行編碼和譯碼；通過該實驗，使學(xué)生對數(shù)據(jù)結(jié)構(gòu)的應(yīng)用有更深層次的理解。.實驗條件 :學(xué)院提供公共機房，1臺/學(xué)生微型計算機。.實驗步驟（含實驗代碼）第1次：完成程序的主框架設(shè)計，進行調(diào)試，驗證其正確性；第2次：詳細設(shè)計，進行調(diào)試，驗證其正確性；第3次：進行整體調(diào)試，運行程序，對運行結(jié)果進行分析，完成實驗報告 。#i

3、nclude#include #include#define MAXWORD 100typedef struct unsigned int weight;char data;unsigned int parent,llchild,rrchild;HTNode,*HuffmanTree;arent=0;(*p).llchild=0;(*p).rrchild=0;for(p=HT+1,i=0;in;+i,+p) (*p).data=stri;(*p).weight=si;for(;i=m;+i,+p)(*p).parent=0;for(i=n+1;i=m;+i)arent=HTs2.parent=

4、i;HTi.llchild=s1;HTi.rrchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);arent;f!=0;c=f,f=HTf.parent)if(HTf.llchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n -start)*sizeof(char);strcpy(HCi,&cdstart);eightk&tj.parent=0)k=tj.weight,flag=j;tflag.parent=1;retur

5、n flag;void Creatree(BT &p,char c)ata);puts(HCi);void Tran(HuffmanTree HT,int n)lchild;elsei=HTi.rrchild;if(HTi.llchild=0)printf(%c,HTi.data);i=2*n -1; j+; printf(n);void TTranChar(HuffmanTree HT,HuffmanCode HC,int n) char ss50;int i,j;ata!=ssi)&(j=n)j+；printf(%s,HCj);i+；printf(n);.實驗結(jié)果與總結(jié):產(chǎn)輸入要用幾種字符

6、：4請輸入字符串；aarfffjjjjjjjbbbbb 字符及出現(xiàn)次數(shù)： 且的個數(shù)為：2匕的個數(shù)為：5 尸的個澈為:4 j的個數(shù)為：？輸出哈夫曼編碼： TOC o 1-5 h z 11O10f:111J：0輸入發(fā)送的（0. 1編碼（以為結(jié)束標志）t 110101110010101111100 擇碼后的字符為ahf j北bfaj 輸入字符串：jj j j jj j00111111110100000011111100Ptes居key tq continue總結(jié)：在實現(xiàn)哈夫曼樹編碼的過程中，首先構(gòu)建哈夫曼樹，并用動態(tài)分配數(shù) 組存儲，也用動態(tài)分配數(shù)組存儲哈夫曼編碼表。程序書上雖然有一部分可借鑒 的代碼，自己只需要編寫幾個函數(shù)即可，但在編寫程序時也遇到一些問題，開 始統(tǒng)計字符串中出現(xiàn)的各種字符及其次數(shù)時，將字母存放數(shù)組中，但是考慮到 字母出現(xiàn)的不同，完全初始化再統(tǒng)計其出現(xiàn)的個數(shù)，不僅占用空間并且時間復(fù) 雜度高。后來采用二叉樹統(tǒng)計出現(xiàn)的字母及個數(shù)，實現(xiàn)了輸入字母種類的靈活 性。通過此次實驗，明白了了解數(shù)據(jù)存儲的具體方式的重要性，在這次實驗中