huffman-13.c

自适应的哈夫曼编码程序

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

typedef struct NODE
{
	int	weight;
	int	Char;
	int	nodeNo;
	struct NODE	*pPrt;
	struct NODE	*pCld[2];
	struct LINK	*plink;
	struct NODE	*pPrev;
}NODE,*PNODE;

typedef struct LINK
{
	PNODE pFirst;
	struct LINK	*pPrev;
	struct LINK	*pNext;
}LINK,*PLINK;

FILE *srcFile, *destFile,*pDestAdapFILE;
int	 srcFileNO, destFileNO,startChar, charCount, E=0, R,tmp[256];
unsigned char pInput[128],pOutput[128];
PNODE pCharNode[256],pNYT;
NODE root;

int	OutputCode(PNODE pNode);
int	Encode();
void Updatelink(PNODE pNode);
void NewHT(PNODE pNode);
void UpdateHT(unsigned char);
/////////////////////////////////////////////////////////////////
int main()
{
	    int i;
        int	isEncode = 1;
          PLINK plink, pPrevLINK;
	    PNODE  pNode,pNext;
        i = 1;
           if(!(srcFile = fopen("FILE.txt","r")))
	{
		printf("cannot open the source file! \n");
		return 0;
	}
	srcFileNO = fileno(srcFile);
	rewind(srcFile);
	if(!(destFile = fopen("CODE-A.txt","w")))
	{
        printf("cannot open the destination file! \n");
		return 0;
	}
	destFileNO = fileno(destFile);
     if(!(pDestAdapFILE = fopen("FILE.txt","r")))
	{
		printf("cannot open the source file! \n");
		return 0;
	}

        while(pow(2,(E+1))<=256)
              E++;

        R = 256 - (int)pow(2,E);
        root.nodeNo = 2*256-1;
        root.pPrt = NULL;
	    pNYT = &root;

        Encode();

	if(destFile)
		fclose(destFile);
	if(srcFile)
		fclose(srcFile);
	if(pNYT && pNYT != &root)
		free(pNYT);
	plink = root.plink;
	while(plink)
	{
		pNode = plink->pFirst;
		while(pNode)
		{
			pNext = pNode->pPrev;
			if(pNode != &root)
			free(pNode);
			pNode = pNext;
		}
		pPrevLINK = plink->pPrev;
		free(plink);
		plink = pPrevLINK;
	}
 printf("\n\nFILE.txt was encoded to FILE-A.txt by adaptive huffman coding\n");
 getch();
}
////////////////////////////////////////////////////////

