数据结构实验三哈夫曼树实验报告.doc

题目：哈夫曼编/译码器
题目要求：
写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0.
概要设计：
数据结构：
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char value;
} HNode; /* 结点结构体 */
函数：
void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n)
作用：构造一个哈夫曼树，并循环构建
int main ()
作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译
详细设计：
哈夫曼树的建立：
void DEMONHuffmanTree (HNode HuffNode[MAXNODE], int n)
{
int i = 0, j, m1, m2, x1, x2;
char x;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
while (i<n)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
scanf("%c",&x);
scanf("%c",&HuffNode[i].value); //实际值，可根据情况替换为字母
i++;
}
/* 输入 n 个叶子结点的权值 */
scanf("%c",&x);
for(i=0;i<n;i++)
{
scanf ("%d", &HuffNode[i].weight);
}
for (i=n; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i;
}
/* 循环构造 Huffman 树 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXQZ; // m1、m2中存放两个无父结点且结点权值最小的两个结点
x1=x2=0;//找出所有结点中权值最小、无父结点的