本文共 3952 字，大约阅读时间需要 13 分钟。
//哈夫曼编码
#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
typedef struct{
charc;
intweight;
intparent;
intlchild,rchild;
char*HC;
}HTNode;
//选取两棵带权最小子树的函数
int Select_Tree(HTNode *H,int x)
{
inti,a=1000000000,b,c;
for(i=1;i<=x;i++)
{
if(H[i].parent==0){b=H[i].weight;
if(a>b)
a=b,c=i;
}
}
H[c].parent=-1;
returnc;
}
//创建哈夫曼树
int Create_HuffmanTree(HTNode *H,intn,int m)
{
inti,s1,s2;
for(i=1;i<=n;i++)
scanf("%d",&H[i].weight);
for(i=1;i<=m;i++)
H[i].parent=H[i].lchild=H[i].rchild=0;
for(i=n+1;i<=m;i++)
{s1=Select_Tree(H,i-1);
s2=Select_Tree(H,i-1);
H[s1].parent=H[s2].parent=i;
H[i].lchild=s1;
H[i].rchild=s2;
H[i].weight=H[s1].weight+H[s2].weight;
}
printf("哈夫曼树创建成功！！！\n");
returnOK;
}
//输出哈夫曼树表格
int print_HuffmanTree(HTNode *H)
{
inti;
printf("哈夫曼树的表格数据为:\n");
printf(" num c weight parent lchild rchild\n");
for(i=1;i<=H[0].weight;i++)
printf(" %d %c %d %d %d %d\n",i,H[i].c,H[i].weight,H[i].parent,H[i].lchild,H[i].rchild);
for(i=H[0].weight+1;i<=H[0].parent;i++)
printf(" %d - %d %d %d %d\n",i,H[i].weight,H[i].parent,H[i].lchild,H[i].rchild);
returnOK;
}
//输出所有字符的哈夫曼编码
int print_Huffmannum(HTNode *H)
{
char*q;
q=(char*)malloc(H[0].weight*sizeof(char));
q[H[0].weight-1]='\0';
inti,c,f;
intstart;
for(i=1;i<=H[0].weight;i++)
{start=H[0].weight-1;
f=i;
while(H[f].parent!=0)
{
c=f;
f=H[f].parent;
if(H[f].lchild==c)q[--start]='0';
elseq[--start]='1';
}
H[i].HC=(char*)malloc((H[0].weight-start)*sizeof(char));
strcpy(H[i].HC,&q[start]);
}
for(i=1;i<=H[0].weight;i++)
{printf("%c的二进制前缀编码为: ",H[i].c);
puts(H[i].HC);
}
returnOK;
}
//输入字符串求哈夫曼编码
int return_HFMnum(HTNode *H)
{
print_Huffmannum(H);
printf("请输入要求哈夫曼编码的字符串:\n");
chara[10000];
gets(a);
intlen=strlen(a);
char*q;
q=(char*)malloc(len*sizeof(char));
strcpy(q,a);
inti,j,count=0;
{
for(i=0;i<len;i++)for(j=1;j<=H[0].weight;j++)
if(q[i]==H[j].c){count++;}}
if(count==len)
{
printf("这行字符串的编码为:\n");
for(i=0;i<len;i++)
for(j=1;j<=H[0].weight;j++)
if(q[i]==H[j].c)printf("%s",H[j].HC);}
else
printf("翻译失败！！！有字符不对应！！！\n");
returnOK;
}
//输入编码翻译字符
int Tranlate_HMnum(HTNode *H)
{
print_Huffmannum(H);
printf("请输入一串哈夫曼编码：\n");
chara[10000];
gets(a);
intlen=strlen(a);
intlen1;
char*q;
q=(char*)malloc(len*sizeof(char));
strcpy(q,a);
inti,j,k=0,m=0,n=0,count=0;
while(n!=len)
{
for(i=1;i<=H[0].weight;i++)
{len1=strlen(H[i].HC);count++;if(count==H[0].weight+1){printf("翻译失败！！！\n");returnOK;}
{
for(j=0;j<len1;j++)if(H[i].HC[j]==q[k]){k++;m++;if(m==len1) {n=n+m;m=0;k=n;count=0;}}
else{k=n;m=0;break;}}
if(n==len)break;
}
}
printf("翻译成功！！！\n翻译的结果为:\n");
k=m=n=0;
while(n!=len)
{
for(i=1;i<=H[0].weight;i++)
{len1=strlen(H[i].HC);
{
for(j=0;j<len1;j++)if(H[i].HC[j]==q[k]){k++;m++;if(m==len1) {n=n+m;m=0;k=n;printf("%c",H[i].c);}}
else{k=n;m=0;break;}}
if(n==len)break;
}}
returnOK;
}
//销毁哈夫曼树
int Destroy_HFMTree(HTNode *H)
{
free(H);
printf("哈夫曼树已销毁！！！要继续操作必须按“”重建\n");
returnOK;
}
//主函数
void main()
{
HTNode *H;
intn,m;
intflag=1,select;
printf("====================菜单=====================\n");
printf("= 1.创建哈夫曼树 =\n");
printf("= 2.输出哈夫曼树表格 =\n");
printf("= 3.输出所有字符的哈夫曼编码 =\n");
printf("= 4.输入字符串求哈夫曼编码 =\n");
printf("= 5.输入编码翻译字符 =\n");
printf("= 6.销毁哈夫曼树 =\n");
printf("= 7.退出操作 =\n");
printf("================支持乱序选择=================\n");
while(flag)
{
printf("\n请选择菜单中的操作选项(必须先选择“”建立哈夫曼树！建立之后再选择其他选项操作):");
scanf("%d",&select);
switch(select)
{
case1:
getchar();
printf("请输入要编码的字符(输入一个字符串)：\n");
chara[10000];
gets(a);
n=strlen(a);
m=2*n-1;
H=(HTNode*)malloc((m+1)*sizeof(HTNode));
H[0].weight=n;
H[0].parent=m;
H[0].lchild=H[0].rchild=10000;
inti,j;
for(i=1,j=0;i<=n;i++,j++)
H[i].c=a[j];
printf("请输入以上每个字符的权(输入整数),一共输入%d个:\n",H[0].weight);
Create_HuffmanTree(H,n,m);break;
case2:
print_HuffmanTree(H);break;
case3:
print_Huffmannum(H);break;
case4:
getchar();
return_HFMnum(H);break;
case5:
getchar();
Tranlate_HMnum(H);break;
case6:
Destroy_HFMTree(H);break;
case7:
flag=0;break;
default:
printf("您输入的数据有误！！！请重新输入！！！\n");
}
}
}
转载地址：http://ksdaf.baihongyu.com/