赫夫曼编码

ACM模版

赫夫曼编码

main

main.cpp

#include <iostream>
#include "huffman.hpp"

int main(int argc, const char * argv[])
{
    // 源码
    char S[] = "I love Golden Dream!";
// char S[] = "I love FishC.com!";
    // 压缩码
    char s[] = "01101101001111111001011100111111110000001010010110010011101101000100110101";
// char s[] = "100011001110010000101011010010100000101011111011111101100101101110";

    // 构建赫夫曼树
    htTree *codeTree = buildTree(S);
    // 构建变长前缀码表
    hlTable *codeTable = buildTable(codeTree);
    // 压缩
    encode(codeTable, S);
    // 解压
    decode(codeTree, s);

    return 0;
}

queue

queue.hpp

#ifndef queue_hpp
#define queue_hpp

#include <stdio.h>
#include "huffman.hpp"

#define TYPE htNode *
#define MAX_SZ 256

typedef struct _pQueueNode  // 队列结点
{
    TYPE val;
    unsigned int priority;
    struct _pQueueNode *next;
}pQueueNode;

typedef struct _pQueue      // 队列
{
    unsigned int size;
    pQueueNode *first;
}pQueue;

void initPQueue(pQueue **queue);                                    // 初始化队列
void addPQueue(pQueue **queue, TYPE val, unsigned int priority);    // 插入队列头结点
TYPE getPQueue(pQueue **queue);                                     // 获取队列头结点

#endif /* queue_hpp */

queue.cpp

#include "queue.hpp"
#include <stdlib.h>

// 初始化队列
void initPQueue(pQueue **queue)
{
    (*queue) = (pQueue *)malloc(sizeof(pQueue));
    (*queue)->first = NULL;
    (*queue)->size = 0;
    return ;
}

// 将出现的字符逐个插入队列，并维护出现次数是从小到大
void addPQueue(pQueue **queue, TYPE val, unsigned int priority)
{
    if ((*queue)->size == MAX_SZ)
    {
        printf("\nQueue is full.\n");
        return ;
    }

    pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode));
    aux->priority = priority;
    aux->val = val;

    if ((*queue)->size == 0 || (*queue)->first == NULL)
    {
        aux->next = NULL;
        (*queue)->first = aux;
        (*queue)->size = 1;
        return ;
    }
    else
    {
        // 小于头则插入头
        if (priority <= (*queue)->first->priority)
        {
            aux->next = (*queue)->first;
            (*queue)->first = aux;
            (*queue)->size++;
            return ;
        }
        else
        {
            pQueueNode *iterator = (*queue)->first; // 迭代器
            // 插入合适的位置，维护从小到大顺序
            while (iterator->next != NULL)
            {
                if (priority <= iterator->next->priority)
                {
                    aux->next = iterator->next;
                    iterator->next = aux;
                    (*queue)->size++;
                    return ;
                }
                iterator = iterator->next;
            }

            // 当大于队列内所有值，则插入队尾
            if (iterator->next == NULL)
            {
                aux->next = NULL;
                iterator->next = aux;
                (*queue)->size++;
                return ;
            }
        }
    }
}

// 从队列头逐个取出（越接近头部出现的次数越少）
TYPE getPQueue(pQueue **queue)
{
    TYPE returnValue;
    if ((*queue)->size > 0)
    {
        returnValue = (*queue)->first->val;
        (*queue)->first = (*queue)->first->next;
        (*queue)->size--;
    }
    else
    {
        printf("\nQueue is empty.\n");
    }
    return returnValue;
}

huffman

huffman.hpp

#ifndef huffman_hpp
#define huffman_hpp

#include <stdio.h>

typedef struct _htNode  // 树结点
{
    char symbol;
    struct _htNode *left, *right;
}htNode;

typedef struct _htTree  // 树
{
    htNode *root;
}htTree;

typedef struct _hlNode  // 表结点
{
    char symbol;
    char *code;
    struct _hlNode *next;
}hlNode;

typedef struct _hlTable // 表
{
    hlNode *first;
    hlNode *last;
}hlTable;

htTree *buildTree(char *inputString);               // 构建赫夫曼树
hlTable *buildTable(htTree *huffmanTree);           // 构建变长前缀码表
void encode(hlTable *table, char *stringToEncode);  // 压缩
void decode(htTree *tree, char *stringToDecode);    // 解压

#endif /* huffman_hpp */

huffman.cpp

#include "huffman.hpp"
#include "queue.hpp"
#include <string>
#include <stdlib.h>

