huffman.c

Huffman 编解码源程序 VC语言开发

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
#define MaxSize 65536

//定义缓冲区最大高度

#define CodeMaxLen 32

//定义Huffman编码最大长度

typedef struct HT

{

        char ch;

         unsigned long weight;

         struct HT *pre;

         struct HT *next;

         struct HT *parent;

         struct HT *LChild;

         struct HT *RChild;

}HuffmanTree,RateTabNode;//树结点，同时也是双链表结点

typedef struct

{

     char ch;//字符

     char code[CodeMaxLen];//字符的编码

}CodeNode;//存储字符的Huffman编码

typedef struct

{

     char ch;

     HuffmanTree *leaf;

}LeafNode;//临时存储叶子结点的地址

typedef struct

{

     char ch;

     unsigned long weight;

}OFinal;//最后写入文件的单元

 

void compress(FILE *,FILE*);//压缩

void decompress(FILE *,FILE*);//解压缩

/*********************统计字符权并编码************************/

RateTabNode *Probability(FILE *);//建立双链表

int IsExisted(RateTabNode *,char);//统计文本中字符个数

int SizeAssure(RateTabNode *);//返回双链表大小，即字符的总个数

HuffmanTree* HTCreate(RateTabNode *);//创建Huffman树

void FindLeaf(RateTabNode *,LeafNode *,int);//找出所有叶子并记录地址

void HFCoding(LeafNode *,CodeNode *,int);//从叶子到根，从下向上的进行编码左０　右１

void buf_init(char (*)[8],int);//缓冲初始化

void wbuffer(FILE *,CodeNode *,char (*)[8],int,int);//从文件读取字节

//void bufprintf(char (*)[8],int);//打印缓冲，测试用

void zip(FILE *,char (*)[8],int);//最终将压缩编码写入输出文件

RateTabNode *RebuildLink(OFinal *,int);//双链表重建，从结构体数组

/********************以下是解压缩相关函数**********************/

void deWbuffer(FILE *,char (*)[8],int);//读文件数据到缓冲

char CodeMatch(CodeNode *,int,char *);//编码字符串的匹配

void deRbuffer(FILE *,CodeNode *,int,char (*)[8],int);//从缓冲计数据，解码写入文件

void chstract(char *,char);//将字符加入字符串末尾

 

int main()

{

         FILE *ifp,*ofp,*ffp;

        char choic;

         char *ifilename,*ofilename;

         ifilename=(char *)malloc(255);

         ofilename=(char *)malloc(255);

        printf("a.压 缩\nb.解压缩\n");

        choic=getch();

        if(choic=='a')

        {

            printf("请输入(compress)源文件名:");

            scanf("%s",ifilename);

            printf("请输入(compress)输出文件名:");

            scanf("%s",ofilename);

           if((ifp=fopen(ifilename,"rb"))==NULL)

			
			if(ifp==NULL)

           {

               printf("无法打开文件!");

               getch();

               return 1;

           }

           if((ofp=fopen(ofilename,"wb"))==NULL)

            {

               printf("无法创建文件!");

               getch();

               return 1;

            }

           compress(ifp,ofp);

           printf("文件%s成功压缩为文件%s",ifilename,ofilename);

           fclose(ifp);

           fclose(ofp);

         }

        else

        {

            printf("请输入(decompress)源文件名:");

            scanf("%s",ifilename);

            printf("请输入(decompress)输出文件名:");

            scanf("%s",ofilename);

           if((ofp=fopen(ifilename,"rb"))==NULL)

            {

               printf("无法打开文件!");

               getch();

               return 1;

            }

           if((ffp=fopen(ofilename,"wb"))==NULL)

            {

               printf("无法创建文件!");

               getch();

               return 1;

            }

           decompress(ofp,ffp);

           printf("文件%s成功解压缩为文件%s!",ifilename,ofilename);

           fclose(ofp);

           fclose(ffp);

        }

        getch();

        return 0;

}

/*************************以下是压缩算法************************/

void compress(FILE *ifp,FILE *ofp)

