mortus - Mo 16.12.02 20:50
Titel: neues element in doppelverkettete liste einfuegen (sortiert)

---

in meinem programm muessen staendig neue elemente erzeugt und an der richtigen stelle in eine sortierte liste eingefuegt werden. momentan benutze ich lineares einsortieren. binaeres einsortieren erscheint mir zu unpraktisch in diesem fall. welche moeglichkeiten gibt es noch? dabei sollten keine hilfsarrays verwendet werden.
danke im voraus

Aya - Di 17.12.02 07:44

---

Hi,

ich nehm mal an das du mit VCL arbeitest, da wäre es die einfachste und wohl auch schnellste methode wenn du einfach ne TStringList benutzt.

da kannst du all deine einträge immer reinpacken, und mit TStringList.Sort einfach Sortieren lassen :)

Au'revoir,
Aya

mortus - Di 17.12.02 17:36

---

danke fuer den ratschlag. ich arbeite in diesem fall aber wirklich ohne vcl. (sonst haette ich TList verwendet). so moechte ich bei meiner verketteten liste bleiben. ein listenelement enthaelt ausserdem nicht nur einen string sondern mehrere strings+integer.

AndyB - Di 17.12.02 19:04

---

Wenn du mit verketteten Listen arbeitest, dann ist das lineares einsortieren das einfachst zu programmierenste und auch m.E. das schnellste. Ein binäres Einsortieren verliert seine Geschwindigkeit, da man bei jedem halbieren erst alle Elemente bis zur Mitte durchlaufen muss, was man beim linearen Einsortieren sowieso machen muss, aber eben nur 1x.

Und zur Classes Unit. Diese gehört nicht zur VCL sondern RTL (RunTime Library), wie auch die Unit SysUtils.

Klabautermann - Mi 18.12.02 00:55

---

Hallo,

bei einer sortierten doppelt verketteten Liste währe es siche sinvoll, den "Head" nicht auf das erste Element sondern auf das mittlere. Danach musst du im schlimmsten Fall nur noch die hälfte der Elemente durchsuchen. Du musst beim suchen nur entscheiden in welche Richtung du läufst.
Schwieriger wird es, den Haed auf dem richtigen Element zu halten. Du must ihn nach jedem Einfügen neu positionieren bzw. die Position überprüfen. Wenn du keine Hilfsvariablen verwenden willst (ElementeLinks, Elemente Rechts) musst du in den Fällen im grunde die Liste ablaufen.

Gruß
Klabautermann

Hagbard Celine - Fr 20.12.02 17:39

---

Wenn Du es Dir einfach machen willst dann verwende tObjectList und deren sort Funktion.

Du musst vorher eine funktion definieren die DU dann als Parameter an die sort Funktion übergiebst! In der Funktion musst Du nur den ergleich von deinen Eigenschaften vornehmen und entsprechend den Rückgabewert definieren!

Welches Sortierverfahren hier verwendet wird kann ich dir nicht sagen, aber die werden schon ein sinnvolles gewählt haben!