huffmanencode.cpp

二叉树的各种操作

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#define N 10

typedef struct{
    unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode; //字符指针的指针

void Select(HuffmanTree HT,int k,int &s1,int &s2)
{
	//printf("i-1=%d   ",k);
	int i;
	unsigned int min;
    s1=s2=0;
	int flag=0;
	while (s1==0 || s2==0)
	{
		for (i=1;i<=k;i++) //用于从1-k中选择第一个parent为零的节点
		{
			if (HT[i].parent==0 && i!=s1)
			{
				min=HT[i].weight;
				if (s1==0)
					s1=i;
	            else
			        s2=i;
				//printf("第一个parent为0的节点是%d:%d",i,HT[i].weight);
			    break;
			}
		}
        
	    for(i=1;i<=k;i++)//求得weight值最小并且parent为0的节点
		{
			if ((HT[i].weight<min) && HT[i].parent==0 && i!=s1)
			{
				min=HT[i].weight;
				if (flag==0)
					s1=i;
	            else
			        s2=i;
			}
		}
		flag=1;
	}//while
	//printf("%d-%d\n",s1,s2);
}//Select


void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int * w,int n)
{
	int i;
	int s1,s2;
	char * cd;
	int start;
	if (n<1)
		return;
	int m=2*n-1; //生成哈夫曼树的节点总数
    HuffmanTree p;

	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //给m+1个节点分配内存单元，0号单元未用
	
	printf("初始化。。\n");
	Sleep(1000);
	p=HT+1;
	for(i=1;i<=n;++i)  //叶子节点初始化
	{
		p->lchild=0;
		p->parent=0;
		p->rchild=0;
		p->weight=*w;
		//printf("%d",*w);
		p++;
		w++;
	}
	/*
	printf("\n");
	for(p=HT+1,i=1;i<=n;++i,++p)  //叶子节点初始化
	{
		printf("节点%d:左孩子:%d,右孩子:%d,权重:%d,父节点%:%d\n",i,p->lchild,p->rchild,p->weight,p->parent);
	}
	*/
	for (i=n+1;i<=m;++i)//根节初始化
	{
		p->lchild=0;
		p->parent=0;
		p->rchild=0;
		p->weight=0;
		++p;
	}
    p=HT+n;
	/*
	for(i=n+1;i<=m;++i)
	{
		printf("节点%d:左孩子:%d,右孩子:%d,权重:%d,父节点%:%d\n",i,p->lchild,p->rchild,p->weight,p->parent);
		++p;
	}
    */
	printf("建立哈夫曼树。。。。\n");
	Sleep(1000);
	for (i=n+1;i<=m;++i)//建哈夫曼树，确定n-1个内部节点
	{
		Select(HT,i-1,s1,s2); //从1到i-1中选择weight最小的并且parent为零的节点
		//printf("第%d次选择%d-%d\n",i-n,s1,s2);
	    HT[s1].parent=i;
	    HT[s2].parent=i;
	    HT[i].lchild=s1;
	    HT[i].rchild=s2;

	    HT[i].weight=HT[s1].weight + HT[s2].weight;
		HT[i].parent=0;
	}
    //哈夫曼树建立完毕！
	printf("开始编码。。。\n");
	Sleep(1000);
	HC= (HuffmanCode) malloc ((n+1)*sizeof(char *)); //分配指针数组的空间
	cd = (char*) malloc (n*sizeof(char)); //工作空间，用于临时存放编码
	cd[n-1]='\0';
    unsigned int c,f;
	for (i=1;i<=n;++i)
	{
		start=n-1;
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
			if (HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		HC[i]=(char*) malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
		printf("%d:",HT[i].weight);
	    puts(HC[i]); //输出编码
	}
	free(cd);
}//HuffmanCoding

void main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int weight[N]={15,8,3,9,8,6,4,7,13,10};
	HuffmanCoding(HT,HC,weight,N);

}