huffman_full.cpp

实现huffman的算法 先输入一个文件 译码 输出译码后的文件

//------------------- 公用的常量和类型 ----------------------------
#include<stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
//函数结果状态代码
#define    TRUE    1
#define    FALSE    0
#define    OK        1
#define    ERROR    0
#define    INFEASIBLE    -1
#define    OVERFLOW    -2   
#define    UINT_MAX   1000 
typedef int    Status;    


/* 哈夫曼树和哈夫曼编码的存储表示 */
typedef struct HTNode
{
	char  leaf;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储哈夫曼编码表 */

typedef char **HuffmanCode; /* 动态分配数组存储哈夫曼编码表 */
typedef struct Node
{
	char leaf;
	unsigned  int weight;
	struct Node * next;
}LeafNode,*LeafLink;

typedef struct 
{
	LeafLink  head;
	unsigned  len;
}LeafLinkList;

int min1(HuffmanTree t,int i)
{ /* 函数void select()调用 */
	int j,flag;
	unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
	for(j=1;j<=i;j++)
		if(t[j].weight<k&&t[j].parent==0)
			k=t[j].weight,flag=j;
		t[flag].parent=1;
		return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1为最小的两个值中序号小的那个 */
	int j;
	*s1=min1(t,i);
	*s2=min1(t,i);
	if(*s1>*s2)
	{
		j=*s1;
		*s1=*s2;
		*s2=j;
	}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 算法6.12 */
{ /* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/
	int m,i,s1,s2,start;
	int n=L.len;
	unsigned c,f;
	LeafLink ptr;
	HuffmanTree p;
	char *cd;
	if(n<=1)
		return;
	m=2*n-1;
	printf("表长为%d\t哈夫曼树含节点数为%d\n",n,m);
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
	ptr=L.head->next;
	for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next)
	{
		(*p).leaf=ptr->leaf;
		printf("%d\t",(*p).leaf);
		(*p).weight=ptr->weight;
		printf("%d\n",(*p).weight);
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	for(;i<=m;++i,++p)
	{
		(*p).parent=0;
		(*p).leaf=0;
	}
	for(i=n+1;i<=m;++i) /* 建哈夫曼树 */
	{ /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
		select(HT,i-1,&s1,&s2);
		HT[s1].parent=HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	/* 从叶子到根逆向求每个字符的哈夫曼编码 */
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	/* 分配n个字符编码的头指针向量([0]不用) */
	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==c)
				cd[--start]='0';
			else
				cd[--start]='1';
			HC[i]=(char*)malloc((n-start)*sizeof(char));
			/* 为第i个字符编码分配空间 */
			strcpy(HC[i],&cd[start]); /* 从cd复制编码(串)到HC */
	}
	free(cd); /* 释放工作空间 */
	for(i=1;i<=n;i++)
	{
		printf("%c编码为%s:\n",HT[i].leaf,HC[i]);
	}
}


void InitLeafList(LeafLinkList &L)
{
	L.head=(LeafLink)malloc(sizeof(LeafLink));
	L.head->next=NULL;
	L.len=0;
}
void PrintList(LeafLinkList  L)
{
	LeafLink  p;
	p=L.head->next;
	printf("打印链表\n");
	printf("表长为%d\n",L.len);
	while(p!=NULL)
	{
		printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight);
		printf("打印一个节点\n");
		p=p->next;
	}
	printf("打印结束\n");
	printf("\n");
}

