Tauschen von Pointern in einer doppelt verketteten Liste

greenhorn · Beiträge: 68 D5

Hallo Zusammen,

irgenwie bekomm ich es nicht hin, zwei elemente in einer doppelt verketteten liste zu tauschen... da schmeist er was weg, bringt alles durcheinander... ich weiss einfach nicht warum... :gruebel:

mein bisheriger code sieht wie folgt aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

procedure tDVKList.ExChange(a, b: tDVKListItem);
var
 na, va, nb, vb: tDVKListItem;
begin
 if  (a <> NIL)          and (b <> NIL)
 and (a <> fAnkerAnfang) and (a <> fAnkerEnde)
 and (b <> fAnkerAnfang) and (b <> fAnkerEnde) then
 begin
//Temp. Variablen initialisieren
  va := a.Prior;
  na := a.Next;
  vb := b.Prior;
  nb := b.Next;

  //Umgebung A tauschen
  va.Next  := b;
  na.Prior := b;

  //Umgebung B tauschen
  vb.Next  := a;
  nb.Prior := a;

  //A Tauschen
  a.Prior := vb;
  a.Next  := nb;

  //B Tauschen
  b.Prior := va;
  b.Next  := nb;

 end;
end;

wobei anzumerken ist, dass fAnkerAnfang den Anfang der Liste bildet (kein Datenelement) und fAnkerEnde das ende der Liste. Jedes Element hat drei Pointer (a) prior (welches auf das vorgängerlement zeigt) (b) next (welches auf das nachfolgerelement zeigt) und (c) einen pointer wo die nutzdaten reingehängt werden können

habs auch schon mit hilfsvariabeln versucht (siehe oben) aber da kommt er zur zeit nur in eine endlosschleife...

bitte helft mir.

:flehan:

PS: hier sollen einfach die beiden items a, b in der doppelt verketteten liste vertauscht werden...

hansa · Beiträge: 3079 Erhaltene Danke: 9

Zitat:

PS: hier sollen einfach die beiden items a, b in der doppelt verketteten liste vertauscht werden...

Was ist bei Dir ein Item ? Ein Knoten der Liste, oder nur der Inhalt des Knotens ? Soll der Inhalt der Knoten vertauscht werden oder die Reihenfolge der Knoten ?

_________________
Gruß
Hansa

alzaimar · Verfasst: So 22.10.06 19:26

Du solltest in deiner DVL-Klasse zwei Methoden implementieren, nämlich 'Löschen' und 'Einfügen'. Die einfügen-Methode erwartet als 2.Parameter den Knoten, nach dem der neue Knoten eingefügt werden soll. Dann gehts los:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Procedure TDVLList.Exchange (a,b : TDVLItem);
Var
  parentA, parentB : TDVLItem;

Begin
  parentA := a.Prior;
  parentB := b.Prior;
  Delete (a);
  Delete (b);
  InsertAfter (a, parentB);
  InsertAfter (b, parentA);
End;

Versuche bei der Implementierung von Operationen auf deiner Klasse immer, die Elementaroperationen mit einzubeziehen. Das kann natürlich dazu führen, das die Operation sehr langsam wird, aber wichtig ist zunächst, das die Anwendung funktioniert. Optimieren kannst Du immer noch.

_________________
Na denn, dann. Bis dann, denn.

Horst_H · Verfasst: So 22.10.06 20:19

Hallo,

das ist doch nur ein Zeigertauschen.
Zuerst die Vorgaenger von a,b ermitteln und tauschen.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

Temp := a.prior;
Temp.next := b;//War vorher a
Temp := b.prior;
b.prior := a.prior;
a.prior := temp;
Temp.next := a;//War vorher b

Analog dann die Nachfolger von a,b ermitteln und tauschen.(next,prior tauschen)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

Temp := a.next;
Temp.prior := b;//War vorher a
Temp := b.next;
b.next := a.next;
a.next := temp;
Temp.prior := a;//War vorher b

@alzaimar:
Kann nach delete(a) dieses einfach wieder einfuegen mittels InsertAfter.
a,b sind doch nur Zeiger.
Man müste spasseshalber in delete den Inhalt von a(.Inhalt) loeschen.delete koennte ja auch Speicher freigeben.

Gruss Horst

alzaimar · Verfasst: So 22.10.06 20:36

