View
105
Download
0
Category
Preview:
Citation preview
Verkettete Liste
Visualisierung
New-Operator
• Mit dem New-Operator kann zur Laufzeit (dynamisch) Speicherplatz reserviert und angelegt werden
• Vorteil:– Es wird lediglich der benötigte Speicherplatz
reserviert und nicht beispielsweise über ein Feld (unnötig) viel oder zu wenig Speicherplatz reserviert
– Man kann den Speicher wieder freigeben, ohne die Speicherorganisation zu zerstören (Destruktoren machen zum ersten Mal Sinn)
– Objekte können als Pointer angelegt werden– Einfacher als in der strukturierten
Programmiersprache C (dort mit malloc und calloc und free)
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Auto *start = NULL
Auto *ende = NULL
Das Programm wird gestartet
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Auto *start = NULL
Auto *ende = NULL
Button wird geklickt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start = NULL
Auto *ende = NULL
= NULL
Auto *temp
Mit dem New-Operator wirdein neues Objekt angelegt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start = NULL
Auto *ende = NULL
= NULL
Auto *temp
Wenn *start = Null ist,Setze *start und *ende
auf das neue Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Das ist der Fall
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Button wird geklickt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *
= NULL
= NULL
Auto *temp
Mit dem New-Operator wirdein neues Objekt angelegt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
= NULL
Auto *temp
Wenn *start = Null ist,Setze *start und *ende
auf das neue Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
= NULL
Auto *temp
Das ist nicht der Fall
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
= NULL
Auto *temp
Jetzt tritt der else-Fall in Kraft
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
setze den Pointer *ende->next auf *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Setzte den Pointer *ende auf *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Button wird geklickt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Mit dem New-Operator wirdein neues Objekt angelegt
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Wenn *start = Null ist,Setze *start und *ende
auf das neue Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
= NULL
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Das ist aber nicht der Fall. Also tritt
wieder der else-Fall in Kraft
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
setze den Pointer *ende->next auf *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Setzte den Pointer *ende auf *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Und so würde es weiter gehen.Ein neues Objekt würde angelegt werden durch Klicken des Buttons.*temp zeigt auf das neue Objekt.
Die Pointer würden wie zuvor
ver- bzw. umgebogen werden.
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Folgende Erweiterungsmöglichkeiten wären denkbar.
1. Erweiterung der Klasse mit dem Pointerprevious (vorheriger Knoten)
(Hier rot dargestellt)
Auto *prev
Auto *prev
Auto *prev= NULL
Auto *prev Pointer auf vorheriges Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Auto *prev
Auto *prev
Auto *prev= NULL
Eine weitere Erweiterungsmöglichkeit wäre danach:
Ein Löschen einzelner Knoten
Auto *prev Pointer auf vorheriges Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Auto *prev
Auto *prev
Auto *prev= NULL
Der gelb dargestellte Knoten soll gelöscht werden.
Was muss alles geprüft werden?Welche Pointer müssen verbogen
werden ?
Auto *prev Pointer auf vorheriges Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Auto *prev
Auto *prev
Auto *prev= NULL
Eine weitere Erweiterungsmöglichkeit wäre danach:
Ein Einfügen eines Knoten an eine bestimmte Stelle.
Hier grün eingefärbt.
Auto *prev Pointer auf vorheriges Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *prev
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Auto *prev
Auto *prev
Auto *prev= NULL
Eine weitere Erweiterungsmöglichkeit wäre danach:
Das Ändern der Nutzdaten eines Knoten an eine
bestimmte Stelle. Hier grün eingefärbt.
Auto *prev Pointer auf vorheriges Objekt
Typ
Hersteller
Farbe
KW / PS
Auto *next
Klasse Auto
Nutzdaten
Pointer auf nächstes Objekt
Lege neues Objekt an
Typ
Hersteller
Farbe
KW / PS
Auto *next
Typ
Hersteller
Farbe
KW / PS
Auto *next
Auto *start
Auto *ende
Auto *temp
Typ
Hersteller
Farbe
KW / PS
Auto *next = NULL
Auto *prev
Auto *prev
Auto *prev= NULL
Auto *prev Pointer auf vorheriges Objekt
Eine weitere Erweiterungsmöglichkeit wäre danach:
Das Tauschen zweier Knoten bzw. derer Knoten
Hier grün eingefärbt.
Erweiterungsmöglichkeiten
• Sortierstartpointer
• Sortierendepointer
• Sortierpreviouspointer in der Klasse
• Sortiernextpointer in der Klasse
Recommended