huffman.c

c语言环境下的 哈夫曼编码的串行程序

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

#define LEN 256
#define BUFFERMAX 4196
#define HUFFMANCODELEN 16 

#define HUFFMANCODEBYTE(code,i) hhptr[code].htreeptr->huffmancode.huffmancodebyte[i]

//用链表保存节点，方便排序
struct tree_table
{
    struct tree_table *head;
    struct htree *treeptr;
};

//保存huffman编码
struct _huffmancode
{
      unsigned char huffmancodebyte[HUFFMANCODELEN];
};


struct _huffmanhashptr
{
       struct htree* htreeptr;
};

//huffmantree的节点属性
struct htree
{
    struct htree *lchild;
    struct htree *rchild;
    unsigned char code;
    struct _huffmancode huffmancode;
    float weigth;
    unsigned char bit;//huffmancode位数 
    char leaf;    //1是叶子 
};

FILE *infile,*outfile;
unsigned char infilebuffer[BUFFERMAX],outfilebuffer[BUFFERMAX];
int read_len; 

struct htree g[LEN];
struct _huffmanhashptr hhptr[LEN];
//int testdata[]={10,20,1,2,4,2,0,5,4,2,5,4,2,1,3,6,3,0,1,3,0};
//int testdata[]={1,1,1,2,2,3,4,5,5,6};
int length=0;
struct tree_table *table_head;//链表头指针 
struct htree *forest;//huffman
int test;

void readdata();
void sort();
void set_table();
void huffmantree();
void readfile();
void writefile();
void write_huffmancode();

//遍历huffman树，生成huffman编码
void searchtree(struct htree *f)
{
    static unsigned char deep=0;
    if(f==NULL)return;
    if(f->leaf==1)
    {
        f->bit=deep--;
        hhptr[f->code].htreeptr=f;
        //printf("BBB:%d\tcode:%d\n",f->bit,f->code);
        return;    
    }
    f->lchild->huffmancode=f->huffmancode;
    f->rchild->huffmancode=f->huffmancode;
    f->rchild->huffmancode.huffmancodebyte[deep/8]|=(0x01<<(7-(deep%8)));
    deep++;
    searchtree(f->lchild);
    deep++;
    searchtree(f->rchild);
    deep--;
}

void all()
{
    readfile();
    sort();
    set_table();
    huffmantree();
    searchtree(forest);
    write_huffmancode();
    writefile();
}

int main(int argc, char *argv[])
{
    all();
    system("PAUSE");	
    return 0;
}

//读取文件 
void readfile()
{
     int i;
     infile=fopen("wavelet.dat","rb");
     //fseek(infile,0,2);
     //printf("KKKK:%d\n",ftell(infile));
     do{
       read_len=fread(infilebuffer,sizeof(char),BUFFERMAX,infile);
       readdata();//统计code出现的次数 
     }while(read_len==BUFFERMAX);
     fclose(infile);
     for(i=0;i<length;i++)printf("code:%d\tweigth:%f\n",g[i].code,g[i].weigth);
}

/*
* 保存huffman编码表 
*/
void write_huffmancode()
{
     int i,j,k;
     unsigned char cc[100];
     outfile=fopen("Comfile.dat","ab");
     for(i=0,k=0;i<length;i++)
     {
        cc[k++]=g[i].code;
        cc[k++]=g[i].bit;
        for(j=0;j<((g[i].bit-1)/8+1);j++)
        {
           cc[k+j]=g[i].huffmancode.huffmancodebyte[j];
           k++;
        }
        k=0;
        fwrite(cc,sizeof(char),3+(g[i].bit-1)/8,outfile);
     }
     fclose(outfile);
}

//把源文件根据huffman编码压缩，保存到新文件 
void writefile()
{
     int i,j;
     unsigned char temp[9];//临时保存一个数据的huffman编码，然后在将 temp 写到 outfilebuffer中 
     int tempcode;
     unsigned char code;
     int bufferptr=0;
     int tempbit=0;
     infile=fopen("wavelet.dat","rb");
     outfile=fopen("Comfile.dat","ab");
     while((tempcode=getc(infile))!=EOF)
     {
         code=tempcode;
         tempbit=hhptr[code].htreeptr->bit;
         for(i=0;i<9;i++) temp[i]=0;
         for(i=0;i<9;i++)
         {
             //将文件指针指向的最后一个字节的未使用的位用huffmancode第一个字节的前bufferptr%8位填充 
             temp[i]|=HUFFMANCODEBYTE(code,i)>>(bufferptr%8);
             tempbit-=bufferptr%8;
             if(tempbit<0)//huffmancode写入完毕 
                 break;
             temp[i+1]|=HUFFMANCODEBYTE(code,i)<<(7-(bufferptr%8));
             tempbit-=7-(bufferptr%8);
             if(tempbit<0)
                 break;
         }
         for(j=i;j>=0;j--)
         {
             outfilebuffer[bufferptr/8]|=temp[i-j]; 
         }
         bufferptr+=hhptr[code].htreeptr->bit;
         if(bufferptr/8>BUFFERMAX-8)
         {
             fwrite(outfilebuffer,sizeof(char),bufferptr/8+1,outfile);
                 for(i=0;i<BUFFERMAX;i++)outfilebuffer[i]=0;
             bufferptr=0;
         }
     }
     /*
     for(i=0;i<bufferptr/8;i++)
     {
        printf("bbb:%d\n",outfilebuffer[i]);
     }
     */
     fwrite(outfilebuffer,sizeof(char),bufferptr/8+1,outfile);
     bufferptr=0;
     fclose(infile);
     fclose(outfile);
}

void readdata()
{
    int i,j;
    int exist;
    for(i=0;i<read_len;i++)
    {
        exist=0;
        for(j=0;j<length;j++)
        {
            if(infilebuffer[i]==g[j].code)
            {
                g[j].weigth++;
                exist=1;
                break;
            }
        }
        if(exist==0)
        {
            g[length].code=infilebuffer[i];
            g[length].weigth=1;
            g[length].leaf=1;
            g[length].lchild=NULL;
            g[length].rchild=NULL;
            //g[length].huffmancode=0;
            length++;
        }
    }
}      

//对读取出来的数据排序
void sort(){
    int i,j;
    struct htree temp;
    for(i=0;i<length-1;i++)
    {
        for(j=length-1;j>i;j--)
        {
            if(g[j].weigth>g[j-1].weigth)
            {
                temp=g[j];
                g[j]=g[j-1];
                g[j-1]=temp;
            }
        }
    }
}

void set_table()//按大小顺序建立链表 
{
    int i;
    struct tree_table *tt;
    tt=(struct tree_table *)malloc(sizeof(struct tree_table));
    tt->head=NULL;
    tt->treeptr=g;
    table_head=tt;
    for(i=1;i<length;i++)
    {
        tt=(struct tree_table *)malloc(sizeof(struct tree_table));
        tt->head=table_head;
        tt->treeptr=g+i;
        table_head=tt;
    }
}

void insert_tree(struct htree *ht,struct tree_table **head)
{
     struct tree_table *tableptr;
     tableptr=*head;
     struct tree_table *temp;
     temp=(struct tree_table *)malloc(sizeof(struct tree_table));
     temp->treeptr=ht;
     if(ht->weigth<=tableptr->treeptr->weigth)
     {
       //新树为最小应加在表头 
         *head=temp;
         temp->head=tableptr;
     }else{
           while(tableptr->head!=NULL) 
           {
               if(ht->weigth>tableptr->head->treeptr->weigth)
               {
                   tableptr=tableptr->head;
               }else
               {
                   break;
               } 
           }
           temp->head=tableptr->head;
           tableptr->head=temp;
     }
}

void clean_code(struct htree* ht)
{
     struct _huffmancode temp;
     int i;
     for(i=0;i<16;i++){
     temp.huffmancodebyte[i]=0;
     }
     ht->huffmancode=temp;
}

//生成huffman树
void huffmantree()
{
    struct htree *temptree;
    while(1)
    {
        temptree=(struct htree *)malloc(sizeof(struct htree));
        //temptree 两个子树或叶子生成的新树 
        temptree->lchild=table_head->treeptr;
        temptree->rchild=table_head->head->treeptr;
        temptree->weigth=temptree->lchild->weigth+temptree->rchild->weigth;//将最后两个节点的概率相加得出新的概率，生成新树，把新树作为一个节点插入链表
        //temptree->code=-1;
        temptree->leaf=0;
        clean_code(temptree);
        //temptree->huffmancode=0;
        table_head=table_head->head->head;
        if(table_head==NULL)break;
        insert_tree(temptree,&table_head);
    }
    forest=temptree;
}