Huffman Encoder — Сбой рекурсивной функции кодирования

Мое подозрение связано с вашей первой функцией ‘createTree’

Как показывает мой первоначальный комментарий, вам следует рассмотреть возможность использования очереди с приоритетами по разным причинам. Вот быстрый список проблем, которые я замечаю

• Вы сортируете вектор указателей. Таким образом, указатели будут отсортированы по значениям их адресов, а не по объектам, на которые они указывают. Тем не менее, возможно, вы предоставляете компаратор. Если это так, игнорируйте эту пулю.
• Прибегание вектора каждый раз при выполнении итерации цикла O (nLog (n)), где вставка в очередь с приоритетами и поддержание отсортированного порядка — O (Log (n))
• Так как вы сортируете по указателям, индекс 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), что вам не нужно делать, так как эти переменные-члены были общедоступны в вашем родительском классе. Сделайте функции getLeft и getRight виртуальными и удалите объявления для left и right в классе parentNode вместе с их соответствующими функциями 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 указывали на несуществующую память или память, которая не принадлежала им.

Надеюсь, это помогло …