einfach verkettete Liste

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Wünsche allen einen schönen Nachmittag!

Vorab:
Ja, es ist eine Hausaufgabe. Nur leider komm ich nicht weiter und wäre über eine Hilfestellung oder einen Denkanstoß sehr dankbar.

Aufgabe: Initialisieren Sie eine einfach verkettete Liste mit Zufallszahlen!

Wenn ich die verketteten Listen richtig verstanden habe, dann enthält ein Knoten die Daten und den Verweiß auf den nächsten Knoten, bis das nächste Element NIL ist?

In den Vorlesungen sieht der Konstruktor für einen Knoten wie folgt aus:

Code: Alles auswählen

class Node:
    def __init__(self, d):
        self.data = d
        self.next = None
Für meine Aufgabe sollte die Funktion Append genügen. Die ist wie folgt definiert:

Code: Alles auswählen

def append(data, list):
    node = Node(data)
    if list is None:
        node.next = None
        return node
    i = list
    while i.next is not None:
        i = i.next
    i.next = node
    node.next = None
    return list
nach dem Python4Kids Kapitel 17 ("Die Klasse Knoten") wird dann getestet, ob alles funktioniert, indem man mal einen Knoten erzeugt:

Code: Alles auswählen

node = Node(7)
print(node)
So werden die Knoten erzeugt, mit node.next verweist er auf den nächsten Knoten usw.
Um nun einen Inhalt in die Liste einzufügen, müsste ich die funktion append aufrufen.

Hier komm ich nicht weiter. Ich glaube mir fehlt hier das essentielle Verständnis...

Ich probiere es mal in Worte zu fassen was ich nicht verstehe:

Ich erzeuge die Klasse "Knoten". Diese hat die 2 Eigentschaften self.data und self.next, wobei das "self" nur zum erstmaligen erzeugen der Klasse dient (sorry, OOP haben wir eigentlich noch nicht gemacht, hab jedoch ein bisschen Vorwissen - was nicht unbedingt gut ist).
Was mir nicht klar ist:
* wozu der Parameter "list" in der Funktion append dient.
* wie verwende ich .next? in der Klasse Node ist .next immer = None?
* Wenn .data zum Einfügen von Elementen dient, wofür brauch ich dann die Funktion Append?

Zusammenfassend kann ich nur sagen, dass ich trotz viel Zeitaufwand das zu verstehen, einfach nur verwirrt bin und hoffe, dass mir wer den richtigen Weg zeigen kann, damit mir ENDLICH ein Licht aufgeht.

Danke schomal.
Benutzeravatar
noisefloor
User
Beiträge: 3843
Registriert: Mittwoch 17. Oktober 2007, 21:40
Wohnort: WW
Kontaktdaten:

Hallo,
Wenn ich die verketteten Listen richtig verstanden habe, dann enthält ein Knoten die Daten und den Verweiß auf den nächsten Knoten, bis das nächste Element NIL ist?
Das wäre schon wichtig zu wissen - weil das ja essentiell wichtig für die Aufgabe ist... NIL gibt es in Python nicht (aber z.B. in Lua). "Nichts" ist in Python `None`.

Mit `self` referenziert die Klasse ich selber. `list` ist der Name des Parameters, unter dem es in der Funktion referenziert werden kann. Wobei `list` ein denkbar ungünstiger Name ist, weil es die Build-In Funktion `list` überschreibt - was unerwünschte Nebeneffekte haben kann.

Was mir basierend auf deine Ausführung nicht klar ist: _wie_ soll denn auf den nächsten Konten verwiesen werden? Der muss ja irgendwie "benannt" werden (und damit existieren), um einen Verweis darauf speichern zu können.

Gruß, noisefloor
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Danke schonmal für die Antwort!
Was mir basierend auf deine Ausführung nicht klar ist: _wie_ soll denn auf den nächsten Konten verwiesen werden? Der muss ja irgendwie "benannt" werden (und damit existieren), um einen Verweis darauf speichern zu können.
Soweit ich das verstanden habe, sollte mit Node.next auf den nächsten Knoten verwießen werden.
"Erstellt" wird so einer zb. mit

>>> node1 = Node(1)
>>> node2 = Node(2)


