Verkettung ? Fragen für Info-Klausur

[VeeJay]

Hallo,
wir schreiben am 10.01. eine Informatik-Klausur und bis dahin müssen wir das Prinzip der Verkettung verstanden haben. Leider habe ich das Wort "Verkettung" in keinem einzigen Forum gesehen und darum wollte ich fragen ob mir jemand von euch das Prinzip der Verkettung erklären kann
und wofür man sachen wie "new(a)" oder "a^:='B'" braucht.

Delphi-Quellcode:

Type pointertyp=^char;
Var a,b,c,d,e,f,hilf :pointertyp;

Procedure Zeigerchaos;
Var s:string;
Begin

new(a);new(b);new(c);
new(d);new(e);new(f);

a^:='B';
b^:='a';
c^:='s';
d^:='i';
e^:='c';

form1.edit1.text:=a^+b^+c^+d^+e^;

new(a); a^:='P';
hilf:=e;
e:=b;
d:=hilf;
f^:='l';

form1.edit2.text:=a^+b^+c^+d^+e^+f^;
end;

[Hansa]

suche mal nach "verkette Liste" oder Pointer

Gruß
Hansa

[Sebastian Nintemann]

Hallo und herzlich willkommen!

Zitat von VeeJay:

...und wofür man sachen wie "new(a)" oder "a^:='B'" braucht.

Erst einmal dazu:

Code:

new(a);

Dies reserviert den Speicher für eine neue, dynamische (weil zur Laufzeit erstellte) Variable, sie reserviert so viel Speicher, wie der Typ auf den der Zeiger a zeigt braucht. Ein Zeiger (Pointer) beinhaltet ja nur die Adresse im Speicher einer bestimmten Variable. Damit zeigt a jetzt auf eine Variable, auf die mit a^ (Dereferenzierungsoperator) zugegriffen werden kann.
Mit

Code:

a^ := 'B';

weist du also dem Speicher auf den a zeigt den Inhalt 'B' zu.

Aber es fehlt in der procedure die freigabe des reservierten Speichers, bei dynamischen Variablen macht Delphi das nämlich nicht automatisch, wie bei zB lokalen Variablen!

Zitat von Delphi OH:

When an application is finished using a dynamic variable created with New, it should dispose of the memory allocated for the variable using the Dispose standard procedure.

Also wenn man mit der Arbeit mit einer mit new() erzeugten Variable fertig ist oder eine neue Variable mit a erschaffen werden soll muss man den Speicher mit

Code:

dispose(a);

erst wieder freigeben.

Ich hoffe das war jetzt ein bisschen verständlich

Gruß, Sebastian

[VeeJay]

Danke erstmal
Also wenn ich das jetzt richtig verstanden habe ist die "Verkettung", das Prinzip, womit man erweiterbare Datenbanken machen kann, weil man mit new(xyz) immer neue Glieder erstellen kann. Und wenn man auf dieses neue Glied zugreifen will, muss man xyz^ benutzen ?

Ich hoffe mal das stimmt so. Dann wäre das ganze nämlich gar nicht sooo schwer.

Kann mir vielleicht noch jemand von euch ein kleines einfaches Beispiel für eine dynamische verkettete Datenbank geben?

[Sebastian Nintemann]

Hallo VeeJay, was jetzt beau mit Verkettung gemeint ist kann ich dir nicht sagen, da ich den Begriff so nicht kenne. Auf die neu erstellten Daten musst du aber, wie du richtig gesagt hast mit
xyz^ zugreifen, der ^-Operator dereferenziert den Zeiger, man erhält also mit a^ den Speicherinhalt der an der Adresse a steht.
Gruß, Sebastian

[Christian Seehase]

Moin VeeJay,

also irgendwie komme ich dabei in's Schleudern, wenn ich mir auf der einen Seite Dein Sourcecodebeispiel ansehe, und dann auf der anderen Seite etwas von Verkettung bei Datenbanken höre.

Im zweiten Falle würde ich, wie Hansa auch, an den Begriff verkettete Listen denken.

Das dahinterstehende Prinzip ist recht einfach:

