huffman.cpp

哈夫曼编码,按字母或按单词的编码两种实现

#include <stdio.h>
#include <stdlib.h> 
#include <conio.h> 
#include <string.h> 
#include <malloc.h> 
#include <ctype.h>

#define MAX				80
#define MAX_Word        300
#define Char_MAX        20

typedef struct HTNode{
	unsigned int		weight;
	unsigned int		parent,lchild,rchild;
}HTNode,* HuffmanTree;        //-----哈夫曼树的节点类型----- 

typedef char *HuffmanCode;

typedef struct{
	char           ch;
	unsigned int   count;
	HuffmanCode    HC;
}Statistics;

typedef struct{
	char           ch[Char_MAX];
	unsigned int   count;
	HuffmanCode    HC;
}Statist;



void Count(FILE *fp, Statistics sta[MAX])                            //------统计文件中字符出现的次数------- 
{
	int t,r,i;                                   
	char ch;
	
	for(t=0;t<MAX;t++)                           //初始化统计数组
	{
		sta[t].count=0;
		sta[t].HC=NULL;
		if(t<26) sta[t].ch=t+97;
		else if(t<52) sta[t].ch=t+39;
		else if(t<62) sta[t].ch=t-4;
		else sta[t].ch=NULL;
	}

	if(fp==NULL)
	{
		printf("file doesn't exist,please check...\n");
    	exit (0);
	}	

	i=62;
	while((ch=fgetc(fp))!=EOF)
	{
		if(isalnum(ch))            //------------ch为字母或数字的时候------------------ 
		{
			if(ch>=97)t=ch-97;
			else if(ch>=65)t=ch-39;
			else t=ch+4;
			sta[t].count++;
		}
		else                     //-------------ch为标点符号时-------------------
		{   
			for(r=62;sta[r].ch!=ch&&r<i;r++);
			if(sta[r].ch==ch)sta[r].count++;
			else
			{
				sta[i].ch=ch;
				sta[i++].count++;
			}
		}
	}
	fclose(fp);
}

 
void Count_Word(FILE *fp, Statist sta[MAX_Word])                            //------统计文件中字符出现的次数------- 
{
	int t,r,i,q;                                   
	char buf[Char_MAX]={'\0'};
	char ch;
	
	for(t=0;t<MAX_Word;t++)                           //初始化统计数组
	{
		sta[t].count=0;
		sta[t].HC=NULL;
	}

	if(fp==NULL)
	{
		printf("file doesn't exist,please check...\n");
    	exit (0);
	}	
    
	i=0;r=0;t=0;
	while((ch=fgetc(fp))!=EOF)
	{
		
		if(isalpha(ch))            //------------ch为字母或数字的时候------------------ 
		{
			buf[i++]=ch;
		}
		else
		{
			if(buf[0]!='\0')
			{
				for(r=0;r<=t&&strcmp(sta[r].ch,buf);r++);         //t为已存的最后一个空间
				if(r<=t)sta[r].count++;
				else
				{
					strcpy(sta[++t].ch,buf);
					sta[t].count++;//t++;
				}
			}

			for(q=0;q<Char_MAX;q++)buf[q]='\0';

			buf[0]=ch;
			for(r=0;r<=t&&strcmp(sta[r].ch,buf);r++);
			if(r<=t)sta[r].count++;
			else
			{
				strcpy(sta[++t].ch,buf);
				sta[t].count++;
				for(q=0;q<Char_MAX;q++)buf[q]='\0';				
			}
			i=0;
		}
	}
	fclose(fp);
}


void Select(HuffmanTree HT,int end,int &s1,int &s2)
{                                                      //在0~END之间,找出最小和次小的两个结点序号,返回S1,S2
	int i;
    unsigned int min1=HT[0].weight;
	unsigned int min2=HT[0].weight;
	for (i=1;i<=end;i++)
	{                                                 //找最小的结点序号
		if (HT[i].parent==0&&HT[i].weight<min1)
		{ 
			s1=i;
			min1=HT[i].weight;
		}
	}
    for(i=1;i<=end;i++)
	{                                                 //找次小结点的序号
		if (HT[i].parent==0&&(s1!=i)&&min2>HT[i].weight)
		{
			s2=i;
			min2=HT[i].weight;
        }
    }
}