Hi Horst,

Normalerweise sollte eine Delete-Operation ein Listenelement nicht freigeben, ebensowenig, wie das InsertAfter ein Item erzeugt. Aber ehrlich gesagt habe ich deinen Einwand nicht verstanden.

_________________
Na denn, dann. Bis dann, denn.

Horst_H · Verfasst: So 22.10.06 22:49

Hallo,

Ich habe bei meinen wenigen Listen, bei delete auch das Element sofort entsorgt, also ein dispose oder free eingefügt.
Wenn ich also ein delete einsetzte, würde ein folgendes insert ein nicht vorhandenes Element einfügen.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Procedure TDVLList.Exchange (a,b : TDVLItem); 
Var 
  parentA, parentB : TDVLItem; 

Begin 
  parentA := a.Prior; 
  parentB := b.Prior; 
  Delete (a); //Waere bei mir jetzt geloescht
  Delete (b); //Waere bei mir jetzt geloescht 
  InsertAfter (a, parentB); //Fügt jetzt was ein?
  InsertAfter (b, parentA); 
End;

Falls a kein Zeiger, wovon ich eigentlich ausgehe, sondern eine echte Kopie von a ist das natürlich so machbar.

Hauptsache der Zeigertausch funktioniert, ungetestet

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

procedure tDVKList.ExChange(a, b: tDVKListItem);
var
  temp: tDVKListItem;
begin
  if (a<>b) and (a <> NIL) and (b <> NIL) THEN
    begin
    Temp := a.prior;
    Temp.next := b;//War vorher a
    Temp := b.prior;
    b.prior := a.prior;
    a.prior := temp;
    Temp.next := a;//War vorher b

    Temp := a.next;
    Temp.prior := b;//War vorher a
    Temp := b.next;
    b.next := a.next;
    a.next := temp;
    Temp.prior := a;//War vorher b
    //Falls a oder b der erste in der liste war
    IF a=fAnkerAnfang then
      fAnkerAnfang := b
    else
      IF b=fAnkerAnfang then
        fAnkerAnfang := a;
    //Falls a oder b der letzte in der liste war
    IF a=fAnkerEnde then
      fAnkerEnde := b
    else
      IF b=fAnkerEnde then
        fAnkerEnde := a;
    end;
end;

Gruss Horst

hansa · Beiträge: 3079 Erhaltene Danke: 9

Was ist überhaupt dieses DVL-Dingens ? :shock:

Bin jedenfalls von einer Standard-Pascal Frage ausgegangen. Solange allerdings meine Rückfrage nicht beantwortet wurde, sehe ich keinen großen Sinn zu antworten.

_________________
Gruß
Hansa

greenhorn · Beiträge: 68 D5

hallo zusammen,

das DVKList ist einfach eine doppelt verkettete liste in der man irgendwelche daten als pointer (z.b. objekte) hinterlegen kann, so in der art wie TLIST. nur dass mir TLIST bei grösseren datenmengen zu langsam wird, weil es immer alles verschiebt. daher dacht ich, mach doch mal was flexibleres... bin aber hier noch am anfang.

hier mal der ganze code (von horst die EXCHANGE routine eingefügt).

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:

unit DVKList;

interface
uses
  SysUtils;

type
 TDVKListSortCompare = function (Item1, Item2: Pointer): Integer;

 pDVKListItem = ^tDVKListItem;
 tDVKListItem = class
  private
   fPrior, fNext, fData: tDVKListItem;
  public
   constructor create;
   destructor Destroy; override;
   property Prior: tDVKListItem read fPrior write fPrior;
   property Next : tDVKListItem read fNext  write fNext;
   property Data : tDVKListItem read fData  write fData;
 end;

 pDVKList = ^tDVKList;
 tDVKList = class
 private
  fAnkerAnfang, fAnkerEnde, fLauf: tDVKListItem;
  fcount: integer;
   procedure ExChange(a, b: tDVKListItem);
 public
  constructor Create;
  destructor  Destroy; override;
  function  First: Pointer;
  function  Last : Pointer;
  function  Next : Pointer;
  function  prior: Pointer;
  function  read : Pointer;
  function  BOF  : boolean;  //Begin of List
  function  EOF  : boolean;  //End of List
  procedure Add(myPointer: pointer);
  procedure Insert(myPointer: pointer);
  procedure del(myPointer: pointer);
  procedure DelCurrent;
  property  Count: Integer read fCount;
  procedure Sort(Compare: TDVKListSortCompare);
 end;


