C语言版数据结构程序设计题目：哈夫曼数编码、译码

Question

如题所述

Answer 1

这是哈弗曼编码的C语言代码，是我去年写的《数据结构》的实验，译码的代码没找到。这个先给你吧
#include <stdio.h>
#include <stdlib.h>

#define maxnode 100
#define maxvalue 9999
typedef struct huffmantree //定义哈弗曼树结点类型
{
int weight;
int parent,lchild,rchild;
}htnode;

#define maxbit 10
typedef struct huffmantreetype //定义哈弗曼编码类型
{
int bit[maxbit];
int start;
}htnodetype;

static htnode ht[maxnode];
void Creat_ht(int n) //生成哈弗曼树
{
int i,j,m1,m2,k1,k2;
for(i=0;i<2*n-1;i++)
{ht[i].weight=0;
ht[i].parent=-1;
ht[i].lchild=-1;
ht[i].rchild=-1;
}
for(i=0;i<n;i++)
{printf("Please input htnode[%d].weight:",i);scanf("%d",&ht[i].weight);}
for(i=0;i<n-1;i++) //生成n-1个新结点，与n个叶子结点共2n-1个结点
{m1=maxvalue;
m2=maxvalue;
k1=0;k2=0;
for(j=0;j<n+i;j++)
{if(ht[j].parent==-1&&ht[j].weight<m1)
{m2=m1;k2=k1;m1=ht[j].weight;k1=j;}
else if(ht[j].parent==-1&&ht[j].weight<m2)
{m2=ht[j].weight;k2=j;}
}
ht[k1].parent=n+i;ht[k2].parent=n+i;
ht[n+i].weight=ht[k1].weight+ht[k2].weight;
ht[n+i].lchild=k1;ht[n+i].rchild=k2;
}
}

void Get_htnode(int n) //生成哈弗曼树编码，并输出
{
int p,m,t,i,j;
htnodetype cd[50];
for(i=0;i<n;i++)
{t=i;m=maxbit;
do
{m--;
p=ht[t].parent;
if(t==ht[p].lchild)
cd[i].bit[m]=0;
else if(t==ht[p].rchild)
cd[i].bit[m]=1;
t=p;}while(ht[p].parent!=-1);

cd[i].start=m;
}

for(i=0;i<n;i++)
{printf("htnodetype%d:",i);
for(j=cd[i].start;j<maxbit;j++)
printf("%d",cd[i].bit[j]);
printf("\n");
}
}

void main() //主函数
{
int n,i;
printf("Please input n:");
scanf("%d",&n);
Creat_ht(n);
for(i=0;i<2*n-1;i++)
printf("htnode[%d]:weight %d\tparent %d\tlchild %d\trchild %d\n",i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
Get_htnode(n);
}