huff.c

Huffman编解码完整代码

// 霍夫曼树_01051312杨富强.cpp : Defines the entry point for the console application.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


#define MAX_BUFFER 1024  //字符串最大长度
#define MAX_LEN 15   //单个字符的代码最大长度
#define MAX_PATH 80
#define TOKEN " \t\n\r"
#define DATA "fq.dat"


typedef struct lnode  //带权字符节点定义
{ char data;      //字符
  float info;    //权值
  struct lnode *lchild,*rchild,*parent;
} letter;//未建树之前用单链表存储(按权值由小到大,且parent指向下一节点)
 
typedef struct cnode  //已编码字符的节点定义
{ char data;         //字符
  char code[MAX_LEN];   //代码
  struct cnode *next;
} codenode;


letter *root=NULL;   //霍夫曼树的根节点
codenode *first=NULL;//已编码字符库(单链表)的头节点
codenode *q=NULL;    //已编码字符库(单链表)的活动节点
                     //以上三个全局变量所有函数都可引用


letter* GetInfo();   //将用户输入的带权字符,按权值由小到大建立单链表,返回头节点
void Insert(letter *p,letter *lnew);//将节点lnew按权值大小插入到链表p中
letter* CreateTree(letter *head);//将字符单链表head建立霍夫曼树,返回根节点
void MakeCode(letter *root);//为霍夫曼树root的所有叶子节点编码
void Translate(char *mess,int mode);//字符串与代码串互相翻译
void Operator(); //  



/*======================================================================*/
int main(int argc, char* argv[])
{
    letter *head=NULL;//未建树字符链表的头节点(不存字符)
    head=GetInfo();    //建立带权字符的单链表,要求用户输入带权字符
    root=CreateTree(head);//将带权字符的单链表head建立霍夫曼树
    first=(codenode*)malloc(sizeof(codenode));//已编码字符库(单链表)的头节点(不存字符)
	first->next=NULL;//初始化
    q=first;         //初始化
    MakeCode(root);  //编码
    q->next=NULL;

    //以下打印输出编码
    q=first->next;//因为头节点不存字符
    while(q)
    {  
       fprintf(stderr,"\n字符 %c 的代码是 %s",q->data,q->code);
       q=q->next;
	}
    fprintf(stderr,"\n=======================编码结束========================\n\n");

    Operator(); //以下解码或编码
    return 0;
}


letter* GetInfo()  //将用户输入的带权字符,按权值由小到大建立单链表,返回头节点
{ 
   letter *r,*pnew;//r为单链表头节点,pnew为新节点
   char buf[MAX_LEN]; 
   char * args[20];  // pointers to arg strings
   char ** arg;            // working pointer thru args   	
   FILE *openfile;

   r=(letter*)malloc(sizeof(letter));
   r->parent=NULL;    //初始化

   if( (openfile=fopen(DATA,"r"))==NULL )
   {
	    fprintf(stderr,"\nCannot open file: fq.txt \n");
	    exit(0);	 
   }
      
   while(!feof(openfile))
   { 
	  if (fgets(buf, MAX_BUFFER, openfile))
	  {  
             arg = args;
			 *arg++ = strtok(buf,TOKEN);   // tokenize input
             while ((*arg++ = strtok(NULL,TOKEN))); // last entry will be NULL 
             if(args[0]==NULL)
				 continue;
             pnew=(letter*)malloc(sizeof(letter)); //新建空节点

			 if(!strcmp(args[0],"\\1"))
			     pnew->data=' ';
			 else if(!strcmp(args[0],"\\t"))
                 pnew->data='\t';
             else if(!strcmp(args[0],"\\n"))
                 pnew->data='\n';
			 else if(!strcmp(args[0],"\\r"))
                 pnew->data='\r';
             else 			  
				 pnew->data=args[0][0];

			 pnew->info=(float)atof(args[1]) ; //带权字符
             pnew->lchild=NULL;
             pnew->rchild=NULL;
        	 pnew->parent=NULL;
             Insert(r,pnew);  //按权值大小插入单链表
	  }
   }
   fclose(openfile);
   return r;    //返回头节点
}


void Insert(letter *p,letter *lnew)//将节点lnew按权值大小插入到链表p中
{  
   while(p->parent)
   { 
      if(lnew->info<p->parent->info)//比较权值
	  { 
		lnew->parent=p->parent;
        p->parent=lnew;
        return;
	  }
      p=p->parent;
   }
   //若比所有节点权值大,插到尾部
      p->parent=lnew;
      lnew->parent=NULL;
      return;
} 



