首先,我必须提到的是,在阅读了大量问题和教程并观看了一些视频后,问题仍然没有解决。
我是一名Java中级程序员,我编写了一些用于比较优先级队列中的元素的代码,其中元素的保存方式类似于[Comparable element, intpriority]。显然,更高的优先级将被弹出。
问题是: 我修改了代码,使第一个元素具有最高优先级,但它不起作用!我已经缩小了范围,当比较前 2 个元素时,compareTo 方法返回 0,但它不应该返回 0,因此代码失败!
这个类的入栈时间为 O(1),出栈时间为 O(n):
public class PriorityQueueU<T>
{
public class PriorityPair implements Comparable
{
public Comparable element;
public Comparable priority;
public PriorityPair(Comparable element, int priority){
this.element = element;
this.priority = priority;
}
public Comparable<T> getElemet(){
return this.element;
}
public Comparable<T> getPriority(){
return this.priority;
}
public int compareTo(Comparable a)
{
PriorityPair p2 = (PriorityPair)a;
return ((Comparable)priority).compareTo(p2.priority);
}
public String toString(){
String s1 = this.element.toString();
String s2 = this.priority.toString();
String res = "[ " + s1 + ", " + s2 + " ]" ;
return res;
}
public int compareTo(Object o)
{
// TODO Auto-generated method stub
return 0;
}
}
private LinkedList data;
public PriorityQueueU()
{
data = new LinkedList();
}
public void pushUnsorted(Comparable<T> o, int priority)
{
PriorityPair paired = new PriorityPair(o, priority);
data.addLast(paired);
}
public Comparable popUnsorted()
{
int index = 0;
for (int i = 0; i < this.data.size() - 1; i++)
{
if (((PriorityPair) this.data.get(i)).compareTo(this.data.get(i + 1)) < 0)
{
index = i + 1;
}
}
PriorityPair pp = (PriorityQueueU<T>.PriorityPair) this.data.get(index);
this.data.deleteIt(index);
return pp.getElemet();
}
public String toString(){
return this.data.toString();
}
}
}
这是测试行为的代码:
PriorityQueueU<T> unSortedPQ = new PriorityQueueU<>();
unSortedPQ.pushUnsorted( (Comparable<T>) "a", 1000);
unSortedPQ.pushUnsorted((Comparable<T>) "b", 200);
unSortedPQ.pushUnsorted((Comparable<T>) "j", 900);
unSortedPQ.pushUnsorted((Comparable<T>) "r", 9);
unSortedPQ.pushUnsorted((Comparable<T>) "z", 6);
System.out.println("the UNsorted priority Q: ");
System.out.println(unSortedPQ);
System.out.println("*#------------------END OF PUSH-----------------#*");
System.out.println();
System.out.println("the priority Q: " + unSortedPQ);
System.out.println("popped item is: " + unSortedPQ.popUnsorted());
// System.out.println("top of the priority queue is: " + uPriorityQueueU.top());
System.out.println();
System.out.println("the UNsorted priority Q: ");
System.out.println(unSortedPQ);
System.out.println("*#------------------END OF POP-----------------#*");
System.out.println();
非常感谢。
附注请记住,也许我错了,问题出在其他地方! 当前行为:它弹出 j,它是列表中第二高的元素。我已经知道,弹出时,该元素也必须从优先级队列中删除,该队列存储在链表中。我确保链接列表中的删除操作正确,但如有必要,请毫不犹豫地索取代码。
最佳答案
为了使 compareTo
工作,您应该实现 Comparable
接口(interface)提供的方法。
public interface Comparable<T> {
public int compareTo(T o);
}
正如我们从上面的代码中看到的,Copmarable
支持泛型。如果您没有指定要比较的对象类型(保持原样),它将默认为 Object
,它会执行此操作(来自您的代码):
public int compareTo(Object o)
{
// TODO Auto-generated method stub
return 0;
}
因此,您要么使用泛型,要么为 compareTo(Object o)
编写逻辑。
关于java - CompareTo 返回值不正确,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43718718/