ecbtree.c

用哈夫曼编码实现文件压缩和解压缩. 压缩过程的实现：1创建Haffman树&#61664 2打开需压缩文件&#61664 3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出&

#include "ECBTree.h"
#include "MyAssert.h"
#include "ECStack.h"
#include <stdio.h>
#include <stdlib.h>

PBinTree consBTree(EBTreeType* initList)
{
	PBinTree pbtree;
	pbtree=(PBinTree)malloc(sizeof(BinTree));
	
	if(pbtree!=NULL)
		*pbtree=consRestBTree(initList);
	
	gConsPos=0;
	
	return pbtree;
}

PBinTreeNode consRestBTree(EBTreeType* initList)
{
	PBinTreeNode pbnode;
	
	if(initList[gConsPos]=='@')
	{
		gConsPos++;
		pbnode=NULL;
	}
	else
	{
		pbnode=(PBinTreeNode)malloc(sizeof(struct BinTreeNode));
		
		assertF(pbnode!=NULL,"In consRestBTree,MEM APPLY FAILURE\n");
		
		pbnode->info=initList[gConsPos];
		
		gConsPos++;
		
		pbnode->llink=consRestBTree(initList);
		pbnode->rlink=consRestBTree(initList);
	}
	
	return pbnode;
}

void preOrder(PBinTreeNode inNode)
{
	if(inNode==NULL)
		return;
	else
	{
		//preVisit(inNode->info);
		printf("%c->",inNode->info);
		preOrder(inNode->llink);
		preOrder(inNode->rlink);
	}
}

void preVisit(EBTreeType info)
{
	printf("%c->",info);
}


//before it
/*
	findLen=0;
	gFind=0;
*/
void findPath(PBinTreeNode inNode,PBinTreeNode searchNode)
{
	if(inNode==NULL)
		return;
	else
	{
		
		if(gFind)
			 return;
		
		prePanDuan(inNode,searchNode);
		
		if(!gFind)
		{
			findPath(inNode->llink,searchNode);
			findPath(inNode->rlink,searchNode);
		}
	}
}

void prePanDuan(PBinTreeNode inNode,PBinTreeNode searchNode)
{
	if(inNode==searchNode)
			gFind=1;
			
	gFindList[findLen]=inNode->info;
	findLen++;
}


void  locateNode(PBinTreeNode inNode,EBTreeType inInfo,PBinTree targetNode)
{
	if(inNode==NULL)
		return ;
	else
	{
		if(inNode->info==inInfo)
		{
			*targetNode=inNode;
			gFind=1;
			return;
		}
		else
		{
			locateNode(inNode->llink,inInfo,targetNode);
			locateNode(inNode->rlink,inInfo,targetNode);
		}
	}

 }

 int locateVisit(EBTreeType info)
 {
	return 0;
 }
 
 void preOrderUnStack(PBinTreeNode inNode)
{
	
	PBinTreeNode p;
	PSeqStack myStack;
	int flag;

	assertF(inNode!=NULL,"pass in node is null\n");
	

	myStack=createNullSeqStack();
	p=inNode;
	
	preVisit(p->info);//visit
	seqPush(myStack,p);
	while(!isNullSeqStack(myStack))
	{
		while(p->llink!=NULL)
		{
			p=p->llink;//move to left child node
			preVisit(p->info);//visit
			seqPush(myStack,p);//push current node to the stack.
		}
		
		flag=0;
		
		while(!flag&&!isNullSeqStack(myStack))
		{
			p=seqPop(myStack);
			if(p->rlink!=NULL)
			{
				p=p->rlink;
				preVisit(p->info);//visit
				seqPush(myStack,p);
				flag=1;
			}
		}
	}
	printf("preOrder visit end\n");
}


