c++ - 实现霍夫曼树

Question

我有一个程序可以根据在文本输入文件中读取的 ascii 字符频率生成霍夫曼树。霍夫曼编码存储在一个包含 256 个元素的字符串数组中，如果未读取字符，则为空字符串。

我现在正在尝试通过编写一个函数来实现霍夫曼树，该函数采用存储在字符串数组中的霍夫曼代码，并将输入文件的编码输出到输出文件中。

我很快意识到我目前的做法违背了作业的意义。我试过简单地将代码字符串复制到输出文件，使我的编码输出文件大于输入文件。

我希望得到帮助来更改我当前的函数，以便它可以将位输出到输出文件中，从而使输出文件小于输入文件。我卡住了，因为我目前只读写字节？

我当前的函数(fileName 是输入文件参数，fileName2 是输出文件参数):

void encodeOutput(const string & fileName, const string & fileName2, string code[256]) {
    ifstream ifile;//to read file
    ifile.open(fileName, ios::binary);
    if (!ifile)//to check if file is open or not
    {
        die("Can't read again"); // function that exits program if can't open
    }
    ofstream ofile; 
    ofile.open(fileName2, ios::binary); 
    if (!ofile) {
        die("Can't open encoding output file"); 
    }
    int read;
    read = ifile.get();//read one char from file and store it in int
    while (read != -1) {//run this loop until reached to end of file(-1)
        ofile << code[read]; //put huffman code of character into output file
        read = ifile.get();//read next character
    }
    ifile.close();
    ofile.close();
}

Answer 1

你不能只使用 ofile << code[read];如果你需要的是写 bits，最小单位 ofstream理解为一个字节。

为了克服这个问题，您可以将您的位写入某种“位缓冲区”(char 就可以)，并在它有 8 位时写出 。我不完全知道你的代码字符串是什么样的，但应该这样做:

char buffer = 0, bit_count = 0;
while (read != -1) {
  for (int b = 0; b < code[read].size(); b++) {
    buffer << 1;
    buffer |= code[read][b] != 0;
    bit_count++;
    if (bit_count == 8) {
      ofile << buffer;
      buffer = 0;
      bit_count = 0;
    }
  }
  read = ifile.get();
}

if (bit_count != 0)
  ofile << (buffer << (8 - bit_count));