Entwickler-Ecke :: Thema anzeigen - Fragen zu verketteten Listen

Len - Sa 22.05.10 14:11
Titel: Fragen zu verketteten Listen

Hallo Delphi-forum.de .
Ich lerne gerade für meine mündliche Informatikprüfung am Mittwoch.

Ich muss sagen, dass ich wegen persönlicher, aber auch wegen organisatorischer Schwächen der Schule nie wirklich gut in Informatik war. (5-6 Punkte)
Nun habe ich mich in der Vorabizeit mit Referaten etc. echt hochgekämpft auf 10 Punkte, die mir echt viel bedeuten.

Nun aber zum Kerngeschehen:
Im B-Teil meiner mündlichen Prüfung (Frage-Antwort-Spielchen) dreht es sich um Listen und Bäume. Hier möchte ich mich jedoch auf die Listen beziehen.

Was wir können müssen ist:
Einfach verkettete Liste, Doppelverkettung, Ringliste, Rekursion

Der Kern liegt auf der einfachen Verkettung, da müssen wir folgendes beherrschen:
Am Anfang einketten,
Am Ende einketten,
Mitte Einketten
Ausketten

So nun liegt Delphi mir wirklich nicht und ich hoffe ihr könnt mir helfen, ich habe natürlich Material aus dem Unterricht. Das auswendig lernen bringt mir natürlich nicht viel, ich muss das schließlich erklären und dafür muss ich es verstanden haben.

In der entsprechenden Word-Datei ist das ganze so verfasst:
1) Deklaration
type tzeiger=^telement;
telement=record
vorname:string;
zeiger:tzeiger;
end;
var zkopf,zneu,zvorg,zlauf:tzeiger;

2) Initialisieren der Liste:
zkopf:=NIL (leere Liste)

3) Neuen Speicherplatz generieren, bekannt durch den Zeiger darauf:
new(zneu);

4) Elementinhalt setzen:
Mit zeiger^ wird das bezeigte Element angesprochen:
zneu^.vorname:=edvorname.text;

5) Element verketten am Anfang:
zkopf:=zneu; (nach vorne verketten) zneu^.zeiger:=NIL oder (dann aber vorher) zneu^.zeiger:=zkopf;

6) Liste entlang laufen, d.h. zlauf immer weiter setzen:
zlauf:=zkopf;
while zlauf<>NIL do
zlauf:=zlauf^.zeiger;

7) Element ans Ende verketten:
Liste bis zum Ende laufen, Vorgängerzeiger merken. Am Ende ist zlauf=NIL und zvorg zeigt auf das letzte Element.
zvorg^.zeiger:=zneu;
zneu^.zeiger:=NIL

8) In der Mitte verketten:
Die Liste entlang laufen, bis der Platz gefunden ist (zwischen zvorg^ und zlauf^):
zvorg^.zeiger:=zneu;
zneu^.zeiger:=zlauf;

Könntet ihr mir vlt. von Punkt 5 bis Punkt 8 das ganze noch einmal versuchen in Worten zu erklären? Das wäre super nett! Da stehen zwar schon Beschreibungen bei, aber wenn dann mal mehr gefragt wird, als in der Erklärung steht, dann steh ich absolut auf'm Schlauch.
Ich denke, dass das Thema von meinem Infolehrer sehr dankbar ist und auch machbar, jedoch kenne ich wirklich niemanden, der mir das vernünftig erklären könnte, weshalb ich mich an euch wende.

edit: Skizzen wären natürlich optimal - man wird ja wohl noch träumen dürfen ;)
edit²: Wir haben in der Prüfung natürlich keinen PC als Hilfe, wir müssen das an einer Tafel machen.

Gruß,
Len

Moderiert von Narses: Titel geändert, war: "Mündliche Informatikprüfung - Listen".

Jakob_Ullmann - Sa 22.05.10 15:16

Also erstmal: euer Lehrer sollte sich an gewisse Standards halten, wozu gehört, dass ein Zeigertyp immer mit einem P und nicht mit einem T oder einem z beginnt.

5. Es wird einfach ein neues Element generiert, das auf das bisherige erste zeigt und das wird anschließend als erstes gesetzt. Somit wird das neue zum ersten und das bisherige erste zum zweiten Element.

Delphi-Quelltext

1:
2:
3:
4:
5:

