haff.cpp

C语言写得haffman编码。只编码不编译。适用于C语言环境。

#include <stdio.h>
#include <stdlib.h>
#define MAXINT 99999999
#define MAXNUM 100
#define MAXNODE 50
struct HtNode
{
	int ww;
	int parent;
	int llink,rlink;
};
struct HtTree
{
	struct HtNode ht[MAXNUM];
	int root;
};
typedef struct HtTree *PHtTree;


/* 构造具有m个叶结点的哈夫曼树, 数组w存放权值 */
PHtTree Huffman(int m,int *w) 
{ 
	PHtTree pHT; 
	int i,j,m1,m2; 
	int x1,x2;            /* 存放权值最小的两个结点的位置 */
	pHT=(PHtTree)malloc(sizeof(struct HtTree));   /* 创建空哈夫曼树 */ 
	
	if(pHT==NULL)
	{
		printf("Out of space!!\n");
		return pHT;
	}
	for(i=0;i<2*m-1;i++)                           /* 置初态 */ 
		{ 
			pHT->ht[i].llink=-1; 
			pHT->ht[i].rlink=-1; 
			pHT->ht[i].parent=-1;
			if(i<m)
				pHT->ht[i].ww=w[i];
			else 
				pHT->ht[i].ww=-1;
		}
	for(i=0;i<m-1;i++)                 /* 每循环一次构造一个内部结点 */ 
		{ 
			m1=MAXINT;
			m2=MAXINT;
			x1=-1;
			x2=-1;
			for(j=0;j<m+i;j++)
			
				if(pHT->ht[j].ww<m1&&pHT->ht[j].parent==-1)
				{
					m2=m1;
					x2=x1;
					m1=pHT->ht[j].ww;
					x1=j;
				}
				else 
					if(pHT->ht[j].ww<m2&&pHT->ht[j].parent==-1)
					{
						m2=pHT->ht[j].ww;
						x2=j;
					}
					pHT->ht[x1].parent=m+i;
					pHT->ht[x2].parent=m+i;
					pHT->ht[m+i].ww=m1+m2;
					pHT->ht[m+i].llink=x1;
					pHT->ht[m+i].rlink=x2;
					pHT->root=m+i;
			
		}
	return pHT;
			
	
}

//打印huffman树pHT中每个外部结点的编码
void printcode(PHtTree pHT,int m)
{
	int i,j,parent;
	for(j=0;j<m;j++)
	{
		if(pHT->ht[j].llink!=-1||pHT->ht[j].rlink!=-1)continue;			//不是分支节点
		printf("the Reverse code of node %d is:",j+1);					//得到的编码应该倒过来
		i=j;
		while(pHT->ht[i].parent!=-1)
		{
			parent=pHT->ht[i].parent;
			if(pHT->ht[parent].llink==i)
				printf("0");
			else
				printf("1");
			i=parent;
		}
		printf("\n");
	}
}

void main()
{
	int i,m,*w;
	PHtTree pHT;
	printf("输入结点数:");
	scanf("%d",&m);
	pHT=(PHtTree)malloc(sizeof(struct HtTree));
	w = (int *)malloc(m*sizeof(int)); 
	printf("输入%d个结点的权值\n",m); 
	for(i=0;i<m;i++) scanf("%d",&w[i]); 
	printf("输出的编码应该是倒过来的.\n");
	pHT=Huffman(m,w);
	printcode(pHT,2*m-1);
}