霍夫曼編碼器 - 遞歸，編碼功能失敗

Question

我正在使用霍夫曼代碼生成器。以下是我構建樹的功能。該樹基於對象指針的矢量。我已檢查，它似乎工作正常。我現在想通過指針位置pointerVect [0]這應該是樹的根到我的Huffman編碼下面的遞歸函數，但由於某種原因，它不能正常工作，因爲當我嘗試打印的內容代碼存儲的地圖不會打印出來。

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) 
} 

Answer 1

我懷疑是你的第一個功能「createTree」

正如我最初的評論表明，你應該考慮使用優先級隊列由於各種原因。這裏是我注意到的問題的快速列表

• 您正在對指針向量進行排序。所以指針將根據它們的地址值進行排序，而不是他們指向的對象。但是，您可能提供了一個比較器。如果是這種情況，請忽略此項目符號。
• 使用vector while each循環迭代爲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（child class）的對象時，它將調用父類的（asciiChar）getLeft和getRight函數，它將始終返回NULL。你在你的子類（parentNode）中聲明瞭一個左和右，你不需要這樣做，因爲這些成員變量在父類中是公共的。使getLeft和getRight函數變爲虛擬，並刪除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中的這些指針然後指向不存在的內存或不屬於它們的內存。

希望這有助於...