hinzufügen und entfernen von eine einfach verknüpfte Liste

Dachte ich, ich hätte Verständnis, das in meiner vorherigen Frage zu verknüpften Listen, aber ich war schrecklich falsch, ich bin genauso verloren wie ich war, als ich anfangs gepostet.

Ich merke, dass ich technisch zwei Fragen, die aber hoffentlich immer mindestens sollte man die anderen einfach (vorausgesetzt Sie sind einfach in umgekehrter Reihenfolge).

Ich habe 3 Klassen, die bereits mir gegeben, Sie sind:

SLinkedList.java

package chapter3.linkedList;

    public class SLinkedList<V> {
        //instance variables.  Add the tail reference.
        protected Node<V> head, tail;
        protected long size;

        //methods, empty list constructor first
        public SLinkedList () {
            head = null;
            tail = null;
            size = 0;
        }  //end constructor of a SLinkedList

        //method to add nodes to the list.  Storage space for the node
        //is already allocated in the calling method
        public void addFirst (Node<V> node) {
            //set the tail only if this is the very first node
            if (tail == null)
                tail = node;
            node.setNext (head);    //make next of the new node refer to the head
            head = node;            //give head a new value

            //change our size
            size++;
        }  //end method addFirst

        //addAfter - add new node after current node, checking to see if we are at the tail
        public void addAfter (Node<V>currentNode, Node<V>newNode) {
            if (currentNode == tail)
                tail = newNode;
            newNode.setNext (currentNode.getNext ());
            currentNode.setNext (newNode);

            //change our size
            size++;
        }  //end method addAfter

        //addLast - add new node after the tail node.  Adapted from Code Fragment 3.15, p. 118.
        //Mike Qualls
        public void addLast (Node<V> node) {
            node.setNext (null);
            tail.setNext (node);
            tail = node;
            size++;     
        }  //end method addLast

        //methods to remove nodes from the list.  (Unfortunately, with a single linked list
        //there is no way to remove last.  Need a previous reference to do that.  (See
        //Double Linked Lists and the code below.)
        public Node<V> removeFirst () {
            if (head == null)
                System.err.println("Error:  Attempt to remove from an empty list");

            //save the one to return
            Node<V> temp = head;

            //do reference manipulation
            head = head.getNext ();
            temp.setNext(null);
            size--;

            return temp;

        }  //end method removeFirst

        //remove the node at the end of the list.  tail refers to this node, but
        //since the list is single linked, there is no way to refer to the node
        //before the tail node.  Need to traverse the list.
        public Node<V> removeLast () {
            ////declare local variables/objects
            Node<V> nodeBefore;
            Node<V> nodeToRemove;

            //make sure we have something to remove
            if (size == 0)
                System.err.println("Error:  Attempt to remove fron an empty list");

            //traverse through the list, getting a reference to the node before
            //the trailer.  Since there is no previous reference.
            nodeBefore = getFirst ();

            //potential error  ??  See an analysis and drawing that indicates the number of iterations
            //9/21/10.  size - 2 to account for the head and tail nodes.  We want to refer to the one before the
            //tail.
            for (int count = 0; count < size - 2; count++)
                nodeBefore = nodeBefore.getNext ();

            //save the last node
            nodeToRemove = tail;

            //now, do the pointer manipulation
            nodeBefore.setNext (null);
            tail = nodeBefore;
            size--;

            return nodeToRemove;

        }  //end method removeLast

        //method remove.  Remove a known node from the list.  No need to search or return a value.  This method
        //makes use of a 'before' reference in order to allow list manipulation.
        public void remove (Node<V> nodeToRemove) {
            //declare local variables/references
            Node<V> nodeBefore, currentNode;

            //make sure we have something to remove
            if (size == 0)
                System.err.println("Error:  Attempt to remove fron an empty list");

            //starting at the beginning check for removal
            currentNode = getFirst ();
            if (currentNode == nodeToRemove)
                removeFirst ();
            currentNode = getLast ();
            if (currentNode == nodeToRemove)
                removeLast ();

            //we've already check two nodes, check the rest
            if (size - 2 > 0) {
                nodeBefore = getFirst ();
                currentNode = getFirst ().getNext ();
                for (int count = 0; count < size - 2; count++) {
                    if (currentNode == nodeToRemove) {
                        //remove current node
                        nodeBefore.setNext (currentNode.getNext ());
                        size--;
                        break;
                    }  //end if node found

                    //change references
                    nodeBefore = currentNode;
                    currentNode = currentNode.getNext ();
                }  //end loop to process elements
            }  //end if size - 2 > 0

        }  //end method remove

        //the gets to return the head and/or tail nodes and size of the list
        public Node<V> getFirst () { return head; }
        public Node<V> getLast () { return tail; }  
        public long getSize () { return size; }

    }  //end class SLinkedList

