霍夫曼編碼算法給怪樹（Java）

我一直在嘗試很多不同的東西在這裏，似乎無法得到它的工作。輸入是「abbcccddddeeeee」，它給出了鏈接列表a，b，c，d，e，其頻率分別爲1,2,3,4,5。霍夫曼編碼算法給怪樹（Java）

出於某種原因，不過，這似乎是給我基於很多不同的測試下面的樹我已經運行：

    f15 
       / \ 
       f6 f9 
      /\ 
       d4 e5 
      /\ 
      f3 c3 
     /\ 
     a1 b2 

public static HTree createHuffmanTree(HLinkedList list) 
{ 
    while (list.size() != 1) 
    { 
    list = getSortedLinkedList(list); 
    HTreeNode p = list.head; 
    HTreeNode q = p.next; 
    HTreeNode r = new HTreeNode('f'); 
    r.left = p; 
    r.right = q; 
    r.frequency = (p.frequency + q.frequency); 
    list.insertIntoPosition(r, 2); 
    list.remove(0); 
    list.remove(0); 
    list = getSortedLinkedList(list); 
    } 
    return new HTree(list.head); 
}

這將是絕對驚人的，如果有人可以幫助我，我令人難以置信的令人難以置信的沮喪。

謝謝！

來源

2011-10-05 Andrew Latham

問題出在getSortedLinkedList。看起來你正在交換頻率值而不是節點本身，所以指針不會隨頻率值移動。

一般來說，當你在處理鏈表它真的有用提請各階段的照片：

a1->b2->c3->d4->e5

第一步：

f3->c3->d4->e5 
    /\ 
a1 b2

排序：沒有變化

下一個步驟：

f6->d4->e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

排序做到這一點：

d4->e5->f6 (forgot to move child nodes with frequency) 
    /\ 
    f3 c3 
    /\ 
a1 b2

下一步：

 f9->f6 
     /\ 
    d4 e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

排序：

 f6->f9 (forgetting to move child nodes with frequency) 
     /\ 
    d4 e5 
    /\ 
    f3 c3 
    /\ 
a1 b2

最後一步：

來源

2011-10-05 07:48:41 Skizz

太感謝你了！ :) –

霍夫曼編碼算法給怪樹（Java）

回答

相關問題