c++ - 霍夫曼以位存储代码

Question

我已经构建了霍夫曼树。但我不知道如何将代码存储到位，因为我不知道如何

处理可变长度。

我想创建一个表，以位为单位存储霍夫曼代码，以打印编码结果。

我不能使用像 bitset 这样的 STL 容器。

我试过这样

   void traverse( string code = "")const
   {
        if( frequency == 0 ) return;
        if ( left ) {
             left->traverse( code + '0' );
             right->traverse( code + '1' );
        }
        else {//leaf node
             huffmanTable[ch] = code;
        }
   } 

你能给我一些算法来处理它吗？

我想存储“0”使用 1 位，“1”使用 1 位。

提前致谢。

Answer 1

您需要一个缓冲区、一个用于跟踪缓冲区大小(以字节为单位)的变量，以及一个用于跟踪缓冲区中有效位数的变量。

存储位:

1. 检查增加一位是否会增加存储的字节数。如果不是，请跳至第 4 步。

2. 缓冲区中是否有空间来存储额外的字节？如果是，请跳至第 4 步。

3. 重新分配一个大几个字节的存储缓冲区。复制现有数据。增加保存缓冲区大小的变量。

4. 计算存储下一位的字节位置和位位置。根据需要设置或清除该位。

5. 增加保存存储位数的变量。