AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Doppelt verkettete Liste sortieren

Ein Thema von Mr.P-Funk · begonnen am 21. Feb 2005 · letzter Beitrag vom 14. Sep 2010
Antwort Antwort
Seite 1 von 3  1 23      
Mr.P-Funk

Registriert seit: 9. Dez 2003
11 Beiträge
 
Delphi 5 Standard
 
#1

Doppelt verkettete Liste sortieren

  Alt 21. Feb 2005, 23:20
Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.


Ein paar Lösungen die mir eigefallen sind:

1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.

Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.


2. Einen Record mit 2 Feldern hinzufügen.
Delphi-Quellcode:
type
  TDAddress = record
  Value : string;
  PADR : Pointer;
  end;
Ein DynArray von TDAddress anlegen. Dann in einer Schleife die Liste durchlaufen und den Wert nachdem sortiert werden soll in Value schreiben. In PADR kommt dann die Adresse von dem Element.
Das Array sortieren und anschließend die Liste anpassen.
Liste in das Array schreiben:
Delphi-Quellcode:

var
    AoTDA : array of TDAddress;
    Runner: Pzeiger;
    i : integer;
begin
  Runner := Root;
  i := 0;
  while Runner <> NIL do
  begin
     inc(i);
     Setlength(AoTDA, Length(AoTDA)+1);
     AoTDA[i-1].PADR := Pointer(Runner);
     AoTDA[i-1].Value := Runner^.IRGENDWAS; //Irgendwas ist der Wert nachdem sortiert werden soll
     Runner := Runner^.next;
  end;
end;
Liste anpassen:
Delphi-Quellcode:
var i : integer;
    Runner : PZeiger;
begin
   Root := AoTDA[low(AoTDA)].PADR;
   Root^.next := AoTDA[low(AoTDA)+1].PADR;
   Root^.prev := NIL;

   FOR i := low(AoTDA)+1 TO high(AoTDA)-1 DO begin
      Runner := AoTDA[i].PADR;
      Runner^.prev := AoTDA[i-1].PADR;
      Runner^.next := AoTDA[i+1].PADR;
   end;

   Runner := AoTDA[high(AoTDA)].PADR;
   Runner^.next := NIL;
   Runner^.prev := AoTDA[high(AoTDA)-1].PADR;
end;
Die 2 Variante benutze ich im moment, allerdings habe ich gehört das man das so nicht machen darf.
Hatte jemand mit sowas schonmal Erfahrungen gemacht? Gibt es eine Muster-, Standartlösung?
  Mit Zitat antworten Zitat
DelphiDeveloper

Registriert seit: 9. Apr 2003
Ort: Köln
256 Beiträge
 
Delphi XE2 Enterprise
 
#2

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 02:44
Ich sehe an deinem Code noch nicht die doppelverkettung aber mit PREV und NEXT kann ich schon erahnen wie
es gemacht ist.

Schau dir in Delphi doch mal die TList an, hier ein kleines Beispiel wie man darin records/objekte einhaengen kann:
Die Sortiertung ist dann ein Kinderspiel für dich:

Hier die Sourceb die ich gerade auf die schnelle zusammengeklickt habe:

Delphi-Quellcode:
{-----------------------------------------------------------------------------
Author:    DelphiDeveloper  05.02.22
Purpose:  Sort with TList
-----------------------------------------------------------------------------}

unit Unit1;
interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, ExtCtrls;

type

  TDAddress = class
    SValue: string;
    IValue: integer;
    PADR: Pointer;
  end;

  TForm1 = class(TForm)
    BtnCreateTheList: TButton;
    BtnShowList: TButton;
    ListBox1: TListBox;
    RGrpSort: TRadioGroup;
    BtnSort: TButton;
    procedure BtnCreateTheListClick(Sender: TObject);
    procedure BtnShowListClick(Sender: TObject);
    procedure BtnSortClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
    myList: Tlist;
    procedure ClearList;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.BtnCreateTheListClick(Sender: TObject);
var aAdrObj: TDAddress;
  I: integer;
begin
  myList := TList.create;
  // fuelle Liste mit beispielwerten
  for i := 1 to 5 do
  begin
    aAdrObj := TDAddress.Create;
    aAdrObj.SValue := chr(random(20) + 65);
    aAdrObj.IValue := random(10);
    MyList.Add(aAdrObj);
  end;
end;

procedure TForm1.ClearList;
var I: integer;
begin
   // erst die Objekte freigeben
  if assigned(MyList) then
  begin
    for i := 0 to myList.Count - 1 do
      if MyList.Items[i] <> nil then
        TDAddress(myList.Items[i]).Free;
    //und jetzt die Liste
    MyList.Clear;
  end;
end;

procedure TForm1.BtnShowListClick(Sender: TObject);
var i: integer;
begin
  // nur um anzuzeigen was in der Liste steht
  ListBox1.Clear;
  for i := 0 to myList.Count - 1 do
  begin
    ListBox1.Items.Add(Inttostr(TDAddress(myList[i]).IValue) +
      ' ' + TDAddress(myList[i]).SValue);
  end;
end;

function SortierenString(item1,item2:pointer):integer;
begin
  // intern wird quicksort algo verwendet siehe OH
  // sortierung von strings
  result:=CompareText( TDAddress(Item1).SValue, (TDAddress(Item2).SValue));
end;

function SortierenInteger(item1,item2:pointer):integer;
begin
   // intern wird quicksort algo verwendet siehe OH
  // sortierung von integerwerten
  result:=( TDAddress(Item1).iValue - (TDAddress(Item2).iValue));
end;

