时间戳

首页 > 解决方案 > C++ Huffman 代码实现编码大部分时间正确吗？

c++ - C++ Huffman 代码实现编码大部分时间正确吗？

问题描述

晚上大家都在研究霍夫曼编码的 C++ 实现，这就是我所拥有的。奇怪的是，大部分时间都在工作。但是对于某些输入，我得到了不正确的编码/输出。如果您看到我在这里缺少什么，请告诉我……我会继续寻找……谢谢您的帮助！更新了代码以解决下面提到的问题......仍然遇到同样的问题。

#include <iostream> 
#include <queue> 
#include <list> 
#include <iterator>
#include <vector>
#include <algorithm>

class HuffmanCodes
{
struct Node
{
int data;
size_t freq;
Node* left;
Node* right;

Node()
{
   data = '\0';
   freq = 0;
}
Node(int data, size_t freq) : data(data),
                                freq(freq),
                                left(nullptr),
                                right(nullptr)
                                {}
~Node()
{
  delete left;
  delete right;
}
};

struct compare
{
 bool operator()(Node* l, Node* r)
{
   return (l->freq > r->freq);
}
};

Node* top;

void printCode(Node* root, std::string str, std::vector<int>& data, int i)
{
if(root == nullptr)
 return;

if(root->data != '$' && data[i] == root->data )
{
 std::cout << root->data +1 << " : " << str << "\n";
}
printCode(root->left, str + "0" ,data, i);
printCode(root->right, str + "1", data, i);
}

public:
  HuffmanCodes() {}
   ~HuffmanCodes()
 {
   delete top;
 }
 void GenerateCode( std::vector<int>& data, std::vector<size_t>& freq)
 {
  Node* left;
  Node* right;

  std::priority_queue<Node*, std::vector<Node*>, compare > minHeap;

  for(size_t i = 0; i < data.size(); ++i)
  {
     minHeap.push(new Node(data[i], freq[i]));
  }

   while(minHeap.size() != 1)
   {
     std::sort (data.begin(), data.end());
     left = minHeap.top();
     minHeap.pop();

     right = minHeap.top();
     minHeap.pop();

     top = new Node('$', left->freq + right->freq);
     top->left  = left;
     top->right = right;
     minHeap.push(top);
    }
    for( int j = 0; j < data.size(); j++ )
        printCode(minHeap.top(), "", data, j);
 }
};

int main()
{
   int n;
   std::cin >> n;
   std::vector<int> data;
   std::vector<size_t> freq;


   for(int i = 0; i < n; i++){
        int input;
        std::cin >> input;
        freq.push_back(input);
   }

   for(int i = 0; i < n; i++){

       data.push_back(i);
   }
  HuffmanCodes set1;

  size_t size = n;
  set1.GenerateCode(data, freq);

  return 0;
 }

输入：20 84 87 78 16 94 36 87 93 50 22 63 28 91 60 64 27 41 27 73 37

输出：
1010 1100
1001 100010 000 01101 1011
1111 11101 100011 0100 01100
1101 0011 0101
00100 11100 00101 0111 10000

正确输出：1010

1011 1001 100010 000 01011 1100
1111 11101 100011 0100 01010 1101 0011 0110 00100 11100 00101 0111 10000

标签： c++huffman-code

解决方案

Valgrind 立即指向错误的代码：

g++ -std=c++2a -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds  -Weffc++       53367469.cpp    -o 53367469
53367469.cpp: In constructor ‘MinHeapNode::MinHeapNode(int, unsigned int)’:
53367469.cpp:20:1: warning: ‘MinHeapNode::data’ should be initialized in the member initialization list [-Weffc++]
 MinHeapNode(int data, unsigned freq) {
 ^~~~~~~~~~~
53367469.cpp:20:1: warning: ‘MinHeapNode::freq’ should be initialized in the member initialization list [-Weffc++]
53367469.cpp:20:1: warning: ‘MinHeapNode::left’ should be initialized in the member initialization list [-Weffc++]
53367469.cpp:20:1: warning: ‘MinHeapNode::right’ should be initialized in the member initialization list [-Weffc++]
53367469.cpp: In function ‘int main()’:
53367469.cpp:104:8: warning: ISO C++ forbids variable length array ‘p’ [-Wvla]
 int p[n];
        ^
53367469.cpp:105:8: warning: ISO C++ forbids variable length array ‘a’ [-Wvla]
 int a[n];
        ^
53367469.cpp: In function ‘void merge(int*, int, int, int)’:
53367469.cpp:145:14: warning: ISO C++ forbids variable length array ‘left’ [-Wvla]
   int left[n1];
              ^
53367469.cpp:146:15: warning: ISO C++ forbids variable length array ‘right’ [-Wvla]
   int right[n2];
               ^
valgrind -q --leak-check=full ./53367469  <<<"$INPUT" 
==8553== Invalid read of size 8
==8553==    at 0x10A41D: HuffmanCodes(int*, int*, int) (53367469.cpp:72)
==8553==    by 0x10A704: main (53367469.cpp:115)
==8553==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==8553== 
==8553== 
==8553== Process terminating with default action of signal 11 (SIGSEGV)
==8553==  Access not within mapped region at address 0x0
==8553==    at 0x10A41D: HuffmanCodes(int*, int*, int) (53367469.cpp:72)
==8553==    by 0x10A704: main (53367469.cpp:115)
==8553==  If you believe this happened as a result of a stack
==8553==  overflow in your program's main thread (unlikely but
==8553==  possible), you can try to increase the size of the
==8553==  main thread stack using the --main-stacksize= flag.
==8553==  The main thread stack size used in this run was 8720384.

空队列没有有效的top()。

顺便说一句，使用<bits/stdc++.h>效率低下且不可移植；using namespace std也是不明智的。

推荐阅读