PhoneBook mit verketteten listen

Diskutiere PhoneBook mit verketteten listen im Java Basics - Anfänger-Themen Bereich.
A

arhzz

Also ich würde dir raten erst einmal den Algorithmus in Worte zu fassen, damit die Hürde der Programmiersprache entfällt.

Deine while Schleife geht so lange weiter, wie der Vergleich 0 (Elemente sind gleich, wobei du noch nicht das aktuelle Element mit dem einzufügenden vergleichst) ergibt. So die Elemente nicht gleich sind, fügst du das Element ein (ok, das Einfügen fehlt noch, aber du setzt size hoch...)

Das ist aber doch nicht das, was du machen willst nehme ich an...
Na ja ich will di
Du hast den Node p - da steckt doch auch ein Name drin. Vergleich den doch mit der übergebenen Person.
Oooooooo ja dass habe ich voll übersehen, und ein Re auf deine vorhergire Post,wie vergleiche ich nicht das einzufügenden element nicht? Sollte dass nicht das compareTo machen? Und das Einfügen fehlt noch?Also habe ich dass element nicht in der liste eingefügen? Sollte dass nicht der teil mit dem Node n = new node sein?
 
A

arhzz

Bei Verketteten Listen stell dir auch immer gerne die ganze Sache bildlich vor. Nehmen wir einen Zug. Deine PhoneBookList ist das Führerhaus. Dieses Führerhaus kennt nur den ersten Waggon, also der, der an dieses Führerhaus gekoppelt ist (bei dir head). Jeder Waggon hat eine numerischen Wert (bei dir Person) und kennt wiederum den nächsten angekoppelten Waggon (next). Außerdem hast du einen Bahnmitarbeiter, er weiß stets vor welchem Waggon er steht. Nennen wir diesen einmal current. Der Bahnmitarbeiter fängt immer am Führerhaus an, wenn er etwas mit diesen aneinandergekoppelten Waggons tun soll.

Nehmen wir nun also das Beispiel Einfügen. current ist noch null, weil der Bahnmitarbeiter vor dem Führerhaus steht. Außerdem steht ein Waggon (new Node) auf einem anderen Gleis, der numerisch sortiert reingekoppelt werden soll. Der Bahnmitarbeiter geht zum ersten Waggon und schaut sich diesen an und schreitet so Waggon bis Waggon vor (current verändert sich), bis er zwischen einem Waggon mit niedrigerer Nummer und einem Waggon mit höherer Nummer steht. Diese 2 Waggons entkoppelt der Bahnmitarbeiter und koppelt diese stattdessen mit dem Waggon auf dem anderen Gleis. Es sind also 2 Kupplungen zu verändern.

Vielleicht hast du ja auch irgendwo Spielzeug o.Ä. rumliegen, mit welchem du das auf dem Tisch nachspielen kannst.
Okay,ich muss mir das zeichen oder so etwas vielleciht werde ich es besser verstehen.
 
MoxxiManagarm

MoxxiManagarm

Ich habe dir für mein Beispiel mal ein Codebeispiel zusammengeschraubt. Ich hoffe du kannst es daran nachvollziehen. Wenn du verkettete Listen einmal verstanden hast ist es leicht.

Java:
public class Zughaus {
    WaggonNode head;

    public void einreihen(int id) {
        WaggonNode waggon = new WaggonNode(id); // der Waggon auf dem anderen Gleis

        if (head == null) { // der Zug hat noch keinen Waggon
            head = waggon;
        } else if (head.id > id) { // muss zwischen Zughaus und erstem Waggon eingekoppelt werden
            waggon.next = head;
            head = waggon;
        } else {
            WaggonNode current = head;

            // so lange fortschreiten, bis der nächste Waggon eine höhere Nummer hat
            // oder der Bahnmitarbeiter das Ende erreicht hat
            while (current.next != null && current.next.id < id) {
                current = current.next;
            }

            // der Bahnitarbeiter steht nun vor dem Waggon, an welchem der neue Waggon angekoppelt werden soll
            // und führt die Kopplung durch
            waggon.next = current.next;
            current.next = waggon;
        }
    }

    public void ablaufen() {
        WaggonNode current = head;

        while (current != null) {
            System.out.println(current.id);
            current = current.next;
        }
    }

    public static void main(String... args) {
        Zughaus zug = new Zughaus();

        zug.einreihen(8);
        zug.einreihen(5);
        zug.einreihen(7);
        zug.einreihen(2);
        zug.einreihen(1);

        zug.ablaufen();
    }
}

class WaggonNode {
    int id;
    WaggonNode next;

