Implementierung Listen-ADT

[Luca H]

Richtig, was anderes macht Deine append-Methode ja auch nicht.

Dann könnte ich ja mithilfe einer While - Schleife die Stelle herausfinden, in der der neue Wert eingefügt werden muss.

 

[Snaer]

public void append(SortedList l) {
        if (!l.isNil())
            if (first == null) {
                first = l.first;
            } else {
                Node neu;
                for (neu = l.first; neu.next != null; neu = neu.next) {
                    for (Node alt = first; alt.next != null; alt = alt.next) {
                        if (neu.value < alt.value) {
                            neu.next = alt.next;
                            alt.next = neu;
                        }
                    }
                }
            }
    }

Ich versuche hierbei durch beide Listen zu laufen und damit die Werte zu vergleichen.
Meine Idee ist es dabei mit der ersten Schleife die neue Liste zu durchlaufen z.B 6,8,4 bzw 4,6,8, da sie ja durch die Cons Methode bereits sortiert sein sollte, und durch die alte 5,7,9.
Wenn dann der Wert der neuen Liste kleiner ist als der der alten soll der neue Wert an die Stelle eingefügt werden. Jedoch bekomme ich als ersten Wert immer wieder die 5 ausgegeben. Ich habe schon einiges versucht zu verändern finde den Fehler allerdings dennoch nicht.

 

[kneitzel]

Ich habe schon einiges versucht zu verändern finde den Fehler allerdings dennoch nicht.

Hast Du das denn mal durchgespielt auf einem Zettel?
Der neue Node mit der 4 zeigt dann auf den ersten Node der existierenden Liste. Aber first verweist doch noch auf das ehemals erste Element aber nicht auf das neue Erste Element!

Also überleg Dir, wie Du first umsetzen kannst, so dies notwendig sein sollte....

 

[Snaer]

Hast Du das denn mal durchgespielt auf einem Zettel?
Der neue Node mit der 4 zeigt dann auf den ersten Node der existierenden Liste. Aber first verweist doch noch auf das ehemals erste Element aber nicht auf das neue Erste Element!

Also überleg Dir, wie Du first umsetzen kannst, so dies notwendig sein sollte....

Ich habe es zumindest versucht nur scheine ich ein klares Verständnis Problem zu haben.
Meine Überlegung sah ungefähr so aus :
neu (4) alt (5)
Wenn neu < alt
In dem Fall gegeben, dann soll neu.next also 4.next auf alt.next zeigen also 5.next.
und alt.next auf neu.
Dabei habe ich versucht mich an den Zeilen von mihe zu orientieren

toInsert.next = current.next;
        current.next = toInsert;

Also noch zuvor in der Cons Methode
Jedoch habe ich diese glaube nicht verstanden. Auf einem Zettel kam ich dabei auf die Umsetzung :
toInsert = n (5)
current =first (9)
Wenn also die 9 kleiner ist als die 5
Soll current.next (quasi dann 5.next) auf current .next zeigen
Aber wieso soll dann current.next toInsert werden, würde das dann nicht quasi bedeuten das die 5 nach der 9 kommt ?
Also das ich da irgendwo einen Denkfehler habe ist mir bewusst, da der Code ja so funktioniert nur leider bin ich gerade echt verwirrt.

 

[mihe7]

Dann könnte ich ja mithilfe einer While - Schleife die Stelle herausfinden, in der der neue Wert eingefügt werden muss.

Könntest Du. Statt immer wieder den gleichen Code zu schreiben, könntest Du aber auch eine bereits existierende Methode verwenden

 

[mihe7]

Wenn also die 9 kleiner ist als die 5 [...] würde das dann nicht quasi bedeuten das die 5 nach der 9 kommt ?

Ja, wenn die 9 kleiner als die 5 wäre, dann wäre das ja auch richtig

 

[mihe7]

Ich habe es zumindest versucht nur scheine ich ein klares Verständnis Problem zu haben.

Du musst Dir den Spaß erstmal vernünftig aufzeichnen, damit Du nicht ständig den Knoten und den im Knoten gespeicherten Wert verwechselst:

 

[Luca H]

Könntest Du. Statt immer wieder den gleichen Code zu schreiben, könntest Du aber auch eine bereits existierende Methode verwenden

Ich hab mir auch schon gedacht die cons - Methode zu verwenden, weil die ja ungefähr das macht

 

[mihe7]

Ich hab mir auch schon gedacht die cons - Methode zu verwenden, weil die ja ungefähr das macht

Ja, die cons-Methode fügt Dir das Element sogar an der richtigen Stelle ein...

 

[Luca H]