Jeder Datensatz in einer Datei fängt an einem Bestimmten Byte relativ zum Dateianfang an.
Das heisst, der erste Satz fängt immer am Offset (Dateibeginn + Offset = Position in der Datei) 0 an.
Ist die Datei als verkettete Liste aufgebaut, enthält jeder Satz auch noch den Offset des in der logischen Reihenfolge als nächstes kommenden Datensatzes. Ist dieser Wert z.B. 0 oder ein besonderer Wert, der real nicht vorkommen kann, oder entsprechend festgelegt wird, hat man das Ende der Liste erreicht.
Durch diese Methode ist es dann relativ einfach, eine Satz in der logischen Reihenfolge einzufügen.
Man schreibt ihn an das Ende der Datei, sucht den Satz, der vor diesem kommen muss, merkt sich den Offset des Folgesatzes, und ersetzt ihn durch den des neu hinzugefügten.
Anschliessend, wird dann der gespeicherte Offset des Folgesatzes in das dafür vorgesehene Feld des neuen Satzes geschrieben und fertig.
Löschen geht dann ahnlich (Offset des dem zu löschenden Datensatzes folgenden Satzes in den des vorher kommenden schreiben)
Dadurch entstehen dann, mit der zeit Dateien, die auch viel Datenmüll enthalten, und die man deshalb gelegentlich, komprimieren muss.

Schneller geht's dann mit doppelt verketteten Listen, wo jeder Eintrag den Offset des folgenden und den des vorhergehenden erhält.

Wenn man statt des Offsets Indizes verwendet kann man mit diesem Prinzip auch Arrays verwalten.

[Chewie]

Wenn ich mich nicht irre, hab ich das mal auf Bayern-Alpha (IT-Kompaktkurs) gesehen. Bei C++ benutzt man die Verkettungen, weil es keine Listen gibt, deren Größe man zur Laufzeit ändern kann. Bei Pascal gibt es dies aber (SetLength bei dyn. Arrays) und die Verkettung ist deshalb nicht unbedingt notwendig.
Oder verwechsle ich da jetzt was?

[Hansa]

Hi,

Zitat von Chewie:

Wenn ich mich nicht irre...... Bei C++ benutzt man die Verkettungen, weil es keine Listen gibt, deren Größe man zur Laufzeit ändern kann....Oder verwechsle ich da jetzt was?

Uff, das Prinzip der verketteten Listen ist meines Wissens in C weit verbreiteter, als in Pascal, bzw. Delphi. Falls nicht, kommt hoffentlich ein Kommentar.

Gruß
Hansa

[fiasko]

Zitat von Chewie:

Wenn ich mich nicht irre...... Bei C++ benutzt man die Verkettungen, weil es keine Listen gibt, deren Größe man zur Laufzeit ändern kann....Oder verwechsle ich da jetzt was?

Soweit ich weiß, sind dynamische Array gerade in der C Welt sehr beliebt. Es läßt sich damit wesentlich einfacher als unter Pascal & Co. umgehen (da ist einfach jeder Zeiger ein Zeiger auf ein Array, und ein Array automatisch ein Zeiger).

Der Quelltext vom ersten Posting sieht aber nich so aus, als sollte hier irgendwas mit dyn. Listen oder Arrays gemacht werden. Auf mich hat das eher so den Eindruck das der Lehrer hier das verknüpfen der Char-Zeiger und was dann nach den lustigen Wertzuweisungsspielchen herauskommt meint.


Thomas

[Hansa]

Hi,

Zitat:

. Auf mich hat das eher so den Eindruck das der Lehrer hier das verknüpfen der Char-Zeiger und was dann nach den lustigen Wertzuweisungsspielchen herauskommt meint.

So isses. Die fangen immer so an. Es geht um verkettete Listen. Ein Pointer (Zeiger) hat immer mindestens zwei Bestandteile : den Inhalt und die Adresse des nächsten Listen-Elementes. Dies hat wieder einen Inhalt und die Adresse des nächsten usw. Wer das durchschaut hat, kann auch den Zeiger an das Anfangselement zurückgeben, das wäre dann sozusagen ein Kreis. Aber ein Anfang muß auch her : NIL. Will nicht wissen, wieviele mit NIL operieren, ohne zu wissen, was das ist. Soviel von mir.

Gruß
Hansa