void EnLeafList(LeafLinkList &L,char ch)
{
    LeafLink  p,pre,temp;
	int flag=0;
    pre=p=L.head;
	printf("%d即为%c******\n\n",ch,ch);
	   if(p->next==NULL)    //p->next=NULL则为第一次插入操作
	   {
		   printf("第一次插入\n");
		   temp=(LeafLink)malloc(sizeof(LeafNode));
		   temp->leaf=ch;
		   temp->weight=1;
		   temp->next=NULL;
		   p->next=temp;
		   L.len++;
	   }
	   
	   else
	   {
		   
		   
		   p=p->next;
		   while(p!=NULL)
		   {
			   
			   if(ch==p->leaf) 
			   {
				   p->weight++; 
				   printf("加权\n");
				   p=NULL;
				   flag=1;
			   }                                 //权重加一
			   else if(ch<p->leaf)               //插入
			   { 
				   printf("插入A\n");
				   temp=(LeafLink)malloc(sizeof(LeafNode));
				   temp->leaf=ch;
				   temp->weight=1;
				   temp->next=p;
				   pre->next=temp;
				   L.len++;
				   flag=1;
				   p=NULL;
			   }
			   else                          //继续寻找插入点
			   {
				   pre=p;
				   p=p->next;
			   }
		   }
		   
		   if(p==NULL&&flag!=1)  //若p=NULL则插到链尾
		   {
			   printf("插入B\n");
			   temp=(LeafLink)malloc(sizeof(LeafNode));
			   temp->leaf=ch;
			   temp->weight=1;
			   temp->next=NULL;
			   pre->next=temp;
			   L.len++;
		   }	 
	   }
	   
}
void  EnCoding()
{
	FILE  *fp,*fr,*fc;
    HuffmanTree HT;
    HuffmanCode HC;
	int i,n;
    LeafLinkList   L;
	InitLeafList(L);
    char filename[15];
    char ch;
    printf("请输入文件名:\n ");
    scanf("%s",filename);
    if( !(fp=fopen(filename,"r")) )
	{
        printf("打开文件失败，请输入正确的文件名!! ");
        exit(0);
    }
	ch=getchar();             //接收执行scanf语句时最后输入的回车符
	printf("文件已经打开\n");
	while(!feof(fp)) 
	{
		
		ch=fgetc(fp);
		if(ch==-1)
		{
			printf("结束统计\n");
		}
		else
		{
			EnLeafList(L,ch);
		}
	}
	PrintList(L);
    HuffmanCoding(HT,HC, L);
	n=L.len;
	   for(i=1;i<=n;i++)
	   {
		   puts(HC[i]);
	   }
	   char TreeName[15];
	   printf("把哈夫曼树存入文件，请输入文件名:\n ");
       scanf("%s",TreeName);
	   if( !(fr=fopen(TreeName,"wb")) )
	   {
		   printf("打开文件失败，请输入正确的文件名!! ");
		   exit(0);
	   }
	   ch=getchar();     //接收执行scanf语句时最后输入的回车符
	   printf("文件已经打开\n");
	   //把哈夫曼树存入文件
	   printf("%d\n",n);
	   printf("把树的长度先存入\n");
	   putw(n,fr);      //把树的长度先存入
	   for(i=1;i<=2*n-1;i++)
		   if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)
			   printf("文件写入出错\n");	
		   fclose(fr);
		   
		   printf("打印原来的树\n");
		   for(i=1;i<=2*n-1;i++)
			   printf("%c %u  %u  %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild );
		   fclose(fr);
		   
		   printf("把编码结果存入文件，请输入文件名:\n ");
		   char CodeFileName[15];
		   scanf("%s",CodeFileName);
		   if( !(fc=fopen(CodeFileName,"wb")) )
		   {
			   printf("打开文件失败，请输入正确的文件名!! ");
			   exit(0);
		   }
		   ch=getchar();        //接收执行scanf语句时最后输入的回车符
		   
		   printf("待编码的文件位置指针重新指向开始位置\n");
		   printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n");
		   rewind(fp);    
		   while(!feof(fp)) 
		   {
			   
			   ch=fgetc(fp);
			   printf("%c\n",ch);
			   if(ch==-1)
			   {
				   printf("结束编码\n");
			   }
			   else
			   {
				   for(int tap=0,i=1;tap==0&&i<=n;)        //查找，该叶子对应的编码串
				   {
					   if(ch==HT[i].leaf)                   //找到，打印出对应的编码，并存入文件
					   {
						   printf("%s\n",HC[i]);
						   fputs(HC[i],fc);                   //将编码字符串存入文件
						   
						   tap=1;
					   }
					   else
					   {
						   i++;
					   }
				   } 
			   }
		   }
		   fclose(fp);    //关闭文件
		   fclose(fc);    //关闭文件
} 
int decode(FILE *fc,HuffmanTree HT,int n)
{
	while(!feof(fc))
	{
		char ch=fgetc(fc);
		if(ch=='0')
		{		
			n=HT[n].lchild;
			if(HT[n].leaf!=0) 
			{
				printf("%c",HT[n].leaf);
				return OK;
			}
			else
			{
				decode(fc,HT,n);
				return OK;
			}
		}
		else if(ch=='1')
		{
			
			n=HT[n].rchild;
			if(HT[n].leaf!=0)
			{
				printf("%c",HT[n].leaf);
				return OK;
			}
			else 
			{
				decode(fc,HT,n);
				return OK;
			} 
		}
		else return OK;
	}
	return ERROR;
}


void Decoding()                             //解码文件，并将结果显示出来
{
	   FILE *fc,*fr;
	   char CodeFileName[15],ch,TreeName[15];
	   int i;
       printf("解码文件，请输入文件名(如*.dat):\n ");
       scanf("%s",CodeFileName);
	   if( !(fc=fopen(CodeFileName,"r")) )
	   {
		   printf("打开文件失败，请输入正确的文件名!! ");
		   exit(0);
	   }
	   ch=getchar();     //接收执行scanf语句时最后输入的回车符
	   printf("存放编码结果文件已经打开\n");
	   
	   //读入哈夫曼树
	   
	   HuffmanTree HT;
	   printf("取出对应的哈夫曼树文件，请输入文件名,\n");
	   scanf("%s",TreeName);
	   if( !(fr=fopen(TreeName,"rb")) )         //打开存放哈夫曼树的文件
	   {
		   printf("打开文件失败，请输入正确的文件名!! ");
		   exit(0);
	   }
	   int  n=getw(fr);                  //将叶子数目取出
	   printf("叶子数目%d\n",n);
	   HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));           /* 然后分配空间，0号单元未用 */  
	   
	   for(i=1;i<=2*n-1;i++)
		   if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
			   printf("文件读出出错\n");
		   int length=2*n-1;     //总长度
		   printf("总结点数目为：%d\n",n);
		   printf("该文件译码后得到的源文件为：\n");
		   printf("**************************************\n");
		   while(!feof(fc))
		   {
			   decode(fc,HT,length);
		   }
		   printf("**************************************\n");
		   printf("\n\n");
}