implementation


////////////////////////////////////////////////////////////////
{ tDVKList }
////////////////////////////////////////////////////////////////

procedure tDVKList.Add(myPointer: pointer);
var
 v: tDVKListItem;
begin
 if fAnkerAnfang = NIL then
 begin //1. Element
  v := tDVKListItem.create;  fAnkerAnfang := v;
  v := tDVKListItem.create;  fAnkerEnde   := v;
  v := tDVKListItem.create;  fLauf        := v;

  fLauf.fData := myPointer; //Daten zuweisen

  fAnkerAnfang.Next := fLauf;        //Anfang setzen
  fAnkerEnde.Prior  := fLauf;        //Ende setzen
  fLauf.Prior       := fAnkerAnfang; //vorgänger setzen
  fLauf.Next        := fAnkerEnde;   //nachfolger setzen

  fCount             := 1;            //Zähler setzen
 end
 else
 begin //Zum Schluss neuen Knoten einfügen
  v := tDVKListItem.create;            //Neues Item erstellen
  v.Data           := myPointer;       //Daten zuweisen
  v.Next           := fAnkerEnde;      //Nachfolger setzen
  v.Prior          := fAnkerEnde.Prior;//Vorgänger als neuen Vorgänger setzen
  v.Prior.Next     := v;               //Neuen Nachfolger beim alten Vorgänger setzen
  fAnkerEnde.Prior := v;               //Neuen Vorgänger setzen;

  inc(fCount);                         //Zähler setzen
 end;
end;

procedure tDVKList.Insert(myPointer: pointer);
var
 v,n,t: tDVKListItem;
begin
 if (fAnkerAnfang = NIL) OR (count = 0) then
 begin
  add(myPointer);
 end
 else
 begin
  t            := tDVKListItem.create;
  t.Data       := myPointer;

  if fLauf = fAnkerAnfang then fLauf := fAnkerAnfang.Next;
  if fLauf = fAnkerEnde then   fLauf := fAnkerEnde.Prior;

  v := fLauf;
  n := fLauf.Next;

  v.Next  := t;
  t.Prior := v;

  n.Prior := t;
  t.Next  := n;

  fLauf := t;
 end;
end;

function tDVKList.BOF: boolean;
begin
 if (fLauf = NIL)
 or (fLauf = fAnkerAnfang)
 or (fLauf.fPrior = NIL)  then
  result := true
 else
  result := false;
end;

function tDVKList.EOF: boolean;
begin
 if (fLauf = NIL)
 or (fLauf = fAnkerEnde)
 or (flauf.fNext = NIL) then
  result := true
 else
  result := false;
end;

constructor tDVKList.Create;
begin
 inherited;
 fAnkerAnfang := NIL;
 fAnkerEnde   := NIL;
 fLauf        := NIL;
 fcount       := 0;
end;

// hier nach den Pointer in fLauf.data suchen
// und dann diesen knoten freigeben
procedure tDVKList.del(myPointer: pointer);
begin
 if  (fAnkerAnfang       <> NIL)
 and (fAnkerAnfang.fNext <> NIL) then //Liste wurde mal erstellt.
 begin
  fLauf := fAnkerAnfang.Next;
  repeat
   if fLauf.Data = myPointer then
   begin
    delCurrent;  //akutellen knoten löschen
    Exit;
   end;
   fLauf := fLauf.Next;
  until fLauf.Next = fAnkerEnde;
 end;
end;

//Aktueller Knoten auf dem fLauf zeigt wird gelöscht und
//die Zeiger angepasst.
procedure tDVKList.DelCurrent;
var
 v,n,t: tDVKListItem;

