www.pudn.com > Hman_byC.rar > HuffMan_main.cpp

#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]->possibleBuffer[min]->possible) 
				min=j; 
		} 
		swap(q,i,min); 
	} 
	if(q->Buffer[0]->levelBuffer[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]->levelBuffer[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); 
}