int OutputCode(PNODE pNode)
{
	int len=0,marker=0;
    char c;

    fscanf(pDestAdapFILE,"%c",&c);
    printf("\nthe Huffman code of %c is :",c);

	if(pNode == pNYT)
			marker=1;
    while(pNode->pPrt)
	{
		tmp[len++] = (pNode->pPrt->pCld[1] == pNode)?1:0;
		pNode = pNode->pPrt;
	}
    if(marker == 1)
        tmp[0]=1;
	while(len--)
	{
    	printf("%d",tmp[len]);
        fprintf(destFile,"%d",tmp[len]);
	}
	return 1;
}
////////////////////////////////////////////////
int Encode()
{
	int bufLen,i;
	while(!eof(srcFileNO))
	{
        bufLen = read(srcFileNO, pInput, 128);
		if(!bufLen)
			break;

        for(i=0; i<bufLen; i++)
	   {
         if(!pCharNode[pInput[i]])
         {
         if(pNYT != &root)
         	if(!OutputCode(pNYT))
				return 0;
         }
		 else
  			if(!OutputCode(pCharNode[pInput[i]]))
				return 0;
         UpdateHT(pInput[i]);
	    }
         return 1;
       }
}
//////////////////////////////////////////////////////////
void UpdateLINK(PNODE pNode)
{
	PLINK plink = root.plink;
	PNODE  pNext;

	if(!plink && root.pCld[1])
	{
		plink = root.pCld[1]->plink;
		while(plink && plink->pNext)
			plink = plink->pNext;
	}

	while(plink && plink->pPrev && plink->pFirst->weight > pNode->weight)
	{
		plink = plink->pPrev;
	}

	if(plink && plink->pFirst->weight == pNode->weight)
	{
		pNode->plink = plink;

		if(pNode->plink->pFirst->nodeNo < pNode->nodeNo)
		{
			pNode->pPrev = pNode->plink->pFirst;
			pNode->plink->pFirst = pNode;
		}
		else
		{
			pNext = pNode->plink->pFirst;
			while(pNext->pPrev && pNext->pPrev->nodeNo > pNode->nodeNo)
				pNext = pNext->pPrev;
			pNode->pPrev = pNext->pPrev;
			pNext->pPrev = pNode;
		}
	}

	else
	{
		pNode->plink = (PLINK) malloc(sizeof(LINK));
		pNode->plink->pFirst = pNode;
		pNode->pPrev = NULL;
		if(!plink)
		{
			pNode->plink->pPrev = NULL;
			pNode->plink->pNext = NULL;
		}
		else if(plink->pFirst->weight < pNode->weight)
		{
			pNode->plink->pPrev = plink;
			pNode->plink->pNext = plink->pNext;
		}
		else
		{
			pNode->plink->pPrev = NULL;
			pNode->plink->pNext = plink;
		}
		if(pNode->plink->pPrev)
			pNode->plink->pPrev->pNext = pNode->plink;
		if(pNode->plink->pNext)
			pNode->plink->pNext->pPrev = pNode->plink;
	}
}
//////////////////////////////////////////////////////////
void NewHT(PNODE pNode)
{
	NODE node;
	PNODE pNext;
	if(!pNode)
		return;

	if(pNode->plink->pFirst != pNode->pPrt)
	{

		if(pNode->plink->pFirst->nodeNo > pNode->nodeNo)
		{
			node = *pNode->plink->pFirst;

			if(pNode->plink->pFirst->pPrt == pNode->pPrt)
			{
				pNode->pPrt->pCld[0] = (pNode->pPrt->pCld[0] == pNode)?pNode->plink->pFirst:pNode;
				pNode->pPrt->pCld[1] = (pNode->pPrt->pCld[1] == pNode)?pNode->plink->pFirst:pNode;
			}
			else
			{
				if(pNode->plink->pFirst->pPrt)
				{
					if(pNode->plink->pFirst->pPrt->pCld[0] == pNode->plink->pFirst)
						pNode->plink->pFirst->pPrt->pCld[0] = pNode;
					else
						pNode->plink->pFirst->pPrt->pCld[1] = pNode;
				}
				if(pNode->pPrt)
				{
					if(pNode->pPrt->pCld[0] == pNode)
						pNode->pPrt->pCld[0] = pNode->plink->pFirst;
					else
						pNode->pPrt->pCld[1] = pNode->plink->pFirst;
				}

				pNode->plink->pFirst->pPrt = pNode->pPrt;
				pNode->pPrt = node.pPrt;
			}
			pNext = pNode->plink->pFirst;
			while(pNext->pPrev->nodeNo > pNode->nodeNo) pNext = pNext->pPrev;
			if(pNext == pNode->plink->pFirst)
			{
				pNode->plink->pFirst->pPrev = pNode->pPrev;
				pNode->pPrev = pNode->plink->pFirst;
			}
			else
			{
				pNode->plink->pFirst->pPrev = pNode->pPrev;
				pNext->pPrev = pNode->plink->pFirst;
				pNode->pPrev = node.pPrev;
			}

			pNode->plink->pFirst->nodeNo = pNode->nodeNo;
			pNode->nodeNo = node.nodeNo;

			pNode->plink->pFirst = pNode;
		}
		
		if(pNode->pPrev)
			pNode->plink->pFirst = pNode->pPrev;
		else
		{

			if(pNode->plink->pPrev)
				pNode->plink->pPrev->pNext = pNode->plink->pNext;

			if(pNode->plink->pNext)
				pNode->plink->pNext->pPrev = pNode->plink->pPrev;
			free(pNode->plink);
		}
	}
	else
	{
		pNext = pNode->plink->pFirst;
		while(pNext->pPrev != pNode)	pNext = pNext->pPrev;
		pNext->pPrev = pNode->pPrev;
	}
	
	pNode->plink = NULL;
	pNode->weight++;
	UpdateLINK(pNode);
	NewHT(pNode->pPrt);
}
///////////////////////////////////////////////////////////
void UpdateHT(unsigned char c)
{
	if(!pCharNode[c])
	{
		pNYT->weight = 1;
		pNYT->Char = -1;
		pNYT->pCld[1] = (PNODE) malloc(sizeof(NODE));//new leaf
		pNYT->pCld[0] = (PNODE) malloc(sizeof(NODE));//new NYT

		pNYT->pCld[0]->pPrt = pNYT;
		pNYT->pCld[0]->nodeNo = pNYT->nodeNo-2;
		pNYT->pCld[0]->weight = 0;
		pNYT->pCld[0]->Char = -1;
		memset(pNYT->pCld[0]->pCld,0,sizeof(pNYT->pCld[0]->pCld));
		pNYT->pCld[0]->pPrev = NULL;
 	    pNYT->pCld[0]->plink = NULL;

		pNYT->pCld[1]->pPrt = pNYT;
		pNYT->pCld[1]->nodeNo = pNYT->nodeNo-1;
		pNYT->pCld[1]->weight = 1;
		pNYT->pCld[1]->Char = c;
		memset(pNYT->pCld[1]->pCld,0,sizeof(pNYT->pCld[1]->pCld));
		pNYT->pCld[1]->pPrev = NULL;
		pNYT->pCld[1]->plink = NULL;

		pCharNode[c] = pNYT->pCld[1];
		pNYT = pNYT->pCld[0];

		UpdateLINK(pNYT->pPrt);
		pCharNode[c]->plink = pCharNode[c]->pPrt->plink;
		pCharNode[c]->pPrt->pPrev = pCharNode[c];

		NewHT(pCharNode[c]->pPrt->pPrt);
	}
	else
	{
		NewHT(pCharNode[c]);
	}
}