Ja, die cons-Methode fügt Dir das Element sogar an der richtigen Stelle ein...

Okay das Prinzip habe ich verstanden also müsste ich nur die Mehtode cons aufrufen und die würde die Zahlen sortiert einfügen

 

[mihe7]

Ja, wboei cons halt immer nur eine Zahl einfügt (sonst wäre es ja genau das gleiche wie append)

 

[Luca H]

Ja, wobei cons halt immer nur eine Zahl einfügt (sonst wäre es ja genau das gleiche wie append)

Eine Frage hätte ich noch. Und zwar gibt es eine Möglichkeit die cons - Methode aufzurufen und diese dann in append zu erweitern, das die alle Elemente hinzufügt und nicht nur eine?

 

[mihe7]

Und zwar gibt es eine Möglichkeit die cons - Methode aufzurufen und diese dann in append zu erweitern, das die alle Elemente hinzufügt und nicht nur eine?

Das ist Sinn und Zweck der Sache. Konkret: für jedes Element der übergebenen Liste cons aufrufen.

 

[Luca H]

Das ist Sinn und Zweck der Sache. Konkret: für jedes Element der übergebenen Liste cons aufrufen.

Prinizpiell müsste das doch dann mit

Node i = cons();

gehen oder?

 

[Snaer]

Hast Du das denn mal durchgespielt auf einem Zettel?
Der neue Node mit der 4 zeigt dann auf den ersten Node der existierenden Liste. Aber first verweist doch noch auf das ehemals erste Element aber nicht auf das neue Erste Element!

Also überleg Dir, wie Du first umsetzen kannst, so dies notwendig sein sollte....

Ich verstehe nicht wieso first noch auf das ehemals erste Element zeigt. Ich habe es mir auch aufgezeichnet bzw zumindest versucht.
Also neu ist ja = l.first. Also ist neu der erste Knoten der neuen Liste in dem Fall dann 4 richtig ?
Wenn dann alt = first ist ist ja alt der erste Knoten der alten Liste also 5.
Somit sollte die if Anweisung sofort gelten da 4 < 5 ist.
Dann verweist der Knoten mit der 4 auf den vorherigen ersten Knoten mit der 5. Und der ehemals alte Knoten soll ersetzt werden.
Ich verstehe nicht wo genau der Unterschied zwischen dem Versuch und diesen Zeilen genau ist.

Node current = first;
        while (current.next != null && current.next.value < n) {
            current = current.next;
        }
        toInsert.next = current.next;
        current.next = toInsert;
        
    }

Wenn ich die Zeilen durchspiele müsste es ja so aussehen.
Zuallererst wird die 9 in die leere Liste hineingefügt. Anschließend soll die ein Knoten mit der 5 eingefügt werden.
Daher verweist der Knoten mit der 5 auf current.next also dem Knoten mit der 9.
Und an die Stelle von current.next wird die 5 eingeschoben.

 

[mihe7]

Prinizpiell müsste das doch dann mit

Die Methode cons() existiert nicht.

 

[Luca H]

Die Methode cons() existiert nicht.

Ich übersehe hier die einfachsten Dinge. Ich komm einfach nicht drauf wie ich in append die Methode - cons aufrufen kann
Uns wurde das aber auch nicht erklärt in der letzten Übung, weil der Übungsleiter selbst kein bock hatte..

 

[mihe7]

Naja, der Übungsleiter muss ja wohl nicht extra dazu sagen, dass nur genutzt werden kann, was auch definiert ist. Eine Methode cons() ohne Parameter gibt es nicht.

 

[1337Avdu]

@Luca H wo studierst du denn? - Sowas ist Grundvoraussetzung.

 

[Luca H]

@Luca H wo studierst du denn? - Sowas ist Grundvoraussetzung.

Koblenz

 

[Luca H]

Naja, der Übungsleiter muss ja wohl nicht extra dazu sagen, dass nur genutzt werden kann, was auch definiert ist. Eine Methode cons() ohne Parameter gibt es nicht.

Das Problem ist einfach das er nicht mal erklärt hat wie man eine ADT List implementiert

 

[mihe7]

Ich verstehe nicht wo genau der Unterschied zwischen dem Versuch und diesen Zeilen genau ist.

Die alte Liste sei 5->6->null und die neue Liste 1->2->null

Die äußere Schleife iteriert mit neu über die neue Liste, also ist neu erstmal 1.

neu=1->2 (neu ist ein Knoten mit dem Wert 1 und der Knoten zeigt auf einen anderen Knoten mit dem Wert 2).

In der inneren Schleife iterierst Du mit alt über die alte Liste, also ist alt erstmal 5.

