huffman.cpp

利用哈夫曼编码的原理对字符进行处理,最后输出的是对输入的字符的0和1的编码

#include<iostream>
#define MaxSize 50

using namespace std;

typedef struct
{//huffman树的 结点类型
    char data;   //结点值 
    int weight;  //权重 
    int parent;  //父结点 
    int left; //左结点 
    int right; //右结点 
}huffnode;

typedef struct
{ //huffman编码的结构类型
    char cd[MaxSize];//编码 
    int start;
}huffcode;

void creahuffman(huffnode ht[],int n)
{// 构造赫夫曼树
    int i,k,l,r,m1,m2;
    for(i=0; i<2*n-1; i++)
       ht[i].parent=ht[i].left=ht[i].right=0;
    for(i=n;i <2*n-1;i++)
    {
       m1=m2=32767; 
       l=r=0;//l,r为最小权重的两个结点位置
       for(k=0;k <i-1;k++)
          if(ht[k].parent==0)
          if(ht[k].weight <m1)
          {
             m2=m1;
             r=l;
             m1=ht[k].weight;
             l=k;
          }
          else if(ht[k].weight <m2)
          {
             m2=ht[k].weight;
             r=k;
          }
       ht[l].parent=i;ht[r].parent=i;
       ht[i].weight=ht[l].weight+ht[r].weight;
       ht[i].left=l;ht[i].right=r;
    }
}

void creahfcode(huffnode ht[],huffcode hcd[],int n)  
{//求赫夫曼编码
    int i,f,c;
    huffcode d;
    for(i=0;i <n;i++)
    {
       d.start=n+1;
       c=i;
       f=ht[i].parent;
       while(f!=0)
       {
          if(ht[f].left==c)
             d.cd[--d.start]='0';
          else
             d.cd[--d.start]='1';
          c=f;
          f=ht[f].parent;
       }
       hcd[i]=d;
    }
}

void disphuffman(huffnode ht[],huffcode hcd[],int n) 
{//输出赫夫曼编码 
    int i,k;
    cout<<"輸出哈夫曼編碼:"<<endl;
    for(i=0;i <n;i++)
    {
       cout<<"第一个数值"<<ht[i].data<<"的哈夫曼编码为:";
       for(k=hcd[i].start; k<=n; k++)
          cout<<hcd[i].cd[k];
       cout<<endl;
    }
}

int main()
{
    int n;
    huffnode ht[2*MaxSize];
    huffcode hcd[MaxSize];
    cout<<"输入数值的个数:";
    cin>>n;
    while (n<=MaxSize)
    {
       for(int i=0; i<n; i++)
       {
               cout<<"第"<<(i+1)<<"个数值的值和权分别为:";
               cin>>ht[i].data>>ht[i].weight;
       }
       break;
    }

//    ht[0].data='a'; 
//    ht[1].data='b';
//    ht[2].data='c'; 
//    ht[3].data='d';
//    ht[4].data='e'; 
//    ht[5].data='f';
//    ht[0].weight=10; 
//    ht[1].weight=2;
//    ht[2].weight=6; 
//    ht[3].weight=4;
//    ht[4].weight=3; 
//    ht[5].weight=1;

    creahuffman(ht,n);
    creahfcode(ht,hcd,n);
    disphuffman(ht,hcd,n);

    system("pause");
    return 0;
}