![]() |
Verkettung ? Fragen für Info-Klausur
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; |
suche mal nach "verkette Liste" oder Pointer
Gruß Hansa |
Hallo und herzlich willkommen!
Zitat:
Code:
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.
new(a);
Mit
Code:
weist du also dem Speicher auf den a zeigt den Inhalt 'B' zu.
a^ := 'B';
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:
Code:
erst wieder freigeben.
dispose(a);
Ich hoffe das war jetzt ein bisschen verständlich :hi: Gruß, Sebastian |
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? |
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
Delphi-Quellcode:
zugreifen, der ^-Operator dereferenziert den Zeiger, man erhält also mit a^ den Speicherinhalt der an der Adresse a steht.
xyz^
Gruß, Sebastian |
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. |
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? |
Hi,
Zitat:
Gruß Hansa |
Zitat:
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 |
Hi,
Zitat:
Gruß Hansa |
Hi,
Zitat:
Gruß Hansa P.S.: Wann ist die Klausur ? |
Das mit dem "Wortspiel" hab ich jetzt verstanden und ich bin bei der erweiterten Version und brauche wohl wieder Hilfe :?
Also:
Delphi-Quellcode:
...das OOP hab ich ja eigentlich drauf, aber das verstehe ich nicht ?
Type pkette = ^knoten; // p steht für Pointer
knoten = RECORD wort : string; next : pKette; END; Wäre gut wenn mir jemand erklären könnte warum ein Typ pkette eine Eigenschaft, die auch pkette heißt, haben kann und vielleicht auch alles andere an dem Type. :lol: Danke nochmal für alles, was ihr mir bis jetzt erklärt habt ;) |
Hi,
aha, bist auch noch dran. Wie ich sehe läuft das auf meine Vermutung mit der verketteten Liste hinaus. Konnte fast nur so sein. Zitat:
1. Dein Quelltext war für diese Zwecke unleserlich, was nur bedeutet, daß wort und next in einer Zeile stehen. Kleine Ursache, aber große Wirkung. 2. vergiß OOP, das hat in diesem Zusammenhang nichts zu bedeuten. 3. next reicht den Zeiger an das nächste Element, welches wiederum vom Typ pKette ist und auch einen Inhalt hat. Mit Inhalt sind die Daten gemeint ("wort") ! Zusätzlich das nächste Element wieder ein next, nämlich das des nächsten Elementes. Tip : vergiss in diesem Zusammenhang alles, was Du über Delphi weißt. Das ist für jede Programmiersprache gültig. Ähm, wann ist nochmal die Klausur ? Gruß Hansa |
Die Klausur ist am 10.01.
Unser Info-Lehrer war so freundlich uns all die Sachen über die Ferien auf zu geben. Wir hatten nur 1 Stunde Unterricht darüber. Und in der haben wir das Beispiel ganz oben gemacht. Was ich hier poste ist vielleicht ein Achtel von allem, was wir noch machen müssen :P Meinst du das krieg ich noch hin, zumindest mit den verketteten Listen? Hier ist noch der restliche Code:
Delphi-Quellcode:
unit Unit1; //Zeiger_verkett1 (ohne Verkettungsprozedur)
// Aufgaben: 1) Erkläre den Datentyp "knoten" (siehe unten) // 2) Welche Ausgabe ist am Ende in Edit1.Text zu erwarten? // 3) Was versteht man bei der Reihenfolge der Daten unter LIFO ? // 4) Welche Vorteile bringt die dynamische Verkettung von Daten? interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) Edit1: TEdit; Button1: TButton; procedure Button1Click(Sender: TObject); private public end; var Form1: TForm1; Satz : string; implementation {$R *.DFM} //--------------------------------------------------- Type pkette = ^knoten; // p steht für Pointer knoten = RECORD wort : string; next : pKette; END; //--------------------------------------------------- Var kette: pKette; procedure TForm1.Button1Click(Sender: TObject); Var neu, hilf :pKette; begin kette:=nil; //Die Kette erhält einen Anfang satz:=''; New(neu); //Ein neues Kettenglied wird erzeugt neu.wort:='Das '; neu.next:=kette; kette:=neu; //...und angehängt New(neu); //...noch ein Kettenglied neu.wort:='wars '; neu.next:=kette; kette:=neu; New(neu); //...und noch eines neu.wort:='schon '; neu.next:=kette; kette:=neu; {---------------------------------------------} satz:=kette^.wort; // Die Kette wird ausgelesen {Wenn wir den Kettenzeiger nicht verändern und statt- dessen den Hilfzeiger, können wir den Anfang der Kette stets wiederfinden!} hilf:=kette^.next; // Zum nächsten... satz:=satz+hilf^.wort; hilf:=hilf^.next; // Zum nächsten... satz:=satz+hilf^.wort; edit1.text:=satz; // Ausgabe am Bildschirm end; end. |
Hi,
Zitat:
Code:
usw., wahrscheinlich guckt der nur nach ; := und so. Der ist viel zu faul, alles durchzugehen.
a^ := next; x := a;
Gruß Hansa P.S.: Auf keinen Fall würde ich wegen dieses Themas etwas anderes vernachlässigen. Vermute fast, daß eine Aufgabe mit Pointern überhaupt nicht kommt. |
Moin VeeJay,
Bestimmt werden diese Ausführungen noch ergänzt werden ;-) Anmerkung: Wenn das Beispiel von Deinem Lehrer stammt, dann hat er es aber inkonsequent geschrieben. Entweder er schreibt den dereferenzierungsoperator ^ immer mit oder nie, aber nicht mal so und mal so. Eigentlich müsste jede neu.xxxx neu^.xxxx geschrieben werden, oder statt kette^.xxxx und hilf^.xxxx kette.xxxx und hilf.xxxx. Aber dieser, unnötige, Wechsel kann doch recht verwirrend sein. Das Weglassen funktioniert aber auch nur, weil der Compiler clever genug ist zu wissen was gemeint ist, wenn man neu.wort schreibt (und das ^ weglässt) |
Hi VeeJay,
Christian Seehase hat eine ähnliche Vermutung, wie ich. Der hat nicht viel Ahnung. Liest Du seinen Kommentar, verstehst Du hoffentlich, warum ich frage, wann die Klausur ist ? Also : Pokerspieler (J/N) ? Falls ja : mit Antworten bluffen, falls Nein : vergiss es. Ansonsten kann ich Dir nicht mehr viele Tips geben. @Christian Seehase : @VeeJay : hier nicht weiterlesen, das verwirrt Dich nur. :!: Was ist mit doppelt-verketteten Listen oder zyklische, die ich schon angedeutet habe ? Gruß Hansa[/quote] |
Auch wenn das Posting schon ein Stück weiter oben steht...
Zitat:
Thomas |
Also bei aller Schwierigkeit,
ich denke, ich weiß jetzt schon eine Menge mehr über das Thema als ich noch vor 2 Tagen wusste. Ist echt cool, dass ihr mir das alles zeigt. Ich werde morgen noch mal alles zusammenfassen und gucken ob ich noch Probleme mit bestimmten Sachen habe, die unbedingt noch gelöst werden müssen. Ansonsten werde ich das Prinzip wohl auswendig lernen ohne es zu verstehen :roll: Vielleicht kann mir auch noch jemand den Zusammenhang zwischen a^ und @a erklären.... Dann bis morgen |
Moin VeeJay,
mit Zusammenhang wird's schwierig ;-) Ich hab' Dir hier mal ein "wildes" Beispiel zusammengestellt: (um das try/finally brauchst Du Dich erstmal nicht zu kümmern, auch wenn's wichtig ist)
Delphi-Quellcode:
War das soweit verständlich mit ^ und @ ?
var
p : PChar; // Pointer auf Char c : Char; // Ein Character begin p := AllocMem(1); // Speicher reservieren und Adresse dieses Speichers nach p try p^ := 'a'; // Jetzt an diese Stelle ein Zeichen schreiben. c := p^; // und jetzt dieses Zeichen an die Charactervariable übergeben ShowMessage(c); // Anzeigen, dass es auch geklappt hat finally FreeMem(p,1); // Nun kann der Speicher wieder freigegeben werden end; p := @c; // Jetzt die Adresse der Charactervariablen nach p ShowMessage(p^); // Und sich das a anzeigen lassen c := 'b'; // Jetzt ein anderes Zeichen in der Charactervariablen speichern ShowMessage(p^); // aber wieder anzeigen lassen, auf was p zeigt... siehe da es erscheint ein b end; |
Zitat:
Gruß Hansa |
Hallo,
mit deinem Wissen über Pointer, kannst du nun auch einfache verkette Listen erstellen. Wichtig für Ketten sind die While Schleifen, die du bei fast allen Aktionen brauchst (z.B beim Einfügen, Löschen und durchsuchen der Kette)
Delphi-Quellcode:
Einfügen in die Liste geht dann z.B so:
Type
pElementZeiger := ^tElement; tElement := object next :tElementZeiger; inhalt: integer; end; Var kopf : pElementZeiger; //Globale Variable die immer auf das erste Element der Liste zeigt.
Delphi-Quellcode:
Das Ausgeben der Liste ist genauso einfach:
Procedure InsertNewElement (content : integer);
Var hilf, newelement : pElementZeiger; Begin hilf := kopf^.next; while (hilf<>nil) do hilf := hilf^.next; //mit der Schleife kommt man ans Ende der Liste, wo dann das neue Element eingefügt wird new(newelement); newelement^.inhalt := content; newelement.^next := nil; hilf^.next := newelement; end;
Delphi-Quellcode:
Suchen funktioniert ebenfalls mit der Schleife:
Procedure ShowList;
Var hilf :pElementZeiger; Begin hilf := kopf; while (hilf^.next <> nil) do begin memo1.lines.Add (inttostr(hilf^.inhalt)); hilf := hilf^.next; end; end;
Delphi-Quellcode:
Das löschen eines Elementes in der Liste ist schon komplizierter, da man darauf achten muss, dass die Zeiger später wieder auf die richtigen Elemente Zeigen und die Kette nicht auseinander bricht.
Procedure FindElement (content : integer);
Var hilf : pElementZeiger; Begin hilf := kopf; while (hilf <> nil) do begin if hilf^.inhalt = content then showmessage('Element gefunden: ' + inttostr(hilf^.inhalt)); hilf := hilf^.next; end; end;
Delphi-Quellcode:
So, ich denke das ist schonmal ein kleiner Überblick wie man mit einfach verketten Listen arbeitet. Doppelt verkette Listen haben nicht nur einen Zeiger auf das Nachfolge Elemnet, sondern auch einen Zeiger auf ihren Vorgänger. Dadurch werde Opperationen wie z.B das Löschen einfacher.
Procedure LoescheElement (content : integer);
Var hilf1, hilf2 : pelementZeiger; Begin Hilf1 := Kopf; If Kopf^.inhalt = content then begin Kopf := Kopf^.next; Dispose (hilf1); end else Repeat hilf2 := hilf1; hilf1 := hilf1^.next; Until (Hilf1 = nil) or (Hilf1^.inhalt = content); If Hilf1 <> nil then begin Hilf2^.next := Hilf1^.next; Dispose (Hilf1); end; end; Die Quelltexte können Fehler beinhalten, da ich sie eben so aus dem Kopf aufgeschrieben habe. Ist schon wieder etwas her wo ich mich mit Listen beschäftigen musste. Mfg Salomon |
Re: Verkettung ? Fragen für Info-Klausur
Ich bin auch gerade dabei mich mit Listen zu beschäftigen. :)
Ich habe versucht das wie folgt umzusetzen, orientiert an dem Code über mir:
Delphi-Quellcode:
Nur wenn ich eine Zahl zu der Liste hinzufügen möchte, stürzt er Mit EAccessViolation ab. :(. An der Adresse 00000004 kann er nicht schreiben steht dann zusätzlich da.
PZahl = ^TZahl;
TZahl = record Item : Integer; Next : PZahl; end; type TintList = class Zahl : TZahl; PFirst : PZahl; constructor Create; procedure Add(Int: Integer); //procedure Delete(Index: Integer); //function Get(index: Integer): Integer; end; ... constructor TintList.Create; begin inherited Create; Zahl.Item := 0; Zahl.Next := nil; PFirst := @Zahl; end; ... procedure TintList.Add(int: Integer); var Digit: PZahl; Silk : PZahl; begin //Silk := PFirst^.next; <-- IST FALSCH!!!! Silk := PFirst; If Silk <> nil Then while (Silk^.Next <> nil) do Silk := Silk^.next; New(Digit); Digit^.Item := int; Digit^.Next := nil; Silk^.Next := Digit; /// <--- Hier WAR er abgestürzt jetz gehts wieder... end; Aber eigentlich sollte die Routine einfach das letzte Element finden, was dann ja Silk sein soll. Und das darf unmöglich auf 00000004 zeigen. :shock: Wie kann das denn sein. Ich blic da nich durch :cry: EDIT: Habs rausgefunden. Ich habe es oben korrigiert und die falsche Zeile auskommentiert. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 11:39 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz