请写出赫夫曼算法的C代码
时间: 2023-03-10 20:15:21 浏览: 60
// 以下是赫夫曼算法的C代码:#include<stdio.h>
#include<stdlib.h>// 定义Huffman树结点
typedef struct node
{
int weight;
int lchild;
int rchild;
int parent;
}HuffmanTree;// 定义Huffman编码
typedef struct
{
char cd[10];
int start;
}HuffmanCode;// 创建Huffman树
void CreateHuffmanTree(HuffmanTree ht[], int n)
{
int i,j,m1,m2,x1,x2;
// 初始化Huffman树
for(i=1;i<=n;i++)
{
ht[i].weight=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].parent=0;
}
// 建立Huffman树
for(i=1;i<=n-1;i++)
{
m1=m2=32767;
x1=x2=0;
for(j=1;j<=n+i-1;j++)
{
if(ht[j].weight<m1 && ht[j].parent==0)
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if(ht[j].weight<m2 && ht[j].parent==0)
{
m2=ht[j].weight;
x2=j;
}
}
ht[x1].parent=n+i-1;
ht[x2].parent=n+i-1;
ht[n+i-1].weight=ht[x1].weight+ht[x2].weight;
ht[n+i-1].lchild=x1;
ht[n+i-1].rchild=x2;
}
}// 根据Huffman树,创建Huffman编码
void CreateHuffmanCode(HuffmanTree ht[], HuffmanCode hc[], int n)
{
int i,j,c,p;
char cd[10];
// 初始化Huffman编码
for(i=1;i<=n;i++)
{
hc[i].start=n;
hc[i].cd[n]='\0';
}
cd[n-1]='\0';
// 生成Huffman编码
for(i=1;i<=n;i++)
{
c=i;
p=ht[i].parent;
j=n-1;
while(p!=0)
{
if(ht[p].lchild==c)
cd[j]='0';
else
cd[j]='1';
j--;
c=p;
p=ht[p].parent;
}
for(j=0;j<n;j++)
hc[i].cd[j]=cd[j];
hc[i].start=j;
}
}int main()
{
int n;
HuffmanTree ht[100];
HuffmanCode hc[100]; printf("请输入Huffman树的结点数:");
scanf("%d",&n);
CreateHuffmanTree(ht, n);
CreateHuffmanCode(ht, hc, n);
printf("结点\t权值\t父结点\t左孩子\t右孩子\tHuffman编码\n");
for(int i=1;i<=n;i++)
{
printf("%d\t%d\t%d\t%d\t%d\t%s\n",i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild,hc[i].cd+hc[i].start);
}
return 0;
}