哈夫曼编码报告.docx

实验项目：哈夫曼编码
1 •问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发 送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双 向传输信息的信道），每端都需要一个完整的编 /译码系统。试为这样的信息收发站设
计一个哈夫曼编/译码系统。
2 .一个完整的系统应具有以下功能：
）初始化（Initialzation ）。读入字符及每个字符的权值，建立哈夫曼树 HuffTree ;
）编码（Encoding ）。用已建好的哈夫曼树，对输入的文本进行编码形成报文，将报文显示出来；
3） 译码（Decoding ）。利用已建好的哈夫曼树，对输入的代码进行解码形成原文，并将结果显示；
4） 输出（Output ）:输出出现的字符以及各字符出现的频度（或概率）；输出各个字符的编码，输出代码 译出的原文；
：
理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上， 构造哈夫曼树，并用构造的哈夫曼
树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。
实验条件：学院提供公共机房，1台/学生微型计算机。
实验步骤（含实验代码）
第i次：完成程序的主框架设计，进行调试，验证其正确性；
第2次：详细设计，进行调试，验证其正确性；
第3次：进行整体调试，运行程序，对运行结果进行分析，完成实验报告
#i nclude<stdio. h>
#i nclude<stri ng. h>
#i nclude<malloc. h>
#defi ne MAXWORD 100 typedef struct
un sig ned int weight:char data;
un sig ned int pare nt,llchild, rrchild;
}HTNode, *HuffmanTree;
typedef char * *HuffmanCode;
//动态分配数组存储哈夫曼
树
/ /动态分配数组存储哈夫曼编码
typedef struct tnode
{ char ch; 〃 字符
int count; //出现次数
struct tnode *lchild,*rchild;
)BTree, *BT;
int a=0, b=0;int s[MAXWORD]:char str[MAXWORD]:
void main()
{ int n;int i=0;
HuffmanTree HT;HuffmanCode HC;
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int n);
void DispHCode (HuffmanTree HT, HuffmanCode HC, int n);
void Creatree(BT &p,char c); //Creatree() 和
InOrderTraverse()
void InOrderTraverse(BT p) ; //利用二叉树统计出现的字符及 个数void TTranChar(HuffmanTree HT, HuffmanCode HC,int n);
void Tran(HuffmanTree HT, int n) ; printf (〃请输入要用几种字符：〃);
BT root=NULL;
printf(〃\n〃)；
printf C'请输入字符串：\n〃)； scanf (〃%s〃, str);
while (str [i] !=' \0')
{Creatree(root, str[i]);i++;}
printfC字符及出现次数：\n〃)；
InOrderTraverse(root);
printf (〃\n〃)；
HuffmanCoding(HT, HC, n);
DispHCode(HT, HC, n);
Tran (HT, n);
TTranChar(HT, HC, n);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int n)
{ // w放n个权值，构造赫夫曼树HT, n个字符编码HC
void select (HuffmanTree t, int i, int &sl, int &s2):
int m, i, si, s2, start;char *cd;unsigned c, f:
HuffmanTree p;
if(n<=l) return;
m二2*nT;
HT=(Huffman