首页 文章

具有霍夫曼树的优先级队列

提问于
浏览 次
5

我试图通过读取文件并计算每个字母空格符号的频率等来创建一个霍夫曼树 . 我正在使用Priorityqueue将项目从最小到最大排队但是当我将它们插入队列时它们不能正确排队这是我的代码 . 包霍夫曼;

import java.io.FileNotFoundException; import java.io.FileReader; import java.util.ArrayList; import java.util.PriorityQueue; import 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;私人的

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

}

如何获得优先级以使用频率编号将它们从最小到最大排队？

java queue huffman-code

3 回答

  • 4

    实际上你错过了实现 compareTo 方法来使你的对象有效地比较 .

    正如文档所述， compareTo 方法应该

    返回负整数，零或正整数，因为此对象小于，等于或大于指定对象 .

    这意味着在您的情况下，您应该执行以下操作：

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

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

    但是请注意，可比较的类型有一个更好的泛型类型： Comparable<T> 所以你可以避免在 arg0 上使用静态类型安全的对象：#1774041_对象：

    class Frequency implements Comparable<Frequency> {   
  public int compareTo(Frequency f2) {
    // directly compare
  }
}
    回复于
  • 2

    我认为“自动生成的方法存根”需要用“compareTo”的实际实现填充，以满足可比较的东西的要求，我认为PriorityQueue将依赖它 . 实现可能是“n <arg0”，并从Object进行适当的向下转换 .

    回复于
  • 2

    Priority Queue，就像数据结构一样，基于排序的概念 - 当您想要以某种方式排序元素时，您使用这样的结构 - 哪些元素比其他元素更重要，等等 .

    在Java中，排序对象通常以两种方式之一完成 - 您的对象实现 Comparable 接口，或者提供 Comparator<E> ，它知道如何订购 E 类型的对象 .

    要确定哪个对象是"more important"而不是另一个对象，将调用 compareTo() 方法 . 这个方法有一个非常简单的 Contract ：

    将此对象与指定的订单对象进行比较 . 返回负整数，零或正整数，因为此对象小于，等于或大于指定对象 .

    您的 Frequency.compareTo() 实现始终返回0以进行比较 . 因此，您指定所有 Frequency 对象都等于任何其他 Frequency 对象 . 这显然不是你想要的 .

    回复于

相关问题