huffman.cpp

huffman树 我自己做的 比较简单 希望大家给予完善

#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include <string>
#include "malloc.h"
#include <iostream.h>
typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子
typedef char Elemtype;
typedef struct TNode{
    Elemtype letter; 
    int weight;
    int parent;
    Which sigh;
    char *code;
}HTNode,*HuffmanTree;
//设定全局变量
int n;
char cha[100];
char codea[100];


void InitTreeNode(HuffmanTree &HT){//初始前N个结点,后M-N个结点置空
    int i;int w;char c;
	char ch[100];
	int code[100];
		for(i=0;i<100;i++)
		{
			code[i]=0;
			ch[100]='#';
		}
    int m=2*n-1;
    HuffmanTree p;
    HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
    cout<<"input database letter and weight"<<endl;
    p=HT;
    getchar();
    for (i=1;i<=n;i++){
        scanf("%c%d",&c,&w);
        p->code='\0';
        p->letter=c;
        p->parent=0;
        p->sigh=none;
        p->weight=w;
		code[i]=w;
		codea[i]=code[i];
		ch[i]=c;
        p++;
        getchar();
    }
    for (;i<=m;i++,p++){
        p->code='\0';
        p->letter=' ';
        p->parent=0;
        p->sigh=none;
        p->weight=0;
		code[i]=0;
		codea[i]=0;
		ch[i]='\0';
    }


 
	
//复制到全局变量中
for (i=0;i<100;i++)
{
	 
	 cha[i]=ch[i];
	 
	 
}



}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2){//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的结点序号
     if (HT[i].parent==0&&HT[i].weight<min1){ 
         *s1=i;
         min1=HT[i].weight;
}
}
     min2=INT_MAX;
      for(i=0;i<=end;i++){//找次小结点的序号
          if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
              *s2=i;
              min2=HT[i].weight;
          }
      }
}
void HuffmanTreeCreat(HuffmanTree &HT){//建立HUFFMAN树
    int i;
	int m=2*n-1;
    int s1,s2;
    for(i=n;i<m;i++){
        Select(HT,i-1,&s1,&s2);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[s1].sigh=right_child;
        HT[s2].sigh=left_child;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
}

void HuffmanTreeCode(HuffmanTree HT){//HUFFMAN译码
int i;
int j;
float avrh=0;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
     p=i;
     s=n-1;
	 j=-1;
    while (HT[p].parent!=0){//从结点回溯,左孩子为0,右孩子为1
        if (HT[p].sigh==left_child)
		{
			  j=j+1;
			  temp[--s]='0';
			  avrh=avrh+1;
		}
        else if (HT[p].sigh==right_child)
		{     
			  j=j+1;
			  temp[--s]='1';
			  avrh=avrh+1;
		}
		
		    
        p=HT[p].parent;
    }
    HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间
    strcpy(HT[i].code,temp+s);
    
	}

  
			  
//结果输出
for (i=0;i<n;i++)
	
{   
cout<<cha[i+1]<<"的huffman编码为:"<<HT[i].code<<endl;
	
}
   cout<<"huffman编码的平均长度为:"<<avrh/n<<endl; 
}



void main()
{
	
    HTNode hnode;
    HuffmanTree huff;
    huff=&hnode;
    cout<<"input the letter for coding number"<<endl;
    scanf("%d",&n);
    InitTreeNode(huff);
    HuffmanTreeCreat(huff);
    HuffmanTreeCode(huff);
	
} 


/********************************结果示例*********************************/
/*
input the letter for coding number
5
input database letter and weight
a1
s2
d3
f4
g5
a的huffman编码为:101
s的huffman编码为:100
d的huffman编码为:11
f的huffman编码为:01
g的huffman编码为:00
huffman编码的平均长度为:2.4
Press any key to continue
*/