Schnellste und einfachste Methode für verkettete Liste

[Andreas L.]

Abend,
ich hab eine Liste die beliebig viele Elemente enthalten kann. Die Elemente sind wiederum Listen und können ebenfalls beliebig viele Elemente enthalten.

Beispiel:

Code:

Element (root)
|-Element
| |-Element
| |-Element
|   |-Element
|     |-Element
|-Element     
etc.

Wie gehe ich die Liste am besten durch? Ich muss die Liste speichern und laden sowie in einer TreeView anzeigen können. Ich denke Rekursion ist die Lösung, kenne mich damit aber nicht aus. Irgendwelche Ideen?

[Vjay]

Im grunde beantwortest du es dir selbst. -> Informiere dich über Rekursion.

Die TTreeItems eines TTreeViews haben eine Data - Eigenschaft, falls den den Treeview ständig parat hast, kannst du auch alle Items in ihm "belassen" und nur mit dem TreeView arbeiten.

[jfheins]

Wenn du so einen Baum speichern willst, solltest du so eine Art Inhaltsverzeichnis anlegen ;)

Also: Jeder Knoten hat einen Namen, Daten und X Kindknoten.

Also machst du sowas:

Code:

"Knoten1"$Adresse,2;"UnterknotenVon1Nr1"$Adresse,1;"UnterknotenVon11"$Adresse,0;"Unterknoten2"$Adresse,0;"Knoten2"$adresse,0

Bei diesem Format speicherst du also den Namen, die Adresse (in der Datei) und die Anzahl der Kinder. Anhand dieser Daten kannst du das ganze wieder zusammenfriemeln.

Oder du machst die Datei direkt Rekursiv, so wie das hier. Das ist ein Ausschnitt aus einer Terminverwaltung, die ich mal in Java geschrieben habe. Das ist kein Programmcode, sondern die gespeicherte "Datenbank". Das ganze wurde dann von einer Klasse eingelesen und rekursiv wieder in eine Baumstruktur umgewandelt ;)

Code:

new TYearly{
   Title="My Birthday";
   Priority=30;
   DaysInAdvance=1;
   Description="My Birthday ...";
   StartDate=new TDate{
      Year=2007;
      Month=3;
      Day=16;
      Time=null;
   };

   EndDate=new TDate{
      Year=2026;
      Month=3;
      Day=16;
      Time=null;
   };

   Day=12;
   Month=3;
};

new TAppointment{
   Title="Meeting with Dr. Suthers";
   Priority=15;
   DaysInAdvance=4;
   Description="This is a sample appointment.";
   Date=new TDate{
      Year=2007;
      Month=3;
      Day=24;
      Time=null;
   };

};

new TAppointment{
   Title="English Essay ";";;"";
   Priority=12;
   DaysInAdvance=7;
   Description="This is the english essay about "The Outsider"";
   Date=new TDate{
      Year=2007;
      Month=3;
      Day=16;
      Time=null;
   };

};

new TWeekly{
   Title="Guitar lesson";
   Priority=10;
   DaysInAdvance=3;
   Description="This is my Weekly guitar lesson, every Friday at 10:15";
   StartDate=new TDate{
      Year=2007;
      Month=1;
      Day=1;
      Time=null;
   };

   EndDate=new TDate{
      Year=2007;
      Month=5;
      Day=23;
      Time=null;
   };

   DayOfWeek=4;
   Time=new TTime{
      Hour=16;
      Minute=15;
   };

};

new TWeekly{
   Title="Sport Session";
   Priority=8;
   DaysInAdvance=3;
   Description="";
   StartDate=new TDate{
      Year=2007;
      Month=1;
      Day=2;
      Time=null;
   };

   EndDate=new TDate{
      Year=2007;
      Month=4;
      Day=20;
      Time=null;
   };

   DayOfWeek=1;
   Time=null;
};

new TWeekly{
   Title="Sport Session";
   Priority=8;
   DaysInAdvance=5;
   Description="";
   StartDate=new TDate{
      Year=2007;
      Month=1;
      Day=4;
      Time=null;
   };

   EndDate=new TDate{
      Year=2007;
      Month=4;
      Day=20;
      Time=null;
   };

   DayOfWeek=5;
   Time=null;
};

new TAppointment{
   Title="Economics past paper";
   Priority=7;
   DaysInAdvance=8;
   Description="This is a back\nentry.";
   Date=new TDate{
      Year=2007;
      Month=3;
      Day=25;
      Time=null;
   };

}

P.S. da wo Time=null steht, hätte man natürlich noch ein Time-Objekt einfügen können - theoretisch ist die Rekursionstiefe nicht begrenzt ^^ ;)

