Verkette Listen

[d_rose]

Folgendes Problem: Also ich hab mir bereits jegliche Information zu verketteten Listen durchgelesen. Bisher waren alle Ansätze so das man eine Knoten-Klasse erstellt, mit den Attributen "Eintrag" und "Nachfolger". Und dann hat man eine Klasse LinkedList erstellt, Mithilfe der man diese Datenstruktur modelliert.

Leider kann ich so wie es scheinbar von uns gewollt ist, mir leider gar nicht vorstellen, wie ich damit umzugehen habe.
Daher wäre ich für jegliche Ansätze dankbar, ansonsten lösch ich das hier wieder wenn das unpassend.
ich weis es sollen hier keine aufgaben gelöst werden

[__blackjack__]

@d_rose: Du hast halt nur eine Knoten-Klasse die ihr `Vliste` nennen sollt. Ich sehe jetzt das konkrete Problem nicht‽ Man kann einen Knoten der den Kopf der Liste enthält und über den alle Folgeelemente erreichbar sind, doch durchaus als Liste auffassen. Das ist so ziemlich das simpelste wie man das machen kann. Wo hast Du Denn ganz konkret ein Problem damit?

Also zum Beispiel könnte man Dir Durchaus den Code für a) zeigen, denn das ist wirklich nicht viel mehr als eben eine Klasse mit den beiden Attributen zu erstellen, deren Initialwerte als Argumente an `__init__()` übergeben werden. Das Erstellen der Beispielliste ist in Aufgabenteil c) ja schon gezeigt, nur mit den Werten 1, 2, und 3 statt denen die in a) verwendet werden sollen. Und für den Zugriff auf das dritte Element musst Du Dir halt überlegen wie Du an das erste kommst. Dann wie an das zweite. Und dann wie an das dritte. Und das ist dann die Lösung für den Zugriff auf das dritte Element.

[d_rose]

Also mein erstes Problem das sich mir bereitet, wie die Instanz auszusehen hat:
also ich erstelle ganz normal die Klasse, dann die Initialisierungsmethode, mit den Attributen "Eintrag" und "Nachfolger".
Mir persönlich ist es dann schon eigenartig wenn ich zum Beispiel die Instanz erstelle mit (5,"ab",(0.36,None))) als Argument.
Würde ich mir dann zum Beispiel den "Eintrag" ausgeben lassen wäre diese die 5. und der Nachfolger wäre ("ab",(0.36,None)).
Ich weis nicht, also entweder ich hab nen massiven Denkfehler oder einfach nur dumm das ich den Wald vor lauter Bäumen nicht mehr sehe.

Code: Alles auswählen

class Vliste:
        def __init__(self, eintrag, nachfolger):
                self.eintrag = eintrag
                self.nachfolger = nachfolger


        
instanz_1 = Vliste(5,Vliste("ab",Vliste(0.36,None)))

[__blackjack__]

@d_rose: Na das ist doch schon fast alles für Aufgabenteil a). Du hast die Klasse geschrieben und die Beispielliste als Exemplar(e) dieser Klasse dargestellt.

Wobei Du im Beitragstext nicht ganz korrekt bist. Du erstellst nichts mit (5,"ab",(0.36,None))) als Argument. Das wäre in Python ja ein verschachteltes Tupel. Wobei man die verkettete Liste natürlich auch genau so repräsentieren könnte und dann Funktionen schreiben könnte die beispielsweise etwas an so eine Listendarstellung anhängen. Eine Vergleichsfunktion bräuchte man nicht schreiben, denn da würde der ``==``-Operator auf Tupeln schon das richtige machen.

Der `eintrag` von `instanz_1` wäre tatsächlich 5, der Nachfolger aber nicht ("ab",(0.36,None)) sondern das Exemplar das durch den zweiten `Vliste()`-Aufruf in dem Ausdruck erstellt wurde. Das hat den als `eintrag` 'ab' und als Nachfolger das Exemplar das durch den dritten `Vliste()`-Aufruf erstellt wurde. Beziehungsweise von der Ausführungsreihenfolge her natürlich der erste Aufruf, denn die Argumente werden in Python ja vor dem Aufruf ausgewertet.

Vielleicht kannst Du den Knoten im Kopf ja lösen, oder zumindest lockern, wenn Du das nicht als einen Ausdruck hin schreibst, sondern die einzelnen Zwischenergebnisse an Namen bindest. Und auf dem ersten Bild ist ja eine Zeichnung der Struktur, schreib da mal `eintrag` und `nachfolger` an die richtigen Stellen.

Und Du könntest das mal in einer interaktiven Python-Shell ausprobieren und schauen wie Du auf die Attribute zugreifen kannst und was da jeweils als Ergebnis heraus kommt. Hilfreich könnte auch eine `__repr__()`-Implementierung sein, die etwas mehr über die Objekte ausgibt.

