1

在使用链表（实际上是一个内部类Node）实现优先级队列时，我对insert()and方法进行了如下编码。它使用惰性方法保持项目无序，然后仅在发生or调用max()时才通过它们搜索最大元素。max()deleteMax()

public class LinkedListMaxPQ<Item extends Comparable<Item>>{
    private int N;
    private Node head;

   public void insert(Item item) {
       Node old = head;
       head = new Node();
       head.item = item;
       head.next = old;
       N++;
    }

    public Item max() {
        Item maxitem = (Item) this.head.item;
        for(Node t=head.next;t!=null;t=t.next){
            if(gt(t.item,maxitem)){
            maxitem = (Item) t.item;
            }
        }
        return maxitem;
    }
    private boolean gt(Comparable x,Comparable y){
    return x.compareTo(y) > 0;
}



   private class Node<Item extends Comparable<Item>>{
      Item item;
      Node next;
   }

}

我想知道为什么我需要演员表Item maxitem = (Item) this.head.item？由于该类使用泛型类型Item which extends Comparable并且内部类也使用 Item extends Comparable ，因此人们会认为这样的强制转换是不必要的。

如果我省略演员表

Item maxitem = this.head.item;

编译器会抱怨类型不匹配

类型不匹配：无法从 Comparable 转换为 Item

有人可以解释为什么会这样吗？

4

4 回答 4

2

因为 JavaItem在类声明中被视为类型参数（与 中声明的类型参数Node无关）。ItemLinkedListMaxPQ<Item extends Comparable<Item>>

该声明——

private class Node<Item extends Comparable<Item>>{
    Item item;
    Node next;
}

告诉编译器您正在创建一个私有类，该类有一个名为 的类型参数Item，它是 的子类型Comparable<Item>。在类型擦除期间，这Item将被其类型的边界替换Comparable。这就是为什么你需要那个明确的演员。

此外，以下行 -

private Node head;

创建一个原始类型Node，没有任何可用的类型信息。您应该收到此行的警告。

要解决此问题，请声明head如下 -

private Node<Item> head;

并通过以下方式创建一个实例 -

head = new Node<Item>();  // if you are using jdk 6 or lesser
head = new Node<>();  // if you are using jdk 7

以类似的方式更新所有Node引用，您的警告应该消失了。

如果您需要进一步澄清类型参数绑定，您可以阅读我的一篇博客文章，其中我试图解释类型参数绑定的工作原理。

于 2013-08-21T12:59:32.547 回答
1

你需要

private class Node{
...

通过将其设置为：

private class Node<Item extends Comparable<Item>>{

您正在创建一个新的泛型类型Item，它与封闭类的类型不同Item，即使它具有相同的名称。

于 2013-08-21T13:00:49.930 回答
0

它很简单，因为您在创建头部时没有指定类型，node.head 具有类型对象

这应该可以解决您的问题

public class LinkedListMaxPQ<Item extends Comparable<Item>>{
    private int N;
    private Node<Item> head;

   public void insert(Item item) {
       Node<Item> old = head;
       head = new Node<Item>();
       head.item = item;
       head.next = old;
       N++;
    }

    public Item max() {
        Item maxitem =  this.head.item;
        for(Node<Item> t=head.next;t!=null;t=t.next){
            if(gt(t.item,maxitem)){
            maxitem =  t.item;
            }
        }
        return maxitem;
    }



   private class Node<Item extends Comparable<Item>>{
      Item item;
      Node<Item> next;
   }

}
于 2013-08-21T13:07:37.813 回答
0

正如@JonathanDrapeau 指出的那样，答案很简单：将t变量的声明更改为Node<Item>：

    for (Node<Item> t = head.next; t != null; t = t.next){
        if (gt(t.item, maxitem)){
        maxitem = t.item;
        }
    }

第二个选项：删除类型参数表单Node类定义，如果要引用与父LinkedListMaxPQ类中相同的类型：

public class LinkedListMaxPQ<Item extends Comparable<Item>> {

    ...

    private class Node {
        Item item;
        Node next;
    }
}
于 2013-08-21T13:22:42.153 回答