huffcoder.cpp

基于哈夫曼编码的实现

//HUFFMAN    仅支持小写的26个字母排序,不支持其它任何字符，如大写，空格等等
#include <iostream.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>

typedef struct node{
	char cha;  //character
	int num;   //文本中该字符出现的次数
	int huff;   //非0即1
	struct node *pL;
	struct node *pR;
} huffnode;

huffnode *hnode[27];

//////////////////输入字符生成test.txt//////////////////////////
void creattesttxt()
{
	FILE *fp1;
	char ch;
	if((fp1=fopen("test.txt","w+"))==NULL)
	{
		cout<<"cannot open file!"<<endl;
			exit(0);
	}
	while((ch=fgetchar())!='\n')
	{
		fputc(ch,fp1);
	}
	fclose(fp1);
}

///////////////////////根据文本中该字符出现的次数排序////////////////////////////
void sort(huffnode *hnode[27])
{
	int i,j;
	huffnode *t; t=(huffnode*)malloc(sizeof(huffnode));//t是监视哨
	for(i=1;i<27;i++)
	 for(j=27-1;j>=i+1;j--)
	  if(hnode[j]->num>hnode[j-1]->num)
	  {
	  	  t=hnode[j];hnode[j]=hnode[j-1];hnode[j-1]=t;
	  }	  
}

/////////////////////////////////统计字符信息/////////////////////
void count()   
{
	FILE *fp1; 
	int j;
	for(j=1;j<27;j++) hnode[j]=(huffnode*)malloc(sizeof(huffnode));
	for(j=1;j<27;j++) hnode[j]->cha=(char)(96+j);
	for(j=1;j<27;j++) hnode[j]->num=0; 
	char ch; 
	fp1=fopen("test.txt","r");
	while(!feof(fp1))
	{	
		ch=(char)fgetc(fp1);
		for(j=97;j<123;j++)
			if(ch==char(j)) hnode[j-96]->num++;
	}
	for(j=1;j<27;j++)     //把所有的HUFF都赋值1是为了以后生成的文本
		hnode[j]->huff=1;
	fclose(fp1);
	sort(hnode);
}

/////////////////////////建立HUFFMAN树//////////////////////
huffnode *hufftree(huffnode *hnode[27]) 
{
	int i;
	huffnode *pts,*parent;
	huffnode *phead=(huffnode*)malloc(sizeof(huffnode));
	phead->huff=0;
	pts=parent=phead;
	for(i=1;i<27 && hnode[i]->num>0;i++)
	{
		pts->pR=hnode[i];
		pts->pL=(huffnode*)malloc(sizeof(huffnode));
		parent=pts;
		pts=pts->pL;
		pts->huff=0;
	}
	hnode[i-1]->huff=0;
	parent=hnode[i-1];
	parent->pL=NULL;
	parent->pR=NULL;
	return phead;
}


///////////////////////生成compare.txt/////////////////////////////

void creatcomparetxt()
{
	int i,j;
	hufftree(hnode);
	huffnode *xxx=hufftree(hnode);
	huffnode *pst;
	pst=xxx;
	xxx=xxx->pL;

	FILE *fp1;
	char ch;
	if((fp1=fopen("compare.txt","w+"))==NULL)
	{
		cout<<"cannot open file!"<<endl;
			exit(0);
	}

	for(i=1;i<27 && hnode[i]->num>0;i++)
	{
		ch=hnode[i]->cha;
		if(i==1) {
			fputc(ch,fp1);
			fputs("  ",fp1);
			fprintf(fp1,"%d",hnode[i]->huff);
			fputs("\n",fp1);
		}
		else
		{
			fprintf(fp1,"%c",ch);
			fputs("  ",fp1);
			for(j=0;j<i-1;j++)
			{
				pst=xxx;
				fprintf(fp1,"%d",pst->huff);
			}
			if(hnode[i]->huff)
				fprintf(fp1,"%d",hnode[i]->huff);
			fputs("\n",fp1);
		}
	}
	fclose(fp1);
}

///////////////////生成binary.txt//////////////////////////////
void creatbinarytxt()
{
	char ch1,ch2;
	hufftree(hnode);
	huffnode *xxx=hufftree(hnode);
	huffnode *pst;
	pst=xxx;
	xxx=xxx->pL;
	FILE *fp1,*fp2,*fp3;
		
	if((fp1=fopen("test.txt","r"))==NULL||(fp2=fopen("compare.txt","r"))==NULL||(fp3=fopen("binary.txt","w+"))==NULL)
	{
		cout<<"cannot open file!"<<endl;
			exit(0);
	}

	while(!feof(fp1))
	{
		ch1=(char)fgetc(fp1);
		rewind(fp2);
		while(!feof(fp2))
		{
			ch2=(char)fgetc(fp2);
			if(ch1==ch2)
			{
				while((ch2=(char)fgetc(fp2))!='\n' && !feof(fp2))
					if(ch2!=' ')
						fputc(ch2,fp3);
				break;
			}
		}	

	}
	fclose(fp1);
	fclose(fp2);
	fclose(fp3);
}

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

void main()
{
	creattesttxt();
	count();
	creatcomparetxt();
	creatbinarytxt();
}