Hi,
leider kann ich dir kein Buch empfehlen, aber ich denke du findest schon hier viel Hilfe zu Pointern. Was möchtest du denn genau wissen (also da du bis Baumstrukturen gehen willst gehe ich davon aus, dass du das grob weißt).
Über Pointer gibt es gar nicht so viel zu sagen (was nichts mit Mächtigkeit oder Schaden zu tun hat). Ein Pointer ist ein Zeiger (ok, geht irgendwie aus dem Namen hervor).
Ein Pointer ist dabei halt ein Zeiger auf eine Speicheradresse. Deshalb ist ein Pointer auch immer ein Prozessorwort groß (also bei 32-Bit CPU u. BS 32, bei 64 Bit dann natürlich 64 Bit etc).
Was aber nun an der Stelle steht, auf die man zeigt, geht nicht aus dem Pointer hervor.
Die Adressen auf die ein Pointer zeigen kann sind immer größer 0. Die Adresse 0 ist reserviert und besonders. Zeigt ein Pointer auf 0 (man sagt auch Nullzeiger *g*), dann zeigt er auf nichts. In Delphi weißt man einem Pointer dazu den wert nil zu (nil = Nullzeiger).
Wenn du nun einen Pointer darauf prüfst, ob er nil ist oder nicht, kannst du so testen ob ihm schon eine Adresse zugewiesen wurde. Wenn er auf nil zeigt, heißt dass, das er auf keine Information zeigt. Also solltest du auch nicht versuchen dort etwas zu lesen, dass führt zu Fehlermeldungen.
Pointer sind zwar sehr mächtig und in sehr Hardwarenahen Sprachen gibt es auch kaum einen Ersatz, aber Pointer werden eigentlich immer gerne gemieden. Der Grund dafür ist einfach, es gibt typisierte Pointer, so genannte Referenzen. Sie machen nicht viel anders als ein Pointer, ausser dass sie auf einen bestimmten Datentypen zeigen.
So zeigen sowohl Pointer als auch Referenzen auf einen Speicherbereich, aber bei einer Referenz kennst du den Datentypen, der sich an dieser Stelle befindet.
Das Problem an einem Pointer ist, dass du ihn leicht auf den falschen Speicherbereich zeigen lässt. Da er nicht prüfen kann was sich an dieser Adresse befindet, kannst du dir also auch Speicher überschreiben, auf den du garnicht zugreifen wolltest.
In Delphi begegnen dir Referenzen implizit immer, wenn du es mit Instanzen von Klassen zu tun hast. Ich würde dir empfehlen Listen und Bäume immer mit Klassen zu realisieren, hat wie ich finde viele Vorteile.
Aber machen wir mit Pointern weiter.
Wie gesagt, immer wenn es um Pointer geht sollte man vorsichtig sein. Trotzdem hat sich sicherlich jmd. was dabei gedacht Pointer einzuführen. Die Grundidee ist recht einfach. Wenn du große Datenstrukturen hast, sagen wir mal nur 40 Byte und du übergibst diese an eine Prozedur und schreibst sie irgendwann in den Speicher zurück, dann müssen jedesmal 40 Byte verschoben werden. Zeigst du hingegen nur auf die Adresse der Datenstruktur, müssen nur 4 Byte (bei einer 32-Bit CPU) verschoben werden. Das ist aber auch die optimale Größe für CPU zugriffe, ein Pointer ist gerade so groß wie ein CPU Register.
Somit sparst du also Zugriffe auf den Speicher, das steigert die Performance.
Eine andere Sache ist es, dass du Variablen in der Regel Call-By-Value übergibst (wie gesagt i.d.R, gibt auch Programmiersprachen wo das anders ist). Was heißt das? Nun ja, wenn du eine Zahl an eine Funktion übergibst und diese in dieser Funktion änderst, dann gilt die Änderung nur für die Funktion. Die eigentlich übergebene Variable behält ihren eigentlichen Wert.
Eine Alternative dazu heißt Call-By-Value-Result. Hier wird die übergebene Variable nach der Abarbeitung der Funktion in den Speicher der Variablen zurück geschrieben. Hier stößt du natürlich auch wieder auf das Problem der großen Datentypen.
Eine andere Möglichkeit ist es natürlich einfach einen Zeiger auf die Adresse der Variablen zu übergeben.
Wenn du nun in den Bereich auf den der Pointer zeigt schreibst, änderst du natürlich auch den Wert, der in der Variablen steht.
Wird sicher deutlicher durch ein Beispiel
Delphi-Quellcode:
// Hier call by Value
procedure CallByValue(Value : Integer);
begin
inc(Value); // erhöht den Wert von Value um 1
end;
// Hier call by value result
procedure CallByValueResult(var Value : Integer);
begin
inc(Value); // erhöht den Wert von Value um 1
end;
// Und nun mit einem Pointer
procedure CallWithPointer(p : Pointer);
begin
inc(Integer(p^));
// p^ dereferenziert den Pointer
// Integer(p^) castet / interpretiert den Wert als Integer
// inc erhöht den Wert um eins
end;
procedure Test;
var V : Integer;
begin
V := 0;
CallByValue(V);
// V = 0
CallByValueResult(V);
// V = 1
CallWithPointer(@V);
// V = 2
end;
Ok, wie du hier siehst macht verändert der erste Aufruf den Wert von V garnicht. Doch wird der Wert in jeder Funktion um 1 erhöht. Bei CallByValueResult wird der Wert von V um 1 hochgezählt, macht also das was du willst, aber es bleibt das Problem der großen Datentypen. Nun ja, es gibt Compiler die ein Call-by-Value-Result über Referenzen realisieren, aber dass möchte ich nur der Vollständigkeit halber erwähnen (wäre dann natürlich auch Call-By-Reference, aber egal).
Hier ist der letzte Fall interessant. Schauen wir uns erstmal die Funktion CallWithPointer an. Als Parameter übergibst du hier kein Integer sondern einen Pointer. Das heißt p enthält an dieser Stelle wirklich nur eine Adresse. Würdest du jetzt den Wert von p verändern, so veränderst du nur die Adresse auf die der Pointer zeigt. Also Vorsicht!
Wenn du den Wert hinter der Adresse ändern möchtest, musst du den Pointer dereferenzieren. Dass machst du mit dem ^ (hinter dem p). Da der Pointer Typenlos war, weiß Delphi nicht, was genau sich an dieser Adresse befindet. Also musst du noch sagen, was genau da stehen soll. Dazu castest du einfach den Wert an dieser Stelle (hier also in ein Integer). Durch dieses Integer(p^) liest Delphi also 32 Bit (Länge von Integer) ab der Adresse p und interpretiert diese als Vorzeichenbehaftete Zahl.
Schauen wir uns noch den Aufruf an. Während du bei CallByValue und CallByVaueResult einfach die Integer-Variable übergeben kannst, erwartet die letzte Funktion eine Adresse. Die Adresse einer Variablen bekommst du, indem du ein @ vor die Variable schreibst. Soviel zu dem kurzen Programm.
Wie gesagt, Pointer sind an sich untypisiert, aber es gibt auch typisierte Pointer. Ein paar findest du schon vordefiniert in Delphi (ich denke in der
Unit System), aber du kannst dir zu jedem Typen einen typisierten Pointer erstellen. Nach Konvention sollten Pointertypen immer mit einem vorangestellten P beginnen. Das macht es auch leichter einen Pointer als solchen zu erkennen.
Bei einem typisierten Pointer ändert sich nicht viel. Der einzigste Unterschied liegt darin, dass Delphi hier eine Adresse auf eine Variable vom richtigen Typ erwartet (ACHTUNG, muss unter Projekt|Optionen|Compiler|Typisierter @-Operator eingeschaltet werden). Ist die Option abgeschaltet, kannst du auch gleich mit untypisierten Pointern arbeiten.
Da sich alles leichter mit einem Beispiel erklären lässt, das gleiche Beispiel mit typisiertem Pointer
Delphi-Quellcode:
type
PInteger = ^Integer; // definiert einen typisierten Pointer
procedure CallWithPointer(p : PInteger);
begin
inc(p^); // erhöht den Wert auf den p zeigt um 1
end;
procedure Test;
var V : Integer;
B : Byte;
begin
V := 0;
CallWithPointer(@V);
// V = 1
CallWithPointer(@B);
// Delphi Compiler warnt (wenn Option angeschaltet)
end;
Wie du hier siehst, entfällt einerseits das mit dem Casten, da PInteger ein Zeiger auf ein Integer ist. Gleichzeitig kann nun der Compiler prüfen ob die übergebene Adresse auch auf den richtigen Typ zeigt. Da CallWithPointer nun einen Zeiger auf ein Integer erwartet, wird die Adresse von B nicht akzeptiert. Dies ist auch gut so, immerhin ist ein Byte nun mal nur 1 Byte, ein Integer aber 4 Byte groß.
Würdest du also versuchen an die Adresse von B 4 Byte zu schreiben, dann überschreibst du dir gleich 3 Byte (ohne zu wissen was dort steht). Schon 1 überschriebenes Byte kann dabei schon zu Abstürzen oder nicht auffindbaren Fehlern führen.
Natürlich gibt es noch andere Dinge, die man mit Pointern machen kann. Und nun kommen wir zu den Listen. Bäume sind dabei nur ein spezieller Typ von Liste (ok, eher umgekehrt, aber egal). Jedenfalls ist die Idee dahinter die gleiche.
Was Listen angeht, so fangen wir einfach mal mit den einfachsten an: Einfach Verkettete Listen.
Die Idee einer Liste ist sehr einfach. Es handelt sich um ein dynamische Struktur. Das heißt, die Größe ist nicht von festgelegt. Sie kann wachsen und schrumpfen. Ihr größter Vorteil ist, dass du somit immer nur den Speicher belegst, den du brauchst. Ein Nachteil ist es, dass du nicht weißt wie lang deine Liste ist. Somit kannst du auch nicht einfach auf das Xte Element zugreifen.
Ok, zu Listen findest du definitiv eine Menge (google, hier,...)
Also kommen wir zum einfachen Beispiel und schauen dann warum es funktioniert
Delphi-Quellcode:
type
PList = ^TList;
TList = record
Value : Integer;
Next : PList;
end;
var list : PList;
procedure Add(Element : PList);
var buffer : PList;
begin
// prüfen ob die Liste leer ist
if list = nil then
begin
// wenn sie leer ist, ist das eingefügte element das erste Element
list := Element;
end
else
begin
// sonst laufe bis zum letzten Element
buffer := list;
while buffer^.next <> nil do
begin
buffer := buffer^.next;
end;
// füge Element ans Ende ein
buffer.next := Element;
end;
end;
function RemoveLast : PList;
begin
// Wenn die Liste leer ist, wird nil zurück gegeben
if list = nil then
begin
result := nil
end;
else
begin
// Liste bis zum Ende durchgehen und letztes Element zurückgeben
while result^.next <> nil do
begin
result := result^.next;
end;
end;
end;
Ja, hier siehst du einfach mal wie eine solche Liste aussehen kann. TList speichert dabei Information (hier nur ein Integer) und einen Zeiger auf seinen Nachfolger. Zeigt der Nachfolger auf nil, so ist das gleichbedeutend damit, dass es keinen Nachfolger gibt. List speichert den Zeiger auf dein erstes Element. Möchtest du nun auf ein bestimmtes Element zugreifen, so musst du immer vom ersten Element aus zu dem Nachfolger. Dann zu dessen, ... bis du dort bist wo du hinmöchtest. Wichtig ist es, dass du prüfen musst ob es einen Nachfolger gibt.
Zeigt ein Pointer auf nil und du möchtest auf eine Eigenschaft von diesem Pointer zugreifen, so bekommst du eine AccessViolation.
Ja, dies ist natürlich eine sehr einfache Liste. Wie du siehst fügt man ein, indem man zum Ende der Liste läuft und dann den Zeiger auf den Nachfolger setzt. Das hier das letzte Element entfernt wird, ist nur meiner Faulheit zu verdanken.
Wichtig ist es bei Listen (oder auch Bäumen) den Zusammenhang der Elemente zu beachten. Sollte das erste Element entfernt werden, so solltest du beachten, dass das erste Element im Moment die gesamte Liste beinhaltet. Das zurückgegebene Element ist also ein Element, dass noch auf eine Liste zeigt. Würdest du aber einfach nur den Zeiger auf Next löschen, hättest du zwar das erste Element extrahiert, aber auch die Restliste gelöscht.
Also müsstest du das erste Element zwischen speichern, die Restliste also neue Liste speichern und dann den Zeiger des ersten Elements nil setzen.
Delphi-Quellcode:
function RemoveFirst : PList;
begin
// Wenn die Liste leer ist, wird nil zurück gegeben
if list = nil then
begin
result := nil
end;
else
begin
// zwischen speichern des ersten Elements
// welches aber noch auf die Restliste zeigt
result := list;
// alte Liste durch Restliste ersetzen
list := list^.next;
// löschen der Restliste vom ersten Element
result^.next := nil;
end;
end;
Ja, das nächste Thema sind dann doppelt-verkettete Listen und Bäume. Aber darauf werde ich heute nicht mehr eingehen. Hoffe mal es hilft dir soweit weiter. Zu den anderen Themen findest du wirklich überall ne ganze Menge. Wichtig ist, dass du das hier alles verstanden hast. Dann sind andere Listen und Bäume gar nicht viel schwerer. Du musst nur überlegen wo du dann was einfügst und wie du was entfernst.
Falls noch fragen sind, frag einfach!
Gruß Der Unwissende
Antwort
20. Nov 2005, 20:04
www.luckie-online.de > Delphi
Zitat
Linear-Darstellung