begin
 if  (fLauf        <> NIL)
 and (fAnkerAnfang <> NIL)
 and (fAnkerEnde   <> NIL)
 and (fLauf        <> fAnkerAnfang)
 and (fLauf        <> fAnkerEnde)  then
 begin
  dec(fcount);      //Zähler verminden

  t := fLauf; //Laufvariable sichern
  v := fLauf.Prior; //Vorgänger merken
  n := fLauf.Next;  //Nachfolger merken

  v.Next  := n; //Pointer des Nachfolgers des Vorgängers auf Nachfolger setzen
  n.Prior := v; //Pointer des Vorgängers des Nachfolgers auf Vorgänger setzen

  //Knoten freigeben
  freeAndNil(t);

  //Laufvariable neu Positionieren
  if v <> fAnkerAnfang then
   fLauf := v     //Wenn noch Vorgänger vorhanden, auf Vorgänger positioieren
  else
   if n <> fAnkerEnde then
    fLauf := n    //Wenn noch Nachfolger vorhanden, auf Nachfolger positionieren
   else
    fLauf := NIL; //Wenn kein Item mehr vorhanden, auf NIL setzen
 end;
end;

destructor tDVKList.Destroy;
var
 v: tDVKListItem;
begin

 //Liste durchlaufen und freigeben
 if  (fAnkerAnfang <> NIL)
 and (fAnkerAnfang.fNext <> NIL) then //wenn knoten vorhanden sind
 begin
  fLauf := fAnkerAnfang; //auf ersten knoten setzen
  repeat
   v := fLauf.fNext;  //nachfolger merken
   FreeAndNIL(fLauf); //objekt freigeben

   fLauf := v;        //auf nächsten knoten setzen
  until v = NIL;      //solange bis kein knoten mehr existiert
 end;
 inherited;
end;

function tDVKList.First: Pointer;
begin
 result := NIL;
 if (fAnkerAnfang <> NIL)
 or (fLauf        <> NIL) then
 begin
  fLauf := fAnkerAnfang.fNext;
  result := flauf.Data;
 end;
end;

function tDVKList.Last: Pointer;
begin
 result := NIL;
 if (fAnkerEnde <> NIL)
 or (fLauf      <> NIL) then
 begin
  fLauf := fAnkerEnde.fPrior;
  result := fLauf.Data;
 end;
end;

function tDVKList.Next: Pointer;
begin
 result := NIL;
 if not Eof then
 begin
  fLauf := fLauf.Next;
  result := fLauf.Data;
 end;
end;

function tDVKList.prior: Pointer;
begin
 result := NIL;
 if not BOF then
 begin
  fLauf := fLauf.Prior;
  result := flauf.Data;
 end;
end;

function tDVKList.read: Pointer;
begin
 result := NIL;
 if fLauf <> NIL then result := fLauf.Data;
end;

// ITEM1 > ITEM2 --> >0
// ITEM1 < ITEM2 --> <0
// ITEM1 = ITEM2 --> 0
procedure tDVKList.Sort(Compare: TDVKListSortCompare);
var
 v: tDVKListItem;
begin
 if  (fLauf        <> NIL) //pointer initialisiert
 and (fAnkerAnfang <> NIL)
 and (fAnkerEnde   <> NIL)
 and (fAnkerAnfang.Next <> fAnkerEnde.Prior) then //und mehr als ein Element vorhanden
 begin
  flauf := fAnkerAnfang.next;
  while fLauf <> fAnkerEnde.Prior do
  begin
   v := fLauf.Next;
   while v <> fAnkerEnde.Prior do
   begin
    if compare(fLauf.Data, v.Data)<0 then
    begin
     ExChange(fLauf, v);
     break;
    end;
    v := v.Next;
   end;
   fLauf := fLauf.Next;
  end;
 end;
end;

procedure tDVKList.ExChange(a, b: tDVKListItem);
var
  temp: tDVKListItem;
begin
  if (a<>b) and (a <> NIL) and (b <> NIL) THEN
    begin
    Temp := a.prior;
    Temp.next := b;//War vorher a
    Temp := b.prior;
    b.prior := a.prior;
    a.prior := temp;
    Temp.next := a;//War vorher b
    Temp := a.next;
    Temp.prior := b;//War vorher a
    Temp := b.next;
    b.next := a.next;
    a.next := temp;
    Temp.prior := a;//War vorher b
    //Falls a oder b der erste in der liste war
    IF a=fAnkerAnfang then
      fAnkerAnfang := b
    else
      IF b=fAnkerAnfang then
        fAnkerAnfang := a;
    //Falls a oder b der letzte in der liste war
    IF a=fAnkerEnde then
      fAnkerEnde := b
    else
      IF b=fAnkerEnde then
        fAnkerEnde := a;
    end;