Mit `self` referenziert die Klasse ich selber. `list` ist der Name des Parameters, unter dem es in der Funktion referenziert werden kann. Wobei `list` ein denkbar ungünstiger Name ist, weil es die Build-In Funktion `list` überschreibt - was unerwünschte Nebeneffekte haben kann.
Worauf soll list in der Funktion referenzieren? Was wäre denn ein Beispiel für einen Übergabewert bzw. was soll damit gemacht werden?
Der Code ist aus den Vorlesungs-Folien.
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Deine Liste ist immer einfach nur ein Knoten, auch genannt der Kopf der Liste. Und ein Knoten mit next == None ist einfach nur eine einelementige Liste.

Und damit sollte doch auch klar werden, was append macht: es nimmt ein Datum, erzeugt einen neuen Knoten, und wenn man KEINE Liste (List == None) übergeben hat, ist das die neue Liste. Wird ja auch zurück gegeben.

Und wenn man doch eine Liste übergeben hat, rennt append bis an deren Ende, und haengt die da an. Und gibt die Liste zurück.
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Okay...

Ich denke was mir nicht klar ist, ist das zusammenspiel der Knoten und der Liste(n)



Wie hat denn das Grundsätzlich auszusehen?
Ich erzeuge mir die Knoten und zu jedem Knoten eine Liste.
Die muss ich dann verknüpfen.

Mit dem Code aus dem Eingangspost würde ich das theoretisch wie folgt machen:

Code: Alles auswählen

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3

Node.data.append(7) 
Mir ist klar, dass das nicht richtig ist. Aber wie füge ich dann an der richtigen Position ein Element zum richtigen Knoten ein?

Ich weiß, dass das Grundwissen sein sollte - nur leider schließt sich mir das mit den bisherigen Unterlagen nicht.
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Dein append macht das, was du da von Hand machst. Und das ist eine Funktion, wieso rufst du die als Methode auf einem Knoten auf? Bzw. noch schlimmer, auf dem Datum data, das ja alles sein kann, und ueberhaupt nix mit append zu tun hat.

Und append kennt auch keine Position, erst recht keine "richtige". Was soll das denn sein?

Bau dir erstmal eine Liste mit drei Elementen nur mit append. WICHTIG: append bekommt ein *DATUM* (Einzahl von Daten, nicht der Tag) als erstes Argument, und einen Knoten/Liste als zweites, *ODER* None, wenn du eine neue Liste machen willst.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Du erzeugst nur Knoten. Jeder Knoten kann ein Datum enthalten und auf einen weiteren Knoten zeigen. So entsteht eine Liste.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@Reversibuh: was ich nicht verstehe ist, warum Du eine Klasse geschrieben hast, obwohl in Deinem Kurs noch gar keine Klassen behandelt wurden, und warum Du ein »append« hast, das Du aber gar nicht verstehst, also gar nicht selbst geschrieben hast.

Vielleicht solltest Du die Aufgabe selbst mit den Mitteln, die Du schon kennst, lösen.
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Super, danke an die 2 letzten Antworten... Denke ich habs verstanden. Zumindest konnte ich den Inhalt und die Speicheradresse des Verweißes ausgeben.

Dann probier ich mal Suchalgorithmen damit zu schreiben :lol:
Schönen Abend wünsch ich noch.
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Ich bin normalerweise nicht so, aber weil du sonst ja vernünftig formulierst: Hinweise, Verweise und Naseweise haben nichts mit der Farbe Weiß zu tun. :mrgreen:
Reversibuh
User
Beiträge: 8
Registriert: Freitag 5. Januar 2018, 14:31

Oh...
Hatte ich wohl falsch im Kopf. Danke für den Hinweis :)
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

Sirius3 hat geschrieben:@Reversibuh: was ich nicht verstehe ist, warum Du eine Klasse geschrieben hast, obwohl in Deinem Kurs noch gar keine Klassen behandelt wurden, und warum Du ein »append« hast, das Du aber gar nicht verstehst, also gar nicht selbst geschrieben hast.
Na ja, die Klasse wird ja wie ein Struct/Record verwendet; die Aufgabe ist ja an sich schon als Python verkleidetes C/Pascal. Insofern kann ich mir schon vorstellen, dass das genau so vorgegeben ist.
Antworten