Edit: Meine Implementierung so weit, mit dem externen `attr`-Modul um schon eine `__repr__()`-Darstellung und einen Vergleich zwischen `LinkedList`-Objekten zu bekommen:

Code: Alles auswählen

#!/usr/bin/env python3
from attr import attrib, attrs


@attrs
class LinkedList:
    value = attrib()
    next = attrib(default=None)


def main():
    list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
    print(list_a)


if __name__ == '__main__':
    main()

Ausgabe:

Code: Alles auswählen

LinkedList(value=5, next=LinkedList(value='ab', next=LinkedList(value=0.36, next=None)))

[d_rose]

Hmmmm meinst du dann ein Objekt innerhalb eines Objektes, sorry das ich das gerade vom Handy aus schreibe. Aber in etwa so hier: instanz_1 = Vliste(5,Vliste(„ab“,Vliste(0.36,None
) ??

[__deets__]

Genau das steht doch so in deinem aufgabentext. Also: ja.

[__blackjack__]

@d_rose: Ich bin jetzt etwas verwirrt, denn das steht nicht nur so im Aufgabentext, sondern auch in *Deinem* letzten Beitrag. Wobei ich das nicht unbedingt als ein Objekt *innerhalb* eines Objektes bezeichnen würde, denn diese drei Objekte sind ja nicht ineinander gespeichert, die sind schon einzeln, aber eben durch das jeweilige `next`-Attribut verbunden.

[d_rose]

Ahhhh okay wahrscheinlich war das so der Knackpunkt, bei meinem Gedanken, jetzt ist mir das bisschen klarer. Danke dafür.

Was sich mir als frage jetzt stellt,welches das 3. Element sein soll? Nur 0.36 im obigen Beispiel oder 0.36,None ?

[__blackjack__]

Hier mal grafisch dargestellt wie das letztendlich aussieht und das *in* `Vlist`-Objekten letztlich gar keine Daten gespeichert sind, sondern das die nur aus jeweils zwei Verweisen auf andere Objekte bestehen:

[__deets__]

Ui, schick. Womit machst du die so schnell? Du zeichnest das doch hoffentlich nicht von Hand?!?!

[d_rose]

okay verstanden.wunderschöne Grafik by the way. eine frage zu der B ich tu es mir da schwer und zwar: erstelle ich eine 2. Instanz mit denselben werten und vergleiche diese mit der 1. wird mir False ausgegeben.
nutze ich die 2. Instanz so indem ich einfach die 2. Instanz als Referenz für Instanz_1 nehme also : Instanz_2 = Instanz_1 so wird mir beim vergleichen True ausgeben. Ich weis das das irgendwas mit dem Speicherort scheinbar zu tuen hat, könnte den Sachverhalt aber genau nicht wiedergeben. Daher muss man ja die einzelnen Attribute miteinander vergleichen um eine Gleichheit festzustellen, allerdings kriege ich das nur für den ersten Wert der Liste hin.
Muss ich da durch die Instanz iterieren um vollständige Gleichheit zu prüfen ?

hier mein ansatz,welcher allerdings False ausgibt trotz gleicher Instanzen:

Code: Alles auswählen

class Vliste:
        def __init__(self, eintrag, nachfolger):
                self.eintrag = eintrag
                self.nachfolger = nachfolger

        def gleich(self, other):
                if self.eintrag == other.eintrag and self.nachfolger == other.nachfolger:
                        return True
                else :
                        return False

[__blackjack__]

@__deets__: PlantUML. Das macht aus Textdateien Grafiken. Der Quelltext zu der Grafik ist der hier:

Code: Alles auswählen

@startuml

title

""vlist_a = Vlist(5, Vlist("ab", Vlist(0.36, None)))""

end title

object object0 <<module>>

object object2 <<float>> {
    0.36
}

object object1 <<NoneType>> {
    None
}

object object3 <<Vlist>>

object3 -> object2 : eintrag
object3 --> object1 : nachfolger

object object4 <<str>> {
    "ab"
}

object object5 <<Vlist>>

object5 -> object4 : eintrag
object5 --> object3 : nachfolger

object object6 <<int>> {
    5
}

object object7 <<Vlist>>

object7 -> object6 : eintrag
object7 --> object5 : nachfolger

object0 -> object7 : vlist_a

footer

www.python-forum.de
endfooter


@enduml

@d_rose: Um zwei Listen zu vergleichen müssen alle Werte in beiden Listen in der gleichen Reihenfolge vorkommen. Du kannst also nicht einfach ``==`` auf die `Vliste`-Objekte anwenden, sondern Du musst a) die Werte vergleichen, und b) ob die in den Folgeelementen auch gleich sind, und c) das die beiden Listen auch gleich lang sind, denn eine ``Vlist(1, Vlist(2))`` und eine ``Vlist(1, Vlist(2, Vlist(3)))`` haben zwar die gleichen Elemente in der gleichen Reihenfolge am Anfang, aber eine hat ein Element mehr.

