1

私はここでさまざまなことを試してきましたが、うまくいかないようです。入力は「abbcccddddeeeee」で、リンクされたリスト a、b、c、d、e がそれぞれ頻度 1、2、3、4、5 で返されます。

ただし、何らかの理由で、実行したさまざまなテストに基づいて、次のツリーが表示されるようです。

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

誰かが私を助けてくれたら最高です。私は信じられないほど、信じられないほどイライラしています。

ありがとうございました！

4

1 に答える 1

3

問題はにあり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

最終段階：

             f15
             /\
           f6  f9
           /\
         d4  e5
         /\
       f3  c3
       /\
     a1  b2
于 2011-10-05T07:48:41.687 に答える