end;

////////////////////////////////////////////////////////////////
{ tDVKListItem }
////////////////////////////////////////////////////////////////

constructor tDVKListItem.create;
begin
 inherited;
 Prior:= NIL;
 Next := NIL;
 Data := NIL;
end;

destructor tDVKListItem.Destroy;
begin
 inherited;
end;

end.

und hier der testrahmen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:

unit uTest;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, DVKList, ComCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    msg: TStatusBar;
    Button2: TButton;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private-Deklarationen }
    dvkList: tDVKList;
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

function sComp(Item1, Item2: Pointer): Integer;
var
 i,j: integer;
begin
 i := strtoInt(pChar(item1));
 i := strtoInt(pChar(item2));
 if i < j then
  result := -1
 else
  if i = j then
   result := 0
  else
   result := 1;
end;

procedure TForm1.Button1Click(Sender: TObject); //einfügen
var
 i: integer;
 pc: pchar;
 s: string;
begin
 memo1.Clear;
 for I := 1 to 3 do
 begin
  s := inttostr(i);
  pc := strnew(pAnsiChar(s));
  dvkList.insert(pc);
 end;

  dvkList.first;
  for I := 1 to 3 do
  begin
   s := inttostr(i+26);
   pc := strnew(pAnsiChar(s));
   dvkList.insert(pc);
   dvkList.Next;
  end;

  dvkList.Sort(sComp);  //sortieren

 dvkList.first;
 while not dvkList.EOF do
 begin
  s := pChar(dvkList.read);
  memo1.Lines.Add(s);
  dvkList.Next;
 end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  i: Integer;
begin
 i := 0;

//delete 1 from 2
 if dvkList <> NIL then
 begin
  dvkList.First;
  while not dvkList.EOF do
  begin
   inc(i);
   if (i mod 2) = 0 then
   begin
    StrDispose(dvkList.read);
    dvkList.DelCurrent;
   end;
   dvkList.Next;
  end;

  //ausgabe in memo
  memo1.Clear;
  dvkList.First;
  while not dvkList.EOF do
  begin
   memo1.Lines.Add(pChar(dvkList.read)^);
   dvkList.Next;
  end;
 end;

end;

procedure TForm1.FormCreate(Sender: TObject);
begin
 dvkList := tDVKList.Create;
 randomize;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
 if dvkList <> NIL then
 begin
  dvkList.First;
  while not dvkList.EOF do
  begin
   StrDispose(dvkList.read);   //Item freigeben
   dvkList.Next;
  end;
  dvkList.Free;
 end;
end;

end.

