compress.c

此为压缩与解压缩程序的文本文件,里面是用C语言编写的程序源代码.此程序运用了huffman树的思想

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

//在dos下运行！“程序/附件/命令提示符 ” 
typedef struct  
{
   unsigned long  weight;
   short left, right, parent;
   unsigned short bit_code;       
   short code_length;
}hufnode;

hufnode huftree[511];

FILE*infile,*outfile;
unsigned long total;
short root_pos;
char *infile_name;
char outfile_name[20];

int main(int argc, char *argv[])
{
    infile_name=argv[1];//给要读入文件名赋值，因为是指针所以直接赋 
    strcpy(outfile_name,argv[2]);//给要输出的文件名赋值，因为是一般字符型，所以要调用字符串复制函数 
    
    void create_huftree();
    short searchroot_pos();
    void create_code(short);
    void output_bits(unsigned short,short);
    
    if((infile=fopen(infile_name,"rb"))==NULL)
    {
        printf("Unable to open input file %s.\n", infile_name);
        return 1;
    }
    while(!feof(infile))//是否到了文件终点 
    {
        unsigned char c=fgetc(infile);
        if(feof(infile))
            continue;//只是跳出此次循环，与break不同！避免多加一次
        ++total;
        ++huftree[c].weight;
    }
    
    printf("压缩%s到%s\n",infile_name,outfile_name); 
    printf("源文件大小为：%d\n",total);         
    
    create_huftree(); 
    
    if((outfile=fopen(outfile_name,"ab"))==NULL)
    {
        printf("Unable to open output file %s.\n",outfile_name);
        return 1;
    }
    fwrite((void*)infile_name,sizeof(char),20,outfile);
    fwrite((void*)&total,sizeof(unsigned long),1,outfile);
    fwrite((void*)&root_pos,sizeof(short),1,outfile);
    fwrite((void*)huftree,sizeof(hufnode),511,outfile);
    fclose(outfile);
    
    short i;
    for(i=0;i<256;i++)
    {
        if(huftree[i].weight!=0)
            create_code(i);
    }
    while(!feof(infile))
    {
        unsigned char c=fgetc(infile);
        output_bits(huftree[c].bit_code,huftree[c].code_length);
    }
    fclose(infile);
    fclose(outfile);

    system("PAUSE");	
    return 0;
}

void create_huftree()                //创建哈夫曼树 
{
    int i;    
    for(i=0;i<511;i++)
    {
        huftree[i].left=-1;
        huftree[i].right=-1;
        huftree[i].parent=-1;    
    }
    for(i=256;i<511;i++)
    {
        unsigned long min1,min2;
        min1=min2=20000;
        int pos1,pos2;
        pos1=pos2=0;
        int j;
        for(j=0;j<i;j++) 
        {  
            if(huftree[j].parent == -1)
            {
                    if(huftree[j].weight<min1) 
                    {
                        pos2=pos1;min2=min1;
                        pos1=j;min1=huftree[j].weight;
                    }
                    else if (huftree[j].weight<min2 ) 
                    {
                        pos2=j;min2=huftree[j].weight; 
                    }
            }
        }
        huftree[i].left=pos1;
        huftree[i].right=pos2;
        huftree[i].weight=huftree[pos1].weight+huftree[pos2].weight;
        huftree[pos1].parent=huftree[pos2].parent=i;
    }
}
short searchroot_pos()//查找根结点的位置
{
    short k;
    for(k=256;k<511;k++)
    {
        if(huftree[k].parent==-1&&huftree[k].left!=-1&&huftree[k].right!=-1)
        {
            root_pos=k;
            break;
        }
    }
    return root_pos;
}

void create_code(short  i )//创建每个字符的编码 
{
    short current = i;
    short parent = huftree[i].parent;
    unsigned short code_length = 0;
    short code = 0;
    while(parent)
    {
        code_length++;
        if(huftree[parent].left == current)   
            code |= 1<<(code_length-1);
        current = parent;
        parent = huftree[current].parent;
    }
    huftree[i].code_length = code_length-1;
    huftree[i].bit_code = code;
}
void output_bits(unsigned short bit_code, short code_length)//输出编码 
{
    static unsigned char buffer = 0;
    static unsigned char bits_used = 0;
    bit_code <<= (16 - code_length);
    short i;
    for(i=0; i<code_length; i++)
    {
        buffer <<= 1;
        buffer |= ((bit_code & 0x8000) !=0);
        bit_code <<= 1;
        bits_used++;
        if(bits_used==8)
        {
            fputc(buffer,outfile);
            bits_used=0;
            buffer=0;
        }
    }
}