Алгоритм кодирования Хаффмана, дающий странное дерево (Java) - PullRequest
Новая
       28

Алгоритм кодирования Хаффмана, дающий странное дерево (Java)

1 голос
/ 05 октября 2011

Я пробовал здесь много разных вещей и не могу заставить его работать. Ввод был "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);
}

Было бы совершенно удивительно, если бы кто-то мог мне помочь, я невероятно, невероятно расстроен.

Спасибо!

1 Ответ

3 голосов
/ 05 октября 2011

Проблема в getSortedLinkedList. Похоже, что вы меняете значения частоты, а не сами узлы, поэтому указатели не перемещаются со значением частоты.

Как правило, когда вы имеете дело со связанными списками, действительно полезно рисовать картинки каждого этапа: 

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

первый шаг: 

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

сортировка: без изменений

следующий шаг: 

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

sort делает это: 

    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
...