哈夫曼树实验报告.doc

哈夫曼树实验报告
实验报告
实验名称 Huffman编码
专业班级 计科三班 姓名 学号
char data; //结点字符
int weight; //结点权值
int parent,lchild,rchild; //父子结点
}HTNode,* HuffmanTree;
typedef char * *HuffmanCode;
void Select(HuffmanTree HT, int m, int& s1, int& s2)
{
int i;
s1 = s2 = 1;
for(i=1; i<=m; i++)
{
if (HT[i].parent==0)
{
s1=i;
break;
}
}
for(i=i+1; i<=m; i++)
{
if (HT[i].parent==0 && HT[s1].weight>HT[i].weight)
s1=i;
}
for(i=1; i<=m; i++)
{
if(HT[i].parent==0&&i!=s1)
{
s2=i;
break;
}
}
for(i=i+1; i<=m; i++)
{
if(HT[i].parent==0 && HT[i].weight<HT[s2].weight && i!=s1)
s2=i;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n)
{ //w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼树编码HC
int f;
int m,i,s1,s2;
int c;
HuffmanTree p;
char *cd;
if (n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for( ;i<=m;++i,++p)
(*p).parent=0;
for(i=n+1;i<=m;++i) //建立赫夫曼树
{ //在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号分别为s1,s2.
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//****从叶子到根逆向求每个字符的赫夫曼编码****
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作区间
cd[n-1]='\0'; //编码结束符
for(i=1;i<=n;++i) //逐个字符求赫夫曼树编码
{ int start;
start=n-1;