Gibt es auch Node.java

package chapter3.linkedList;

public class Node<V> 
{
    //instance variables
    private V element;
    private Node<V> next;

    //methods, constructor first
    public Node () 
    {
        this (null, null);      //call the constructor with two args
    }  //end no argument constructor
    public Node (V element, Node<V> next) 
    {
        this.element = element;
        this.next = next;
    }  //end constructor with arguments

    //set/get methods
    public V getElement () 
    { 
        return element; 
    }
    public Node<V> getNext () 
    { 
        return next; 
    }
    public void setElement (V element) 
    { 
        this.element = element; 
    }
    public void setNext (Node<V> next) 
    { 
        this.next = next; 
    }

}  //end class Node

und schließlich GameEntry.java

package Project_1;

public class GameEntry 
{
    protected String name;  //name of the person earning this score
    protected int score;    //the score value
    /** Constructor to create a game entry */
    public GameEntry(String name, int score) 
    {
      this.name = name;
      this.score = score;
    }
    /** Retrieves the name field */
    public String getName() 
    { 
        return name; 
    }
    /** Retrieves the score field */
    public int getScore() 
    { 
        return score; 
    }
    /** Returns a string representation of this entry */
    public String toString() 
    { 
      return name + ", " + score + "\n"; 
    }

}

SCHNITTPUNKT
Ich erstellte einen Treiber genannt Scores.java, in der es bisher allen, die ich habe ist **ich habe Hinzugefügt, was ich DENKE, ich muss für die Klassen, ich bin wahrscheinlich falsch aber:

package Project_1;

import chapter3.linkedList.*;

import java.util.*;


/** Class for storing high scores in an array in non-decreasing order. */
public class Scores 
{

    //add function
    public SLinkedList<GameEntry> add(GameEntry rank, SLinkedList<GameEntry> scores)
    {
        Node<GameEntry> currentNode = scores.getFirst();
        Node<GameEntry> nextNode = null;
        Node<GameEntry> previousNode = null;
        Node<GameEntry> newNode = new Node<GameEntry>();
        newNode.setElement(rank);

        if(scores.getSize() == 0)
        {
            scores.addFirst(newNode);
        }
        else
        {
            while(currentNode != null)
            {               
                nextNode = currentNode.getNext();
                if(nextNode == null)
                {
                    scores.addLast(newNode);
                }
                else
                {
                    scores.addAfter(currentNode, newNode);
                    break;
                }               
            previousNode = currentNode;
            currentNode = currentNode.getNext();
            }
        }
        return scores;
    }

    //remove function
    public void remove(int i)
    {

    }

    //print function
    /*gameenter printing; 
printing=node.Getelement;           //pseudo code for making it work right
print(printing.getscore) 
print(print.getname) 
*/
    public void print(SLinkedList<GameEntry> scores)
    {
        Node<GameEntry> currentNode = scores.getFirst();        
        GameEntry currentEntry = currentNode.getElement();      
        System.out.printf("[");
        for(int i = 0; i < scores.getSize(); i++)
        {
                System.out.printf(", %s", currentEntry.toString());
                currentNode = currentNode.getNext();
                currentEntry = currentNode.getElement();
        }
        System.out.println("]");
    }
}

Habe ich meine test-Treiber ScoresTest.java, , ich habe ziemlich ausgefüllt:

Paket Project_1;