procedure TForm1.BtnSortClick(Sender: TObject);
begin
   case RGrpSort.ItemIndex of
     0: MyList.Sort( SortierenInteger);
     1: MyList.Sort( SortierenString);
   end;
   // neu anzeigen
   BtnShowList.OnClick(sender);
end;

end.
  Mit Zitat antworten Zitat
Chewie

Registriert seit: 10. Jun 2002
Ort: Deidesheim
2.886 Beiträge
 
Turbo Delphi für Win32
 
#3

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 12:11
Zum wasweißichwievielten Mal:
TList ist keine(!!!) verkettete Liste, sondern ein Array!
Martin Leim
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
  Mit Zitat antworten Zitat
IngoD7

Registriert seit: 17. Feb 2004
464 Beiträge
 
Delphi 7 Enterprise
 
#4

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 12:43
Zitat von Chewie:
Zum wasweißichwievielten Mal:
TList ist keine(!!!) verkettete Liste, sondern ein Array!
Stimmt. Wo wurde denn was anderes behauptet?
  Mit Zitat antworten Zitat
Chewie

Registriert seit: 10. Jun 2002
Ort: Deidesheim
2.886 Beiträge
 
Turbo Delphi für Win32
 
#5

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 13:17
Naja, das Thema sind doppelt verkettete Listen, und der Vorredner brachte heri TList ins Spiel.
Martin Leim
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
  Mit Zitat antworten Zitat
IngoD7

Registriert seit: 17. Feb 2004
464 Beiträge
 
Delphi 7 Enterprise
 
#6

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 13:44
Zitat von Chewie:
und der Vorredner brachte heri TList ins Spiel.
Ja schon, aber (wenn ich es richtig verstanden habe) als Alternative zur verketteten Liste.
  Mit Zitat antworten Zitat
Chewie

Registriert seit: 10. Jun 2002
Ort: Deidesheim
2.886 Beiträge
 
Turbo Delphi für Win32
 
#7

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 13:46
Hm, wie auch immer. Man kanns auf jeden Fall nie oft genug sagen
Martin Leim
Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
  Mit Zitat antworten Zitat
Niko

Registriert seit: 23. Jun 2003
416 Beiträge
 
Delphi 2006 Professional
 
#8

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 14:04
Hi

Zitat von Mr.P-Funk:
Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.
Genau deshalb ist Quicksort für eine verkettete Liste nicht besonders gut geeignet. Das schnellste Sortierverfahren für Listen dürfte Mergesort sein (benötigt keinen direkten Zugriff auf die Elemente).
"Electricity is actually made up of extremely tiny particles called electrons, that you cannot see with the naked eye unless you have been drinking." (Dave Barry)
  Mit Zitat antworten Zitat
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#9

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 14:11
Zitat von Mr.P-Funk:
Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?

Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.


Ein paar Lösungen die mir eigefallen sind:

1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.

Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.


2. Einen Record mit 2 Feldern hinzufügen.
Mit einem zusätzlichen Speicheraufwand von 1 Zeiger pro Element kann man ein indirektes Sortieren durchführen:
Delphi-Quellcode:
type
   PSortItem = ^TSortItem;
   // die Grundstruktur deiner doppelt verketteten Liste
   TSortItem = Record
      data:string;
      Prev : PSortItem;
      Next : PSortItem;
   end;

var
   // Hilfsarray zum Sortieren
   SortArray : array of PSortItem;
Ich gehe jetzt davon aus, dass deine doppelt verkettete Liste komplett aufgebaut ist.
Der nächste Schritt ist nun das Hilfsarray zu dimensionieren.
Dazu wird die Anzahl der Elemente benötigt (entweder schon bekannt oder man muss die Liste durchzählen):
   SetLength(SortArray, AnzahlElemente); Jetzt wird das Array bestückt:
Delphi-Quellcode:
runner := FirstElement
for i:=0 to AnzahlElemente-1 do
begin
   SortArray[i] := runner;
   runner := runner.Next;
end;
Jetzt ist der double-linked List ein Array übergestülpt.
Beim Sortieren wird nun über das Array SortArray gearbeitet und innerhalb des Arrays werden Zeiger vertauscht.
Die Verkettungen innerhalb der double linked List bleiben völlig unberücksichtigt.
Nach dem Sortieren enhält das Array die Zeiger auf die Elemente in sortierter Form.
Jetzt werden alle Verkettungen der double-linked List quasi weggeschmissen und mit Hilfe
des SortArray neu aufgebaut:
Delphi-Quellcode:
Head := SortArray[0]; // Kopf der Liste
// gesonderte Behandlung für Anfangselement
SortArray[0]^.Prev := nil;
SortArray[0]^.Next := SortArray[1];
for i := 1 to AnzahlElemente-2 do
begin
   SortArray[i]^.Prev := SortArray[i-1];
   SortArray[i]^.Next := SortArray[i+1];
end;
// gesonderte Behandlung für letztes element
SortArray[AnzahlElemente-1]^.Prev := SortArray[AnzahlElemente-2];
SortArray[AnzahlElemente-1]^.Next := nil;
Tail := SortArray[AnzahlElemente-1];
Andreas
  Mit Zitat antworten Zitat
Robert Marquardt
(Gast)

n/a Beiträge
 
#10

Re: Doppelt verkettete Liste sortieren

  Alt 22. Feb 2005, 14:35
Der einfachste Weg ist es ein Array von Zeigern auf die Daten zu erzeugen und dann dieses Array mit QuickSort oder HeapSort zu sortieren.
Das funktioniert wenn die Daten selbst als Zeiger im Verkettungsknoten gespeichert sind.
Danach spielt man die Zeiger einfach wieder in die Liste ein.

Natuerlich hat dieses Verfahren eine limitation, naemlich der zusaetzliche Platzaufwand fuer das Array.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:38 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz