c++ - 我如何在 C++ 中表示二进制数(用于霍夫曼编码器)？

Question

我正在写我自己的 Huffman encoder ，到目前为止，我已经创建了霍夫曼树，方法是使用 minHeap 弹出两个最低频率的节点并创建一个链接到它们的节点，然后将新节点推回一个节点(泡沫、冲洗、重复直到只有一个节点)。

所以现在我已经创建了树，但我需要使用这棵树为每个字符分配代码。我的问题是我不知道如何在 C++ 中存储数字的二进制表示。我记得读过 unsigned char 是字节的标准，但我不确定。

我知道我必须递归遍历树，每当我碰到一个叶节点时，我必须分配相应的字符，无论当前代表路径的代码是什么。

这是我目前所拥有的:

void traverseFullTree(huffmanNode* root, unsigned char curCode, unsigned char &codeBook){

    if(root->leftChild == 0 && root->rightChild == 0){ //you are at a leaf node, assign curCode to root's character
        codeBook[(int)root->character] = curCode;
    }else{ //root has children, recurse into them with the currentCodes updated for right and left branch
        traverseFullTree(root->leftChild, **CURRENT CODE SHIFTED WITH A 0**, codeBook );
        traverseFullTree(root->rightChild, **CURRENT CODE SHIFTED WITH A 1**, codeBook);
    }

    return 0;
}

CodeBook 是我的数组，其中包含最多 256 个字符的代码(对于 ASCII 中的每个可能的字符)，但我实际上只会将代码分配给树中出现的值。

我不确定这是否是遍历我的霍夫曼树的正确方法，但这似乎立即起作用(尽管我还没有测试过)。另外，如何调用没有零或一的整棵树的根(树的最顶端)的遍历函数？

我应该改用字符串并在字符串后附加 0 还是 1？

Answer 1

因为计算机是二进制的...C/C++ 中的所有数字都已经是二进制格式了。

int a = 10;

变量a是二进制数。

你要看的是位操作，运算符如& | << >> .

使用霍夫曼编码，您可以将数据打包成一个字节数组。

我已经很久没有写过C了，所以这是一个“即兴”的伪代码......

完全未经测试——但应该会给您正确的想法。

char buffer[1000]; // This is the buffer we are writing to -- calc the size out ahead of time or build it dynamically as go with malloc/ remalloc.

void set_bit(bit_position) {
  int byte = bit_position / 8;
  int bit = bit_position % 8;

  // From http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
  byte |= 1 << bit;
}

void clear_bit(bit_position) {
  int byte = bit_position / 8;
  int bit = bit_position % 8;

  // From http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
 bite &= ~(1 << bit);
}


// and in your loop, you'd just call these functions to set the bit number.
set_bit(0);
clear_bit(1);