New(zneu);  // generieren
{ nun hat es eine Eigenschaft zeiger, die auf das nächste zeigen soll.
  das bisherige erste ist noch mit zkopf ansprechbar }
zneu.zeiger := zkopf;  // Falls das zum Verständnis beiträgt: zneu.zeiger := @(zkopf^);
zkopf := zneu;

6. Liste entlang laufen

Ich denke mal, so ist es besser:

Quelltext

1:
2:
3:
4:

Beginne ganz am Anfang
Wiederhole das hier:
  Mache mit dem nächsten Element weiter. Also mit dem, auf das gezeigt wird.
und zwar, bis wir hinten angekommen sind (also bis auf nichts gezeigt wird)

heißt:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

// Beginne
zlauf := zkopf; // erstes Element
// Wiederhole das hier:
repeat
  // Mache mit dem nächsten Element weiter.
  zlauf := zlauf^.zeiger;
// bis auf nichts gezeigt wird
until zlauf^.zeiger = nil; // not in list

Ich denke, dass die repeat-until-Schleife mehr zum Verständnis beiträgt, aber die Variante mit while ist trotzdem besser (Spezialfall: es gibt nur ein Element).

7. Erstmal müssen wir die Liste entlang laufen. Dafür nehmen wir den Code von 5. Danach sollte ja zlauf auf das letzte Element zeigen. Den Namen behalte ich mal bei:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

// Zuerst neues Element erzeugen, was danach das letzte sein soll:
New(zneu);
// Das bisherige letzte Element bekommt das neue als Nachfolger
zlauf := zneu;
// Irgendwohin muss das letzte (jetzt bereits zneu) ja zeigen, wenn auch auf nichts:
zneu^.zeiger := nil; // Beachte: nil ist schon ein Zeiger. Zeigt soweit ich weiß auf Adresse $0

8. In die Mitte:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

// Neues Element erzeugen
New(zneu);
// Der Vorgänger (zvorg) muss natürlich spezifiziert werden.
// Annahme vom Lehrer: zvorg ist der Vorgänger von zlauf, also zvorg^.zeiger = zlauf,
// was ich ehrlich gesagt bescheuert finde. ;-)

// der neue Nachfolger von zvorg ist jetzt zneu und zneu bekommt als Nachfolger zlauf
zvorg^.zeiger := zneu; // Klar, wieso es zvorg^ mit ^ heißen muss?
zneu^.zeiger := zlauf;

Nebenbei: Die Bezeichnung .zeiger ist krank. Variablennamen müssen wie Eigenschaften selbsterklärend sein. In dem Fall steht "zeiger" für Nachfolger. Gängig wäre eine Bezeichnung wzb. Succ für Successor.

Len - Sa 22.05.10 15:36

Hallo Jakob_Ullmann.

Danke für deine Hilfe, hat mir echt geholfen. Zur Verteidigung meines Infolehrers muss ich sagen, dass wir keinen "richtigen" Informatiklehrer haben. Unser Lehrer hat das wohl nur über Fortbildungen beigebracht bekommen, er hat es aber nicht studiert. Schon traurig für ein Gymnasium mit dem Ruf einer "Eliteschule" (was sie definitiv nicht ist ;) )

Bei Punkt 8 (Mitte verketten) bin ich mir nicht ganz sicher, ob ich das verstanden habe:

Der Vorgängerzeiger wird auf das einzukettende Element gerichtet (zvorg^.zeiger := zneu;).
Der Zeiger vom einzukettenden Element wird auf den Laufzeiger gerichtet (zneu^.zeiger := zlauf;)

stimmt das so ?

Gausi - Sa 22.05.10 15:38

Hallo und :welcome: in der Entwickler-Ecke,

am besten macht man sich sowas mit einer kleinen Skizze klar, was da zu tun ist. Ich hab das für den Punkt 5 (einfügen am Kopf) mal probiert.

Wenn das neue Element den neuen Kopf bilden soll, muss der Nachfolger (Zeiger) vom neuen Element zneu auf den alten Kopf zkopf zeigen, und hinterher der Kopf auf das neue Element. Das ist dann auch schon alles.

anfang

Und wenn man zwischendurch was einfügen möchte, ist das ebenso einfach. Knapp umschrieben wird das mit "Zeiger umbiegen". :D

