weixin_29436869 于 2015.06.30 17:26 提问

4个回答

u012216727      2015.06.30 17:29

qq_27969037 点击[http://pinyin.cn/1DSzxV1QzFN 查看这张图片。[访问验证码是：446080请妥善保管]

gengxiaoming7   2015.06.30 17:44

u012736907   2015.06.30 18:22

u012736907   2015.06.30 18:25

`````` // 哈夫曼树及编码.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define MAX 10000
#define NUM 10000

typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
}HNodeType;

typedef struct
{
int bit[MAX];
int start;
}HCodeType;
HNodeType HFMTree[MAX];
HCodeType HuffCode[MAX];

/*创建哈夫曼树*/
void Create_HuffMTree(HNodeType HFMTree[],int n)
{
int m1,m2,x1,x2;
for(int i=0;i<2*n-1;i++)
{
HFMTree[i].weight=0;
HFMTree[i].parent=-1;
HFMTree[i].lchild=-1;
HFMTree[i].rchild=-1;
}
for(int i=0;i<n;i++)
{
printf("添加的第%d个叶子值为：",i+1);
scanf_s("%d",&HFMTree[i].weight);
}
for(int i=0;i<n-1;i++)
{
x1=x2=MAX;
m1=m2=0;
for(int j=0;j<n+i;j++)
{
if(HFMTree[j].parent==-1&&HFMTree[j].weight<x1)
{
x2=x1;
m2=m1;
x1=HFMTree[j].weight;
m1=j;
}
else if(HFMTree[j].parent==-1&&HFMTree[j].weight<x2)
{
x2=HFMTree[j].weight;
m2=j;
}

}
HFMTree[m1].parent=n+i;
HFMTree[m2].parent=n+i;
HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;
HFMTree[n+i].lchild=m1;
HFMTree[n+i].rchild=m2;
}
}

/*哈夫曼编码*/
void HaffmanCode(HNodeType HFMTree[],HCodeType HuffCode[],int n)
{
HCodeType cd;
int c,p;
for(int i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HFMTree[c].parent;
while(p!=-1)
{
if(HFMTree[p].lchild==c)
{
cd.bit[cd.start]=0;
}
else if(HFMTree[p].rchild==c)
{
cd.bit[cd.start]=1;
}
cd.start--;
c=p;
p=HFMTree[c].parent;
}

for(int j=cd.start+1;j<n;j++)
{
HuffCode[i].bit[j]=cd.bit[j];
}
HuffCode[i].start=cd.start+1;
}
for(int i=0;i<n;i++)
{
printf("\n叶子的值为%d的编码：",HFMTree[i].weight);
for(int j=HuffCode[i].start;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int n=5;
printf("哈夫曼树的叶子结点个数n=");
scanf_s("%d",&n);
Create_HuffMTree(HFMTree,n);
printf("\n哈夫曼树表示为：\n");
for (int i=0;i<2*n-1;i++)
printf("i=%d\tweight:%d\tlchild=%d\trchild=%d\tparent=%d\n",i,HFMTree[i].weight,HFMTree[i].lchild,HFMTree[i].rchild,HFMTree[i].parent);
printf("\n哈夫曼树的叶子节点的编码为:");
HaffmanCode(HFMTree,HuffCode,n);
printf("\n\n");
return 0;
}

``````