decode.c

huffman的压缩与解压程序

/*****************************/
/*  huffman编码实现数据压缩  */
/*        软件学院           */
/*        软件四班           */
/*        学号：1023710411   */
/*        姓名：王磊         */
/*****************************/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAX 256


typedef struct
{
    char data;
    int num;
}node;

typedef struct
{
    char HTData;
    int Weight;
    int Parent;
    int lChild;
    int rChild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

FILE *dep,*outp;
int AllCount=0;
int n;
node stable[MAX];
HuffmanTree HT;
HuffmanCode HC;

void Select(HuffmanTree HT,int Count,int *s1,int *s2)
{
    int i;
    unsigned int temp1=0;
    unsigned int temp2=0;
    unsigned int temp3;
    for(i=1;i<=Count;i++)
    {
        if(HT[i].Parent==0)
        {
            if(temp1==0)
            {
                temp1=HT[i].Weight;
                (*s1)=i;
            }
            else
            {
                if(temp2==0)
                {
                    temp2=HT[i].Weight;
                    (*s2)=i;
                    if(temp2<temp1)
                    {
                        temp3=temp2;
                        temp2=temp1;
                        temp1=temp3;

                        temp3=(*s2);
                        (*s2)=(*s1);
                        (*s1)=temp3;
                    }
                }
                else
                {
                    if(HT[i].Weight<temp1)
                    {
                        temp2=temp1;
                        temp1=HT[i].Weight;

                        (*s2)=(*s1);
                        (*s1)=i;
                    }
                    if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
                    {
                        temp2=HT[i].Weight;
                        (*s2)=i;
                    }
                }
            }
        }
    }
}

void HuffmanCoding(HuffmanTree *HT,
                 HuffmanCode *HC,
                 node *stable,
                 int Count)
{
    int i,j;
    int s1,s2;
    int TotalLength;
    char* cd;
    int c;
    int f;
    int start;

    if(Count<=1) return;
    TotalLength=Count*2-1;
    (*HT)=(HuffmanTree)malloc((TotalLength+1)*sizeof(HTNode));

    for(i=1;i<=Count;i++)
    {
        (*HT)[i].HTData=stable[i-1].data;
        (*HT)[i].Parent=0;
        (*HT)[i].rChild=0;
        (*HT)[i].lChild=0;
        (*HT)[i].Weight=stable[i-1].num;
    }
    for(i=Count+1;i<=TotalLength;i++)
    {
        (*HT)[i].HTData='';
        (*HT)[i].Weight=0;
        (*HT)[i].Parent=0;
        (*HT)[i].lChild=0;
        (*HT)[i].rChild=0; 
    }


    for(i=Count+1;i<=TotalLength;++i)
    {
       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;
    }


    (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
    cd=(char*)malloc(Count*sizeof(char));
    cd[Count-1]='\0';
    for(i=1;i<=Count;++i)
    {
        start=Count-1;

        for(c=i,f=(*HT)[i].Parent;f!=NULL;c=f,f=(*HT)[f].Parent)
        {
            if((*HT)[f].lChild==c)
                cd[--start]='0';
            else
                cd[--start]='1';
            (*HC)[i]=(char*)malloc((Count-start)*sizeof(char));
            strcpy((*HC)[i],&cd[start]);
        }

    }

}

void main()
{
    int i,j,k,p,q,a,b;
    char t;
    outp=fopen("report.txt","a+");
    if((dep=fopen("huffman.txt","rb"))==NULL)
        printf("Can not open huffman.txt! \n");
    else
    {
        fseek(dep,1000L,0);
        fscanf(dep,"%d",&AllCount);
        rewind(dep);
        for(i=0;i<AllCount;i++)
           fread(&stable[i], sizeof(node), 1, dep);
        HuffmanCoding(&HT,&HC,&stable,AllCount);
        rewind(dep);
        fseek(dep,1010L,0);
        t=fgetc(dep);
        for(a=1,q=HT[1].Parent;q!=0;a=q,q=HT[q].Parent){}
        q=p=a;
        while(!feof(dep))
        {
            if(t=='0')
                {p=q;q=HT[p].lChild;}
            else
                {p=q;q=HT[p].rChild;}
            if(HT[q].HTData!='')
                {fprintf(outp,"%c",HT[q].HTData);q=p=a;}
            t=fgetc(dep);
        }
    }
    printf("See report.txt for detail!");
    getch();
    fclose(dep);
    fclose(outp);
}