void HuffmanEncoding(HuffmanTree &HT,Statistics sta[])
{
	unsigned int c;
	int m,n,i,k,f,s1,s2,start;
	char * cd;
	HuffmanTree p;
	
    for(i=0,n=0;i<MAX;i++)
	{
		if(sta[i].count)n++;
	}
    
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(p=HT+1,i=1;i<=MAX;++i) 
	{
		if(sta[i-1].count)
		{
			p->weight=sta[i-1].count;
			p->parent=0;
			p->lchild=0;
			p->rchild=0;
			++p;
		}

	}
	for(;p<HT+m+1;p++)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;
	}
	HT[0].lchild=2*n-1;
	HT[0].rchild=0;

	cd=(char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	
	k=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==c) cd[--start]='0';
			else cd[--start]='1';
		}
		

		for(;!sta[k].count;k++);
		sta[k].HC=(char *)malloc((n-start)*sizeof(char));
		strcpy(&sta[k++].HC[0],&cd[start]);
	}
	free(cd);
}

  
void HuffmanEncodingWord(HuffmanTree &HT,Statist sta[MAX_Word])
{
	unsigned int c;
	int m,n,i,k,f,s1,s2,start;
	char * cd;
	HuffmanTree p;
	
    for(i=0,n=0;i<MAX_Word;i++)
	{
		if(sta[i].count)n++;
	}
    
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(p=HT+1,i=1;i<=MAX_Word;++i) 
	{
		if(sta[i-1].count)
		{
			p->weight=sta[i-1].count;
			p->parent=0;
			p->lchild=0;
			p->rchild=0;
			++p;
		}

	}
	for(;p<HT+m+1;p++)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;
	}
	HT[0].lchild=2*n-1;
	HT[0].rchild=0;

	cd=(char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	
	k=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==c) cd[--start]='0';
			else cd[--start]='1';
		}
		

		for(;!sta[k].count;k++);
		sta[k].HC=(char *)malloc((n-start)*sizeof(char));
		strcpy(&sta[k++].HC[0],&cd[start]);
	}
	free(cd);
}                                                



void PrintCodeList(Statistics sta[MAX])
{
	int i,j=1;
	char str[25];
	FILE *file;

	printf("Encode list is...\n\n\n");
	printf("Num      Char       Count        Encode...\n");
	for(i=0;i<MAX;i++)
	{
		if(sta[i].count)
		{

			printf("%-5d      %-5c        ",j++,sta[i].ch);  
			printf("%-5u        ",sta[i].count);
			printf("%-12s",sta[i].HC);
			printf("\n");
		}
	}
    printf("\n\nTotal chars:   %d\n",j-1); 

	printf("输入要保存字母编码表的文件...\n");
	scanf("%s",str);
	file=fopen(str,"w"); 
	fputs("Encoding list...:\n\n\n",file);
	fputs("No      Char        Count       Encode\n\n",file);
	for(i=0,j=0;i<MAX;i++)
	{		
		if(sta[i].count)fprintf(file,"%-10d%-10c%-10u%-10s\n",j++,sta[i].ch,sta[i].count,sta[i].HC);
		
	}
	fprintf(file,"\n\nTotal chars:   %d\n",j-1); 
		
	fclose(file);
	printf("CodeList print accomplished!!!\n");
}

