huffman.cpp

实现最优二叉树的构造；在此基础上完成哈夫曼编码器与译码器。 假设报文中只会出现如下表所示的字符： 字符 A B C D E F G H I J K L M N 频度 186 64 13 22

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

#include "stdafx.h"
#include "Huffman.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>
#include <ctype.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Huffman::Huffman()
{

}

Huffman::~Huffman()
{

}

void Huffman::HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{  //  构造HuffmanTree,并求出n个字符的Huffman
   int m,s1,s2,start,f,c,i;
   HuffmanTree p;
   char *cd;

   if(n<=1) return ;
   m=2*n-1;
   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
   for(p=HT+1,i=1;i<=n;++i,++p) 
   {   
	   p->weight=w[i];   
	   p->lchild=0;   
	   p->rchild=0;  
	   p->parent=0;
   }
   for(;i<=m;++i,++p) 
   {   
	   p->weight=(unsigned)0;   p->lchild=0;   p->rchild=0;  p->parent=0;
   }
   for(i=n+1;i<=m;++i)
   {   //建Huffmantree;
       select(HT,i-1,s1,s2);
	   HT[s1].parent=i;      HT[s2].parent=i;   
	   HT[i].lchild=s1;      HT[i].rchild=s2;
	   HT[i].weight=HT[s1].weight+HT[s2].weight;
   }
   
   //---从叶子到根逆向求每个字符的Huffman code---
   HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
   cd=(char *)malloc(n*sizeof(char));  //分配求编码的工作空间
   cd[n-1]='\0';
   for(i=1;i<=n;++i)
   {
	   start = n-1;
	   for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		   if(HT[f].lchild==(unsigned)c) cd[--start]='0';
		   else cd[--start]='1';
	   HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
	   strcpy(HC[i],&cd[start]);
	 //  printf("%c,%3d,%s\n",C[i],W[i],&cd[start]);
   }
   free(cd);
}   //HuffmanCoding



void Huffman::select(HuffmanTree HT, int i, int &s1, int &s2)
{
	int a;

	for(a=1;a<=i;a++)
	{
		if(HT[a].parent==0) 
		{
			s1=a;
			a++;
			break;
		}
	}
	for(;a<=i;a++)
	{
		if(HT[a].parent==0) 
		{
			s2=a;
			a++;
			break;
		}
	}
	for(;a<=i;a++)
	{
		if(HT[a].parent==0)
			if(HT[a].weight<HT[s1].weight && HT[a].weight<HT[s2].weight)
			{
				if(HT[s1].weight<HT[s2].weight) 
					s2=a;
				else 
				{
					s1=s2; s2=a;
				};
			}
			else
				if(HT[a].weight<HT[s1].weight)
                {
					s1=s2; s2=a;
				}
				else
					if(HT[a].weight<HT[s2].weight)
						s2=a;

	}

}

Status Huffman::getweight()
{
    int i,w1[300];
	char ch[300];
    FILE *fp;

	if((fp=fopen("chars.txt","r"))==NULL)
	{
		printf("文件打开失败!");
		return FALSE;
	};
	i=1;
	while(!feof(fp))
	{
		fscanf(fp,"%c,%d\n",&ch[i],&w1[i++]);
	 // 	printf("%c %d\n",ch[i-1],w1[i-1]);
	}
	fclose(fp);
	W=(int *)malloc(i*sizeof(int));
    C=(char *)malloc(i*sizeof(char));

	N=i-1;
	for(i=1;i<=N;i++)
	{
		W[i]=w1[i];
		C[i]=ch[i];
	}
    return OK;
   
}//计算权值

void Huffman::init()
{
   getweight();//调用取得权值函数
}

void Huffman::writecodetable()
{
    FILE *fp;
	int i;

	if((fp=fopen("codetable.txt","w"))==NULL)
	{
		printf("代码表文件创建失败!");
		return ;
	};
     
	for(i=1;i<=N;i++)
	{
		fprintf(fp,"%c,%3d,%s\n",C[i],W[i],HC[i]);
        printf("%c,%3d,%s\n",C[i],W[i],HC[i]);
	}
	
	
	fclose(fp);
	//printf("%c, %d, %s\n",C[i],W[i],HC[i]);
}

void Huffman::txt2code()
{//打开文件
    FILE *fin,*fout;
    char ch,filename[32];
	int i;
    
	printf("待编码的文件名: ");
	gets(filename);
	if((fin=fopen(filename,"r"))==NULL)
	{
		printf("打开文件失败!");
		return ;
	};
	if((fout=fopen("hcode.txt","w"))==NULL)
	{
		printf("创建编码文件失败!");
		return ;
	};
    while(!feof(fin))
	{
		ch=toupper(fgetc(fin));
        i=1;
		while(i<=N && (C[i]!=ch))
			i++;

		if(i<=N)
			fprintf(fout,"%s",HC[i]);
		else
			fprintf(fout,"%s","@");
	};

    fclose(fout);
	fclose(fin);
}

void Huffman::code2txt()
{
    FILE *fin,*fout;
    char ch,code[20],filename[32];
	int i,j;
    
	printf("待译码的文件名: ");
	gets(filename);
	if((fin=fopen(filename,"r"))==NULL)
	{
		printf("打开文件失败!");
		return ;
	};
	if((fout=fopen("htxt.txt","w"))==NULL)
	{
		printf("创建明文文件失败!");
		return ;
	};
	ch=fgetc(fin);
    while(!feof(fin))
	{
		if(ch=='@')
            fprintf(fout,"@");
		else
		{
			i=0;
			while(ch!='@')
			{
				code[i]=ch;code[i+1]='\0';
				j=1;
				while(j<=N && strcmp(code,HC[j]))
					j++;
				if(j<=N)//
				{
					fprintf(fout,"%c",C[j]);
					break;
				}
				else
				{
					ch=fgetc(fin);
					i++;
				}
			}
		}
    	ch=fgetc(fin);
	};
	
    fclose(fout);
	fclose(fin);
}

int Huffman::display()
{//输入要打开的一个文件名并显示文件内容
	FILE *fp;
	int i=0;
	char filename[32];
	char L[256];
	cout<<"请输入文件名："<<endl;
	cin>>filename;
	if((fp=fopen(filename,"r"))==NULL)
	{
		cout<<"错误：无法打该开文件！"<<endl;
		return ERROR;
	}
	while(!feof(fp))
	{
		fgets(L,256,fp);
		cout<<" "<<L;	
	}
	return OK;

}//显示待编码的文件内容