// 创建赫夫曼树
htTree *buildTree(char *inputString)
{
    int *probability = (int *)malloc(sizeof(int) * 256);    // 存放ASCII自定义对应的字符
    // 初始化
    for (int i = 0; i < 256; i++)
    {
        probability[i] = 0;
    }

    // 统计待编码的字符串各个字符出现的次数
    for (int j = 0; inputString[j] != '\0'; j++)
    {
        probability[(unsigned char)inputString[j]]++;   // 此处强制转换可有可无
    }

    // pQueue队列的头指针
    pQueue *huffmanQueue;
    initPQueue(&huffmanQueue);

    // 填充队列
    for (int k = 0; k < 256; k++)
    {
        if (probability[k] != 0)
        {
            htNode *aux = (htNode *)malloc(sizeof(htNode));
            aux->left = NULL;
            aux->right = NULL;
            aux->symbol = (char)k;

            addPQueue(&huffmanQueue, aux, probability[k]);
        }
    }

    free(probability);  //插入完毕，释放无用内存

    // 生成赫夫曼树
    while (huffmanQueue->size != 1)
    {
        int priority = huffmanQueue->first->priority;
        priority += huffmanQueue->first->next->priority;

        htNode *left = getPQueue(&huffmanQueue);
        htNode *right = getPQueue(&huffmanQueue);

        htNode *newNode = (htNode *)malloc(sizeof(htNode));
        newNode->left = left;
        newNode->right = right;

        addPQueue(&huffmanQueue, newNode, priority);
    }

    htTree *tree = (htTree *)malloc(sizeof(htTree));

    tree->root = getPQueue(&huffmanQueue);  // 赫夫曼树根结点

    return tree;                            // 返回赫夫曼树
}

// 生成前缀码
void traverseTree(htNode *treeNode, hlTable ** table, int k, char code[256])
{
    if (treeNode->left == NULL && treeNode->right == NULL)  // 存储前缀码
    {
        code[k] = '\0';
        hlNode *aux = (hlNode *)malloc(sizeof(hlNode));
        aux->code = (char *)malloc(sizeof(char) * (strlen(code) + 1));
        strcpy(aux->code, code);
        aux->symbol = treeNode->symbol;
        aux->next = NULL;

        if ((*table)->first == NULL)
        {
            (*table)->first = aux;
            (*table)->last = aux;
        }
        else
        {
            (*table)->last->next = aux;
            (*table)->last = aux;
        }
    }

    if (treeNode->left != NULL)     // 如果左孩子不为空，则前缀码填'0'
    {
        code[k] = '0';
        traverseTree(treeNode->left, table, k + 1, code);
    }

    if (treeNode->right != NULL)    // 如果右孩子不为空，则前缀码填'1'
    {
        code[k] = '1';
        traverseTree(treeNode->right, table, k + 1, code);
    }
    return ;
}

// 构建变长前缀码表
hlTable *buildTable(htTree *huffmanTree)
{
    hlTable *table = (hlTable *)malloc(sizeof(hlTable));
    table->first = NULL;
    table->last = NULL;

    char code[256];
    int k = 0;

    traverseTree(huffmanTree->root, &table, k, code);
    return table;   // 返回变长前缀码表
}

// 压缩
void encode(hlTable *table, char *stringToEncode)
{
    hlNode *traversal;

    printf("Encoding......\nInput string:\n%s\nEncoded string:\n", stringToEncode);

    for (int i = 0; stringToEncode[i] != '\0'; i++)
    {
        traversal = table->first;
        while (traversal->symbol != stringToEncode[i])
        {
            traversal = traversal->next;
        }
        printf("%s", traversal->code);
    }
    printf("\n");
    return ;
}

// 解压
void decode(htTree *tree, char *stringToDecode)
{
    htNode *traversal = tree->root;

    printf("\nDecoding......\nInput string:\n%s\nDecoded string:\n", stringToDecode);

    for (int i = 0; stringToDecode[i] != '\0'; i++)
    {
        if (traversal->left == NULL && traversal->right == NULL)
        {
            printf("%c", traversal->symbol);
            traversal = tree->root;
        }

        if (stringToDecode[i] == '0')       // 等于'0'向左孩子查找
        {
            traversal = traversal->left;
        }
        else /* if (stringToDecode[i] == '1')等于'1'向右孩子查找 */
        {
            traversal = traversal->right;
        }
    }

    if (traversal->left == NULL && traversal->right == NULL)
    {
        printf("%c", traversal->symbol);
    }
    putchar('\n');
    return ;
}