void PrintCodeListWord(Statist sta[MAX_Word])
{
	int i,j;
	char str[25];
	FILE *file;

	printf("Encode list is...\n\n\n");                   
	printf("＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊  ＊ ＊ \n");
	printf("Num        Word                  Count         Encode\n");
	for(i=0,j=1;i<MAX_Word;i++)
	{
		if(sta[i].count)
		{

			printf("%-5d      %-15s        ",j++,sta[i].ch);  
			printf("%-5u        ",sta[i].count);
			printf("%-12s",sta[i].HC);
			printf("\n");
		}
	}

	printf("\n\nTotal Words: %d\n",--j);
	printf("＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊  ＊ ＊ \n");
		
	printf("输入要单词编码表的文件...\n");
	scanf("%s",str);
	file=fopen(str,"w"); 
	fputs("Encoding list...:\n\n\n",file);
	fputs("Num        Char        Count       Encode\n\n",file);
	for(i=0,j=1;i<MAX_Word;i++)
	{		
		if(sta[i].count)
		{
			fprintf(file,"%-10d%-15s%-10u%-15s\n",j++,sta[i].ch,sta[i].count,sta[i].HC);
		}
	}

	fprintf(file,"\n\nTotal Words: %d",--j);
	
	fclose(file);
	printf("CodeList print accomplished!!!\n");
}


void EncodeFileWord(FILE *fp,Statist sta[MAX_Word])
{                                               //将文章进行编码
	
	int r,i,q;                                    //参数传递存在问题
	char ch,str[25]; 
	char buf[Char_MAX]={'\0'};
	FILE *newf;
	if(fp==NULL)
	{
		printf("file doesn't exist,please check...\n");
    	exit (0);
	}


	printf("输入要保存字母编码文件地址...\n");
	scanf("%s",str);
	newf=fopen(str,"w");

	i=0;r=0;
	while((ch=fgetc(fp))!=EOF)
	{
		
		if(isalpha(ch))            //------------ch为字母或数字的时候------------------ 
		{
			buf[i++]=ch;
		}
		else
		{
			if(buf[0]!='\0')
			{
				for(r=0;r<MAX_Word&&strcmp(sta[r].ch,buf);r++);         //t为已存的最后一个空间
				printf("%s",sta[r].HC);
			    fputs(sta[r].HC,newf);
			}

			
			for(q=0;q<Char_MAX;q++)buf[q]='\0';

			buf[0]=ch;
			for(r=0;r<MAX_Word&&strcmp(sta[r].ch,buf);r++);
			printf("%s",sta[r].HC);
			fputs(sta[r].HC,newf);

			for(q=0;q<Char_MAX;q++)buf[q]='\0';				
			i=0;
		}
	}
	fclose(fp);
	fclose(newf);
	printf("\n\n\nFile Encode accompolished!!!\n");
}


void EncodeFile(FILE *fp,Statistics s[MAX])
{                                               //将文章进行编码
	
	int t,r;                                    //参数传递存在问题
	char ch,str[25];
	FILE *newf;

	
	if(fp==NULL)
	{
		printf("file doesn't exist,please check...\n");
    	exit (0);
	}

	
	printf("输入要保存字母编码的文件的地址...\n");
	scanf("%s",str);
	newf=fopen(str,"w");
    
	while((ch=fgetc(fp))!=EOF)
	{
		if(isalnum(ch))            //------------ch为字母或数字的时候------------------ 
		{
			if(ch>=97)t=ch-97;
			else if(ch>=65)t=ch-39;
			else t=ch+4;
			printf("%s",s[t].HC);
			fputs(s[t].HC,newf);
		}
		else                      //--------------ch为标点符号时---------------------- 
		{
			for(r=62;s[r].ch!=ch&&r<MAX;r++);
			if(s[r].ch==ch)
			{
				printf("%s",s[r].HC);
				fputs(s[r].HC,newf);

			}

		}
				
	}
	fclose(newf);
	fclose(fp);
    printf("\n\n\nFile Encode accompolished!!!\n");
}


