霍夫曼编码.cpp

经典的霍夫曼算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define MAX_LEN        128

typedef struct huffman {
        char _elem;
        char *_code;
        short _leaf;
        int _freq;
        struct huffman *_left;
        struct huffman *_right;
} Huffman;
//Global variables
Huffman *huff[MAX_LEN];
FILE *fin, *fout;
int index = 1;

void quicksort(Huffman *[], int, int);
int partition(Huffman *[], int, int, Huffman*);
int findpivot(int, int);
void swap(Huffman *[], int, int);
void get_and_init();                        //Get data and initialize *huff[]
void build_huff_tree(Huffman *[], int);     //Build the huffman tree
void encode(Huffman*, const char*);         //Encode the chars
void decode(Huffman*);                      //Decode the encoded to original
void traverse(Huffman*);                    //Go through the huffman tree

int main()
{
        static int tmp[MAX_LEN+1] = {0};
        int i = 0, c, j;
        fin = fopen("huffman_in.txt", "r+");
        while(!feof(fin)){        
                c = fgetc(fin);
                tmp[c]++;
        }
        for(j = 0; j <= MAX_LEN; j++)
                if(tmp[j] != 0){                
                        (huff[i]) = (Huffman*)malloc(sizeof(Huffman));
                        (huff[i])->_elem = j;
                        (huff[i])->_freq = tmp[j];
                        (huff[i])->_leaf = 1;
                        (huff[i])->_left = NULL;
                        (huff[i])->_right = NULL;
                        i++;
                }
        //Begin to build the huffman tree and encode the chars
        quicksort(huff, 0, i);
        while(--i > 0){        
                build_huff_tree(huff, i);
                quicksort(huff, 0, i);
        }
        fout = fopen("huffman_out.txt", "w");
        huff[0]->_code = (char*)malloc(sizeof(char));
        (huff[0]->_code)[0] = '\0';
        encode(huff[0], huff[0]->_code);
        fclose(fout);//End of building

        //Encode the chapter based on the huffman tree
        fout = fopen("huffman_out_code.txt", "w+");
        rewind(fin);
        while(!feof(fin)){
                c = fgetc(fin);
                for(i = 1; i < index; i++)
                        if(c == huff[i]->_elem){
                                fprintf(fout, "%s", huff[i]->_code);
                                break;
                        }
        }
        fclose(fin);
        fclose(fout);//End of encoding
        
        //Decoding the codes to original
        fin = fopen("huffman_out_code.txt", "r+");
        fout = fopen("huffman_out_decode.txt", "w+");
        decode(huff[0]);//End of decoding

        return 0;
}

void build_huff_tree(Huffman *root[], int n)                        //Build huffman tree
{
        Huffman *ptr = (Huffman*)malloc(sizeof(Huffman));
        ptr->_left = (root[n]);
        ptr->_right = (root[n-1]);
        ptr->_leaf = 0;
        ptr->_freq = ptr->_left->_freq + ptr->_right->_freq;
        (root[n-1]) = ptr;
}
void encode(Huffman *root, const char *code)                        //Encode the chars based on the huffman tree
{
        char *lcode = NULL, *rcode = NULL;        
        if(root == NULL) return;
        if(root->_leaf){        
                root->_code = (char*)malloc(sizeof(char) * (strlen(code) + 1));
                strcpy(root->_code, code);
                if(root->_elem == '\n')
                        fprintf(fout, "Char %s%s", "\\n", " is encoded to: ");
                else
                        fprintf(fout, "Char %c%s", root->_elem, " is encoded to: ");
                fprintf(fout, "%s\n", root->_code);
                huff[index++] = root;
        }
        lcode = (char*)malloc(sizeof(char) * (strlen(code) + 2));
        strcpy(lcode, code);
        strcat(lcode, "0");
        encode(root->_left, lcode);
        free(lcode);
        rcode = (char*)malloc(sizeof(char) * (strlen(code) + 2));
        strcpy(rcode, code);
        strcat(rcode, "1");
        encode(root->_right, rcode);
        free(rcode);
}
void decode(Huffman *root)                                                                //Decode the encoded to original
{
        char c;
        while(!feof(fin)){        
                if(root->_leaf){
                        fputc(root->_elem, fout);
                        root = huff[0];
                }else{
                        c = fgetc(fin);        
                        if(c == '0')
                                root = root->_left;
                        else if (c == '1')
                                root = root->_right;
                }
                /*if(c == '0')
                        decode(root->_left);
                else if(c == '1')
                        decode(root->_right);*/
        }
}
void traverse(Huffman *root)                                                        //Traverse the intire huffman tree
{
        if(root == NULL)        return;
        if(root->_leaf)
                printf("%2c", root->_elem);
        traverse(root->_left);
        traverse(root->_right);
}
//Quicksort and its help functions
int partition (Huffman *root[], int low, int high, Huffman *pivot)
{
        do{        
                while ((root[++low])->_freq > pivot->_freq);                //move right
                while (high != 0 && (root[--high])->_freq < pivot->_freq);
                //the low's element is bigger than pivot and 
                //the high's element is less than pivot,so we should swap their elements
                swap (root, low, high);                                
        }while (low < high);
        //at the last loop, low is bigger than high so we should swap their elements 
        swap (root, low, high);
        return low;
}

int findpivot (int low, int high)
{
        srand (time (NULL));
        return low + rand () % (high - low);
}
void quicksort(Huffman *root[], int left, int right)
{
        int pivot, index;
        if (left >= right - 1) return;
        pivot = findpivot (left, right);
        swap (root, pivot, right - 1);                                        //put pivot at end
        //For later convinience, low bound is decreased
        index = partition(root, left - 1, right - 1, root[right - 1]);
        //the element whose subscrpt is index is in the right position right now
        swap (root, index, right - 1);
        quicksort(root, left, index);
        quicksort(root, index + 1, right);
}
void swap(Huffman *root[], int low, int high)
{
        Huffman *tmp = (root[low]);
        root[low] = root[high];
        root[high] = tmp;
}