解碼哈夫曼樹

我試圖解碼格式的哈夫曼樹：我使用的是實施這裏找到解碼哈夫曼樹

001A1C01E01B1D

：Efficient way of storing Huffman tree編碼在上面的表格樹並對其進行解碼，以及。

這是我實現它：

HuffmanNode* HuffmanTree::decodeTree(string tree, int idx) { 
    cout << idx << endl; 
    if (tree[idx] == '1') { 
     idx += 2; 
     return new HuffmanNode(tree[idx - 1]); 
    } 
    else { 
     if (idx != tree.length() - 1) { 
      idx++; 
      HuffmanNode* leftChild = decodeTree(tree, idx); 
      idx++; 
      HuffmanNode* rightChild = decodeTree(tree, idx); 
      return new HuffmanNode(leftChild, rightChild); 
     } 
     else 
      return new HuffmanNode(tree[idx]); 
    } 
}

我得到一個訪問衝突寫的位置時的功能開，（在「迴歸新HuffmanNode（樹[IDX - 1]）;」），我希望最終的回報會成爲樹的根源，但經過進一步檢查，似乎並非如此。任何人都可以給我一些指點嗎？（沒有雙關語意）

來源

2015-04-02 Taylor Bishop

你期待IDX的遞歸調用之間共享？如果是這樣的話，你需要將它作爲參數列表中的參考。你也可以做一些額外的安全檢查（有適當的錯誤）。例如，它會被任何以「1」結尾的字符串絆倒。 – Dave 2015-04-02 19:06:39

與您的代碼的問題是，idx不遞歸運行中修改。它傳遞到功能int &：HuffmanNode* HuffmanTree::decodeTree(string tree, int &idx)

還有一個更錯誤在你的代碼，這使得它出現段錯誤：不是

if (tree[idx] == '1') { 
    idx += 2; 
    return new HuffmanNode(tree[idx - 1]); 
}

你應該有

if (tree[idx] == '1') { 
    ++idx; 
    return new HuffmanNode(tree[idx]); 
}

另一個1是被添加到索引第二塊內：

idx++; 
HuffmanNode* leftChild = decodeTree(tree, idx); 
idx++; 
HuffmanNode* rightChild = decodeTree(tree, idx);

另外，請考慮做一件事情，類似於您鏈接的示例：將引用傳遞給字符串迭代器（或istringstream或其他流），並且不傳遞索引：HuffmanNode* HuffmanTree::decodeTree(std::string::const_iterator &tree)。

而且，你不必做這樣if (idx != tree.length() - 1)檢查該樹是良好的。您可能還會在功能開始時執行此操作，以檢查輸入中的錯誤，並檢查當前符號是'0'還是'1'。

來源

2015-04-02 19:56:42 Kolmar

如果它的格式正確，你的意思是什麼？它必須有某種基本情況，它不會停止調用該函數，並可能超出字符串的末尾？我嘗試過使用迭代器，但我遇到了同樣的問題 - 我無法知道輸入流的結束時間，以及我是否完成了在樹中的讀取。 – 2015-04-05 20:44:13

@TaylorBishop不，如果實現中沒有錯誤，並且編碼的字符串是正確的，則此算法無法讀取超出字符串的末尾。看看你鏈接的帖子。可以將實際數據放在與樹相同的字符串/數組中。因此，您可以從解碼樹的索引開始解碼數據。編碼樹中的所有內部節點都標記爲0，葉子標記爲1.在讀取標記爲1的節點之後，您不再進行遞歸調用。這是基本情況。 – Kolmar 2015-04-05 22:04:38

解碼哈夫曼樹

回答

相關問題