haffman.txt

用二叉树实现哈佛曼编码

     
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define null 0
#define MAXN 100
#define MAXM 300

struct tagTree{//用二叉排序树保存出现的各个字符
	char optr;    //需要编码的某个字符
	int n_appear; //当前字符出现的次数
	struct tagTree*lchild;
	struct tagTree*rchild;
}*btree;//btree作为二叉排序树的根

struct tagHeap{//堆结构
	char optr;    //当前字符，叶子时有效
	int n_appear; //当前子树出现的次数
	struct tagHeap*lchild;
	struct tagHeap*rchild;
}*heap[MAXM];//开始时最多可以有MAXN棵子树

int n_heap,n_code;
char code[MAXN];//打印haffman编码时候用到

void insert_to_heap(struct tagHeap *pt)//插入一个元素到堆，从下到上调整
{
	heap[++n_heap] = pt; //插入节点到最后
	int parent,child=n_heap;
	while(child > 1)
	{
		parent = child >> 1;//获得child的parent节点的index
		if(heap[parent]->n_appear <= heap[child]->n_appear)break;
		pt = heap[parent];          //child节点和parent节点交换步骤1
		heap[parent] = heap[child]; //child节点和parent节点交换步骤2
		heap[child] = pt;           //child节点和parent节点交换步骤3
		child = child >> 1;
	}
}//inseart_to_heap

void delete_from_heap(struct tagHeap *&pt)//从堆中取出根节点，从上到下调整
{
	if(!n_heap)//堆为空则有pt返回NULL
	{
		pt = null; return;
	}
	pt = heap[1];
	int child,parent=1;
	while(1)
	{
		child = parent << 1;//获取左孩子的index
		if(child < n_heap)
		{
			if(heap[child]->n_appear <= heap[child+1]->n_appear)
			{
				heap[parent] = heap[child];
				parent = child;
			}
			else
			{
				heap[parent] = heap[child+1];
				parent = child + 1;
			}
		}
		else if(child == n_heap)
		{
			heap[parent] = heap[child];
			--n_heap;
			break;
		}
		else
		{
			heap[parent] = heap[n_heap];
			--n_heap;
			break;
		}
	}
}//delete_from_heap

void insert_to_btree(struct tagTree*&btree,char optr)//新出现的字符插入到二叉树，已有的则计数器加一
{
	if(btree == null)
	{
		btree = (struct tagTree*)malloc(sizeof(struct tagTree));
		btree->optr = optr;
		btree->n_appear = 1;
		btree->lchild = null;
		btree->rchild = null;
	}
	else if(btree->optr == optr)
	{
		btree->n_appear++;
	}
	else if(btree->optr < optr)
	{
		insert_to_btree(btree->rchild,optr);
	}
	else
	{
		insert_to_btree(btree->rchild,optr);
	}
}//insert_to_btree

void init_data(void)
{
	btree = null;
	n_heap = 0;
	char optr;
	while(scanf("%c",&optr)!=EOF)
	{
		insert_to_btree(btree,optr);
	}
}//init_data

void init_heap(struct tagTree*btree)
{
	if(btree != null)
	{
		struct tagHeap *pt;
		pt = (struct tagHeap *)malloc(sizeof(struct tagHeap));
		pt->lchild = null;
		pt->rchild = null;
		pt->n_appear = btree->n_appear;
		pt->optr = btree->optr;
		insert_to_heap(pt);
		if(btree->lchild != null)
		{
			init_heap(btree->lchild);
		}
		if(btree->rchild != null)
		{
			init_heap(btree->rchild);
		}
	}
}//init_heap

void haffman(void)
{
	init_heap(btree);
	while(n_heap >= 2)//不断的将出现次数最少的两棵子树合并
	{
		struct tagHeap *pt1,*pt2,*pt;
		delete_from_heap(pt1);
		delete_from_heap(pt2);
		pt = (struct tagHeap *)malloc(sizeof(struct tagHeap));
		pt->lchild = pt1;
		pt->rchild = pt2;
		pt->optr = '\0';
		pt->n_appear = pt1->n_appear + pt2->n_appear;
		insert_to_heap(pt);
	}
}//haffman

void print_haffman_code(struct tagHeap *pt,int len)//打印haffman编码
{
	if(pt != null)
	{
		if(pt->lchild == null)
		{
			code[len] = '\0';
			printf("optr=%c,value=%d,n_appear=%d,haffman code=%s\n",pt->optr,(int)pt->optr,pt->n_appear,code);
		}
		else
		{
			code[len] = '0';
			print_haffman_code(pt->lchild,len+1);
		}
		if(pt->rchild != null)
		{
			code[len] = '1';
			print_haffman_code(pt->rchild,len+1);
		}
	}
}//print_haffman_code

void print_haffman(void)
{
	if(n_heap >= 1)
	{
		print_haffman_code(heap[1],0);
	}
	else
	{
		printf("输入为空，编码失败!\n");
	}
}//print_haffman

int main(void)
{
	freopen("D:\\in.txt","r",stdin); //文件输入，若要改为手动输入，请注释次行
	init_data();
	haffman();
	print_haffman();
	return 0;
}