void DecodeFile(HuffmanTree HT,Statistics sta[MAX])
{
	char ch;
	int p,i;
	char str[25];
	FILE *newf,*f;
	p=HT[0].lchild;

	printf("输入要解码的文件的地址...\n");
	scanf("%s",str);
	newf=fopen(str,"r");
	printf("输入要保存字母解码文件的地址...\n");
	scanf("%s",str);
	f=fopen(str,"w");
	
	if(newf==NULL)
	{
		printf("file doesn't exist,please check...\n");
    	exit (0);
	}
	

	while((ch=fgetc(newf))!=EOF)
	{
		p=(ch-48)?HT[p].rchild:HT[p].lchild;
		if(!HT[p].rchild)
		{
			for(i=0;p>0;i++)
			{
				if(sta[i].count)p--;
			}
			printf("%c",sta[i-1].ch);
			fputc(sta[i-1].ch,f);
			p=HT[0].lchild;
		}
	}
	fclose(f);
	fclose(newf);
	printf("\n\n\nFile Decode accompleted!!!\n");
}

void DecodeFileWord(HuffmanTree HT,Statist sta[MAX_Word])
{
	char ch,str[25];
	int p,i;
	FILE *newf,*f;
	p=HT[0].lchild;
	
	printf("输入要解码的文件的地址...\n");
	scanf("%s",str);
	newf=fopen(str,"r");
	printf("输入要保存字母解码文件的地址...\n");
	scanf("%s",str);
	f=fopen(str,"w");

	if(newf==NULL)
	{
		printf("file doesn't exist,please check...\n");
    	exit (0);
	}
	
	
	while((ch=fgetc(newf))!=EOF)
	{
		p=(ch-48)?HT[p].rchild:HT[p].lchild;
		if(!HT[p].rchild)
		{
			for(i=0;p>0;i++)
			{
				if(sta[i].count)p--;
			}
			printf("%s",sta[i-1].ch);
			fputs(sta[i-1].ch,f);
			p=HT[0].lchild;
		}
	}
	fclose(f);
	fclose(newf);
	printf("\n\n\nFile Decode accompleted!!!\n");
}

void  Begin()
{
	printf("＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊\n");
	printf("＊                      1 、  编码并查看编码列表                     ＊\n");
	printf("＊                      2 、  文章编码                               ＊\n");
    printf("＊                      3 、  文章解码                               ＊\n");
	printf("＊                      4 、  重新选择编码方式                       ＊\n");
	printf("＊                      5 、  版权信息                               ＊\n");
	printf("＊                      6 、  退出应用程序                           ＊\n");
	printf("＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊\n");
	printf("选择数字键切换功能:");
}


void CopyRight(){
	printf("＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊\n");
	printf("＊                  Copyright &copy 2008 data structure.             ＊\n");
	printf("＊                  电子信息科学与技术05-1  All rights reserved.     ＊\n");
	printf("＊                  数据结构课程设计                                 ＊\n");
	printf("＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊\n");
}




void main()
{
	FILE *fp;
	HuffmanTree HT=NULL;
	Statistics sta[MAX];
	Statist    statist[MAX_Word];
	char       string[25];
	int choice=1,i;
	

	printf("选择编码方式1 --按字母编码  0 --按单词编码\n");
	scanf("%d",&i);
	
	while(1)
	{
		Begin();
		scanf("%d",&choice);
						
		switch(choice)
		{
			case 1 :
				{
					printf("输入要编码的文件...\n");
					scanf("%s",string);
					fp=fopen(string,"r");
									
					if(i)
					{
						Count(fp,sta);
						HuffmanEncoding(HT,sta);
						PrintCodeList(sta);
					}
					else
					{
						Count_Word(fp,statist);
						HuffmanEncodingWord(HT,statist);
						PrintCodeListWord(statist);
					}
					break;
				}
			case 2 : 
				{
					fp=fopen(string,"r");
					if(i)EncodeFile(fp,sta);
					else EncodeFileWord(fp,statist);
					break;
				}
			case 3 :
				{
					if(i)DecodeFile(HT,sta);
					else DecodeFileWord(HT,statist);
					break;
				}
			case 4 :
				{
					printf("选择编码方式1 --按字母编码  0 --按单词编码\n");
	                scanf("%d",&i);                     break;
				}
			case 5 : CopyRight();                       break;
			case 6  : printf("谢谢使用!再见!");exit(0);
			default : printf("请正确选择切换1--6的功能");break;
		};
	}
}