nur leider funktioniert das sortieren noch nicht. was ist hier noch falsch? :-(

@hansa: als item bezeichne ich den knoten in der liste. bin jetzt auch schon auf den gedanken gekommen, einfach den inhalt auszutauschen, möcht ich aber nicht tun, da die integrität des objektes verletzt wird und ich in das objekt noch weitere eigenschaften implementieren möchte.

Horst_H · Verfasst: Mo 23.10.06 11:50

Hallo,

da stimmt doch was nicht

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

function sComp(Item1, Item2: Pointer): Integer; 
var 
 i,j: integer; 
begin 
 i := strtoInt(pChar(item1)); 
 i := strtoInt(pChar(item2));// <----------- Wie waere es mit j statt i
 if i < j then 
  result := -1 
 else 
  if i = j then 
   result := 0 
  else 
   result := 1; 
end;

Wieso kannst Du das erste Element nicht benutzen?
Soll deine Liste ein Ring sein?

Gruss Horst

hansa · Beiträge: 3079 Erhaltene Danke: 9

Stimmen die Datenstrukturen so überhapt ? Habe hier mal eine eigene Liste gesucht :

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

  TZeiger = ^TDaten;

  TDaten = record
// eigentliche Daten
    Nachfolger,
    Vorgaenger : TZeiger;
  end;

  TListe = class
  public
    Aktuell,
    First,
    Last : TZeiger;
    Anzahl : integer;
    constructor create;
    procedure Auflegen;
  end;

var Liste : TListe;

Außer, daß das Ganze nur wenig OOP und Methoden hat, müßte es allgemeingültig sein. Vergleiche das mal selber mit deinem Code. Der ist mir jetzt zu kompliziert. :mrgreen:

_________________
Gruß
Hansa

greenhorn · Beiträge: 68 D5

hallo zusammen,

an der vergleichsmethode lag es nicht. aber das problem ist berichtig :oops:

. habe die vermutung, dass noch etwas mit dem tausch nicht funktioniert... wenn ich nur wüsste was :?!?:

@hansa: tja, dein code hilft mir nicht wirklich weiter... fand, da fehlt was... aber im prinzip ist es schon das gleiche, nur halt statt 'n record 'ne class :wink:

aber ich denk, an dem kanns nicht wirklich liegen.

@horst: nein, das ganze ist eine liste, nur dass ich das erste und das letzte element nicht nütze. die sind für mich zeiger, damit ich weiss, wo der anfang und das ende liegt. so kann ich bequem von vorne nach hinten und von hinten nach vorne durch die liste gehen

hoffe ihr habt noch einen tip :flehan:

hansa · Beiträge: 3079 Erhaltene Danke: 9

greenhorn hat folgendes geschrieben:

...
@hansa: tja, dein code hilft mir nicht wirklich weiter... fand, da fehlt was... aber im prinzip ist es schon das gleiche, nur halt statt 'n record 'ne class :wink:

aber ich denk, an dem kanns nicht wirklich liegen.
...

Tja, und nun ? Was fehlt ? Überlegen !

_________________
Gruß
Hansa

Martok · Verfasst: Di 24.10.06 04:49

greenhorn hat folgendes geschrieben:

Jedes Element hat drei Pointer (a) prior (welches auf das vorgängerlement zeigt) (b) next (welches auf das nachfolgerelement zeigt) und (c) einen pointer wo die nutzdaten reingehängt werden können

Dann reicht es doch theoretisch, nur die Daten-Pointer zu tauschen, oder?

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

hansa · Beiträge: 3079 Erhaltene Danke: 9

Was mein Vorredner farblich gekennzeichnet hat, das ist der Unterschied.

Ich habe die Nutzdaten von den Zeigern getrennt. Bin mir nicht sicher, aber was soll das, dass eine Liste einen Zeiger hat, der auf sich selbst zeigt ? :shock:

_________________
Gruß
Hansa

alzaimar · Verfasst: Di 24.10.06 11:26

Also, OOP geht doch anders:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

Type
  TDLItem = Class
    fPrior,
    fNext : TDLItem;
    fData : Pointer;
//    fKey : TSomeType;
  Public
    Constructor Create (aData : Pointer{; aKey : TSomeType});
//    Property Key : TSomeType Read fKey; // Jedes Listenelement sollte einen eindeutigen Schlüssel haben, nach dem man suchen kann
    Property Prior : TDLItem Read fPrior Write fPrior;
    Property Next : TDLItem Read fNext Write fNext;
    Property Data : Pointer Read fData Write fData; // Hier hängen die Daten dran
  End;

  TDoubleLinkedList = Class
    fRoot : TDLItem;
    fWalker : TDLItem; // Interner 'läufer' für die First/Next/Prior/Last Methoden
  Public
    Constructor Create;
    Destructor Destroy;
    Procedure Append (anItem : TDLItem);
    Procedure InsertAfter (aParent, anItem : TDLItem); 
    Procedure Delete (anItem : TDLItem); // Das Element wird *nicht* freigegeben
    Procedure Clear; // Liste wird geleert und die Elemente werden freigegeben
//  Function FindItem (aKey : TSomeType) : TDLItem;

//  ...  Was einem noch so einfällt

    Function First : TDLItem; // Liefert das erste Element der Liste oder nil, wenn die Liste leer ist
    Function Last : TDLItem; // Liefert das letzte Element der Liste oder nil, wenn die Liste leer ist
    Function Next : TDLItem; // Liefert das nächste Element der Liste oder nil, wenn die Liste durchlaufen wurde
    Function Prior : TDLItem; // Liefert das vorherige Element der Liste oder nil, wenn die Liste am anfang steht
  End;

Die Implementierung einer solchen Klasse sollte keine Wünsche offen lassen. Mit den Methoden 'Delete' und 'InsertAfter' ist dann auch das 'Exchange' kein Problem.

Die 'Delete' Methode ist bezüglich des TDLItems deshalb nicht destruktiv (gibt also das Element *nicht* frei), weil die Gegenstücke (Append bzw. InsertAfter) nicht konstruktiv sind.

Greenhorn: Tipp das o.g. mal ein und drücke 2x Ctrl+C, einmal mit dem Cursor auf dem 'Constructor Create' in der Definition für TDLItem (oder in der Nähe) und einmal in der Klasse 'TDoubleLinkedList'. Dann bekommst du schon das Implementierungsgrüst. Dann einfach alle Methoden auffüllen und los gehts.

_________________
Na denn, dann. Bis dann, denn.

greenhorn · Beiträge: 68 D5

so jetzt hab ichs.

@horst_h: dein vertauschalgo war doch richtig, das problem lag an anderer stelle

habs jetzt so gelöst

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:

//a) das Item bekommt 'ne neue methode
 tDVKListItem = class
  private
   fPrior, fNext, fData: tDVKListItem;
  public
   constructor create;
   destructor Destroy; override;
   property Prior: tDVKListItem read fPrior write fPrior;
   property Next : tDVKListItem read fNext  write fNext;
   property Data : tDVKListItem read fData  write fData;
   procedure linkTakeOver(aNode: tDVKListItem);  //Platz in der Liste von aNode übernehmen <-- neue Methode
 end;

//b) die ist folgendermassen definiert
//Übernimmt von aNode den Vorgänger und Nachfolger
procedure tDVKListItem.linkTakeOver(aNode: tDVKListItem);
begin
 if (aNode <> NIL) then
 begin
  prior := aNode.Prior;
  fprior.Next := self;

  Next := aNode.Next;
  fNext.Prior := self;
 end;
end;

//c) damit vereinfacht sich in der Verwaltungseinheit der Aufruf
procedure tDVKList.ExChange(a, b: tDVKListItem);
var
 tmp: tDVKListItem;
begin
 if (a<>b) and (a <> NIL) and (b <> NIL) THEN
 begin
  tmp := tDVKListItem.create;
  try //wo ist die komplexität geblieben??????
   tmp.linkTakeOver(a);
   a.linkTakeOver(b);
   b.linkTakeOver(tmp);
  finally
   tmp.Free;
  end;
 end;

das problem warum das sortieren nicht klappte war, dass durch den tausch die ganze liste durcheinanderkam. daher muss man sich nur den nächsten knoten merken und die ganze sache läuft rund ;-)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

