#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char** Huffmancode;
typedef struct Huffman{
int weight;
int parent;
int lchild;
int rchild;
}Huffman,*Huff;
int select(Huff HT,int val);
Huff create_HuffmanTree(int n);
void huffmancoding(Huff HT,Huffmancode *HC,int n);
int main()
{
int n,i;
printf("请输入节点个数\n");
scanf("%d",&n);
Huffmancode HC;
Huff HT = create_HuffmanTree(n);
huffmancoding(HT,&HC,n);
for(i = 1;i<=n;i++)
{
printf("权重为%d的编码为:%s\n",HT[i].weight,HC[i]);
}
return 0;
}
int select(Huff HT,int val)
{
int i,t; //t存放临时weight值
int m; // 存放最小值的位置
for(i = 1;i<val;i++)
{
if(HT[i].parent == 0)
{
t = HT[i].weight;
m = i;
break;
}
}
for(i = 1;i<val;i++)
{
if(HT[i].parent == 0)
if(HT[i].weight < t)
{
t = HT[i].weight;
m = i;
}
}
return m;
}
Huff create_HuffmanTree(int n)
{
Huff HT = (Huff)malloc(sizeof(Huffman)*n*2); //n个节点要合并 n-1 次，新增 n-1个 节点，则需要创建n+(n-1) = 2n-1个节点
int i,j; //but 一般不用数组下标为零的元素，则创建2n个节点，只有1~2n-1存放有效数据
int val; //存放节点值
for(i = 1;i< (2*n);i++) //哈夫曼树的初始化
{
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
}
printf("请输入各个节点的权重\n");
for(j = 1;j<=n;j++) //n个节点的赋值
{
scanf("%d",&val);
HT[j].weight = val;
}
int s1,s2; //s1,s2存放目前数组中所有元素的 最小元素和次小元素位置
for(j = n+1;j<(2*n);j++)
{
s1 = select(HT,j); //选出最小值
HT[s1].parent = j;
s2 = select(HT,j); //选出第二小值
HT[s2].parent = j;
HT[j].weight = HT[s1].weight+HT[s2].weight;
HT[j].lchild = s1;
HT[j].rchild = s2;
}
return HT;
}
void huffmancoding(Huff HT,Huffmancode *HC,int n) //HC这里需要传递指针
{
int i;
int f,m;
(*HC)= (char**)malloc((n+1)*sizeof(char *));
char *ch = (char *)malloc(sizeof(char)*n);
ch[n-1] = '\0';
int start; //字符串起始复制位置
for(i = 1;i<=n;i++)
{
f = HT[i].parent;
m = i;
start = n-2;
while(f != 0)
{
if(HT[f].lchild == m)
ch[start] = '0';
if(HT[f].rchild == m)
ch[start] = '1';
m = f;
f = HT[f].parent;
start--;
}
(*HC)[i] = (char*)malloc((n-start-1)*sizeof(char));
strcpy((*HC)[i],&ch[start+1]); //strcpy(char *,char *)
//printf("%s",(*HC)[i]);
}
free(ch);
}