import chapter3.linkedList.SLinkedList;

 public class ScoresTest {
    /**
     * @param args
     */

    public static void main(String[] args) 
    {
        SLinkedList<GameEntry> highScores = new SLinkedList<GameEntry>();  //Linked List for Game Entry
        GameEntry entry;
        Scores rank = new Scores();     
        entry = new GameEntry("Flanders", 681);     
        highScores = rank.add(entry, highScores);
        entry = new GameEntry("Krusty", 324);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Otto", 438);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Bart", 875);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Homer", 12);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Lisa", 506);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Maggie", 980);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Apoo", 648);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Smithers", 150);
        highScores = rank.add(entry, highScores); 
        entry = new GameEntry("Burns", 152);
        highScores = rank.add(entry, highScores); 
        System.out.println("The Original High Scores");
        rank.print(highScores);

        entry = new GameEntry("Moe", 895);
        highScores = rank.add(entry, highScores);
        System.out.println("Scores after adding Moe");
        rank.print(highScores);

        //highScores = rank.remove(4);
        System.out.println("Scores after removing Apoo");
        rank.print(highScores);
    }
}

Ist völlig fertig, ziemlich sicher, ich habe nichts mehr hinzuzufügen.

Ich bin nicht auf der Suche für jemanden zu beantworten für mich, aber ich habe keine Ahnung, wo Sie anfangen sollen oder wie Sie die hinzufügen oder entfernen " - Funktion in keiner Weise. Dies ist ein intermediate-Kurs, das Buch tut nichts für die Erklärung von verknüpften Listen (gehen Sie voran und schauen Sie selbst, wenn Sie mir nicht glauben, wird der text aufgerufen, Datenstrukturen und Algorithmen in Java, 5. Auflage). Es wird gezeigt, wie solche, die mit einer Reihe ganz einfach...die funktioniert perfekt für eine verknüpfte Liste, aber anscheinend sind die Lehrer nicht wollen, dass wir auf diese Weise tun, so traurig es ist, ich bin jetzt völlig verloren, wie dies zu tun.

Ich habe versucht, auf der Suche nach anderen Völker, die Antworten auf die hier, und google, und bisher hat sich nichts angeklickt oder gemacht überhaupt einen Sinn, ich kann einfach nicht begreifen, wie es funktioniert, und der Lehrer seine Erklärung und das Beispiel war nur zu zeichnen-Boxen auf dem Brett, ich habe noch nie gesehen, Sortieren, hinzufügen oder entfernen-Funktion codiert für eine verknüpfte Liste...weiß ja nicht, was ich habe nicht gelehrt, oder nicht finden kann.

Jede Hilfe wird sehr geschätzt, und ich danke Ihnen im Voraus!

BEARBEITEN

Ich schaute auf den import von java.util.*; und die Befehle für verknüpfte Listen, scheinen Sie schmerzlich einfach. entfernen würde ich nur verwenden Liste.Unterliste(ich, ich).clear(); und den Wert, den ich entfernen möchte ist entfernt, super einfach, scheint es doch nur versuchen zu nutzen slinkedlist.java und node.java ich kann einfach nicht scheinen, um Ihnen zu Folgen, in irgendeiner Weise, Form oder form. Ich glaube, der Lehrer hat in der Tat schreiben, und ich habe versucht zu Fragen, für seine Hilfe, blieb 2 Stunden nach dem Unterricht zu versuchen, um zu verstehen, wie Sie von ihm, und wie Sie sehen können, es half nicht viel. Danke nochmals für die Hilfe!

BEARBEITEN

Auch ich entschuldige mich, wenn dies scheint, wie es ist vage, aber ich habe nicht einen bestimmten Punkt, wo meine Verwirrung scheint verknüpft, ich verstehe, verknüpfte Listen, wenn wir reden über die java.util.linkedList;, aber soweit mit dem was ich habe gegeben, in diesem Umstand, kann ich nicht Folgen der Logik auf alle, die mich ziemlich verloren und unsicher, wo man anfangen soll.

InformationsquelleAutor Soully | 2011-09-15

In pseudo-code (bitte beachten ich bin nicht mit gebunden Prüfung etc, einfach die Logik)

