标题: C语言经典算法之哈慢树 [打印本页]

---

作者: 苹果也疯狂    时间: 2014-5-22 09:47     标题: C语言经典算法之哈慢树

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define n 6
#define m 2*n-1
typedef struct
{ float weight;
intlchild,rchild,parent;
}codenode;
typedef codenode huffmantree[m];
typedef struct
{ char ch;
charbits[n+1];
}code;
typedef code huffmancode[n];
void inithf(huffmantree T)          //－哈夫曼树的初始化
{ int i;
for(i=0;i<m;i++)
  {T.weight=0;
   T.parent=-1;
   T.lchild=-1;
   T.rchild=-1;
  }
}
void inputhf(huffmantree T)      //－输入哈夫曼树的树据
{ int i;float k;
for(i=0;i<n;i++)
  {scanf("%f",&k);
   T.weight=k;
  }
}
void selectmin(huffmantree T,int k,int*p1,int *p2)
{ int i;float small1=10000,small2=10000;
for(i=0;i<=k;i++)
  {if(T.parent==-1)
if(T.weight<small1)
  {small2=small1;
   small1=T.weight;
   *p2=*p1;
   *p1=i;
  }
else
  if(T.weight<small2)
     { small2=T.weight;
*p2=i;
     }
  }
}
void creathftree(huffmantree T)    //－建哈夫曼树
{ int i,p1,p2;
inithf(T);
inputhf(T);
for(i=n;i<m;i++)
  {selectmin(T,i-1,&p1,&p2);
   T[p1].parent=T[p2].parent=i;
   T.lchild=p1;
   T.rchild=p2;
   T.weight=T[p1].weight+T[p2].weight;
  }
}
void creathfcode(huffmantree T, huffmancodeH)  //－哈夫曼编码表
{ int i,c,p,start;char cd[n+1];
cd[n]='\0';
for(i=0;i<n;i++)
  {H.ch=getchar();
   start=n;
   c=i;
   while((p=T[c].parent)>=0)
    {
cd[--start]=(T[p].lchild==c)?'0':'1';
c=p;
    }
   strcpy(H.bits,&cd[start]);
  }
}
void zip(huffmancode H,char *ch,char*s)    //－编码
{ int j=0;char *p[n]; unsigned int i;
for(i=0;i<strlen(ch);i++)
  {  while(ch!=H[j].ch) j++;
    p=H[j].bits;
   }
strcpy(s,p[0]);
for(i=1;i<n;i++)
   strcat(s,p);
puts(s);
}
void uzip(huffmancode H,char *s,huffmantreeT)  //－解码
{ int j=0,p;
unsigned int i;
charch[n+1];
while(i<strlen(s))
  {p=m-1;
   while(T[p].lchild!=-1)
    { if(s[  i  ]=='0')
{p=T[p].lchild;i++;}
else
{p=T[p].rchild;i++;}
    }
   ch[j]=H[p].ch;
   j++;
  }
ch[j]='\0';
puts(ch);
}
main()
{ char ch[]="abcdef", s[36];
huffmantree T;
huffmancode H;
creathftree(T);
getchar();
creathfcode(T,H);
zip(H,ch,s);
uzip(H,s,T);
}

---

欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)

Powered by Discuz! 7.0.0