本帖最后由 芯圣电子官方QQ 于 2023-7-20 10:37 编辑
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char data;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT,int m,int &s1,int &s2)//选择两个权值较小的结点,并返回序号
{
int i,j,min1,min2;
min1=min2=1000;
for(i=1;i<=m;i++)
if(HT[i].parent==0&&HT[i].weight<min1)
{
min1=HT[i].weight;
s1=i;
}
for(j=1;j<=m&&j!=s1;j++)
if(HT[i].parent==0&&HT[i].weight<min2)
{
min2=HT[j].weight;
s2=j;
}
}
void CreateHuffmanTree(HuffmanTree &HT,int n)//建立哈夫曼树
{
if(n<=1) return;
HT=(HuffmanTree)malloc(sizeof(HTNode)2n);
int i,j,s1,s2;
char ch='a';
for(i=1;i<=(2n-1);++i)
{
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(j=1;j<=n;++j,ch++)
{
if(j==1)
{
HT[1].data=' ';
scanf("%d",&HT[j].weight);
}
else
{
HT[j].data=ch;
scanf("%d",&HT[j].weight);
}
}
for(i=n+1;i<=(2n-1);++i)
{
Select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[i].lchild=s1;
HT[i].rchild=s2;
}
}
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)//求哈夫曼编码
{
HC=new char*[n+1];
char *cd;
cd=(char *)malloc(sizeof(char)*n);
int i,start,c,f;
for(i=1;i<=n;++i)
{
start=n-1;
c=i;
f=HT[i].parent;
while(f!=0)
{
--start;
if(HT[f].lchild==c) cd[start]='0';//回溯时走左分支为0，右分支为1
else cd[start]='1';
c=f;
f=HT[f].parent;
}
HC[i]=(char)malloc(sizeof(char)(n-start));
strcpy(HC[i],&cd[start]);
}
delete(cd);
}
void InterpretCode(HuffmanCode HC,char *str)//译码
{
int i;
for(i=0;i<strlen(str);i++)
{
if(str[i]==' ') printf("%s",HC[1]);
else{
if(str[i]>='A'&&str[i]<='Z') str[i]=str[i]+32;
if(str[i]>='a'&&str[i]<='z') printf("%s",HC[str[i]-95]);
}
}
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
CreateHuffmanTree(HT,27);
printf("请输入报文:");
CreateHuffmanCode(HT,HC,27);
char s[100];
gets(s);
InterpretCode(HC,s);
return 0;
}
| 
楼主
标题置顶
标题高亮
