Fragen zu verketteten Listen

Len · Hält's aus hier Beiträge: 6

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

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 · Verfasst: 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.

markieren

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:

markieren

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:

markieren

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:

markieren

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:

markieren

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 · Hält's aus hier Beiträge: 6

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 · Verfasst: Sa 22.05.10 15:38

Hallo und

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".

Einloggen, um Attachments anzusehen!

_________________
We are, we were and will not be.

Jakob_Ullmann · Verfasst: 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, ;-)

Ehemaliges Mitglied Erhaltene Danke: 1

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

Len · Hält's aus hier Beiträge: 6

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 · Verfasst: 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.

markieren

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 · Hält's aus hier Beiträge: 6

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

Also zvorg^.zeiger:=zlauf;

?

jaenicke · Verfasst: 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 · Verfasst: 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:

markieren

Delphi-Quelltext

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

Len · Hält's aus hier Beiträge: 6

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 ?

markieren

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 · Verfasst: Di 25.05.10 11:21

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

Gruss Alf

_________________
Wenn jeder alles kann oder wüsste und keiner hätt' ne Frage mehr, omg, währe dieses Forum leer!

Len · Hält's aus hier Beiträge: 6

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 · Verfasst: 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.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme