huffman.txt

哈夫曼编码的程序 是VC++编的 只是用TXT保存了

#include<iostream.h>
#include<math.h>
#include<string.h>
#define maxnode 100  //定义最大节点个数为100
#define maxh 15      //定义哈夫曼树的最大深度为15

struct HuffmanTree{
      int weight; //权重
      int parent; //父节点序号
      int lchild; //左孩子
      int rchild; //右孩子
      HuffmanTree *next;
};

/*排序*/
int *sort(HuffmanTree *HT,int n) //n是节点个数
{
    int *s,*ss;
    s=new int[n];
    ss=new int[n];
    for(int i=0;i<n;i++)
    {s[i]=i+1;ss[i]=HT[i].weight;}
    for(i=0;i<n;i++)
    {
        if(ss[i]>ss[i+1])
        {
           int t1=ss[i];ss[i]=ss[i+1];ss[i+1]=t1;
           int t2=s[i];s[i]=s[i+1];s[i+1]=t2;}
    }
    return s;
}

/*采用递归函数计算前缀编码*/
char *getcode(HuffmanTree *HT,int h,int i,int k)//h为哈夫曼树的深度,i为节点序号
{
    char *code;
    code=new char[h];
    int j=HT[i].parent;//第i个节点的父节点的序号
    if(HT[j].lchild==i+1) //若是左孩子
       code[++k]='0';     //则码元是0
    else code[++k]='1';   //若是右孩子，则码元是1
    if(j==0)
        return code;
    else
    { 
        i=j;
        getcode(HT,h,i,k);
     }
	return  code;
}

void main(void)
{
    int w[100];
    HuffmanTree *HT=NULL; /*哈夫曼树的头节点*/
    cout<<"请输入各子树的权重(以-1结束):";
    cin>>w[0];
    int i=0;
    while(w[i]!=-1)
    {
        HuffmanTree *T;
		T=new HuffmanTree;
        T->weight=w[i];
        T->parent=T->lchild=T->rchild=0;
        T->next=NULL;
         i++;
        if(HT==NULL)
           HT=T;
        else
        {
            HuffmanTree *p;
            while(p->next!=NULL)
               p=p->next;
            p->next=T;//将T链接在HT的尾部
         }
         cin>>w[i];
    }    /*将i个节点存入到链表HT中*/
    
	int n=i;    //记节点总数为n,其左右孩子均为空

    //共需要2n-1个存储单元
    /*先对n个节点按升序进行排序，将序号存入数组s[n]中*/
    int *s;
    s=new int[n];
    s=sort(HT,n);
    for(i=n;i<2*n-1;i++)
    {
        HuffmanTree *node=new HuffmanTree;/*用于存储合并两棵权重最小的子树生成的节点*/
        node->weight=HT[s[i-n]].weight+HT[s[i-n+1]].weight;
        node->parent=0;
        node->lchild=s[i-n];
        node->rchild=s[i-n+1];
        HT[s[i-n]].parent=i;
        HT[s[i-n+1]].parent=i;
        HT[i].next=node;
     }
     cout<<"哈夫曼树的结构为:\n";
     cout<<"   weight     parent      lchild      rchild  \n";
     for(i=0;i<2*n-1;i++)
     {
         cout<<'\t'<<i+1<<'\t'<<HT[i].weight<<'\t'<<HT[i].parent<<'\t';
         cout<<'\t'<<HT[i].lchild<<'\t'<<HT[i].rchild<<'\n';
     }
     cout<<"*   *    *    *   *   *   *   *   *   *   *   *   *   *   *   *   *   *";
     cout<<"哈夫曼编码为：\n";
	 double n1=double(n);
	 double l1=log10(n1);
	 double l2=log10(2.0);
     int h=int (double(l1)/l2+1);    //哈夫曼树的深度

     char (*code)[maxnode];
     code=(char(*)[maxnode])new char[maxh];  //n个码字,每个码字的最大长度为h

     /*逐个求每个节点的码字*/
     for(i=0;i<n;i++)
     {
         int k=0;
         strcpy(code[i],getcode(HT,h,i,k));
      }
      for(i=0;i,n;i++)
      {
          cout<<"节点"<<i+1<<":"<<'\t';
          for(int j=h-1;j>=0;j--)
             code[i][j];
          cout<<'\n';
       }
}