int PreOrderPrint(HuffmanTree HT,int n,int count)
{
	if(HT[n].lchild)
	{
		for(int i=0;i<count;i++)
			printf("   ");
		printf("%u\n",HT[n].weight);
        if( PreOrderPrint(HT,HT[n].lchild, ++count) )
			if (PreOrderPrint(HT,HT[n].rchild, ++count))  
				return OK;
			return ERROR;
	}
	else return OK;
}
void PrintTree()
{
	//读入哈夫曼树
	FILE *fr;
	char TreeName[15];
	HuffmanTree HT;
	printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n");
	scanf("%s",TreeName);
	if( !(fr=fopen(TreeName,"rb")) )         //打开存放哈夫曼树的文件
	{
        printf("打开文件失败，请输入正确的文件名!! ");
        exit(0);
    }
	int  n=getw(fr);                  //将叶子数目取出
	printf("含叶子数%d\n",n);
	HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));           /* 然后分配空间，0号单元未用 */  
	
	for(int i=1;i<=2*n-1;i++)
		if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
			printf("文件读出出错\n");
		int	count=0;
		n=2*n-1;
		printf("总结点数目为；%d\n",n);
		printf("哈夫曼树的存储形式为：\n");
		for(i=1;i<=n;i++)
		{
			printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
		}
		printf("哈夫曼树的凹入表形式为：\n");
		PreOrderPrint(HT,n,count);
}
void PrintCodeFile()
{
	FILE *fc;
	printf("打印编码后的文件，请输入文件名(如*.dat):\n ");
	char CodeFileName[15];
	scanf("%s",CodeFileName);
	
	if( !(fc=fopen(CodeFileName,"r")) )
	{
        printf("打开文件失败，请输入正确的文件名!! ");
        exit(0);
    }
	
    char ch=getchar();     //接收执行scanf语句时最后输入的回车符
	printf("打印编码后的文件，打印方法一\n");
	int flag=1;
    while(!feof(fc)) 
	{
		
		ch=fgetc(fc);
		if(ch==-1)
		{
			printf("结束打印\n");
		}
		else
		{  
			printf("%c",ch);	
			if(flag<=49)
				flag++;
			else
			{
				flag=1;
				printf("\n");
			}
		}
	}
	printf("打印编码后的文件，打印方法二\n");
	rewind(fc);
	char str[50];
	while(!feof(fc)) 
	{
		fgets(str,51,fc);
		puts(str);
	}
    fclose(fc);        //关闭文件
}

void Initialization()                    //系统初始化
{
	printf("**************************************\n");
	printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*打印哈夫曼树请输入t\n*结束请输入q \n");
	printf("**************************************\n");
	printf("\n\n\t\t字符:\n\n\n");
	printf("**************************************\n");
	printf("* 输入一个字符:e,d,p,t or q *\n");
	printf("**************************************\n");
}

int read(char cmd)
{
	int i,flag=0;
	char choice[10]={'e','E','d','D','p','P','T','t','Q','q'};
    for(i=0;i<10;i++)
	{
		if(cmd==choice[i])  flag++;   
    }
	if(flag==1)     return FALSE;
	else return TRUE;
}
void ReadCommand(char &cmd)                   // 读入操作命令符
{
	do
	{ 
		cmd=getchar();
	}
	while(read(cmd));
}
void Interpret(char cmd)                     //解释执行操作命令
{
	switch(cmd)
	{
	case 'e':
	case'E':    
		EnCoding();
		Initialization();
		break;
    case 'd':
	case'D':      
		Decoding();
		Initialization();
		break;
    case 'p':
	case'P':    
		PrintCodeFile();
		Initialization();
		break;
	case't':
	case'T':
		PrintTree();              // Print();
		Initialization();
		break;
	case 'q': 
	case'Q':
		exit(0);
		break;
	default: 
		printf("Error\n");
		break;
	}
}
void main()         //用户驱式
{
	char cmd;
	Initialization();   //初始化
	do
	{
		ReadCommand(cmd);     //读入一个操作命令符
		Interpret(cmd);       //解释执行操作命令符
	}
	while(cmd!='q'&&cmd!='Q');
	EnCoding();
	Decoding();
	
}