code.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 *fp,*outp,*huffcodep,*dep;
int AllCount=0;
int Index;
int n;
node stable[MAX];
HuffmanTree HT;
HuffmanCode HC;

int lookup(char s)
{
    int p;
    for(p=0;p<AllCount;p++)
        if(stable[p].data==s)
        return p;
    return -1;
}

int lexan()
{
    char t;
    int i=0;
    t = fgetc(fp); n=1;
        while(!feof(fp))
        { 
            if(i==0)
            {
                stable[i].data=t;
                stable[i].num=1;
                AllCount++;
                i++;
            }
            else
            {
                Index=lookup(t);
                if(Index==-1)
                {
                    stable[i].data=t;
                    stable[i].num=1;
                    AllCount++;
                    i++;
                }
                else
                   stable[Index].num++;
            }
            t=fgetc(fp);
            n++;
        }
    return AllCount;
}

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;
    char t;
    huffcodep=fopen("huffman.txt","wb");
    outp=fopen("output.txt","wb");
    if((fp=fopen("input.txt","r"))==NULL)
        printf("Can not open input.txt! \n");
    else
    {
        lexan();
        HuffmanCoding(&HT,&HC,&stable,AllCount);
        printf("See output.txt for code!\nSee huffman.txt for finally code!");
        for(i=0;i<AllCount;i++)
        {
           fwrite(&stable[i], sizeof(node), 1, huffcodep);
            fprintf(outp,"%c    ",stable[i].data);
            fprintf(outp,"%d    ",stable[i].num);
            fprintf(outp,"%s    ",HC[i+1]);
        }
        rewind(fp);
        rewind(huffcodep);
        fseek(huffcodep,1000L,0);
        fprintf(huffcodep,"%d",AllCount);
        rewind(fp);
        fseek(huffcodep,1010L,0);
        t=fgetc(fp);
        for(i=0;i<k;i++)
        {
            for(j=0;j<AllCount;j++)
            {
               if(t==stable[j].data)
                {
               fprintf(huffcodep,"%s",HC[j+1]);}
           }
           t=fgetc(fp);
       }
    }
    getch();
    fclose(fp);
    fclose(outp);
}