{

         RateTabNode *head,*temp;

         HuffmanTree *root;

        signed ArraySize;

         int i=0;

         LeafNode *leafhead;//存储叶子结点的地址，利于编码

         CodeNode *codehead;//存储编码的数组首地址]

         OFinal *ofinalhead;//把原始的字符和权信息输出文件

         char buffer[MaxSize][8];//缓冲区，最大处理K数据

 

         buf_init(buffer,MaxSize);//初始化缓冲区

        head=Probability(ifp);//统计概率，建立双链表

         ArraySize=SizeAssure(head);//叶子个数

 

        ofinalhead=(OFinal *)malloc(ArraySize*sizeof(OFinal));

         for(i=0,temp=head;temp!=NULL;temp=temp->next,++i)

         {

              ofinalhead[i].ch=temp->ch;

              ofinalhead[i].weight=temp->weight;

         }

 

         root=HTCreate(head);//创建Huffman树，返回根结点

         

         leafhead=(LeafNode *)malloc(ArraySize*sizeof(LeafNode));

         codehead=(CodeNode *)malloc(ArraySize*sizeof(CodeNode));

         

         for(i=0;i<ArraySize;++i)

         {

              int j=0;

              for(j=0;j<CodeMaxLen;++j)

                   codehead[i].code[j]='#';

         }

         //初始化编码表全部为'#'

         FindLeaf(root,leafhead,ArraySize);//找出所有叶子结点，记录地址

         HFCoding(leafhead,codehead,ArraySize);//从叶子到根，从下向上进行编码

         /***********以上两个函数完成编码***********/

         

         for(i=0;i<ArraySize;++i)

         printf("\n%c\t%s",codehead[i].ch,codehead[i].code);

         

         fwrite(&ArraySize,sizeof(unsigned),1,ofp);//写入共有多少种字符

         fwrite(ofinalhead,sizeof(OFinal),ArraySize,ofp);//写入编码表，以便解压

 

         rewind(ifp);

         while(!feof(ifp))

         {

             wbuffer(ifp,codehead,buffer,MaxSize,ArraySize);//读文件二进制，转换为或写入缓冲

              zip(ofp,buffer,MaxSize);//转换成编码输出

              if(feof(ifp))break;

         }

}

RateTabNode *Probability(FILE *ifp)//对字符作分类并统计数量(权)

{

         char temp;

         RateTabNode *head,*p,*q;

         

         q=(RateTabNode *)malloc(sizeof(RateTabNode));

         head=p=q;

         q->next=NULL;

         head->pre=NULL;

         head->LChild=head->RChild=NULL;

         q->ch=temp=fgetc(ifp);

         q->weight=0;

         

         while(!feof(ifp))

         {

              

              if(!IsExisted(head,temp))//如果存在temp字符，则权加(IsExisted函数中);不存在，创建新结点

              {

                   q=(RateTabNode *)malloc(sizeof(RateTabNode));

                   p->next=q;

                   q->pre=p;

                   p=q;

                   p->next=NULL;

                   p->LChild=p->RChild=NULL;

                   

                   p->ch=temp;

                   p->weight=1;

              }

              temp=fgetc(ifp);

         }

         return head;

}

int IsExisted(RateTabNode *head,char ch)//判断当前双链表中是否有ch字符，若有则数量加并返回真，否则返回假

{

         RateTabNode *temp=head;

         while(temp!=NULL)

         {

              if(ch==temp->ch)

              {

                   ++temp->weight;

                   return 1;

              }

              temp=temp->next;

         }

         return 0;

}

 

int SizeAssure(RateTabNode *head)//测链表长度，即字符的种类数

{

     RateTabNode *temp;

     int num=1;

     temp=head;

     

     while(temp->next!=NULL)

     {

         ++num;

         if(temp->next==NULL)break;

         temp=temp->next;

     }

     return num;

}

 

void wbuffer(FILE *ifp,CodeNode *codehead,char (*buffer)[8],int size,int ArraySize)//将字符用编码替换，写入缓冲

{

     char temp;

     int i=0;

     signed long offset=0;

 

     buf_init(buffer,MaxSize);

     while(!feof(ifp)&&offset<8*size)

     {

        if(feof(ifp))break;

       temp=fgetc(ifp);

        

        for(i=0;i<ArraySize;++i)

         {

              int k=0;

              if(temp==codehead[i].ch)

              {

                   for(k=0;k<CodeMaxLen;++k)

                       if(codehead[i].code[k]!='#'&&codehead[i].code[k]!='\0')//不要忘记还有个'\0'

                       {

                            if(offset==8*size)break;

                            *(*buffer+offset)=codehead[i].code[k];

                            ++offset;

                       }

              }

         }

     }

}

/*void bufprintf(char (*buffer)[8],int size)

{

     int i,j;

     for(i=0;i<size;++i)

     {

         for(j=0;j<8;++j)

              printf("%d",buffer[i][j]);

         printf("\n");

     }

}*/

 

void zip(FILE *ofp,char (*buffer)[8],int size)//写缓冲到文件

{

     int i=0,j=0;

     

     while(i<size)

     {

          char temp=0;

          for(j=0;j<8&&buffer[i][j]!=-1;++j)

          {

               if(buffer[i][j]==-1)break;

               temp+=(buffer[i][j]-48)<<(7-j);

          }