C语言,数据结构,哈夫曼编/译码器
发布网友
发布时间：2022-04-25 16:58
共1个回答
热心网友
时间：2023-10-20 22:01
哈弗曼编码
#include<stdio.h>
#include<stdlib.h>
typedef struct Huffman
{
int w; //权值
int l,r,p;//左孩子，右孩子，父亲
}HF;
int *p=NULL;
int Find(HF **hf,int val,int n)//在查找值为val的下标
{
int i;
for(i=1;i<=n;i++)
{
if(p[i]!=1)
{
if((*hf)[i].w==val)
{
p[i]=1;
break;
}
}
}
return i;
}
int Min(HF **hf,int n)//查找1~n中最小的权值
{
int i,min=1000;
for(i=1;i<=n;i++)
{
if(p[i]!=1)
{
if((*hf)[i].w<min)
min=(*hf)[i].w;
}
}
return min;
}
void Select(HF **hf,int *s1,int *s2,int n)//在第1~n中找出最小的两个权值
{
*s1=Find(hf,Min(hf,n),n);
*s2=Find(hf,Min(hf,n),n);
}
void Createhf(HF**hf,char **ch,int w[],int n)
{
int i,j;
int tmp1;
int s1,s2;
char *hfcode=NULL;
*hf=(HF*)malloc(sizeof(HF)*2*n);
p=(int*)malloc(sizeof(int)*2*n);
memset(p,0,sizeof(int)*2*n);
for(i=1;i<=n;i++)//初始化叶子节点
{
(*hf)[i].w=w[i-1];//给1~n个叶子节点赋权值
(*hf)[i].p=0;
(*hf)[i].r=0;
(*hf)[i].l=0;
}
for(;i<2*n;i++)//给n+1~2n-1个父节点初始化
{
(*hf)[i].w=0;
(*hf)[i].l=0;
(*hf)[i].r=0;
(*hf)[i].p=0;
}
for(i=n+1;i<2*n;i++)
{
Select(hf,&s1,&s2,i-1);
(*hf)[i].w=(*hf)[s1].w+(*hf)[s2].w;
(*hf)[i].l=s1;
(*hf)[i].r=s2;
(*hf)[s1].p=(*hf)[s2].p=i;
}
hfcode=(char*)malloc(n+1);
hfcode[n]='\0';
tmp1=n-1;
for(i=1;i<=n;i++)
{
for(j=i;(*hf)[j].p!=0;j=(*hf)[j].p)
{
if(j==(*hf)[(*hf)[j].p].l)
{
hfcode[tmp1--]='0';
}
else if(j==(*hf)[(*hf)[j].p].r)
{
hfcode[tmp1--]='1';
}
}
strcpy(ch[i-1],&hfcode[++tmp1]);
tmp1=n-1;
}
free(hfcode);
hfcode=NULL;
}
void main()
{
HF *hf=NULL;
int n,i;
char**ch=NULL;
int *w=NULL;
puts("请输入叶子结点数：");
scanf("%d",&n);
ch=(char**)malloc(sizeof(char *)*n);
for(i=0;i<n;i++)
{
ch[i]=(char*)malloc(sizeof(char)*10);
}
w=(int*)malloc(sizeof(int)*n);
puts("请输入叶子节点的权值：");
for(i=0;i<n;i++)
{
scanf("%d",&w[i]);
}
Createhf(&hf,ch,w,n);
for(i=0;i<n;i++)
{
puts(ch[i]);
}
free(ch);
ch=NULL;
free(w);
w=NULL;
free(hf);
hf=NULL;
free(p);
p=NULL;
}
运行结果
望采纳！
追答你可以把输入那块改成初始化