[alzaimar]

Zum Speichern eignet sich z.B, XML oder JSON, das sind standardisierte Formate und Klassen gibts schon dafür.
Als Datenstruktur eignet sich z.B. soetwas:

Delphi-Quellcode:

Type
  TMyTreeNode = Class
  Public
    Property Father : TMyTreeNode; // Zeiger auf den übergeordneten Knoten oder NIL, wenn der Knoten schon der oberste ist.
    Property FirstChild : TMyTreeNode; // Zeiger auf den ersten untergeordneten Knoten oder NIL, wenn es Keine gibt.
    Property Next : TMyTreeNode; // Zeiger auf den nächsten Knoten mit gleichem Father, oder NIL, wenn der Knoten der letzte in der Liste ist.
    Property Data : TObject; // Daten des Knotens
  End;

In Datenbanken werden die Knoten durchnumeriert und zum Speichern speichert man eben nur die ID's der Väter, Kinder und Geschwister. Beim Einlesen muss man dann die Verweise wieder zusammensuchen, das geht aber mit einer Lookupliste sehr schnell. Eine weitere Möglichkeit, die Daten schnell einzulesen ist, sie geeignet zu sortieren.

Eine Hierarchie kann man auch so abspeichern, indem man die Knoten mit 'Namen' versieht. Dabei gilt folgende Regel:
Name (Knoten) = Name (Knoten.Father)+'/'+Knoten.ID

Dann schmeisst man diese Namen in eine Liste und sortiert sie alphabetisch und speichert sie ab.
Beim Einlesen kann man dann ohne Suchen die Knoten direkt verlinken.

Hoffe, das hilft.

[Andreas L.]

Zitat:

Zitat von alzaimar

Eine Hierarchie kann man auch so abspeichern, indem man die Knoten mit 'Namen' versieht. Dabei gilt folgende Regel:
Name (Knoten) = Name (Knoten.Father)+'/'+Knoten.ID

Dann schmeisst man diese Namen in eine Liste und sortiert sie alphabetisch und speichert sie ab.
Beim Einlesen kann man dann ohne Suchen die Knoten direkt verlinken.

Hoffe, das hilft.

Daran dachte ich auch schon. Werde es wohl so machen. Habe inzwischen auch ein wenig experimentiert und dachte mir das es mit einem MemoryStream am einfachsten geht.

Delphi-Quellcode:

mem := Tmemorystream.create;
mem.writecomponent(meinekompo);
mem.savetofile('bla.dat');
mem.free;

Geht aber nicht, die Datei ist 23 Bytes groß und beim laden bleibt die Kompo leer (natürlich habe ich die Kompo vor dem Speichern mit 10000 Elementen gefüllt). Liegt wohl daran das WriteComponent nur Components[] und ComponentCount zum auffinden von Objekten verwendet. In meiner Klasse habe ich die Elemente im private Teil als FBla deklariert und im public die passende property ala

Delphi-Quellcode:

property Bla[Index: Integer]:Tbla read getBla write Setbla;

Aber das bringt mich auch nicht um die Rekursion rum, ich muss die Daten schließlich in einer TreeView anzeigen und einzelne, ausgewählte Elemente übers Web transportieren.

Also werde ich es wohl so machen wie alzaimer vorgeschlagen hat: Einfach und effektiv!

Danke an alle die geantwortet haben.

[Andreas L.]

Ok, ich habe jetzt alle Ordner in einer ObjectList. Jeder Ordner hat die Eigenschaft Folder (Integer) welche den Index des übergeordneten Ordners angibt. Jetzt muss ich das ganze so zusammenfrickeln das es in einer TreeView korrekt dargestellt wird. Aber ich scheitere... Ich bräuchte einen Denkanstoß! Irgendwelche Ideen?

[jfheins]

Ich kenne mich jetzt grad nicht mit dem Treeview aus (lange nicht mehr VCL programmiert, in der Uni brauchen wir C ...) aber:

Du musst den Baum von oben nach unten aufbauen. Du nimmst dir also ein Element herais, und hangelst dich anhand der ParentID (oder was du da hast) bis zum obersten Element. Dann suchst du alle, die dieses Element als Parent angeben und hängst sie dran. Dann gehst du rekursiv vor. Dann hast du den gesamten Baum wieder beisammen.
Um eine effiziente Suche hinzubekommen, könntest du die Menge (beim speichern) sortieren, und dann eine BinarySearch drüberlaufen lassen, sonst suchst du dich bei vielen Elementen ja zu tode ;)