/*Start of Haffman Tree Ulti Function*/
/*
	struct HtNode
	{
		EBTreeType type;
		int parentIndex;
		int llinkIndex;
		int rlinkIndex;
	};
*/
PHtTree consHtTree(EBTreeType* initList)
{
	PHtTree pht;
//	int i;
	
	pht=(PHtTree)malloc(sizeof(struct HtTree));
	
	assertF(pht!=NULL,"in consHtTree,mem apply failure\n");
	
//	for(i=0;i<2*m-1;i++)
	
	return NULL;
}

PHtTree haffmanAlgorithm(int m,EBTreeType* w)
{
	PHtTree pht;
	int i,j;
	int firstMinIndex,secondMinIndex;
	int firstMinW,secondMinW;
	
	pht=(PHtTree)malloc(sizeof(struct HtTree));
	
	assertF(pht!=NULL,"in haffman algorithm,mem apply failure\n");
	
	/*Initialize the tree array*/
	for(i=0;i<2*m-1;i++)
	{
		pht->ht[i].llinkIndex=-1;
		pht->ht[i].rlinkIndex=-1;
		pht->ht[i].parentIndex=-1;
		if(i<m)
		{
			pht->ht[i].ww=w[i];
			pht->ht[i].info=(char)i;
		}
		else 
			pht->ht[i].ww=-1;
	}
	
	for(i=0;i<m-1;i++)//new Inner Node Num:m-1
	{
		firstMinW=MAXCHAR;
		firstMinIndex=-1; 
		
		secondMinW=MAXCHAR;
		secondMinIndex=-1;
		
		for(j=0;j<m+i;j++)
		{
			if(pht->ht[j].ww<firstMinW&&pht->ht[j].parentIndex==-1)
			{
				//trans minFirst info to minSecond info
				secondMinIndex=firstMinIndex;
				secondMinW=firstMinW;
				
				//set new first min node.
				firstMinIndex=j;
				firstMinW=pht->ht[j].ww;
			}
			else if(pht->ht[j].ww<secondMinW&&pht->ht[j].parentIndex==-1)/*update second node info*/
			{
				secondMinW=pht->ht[j].ww;
				secondMinIndex=j;
			}
		}
		
		//Construct a new node. m+i is current new node's index
			pht->ht[firstMinIndex].parentIndex=m+i;
			pht->ht[secondMinIndex].parentIndex=m+i;
			
			pht->ht[m+i].ww=firstMinW+secondMinW;
			pht->ht[m+i].llinkIndex=firstMinIndex;
			pht->ht[m+i].rlinkIndex=secondMinIndex;
			pht->rootIndex=m+i;
	}
	
	return pht;
}

/*Invoke
	preHtOrder(myHtTree,myHtTree->rootIndex)
*/
void preHtOrder(PHtTree inTree,int rootIndex)
{
	if(rootIndex==-1)
		return;
	else
	{
		preHtVisit(inTree->ht[rootIndex].info);
		preHtOrder(inTree,inTree->ht[rootIndex].llinkIndex);
		preHtOrder(inTree,inTree->ht[rootIndex].rlinkIndex);
	}
}
/*Invoke:
	preHaffListMake(myHtTree,myHtTree->rootIndex,0x00,0,myList)
*/
void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inList)
{
	/*
	typedef struct
	{
		char asciiCode;
		unsigned haffCode;
		int haffCodeLen;
	}HaffCode;
	*/
	if(inTree->ht[rootIndex].llinkIndex==-1&&inTree->ht[rootIndex].rlinkIndex==-1)
	{
		inList[inTree->ht[rootIndex].info].haffCode=youBiao;
		inList[inTree->ht[rootIndex].info].haffCodeLen=sDepth;
	}
	else
	{
		preHaffListMake(inTree,inTree->ht[rootIndex].llinkIndex,youBiao<<1,sDepth+1,inList);
		preHaffListMake(inTree,inTree->ht[rootIndex].rlinkIndex,(youBiao<<1)|0x01,sDepth+1,inList);
	}
}


void preHtVisit(InfoType info)
{
	printf("%c->",info);
}