我正在研究霍夫曼代码生成器。下面是我组成树的功能。该树基于对象指针 vector 。我已经检查过了,它似乎工作正常。我现在想将位于 pointerVect[0] 位置的指针传递给下面的霍夫曼编码递归函数,它应该是树的根,但是由于某种原因它无法正常工作,就像我尝试打印的内容一样存储代码的 map 没有打印出来。
class asciiChar //Individual character module >>> Base Class
{
public:
void setCharValue (char letter)
{
charValue = letter;
}
char getCharValue ()
{
return charValue;
}
void incrementCharCount ()
{
charCount++;
}
int getCharCount()
{
return charCount;
}
virtual asciiChar * getLeft()
{
return left;
}
virtual asciiChar * getRight()
{
return right;
}
asciiChar(char c, int f) //Constructor
{
charValue = c;
charCount = f;
}
asciiChar & operator= (const asciiChar & other) //Overloaded assignment operator
{
charValue = other.charValue;
charCount = other.charCount;
return *this;
}
char charValue;
int charCount = 0;
asciiChar * left = NULL;
asciiChar * right = NULL;
};
class parentNode : public asciiChar //Connector node
{
public:
parentNode(asciiChar c0, asciiChar c1) : asciiChar(NULL, c0.getCharCount() + c1.getCharCount())
{
left = &c0;
right = &c1;
}
~parentNode()
{
if (left) delete left;
if (right) delete right;
}
};
asciiChar* createTree (vector<asciiChar> sortedVector)
{
vector<asciiChar*> pointerVect;
pointerVect.reserve(sortedVector.size());
for(int i=0; i < sortedVector.size(); i++)
{
pointerVect.push_back(new asciiChar(sortedVector[i].getCharValue(), sortedVector[i].getCharCount()));
}
while (pointerVect.size() > 1)
{
asciiChar * newL = pointerVect.back();
pointerVect.pop_back();
asciiChar * newR = pointerVect.back();
pointerVect.pop_back();
asciiChar * parent = new parentNode(* newL, * newR);
pointerVect.push_back(parent);
vectSort2 (pointerVect);
}
return pointerVect[0]; //Returns pointer at very top (The root of the tree)
}
最佳答案
我怀疑你的第一个函数“createTree”
正如我最初的评论所指出的,出于各种原因,您应该考虑使用优先级队列。这是我注意到的问题的快速列表
- 你正在对一个指针 vector 进行排序。所以指针将根据它们的地址值而不是它们指向的对象进行排序。但是,您可能正在提供一个比较器。如果是这种情况,请忽略此项目符号。
- 每次 while 循环迭代对 vector 进行排序的时间复杂度为 O(nLog(n)),其中插入优先级队列并保持排序顺序的时间复杂度为 O(Log(n))
- 由于您是按指针排序,因此不能保证 vector 的索引 0 是树的根。
考虑改用优先级队列: 在头文件中
#include <queue>
// Comparator for priority queue. Use this so it compared what the pointers point too and not the pointers themselves. This way the frequencies are used for the
// comparisons. This forces the priority queue to order from lowest freq
// to the highest frequency
struct CompareHuffChars : public binary_function<asciiChar*, asciiChar*, bool>
{
bool operator()(const asciiChar* left, const asciiChar* right) const
{
// Be sure to add functionality to get frequency for each asciiChar object
return left->getFrequency() > right->getFrequency();
}
}; // end struct
priority_queue<asciiChar*,vector<asciiChar*>,CompareHuffChars > * bytePriorityQueue;
asciiChar * huffmanTree; // Pointer to assign to root node of tree when found
在实现文件中....
while (!(this->bytePriorityQueue->empty())) {
asciiChar * qtop = this->bytePriorityQueue->top();
this->bytePriorityQueue->pop();
if (this->bytePriorityQueue->empty()) {
// Found the root asciiChar node
this->huffmanTree = qtop; // huffManTree = asciiChar *
} else {
// There are more asciiChar nodes so we need to grab the 2nd from top
// and combine their frequencies into a new asciiChar node and insert it
// back into the priority queue
asciiChar * newNode;
asciiCharChar * qtopSecond = this->bytePriorityQueue->top();
// Remove it from the queue
this->bytePriorityQueue->pop();
// Now create a new asciiChar node with the added frequences
// qtopSecond should always be > or = qtop
// which will adhere to the binary tree structure
// This assumes asciiChar adds the frequencies of qtop and qtopSecond in constructor
newNode = new asciiChar(qtop,qtopSecond);
// Push the new node into the p queue
// Stays sorted with Log(n) insertion
this->bytePriorityQueue->push(newNode);
// Now repeat this until the tree is formed (1 node left in queue)
} // end if
} // end while
//The p queue should now be completely empty (len =0)
}
现在我的版本需要对 asciiChar 进行一些重构。但是,此方法应该比发布的方法更好,并且可以解决您的错误。
编辑
好的,我“认为”我发现了您的错误。在 asciiChar 的头文件中,getLeft 和 getRight 函数是非虚拟函数。这意味着当您有一个类型为 asciiChar * 的基指针指向一个类型为 parentNode(子类)的对象时,它将调用父类(asciiChar)的 getLeft 和 getRight 函数,该函数将始终返回 NULL。您在子类 (parentNode) 中重新声明了一个 left 和 right,您不需要这样做,因为这些成员变量在您的父类中是公开的。使 getLeft 和 getRight 函数成为虚拟函数,并删除 parentNode 类中的 left 和 right 声明以及它们各自的 getter 函数。
// In aschiiChar
virtual asciiChar * getLeft()
{
return left;
}
virtual asciiChar * getRight()
{
return right;
}
旁注:如果指针为 NULL,则应在删除前检查析构函数。
if (left) delete left;
if (right) delete right;
最终编辑
感谢您发布更多信息。好的,您的问题归结为以下几点:
// This is your parentNode constructor
parentNode(asciiChar c0, asciiChar c1) : asciiChar(NULL, c0.getCharCount() + c1.getCharCount())
{
left = &c0;
right = &c1;
}
// This is what the parentNode constructor should look like
parentNode(asciiChar * c0, asciiChar * c1) : asciiChar(NULL, c0->getCharCount() + c1->getCharCount())
{
left = c0;
right = c1;
}
最后...
asciiChar* createTree (vector<asciiChar> sortedVector)
{
vector<asciiChar*> pointerVect;
pointerVect.reserve(sortedVector.size());
for(int i=0; i < sortedVector.size(); i++)
{
pointerVect.push_back(new asciiChar(sortedVector[i].getCharValue(), sortedVector[i].getCharCount()));
}
while (pointerVect.size() > 1)
{
asciiChar * newL = pointerVect.back();
pointerVect.pop_back();
asciiChar * newR = pointerVect.back();
pointerVect.pop_back();
// CHANGE HERE
// Don't dereference the pointers. If you dereference them you are passing by value
// and creating copies in the constructor which are destroyed upon exit of the constructor
asciiChar * parent = new parentNode( newL, newR);
pointerVect.push_back(parent);
vectSort2 (pointerVect);
}
return pointerVect[0]; //Returns pointer at very top (The root of the tree)
}
您的问题归结为您按值传递并将本地拷贝的地址分配给 parentNode 的成员变量指针。 parentNode 中的这些指针随后指向不存在的内存或不属于它们的内存。
希望这对您有所帮助...
关于c++ - 霍夫曼编码器 - 递归,编码功能失败,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17622930/