letter* CreateTree(letter *head)//将带权字符的单链表head建立霍夫曼树
{  letter *pnode=NULL;//指向子树根节点
   while(head->parent->parent)//当单链表中除头节点外只剩一个节点,建树完毕
   {
      pnode=(letter*)malloc(sizeof(letter));
      pnode->lchild=head->parent;
      pnode->rchild=head->parent->parent;
      head->parent=pnode->rchild->parent;//摘掉单链表的前两个节点,作为根节点的左右儿子
      pnode->info=pnode->lchild->info+pnode->rchild->info;
      pnode->lchild->parent=pnode->rchild->parent=pnode;
	  pnode->parent=NULL;
      Insert(head,pnode);//将子树根节点插入单链表
   }
   pnode=head->parent;
   return pnode;//返回根节点
}

void MakeCode(letter *p)//为霍夫曼树root的所有叶子节点编码
{  static char temp[MAX_LEN];//在函数递归调用过程中,都可使用其值
   static int top=-1;//在函数递归调用过程中,都可使用其值
   
   if(p->lchild)           //有左子树
   {   temp[++top]='0';    //入栈
       MakeCode(p->lchild);//递归
       temp[top]='1';      //修改栈顶
       MakeCode(p->rchild);//递归
       top--;              //退栈
   }
    else //无左子树,即为叶子节点
    {  q->next=(codenode*)malloc(sizeof(codenode));
	   q=q->next;
	   q->data=p->data;
//	   strset(q->code,0);//置空
	   q->code[0]=0;
       strncpy(q->code,temp,top+1);
	   q->code[top+1]=0;
    }//新建编码节点,并插到单链表中
    return;
}



void Translate(char *mess,int mode)//字符串与代码串互相翻译
{
  int i;
  char trans[MAX_BUFFER*MAX_LEN];
  codenode *q;
//  fprintf(stderr,"mark 1: mode=%d mess=%s### codes=%s### \n",mode,mess,codes); ///////////////////////////////////
  if(mode==0)//加密
  {  
	 trans[0]=0;
	 for(i=0;mess[i];i++)//扫描mess
     {  
		q=first->next; ///// 
        while(q)  //在编码链表中查找mess[i]
		{ 
		   if(q->data==mess[i])
			   break;//找到mess[i],退出查找
           q=q->next;
		}
        if (q)
			strcat(trans,q->code);//找到mess[i]
	    else //未找到mess[i]
		   fprintf(stderr,"原文包含未编码字符%c,程序将自动跳过\n",mess[i]);
     }
	 trans[strlen(trans)]=0;// end with '\0'
	 if(i==MAX_BUFFER-1)
		 fprintf(stderr,"原文太长,可能已经溢出!\n");
	 fprintf(stderr,"加密后的文字如下:\n");
  }

   else //解密
   {  
	  letter *p=root;//从根节点开始
      int j=-1;
      
	  if(p->lchild)
        for(i=0;mess[i];i++)  //扫描
		   {  
			  if(mess[i]=='0')
		         p=p->lchild; //深入左子树
              else if(mess[i]=='1')
				  p=p->rchild;//深入右子树
              else 
			  {
				 trans[++j]=mess[i];
                 p=root;//重新开始下一次深入查找
				 continue;
              }
			  
			  if(!p->lchild) //遇到叶子节点
			  {  
				 trans[++j]=p->data;
                 p=root;//重新开始下一次深入查找
			  }
		   }
	  else     //只有根节点
	      trans[++j]=p->data;

	  trans[++j]=0;
      if((p!=root)&&p->lchild)
		  fprintf(stderr,"\n密文结尾有误!");
	  if(i==MAX_BUFFER-1)
		  fprintf(stderr,"\n密文太长,可能已经溢出!");
      fprintf(stderr,"\n破译后的文字如下:\n");
   }

   fprintf(stdout,"%s",trans);
   fprintf(stderr,"\n");
}


void Operator()
{
    char ch,buffer[MAX_BUFFER],path[MAX_PATH];
    FILE *openfile;
    
    while(1)
    {  
	   fprintf(stderr,"\n解密（键盘输入）请按1, 加密（键盘输入）请按2,");
       fprintf(stderr," 破译文章请按3, 加密文章请按4，退出请按0: ");
	   ch=getchar();
	   getchar();  //    Strange !!!! 

	   switch(ch)
	   {
		  case '1':  
			        fprintf(stderr,"\n请输入代码串:\n");
		  case '2':
			        if(ch=='2')
						fprintf(stderr,"\n请输入字符串:\n");
		            gets(buffer);                    
                    Translate(buffer,ch%2);  //翻译
					break;
		  case '3':  
		  case '4':
			        fprintf(stderr,"\n请输入文件名:\n");
		            gets(path);
                    if((openfile=fopen(path,"r"))==NULL)
					{
                	    fprintf(stderr,"\nCannot open file: %s \n",path);
	                    break;	 
					}
                    while(!feof(openfile))
					{ 
                 	   if(fgets(buffer,MAX_BUFFER,openfile))                   
                          Translate(buffer,ch%2);  //翻译
					}
					fclose(openfile);
                    break;
		  case '0':
			       	fprintf(stderr,"\n===============退出==============\n\n");
			        exit(0);
          default:  
			        fprintf(stderr,"\n输入错误！\n\n");
	   }
	}
}