haffman.c

数据结构学习点滴

/*************************************************
* Copyright (c) 2005, 南天软件金融软件部         *
* All rights reserved.                           *
*                                                *
* 文件名称: haffman.c                            *
* 文件标识:                                      *
* 摘    要: 实现哈夫曼编码                       *
*                                                *
* 当前版本: 1.1                                  *
* 作    者: YYF                                  *
* 完成日期: 2005.1.15                            *
*                                                *
* 取代版本: 1.0                                  *
* 原作者  : YYF                                  *
* 完成日期: 2005.1.14                            *
*************************************************/
#include "myhdr.h"
#define MAXNODE 30
#define MAXNUM 5000

/***哈夫曼树结构体***/

struct haffnode{
	int	weight;
	int	parent;
	int	lchild;
	int	rchild;
};

/********struct haffcode{
	*int	bit[MAXNODE];
	*int	start;
	*int	weight;
}****/

struct haffnode *haffmantree();
int haffmancode( struct haffnode *tree );

int
main()
{
	struct haffnode		*tree;
	tree = NULL;
	tree = haffmantree();
	haffmancode( tree );
	return( 0 );
}

/***构建哈夫曼树***/

struct haffnode *
haffmantree(){
	int	LeafCount;
	int	NodeCount;
	struct haffnode 	ht[MAXNODE];
	int 	pos1;
	int	pos2;
	int	min1;
	int 	min2;
	int	i;
	int	j;
	
	LeafCount = 0;
	NodeCount = 0;
	pos1	  = 0;
	pos2      = 0;
	min1      = 0;
	min2      = 0;
	i         = 0;
	j         = 0;
	memset( &ht, 0, sizeof( struct haffnode ) );

	/***定义叶子节点数***/

	printf( "Input the num of node\n" );
	scanf( "%d", &LeafCount );
	fflush( stdin );
	if( LeafCount >= 16 )
	{
		printf( "The LeafCount should be less 16\n" );
		exit( 1 );
	}
		
	if( LeafCount <= 1 )
	{
		printf( "Node is poor\n" );
		exit( 1 );
	}
	/***哈夫曼树的初始化***/
		
	NodeCount = 2 * LeafCount - 1;
	for( i = 0; i < NodeCount; i++ )
	{
		ht[i].parent = 0;
		ht[i].lchild = 0;
		ht[i].rchild = 0;
	}
	for( i = 0; i < LeafCount; i++ )
	{
		printf( "Input a weight for %d 号节点\n", i );
		scanf( "%d", &ht[i].weight );
		fflush( stdin );
	}  		
	for( i = LeafCount; i < NodeCount; i++ );
	{
		ht[i].weight =  0;	
	}
	
	/***找两个未在哈夫曼树中的最小节点***/

	for( i = LeafCount; i < NodeCount; i++ )
	{
		pos1 = 0;
		pos2 = pos1;
		min1 = MAXNUM;
		min2 = min1;
		for( j= 0; j < i; j++ )
		{
			if( ht[j].parent == 0 )
			{
				if( ht[j].weight < min1 )
				{
					pos2 = pos1;
					min2 = min1;
					pos1 = j;
					min1 = ht[j].weight;
				}
				else
				if( ht[j].weight < min2 )
				{
					pos2 = j;
					min2 = ht[j].weight;
				}
			}
		}
		
		/***建立哈夫曼树***/
	
		ht[i].lchild = pos1;
		ht[i].rchild = pos2;
		ht[i].weight = ht[pos1].weight + ht[pos2].weight;
		ht[pos1].parent = i;
		ht[pos2].parent = i;
	}
	
	for( i = 0 ; i < NodeCount; i++ )
	{
		printf( "the %d node weight is %d\n", i, ht[i].weight );
		printf( " address of %d node %d\n", i, &ht[i] );
	}
	return ht;
}

int
haffmancode( struct haffnode *tree )
{
	struct haffnode		*PNode;/**哈夫曼节点**/
	int	j;		       /**循环变量***/	
	int	i;                     /**循环变量***/
	int	LeafCount;             /**叶子节点***/
	int	LeafNum;               /**某个叶子**/
	int	NodeNum;               /**某个父节点**/
	int	start;		       /**编码循环变量**/
	int	hc[15];		       /**存储哈夫曼编码**/	
	struct haffnode		ht[MAXNODE];/**存储哈夫曼树**/
	
	i = 0;
	j = 0;
	LeafCount = 0;
	LeafNum = 0;
	NodeNum = 0;
	start = 0; 
	PNode = tree;
	memset( hc, 0, sizeof( hc ) );
	memset( &ht, 0, sizeof( struct haffnode ) );
	
	/**求出叶子数**/
	while( PNode != NULL && PNode->weight != 0 )
	{
		i++;
		PNode++;
	}
	LeafCount = ( i + 1 ) / 2;

	/***下面这个指针让其回到首地址，很重要***/
	PNode = tree;
	
	/**存储哈夫曼树***/
	for( i = 0; i< 2 * LeafCount - 1; i++ )
	{
		ht[i].weight = PNode->weight;
		ht[i].lchild = PNode->lchild;
		ht[i].rchild = PNode->rchild;
		ht[i].parent = PNode->parent;
		PNode++;
	}
	
	/***生成哈夫曼编码***/
	for( i = 0; i < LeafCount; i++ )
	{
		LeafNum = i;
		NodeNum = ht[i].parent;
		while( NodeNum != 0 )
		{
			if( ht[NodeNum].lchild == LeafNum )
			{
				hc[start] = 0;
				start++;
			}
			else
			{
				hc[start] = 1;
				start++;
			}
			
			/**以下是while循环的条件**/ 
			LeafNum = NodeNum;
			NodeNum = ht[NodeNum].parent;
		}
		
		printf( "the huffmancode is:  " );
		/**打出哈夫曼编码***/	
	        for( j = 0; j < start; j++ )
		{
			printf( "%d", hc[start-j-1] );
		}
		printf( "\n" );
		start = 0;/**清理数组hc[]**/
		
	}
	
	return( 0 );
}