huffman_main.cpp

哈夫曼编码函数 C语言

#ifndef NULL
	#define NULL 0
#endif

#include "HuffNode.h"
#include "Queue_c.h"
#include "stdio.h"
#include "malloc.h"

struct Queue * code_queue=(struct Queue *)
							malloc(sizeof(struct Queue));
struct HuffNode * head=(struct HuffNode *)
							malloc(sizeof(struct HuffNode));

int FindCode(unsigned char code){
	for(int i=0;i<=code_queue->QueueLen;i++)
		 if(code_queue->Buffer[i]->data==code)
			 return i;
	return -1;
}

void Input_data(unsigned char code){
	int i; 
	if((i=FindCode(code))!=-1) //已有节点
		code_queue->Buffer[i]->possible++;
	else{//新节点
		struct HuffNode * temp=(struct HuffNode *)
							malloc(sizeof(struct HuffNode));
		temp->data=code;
		temp->possible=1;
		temp->code=0;
		temp->level=0;
		temp->left=temp->right=NULL;//叶子
		InsertData(code_queue,temp);
	}
	code_queue->sumwords++;
}

void swap(struct Queue *s,int sindex,int dindex){
		struct HuffNode * temp=(struct HuffNode *)
							malloc(sizeof(struct HuffNode));
		temp->data=s->Buffer[dindex]->data;
		temp->possible=s->Buffer[dindex]->possible;
		temp->left=s->Buffer[dindex]->left;
		temp->right=s->Buffer[dindex]->right;
		temp->level=s->Buffer[dindex]->level;
		s->Buffer[dindex]->data=s->Buffer[sindex]->data;
		s->Buffer[dindex]->possible=s->Buffer[sindex]->possible;
		s->Buffer[dindex]->left=s->Buffer[sindex]->left;
		s->Buffer[dindex]->right=s->Buffer[sindex]->right;
		s->Buffer[dindex]->level=s->Buffer[sindex]->level;
		s->Buffer[sindex]->data=temp->data;
		s->Buffer[sindex]->possible=temp->possible;
		s->Buffer[sindex]->left=temp->left;
		s->Buffer[sindex]->right=temp->right;
		s->Buffer[sindex]->level=temp->level;
}

void sortQueue(struct Queue *q,int start){
	//选择排序
	unsigned char min;
	for(unsigned char i=start;i<=q->QueueLen;i++){
		min=i;
		for(unsigned char j=i+1;j<=q->QueueLen;j++){
			if(q->Buffer[j]->possible<q->Buffer[min]->possible)
				min=j;
		}
		swap(q,i,min);
	}
	if(q->Buffer[0]->level<q->Buffer[1]->level)
		swap(q,0,1);
}

void Search(struct HuffNode * p,int flag){
	if(p!=NULL){
	  p->code=flag;
	  Search(p->left,p->code<<1);
	  Search(p->right,(p->code<<1)+1);
	}
}

void Out(struct HuffNode * p){
	if(p!=NULL){
	  if(p->left==NULL && p->right==NULL) printf("%d,%d,%f\n",p->data,p->code,p->possible);
	  Out(p->left);
	  Out(p->right);
	}
}

void DoHuffMan(){
	while(code_queue->QueueLen>1){
		struct HuffNode * temp=(struct HuffNode *)
								malloc(sizeof(struct HuffNode));	
		temp->code=0;
		temp->left=code_queue->Buffer[1];
		temp->right=code_queue->Buffer[0];
		if(code_queue->Buffer[1]->level>=code_queue->Buffer[0]->level)
			temp->level=code_queue->Buffer[1]->level+1;
		else
			temp->level=code_queue->Buffer[0]->level+1;
		temp->possible=code_queue->Buffer[1]->possible+
						code_queue->Buffer[0]->possible;
		code_queue->Buffer[0]=temp;
		DeleteIndex(code_queue,1);
		sortQueue(code_queue,0);
	}
	if(code_queue->Buffer[0]->level<code_queue->Buffer[1]->level)
		swap(code_queue,0,1);
	head->code=0;
	head->right=code_queue->Buffer[0];
	head->left=code_queue->Buffer[1];
	Search(head,0);
}

int FileIn(char *str){
	FILE *fp;
	if((fp=fopen(str,"rb"))==NULL) return 0;
	unsigned char data;
	while (!feof(fp)){
	fread(&data,1,1,fp);
	Input_data(data);
	}
	for (int i=0;i<=code_queue->QueueLen;i++)
		code_queue->Buffer[i]->possible/=code_queue->sumwords;
	return 1;
}

void main()
{   //初始化
	InitQueue(code_queue);

	//数据输入
	FileIn("HuffNode.h");

	//初排序
	sortQueue(code_queue,0);

	DoHuffMan();
	Out(head);
}