Rang für Symboltabelle

Question

Wie würde ich die Anzahl der Schlüssel zurückgeben, die kleiner als der angegebene Schlüssel ist? Ich weiß einfach nicht, wo ich anfangen soll. Ich habe die Startbasis aber anders als das ich weiß nicht, wo

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 
    } 

EDIT beginnen: Das ist, was ich bisher haben aber meine for-Schleife ist falsch und gibt mir Fehler

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

Pseudo code:

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

Das sollte Sie beginnen.

---

EDIT

Ok, so haben Sie geschrieben tatsächlich einen echten Versuch, den Code zu schreiben, die das Geheimnis ist echte Hilfe auf Stack-Überlauf zu bekommen.

Ihr Code mit dem richtigen Einzug, ...

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

... zeigt eine return-Anweisung innerhalb der Schleife. Nicht genau was du wolltest.

Die if (x.next < key) auch gibt Ihnen Kummer, weil Sie Key mit Key, nicht Node mit Key vergleichen müssen.

Schließlich erfordert die Comparable Schnittstelle die Key Implementierung der compareTo(Key other) Methode. Verwendet wie:

key.compareTo(x.key) 

Das gibt ein -1, 0 oder 1 je nachdem, welche größer ist, oder wenn sie gleich sind. Sie wollen also wirklich:

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

oder

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

Übung links nach Student.

Answer 2

Ihr Code ist fast da, aber Sie haben drei Probleme:

• Die return Aussage ist in der for Schleife. Wenn Sie die Einrückung korrigiert haben, würden Sie das sehen. Verschiebe es nach draußen.
• Sie möchten x.next nicht mit key vergleichen. Sie möchten x.key mit dem Parameter key vergleichen.
• Sie können nicht mit dem Operator < vergleichen. Da KeyComparable ist, können Sie vergleichen, indem Sie compareTo() anrufen.Hier

ist der aktualisierte Code:

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