Zum hinzufügen eines Knotens auf der Vorderseite der Liste:

newNode->nextNode = startNode
startNode = newNode

Hinzufügen eines bestimmten index:

index = 0
currentNode = startNode

//find the node in the list. here you will need to do all kinds of bound checking
while index is less than position
    currentNode = currentNode.nextNode  //move your node pointer to the position
    increment index

//so here we basically insert the new node into the list. what needs to happen is
//to NOT break the list by forgetting the node after the current node. this is why
//we first set the new nodes' next one, to the current nodes' (the one already in
//the list) next node. this way, we still have all the information we need. then,
//when we set the current nodes' next node to the new node, we essentially "break"
//the link and "repair" it by adding the new link.

newNode.nextNode = currentNode.nextNode //some more bound checking required
currentNode.nextNode = newNode

Entfernen von einem bestimmten index:

index = 0
delNode = startNode

//find the node in the list. here you will need to do all kinds of bound checking
while index is less than (position - 1)
    delNode = delNode.nextNode  //move your node pointer to the position
    increment index

delNode.nextNode = delNode.nextNode.nextNode

//that's it. by setting the node's (before the one you whish to delete)
//next node to the node AFTER the one you want to delete, you basically
//"skip" over that node. since it is no longer referenced, the garbage
//collector will take care of the rest. if you wish to return that node
//you can do it quite easily by remembering it.

storeNode = delNode.nextNode                 //some more bound checking required
delNode.nextNode = delNode.nextNode.nextNode //some more bound checking required

//now you still have a reference to the deleted node in storeNode

UPDATE

OK, also wenn ich das richtig verstehe, müssen Sie zum erstellen einer verknüpften Liste, die speichert die Ergebnisse in einer aufsteigenden Reihenfolge. Soweit ich sehen kann, die gesamte verkettete Liste implementiert für Sie, Sie müssen einfach verwenden den Klassen zur Verfügung gestellt, und fügen Sie die Logik in Scores.java um die Liste sortiert.

Zunächst einmal, sehe ich deine Knoten nicht vergleichbar sind. Wenn Sie überhaupt erlaubt das ändern der Quelle, die Sie erhalten, würde ich empfehlen, dass Sie implementieren Comparable<Node> und auch überschreiben der equals(Object o) so, Sie haben Logik, Sie miteinander zu vergleichen. Zwei Knoten enthalten kann, die dem gleichen element, aber das bedeutet nicht, dass Sie gleich sind.

Bitte beachten Sie die änderung in der Methode Unterschriften!

//add function
public void add(Node<GameEntry> score) {
    //adding is where you now want to keep everything sorted. so I highly
    //recommend that you implement `Comparable` as I mentioned above. if not,
    //you have to put the logic in here.

    Node<GameEntry> currentNode = highScored.getFirst();
    Node<GameEntry> prevNode = null;

    //if the list is empty, or the new node must go in before the head,
    //simply add it as the head.
    if (highScores.size() == 0 || score.compareTo(currentNode) < 0) {
        highScores.addFirst(score);
    }

    //search for the position of the new node. while the node has a higher score
    //than the current node, we need to continue on so we can place it in the
    //correct place.
    while (currentNode != null && currentNode.compareTo(score) > 0) {
        prevNode = currentNode;
        currentNode = currentNode.getNext();
    }

    //if the currentNode is null, it means it is the highest score, so
    //we can simply add it to the end
    if (currentNode == null) {
        highScores.addLast(score);
    } else {
        //otherwise just add it after the correct node
        highScores.addAfter(prevNode, score);
    }
}


