huffman.cpp

超级经典的

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct{
	double weight;
	int parent,lchild,rchild;
}HTnode,*HTree;
void InitData();
void select(HTree HT, int len, int* index1, int* index2);
int create(HTree* HT, double* weight, int num);
void huffmanCode(HTree HT, char** HC,int num);
void huffmanCoding();//编码过程
void dhuffmanCoding();//译码过程
void show();
double data[1000][4]={0};
int length=0,l=0,n=0;
char* HC[1000];  //定义指向编码串的指针数组
int main()
{
	int i=0;
	double qdata[1000];
	memset(HC,0,1000);
	memset(qdata,0,1000);
	InitData();
	for(i=0;i<n;i++)
		qdata[i]=data[i][3];	
	HTree HT;
	//创建Huffman树
	create(&HT,qdata,n);
	//编码
	huffmanCode(HT,HC,n);
	//打印编码串
	for(i = 0; i < n;++i)
		printf("%f-%f-%f: %s\n",data[i][1],data[i][2],data[i][3],HC[i]);
	show();
	printf("共有：%d条记录及%d个权值\n",length,n);
	printf("正在编码中....\n");
	printf("正在将编码数据写入code.txt文件中....\n");
	huffmanCoding();
	printf("编码完成......\n");
	printf("正在译码中....\n");
	printf("正在将译码数据写入data.txt文件中....\n");
	dhuffmanCoding();
	printf("译码完成......\n");
	system("pause");
	return 0;
}
void InitData()
{
	int i,flag=0;
	double temp=0;
	FILE* p=fopen("hfm.txt","r");
	while(1)
	{
		fscanf(p,"%lf",&temp);
		for(i=0;i<n;i++)
		{
			if(temp==data[i][1])
			{
				flag=1;
				data[i][2]=data[i][2]+1;
				length++;
				for(i=0;i<n;i++)
					data[i][3]=data[i][2]/length;
				break;
			}
		}
		if(flag==0)
		{
			data[n][1]=temp;
			data[n][2]=data[n][2]+1;
			length++;
			n++;
			for(i=0;i<n;i++)
				data[i][3]=data[i][2]/length;	
		}
		if(feof(p))break;
		flag=0;
	}
	fclose(p);
}
void select(HTree HT, int len, int* index1, int* index2){
	int i;
	//初始化*index1
	for(i = 0; i < len; i++)
		if(HT[i].parent == 0){
			*index1 = i;
			break;
		}
		//求最小值*index1
		for(i = 0; i < len; i++)
			if(HT[i].parent == 0)
				if(HT[i].weight < HT[*index1].weight)
					*index1 = i;
				//初始化*index2
				for(i = 0; i < len; i++)
					if(HT[i].parent == 0 && i!= *index1){
						*index2 = i;
						break;
					}
					//求次小值*index2:
					for(i = 0; i < len; ++i)
						if(i != *index1)
							if(HT[i].parent == 0)
								if(HT[i].weight < HT[*index2].weight)
									*index2 = i;
								
}
//创建Huffman树：
int create(HTree* HT, double* weight, int num){
	int i, nodeNum;
	int min1,min2;
	double* w = weight;
	HTree p;
	if(num <= 1)
		return 1;
	nodeNum = 2*num - 1;
	//分配所有结点的空间
	(*HT) = (HTree)malloc(sizeof(HTnode)*nodeNum);
	if(!(*HT))
		return -1;
	//对叶子结点初始化
	for(i = 0, p = *HT; i < num; ++i, ++p,++w){
		p->weight = *w;
		p->lchild = p->rchild = p->parent = 0;
	}
	//对剩余的非叶子结点初始化
	for( ; i < nodeNum; ++i,++p)
		p->weight = p->lchild = p->rchild =p->parent = 0;
	//链接各个结点形成Huffman树
	for(i = num; i < nodeNum; ++i){
		select(*HT, i ,&min1,&min2);
		(*HT)[min1].parent = i;
		(*HT)[min2].parent = i;
		(*HT)[i].weight = (*HT)[min1].weight + (*HT)[min2].weight;
		//最小值为其左孩子，次小值为其右孩子，也可以按照反顺序，那么得到的编码有些不同
		(*HT)[i].lchild = min1;
		(*HT)[i].rchild = min2;
	}
	return 1;
}
//编码函数：在已建立的Huffman树的基础之上进行编码（从字符到对应的01串的过程）
void huffmanCode(HTree HT, char** HC,int num){
	int i,temp,start,par;
	char* workSpace;
	//申请求编码要用的工作空间，该空间最大为2*num-1-num+1 = num个字节
	workSpace = (char*)malloc(num*sizeof(char));
	//不需要执行下面的语句，因为HC一般从主函数传入
	//HC = (char**)malloc(num*sizeof(char*));
	//逆向求字符编码，首先将工作空间用字符串结束标志初始化：
	workSpace[num-1] = '\0';
	//双重循环依次对各个字符求编码 
	for(i = 0; i < num ; ++i){
		start = num -1;
		//循环结束标志是结点的双亲结点为0，也即到达了根结点了
		for(temp = i,par = HT[i].parent;     par != 0;      temp = par,par = HT[par].parent)
			if(HT[par].lchild == temp)
				workSpace[--start] = '0';
			else
				workSpace[--start] = '1';
			//为当前求得的字符编码分配适当大小的空间
			*(HC+i) = (char*)malloc((num - start)*sizeof(char));
			//从工作空间拷贝编码串到分配好的区域中
			strcpy( *(HC+i) , &workSpace[start]);
	}
	//释放工作空间
	free(workSpace);
}
void huffmanCoding()
{
	int i=0;
	double temp=0;
	FILE* p=fopen("hfm.txt","r");
	FILE* fp=fopen("code.txt","w");
	while(1)
	{
		fscanf(p,"%lf",&temp);
		for(i=0;i<n;i++)
		{
			if(data[i][1]==temp)
			{
				fprintf(fp,"%s\n",HC[i]);
				break;
			}
		}
		if(feof(p))break;
	}
	fclose(p);
	fclose(fp);
}
void dhuffmanCoding()
{
	int i=0;
	long int m=0,k=0;
	char temp[20];	
	FILE* p=fopen("code.txt","r");
	FILE* fp=fopen("data.txt","w");
	while(1)
	{
		memset(temp,0,20);
		fgets(temp,20,p);
		if(feof(p))break;
		m=atoi(temp);
		for(i=0;i<n;i++)
		{
			k=atoi(HC[i]);
			if(m==k)
			{
				fprintf(fp,"%f\n",data[i][1]);
				break;
			}
		}
	}
	fclose(p);
	fclose(fp);
}
void show()
{
	printf("\n\t\t-************************************-\n");
	printf("\t\t-* 此程序演示哈夫曼编码以及译码过程 *-\n");
	printf("\t\t-* www.coolboys.cn  Design by cooky *-\n");
	printf("\t\t-************************************-\n");
}