用哈夫曼树实现文本文件的压缩与解压缩.txt

采用哈夫曼编码思想实现某个文件的压缩和解压缩功能,并提供压缩前后的文件占用空间之比．要求：(1)压缩前文件的规模应不小于５Ｋ．(2)提供原文件与压缩后文件的相同性比较功能．

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAX_SINGLECODE_LEN 10        //单个字符最大码长
#define MAX_STRING_LEN 1000            //要编码的字符串的最大长度
#define MAX_CODESTRING_LEN 50000             //产生的二进制码的最大长度
#define MAX_WORDS 1000            //要编码的字符串中字符种数最大值
#define END_TREE 30000            //树部分存储的结束符
#define PATH_LEN 50            //路径串最大长度
typedef struct Huffmantree    //哈夫曼树结构定义
{   char ch;                //字符部分
    int weight;                //结点权值
    int    mark;                //标记是否加入树中
    struct Huffmantree *parent,*lchild,*rchild,*next;
}HTNode,*LinkTree;
typedef struct     //编码字典结构定义
{   char ch;                //字符部分
    char code[MAX_SINGLECODE_LEN];    //编码部分
}CodeDictionary;
LinkTree setWeight(char *string)
{   int i=0;                                    //文件字符串下标
    LinkTree tree;                                //头指针
    LinkTree ptr,beforeptr;                        //创建指针与其前驱
    HTNode *node;
    if((tree=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建链表的头结点
        return NULL;
    tree->next=NULL;
     for(i=0;string[i]!='\0';i++)
    {    ptr=tree;
        beforeptr=tree;
         if((node=(HTNode *)malloc(sizeof(HTNode)))==NULL)    return NULL;
         node->next=NULL; node->parent=NULL;node->lchild=NULL;node->rchild=NULL;
       node->mark=0;node->ch=string[i];node->weight=1;
        if(tree->next==NULL)                    //如果是第一个非头结点
            tree->next=node;
        else
        {    ptr=tree->next;
            while(ptr&&ptr->ch!=node->ch)        //查找相同字符
            {     ptr=ptr->next;beforeptr=beforeptr->next; }
            if(ptr&&ptr->ch==node->ch)            //如果链表中某结点的字符与新结点的字符相同
            {    ptr->weight++;  free(node);  }                  //将该结点的权加一  
         else                                //将新结点插入链表后
            {     node->next=beforeptr->next; beforeptr->next=node;}
        }
    }
    return tree;                                //返回头指针
}
LinkTree sortNode(LinkTree tree)
{    LinkTree head,ph,beforeph,pt;                      //创建指针及其前驱
     if((head=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建新链表的头结点
        return NULL;
    head->next=NULL; ph=head; beforeph=head;
     while(tree->next)
    {     pt=tree->next;                            //取被操作链表的头结点
        tree->next=pt->next;
        pt->next=NULL;
         ph=head->next;
        beforeph=head;
         if(head->next==NULL)
            head->next=pt;                        //创建当前操作链表头结点
        else
        {   while(ph&&ph->weight<pt->weight)    //将被操作结点插入相应位置
            {    ph=ph->next;
                beforeph=beforeph->next;
            }
            pt->next=beforeph->next;
            beforeph->next=pt;
        }
    }
    free(tree);return head;  //返回排序后的头指针
}
LinkTree createHTree(LinkTree tree)
{   LinkTree p,q,beforep;
    HTNode *newnode;
     for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next)
                                                //p、q初值为头结点后的两个结点，即最小权结点
	 {   tree->next=q->next;q->next=NULL;  p->next=NULL;
        if((newnode=(HTNode *)malloc(sizeof(HTNode)))==NULL)  ////申请新结点作为中间结点
        return NULL;
        newnode->next=NULL; newnode->mark=0;
        newnode->lchild=p; newnode->rchild=q;//取链表头结点后的两个结点作为新结点的左、右孩子
         newnode->weight=p->weight+q->weight;    //权值相加
         p=tree->next; beforep=tree;
       if(p!=NULL&&p->weight>=newnode->weight)
        {    newnode->next=beforep->next;        //将新结点插入原链表的相应位置
            beforep->next=newnode;    
        }
        else
        {  while(p!=NULL&&p->weight<newnode->weight)
            {    p=p->next;
                beforep=beforep->next;
            }
            newnode->next=beforep->next;
            beforep->next=newnode;
        }
    }
    return (tree->next);
}
void codeHTree(LinkTree tree,CodeDictionary *codedictionary)
{   int index=0,k=0;
    char code[MAX_SINGLECODE_LEN];                //用于统计每个字符的哈夫曼编码
    LinkTree ptr=tree;                            //从树的根结点开始
     if(ptr==NULL)
    { printf("要压缩的文件是空的!\\n");
        exit(0);
    }
    else
    {  while(ptr->lchild&&ptr->rchild&&ptr->mark==0)
	{    while(ptr->lchild&&ptr->lchild->mark==0)
            { code[index++]='0';                //左支路编码为0
                ptr=ptr->lchild;
                if(!ptr->lchild&&!ptr->rchild)    //如果没有左右孩子，即叶子结点
                { ptr->mark=1;                //作标记，表明该字符已被编码
                    code[index]='\0';            //编码0-1字符串结束
                    codedictionary[k].ch=ptr->ch;//给字典赋字符值
                    for(index=0;code[index]!='\0';index++)
                        codedictionary[k].code[index]=code[index];//给字典赋码值
                    codedictionary[k].code[index]='\0';
                    k++;ptr=tree;index=0;
                 }
            }
            if(ptr->rchild&&ptr->rchild->mark==0)
            {    ptr=ptr->rchild;     
                code[index++]='1';                           
            }
            if(!ptr->lchild&&!ptr->rchild)        //如果没有左右孩子，即叶子结点
            {    ptr->mark=1;
                code[index++]='\0';
                codedictionary[k].ch=ptr->ch;    //给字典赋字符值
                for(index=0;code[index]!='\0';index++)
                    codedictionary[k].code[index]=code[index];//给字典赋码值
                codedictionary[k].code[index]='\0';
                k++;ptr=tree;index=0;
             }
            if(ptr->lchild->mark==1&&ptr->rchild->mark==1)//如果左右孩子都已标记
            {   ptr->mark=1;ptr=tree;index=0;
            }
        }
    }
    printf("\n");
}
void decodeHTree(LinkTree tree,char *code,char *filestring)
{    int i=0,j=0,k=0;
    char *char0_1;
    LinkTree ptr=tree;
    char0_1=(char *)malloc(MAX_SINGLECODE_LEN);    //此数组用于统计输入的0-1序列
     printf("预览解压后的字符：\n");
    for(j=0,ptr=tree;code!='\0'&&ptr->lchild&&ptr->rchild;j=0,ptr=tree)
    {    for(j=0;code[i]!='\0'&&ptr->lchild&&ptr->rchild;j++,i++)
        {  if(code[i]=='0')
            {     ptr=ptr->lchild; char0_1[j]='0';  }
            if(code[i]=='1')
            {   ptr=ptr->rchild;char0_1[j]='1';}
        }                        
        if(!ptr->lchild&&!ptr->rchild)
        {   printf("%c",ptr->ch);                //显示解压后的字符
            filestring[k++]=ptr->ch;            //将字符逐一保存到字符串里
        }
        if(code[i]=='\0'&&ptr->lchild&&ptr->rchild)
        {    char0_1[j]='\0';
            printf("\n没有与最后的几个0-1序列：%s相匹配的字符!\n",char0_1);
            return;
        }
    }
    printf("\n\n");filestring[k]='\0';free(char0_1);
}
void deleteNode(LinkTree tree)
{    LinkTree ptr=tree;
    if(ptr)    {     deleteNode(ptr->lchild);deleteNode(ptr->rchild);free(ptr);}
}
void compressString(char *string,CodeDictionary *codedictionary,char *codestring)
{   int i=0,j=0,k=0,m;
    while(string[i])                            //整个文件字符串没结束时
	  {   while(string[i]!=codedictionary[j].ch&&j<MAX_WORDS)   //找与对应字符相同的字符
            j++;
        if(string[i]==codedictionary[j].ch)       //如果找到与对应字符相同的字符
            for(m=0;codedictionary[j].code[m];m++,k++)
                codestring[k]=codedictionary[j].code[m];
        j=0;   i++;                                 //字典复位
    }
    codestring[k]='\0';
}
void readFile(char *string)
{   FILE *fp;
    int i;
    char ch,path[PATH_LEN];                   //记录读入的字符及文本文件的读路径
    printf("请输入要压缩的文本文件地址：（无需扩展名）");
    gets(path);
    if((fp=fopen(strcat(path,".txt"),"r"))==NULL)
    {   printf("\n路径不正确！\n");getch(); return;}
    ch=fgetc(fp);
    for(i=0;ch!=EOF;i++)
    {   string[i]=ch;ch=fgetc(fp);}
    string[i]='\0';fclose(fp);
    }
void writeCode(LinkTree tree,char *string)
{   FILE *fp;
    int i,j=0,weight;                                     //记录写入的权值
    char ch;                                    //记录写入的字符
    LinkTree p;
    char path[PATH_LEN];                        //0-1码文件的写路径
    printf("请输入压缩后的保存路径及文件名：（无需扩展名）");
    gets(path);
    if((fp=fopen(strcat(path,".yxy"),"w+"))==NULL)
    {   printf("\n文件路径出错！\n");getch();return;}
    p=tree->next;
    do
    {   ch=p->ch;weight=p->weight;
        fprintf(fp,"%c%d",ch,weight); p=p->next;
     }while(p);
    fprintf(fp,"%c%d",'^',END_TREE);
    fseek(fp,sizeof(char),1);                    //空出区分位
    for(i=0;string[i];i++)
    {   ch=string[i];fputc(ch,fp);}
    printf("\n压缩成功！\n");getch();fclose(fp);
}
void readCode(LinkTree tree,char *string)
{   FILE *fp;
    int i=0,weight;   //记录读入的权值                                   
    char ch;                                    //记录读入的字符
	unsigned char ch1;
    LinkTree ptr,beforeptr;
    char path[PATH_LEN];                        //0-1码文件的读路径
    printf("请输入要解压的文件路径及文件名：（无需扩展名）"); gets(path);
    if((fp=fopen(strcat(path,".yxy"),"r"))==NULL)
    { printf("\n文件路径出错！\n");getch(); return;}
    beforeptr=tree;
    fscanf(fp,"%c%d",&ch,&weight);
    while(weight!=END_TREE)
    {   if((ptr=(LinkTree)malloc(sizeof(HTNode)))==NULL)
        {  printf("内存不足！");getch();exit(1); }
        ptr->ch=ch;ptr->weight=weight;ptr->lchild=NULL;
        ptr->rchild=NULL;ptr->mark=0;
        beforeptr->next=ptr;beforeptr=ptr;
        fscanf(fp,"%c%d",&ch,&weight);
    }
    beforeptr->next=NULL;
     fseek(fp,sizeof(char),1);                    //文件指针定位
    ch1=fgetc(fp);
    for(i=0;ch!=EOF;i++)
    {   string[i]=ch;ch=fgetc(fp); }
    string='\0';fclose(fp);
}
void writeFile(char *string)
{   FILE *fp; char ch; int i;
    char path[PATH_LEN];                        //文本文件的写路径
    printf("请输入解压后的保存路径及文件名：（无需扩展名）");gets(path);
    if((fp=fopen(strcat(path,".txt"),"w+"))==NULL)
    {   printf("\n文件路径出错！\n");getch();return;}
   for(i=0;string;i++)
	{    ch=string[i];fputc(ch,fp); }
         printf("\n解压成功！\n");getch();fclose(fp);
}
void menu()
{   printf("\n\n\n\n\t\t -****   欢迎使用WINYXY压缩工具 ****--");
    printf("\n\n\n\t\t\t\t<a> 压 缩\n\t\t\t\t<b> 解 压\n\t\t\t\t<c> 退 出\n\n");
    printf("请按键选择：\n");
}
void main(void)
{   char choice;            //菜单选择变量
    char string[MAX_STRING_LEN];    //保存从文件中读取的内容
    LinkTree temp,ht,htcopy,tempcopy, htree;//保存赋了权值的表,排序后的表,表备份,保存哈夫曼树
    LinkTree ptr=NULL;
    CodeDictionary codedictionary[MAX_WORDS];//编码字典
    char codestring[MAX_CODESTRING_LEN];    //保存0-1形的代码串     
    char codestring2[MAX_CODESTRING_LEN];//保存0-1形的代码串
    LinkTree ht2,  htree2;          //保存读取的树,保存排序后的表
    char filestring[MAX_STRING_LEN];    //解码后要写入文件中的内容
    if((ht2=(LinkTree)malloc(sizeof(HTNode)))==NULL)//创建链表的头结点
    {  printf("内存不足！");getch();exit(0);}
    ht2->next=NULL;
     while(1)
	 {   menu();  choice=getch();          //调入主菜单,读入用户选项
        switch(choice)        //判断用户选择
        {   case 'a':
            case 'A':
                printf("您选择了压缩文件模式:");
                readFile(string);    //读取要编码的文件（字符串）
                temp=setWeight(string);            //得到有权值的表
                tempcopy=setWeight(string);
                ht=sortNode(temp);                //按权值排序后的表
                htcopy=sortNode(tempcopy);        //用于记录解码树
                htree=createHTree(ht);            //得到哈夫曼树
                codeHTree(htree,codedictionary);//哈夫曼编码
                compressString(string,codedictionary,codestring);//压缩为0-1码
                writeCode(htcopy,codestring);    //将解码树和0-1码保存                
                deleteNode(htree);                //释放空间*/
                break;
            case 'b':
            case 'B':
                printf("您选择了解压缩文件模式:");
                readCode(ht2,codestring2);        //读取要解码的0-1码
                htree2=createHTree(ht2);        //得到哈夫曼树
                codeHTree(htree2,codedictionary);//哈夫曼编码
                decodeHTree(htree2,codestring2,filestring); //解码
                writeFile(filestring);            //将解码文件保存
                deleteNode(htree2);                //释放空间
                break;
            case 'c':
            case 'C':
				printf("您已安全退出！\n");
                exit(0);                        //退出程序
        }
    }
}