//remove function
public void remove(Node<GameEntry> score) {
    //removing an element should be as described above. if you keep
    //your list sorted during the ADD method, removing any element
    //should not break the order.

    //find the element - removal from a linked list is O(n),
    //since we need to know what the element BEFORE the one
    //is that you want to remove. assuming you have implemented
    //the equals method to check equality of nodes:

    Node<GameEntry> currentNode = highScores.getFirst();
    Node<GameEntry> prevNode = null;
    while (currentNode != null && !currentNode.equals(score)) {
        prevNode = currentNode;
        currentNode = currentNode.getNext();
    }

    //if currentNode is null, the node we wanted to remove was not
    //in the list.
    if (currentNode == null) {
        System.out.println("Node not found");
        return;
    }

    //now, we need to check if there is a node after the one we want
    //to remove.
    if (prevNode.getNext().getNext() != null) {
        //if there is, we follow the logic from the pseudo code
        prevNode.setNext(prev.getNext().getNext());
    } else {
        //if not, we only need to remove the last entry (since the
        //one we want to remove is the last one)
        highScores.removeLast();
    }
}

WICHTIG

Bitte überprüfen Sie die Logik hier. Ich habe es wirklich schnell und ohne eine IDE wie ich bin nicht an meinem computer Entwicklung im moment. Wenn jemand findet, etwaige Probleme, hinterlassen Sie bitte einen Kommentar und ich werde es beheben.

Ist dies nicht genau das, was Sie fragte (Ihre Frage ist ein wenig vage), lass es mich wissen.

UPDATE 2

Lesen, auf Comparators hier, hier und hier.

Lies diesen post mehrmals...ich verstehe nicht, was du meinst, leider. Wie ich bereits erwähnte, habe ich nicht gesehen node.java oder slinkedlist.java bevor überhaupt, so habe ich keine Ahnung, wie Sie zu nutzen. Ich weiß nicht, ob es ist, wie Sie es formulieren, oder meine Allgemeinen Mangel an Verständnis, aber ich Folge nicht dem, was Sie geschrieben haben. Ich habe die java.util.linkedList gefunden und es scheint nicht sehr schwer, mein Problem kommt mit diesen Dateien, die mir gegeben.
Verbrachte mehr Zeit die Eingabe nutzlos code, kam mit etwas...Knoten<GameEntry> Aktuelles;, aber wenn ich mir im aktuellen = getFirst(), es sagt, es ist nicht eine Funktion, und wenn ich in chapter3.linkedList.SLinkedList.getFirst(); Sie sagt, Sie hat statisch zu sein, um verwendet werden, also nochmal ich bin in einem impass auf, wie diese Arbeit zu machen.
Zu kommentieren, ich bin-nicht - erlaubt zu ändern, die Klassen, die mir gegeben ist, dass SLinkedList.java, Node.java und GameEntry.java wenn ich ändern könnte, ich versichere Ihnen, ich würde diese einfach löschen und nur den import von java.util.linkedList, weil das alles gebaut und viel einfacher und erfordert nicht den Knoten jeglicher Art, also, während die zu vergleichen wäre schön, es gibt keine Möglichkeit, es zu implementieren. Jedoch, was Sie geschrieben haben, macht VIEL aus, da der Knoten immer noch verwirrt den Teer aus mir heraus, aber es macht mehr Sinn, als es Letzte Nacht getan hat.
Auch auf der Linie "highScores.addLast(Partitur);", schießt es den Fehler "Die Methode addFirst(Knoten<GameEntry>) in der Art SLinkedList<GameEntry> ist nicht anwendbar für die Argumente (SLinkedList<GameEntry>)" Könnte falsch sein, aber es sieht aus wie es nicht wollen, dass die verknüpfte Liste, aber ein Knoten Ihre, so dass anstelle von Noten wäre es currentNode? Dasselbe für die addFirst() oben drauf, und addAfter (unten).
Wenn Sie Lesen, das Fette Teil in meinem update, ich habe gesagt, ich habe die Signaturen. Das heißt, ich änderte die Methode, die Erklärungen sich nicht nehmen, eine verknüpfte Liste, sondern ein Knoten. Nur einen genaueren Blick auf das, was ich Tat. Als für nicht in der Lage zu ändern, die bestehenden Klassen, die Sie erreichen können, genau das gleiche wie die Umsetzung Comparable und überschreiben equals(...) durch die Erstellung einer benutzerdefinierten Comparator und eine einfache Hilfs-Methode für equals().... Haben Sie einen Blick auf das zweite update.

InformationsquelleAutor Nico Huysamen

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.