数据结构——赫夫曼编码

秒速五厘米 2022-08-03 00:24 208阅读 0赞

效果如下：

![Center][]

源程序如下：

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<string.h>  
typedef struct  
\{  
int weight;  
int parent,lchild,rchild;  
\}HTNode,\*HuffmanTree; //动态分配数组存储赫夫曼树  
typedef char \*\*HuffmanCode;//动态分配数组存储赫夫曼编码表  
void Select(HuffmanTree HT,int n,int &s1,int &s2)  
\{  
int i;  
s1=s2=0;  
for(i=1;i<=n;i++)  
\{  
if(HT\[i\].weight<HT\[s2\].weight&&HT\[i\].parent==0&&s2!=0)  
\{  
if(HT\[i\].weight<HT\[s1\].weight)  
\{  
s2=s1;  
s1=i;  
\}  
else  
s2=i;  
\}  
if((s1==0||s2==0)&&HT\[i\].parent==0)  
\{  
if(s1==0)  
s1=i;  
else if(s2==0)  
\{  
if(HT\[i\].weight<HT\[s1\].weight)  
\{  
s2=s1;s1=i;  
\}  
else  
s2=i;  
\}  
\}  
\}  
if(s1>s2)  
\{  
i=s1;  
s1=s2;  
s2=i;  
\}  
\}  
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int \*w,int n)  
\{  
int i,m,start,c,f;  
int s1=0,s2=0;  
char \*cd;  
HuffmanTree p;  
if(n<=1)  
return;  
m=2\*n-1;  
HT=(HuffmanTree)malloc((m+1)\*sizeof(HTNode));//0号单元未用  
for(p=HT+1,i=1;i<=n;++i,++p,++w)  
\{  
 p->weight=\*w;  
 p->parent=0;  
 p->lchild=0;  
 p->rchild=0;  
\}  
for(;i<=m;++i,++p)  
\{  
 p->weight=0;  
 p->parent=0;  
 p->lchild=0;  
 p->rchild=0;  
\}  
for(i=n+1;i<=m;++i)//建赫夫曼树  
\{  
//----在HT\[1...i-1\]选择parent为0且weight最小的两个接点，其序号分别为s1,s2----  
 Select(HT,i-1,s1,s2);  
 HT\[s1\].parent=i;  
 HT\[s2\].parent=i;  
 HT\[i\].lchild=s1;  
 HT\[i\].rchild=s2;  
 HT\[i\].weight=HT\[s1\].weight+HT\[s2\].weight;  
\}  
//----从叶子到根逆向求每个字符的赫夫曼编码----  
HC=(HuffmanCode)malloc((n+1)\*sizeof(char\*));  
cd=(char\*)malloc(n\*sizeof(char));  
cd\[n-1\]='\\0'; //编码结束符  
for(i=1;i<=n;++i)  
\{  
 start=n-1; //编码结束符位置  
 for(c=i,f=HT\[i\].parent;f!=0;c=f,f=HT\[f\].parent)  
 if(HT\[f\].lchild==c)  
cd\[--start\]='0';  
 else  
cd\[--start\]='1';  
 HC\[i\]=(char\*)malloc((n-start)\*sizeof(char));  
 strcpy(HC\[i\],&cd\[start\]);  
\}  
free(cd);  
\}  
void main()  
\{  
int \*weigh;  
int i,n;  
HuffmanTree HT;  
HuffmanCode HC;  
printf("............赫夫曼编码...........\\n\\n");  
printf("请输入结点个数：");  
scanf("%d",&n);  
weigh=(int \*)malloc(n\*sizeof(int));  
printf("请输入%d个权值：",n);  
for(i=0;i<n;i++)  
\{  
scanf("%d",weigh+i);  
\}  
HuffmanCoding(HT,HC,weigh,n);  
for(i=1;i<=2\*n-1;i++)  
\{  
printf("%3d %3d %3d %3d\\n",HT\[i\].weight,HT\[i\].parent,HT\[i\].lchild,HT\[i\].rchild);  
\}  
for(i=1;i<=n;i++)  
\{  
printf("序号%2d:",i);  
 printf("权值%3d:",HT\[i\].weight);  
 printf("编码%s\\n",HC\[i\]);  
\}  
\}

[Center]: /images/20220731/9db707a9e1ee440988ab53503f1fab46.png