huff.cpp

哈夫曼编码和译码 觉得自己有用的话就下把 我自己觉的还不错

#include <iostream.h>
#include "stdio.h"
#include "string.h"
#define MAX 99
char cha[MAX];
char hc[MAX-1][MAX];
int s1,s2; //设置全局变量，以便在方法(函数)select中返回两个变量
void menu();
typedef struct //huffman树存储结构
{
 unsigned int wei;
 int lch,rch,parent;
}hufftree;
 
 
void select(hufftree tree[],int k) //找寻parent为0,权最小的两个节点
{
 int i;
 for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;
 for (i=1;i<=k;i++)
    if (tree[i].parent==0 && tree[i].wei<tree[s1].wei) s1=i;
 for (i=1; i<=k ; i++)
    if (tree[i].parent==0 && i!=s1) break; s2=i;
 for (i=1;i<=k;i++)
    if ( tree[i].parent==0 && i!=s1 && tree[i].wei<tree[s2].wei) s2=i;
}
 
void huffman(hufftree tree[],int *w,int n) //生成huffman树
{ int m,i;
   if (n<=1) return;
   m=2*n-1;
 for (i=1;i<=n;i++)
   {
        tree[i].wei=w[i];
        tree[i].parent=0;
      tree[i].lch=0;
        tree[i].rch=0;
 }
 for (i=n+1;i<=m;i++)
   {
        tree[i].wei=0;
        tree[i].parent=0;
      tree[i].lch=0;
        tree[i].rch=0;
 }
   for (i=n+1;i<=m;i++)
   {
          select(tree, i-1);
       tree[s1].parent=i;
       tree[s2].parent=i;
       tree[i].lch=s1;
       tree[i].rch=s2;    
       tree[i].wei=tree[s1]. wei+ tree[s2].wei;
      }
}
void huffmancode(hufftree tree[],char code[],int n)
{
 int start,c,i,f;
 code[n-1]='\0';
 cout <<"Huffman编码:" <<endl;
 for(i=1;i<=n;i++)
 {
        start=n-1;
       for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)
       {  
               if(tree[f].lch==c)       
                      code[--start]='0';    
               else            
                      code[--start]='1';
        }
     strcpy(hc[i],&code[start]);
     cout <<cha[i] <<"-->" <<hc[i] <<endl;
 }
}
void tohuffmancode(int n)
{
   int i=0,j;
   char anychar[9999];
   cout <<"请输入一段字符:" <<endl;
   cin >>anychar;
   cout <<"进行Huffman编码后的结果为:" <<endl;
   for (;anychar[i]!='\0';i++)
   {
      j=0;
      for(;anychar[i]!=cha[j]&&j<=n;)
               j++;
      if (j<=n)
               cout <<hc[j];
   }
   cout <<endl;
}
 
void decode(char ch[],hufftree tree[],int n)
{
 int i,j,m;
 char b;
 m=2*n-1;
 i=m;
 cout <<"请输入你要解码的编码:" <<endl;
 cin >>b;
 cout <<"解码结果为:" <<endl;
 while(b!='#')   //遇到回车时，结束
 {
 
 if(b=='0')
        i=tree[i].lch;
 else
        i=tree[i].rch;
 if(tree[i].lch==0)
 {
        cout <<ch[i];
      j=i,i=m;
 }
 cin >>b;
 }
 if(tree[j].lch!=0)
    cout <<"发生错误!!";
}
 
void huff()
{
 int i=0,n=0;
 int *w,wei[MAX];
 char code[MAX];
 hufftree tree[MAX];
 w=wei;
 cout <<"请输入n(n为你要建树的字符个数):" <<endl;
 cin >>n;
 cout <<"请输入字符和它的权值(例如:a20):" <<endl;
 for(i=1;i<=n;i++)
 {
        cin >>cha[i] >>wei[i];
 }
 huffman(tree,w,n);   //生成huffman树
 huffmancode(tree,code,n); //编码A
 tohuffmancode(n);//编码B
 decode(cha,tree,n); //译码
 cout <<"按任意键返回";
 getchar();
 menu();
}