Implementierung Listen-ADT

Code: 
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.
 
Snaer hat gesagt.:
Ich habe schon einiges versucht zu verändern finde den Fehler allerdings dennoch nicht.
Zum Vergrößern anklicken....

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....
 
JustNobody hat gesagt.:
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....
Zum Vergrößern anklicken....
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
Code: 
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. 🙄
 
JustNobody hat gesagt.:
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....
Zum Vergrößern anklicken....
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.
Code: 
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.
 
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.
 
Snaer hat gesagt.:
Ich verstehe nicht wo genau der Unterschied zwischen dem Versuch und diesen Zeilen genau ist.
Zum Vergrößern anklicken....
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.
 
mihe7 hat gesagt.:
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.
Zum Vergrößern anklicken....
Gut danke das macht es mir ersichtlich, aber wieso verhält es sich dann nicht genauso bei dem Code ?
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?
 
Luca H hat gesagt.:
Das Problem ist einfach das er nicht mal erklärt hat wie man eine ADT List implementiert
Zum Vergrößern anklicken....
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:
Java: 
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.
 
Snaer hat gesagt.:
aber wieso verhält es sich dann nicht genauso bei dem Code ?
Zum Vergrößern anklicken....
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.

Snaer hat gesagt.:
Ist first selbst ein Element der Liste oder ist es nur der erste Zeiger auf den nächsten Knoten?
Zum Vergrößern anklicken....
first ist nur der Zeiger auf den ersten Knoten der Liste.
 
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....
 
mihe7 hat gesagt.:
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:
Java: 
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.
Zum Vergrößern anklicken....
Ich habe mal versucht es mithilfe des Methoden Aufrufs von cons zu regeln.
Code: 
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
 
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 hat gesagt.:
Die Bedingung habe ich für den Fall eingesetzt, dass die erste Liste null sei, sodass quasi die neue Liste diese einfach ersetzen kann.
Zum Vergrößern anklicken....
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.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

ADT Implementierung (Array basics)
Antworten: 16
Listen in Listen in Listen ... ???
Antworten: 2
Listen | und einige Methoden für Listen
Antworten: 11
Listen, über Listen. und doch kein Überblick
Antworten: 8
Listen sortieren bei mehreren Listen zu einer
Antworten: 2

Zurück
Oben