huffman.cpp

数据结构测试程序

// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#include "Huffman.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Huffman::Huffman()
{

}

Huffman::~Huffman()
{

}

void Huffman::getweight()//pass
{
	FILE *in;
	char ch,file[10];
	printf("enter the file name to get weight\n");
	scanf("%s",file);
	if ((in=fopen(file,"r"))==NULL)
	{
		printf("cannot open file\n");
		return;
	}
	int i;
	for (i=1;i<=N;i++)
	{
		huftree[i].weight=0;
	}
	ch=fgetc(in);

	while (!feof(in))
	{
		huftree[ch-96].weight+=1;
	    ch=fgetc(in);
	}
	
	return;

}

void Huffman::select(int k)
{
	int j;
	int tag=0;

	for(j=1;j<=k;j++)
	{
		if (tag==1)
		{
			if((huftree[j].parent==0)&&(huftree[j].weight<huftree[s1].weight))
			s1=j;
		}

		else if (huftree[j].parent==0)
		{
			s1=j;
			tag=1;
		}
		
	}

	tag=0;

	for (j=1;j<=k;j++)
	{
		if (tag==1)
		{
			if((huftree[j].parent==0)&&(j!=s1)&&(huftree[j].weight<huftree[s2].weight))
			s2=j;
		}
		else if ((huftree[j].parent==0)&&(j!=s1))
		{
			s2=j;
			tag=1;
		}
	}
}



void Huffman::encoder()
{
	
	int i;
	for (i=1;i<=N;i++)
	{
		huftree[i].weight=i+96;
	}
//	int k=0;
	FILE *in;
	char ch,infile[10];
//	FILE *out;
//	char outfile[10];
	char get='y';//是否再做
	while (get=='y')
	fff:	{
	printf("enter the infile name:\n");
	
	scanf("%s",infile);
	if((in=fopen(infile,"r"))==NULL)
	{
		printf("cannot open %s\n",infile);
		return;
	}

	int f;
	f=M;
	ch=fgetc(in);
	while (ch!=EOF)
	{
		if (huftree[f].lch==0)
		{
			printf("%c",huftree[f].weight);
			f=M;
		}
		if (ch==48)
			f=huftree[f].lch;
		else f=huftree[f].rch;
		ch=fgetc(in);
	}

	printf("do you want to do it again(y..n)\n");
	scanf("%*%c",&get);
//	if (get=='y') goto fff;
	}
}



void Huffman::code()
{
	int i;
	int c,f;
	
	for (i=1;i<=M;i++)
	{
		huftree[i].parent=0;
		huftree[i].lch=0;
		huftree[i].rch=0;
	}

	for(i=N;i<=M;i++)
	{
		select(i-1);
		huftree[s1].parent=i;
		huftree[s2].parent=i;
		huftree[i].lch=s1;
		huftree[i].rch=s2;
		huftree[i].weight=huftree[s1].weight+huftree[s2].weight;
	}

	for (i=1;i<=N;i++)
	{
		cd.start=N;
		c=i;
		f=huftree[c].parent;
		while (f)
		{
			if(huftree[f].lch==c)
				cd.bits[cd.start]=0;
			else cd.bits[cd.start]=1;
			cd.start-=1;
			c=f;
			f=huftree[f].parent;
		}
		hufcode[i]=cd;
	}
}

void Huffman::outweight()//pass
{
	int i;
	for (i=1;i<=N;i++)
	{
		printf("%c %d  ",i+96,huftree[i].weight);
		printfcode(i);
		printf("    ");
		if (i%4==0)
			printf("\n");
	}
	printf("\n");

}

void Huffman::printfcode(int j,FILE *out)
{
	int i;
	for (i=hufcode[j].start+1;i<=N;i++)
	{fputc(hufcode[j].bits[i]+48,out);
	printf("%d",hufcode[j].bits[i]);}
}



void Huffman::outHuf()
{
	FILE *in,*out;
	char ch,file[10];
	char get='y';//是否再做
	while (get=='y')
	{
	printf("enter the file name to get code\n");
	scanf("%s",file);
	if ((in=fopen(file,"r"))==NULL)
	{
		printf("cannot open file%s\n",file);
		return;
	}

	printf("enter the file name to get code\n");
	scanf("%s",file);
	if ((out=fopen(file,"w"))==NULL)
	{
		printf("cannot open file%s\n",file);
		return;
	}

	ch=fgetc(in);
	while (!feof(in))
	{ 
		printfcode(ch-96,out);
		ch=fgetc(in);
	}

	printf("do you want to do it again(y..n)\n");
	scanf("%*%c",&get);
	}

	fclose(in);
	fclose(out);
	
	return;
}

void Huffman::printfcode(int j)
{
	int i;
	for (i=hufcode[j].start+1;i<=N;i++)
		printf("%d",hufcode[j].bits[i]);
}