哈夫曼编码.cpp

前一阵出去玩了

#include "malloc.h" 
#include "string.h"
#include "stdio.h" 
#define MAX 1.0
typedef struct{ 
double weight; 
int parent,lchild,rchild;
bool use;
}HTNode,*Huffmantree; 
void Select(Huffmantree HT,int k,int *s1,int *s2) 
{
double min1= MAX;
int i,a,b; 
for (i=1;i<=k;i++) 
{
if (min1>=HT[i].weight&&HT[i].use==true)
{
a=i; 
min1=HT[i].weight; 
} 
} 
   *s1=a; 
double min2=MAX; 
for(i=1;i<=k;i++) 
{
if ((*s1!=i)&&min2>HT[i].weight&&HT[i].use==true) 
{
b=i; 
min2=HT[i].weight; 
} 
} 
*s2=b; 
printf("s1:=%d,s2=%d\n",*s1,*s2); 
} 
void HuffmanCoding(Huffmantree HT,double *w,int n,int m) 
{
char **HC; 
Huffmantree p; 
char *cd; 
int i,i1,start,c,s1,s2,f; 
for(p=HT,p++,i=1;i<=n;++i,++p,++w) 
{
p->weight=*w; 
p->parent=0; 
p->lchild=0; 
p->rchild=0;
p->use=true;
} 
for(;i<=m;++i,++p) 
{
p->weight=0.0; 
p->parent=0; 
p->lchild=0; 
p->rchild=0; 
p->use=true;
} 
for(i=n+1;i<=m;++i) 
{
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[s1].use=false;HT[s2].use=false;
HT[i].lchild=s1;HT[i].rchild=s2; 
HT[i].weight=HT[s1].weight+HT[s2].weight; 
} 
HC=(char **)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]); 
} 
for(i1=1;i1<=n;i1++) 
printf("第%d个符号的编码为：%s\n",i1,HC[i1]); 
} 
int main() 
{

int i0,n,m; 
char a;
double s[256],fault=0.;
Huffmantree HT;
int check=1;
do
{
printf("输入哈夫曼编码的个数:\n"); 
scanf("%d",&n);
if(n>256)
printf("个数太多，重新输入：\n");
else
check=0;
}while(check);
check=1;
do
{
printf("输入这些使用频度:\n");
for(i0=0;i0<n;i0++)
{
scanf("%lf",&s[i0]);
getchar();
}
for(i0=0;i0<n;i0++)
{
fault+=s[i0];
}
if(fault>0.9&&fault<=1.0)
check=0;
else
printf("使用频度综合不为1，重新输一次:\n");
}while(check);
m=2*n-1; 
HT=(Huffmantree)malloc((m+1)*sizeof(HTNode)); 
HuffmanCoding(HT,s,n,m);
printf("输入任何字母退出:\n");
scanf("%c",&a);

return 0;
}