Edit: Der `nachfolger` muss nicht gleich sein und wird es in der Regel auch nicht.

[__blackjack__]

@d_rose: Noch ein Nachtrag zum Code: Die Bedingung im ``if`` ergibt ja schon `True` oder `False` – das kann man einfach direkt zurückgeben.

Also wenn man so etwas hat:

Code: Alles auswählen

    if some_condition:
        return True
    else:
        return False

Dann kann man auch einfach schreiben:

Code: Alles auswählen

    return some_condition

Selbst wenn man den Vergleich richtig macht, kann dieser Hinweis an einer Stelle zur Anwendung kommen. Je nach dem wie man es konkret ausformuliert.

Und ich würde dem `nachfolger`-Argument in der `__init__()` einen Defaultwert von `None` verpassen. Dann muss man das nicht angeben beim Aufruf.

[d_rose]

Wie vergleich ich den die Listenlänge? einfach len() tut es ja nicht. ich krieg die Krise mit dieser Datenstruktur.
ich kämpfe schon damit gerade mir das 3. Element auszugeben, also überhaupt über die 5 hinauszukommen des Objektes. Soll das innerhalb der init() geschehen oder auserhalb im Hauptcode ist mir nicht ersichtlich

[__blackjack__]

@d_rose: Na ausserhalb der `__init__()`. Wenn Du das in der `__init__()` machen würdest, dann würde ja für jede VListe die Du erstellst, also für a) alle *drei*, das dritte Element ausgegeben, aber nur eine von den drei Listen hat ja überhaupt ein drittes Element, weil die anderen beiden kürzer als drei Elemente sind.

Die Listenlänge musst Du nicht unbedingt vergleichen, es reicht wenn du testest das nicht eine der beiden Listen länger ist als die andere während Du testest ob die einzelnen Elemente gleich sind. Da kommst Du dann ja irgend wann an den Punkt das entweder nur eine der beiden Listen zuende ist, oder eben beide. Wenn nur eine von beiden zuende ist, dann sind sie offensichtlich nicht gleich lang und damit unterschiedlich. Man könnte natürlich auch `__len__()` passend implementieren, damit `len()` funktioniert, aber das wäre ineffizienter weil man dann ja schon für `len()` die Liste linear durchgehen und Elemente zählen müsste.

Wenn man sich die Zeichnung oben anschaut, kommt man an die 5 mit `vlist_a.eintrag`. Es gäbe ja noch eine andere Möglichkeit. `vlist_a.nachfolger`. Da bekommt man dann wieder ein `Vlist`-Objekt. Wo man wieder zwei Möglichkeiten hat im Objektgraphen weiter zu gehen: `eintrag` oder `nachfolger`. Bei `eintrag` wird man da was bekommen? Und bei `nachfolger`?

[sls]

Ui, wart ihr nicht vor einiger Zeit mal so ein bisschen kritisch ggü. UML?

[__deets__]

Als Visualisierung, zur Kommunikation? Noe. Als zentrales Entwurfselement mit transparenter Code-Generierung und all seinen Schleifchen und Glitzer, wie es einem IBM Rational verkaufen will? Ja.

[__blackjack__]

Was __deets__ gesagt hat.

[d_rose]

Das kommt mir irgendwie dumm vor, aber Instanz_1.nachfolger.nachfolger.eintrag gibt mir jedenfalls das 3. element aus. aber mir ist immer noch rätselhaft damit zu arbeiten.

[__blackjack__]

@d_rose: Damit wird man *so* auch nicht arbeiten, ich denke in diesem letzten Teil von Aufgabe a) ging es einfach darum diesen Zusammenhang und die Verkettung und das durchgreifen können über die einzelnen Objekte zu erkennen. Für die Vergleichsmethode in b) muss man dass dann dynamischer/allgemeiner lösen. Und für das Anhängen in c) auch. Ich würde übrigens eventuell erst c) empfehlen, weil das ein kleines bisschen simpler umzusetzen ist als b). Denn da muss man sich erst einmal nur mit *einer* Liste beschäftigen, während beim Vergleich ja *zwei* beteiligt sind.

Meine nicht-repräsentative Python-Lösung erweitert um den Durchgriff auf das dritte Element und schon im Vorgriff auf den Vergleich das `next`-Attribut vom Vergleich per `attrs`-genrierten Vergleichsmethoden zwischen `LinkedList`-Objekten ausgeschlossen:

Code: Alles auswählen

#!/usr/bin/env python3
from attr import attrib, attrs


@attrs
class LinkedList:
    value = attrib()
    next = attrib(default=None, cmp=False)


def main():
    list_a = LinkedList(5, LinkedList('ab', LinkedList(0.36)))
    print('list_a', list_a)
    print('list_a third value', list_a.next.next.value)
    

if __name__ == '__main__':
    main()