Jakob_Ullmann - Sa 22.05.10 15:51

Len hat folgendes geschrieben :

Der Vorgängerzeiger wird auf das einzukettende Element gerichtet (zvorg^.zeiger := zneu;).
Der Zeiger vom einzukettenden Element wird auf den Laufzeiger gerichtet (zneu^.zeiger := zlauf;)

stimmt das so ?

Ja, nur dass hier zlauf die Funktion des Nachfolgers hat. Also das einzukettende Element soll zwischen Vorgängerzeiger und Laufzeiger gekettet werden. Aber bei dem Code ist der Laufzeiger nunmal als das letzte Element gebraucht worden, was aber keine Einschränkung ist. Deshalb sage ich ja: tolle Benennung, ;-)

Delete - Sa 22.05.10 17:57

Hier ist noch etwas praktischer Lesestoff: http://www.michael-puff.de/Programmierung/Delphi/Tutorials/Listen/
- Arrays
- Einfach verkettete Listen
- Doppelt verkettete Listen

Len - Mo 24.05.10 12:12

Hey, ich bin's nochmal ;)

Danke für Eure Hilfe, es hat echt was gebracht!
Nur ist mir eingefallen, dass ich das "Ausketten" vergessen habe.

Könnte mir das jemand erklären ? Ich habe dazu leider auch keine Unterlagen, was die Sache nicht einfacher macht :(

jaenicke - Mo 24.05.10 12:20

Du meinst die Löschung eines Elements? Nun, was muss denn dabei passieren? Der Zeiger von dem vorherigen Element muss auf das dahinter zeigen, so dass das zu löschende Element weg ist.

Quelltext

1:
2:
3:
4:

O===O===O===O
-->
O===O=======O
        O

Schon ist das zu löschende Element raus aus der Liste. Bei einer doppelt verketteten Liste muss natürlich auch der Zeiher des folgenden Elements noch umgebogen werden. (Auf das Element vor dem zu löschenden)

Len - Mo 24.05.10 12:35

Also muss ich einfach den Vorgänger auf den Nachfolger setzen?

Also zvorg^.zeiger:=zlauf;

?

jaenicke - Mo 24.05.10 13:23

Richtig, und das aktuelle Element muss dann natürlich noch freigegeben werden, sonst hängt das weiter im Speicher herum.

Jakob_Ullmann - Mo 24.05.10 14:21

Kleiner Tipp noch: Du erhöhst die Lesbarkeit, wenn du deine Delphi-Codes mit [delphi]{dein Code} s := 'Text';[/delphi] umschließt:

Delphi-Quelltext

1:	{dein Code} s := 'Text';

Len - Di 25.05.10 10:58

jaenicke hat folgendes geschrieben :

Richtig, und das aktuelle Element muss dann natürlich noch freigegeben werden, sonst hängt das weiter im Speicher herum.

Wie mach ich das denn ?

Delphi-Quelltext

1:
2:
3:
4:
5:

New(zneu);  // generieren
{ nun hat es eine Eigenschaft zeiger, die auf das nächste zeigen soll.
  das bisherige erste ist noch mit zkopf ansprechbar }
zneu^.zeiger := zkopf;  // Falls das zum Verständnis beiträgt: zneu.zeiger := @(zkopf^);
zkopf := zneu;

Das habe ich auch noch nicht ganz verstanden.

Dass zkopf auf zneu deuten muss, ist mir klar.
Aber wiese wird der Zeiger von zneu auf zkopf umgebogen und nicht auf zlauf, der ja der Nachfolger(Succ) ist ?

ALF - Di 25.05.10 11:21

Hi, dazu gibt es die Eigenschaft Free.
Also "element.free" z.B.

Gruss Alf

Len - Di 25.05.10 18:27

Moderiert von Narses: Selbst-Zitat entfernt.

Danke@ ALF.

Sorry, dass ich so penetrant pushe, aber morgen geht's los, wär nett, wenn mir das noch jemand beantworten würde ;)

Gruß,

Len

jaenicke - Di 25.05.10 20:42

ALF hat folgendes geschrieben :

Hi, dazu gibt es die Eigenschaft Free.
Also "element.free" z.B.

Das gibt es bei Records nicht. ;-)
Dafür gibt es das Gegenstück zu New, nämlich Dispose.