alt=5->6

Jetzt prüfst Du, ob neu.value < alt.value gilt, was offensichtlich der Fall ist, denn 1 < 5. Also führst Du aus:
neu.next = alt.next, d. h. neu=1->6 und
alt.next = neu, d. h. alt=5->1

Durch die Änderung der next-Zeiger ergibt sich also:
1. für die alte Liste 5->1->6-null
2. für die neue Liste 1->6->null

Mal abgesehen davon, dass die 2 nun ganz verloren ist, stimmt die Reihenfolge in der alten Liste auch nicht.

 

[Snaer]

Jetzt prüfst Du, ob neu.value < alt.value gilt, was offensichtlich der Fall ist, denn 1 < 5. Also führst Du aus:
neu.next = alt.next, d. h. neu=1->6 und
alt.next = neu, d. h. alt=5->1

Durch die Änderung der next-Zeiger ergibt sich also:
1. für die alte Liste 5->1->6-null
2. für die neue Liste 1->6->null

Mal abgesehen davon, dass die 2 nun ganz verloren ist, stimmt die Reihenfolge in der alten Liste auch nicht.

Gut danke das macht es mir ersichtlich, aber wieso verhält es sich dann nicht genauso bei dem Code ?

Node current = first;
        while (current.next != null && current.next.value < n) {
            current = current.next;
        }
        toInsert.next = current.next;
        current.next = toInsert;

Ist first selbst ein Element der Liste oder ist es nur der erste Zeiger auf den nächsten Knoten?

 

[mihe7]

Das Problem ist einfach das er nicht mal erklärt hat wie man eine ADT List implementiert

Das können wir hier schlecht beurteilen, ich bin aber schon verwundert, dass hier gleich mehrere Leute sind, die ernsthafte Probleme haben.

Schau doch mal Deine cons-Methode an, die erwartet einen Parameter, nämlich den einzufügenden Wert.

Wenn Du also eine Methode schreibst:

public void append(SortedList l) {
    cons(5);
    cons(2);
    cons(9);
}

Dann fügt diese Methode die Werte 5, 2 und 9 zur aktuellen Liste hinzu.

Statt der fixen Werte willst Du cons nun für alle Elemente aus l aufrufen, also musst Du über l iterieren. Dafür gibt es verschiedene Möglichkeiten, in jedem Fall brauchst Du eine Schleife.

 

[mihe7]

aber wieso verhält es sich dann nicht genauso bei dem Code ?

1. Ist das der Code für cons und nicht für append.
2. Wird hier bis zum richtigen Element iteriert und nicht einfach eingefügt, sobald neu < alt gilt.
3. Ist es denn wirklich so schwer, das selbst durchzuspielen?

Nimm die Grafik aus 107 und etwas, womit Du auf einen Knoten zeigen kannst, sagen wir mal einen Stift. Dann repräsentiert Dein Stift current. Und dann gehst Du den Code Zeile für Zeile durch. Wenn im Code steht: current=first, dann zeigst Du mit dem Stift auf den ersten Knoten (der auf den first zeigt). Wenn im Code steht: current = current.next, dann zeigst Du mit dem Stift auf den Knoten auf den - ausgehend vom aktuellen - next zeigt (kurz: auf den nächsten Knoten). Das ganze probierst Du aus für die Fälle 1, 4, 7 und 10. Dann sollte klar sein, wie der Code funktioniert.

Ist first selbst ein Element der Liste oder ist es nur der erste Zeiger auf den nächsten Knoten?

first ist nur der Zeiger auf den ersten Knoten der Liste.

 

[kneitzel]

Ja, aber das ist doch auch nicht das erste Mal, dass hier so eine Gruppe aufschlägt oder ist das jetzt lediglich die Gruppe, die vor paar Wochen hier schon aktiv war?

Aber wie dem auch sei: Ich bin hier teilweise mit meinem Latein am Ende. So im Forum können wir nicht alle Grundlagen so ausführlich bringen. Dafür gibt es Lehrbücher. Ein Dozent mag schlecht sein, aber dann muss doch wenigstens auf brauchbare Literatur verwiesen werden.....

Vor allem sehe ich das Problem, dass wir an einer Aufgabe rumhantieren und nicht wirklich sehen, wo die Verständnisprobleme sind. Ich denke, dass da irgend eine Kleinigkeit fehlt. Ich versuche so z.B. immer einen Bezug zu Objekten zu schaffen, die weniger abstrakt sind.... Dann klappt es mit der Vorstellung evtl. und ich habe da immer die Hoffnung, dass es dann "Klick" macht.

