霍夫曼编码的分析与实现(5)

/*优先队列中的最后一棵树即是霍夫曼树*/
    if(pqueue_extract(&pqueue,(void **)tree) != 0)
    {
        pqueue_destroy(&pqueue);
        return -1;
    }
    else
    {
        pqueue_destroy(&pqueue);
    }
    return 0;
}

/*build_table 建立霍夫曼编码表*/
static void build_table(BiTreeNode *node, unsigned short code, unsigned char size, HuffCode *table)
{
    if(!bitree_is_eob(node))
    {
        if(!bitree_is_eob(bitree_left(node)))
        {
            /*向左移动，并将0追加到当前代码中*/
            build_table(bitree_left(node),code<<1,size+1,table);
        }

if(!bitree_is_eob(bitree_right(node)))
        {
            /*向右移动，并将1追加到当前代码中*/
            build_table(bitee_right(node),(code<<1) | 0x0001,size+1,table);
        }

if(bitree_is_eob(bitree_left(node)) && bitree_is_eob(bitree_right(node)))
        {
            /*确保当前代码是大端格式*/
            code = htons(code);

/*将当前代码分配给叶子结点中的符号*/
            table[((HuffNode *)bitree_data(node))->symbol].used = 1;
            table[((HuffNode *)bitree_data(node))->symbol].code = code;
            table[((HuffNode *)bitree_data(node))->symbol].size = size;
        }
    }
    return;
}
/*huffman_compress 霍夫曼压缩*/
int huffman_compress(const unsigned char *original, unsigned char **compressed, int size)
{
    BiTree        *tree;
    HuffCode      table[UCHAR_MAX + 1];
    int          freqs[UCHAR_MAX + 1],
                  max,
                  scale,
                  hsize,
                  ipos,opos,cpos,
                  c,i;
    unsigned      *comp,*temp;

/*初始化，没有压缩数据的缓冲区*/
    *compressed = NULL;

/*获取原始数据中每个符号的频率*/
    for(c=0; c <= UCHAR_MAX; c++)
        freqs[c] = 0;

ipos = 0;

if(size > 0)
    {
        while(ipos < size)
        {
            freqs[original[ipos]]++;
            ipos++;
        }
    }

/*将频率缩放到一个字节*/
    max = UCHAR_MAX;

for(c=0; c<=UCHAR_MAX; c++)
    {
        if(freqs[c] > max)
            max = freqs[c];
    }

for(c=0; c <= UCHAR_MAX; c++)
    {
        scale = (int)(freqs[c] / ((double)max / (double)UCHAR_MAX));

if(scale == 0 && freqs[c] != 0)
            freqs[c] = 1;
        else
            freqs[c] = scale;
    }

/*建立霍夫曼树和编码表*/
    if(build_tree(freqs,&tree) != 0)
        return -1;

for(c=0; c<=UCHAR_MAX; c++)
        memset(&table[c],0,sizeof(HuffCode));

bulid_table(bitree_root(tree), 0x0000, 0, table);

bitree_destroy(tree);
    free(tree);

/*编写一个头代码*/
    hsize = sizeof(int) + (UNCHAR_MAX + 1);

if((comp = (unsigned char *)malloc(hsize)) == NULL)
        return -1;

memcpy(comp,&size,sizeof(int));

for(c=0; c<=UCHAR_MAX; c++)
        comp[sizeof(int) + c] = (unsigned char)freqs[c];

/*压缩数据*/
    ipos = 0;
    opos = hsize*8;

while(ipos < size)
    {
        /*获取原始数据中的下一个字符*/
        c = original[ipos];