霍夫曼樹代碼使用std :: unique_ptr不工作

Question

我正在爲一個家庭作業構建一個霍夫曼編碼器，我需要知道爲什麼我的代碼不工作。我在早期版本中詢問過其他地方，並得到了一個提示：使用std :: unique_ptr，以便從指針中引用的節點在從矢量中刪除時不會從內存中刪除。

這是我到目前爲止有：

#include <iostream>  // Allows the use of std::cout >> and std::cin <<. 
#include <string>  // Allows the use of getline(). 
#include <fstream>  // Allows the use of file I/O. 
#include <utility>  // Allows the use of std::bitset. 
#include <vector>  // Allows the use of vectors. 
#include <algorithm> // Allows the use of std::sort(). 
#include <memory>  // Allows the use of std::unique_ptr. 

struct node 
{ 
    char data; 
    int frequency; 
    std::bitset<1> code; 
    node *left; 
    node *right; 
    bool operator<(const node &temp) const {return frequency < temp.frequency;} 
}; 

std::vector<node> nodeVector; 

void getHuffmanData() 
{ 
    std::ifstream inStream; 
    int size; 
    int tempFrequency; 
    char tempData; 
    node tempNode; 

    inStream.open("huff-source.txt"); 

    if (inStream.fail()) 
    { 
     std::cout << "Failure opening input file.\n"; 
     exit(1); 
    } 

    inStream >> size; 

    while (inStream.peek() != EOF) 
    { 
     inStream >> tempData; 
     inStream >> tempFrequency; 
     tempNode.data = tempData; 
     tempNode.frequency = tempFrequency; 
     nodeVector.push_back(tempNode); 
    } 
    inStream.close(); 
} 

node buildHuffmanTree()  // Returns the root node, which points to all other nodes. 
{ 
    node tempNode; 
    node *x, *y; 
    std::unique_ptr<node> a (new node); 
    std::unique_ptr<node> b (new node); 

    while (!nodeVector.empty()) 
    { 
     std::sort(nodeVector.begin(), nodeVector.end()); 
     *a = nodeVector.front(); 
     x = a.release(); 
     tempNode.left = x; 
     nodeVector.erase(nodeVector.begin()); 
     *b = nodeVector.front(); 
     y = b.release(); 
     tempNode.right = y; 
     nodeVector.erase(nodeVector.begin()); 
     tempNode.frequency = x->frequency + y->frequency; 
     nodeVector.push_back(tempNode); 
     std::sort(nodeVector.begin(), nodeVector.end()); 
     if (nodeVector.size() == 1) {break;} 
    } 
    return tempNode; 
} 


int main() 
{ 
    node test; 
    getHuffmanData(); 
    test = buildHuffmanTree(); 
    std::cout << "Press 'Enter' to continue..."; 
    std::cin.get(); 

    return 0; 
} 

我的樣本輸入文件，如下所示：

4 
a 119 
b 20 
c 44 
d 127 

現在，它運行後，會出現我得到在Xcode中的錯誤信息一次通過buildHuffmanTree（）。它在包含'* a = nodeVector.front（）;'的行中說'線程1：EXC_BAD_ACCESS（代碼= 1，地址= 0x0）'。我怎麼會去修正循環，使該函數可以返回一個合適的樹，像這樣的說明：

310 
/ \ 
127 183 
d / \ 
    64 119 
/\ a 
    20 44 
    b c 

Answer 1

你試圖寫一個復引用空指針。 讓我通過你的代碼來展示錯誤。

node buildHuffmanTree()  // Returns the root node, which points to all other nodes. 
{ 
    node tempNode; 
    node *x, *y; 
    std::unique_ptr<node> a (new node); // a now points to a node in the heap 
    std::unique_ptr<node> b (new node); // b now points to a node in the heap 

    while (!nodeVector.empty()) 
    { 
     std::sort(nodeVector.begin(), nodeVector.end()); 
     *a = nodeVector.front(); // you copy the first node in the vector into the node 
           // on the heap pointed to by a 
     x = a.release();   // x now points to the node on the heap pointed to by a 
           // a now holds a nullptr and will not delete the node on the heap 
     tempNode.left = x;  // tempNode.left now points to the node on the heap 
     nodeVector.erase(nodeVector.begin()); 
     . . . 
     tempNode.frequency = x->frequency + y->frequency; 
     nodeVector.push_back(tempNode); 
     std::sort(nodeVector.begin(), nodeVector.end()); 
     if (nodeVector.size() == 1) {break;} 
    } 
    return tempNode; 
} 

現在我們經過while循環再次

while (!nodeVector.empty()) 
    { 
     std::sort(nodeVector.begin(), nodeVector.end()); 
     *a = nodeVector.front(); // a now holds a nullptr, so this is BAD 
     . . . 
    } 

我相信你沒有完全瞭解使用std::unique_ptr。 你可能想的std::unique_ptr s到所有node對象 集合整個程序中堅持讓你擁有一套獨特的，不會消失的節點。 要將這些節點鏈接到樹中，請使用常規指針（或者可能共享）。 當包含指針 的對象/代碼塊單獨負責刪除指針指向的分配內存時，應使用唯一指針。