main.cpp

利用haffman编码对文章实现压缩和解密

#include <iostream>
#include <cmath>
#include <cstring>
#define N 128
using namespace std;

struct HuffmanNode
{
    int weight;
    int parent;
    int lchild;
    int rchild;
    char ch;
};

HuffmanNode HT[300];  //存储huffman树
char HC[N][100];  //存储huffman编码
int fre[N];    //fre[]中存放对应字母的次数
char le[N];    //le数组存储文章中出现的字母
int m, sum, total = 0;  //m为huffman数的结点总数，total为字符种类数, sum为文章中字符的总个数


//初始化字母出现频率数组f[]
void InitFre()
{
    int i;

    for (i = 0; i < N; i++)
    fre[i] = 0;
}
//读入文件，计算字母出现个数和频率
void OpenFile()
{
    char ch;
    int i;

    freopen("Huffman.txt", "rb", stdin);
    while (scanf("%c", &ch) != EOF)   //读入并计算字母个数
    {
        for (i = 0; i < total; i++) //判断字母是否已经出现过
        {
            if (ch == le[i])    //字母已经出现过，频数加一
            {
                fre[i]++;
                break;
            }
        }
        if (i == total)     //字母未出现过
        {
            fre[total]++;
            le[total++] = ch;
        }
    }
}
//函数功能：选择两个权值最小的结点
void Select(int &p1, int &p2, int n)
{
    int i, j;
    for (i = 1; i <= n; i++)    //p1初始化
    {
        if (HT[i].parent == -1)
        {
            p1 = i;
            break;
        }
    }
    for (j = i + 1; j <= n; j++)    //p2初始化
    {
        if (HT[j].parent == -1)
        {
            p2 = j;
            break;
        }
    }
    for (i = 1; i <= n; i++)    //选择一个权值最小的给p1
        if ((HT[p1].weight > HT[i].weight) && (HT[i].parent == -1) && (p2 != i))    p1 = i;
    for (j = 1; j <= n; j++)    //选择剩下权值最小的给p2
        if ((HT[p2].weight > HT[j].weight) && (HT[j].parent == -1) && (p1 != j))    p2 = j;
}
//存储各个字符对应的huffman编码
void Encoding()
{
    int c, p, i;    //c 和p 分别指示T 中孩子和双亲的位置
    char cd[total + 1];    //临时存放编码
    int start;     //指示编码在cd中的位置
    cd[total] = '\0';    //编码结束符
    for (i = 1; i <= total; i++)    //依次求叶子HT[i]的编码
    {
        start = total;  //编码起始位置的初值
        c = i;  //从叶子HT[i]开始上溯
        while ((p = HT[c].parent) != -1)    //p指向的点不是根结点
        {
            cd[--start] = (HT[p]. lchild == c)? '0' : '1';  //若HT[c]是HT[p]的左孩子，则生成代码0，否则生成代码1
            c = p; //继续上溯
        }
        strcpy(HC[i], &cd[start]);  //将编码复制到编码表HC中
        printf("%c(%d): %s\n", HT[i].ch, fre[i - 1], HC[i]);    //输出编码表
    }
}
//将字母频数作为权值建立huffman树
void HuffmanCoding()
{
    int i, p1, p2;
    m = 2 * total - 1;
    for (i = 1; i <= total; i++)  //HT初始化
    {
        HT[i].weight = fre[i - 1];
        HT[i].parent = -1;
        HT[i].lchild = -1;
        HT[i].rchild = -1;
        HT[i].ch = le[i - 1];
    }
    for (i = total + 1; i <= m; i++)  //HT初始化
    {
        HT[i].weight = 0;
        HT[i].parent = -1;
        HT[i].lchild = -1;
        HT[i].rchild = -1;
        HT[i].ch = 0;
    }
    if(total == 1)  //如果只有一个字符，不需要建立huffman树
    {
        HC[1][0] = '0';
        HC[1][1] = '\0';
        printf("%c(%d): %s\n", HT[1].ch, fre[0], HC[1]);    //输出编码表
        return;
    }
    for (i = total + 1; i <= m; i++)   // 建立huffman树
    {
        Select(p1, p2, i - 1);  //选择两个最小的权值
        HT[p1].parent = i;
        HT[p2].parent = i;
        HT[i].lchild = p1;
        HT[i].rchild = p2;
        HT[i].weight = HT[p1].weight + HT[p2].weight;
    }
    Encoding(); //存储各个字符对应的huffman编码
}
//将文章按照huffman编码压缩
void EssayTranslate()
{
    freopen("Huffman.txt", "rb", stdin);
    freopen("Encode.txt", "wb", stdout);
    char ch;    //存放文章中的字符
    char te = 0;    //存放转换后的字符
    int temp = 7;   //指示压缩过的huffman编码长度
    sum = 1;    //文章中出现过的字符个数
    while (scanf("%c", &ch) != EOF)   //将Huffman.txt中的字母编码输出到Huffman.txt中
    {
        int i;
        for (i = 1; i <= total; i++)    //查找字符的huffman编码
        {
            if (ch == HT[i].ch)
                break;
        }
        int len = strlen(HC[i]);
        int j;
        for (j = 0; j < len; j++)   //将huffman编码压缩为一个字符储存
        {
            if (HC[i][j] == '1')
                te = te | (1 << temp);
            temp--;
            if (temp == -1)  //八位huffman编码压缩为一个字符后输出
            {
                printf("%c", te);
                te = 0;
                temp = 7;
            }
        }
        sum++;
    }
    if (temp != 7)  printf("%c", te);//如果最后的剩余编码不足八位，输出
}
//将压缩后的文章解压
void EssayDecode()
{
    freopen("Encode.txt", "rb", stdin);
    freopen("Decode.txt", "wb", stdout);
    char ch;    //指示压缩文章中的字符
    char str[100];  //指示压缩文章中字符对应的huffman编码
    int flag = 1;   //指示已经转换完的字符个数
    int pos = m, j = 0; //pos指示结点位置，j指示str中0、1的位置
    while (scanf("%c", &ch) != EOF)
    {
        int i;
        for (i = 7; i >= 0; i--)    //依次转换压缩后字符所代表的huffman编码
        {
            if (ch & (1 << i))  //对应编码为1，pos指向结点的右子树
            {
                str[j++] = '1';
                pos = HT[pos].rchild;
            }
            else    //对应编码为零，pos指向结点的左子树
            {
                str[j++] = '0';
                pos = HT[pos].lchild;
            }
            if (HT[pos].lchild == -1 || pos == -1)   //如果已经到了huffman树叶子的位置，输出所代表的字符
            {
                str[j] = '\0';
                j = 0;
                int p;
                for(p = 1; p <= total; p++) //找到编码str对应的字符输出
                {
                    if(!strcmp(str, HC[p]))
                        break;
                }
                printf("%c", HT[p].ch);
                pos = m;
                flag++;
                if(flag == sum)  return;    //如果已经转换了所有的字符，结束
            }
        }
    }
}

int main()
{
    InitFre();  //字母出现频率数组fre初始化
    OpenFile();    //读入文件，计算字母出现个数和频率
    HuffmanCoding();    //将字母频数作为权值建立huffman树
    EssayTranslate();    //将文章按照huffman编码压缩
    EssayDecode();   //将压缩后的文章解压
    return 0;
}