tree.c

哈夫曼压缩程序

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#include"N_error.h"
#include"tree.h"
#include"file.h"
#include"binary.h"
#include"compress.h"


/////////////////////////////////////////////////////////////////////////////////////////////////
unsigned int Statist(weight_t OutWeightArray[256],FILE *fp)/*return how much bitys of the head should be cuted and store the code appears number to A */
{
	int ch;
	unsigned int n = 0;//use to check if the size is too big !
	for(ch = 255;ch >= 0;ch--)
		OutWeightArray[ch] = 0;
	while((ch = ReadC(fp)) != EOF)
	{
		OutWeightArray[ch]++;
		if(++n == -1)//here -1 is the bigest int number because n is unsigned!
		{
			N_ERROR("sorry the file you want to compress is too big more than 4 Gb !");
			exit(0);
		}
	}
	return n;
	/*
	int ch,ch1,i,j,n,r; //here use int ch and ch1 is make 255 not equals to -1(EOF);
	float ra[8] = {0};
	unsigned char *const cp1 = (unsigned char*)&ch1;
	unsigned char *const cp = (unsigned char*)&ch;
	weight_t array[8][256] = {{0}};
	n = 0;
	ch1 = fgetc(fp);
	while((ch = fgetc(fp))!= EOF)	//here use int ch is make 255 not equals to -1(EOF);
	{
		*(cp1+1) = ch;
		for(j = 0;j < 8; j++)
		{
			array[j][*cp1]++;
			ch1 >>= 1;
		}
		if(++n == -1)//here -1 is the bigest int number because n is unsigned!
		{
			N_ERROR("sorry the file you want to compress is too big more than 4 Gb!");
			exit(0);
		}
	}
	for(i = 0;i < 8;i++)
	{
		for(j = 0;j < 256;j++)
		{
			ra[i] += ((float)array[i][j]/(float)n)*((float)array[i][j]/(float)n);
		}
	}
	
	/*************output file fp's size*******************************/
	/*OutFlieSize = n;

	r = 0;
	for(i = 0;i < 8;i++)
	{
		if(ra[r] > ra[i])
			r = i;		
	}
	for(i = 0;i < 256;i++)
		OutWeightArray[i] = array[r][i];
	return r;*/
}
///////////////////////////////////////////////////////////////////////////////////////////
void Swap_2(node_p A, node_p B)
{
    node_t T = *A;
    *A = *B;
    *B = T;
}

void Swap_3(node_p A, node_p B, node_p C)
{
    node_t T = *A;
    *A = *B;
    *B = *C;
    *C = T;
}

void GiveTreeKey(node_p root)
{
	static int key = 1;  //key start from 1 is better than from 0;
	if(!root)N_ERROR("Can not give a empty tree a key!");
	else 
		if(root->Left == NULL)
			root->Key = key++;
		else/*root->Left != 0*/
		{
			GiveTreeKey(root->Left);
			root->Key = key++;
			GiveTreeKey(root->U.Right);
		}	
}


void SaveNodeKey(const node_p root,weight_t KeyArray[256])
{
	if(!root)
	{
		N_ERROR("The tree is empty can not save it's node key");
		exit(0);
	}
	else 
	{
		if(!root->Left)
		{
			if(root->U.Label < 0)
			{N_ERROR("Array's subscript must biger then 0 (int function SaveNodeKey)"); exit(0);}
			 KeyArray[root->U.Label] = root->Key;
		}
		else
		{
			SaveNodeKey(root->Left,KeyArray);
			SaveNodeKey(root->U.Right,KeyArray);
		}
	}
}

/*********用lw创建huffman tree*********************/


node_p MyHuffman(label_weight_p lw,int n)/*A[256]为code信息保存key的数组*/
{
		int i, j, k;
		node_p A;
		if(n == 0) return 0;

		if( ( A = (node_p)CallSpace((2*n-1)*sizeof(*A)) ) == NULL)
		{ exit(0); }
		for ( i = n-1; i >= 0; i-- ) {
			A[i+n-1].Left = 0;
			A[i+n-1].U.Label = lw[i].Label;
			A[i+n-1].Weight = lw[i].Weight;
		}

		for ( k = n-2, i = 2*n-2; i > 0; k--, i -= 2 )
		{
			if ( A[i].Weight > A[i-1].Weight )
				Swap_2(A+i, A+i-1);
			for ( j = i-2; j > k; j-- ) {
				if ( A[j].Weight < A[i].Weight )
					Swap_3(A+i-1, A+i, A+j);
				else if ( A[j].Weight < A[i-1].Weight )
					Swap_2(A+i-1, A+j);
			}
			A[k].Left = A+i;
			A[k].U.Right = A+i-1;
			A[k].Weight = A[i].Weight+A[i-1].Weight;
		}
		GiveTreeKey(A);//给每一个节点一个key有利于搜索！
	return A;
}
void FreeTree(node_p Root)
{
	free(Root);
}

node_p ConstructTree(weight_t WeightInKeyOutArray[256])
{
	/******用统计好的数组A创建需要保存的字节的label_weight*******************/
	int i = 0,n = 0;
	node_p r;
	label_weight_t lw[256] = {{0,0}};
	for(i = 0,n = 0;i < 256;i++)
	{
		if(WeightInKeyOutArray[i])//如果A[i]不为空则这文件中存在字符i需要编码；
		{
			lw[n].Label = i;
			lw[n].Weight = WeightInKeyOutArray[i];
			n++;
		}
	}
	if( n == 0) return 0;
	r = MyHuffman(lw,n);
	SaveNodeKey(r,WeightInKeyOutArray);
	return r;
}
///////////////////store a tree end with the liftest node///////////////////////
void TreeStoNode(node_p root,FILE *fp)
{
	if( !root->Left )
	{
		if( !WriteC(root->U.Label,fp,"Write file error when tree sto nodes"))
			exit(0);
	}
	else
	{
		TreeStoNode(root->Left,fp);
		TreeStoNode(root->U.Right,fp);
	}	
}


void TreeStoEdge(node_p root,int *ch, FILE *fp)
{
	unsigned char *const cp = (char *)ch,*const positionp = (char *)ch+1;
	if( root->Left)
	{	
		WriteBitToC(cp,0,*positionp);
		if( *positionp )
		{
			(*positionp)--;
		}
		else
		{
			WriteFullCToFile( 1,cp,fp);
			*positionp = 7;
		}

		TreeStoEdge(root->Left,ch,fp);
	
		WriteBitToC(cp,1,*positionp);
		if( *positionp )
		{
			(*positionp)--;
		}
		else
		{
			WriteFullCToFile( 1,cp,fp);
			*positionp = 7;
		}

		TreeStoEdge(root->U.Right,ch,fp);
	}
}

void TreeSto(node_p const root,FILE *fp)
{
	node_p p = root;
	int ch = 0;
	char *const cp = (char*)&ch,*const positionp = (char*)&ch + 1;
	char i = 0;

	if( !root )N_ERROR("Can't store a empty tree");
	TreeStoNode(root,fp);
	while( p->Left ) //Sto a leftist label to the end;
	{
		p = p->Left;
	}
    WriteC(p->U.Label,fp,"File Write error ,may be the disk is full");

	ch = 0;
	*positionp = 7;
	TreeStoEdge(root,&ch,fp);

	//make the end of edge stored char with 1;
	for(i = *positionp;i >= 0;i--)
	{
		WriteBitToC(cp,1,i);
	}
	WriteC(*cp,fp,"At function TreeSto Cant not write to file when write Edges");

}
//////////////////////////////////////////////////////////////////////////////
int LeafNumber(node_p root)
{
	if( !root)return 0;
	if( !root->Left)
	{
		return 1;
	}
	else
	{
		return (LeafNumber(root->Left)+LeafNumber(root->U.Right));
	}
}


/////////////////////////////////////////////////////////////////////////////////////////

node_p GetLeft(node_p root)
{
	if( !root)
	{
		N_ERROR("at function GetLeft empty tree can not go left!");
		exit(0);
	}
	return root->Left ;
}

node_p GetRight(node_p root)
{
	if( !root)
	{
		N_ERROR("at function GetRight empty tree can not go right!");
		exit(0);
	}
	return root->U.Right;
}

int IsLeaf(node_p root)
{
	if( !root)return 0;
	if(root->Left) return 0;
	else return 1;
}

key_t GetKey(node_p root)
{
	if(root) return root->Key;
	else
	{
		N_ERROR("at function GetKey can not get a key from a empty tree!");
		exit(0);
	}
}

label_t GetLabel(node_p root)
{
	if(IsLeaf(root))return root->U.Label;
	else
	{
		N_ERROR("at function GetLabel can not get a label from a tree which is not a Leaf!");
		exit(0);
	}
}

weight_t GetWeight(node_p root)
{
	if( root)
		return root->Weight;
	else
	{
		N_ERROR("at function GetWeight can not get weight from a empty tree");
		exit(0);
	}
}

//////////////////////////////////////////////////////////////////////////////////////////
void PrintNodePath(node_p root,weight_t KeyArray[256],label_t l)
{
	printf("\n%c code %d:",l,l);
	while(root->Left)
	{
		if(KeyArray[l] < root->Key)
		{
			root = root->Left;
			printf("0");
		}
		else 
		{
			root = root->U.Right;
			printf("1");
		}
	}
}

/*test main function*/
/*
void main()
{
	weight_t A[256] = {0};
	int i = 0;
	node_p root;
	label_weight_t lw[5] = {
		{'a',77},
		{'f',887},
		{'j',73},
		{'o',9987},
		{'u',1},
	};

	root = MyHuffman(lw,5);
	SaveNodeKey(root,A);
	for(i = 0;i < 256;i++)
		printf("%d\n",A[i]);
	PrintNodePath(root,A,'a');
	PrintNodePath(root,A,'f');
	PrintNodePath(root,A,'o');
	PrintNodePath(root,A,'u');
	PrintNodePath(root,A,'j');
	
	FreeTree(root);

	for(i = 0;i < 256;i++)
		A[i] = i;
	root = ConstructTree(A);
	for(i = 0; i < 256;i++)
		PrintNodePath(root,A,(char)i);
	FreeTree(root);	
}
*/