5

ファイルを読み込んで各文字スペース記号の頻度をカウントするなどして、ハフマン ツリーを作成しようとしています。Priorityqueue を使用して、アイテムを最小から最大までキューに入れていますが、それらをキューに挿入すると、正しくキューに入れられません。これが私のコードです。ハフマンパッケージ;

import java.io.FileNotFoundException; java.io.FileReader をインポートします。import java.util.ArrayList; java.util.PriorityQueue をインポートします。java.util.Scanner をインポートします。

公開クラス ハフマン {

public ArrayList<Frequency> fileReader(String file)
{
    ArrayList<Frequency> al = new ArrayList<Frequency>();
    Scanner s;
    try {

        s = new Scanner(new FileReader(file)).useDelimiter("");
        while (s.hasNext())
        {
            boolean found = false;
            int i = 0;
            String temp = s.next();
            while(!found)
            {


                if(al.size() == i && !found)
                {
                    found = true;
                    al.add(new Frequency(temp, 1));
                }
                else if(temp.equals(al.get(i).getString()))
                {
                    int tempNum = al.get(i).getFreq() + 1;
                    al.get(i).setFreq(tempNum);
                    found = true;
                }
                i++;

            }



        }
    } catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    return al;
}
public void buildTree(ArrayList<Frequency> al)
{
    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());
    }
}
public void printFreq(ArrayList<Frequency> al)
{
    for(int i = 0; i < al.size(); i++)
    {
        System.out.println(al.get(i).getString() + "; " + al.get(i).getFreq());
    }
}

}

buildTree() メソッドでは、私が問題を抱えている場所です。私がやろうとしているのは、文字/スペース/記号と頻度を int として保持する頻度オブジェクトをキューに入れることです。頻度クラスはこれです。public class Frequency は Comparable { private String s; を実装します。プライベート int n;

Frequency(String s, int n)
{
    this.s = s;
    this.n = n;
}
public String getString()
{
    return s;
}
public int getFreq()
{
    return n;
}
public void setFreq(int n)
{
    this.n = n;
}
@Override
public int compareTo(Object arg0) {
    // TODO Auto-generated method stub
    return 0;
}

}

最小から最大の順にキューに入れるために頻度番号を使用するようにpriorityqueueを取得するにはどうすればよいですか?

4

3 に答える 3

4

compareTo実際、オブジェクトを効果的に比較できるようにするためのメソッドを実装できませんでした。

compareToドキュメントに記載されているように、この方法は

このオブジェクトは指定されたオブジェクトよりも小さいか、等しいか、または大きいため、負の整数、ゼロ、または正の整数を返します。

これは、あなたの場合、次のようなことをする必要があることを意味します。

public int compareTo(Object arg0)
{
  Frequency other = (Frequency)arg0;

  return n < other.n ? -1 : (n == other.n ? 0 : 1);
}

ただし、compareには、望ましいジェネリック型があるComparable<T>ことに注意してください。したがって、キャストを回避して、静的型の安全性を備えarg0たオブジェクトにすることもできます。Frequency

class Frequency implements Comparable<Frequency> {   
  public int compareTo(Frequency f2) {
    // directly compare
  }
}
于 2010-07-22T01:01:47.537 に答える
2

PriorityQueueが依存すると思われる、Comparableであるための要件を満たすには、「自動生成されたメソッドスタブ」に「compareTo」の実際の実装を入力する必要があると思います。実装はおそらく"n<arg0"になり、Objectから適切にダウンキャストされます。

于 2010-07-22T00:57:41.970 に答える
2

Priority Queueは、データ構造と同様に、順序付けの概念に基づいています。特定の方法で要素を順序付けたい場合に、このような構造を使用します。どの要素が他の要素よりも重要であるかなどです。

Java では、通常、オブジェクトの順序付けは 2 つの方法のいずれかで行われます。オブジェクトがComparableインターフェイスを実装するComparator<E>か、タイプ のオブジェクトを順序付けする方法を知っている を指定しますE。

どのオブジェクトが他のオブジェクトよりも「重要」であるかを判断するために、compareTo()メソッドが呼び出されます。このメソッドのコントラクトは非常に単純です。

このオブジェクトと指定されたオブジェクトを比較して順序付けます。このオブジェクトが指定されたオブジェクトより小さいか、等しいか、または大きいので、負の整数、ゼロ、または正の整数を返します。

の実装はFrequency.compareTo()、比較のために常に 0 を返します。したがって、すべてのFrequencyオブジェクトが他のFrequencyオブジェクトと等しいことを指定しています。これは明らかにあなたが望むものではありません。

于 2010-07-22T01:03:35.327 に答える