Ich glaube auch, dass man ein paar Dinge einfach im Detail vormachen müsste. Dieses durchspielen auf einem Zettel ist da ein Beispiel. Und da staune ich dann teilweise über die Ascii Zeichnungen die hier teilweise gebracht werden. Ich hab mir noch einmal TeX installiert weil ich dachte, dass ich da dann schnell paar einfache Skizzen machen kann. Einige Dinge gehen ganz schnell, aber auch das ist noch einiges an Aufwand.... Und der blöde Export hin zu html haut nicht wirklich hin, sonst hätte ich da Erläuterungen in mein Blog gepackt .... Aber da geht wahnsinnig Zeit drauf. Man will ja noch einmal drüber schauen und so ...

Also lange Rede einmal kurz gefasst: Ich sehe hier gerade keinen Ansatz, wie das zu lösen ist....

 

[Snaer]

Das können wir hier schlecht beurteilen, ich bin aber schon verwundert, dass hier gleich mehrere Leute sind, die ernsthafte Probleme haben.

Schau doch mal Deine cons-Methode an, die erwartet einen Parameter, nämlich den einzufügenden Wert.

Wenn Du also eine Methode schreibst:

public void append(SortedList l) {
    cons(5);
    cons(2);
    cons(9);
}

Dann fügt diese Methode die Werte 5, 2 und 9 zur aktuellen Liste hinzu.

Statt der fixen Werte willst Du cons nun für alle Elemente aus l aufrufen, also musst Du über l iterieren. Dafür gibt es verschiedene Möglichkeiten, in jedem Fall brauchst Du eine Schleife.

Ich habe mal versucht es mithilfe des Methoden Aufrufs von cons zu regeln.

public void append(SortedList l) {
        if (!l.isNil())
            if (first == null) {
                first = l.first;
            } else {
                for (Node neu = l.first; neu.next != null; neu = neu.next) {
                    this.cons(neu.value);
                }
            }
    }

Dies funktioniert seltsamerweise jedoch nur für 2 von 3 Werten. Während die 4 und die 6 wohl korrekt eingefügt werden, wird die 8 wohl übersprungen

 

[mihe7]

ist das jetzt lediglich die Gruppe, die vor paar Wochen hier schon aktiv war?

Klar. Damals ging es um 2D-Arrays, wenn ich mich recht entsinne und schon da fehlten alle Grundlagen. Darum #99

Dies funktioniert seltsamerweise jedoch nur für 2 von 3 Werten.

Das ist nicht seltsam, sondern liegt an Deiner Schleifenbedingung.

 

[Snaer]

Das ist nicht seltsam, sondern liegt an Deiner Schleifenbedingung.

Ich nehme mal an du meinst da die Schleife nur solange durchläuft bis neu.next != null ist.
Aber muss ich nicht diese Absicherung einbauen, damit ich nicht über das Ende der Schleife laufe?

 

[kneitzel]

Dann spielt es doch mal durch:
Du bist beim vorletzten Element, dann Rückstand du eins weiter und er prüft: neu.next != null und steigt aus.

Also aufzeichnen und schauen, wie lange du weiter gehen musst, damit es funktioniert.

Und brauchst die Sonderbehandlung mit der Prüfung, ob First Null ist?

 

[Snaer]

Und brauchst die Sonderbehandlung mit der Prüfung, ob First Null ist?

Die Bedingung habe ich für den Fall eingesetzt, dass die erste Liste null sei, sodass quasi die neue Liste diese einfach ersetzen kann. Ob es wirklich getestet wird kann ich nicht einsehen, da nur ein kleiner Teil des Tests einsehbar ist.

 

[mihe7]

Die Bedingung habe ich für den Fall eingesetzt, dass die erste Liste null sei, sodass quasi die neue Liste diese einfach ersetzen kann.

Leute, Leute... bevor Ihr Euch an irgendwelche Optimierungen wagt, solltet ihr halbwegs wissen, was ihr da betreibt. Bei Euch fehlt wirklich alles an Grundlagen, was ich mir vorstellen kann. Dozent hin oder her: IHR müsst Euch darum kümmern, die Zeiten, in denen der Lehrer dem Schüler alles nachträgt sind für Euch vorbei.

Zurück zum Thema: first ist eine Referenz(!) auf ein Node-Objekt. Wenn Du first einfach auf l.first setzt, dann referenzieren first und l.first das selbe(!) Objekt. Die Listen bestehen dann nicht aus gleichen Objekten sondern aus identischen. So gut wie jede Änderung der einen Liste wirkt sich damit automatisch auf die andere Liste aus. Das ist nicht das, was Du willst.