verkettete Liste sortieren(DRINGEND)
Daniel Alder
Hallo Programmierer,
Ich suche DRINGEND nach einer Sortierroutine, die eine verkettete Liste
auf dem Heap sortiert. Diese sieht bei mir folgendermassen aus:
Type
Daten = Record
Name : String[35]
Adresse : String[30]
End;
PListe = ^TListe;
TListe = Record
Daten : Data;
Next : PListe; { nächster Listeneintrag }
End;
Var Start : PListe; { erster Listeneintrag }
Dabei sollte die Liste nach Name sortiert werden. Es muss übrigens nicht
sonderlich schnell werden - es sind nur etwa 40 Datensätze
Daniel Alder
--
Daniel Alder - 15-Jähriger Hobby-(Pascal-)programmierer von Ramsen(CH)
Ich suche dauernd nach Programmieranregungen...
Hab' ne neue E-Müll-Adresse: daniel...@gmx.de
Wer seit einer Woche auf meine Antwort wartet, sollte mich nochmals
daran erinnern. Bei mir kann schon mal eine Mail untergehen...
Marcel Schmidt
die Lösung:
Type
TDaten = Record
Name : String[35];
Adresse : String[30];
End;
PListe = ^TListe;
TListe = Record
Daten : TDaten;
Next : PListe; { nächster Listeneintrag }
End;
procedure SortiereListe(var Anfang:pListe);
{ sortiert eine lineare Liste, wichtig ist, daß der Listenanfang mit var
übergeben wird,
da sich der Listenanfang verschieben kann. Mit dieser Prozedur ist es u.a.
möglich,
Teillisten(z. B. ab dem 5. Element...) zu sortieren. }
Var Zeiger1,
Zeiger2,
Zeiger3,
Zeiger4:pListe;
begin
zeiger1:=Anfang;
Zeiger2:=Anfang^.Next;
while Zeiger2<>nil do
begin
if Zeiger2^.Daten.Name<=Anfang^.Daten.Name then
begin { Element ist bisher kleinstes Element}
zeiger3:=Anfang;
Zeiger1^.Next:=Zeiger2^.Next;
Anfang:=Zeiger2;
Anfang^.Next:=Zeiger3;
Zeiger2:=Zeiger1^.Next;
end
else
if Zeiger2^.Daten.Name<Zeiger1^.Daten.Name then
begin { dieses Element muß in den vorderen Teil der Liste
eingefügt werden }
Zeiger3:=Anfang;
while (Zeiger3^.Daten.Name<Zeiger2^.Daten.Name) do
begin
Zeiger4:=Zeiger3;
Zeiger3:=Zeiger3^.Next;
end;
Zeiger1^.Next:=Zeiger2^.Next;
Zeiger2^.Next:=Zeiger3;
Zeiger4^.Next:=Zeiger2;
Zeiger2:=Zeiger1^.Next;
end
else
begin
{ nächstes Element überprüfen }
Zeiger1:=Zeiger2;
Zeiger2:=Zeiger2^.Next;
end;
end;
end;
Daniel Alder schrieb in Nachricht <34FED584...@gmx.de>...
Rolf Witt
daniel...@gmx.de meinte am 05.03.98
zum Thema "verkettete Liste sortieren(DRINGEND)":
> Ich suche DRINGEND nach einer Sortierroutine, die eine verkettete Liste
> auf dem Heap sortiert. Diese sieht bei mir folgendermassen aus:
Hast Du schon mal erwogen, Dir ein Grundlagenbuch zuzulegen?
Etwa "Algorithmen und Datenstrukturen" von N.Wirth dort sind solche
Probleme ausführlichst behandelt und es dürfte auch in den meisten
Büchereien zur Ausleihe bereitstehen.
cu
Rowi
Sensor - Stefan Sänger
Pascal-Version, Addison Wesley-Verlag ...
Grundsaetzlich wuerde ich eine solche Liste gleich sortiert einketten,
also in etwa so:
Type TDaten = Record
Kriterium: XXX; {muss halt vergleichbar sein ...}
...
end;
PEintrag = ^TEintrag;
TEintrag = Record
Daten: TDaten;
PNach: PEintrag;
end;
Var Anfang: PEintrag;
Procedure EintragEinfuegen(NDaten:TDaten);
Var Lauf, Neu: PEintrag;
Begin
Lauf:=Anfang;
New(Neu);
New^.Daten:=NDaten;
While (Lauf^.Daten.Kriterium < NDaten.Kriterium) and
(Lauf.PNach<>nil) do
Lauf:=Lauf^.PNach;
Neu^.PNach:=Lauf^.PNach;
Lauf^.PNach:=Neu;
End;
bye, Sensor ....
--
==============================================================================
Stefan Sänger
mail: sen...@rz.tu-ilmenau.de
phone: 0177-3221656
Marcel Schmidt
Ich habe die aufgeführte Prozedur noch einmal als Delphi-Komponente
implementiert, allerdings in der Weise, daß Listen mit beliebigen Inhalt
sortiert werden können. Dabei werden benutzerdefinierte Prozeduren(Events)
für Vergleich und Ermittlung von Vorgänger und Nachfolger aufgerufen.
Die Komponente ist in Bearbeitung und kann per email angefordert werden. Sie
wurde under Delpi3 Prof. erstellt, sollte aber mit allen Delphi-Versionen
laufen.
Ich habe vor, weiter Sortier-Algorithmen einzubauen.
Die bis jetzt vorliegende Komponente habe ich auf Zeitverhalten getestet.
Dabei wurde folgendes Ergebnis erreicht:
Das Sortieren von 10000 Elementen(Listeneinträge Sortierungs nach einem
Integer-Wert) dauert ca. 12 sec. Die Zeit verdoppelt sich, wenn sich die
Anzahl der Listeneinträge verdoppelt. Desweiteren ist die Zeit abhängig von
der Effizienz der benutzerdefinierten Vergleichsprozeduren, sowie von den in
der Liste abgelegten Elementen ab(vorliegende Sortierung).
Marcel Schmidt
marc...@theoffice.net
Marcel Schmidt schrieb in Nachricht <6dn3go$ijp$1...@news.nacamar.de>...
>die Lösung:
>procedure SortiereListe(var Anfang:pListe);
Sensor - Stefan Sänger
Bei groesseren Datenmengen empfiehlt sich wohl eher der Einsatz
eines binaeren Suchbaumes ...
Joerg Wirtgen
Moin Daniel Alder!
Am Thu, 05 Mar 1998 17:40:36 +0100 schriebst Du:
> Ich suche DRINGEND nach einer Sortierroutine, die eine verkettete Liste
> auf dem Heap sortiert. Diese sieht bei mir folgendermassen aus:
Durchsuche die Algorithmenbücher mal nach Mergesort und seinen
Weiterentwicklungen. Das ist für sequentielle Dateien geeignet und sollte
daher auch für sequentielle Listen funktionieren. Da gibt es bestimmt was
passendes.
Bis dann . . . Jörg
Torsten Landmann
> > Durchsuche die Algorithmenbücher mal nach Mergesort und seinen
> > Weiterentwicklungen. Das ist für sequentielle Dateien geeignet und
sollte
> > daher auch für sequentielle Listen funktionieren.
> sortierte Teile derart zusammengefügt werden, daß sie dannach auch noch
> sortiert sind.
Der Beitrag war ja wohl nichts.
Natürlich werden die beiden Hälften vorher rekursiv auch mit Mergesort
sortiert, bevor sie zusammengesetzt werden.
> Hat man nur eine simple unsortierte Liste und will auch keine Struktur
> darüber packen, bleibt nur Bubblesort. Man kann aber neue Datensätze
gleich
> an die richtige Stelle einhängen.
Also Sortieren durch geordnetes Einfügen.
Kann man übrigens auch einfach als Sortieralgorithmus nehmen. Da muß man
aber den ganzen Scheiß noch einmal im Speicher ablegen.
>
> Btw, bei solch kleinen Datenmengen rentieren sich keine weitreichenden
> Überlegungen, die Suche noch effizienter zu gestalten. Ansonsten bleiben
> immer noch Suchbäume oder dergleichen.
>
> --
> kiek mol wedder in
> __ _
> \ \_ public key via EB/RRQ
t...@experteam.de
In article <01bd5529$73e8d220$61f0a8c1@tlandmann>,
"Torsten Landmann" <tlan...@metronet.de> wrote:
> Also Sortieren durch geordnetes Einfügen.
> Kann man übrigens auch einfach als Sortieralgorithmus nehmen. Da muß man
> aber den ganzen Scheiß noch einmal im Speicher ablegen.
Nicht unbedingt. Was haelst Du von einer verketteten Liste die nichts anderes
als Zeiger zu Deinen Daten enthaelt. Wenn Du eine anders sortierte Liste
brauchst, musst Du lediglich Platz fuer neue Zeiger schaffen, die dann
anderrs sortiert in der Liste landen, die Daten selbst bleiben unangetastet
und auch nur "einfach" vorhanden. Ein recht gutes Beispiel ist das
TCollection Listenobjekt aus der Unit OBJECTS.PAS (ab TP6).
Gruss, Tom.
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/ Now offering spam-free web-based newsreading