2

私はこのハフマンツリービルダーに取り組んできました:

// variable al is an array list that holds all the different characters and their frequencies
// variable r is a Frequency which is supposed to be the roots for all the leaves which holds a null string and the frequencies of the combined nodes removed from the priority queue
public Frequency buildTree(ArrayList<Frequency> al)
{
    Frequency r = al.get(0);
    PriorityQueue<Frequency> pq = new PriorityQueue<Frequency>();
    for(int i = 0; i < al.size(); i++)
    {
        pq.add(al.get(i));          
    }
    /*while(pq.size() > 0)
    {
        System.out.println(pq.remove().getString());
    }*/

    for(int i = 0; i < al.size() - 1; i++)
    {   
       Frequency p = pq.remove(); 
       Frequency q = pq.remove();
       int temp = p.getFreq() + q.getFreq();
       r = new Frequency(null, temp);
       r.left = p; 
       r.right = q;
       pq.add(r);  // put in the correct place in the priority queue
    }
    pq.remove(); // leave the priority queue empty
    return(r); // this is the root of the tree built

}

コードが英語でやろうとしていることは

すべての文字を頻度とともに優先キューに最低頻度から最高頻度まで追加します。次に、ArrayList al (すべての文字を含む) のサイズについて、最初の 2 つをデキューし、デキューされた 2 つのノードである左と右の子を持つように新しいルートを設定し、デキューされた 2 つの結合された頻度で新しいルートを挿入します。アイテムを優先キューに入れます。メソッドが行うべきことはそれだけです。

このメソッドはハフマン ツリーを構築することになっていますが、正しく構築されていません コードに従ってツリーを手動で構築しましたが、紙に書かれていることはプログラムとは異なります。別のプログラムによって生成された正解は、私の解と同じではありません。入力データ (文字と頻度) は次のとおりです。

a 6
b 5
space 5
c 4
d 3
e 2
f 1

周波数はすでにここにあるので、それから読んでいるテキストは問題ではありません。必要なのは、これらの周波数からツリーを構築することだけです。

4

2 に答える 2

2

Java の詳細を無視して、平易な言葉でアルゴリズムを書き出すことはできますか? これは、どこで問題が発生しているか (アルゴリズムまたはそれを実装するコードのいずれか) を理解するのに役立ちますが、人々があなたを助けるのにも役立ちます。

アルゴリズムに関係なく、ルート ノードが の 2 番目の要素から始まることを本当に意図していますArrayListか? Lists は、1 ではなく 0 から始まるインデックスが付けられますList.get(1)。2 番目の要素を返します。

public Frequency buildTree(ArrayList<Frequency> al) {
    Frequency r = al.get(1);
于 2010-07-23T01:50:03.987 に答える
0

これはいつですか？実装の機能ビットごとに単体テストの作成を開始します-そのようにして問題を公開できるかもしれません。また、この混乱のフォーマットを修正してください

"public Frequency buildTree(ArrayList al) { Frequency r = al.get(1); PriorityQueue pq = new PriorityQueue(); for(int i = 0; i < al.size(); i++) { pq.add(al .get(i)); } /while(pq.size() > 0) { System.out.println(pq.remove().getString()); }/"

編集-フォーマット後-コードを読むのに苦労しています。変数名をわかりやすいものにします。「r」は何も教えてくれませんし、「al」も教えてくれません。エンコードしているテキストが何であるかを知るのに役立ちます....

于 2010-07-23T00:22:59.770 に答える