数据结构实验—哈夫曼树的编码和译码

1.建立哈夫曼树

以数组的形式建立哈夫曼树
类似于一下形式

数据结构实验—哈夫曼树的编码和译码

每次找出两个最小的权,将其和放在数组weight位置第一个权为空的位置,将两个最小权的下标放入该点的lchild,rchild中,将两个最小权的parent改为该点,第一次执行后变为

数据结构实验—哈夫曼树的编码和译码

每次循环找出最小的两个权,记录其位置,然后进行相应的赋值就行

实现代码

for (int i = num; i < 2 * num - 1; i++)
    {
        int m = 999, n = 999;
        int loc1 = -1, loc2 = -1;
        for (int j = 0; j < i; j++)
        {
            if (T[j][0] < m && T[j][1] == 0)
            {
                m = T[j][0];
                loc1 = j;
            }
        }
        for (int j = 0; j < i; j++)
        {
            if (T[j][0] < n && T[j][1] == 0)
            {
                if (j != loc1)
                {
                    n = T[j][0];
                    loc2 = j;
                }
            }
        }
        T[loc1][1] = i;
        T[loc2][1] = i;
        T[i][0] = m + n;
        T[i][2] = loc1;
        T[i][3] = loc2;

    }

建立哈夫曼编码

示例哈夫曼树

数据结构实验—哈夫曼树的编码和译码

搜索数组下标为1在左右孩子那两列中的位置,若为左则记0,右记1,再搜索1的双亲节点在左右孩子那两列的中的位置,依次找到每个节点的编码,这样搜索出来是编码的倒置,最后在逆置就好了。

数据结构实验—哈夫曼树的编码和译码

实现代码

for (int i = 0; i < num; i++)
    {
        int m;
        m = i;
        for (int j = num; j < 2*num - 1; j++)
        {
            int status = 0;
            if (T[j][2] == m)
            {
                T_code[i] = T_code[i] + '0';
                status = 1;
            }
            if (T[j][3] == m)
            {
                T_code[i] = T_code[i] + '1';
                status = 1;
            }
            if (status == 1)
            {
                m = j;
            }
        }
    }
    for (int i = 0; i < num; i++)
    {
        reverse(T_code[i].begin(), T_code[i].end());
    }

2.编码,建立与权值下标一一对应的数组,存放字母

依次读入每个字母,找到对应的编码并输出

实现代码

for (int i = 0; message[i] != '\0'; i++)
{
    tree.setCode(message[i]);    
}
void setCode(char a)
{
    for (int i = 0; i < num; i++)
    {
        if (words[i] == a)
        {
            code = code + T_code[i];
        }
    }
}

3.译码
输入代码,设一个string变量,将代码第一个数字赋给变量,如有对应项则记录信息,将变量重置为空。如没有,则将代码前两位赋给变量,直到找到对应项为止。

实现代码

void setMessage(char a)
{
    int status = 0;
    code_message = code_message + a;
    for (int i = 0; i < num; i++)
    {
        if (code_message == T_code[i])
        {
            status = 1;
            message = message + words[i];
        }
    }
    if (status == 1)
    {
        code_message = "";
    }
}

相关推荐