哈夫曼编码解码实验报告及程序.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=
显示全部