procedure tDVKList.Sort(Compare: TDVKListSortCompare);
var
 tmp, v, x: tDVKListItem;
begin
 if  (fLauf        <> NIL) //pointer initialisiert
 and (fAnkerAnfang <> NIL)
 and (fAnkerEnde   <> NIL) then
 begin
  x := fAnkerAnfang.next;  // auf erstes Element positionieren
  while x <> fAnkerEnde.Prior do //liste bis zum ende durchgehen
  begin
   //das Element X ist hier der Schlüssel
   flauf := x; //nächstes Item zuweisen
   x := x.Next; //nächstes Item merken ---> ohne den hier gehts nicht, da die anderen elemente verändert werden.
   tmp := fLauf; //Merker Initialisieren
   v := fLauf.Next; //auf folgeelement positionieren
   while v <> fAnkerEnde do   //liste bis zum ende durchgehen
   begin
    if compare(tmp.Data, v.Data) < 0) then tmp := v; //kleinstes element merken
    v := v.Next; //auf nächstes element setzen
   end;
   if tmp <> fLauf then ExChange(fLauf, tmp); //fals verändert, beide elemente tauschen
   fLauf := fLauf.Next; //auf nächstes element setzen
  end;
 end;
end;

danke für die Hilfe. :beer:

@alzaimar: keine sorge hier kommen noch ein paar schöne sachen rein. danke noch für den denkanstoss. :autsch:

@Martok: genau, das wollte ich ja nicht machen, da das trägerobjekt noch einige andere eigenschaften bekommt und daher schon abzusehen ist, dass das ganze wohl nur noch komplizierter würde und ausserdem kein guter stil wäre.

@hansa: ich find hier keine objekt welches auf sich selbst zeigt... klar man hätt kein objekt dazu gebraucht, mit 'n record, aber in diesem falle will ich es einfach mal so machen und die möglichkeiten und grenzen ausloten. vielleicht wird ja was vernünftiges draus :wink:

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme