符号排名 table

Question

我如何 return 少于给定键的键数？我只是不知道从哪里开始。我有基本的开始，但除此之外我不知道从哪里开始

public class LinkedListST<Key extends Comparable<Key>, Value> {
    private Node first;      // the linked list of key-value pairs

    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;

        public Node(Key key, Value val, Node next)  {
            this.key  = key;
            this.val  = val;
            this.next = next;
        }
    }

public int rank (Key key) {
        if(key == null) return 0;
        //TODO
    }

编辑：这就是我目前所拥有的，但是我的 for 循环是错误的并且给我错误

public int rank (Key key) {
    int count = 0;
    for(Node x = first; x != null; x = x.next){
        if(x.next < key){
            count++;
        }
    return count;
    }
}

Answer 1

伪代码：

initialize counter to zero
loop over all nodes, starting at first:
   if node's key < key:
       increment count
return count

这应该让你开始。

编辑

好的，所以您实际上已经发布了编写代码的真实尝试，这是在 Stack Overflow 上获得真正帮助的秘诀。

您的代码，正确缩进，...

public int rank (Key key) {
    int count = 0;
    for(Node x = first; x != null; x = x.next){
        if (x.next < key){
            count++;
        }
        return count;  // <-- Note!
    }
}

... 显示循环内的 return 语句。不完全是你想要的。

if (x.next < key)也让你伤心，因为你需要比较Key和Key，而不是Node和Key。

最后，Comparable接口需要Key实现compareTo(Key other)方法。像这样使用：

key.compareTo(x.key)

这个 return 是 -1、0 或 1，具体取决于哪个更大或是否相同。所以你真的想要：

if (key.compareTo(x.key) < 0) {

或

if (key.compareTo(x.key) > 0) {

留给学生练习。

Answer 2

您的代码快完成了，但是您遇到了三个问题：

return 语句在 for 循环内。如果您更正了缩进，就会看到。把它移到外面。
您不想比较 x.next 和 key。您想要将 x.key 与 key 参数进行比较。
您不能使用 < 运算符进行比较。由于 Key 是 Comparable，您可以通过调用 compareTo().

这是更新后的代码：

public int rank (Key key) {
    int count = 0;
    for (Node x = first; x != null; x = x.next) {
        if (x.key.compareTo(key) < 0){
            count++;
        }
    }
    return count;
}

符号排名 table

Rank for symbol table

java

symbol-table