    public WaggonNode(int id) {
        this.id = id;
    }
}
Ausgabe:
Code:
1
2
5
7
8
 
A

arhzz

Ich habe dir für mein Beispiel mal ein Codebeispiel zusammengeschraubt. Ich hoffe du kannst es daran nachvollziehen. Wenn du verkettete Listen einmal verstanden hast ist es leicht.

Danke dir viel! Also ich habe auch etwas probiert mit hilfe von google,etwas änlicher zu meinem Beispiel;

Java:
final class TaskList {

  Node head = null;

  void insert(Task task, java.util.Comparator comparator) {
    Node p = head, prev = null;

    while (p != null) {
      int comparison = comparator.compare(task, p.task);

      if (comparison == 0) return;
      if (comparison < 0) break;

      prev = p;
      p = p.next;
    }

    Node n = new Node(task);

    if (prev == null) {
      // p must be head in this case
      assert p == head;

      if (p == null) {
        // insert in empty list
        head = n;
      } else {
        // insert before first element in list
        head = n;
        n.next = p;
      }
    } else {
      if (p == null) {
        // insert after last element
        prev.next = n;
      } else {
        // insert before p, somewhere in the middle
        prev.next = n;
        n.next = p;
      }
    }


Der unterschied sind die methode compareTo (Die ich noch nicht weiss wie ich sie implementieren soll) und der Rückgabetyp.Es ist void und es sollte boolean sein. Jetzt ist nun die frage wie ich diese 2 Dinge in diesen Code implementiere[/codE]
 
MoxxiManagarm

MoxxiManagarm

compareTo kommt dorthin wo ich mit > bzw < die id vergleiche. Bei boolean kommt es darauf an was er bedeudet. Ich nehme mal an es soll false zurückgeliefert werden, falls der Name schon existiert?
 
A

arhzz

Java:
final class TaskList {

  Node head = null;

  void insert(Task task, java.util.Comparator comparator) {
    Node p = head, prev = null;

    while (p != null) {
      int comparison = comparator.compare(task, p.task);

      if (comparison == 0) return;
      if (comparison < 0) break;

      prev = p;
      p = p.next;
    }

    Node n = new Node(task);

    if (prev == null) {
      assert p == head;
      if (p == null) {  
        head = n;
      } else {
        head = n;
        n.next = p;
      }
    } else {
      if (p == null) {
       
        prev.next = n;
      } else {
   
        prev.next = n;
        n.next = p;
      }
    }
compareTo kommt dorthin wo ich mit > bzw < die id vergleiche. Bei boolean kommt es darauf an was er bedeudet. Ich nehme mal an es soll false zurückgeliefert werden, falls der Name schon existiert?
Ja,genau dass.
 
MoxxiManagarm

MoxxiManagarm

Ok, abgeändertes Beispiel (ich habe die Kommentare nun rausgelassen):

Java:
public class Zughaus {
    WaggonNode head;

    public boolean einreihen(int id) {
        WaggonNode waggon = new WaggonNode(id);

        if (head == null) {
            head = waggon;
            return true;
        }

        if (id < head.id) {
            waggon.next = head;
            head = waggon;
            return true;
        }

        if (id == head.id) {
            return false;
        }

        WaggonNode current = head;
        while (current.next != null && current.next.id < id) {
            current = current.next;
        }

        if (current.next != null && current.next.id == id) {
            return false;
        }

        waggon.next = current.next;
        current.next = waggon;
        return true;
    }

    public void ablaufen() {
        WaggonNode current = head;

        while (current != null) {
            System.out.println(current.id);
            current = current.next;
        }
    }

    public static void main(String... args) {
        Zughaus zug = new Zughaus();

        for (int iter : new int[]{8, 5, 7, 2, 1, 8, 1}) {
            if (!zug.einreihen(iter)) {
                System.out.println(iter + " konnte nicht eingekoppelt werden!");
            }
        }

        zug.ablaufen();
    }
}

class WaggonNode {
    int id;
    WaggonNode next;

    public WaggonNode(int id) {
        this.id = id;
    }
}
Ausgabe

Code:
8 konnte nicht eingekoppelt werden!
1 konnte nicht eingekoppelt werden!

1
2
5
7
8
 
A

arhzz

Ok, abgeändertes Beispiel (ich habe die Kommentare nun rausgelassen):

Java:
public class Zughaus {
    WaggonNode head;

    public boolean einreihen(int id) {
        WaggonNode waggon = new WaggonNode(id);

        if (head == null) {
            head = waggon;
            return true;
        }

        if (id < head.id) {
            waggon.next = head;
            head = waggon;
            return true;
        }

        if (id == head.id) {
            return false;
        }

        WaggonNode current = head;
        while (current.next != null && current.next.id < id) {
            current = current.next;
        }

        if (current.next != null && current.next.id == id) {
            return false;
        }

        waggon.next = current.next;
        current.next = waggon;
        return true;
    }

    public void ablaufen() {
        WaggonNode current = head;

        while (current != null) {
            System.out.println(current.id);
            current = current.next;
        }
    }

    public static void main(String... args) {
        Zughaus zug = new Zughaus();

        for (int iter : new int[]{8, 5, 7, 2, 1, 8, 1}) {
            if (!zug.einreihen(iter)) {
                System.out.println(iter + " konnte nicht eingekoppelt werden!");
            }
        }

        zug.ablaufen();
    }
}

class WaggonNode {
    int id;
    WaggonNode next;

    public WaggonNode(int id) {
        this.id = id;
    }
}
Ausgabe

Code:
8 konnte nicht eingekoppelt werden!
1 konnte nicht eingekoppelt werden!

1
2
5
7
8
Okay, ich habe probiert Analog zu deinen Beispiel meinen zu implementieren.

Java:
class PhoneBookList implements PhoneBook {
    private int size = 0;
    Node head;
    
    private static final class Node { //class Wagonnode
        final Person person;
        Node next;
        
        Node(Person person) {
            this.person = person;
        }
    }
    
    public boolean insert(Person person) {
        Node n = new Node(person); //die Person die sagen wir vor der Tür steht.
        Node p = head,prev = null;// den Head auf p zuweisen.
        
        
        if(p == null) {//Niemand ist in dem raum
            head = n;//also soll die neu Person die erste sein die rein geht.
            return true;
        }
        
        int comparison = p.name.compareTo(n.name);//den Namen von der ersten person mit dem Namen der neuen person vergleichen.
        
        if(comparison < 0) {
            n.next = p;
            p = n;
            size++;// den wert size um 1 zu erhohen, brauche ich dass überhaupt?
            return true;
        }
        
        if(comparison == 0) {
            return false;
            
        }
        
        Node current = p;
        while(current.next !=null && current.next.person < person) {
            current = current.next;
        }
        if(current.next !=null && current.next.person == person) {
            return false;
            
        }
    
        n.next = current.next;
        current.next = n;
        return true;
    }
 
MoxxiManagarm

MoxxiManagarm

Was mir spontan auffällt: wenn du size brauchst, dann müsst du es auch überall dort erhöhen, wo du die zurückliefert. Aktuell machst du das nur an einer stelle
 
A

arhzz

Was mir spontan auffällt: wenn du size brauchst, dann müsst du es auch überall dort erhöhen, wo du die zurückliefert. Aktuell machst du das nur an einer stelle
Ja,macht sinn eigentlich, aber nur an den stellen wo ich true zurüc liefere? Wo ich false zurüc liefere macht dass kein sinn denke ich
 
A

arhzz

Ja, halt da wo du tatsächlich was einfügst
Also dass mit return, habe ich angepasst aber ich bekomme ein Fehler;

PhoneBookList.java:40: error: bad operand types for binary operator '<'
while(current.next !=null && current.next.person < person) {
^
first type: Person
second type: Person

Was genau bedeutet dass?
 
mihe7

mihe7

Das bedeutet, dass es nicht möglich ist, zwei Objekte mit < zu vergleichen. S. zum Beispiel Kommentar #25 und #28.
 
A

arhzz

Ich denke ich hab es geschafft

Java:
class PhoneBookList implements PhoneBook {
    private int size = 0;
    Node head = null;

    private static final class Node {
        final Person person;
        Node next;

        Node(Person person) {
            this.person = person;
        }
    }

    public boolean insert(Person person) {
        Node n = new Node(person);
        Node p = head;

        if(p == null) {
            head = n;
            size++;
            return true;
        } else {

            Node temp = p;
            int comparison;
            while(temp.next != null) {
                comparison = temp.person.name.compareTo(person.name);
                if(comparison == 0){
                    return false;
                }
                temp = temp.next;
            }
            temp.next = n;
            size++;
            return true;
        }

    }
}
 
J

JustNobody

Wenn die Liste sortiert sein soll, dann wird diese Anforderung noch nicht erfüllt. Derzeit fügst Du neue Elemente nur am Ende ein.
 
J

JustNobody

Ich empfehle wirklich, das einmal durchzuspielen.

Wenn Du die Liste hast aus:
Anton
Berta
Zeppelin

Und du sollst Martha hinzu fügen:
Wie lange gehst du die Liste durch? Was prüft du beim durchgehen?
 
Thema: 

PhoneBook mit verketteten listen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben