哈夫曼编码解码实验报告及程序.doc

实验1 哈夫曼编码译码的设计 实验题目： 对输入指令进行哈夫曼编/译码系统的设计 实验要求： 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。 实验内容： 1、用C++实现Huffman编码算法程序； 2、根据输入的n个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕 3、要求程序输出显示所有的码字以及译码结果； 实验原理： 根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。因此，构造哈夫曼树有此种方法： 1、由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}； 2、在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和； 3、在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； 4、重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。 所以，构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点，二是将这些结点加入到二叉树中，构建成哈夫曼树。解码则反之。 实验步骤： #includestdio.h #define maxbit 10 /*定义哈夫曼编码最大长度*/ #define maxvalue 10000 /*定义最大权值常量*/ #define maxnodenumber 100/*定义结点最大数目常量*/ typedef struct /*定义结点结构*/ { int weight; /*权重域值为整型*/ char character; int parent,lchild,rchild;/*3个指针域为整型值，即静态指针*/ }htnode; typedef struct /*定义保存一个叶子结点哈曼编码的结构*/ { int bit[maxbit]; /*哈曼编码域为一维数组*/ int start; /*开始位置域为整型*/ }hcodetype; /*定义哈曼编码类型*/ void main() /*主函数*/ {void gethuffmancode(htnode ht[],int n); htnode ht[maxnodenumber]; /*定义链表存储结构区数组*/ int i,j,m1,m2,k1,k2,n,a; printf(Please input n:); /*提示输出叶子结点个数*/ scanf(%d,n); printf(Please input character and weight:\n);/*提示输出各叶子结点的权值*/ for(i=0;i2*n-1;i++) /*数组ht初始化*/ {ht[i].weight=0; /*权重初始化为0*/ ht[i].character=\0; ht[i].parent=-1; /*3个指针域初始化为-1，即NULL*/ ht[i].lchild=-1; ht[i].rchild=-1; } for(i=0;in;i++) /*读入n个叶子结点的权重值*/ {fflush(stdin); scanf(%c %d,ht[i].character,ht[i].weight);} for(i=0;in-1;i++) / *控制n-1趟生成新结点构造哈夫曼树*/ {m1=maxvalue; /*最小权值变量为最大权值*/ m2=