haffman_code.cpp

统计字符出现概率

#include "string.h" 
#include "iomanip.h"
#include "math.h"
#include"iostream.h"
#define MAX_NODE 128 
#define MAX_WEIGHT 1000 

typedef struct  
{ 
	char ch; 
	int weight; //出现次数
	float freq;	//频率
	int parent, lchild, rchild; 
}HTNode; //节点类型

typedef struct 
{ 
	HTNode arr[MAX_NODE]; 
	int length; 
} HTree; //存储整个Haffman树

typedef struct  
{
	int codes[20];
	int length;
}Coded;//每个字符的编码存放位置


// 统计字符出现的次数、频率 
void statistic_char(char *text, HTree *t)
{ 
	int i, j; 
	int text_len = strlen(text); 
	t->length = 0; 
	for (i=0; i<text_len; i++)
	{ //对每个元素
		for (j=0; j<t->length; j++) 
			if (t->arr[j].ch == text[i])
			{ 
				t->arr[j].weight ++; 
				break;
			} 
			
			
			if (j==t->length) 
			{ 
				t->arr[t->length].ch = text[i]; 
				t->arr[t->length].weight = 1; 
				t->length++; 
			} 
	} 


	//计算各个字符出现的频率
	for(int k=0;k<t->length;k++)
	{
		t->arr[k].freq=(float)(t->arr[k].weight)/text_len;
	
	}


} //statistic_char



//创建haffman树（数组存储）
void Create_htree(HTree *t) 
{ 
	int i; 
	int length_node = t->length * 2 - 1; 
	int min1, min2; // 权最小的两个结点  
	int min1_i, min2_i; // 权最小结点对应的编号  
	
	for (i=0; i<t->length; i++)
	{ 
		t->arr[i].parent = -1; 
		t->arr[i].rchild = -1; 
		t->arr[i].lchild = -1; 
	} 
	
	while (t->length<length_node) 
	{ 
		min1 = min2 = MAX_WEIGHT; 
		for (i=0; i<t->length; i++) 
		{ // 对每一个结点  
			if (t->arr[i].parent == -1 // 结点没有被合并  
				&& t->arr[i].weight < min2)
			{ // 结点的权比次最小权小  
				if (t->arr[i].weight < min1) 
				{ // 比最小权的结点还小  
					min2_i = min1_i; min2 = min1; 
					min1_i = i; min1 = t->arr[i].weight; 
				} 
				else 
				{ 
					min2_i = i; min2 = t->arr[i].weight; 
				} 
			} 
		}
		
		t->arr[t->length].weight = min1 + min2; 
		t->arr[t->length].parent = -1; 
		t->arr[t->length].lchild = min1_i; 
		t->arr[t->length].rchild = min2_i; 
		t->arr[min1_i].parent = t->length; 
		t->arr[min2_i].parent = t->length; 
		t->arr[t->length].ch = ' '; 
		t->length++; 
	}
} 


// 对哈夫曼树进行编码 （遍历）
void Coding(HTree *t,  Coded *pcode,float *avg_len) 
{ 
	int len=(t->length+1)/2;
	int parent=0;
	for(int i=0;i<len;i++)
	{     
		int parent=t->arr[i].parent;
		int curent=i;
		int code_len=0;
		while(parent!=-1)
		{
			if((t->arr[parent]).lchild==curent)
				pcode[i].codes[code_len++]=0;
			else
				pcode[i].codes[code_len++]=1;
			curent=parent;
			parent=t->arr[parent].parent;
			
		}
		pcode[i].length=code_len;
		cout<<setw(3)<<t->arr[i].ch;
		cout<<setw(5)<<t->arr[i].weight;
		cout<<setw(7)<<setprecision(2)<<t->arr[i].freq;
		cout<<setw(6)<<code_len<<"\t  ";
		for(int j=pcode[i].length-1;j>=0;j--)
		{
			cout<<pcode[i].codes[j];
		}
		cout<<endl;
	}
     
	for(int k=0;k<len;k++)
	{
		*avg_len+=(float)(t->arr[k].freq)*(pcode[k].length);
	}

	cout<<"哈夫曼编码平均长度为：  "<<setprecision(3)<<*avg_len<<endl;
		
} 

void main() 
{ 
	HTree t; 
	Coded code[100];
	char text[200]; 
	float haf_avg_len=0;
	double equal_len=0;
	cout<<"请输入需要编码的字符串:"<<endl; 
	cin>>text; 
	statistic_char(text, &t); 
	Create_htree(&t); 
	cout<<"编码对应关系为:"<<endl;
	cout<<"字符  次数 频率 编码长度  编 码  "<<endl;
	Coding(&t,  code,&haf_avg_len); 
	
	//等长编码平均长度
	equal_len=(double)log10((t.length+1)/2)/log10(2);
    cout<<"等长编码平均长度为： "<<setprecision(3)<<equal_len<<endl;

	if(haf_avg_len<equal_len)
    {
        cout<<("可见HUFFMAN编码的平均长度要比固定等长编码的平均长度短,故HUFFMAN更优越\n");
    }
    else
    {
        cout<<("huffman编码不行，可能出问题了。\n");;
    }
	
}