哈夫曼编码器和译码器(完整代码)
# 哈夫曼编码器和译码器(完整代码)!(https://i.loli.net/2021/05/25/8qyZe3hKCnFUT7H.png)
!(https://i.loli.net/2021/05/25/VZ3UzDhgic2XEvL.png)
# 执行结果和代码奉上
!(https://i.loli.net/2021/05/25/ZjsMtCQTE79iHcX.png)
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 30 //叶子节点最大值
#define M 2*N-1 //所有结点最大值
typedef struct{
char data;
int weight;
int parent;
int Lchild;
int Rchild;
int flag;
}HTNode,HuffmanTree; //0号单元不用
//初始化哈夫曼树
void InitHuffmanTree(HuffmanTree ht,int n)
{
printf("#提示——（输入示例a b c d e）请输入对应叶子节点的字符：\n");
for(int i=1;i<=n;i++) //初始化叶子节点
{
ht.data='\0';
ht.Lchild=0;
ht.Rchild=0;
ht.weight=0;
ht.parent=0;
ht.flag=0;
getchar(); //消除空格 读取下一次输入的空格并且消除
ht.data=getchar();
}
printf("#提示——（输入示例12 40 15 8 25）请输入对应叶子节点的权重：\n");
for(i=1;i<=n;i++) //初始化叶子节点
{
scanf("%d",&ht.weight);
}
int m=2*n-1;//结点总数
for(i=n+1;i<=m;i++)//初始化非叶子节点
{
ht.Lchild=0;
ht.Rchild=0;
ht.weight=0;
ht.parent=0;
ht.flag=0; //判断是否被删除
}
}
//选择最小权值节点下标
int select(HuffmanTree ht,int n)//选择最小权值的结点下标
{
int i,temp,min;
for(i=1;i<=n;i++)//设置初始下标和权值
{
if(ht.flag==0)
{
temp=ht.weight;//初始权值
min=i;
break;
}
}
for(i=1;i<=n;i++)
{
if(ht.flag==0&&temp>ht.weight)
{
temp=ht.weight;
min=i;
}
}
ht.flag=1;
return min;
}
//构建哈夫曼树
void createHuffmanTree(HuffmanTree ht,int n)
{
for(int i=n+1;i<=(2*n-1);i++)
{
int s1=select(ht,i-1);//这里i-1
int s2=select(ht,i-1);
ht.weight = ht.weight+ht.weight;
ht.parent=i;
ht.parent=i;
ht.Lchild=s1;
ht.Rchild=s2;
}
}
//获得编码（从下往上反向）
int GetCode(int A[],HuffmanTree ht, int n)
{
int length=0,i,j,get;
char s; //定义要输入字符的空间
printf("（#提示——输入示例bbbaddeccbbb）输入要编码的字符：\n");
getchar();//清除换行符
gets(s);
int m=strlen(s);
for(i=m-1;i>=0;i--)//从后往前处理字符
{
for(j=1;j<=n;j++)
{
if(s==ht.data)
{
get = j;//获取最后一个字符的flag也就是位置
}
}
while(ht.parent)
{
if(ht.parent].Lchild==get) //判断父节点的左孩子是否等于我们找的get那个位置
{
A=0; //左孩子是0
}
else{
A=1; //右孩子是1
}
length++;
get=ht.parent;//再把父节点给get 直到父节点为0 就编码成功
}
}
return length-1;//最后会多+1，所以减去一个1
}
//打印编码
void printCode(int A[], int length)
{
int i;
for(i=length; i>=0; i--)//从后向前输出即为编码结果
{
printf("%d",A);
}
printf("\n");
}
//解码
int GetreCode(int A[], char B[], HuffmanTree ht, int length1, int n)
{
int i,length2=0,cur=2*n-1;
for(i=length1;i>=0;i--)
{
if(A)//A只可能为1或者0，提示：0是左孩子，1是右孩子
{
cur=ht.Rchild;//根结点的右孩子赋值给cur
if(ht.Rchild==0)//该结点的右孩子如果是0就说明是叶子节点，提示：二叉树只有0和2
{
B=ht.data;
length2++;
cur=2*n-1;//回到根节点
}
}
else{
cur=ht.Lchild;//和上面一样就不说了
if(ht.Lchild==0)
{
B=ht.data;
length2++;
cur=2*n-1;
}
}
}
return length2-1;
}
//解码打印
void printreCode(char B[],int length2)
{
int i;
for(i=0;i<=length2;i++)
printf("%c",B);
printf("\n");
}
//打印哈夫曼树
void printHuffmanTree(HuffmanTree ht, int n)
{
printf("结点\tweigt\tdata\tLchild\tRchild\tparent\n");
for(int i=1;i<=n;i++)
{
printf("%d\t%d\t%c\t%d\t%d\t%d\n",i,ht.weight,ht.data,ht.Lchild,ht.Rchild,ht.parent);
}
}
int main()
{
HuffmanTree ht;
int n; //n为所需的结点数
int A;//存储编码
char B;//存储输出的字符串
printf("#提示——（输入示例 5）请输入叶子节点个数:\n");
scanf("%d",&n);
InitHuffmanTree(ht,n); //初始化
createHuffmanTree(ht,n); //构建哈弗曼树
int length = GetCode(A,ht,n);
printCode(A,length);
int length2 = GetreCode(A,B,ht,length,n);
printreCode(B,length2);
printHuffmanTree(ht,n);
}
``` 能说说它的实际用图吗？ linuxcool 发表于 2021-6-3 20:30
能说说它的实际用图吗？
但凡学过数据结构的，都应该知道他们的用途 哈哈，感谢分享。 拿走发现在vs2019打开报错 这就很厉害了 搜藏，学习到哈夫曼树的时候再来实验。 不错，看起来有点难度
页:
[1]