Probleme mit Listen/ verkettet Listen

[legionen]

Hallo,

ich habe folgendes Problem:

ich habe in Delphi Listen erzeugt, welche ich auch fleißig mit Daten bestücke, aber an einer Stelle muss ich die Pointer verschieben, z.B. A zeigt auf B, B zeigt auf C...... aber jetzt soll A auf C zeigen und B gelöscht werden..... Leider klapt das bei mir nicht richtig.

Die Liste ist unter Type definiert:

Code:

Type
  Daten = ^WListe;
  Liste = RECORD
    Nummer : integer;
    ND : WDaten;
  END;

Weiter habe ich eine globale Variable welche ein DummyStartpunkt enthält

Code:

var
  Dummy : WDaten;

Mit Inhalt befühlt wird die Liste mit folgenden Befehlen

Code:

Procedure TForm1.ErzeugeListe;
var
  Element : WDaten;
  i : Integer;
Begin
  new (Dummy);
  Element := Dummy; // Verweiß auf Dummy
  For i := 1 To 10 Do
    Begin
      new (Element^.ND);
      Element := Element^.ND; //Damit Zeiger auf letzten Element liegt!
      Element.Nummer := i;
      Element.ND := Nil;
    End;
End;

Auslesen kann ich die ganze Liste ohne Probleme.... While Element.ND <> NIL Do .....

ABER WIE KANN ICH DEN ZEIGER VOM sagen wir Element mit Nummer = 2 zu Element mit Nummer 4 machen?????

VIELEN DANK SCHON MAL FÜR EURE HILFE!!!!!!!!!!!!!!!

[Klaus01]

Hallo,

Erstelle ein Dummy Element, weise dem dummy die Daten von Position B zu.
Dann weist Du dem Element B die Daten von D zu und anschließend dem Element
D die Daten des dummy Elementes.

Oder die Zeiger zum Nachfolger verbiegen.

Liste : A-> B -> C -> D
Die willst B und D vertauschen.

Die Adresse des NAchfolger von A sichern.
Der NAchfolger von A bekommt die Adresse des Elementes D.
C Nachfolger bekommt die Adresse von B (Nachfolger von A).
B Nachfolger die Adresse von D.

Liste: A->D->C->B

Grüße
Klaus

Grüße
Klaus

[legionen]

erstmal danke für die antwort, aber ich will eigentlich nicht einfach zwei inhalte der Elemente vertauschen, sondern die ZEIGER umändern....

A -> B -> C -> D -> ......

zu:

A -> B -> D -> .....


ich will auch nicht einfach alle Elemente eins nach links verschieben, weil ich sonst in den Listen immer mehr Datenschrott bekomme..... Kennt ihr den Algorithmus, wie ich die den Zeiger von B, der auf C zeigt auf D bekommen kann.... und gleichzeitig das Element C löschen kann?????

[Klaus01]

Zitat:

Zitat von legionen

erstmal danke für die antwort, aber ich will eigentlich nicht einfach zwei inhalte der Elemente vertauschen, sondern die ZEIGER umändern....

A -> B -> C -> D -> ......

zu:

A -> B -> D -> .....


Kennt ihr den Algorithmus, wie ich die den Zeiger von B, der auf C zeigt auf D bekommen kann.... und gleichzeitig das Element C löschen kann?????

Den Algorithmus solltest Du dir schon selber programmieren, einen fertigen gibt es da nicht.

Wenn Du Element C löschen willst.
Den Nachfolger von B auf D umbiegen -> Nachfolger B wird Nachfolger C
Das C Element löschen, z.B. mit dispose.

Mußt Du mit verketteten Listen arbeiten?
Sonst kannst Du dir ja 'mal die TList anschauen - die ist etwas komfortabler.

Grüße
Klaus

[legionen]

die theorie kenne ich auch ;) ich weiß ja was ich will, aber mir fehlen die richtigen BEFEHLE!!! ich weiss nicht wie ich den Zeiger richtig umändern kann.... so wie ich es bisher probiert habe funktioniert einfach nicht...... deshalb frage ich ja hier nach rat!

Naja das mit Tlist habe ich auch schon gehört, aber das Problem ist, dass ich an dem Programm schon über 8 monate arbeite und das Programm doch schon zu einer ordentlichen Größe herangewachsen ist....... jetzt auf TList umzusteigen wäre etwas aufwendig....

daher bitte ich euch, mir schnell für das Beispiel die Befehlskette aufzuschreiben......

ohne das zu überschreibende Objekt zu löschen hatte ich es mit

Element.ND := Element^.ND;

// also in diesem Fall der Zeiger von B auf C (Element.ND) soll den Zeiger von C bekommen (Element^.ND)

probiert, aber irgentwie klappt das nicht.

Please show me how stupid i am and give me a easy solution ;)

[Klaus01]

Nun, ich weiß nicht wie ich Dir das anders erklären soll:

Ein Beispiel von mir wie ein Element aus einer doppelt verketteten Liste gelöscht wird.
Vielleicht hilft es Dir ja weiter.

Delphi-Quellcode:

procedure TFeed.deleteItem(aPointer:Pointer);
begin
  ItemList:=aPointer;
  if (aPointer <> firstItem) and (aPointer <> lastItem) then
    begin
      ItemList^.next^.prev:=ItemList^.prev;
      ItemList^.prev^.next:=ItemList^.next;
    end;

  if aPointer = firstItem then
    begin
      firstItem:=ItemList^.next;
      if firstItem <> nil then
        ItemList^.next^.prev:=nil;
    end;

  if aPointer = lastItem then
    begin
      lastItem := ItemList^.prev;
      if lastItem <> nil then
        ItemList^.prev^.next:=nil;
    end;

  dispose(ItemList);
end;

wobei ItemList so ausschaut:

Delphi-Quellcode:

  itemList: PfeedSet;

und PfeedSet so:

Delphi-Quellcode:

  PfeedSet = ^TfeedSet;
  TfeedSet = record
    data : TData;
    prev,next: PfeedSet;
  end;

end;

[edit] noch ein Link zur Verdeutlichung.[/edit]

Grüße und eine gute Nacht
Klaus

[legionen]

Danke, der Link ist schon echt gut, aber leider verstehe ich das mit dem löschen da nicht.

Die schreiben da zum löschen (bezogen auf mein Beispiel)

Element^.ND := Element^.ND^.ND;

statt wie ich : Element.ND := Element^.ND;


jetzt ist das halt so.... wenn ich in der Liste A -> B -> C -> D -> ...
von B nach D kommen möchte, so müsste ich mich laut der Anweisung der Hilfe in Element A befinden, da die Anweisung Element^.ND sich auf den Zeiger von B aus A heraus befindet..... wieso geht meine Version nicht?? den da nehme ich direkt den Zeiger aus B....

das löschen so wie die das beschrieben haben geht doch einen Schritt immer hinten her..... das macht es viel schwerer....

oder gibts da irgentein Problem mit der Definition, das man bei Element.ND keinen Zeiger setzen kann?

[Klaus01]

Zitat:

Zitat von legionen

Danke, der Link ist schon echt gut, aber leider verstehe ich das mit dem löschen da nicht.

Die schreiben da zum löschen (bezogen auf mein Beispiel)

Element^.ND := Element^.ND^.ND;

statt wie ich : Element.ND := Element^.ND;


jetzt ist das halt so.... wenn ich in der Liste A -> B -> C -> D -> ...
von B nach D kommen möchte, so müsste ich mich laut der Anweisung der Hilfe in Element A befinden, da die Anweisung Element^.ND sich auf den Zeiger von B aus A heraus befindet..... wieso geht meine Version nicht?? den da nehme ich direkt den Zeiger aus B....

Zeiger B = Element
Zeiger auf den Nachfolger von B ist Element^.ND
dieser zeigt in der Liste auf C.
Das Listenelement D hat aber die Adresse von B ausgesehen
Element^.ND^.ND.
Da Du von B nach D willst ist es doch logisch den Nachfolger von B auf die Adresse
von D zu legen. Element^.ND:=Element^.ND^.ND
Wenn Du dann noch c löschen willst, mußt Du dir vorher Element^.ND merken
und dann entfernen.

Mal es Dir einfach mal auf einem Blatt Papier auf - es ist nicht so schwer wie es ausschaut.

Gute Nacht
Klaus

[DeddyH]

Ist zwar schon lange her, dass ich was mit verketteten Listen gemacht habe, aber ich versuche trotzdem mal eine Erklärung:
Eine verkettete Liste besteht im Allgemeinen aus Strukturen (Records), die als ein Element 1 (einfach verkettete Liste) oder 2 (doppelt verkettete Liste) Zeiger auf einen Record ihres eigenen Typs beinhalten. Ich nenne diese jetzt mal Navigationszeiger. Das sähe dann etwa so aus:

Delphi-Quellcode:

type PMyRecord = ^TMyRecord;
TMyRecord = record
  Next: PMyRecord; //Navigationszeiger auf das nächste Element der Liste
  Prev: PMyRecord; //bei einer doppelt verketteten Liste Navigationszeiger auf das Vorgängerelement
  ... //Nutzdaten
end;

Bei einer einfach verketteten Liste hat das letzte Element im Feld Next den Wert nil stehen, um das Ende der Liste zu kennzeichnen. Bei einer doppelt verketteten Liste hat das erste Element im Feld Prev nil stehen. Um nun ein Element aus der Liste zu löschen, musst Du dessen Navigationszeiger auf den seines Nachfolgers bzw. Vorgängers setzen, um die Kette nicht zu unterbrechen. Anschließend kannst Du den Speicher des Elements freigeben. Dazu sicherst Du Dir den Zeiger auf das zu löschende Element, biegst diesen auf dessen Nachfolger um und räumst auf.

Delphi-Quellcode:

//Beispiel mit einer einfach verketteten Liste
//ich gehe davon aus, dass Du in einer while-Schleife durch die Elemente iterierst
if Assigned(Element^.Next) and (Element^.Next^.Daten = Kriterium) then //es handelt sich um den Nachfolger des aktuellen Elements
  begin
    tmp := Element^.Next; //alten Zeiger merken
    Element^.Next := tmp^.Next; //Navigationszeiger um eine Position weiter verschieben
    Dispose(tmp); //Speicher freigeben
  end

Das kann man auch schön grafisch darstellen, dann fällt einem das Verständnis leichter.

[legionen]

OKAY, dass mit dem Zeigern habe ich jetzt verstanden :) aber leider bin ich anscheint zu blöd folgendes Problem weitergehend zu lösen:

ich probiere das Problem wieder etwas zu verallgemeinern, aber ich hoffe das es so klappt...

Also ich habe natürlich eine etwas größere Liste, die nicht nur einfach mit einer fortlaufenden zahl gefühlt ist, sondern es werden nach einer bestimmten Rechnung Werte zwischen 0 und 100 eingetragen.... wenn zwei aufeinanderfolgende Werte ähnlich sind, so sollen diese zusammengezogen werden und dann die Liste wieder von Vorne durchlaufen..... solange bis kein aufeinanderfolgendes Wertepaar mehr zusammengezogen wurde..... soweit zur Theorie.... leider macht mir die Umsetzung Probleme.... ich mache mal kurz folgendes Beispiel:

A (1,1) -> B (3,2) -> C (3,3) -> D (3,1) -> E (20

Also wie soll das Programm durchlaufen....

Im ersten Schritt sollen B und C zusammenkommen und die Liste weiter durchlaufen...

A (1,1) -> B (3,25) -> D (3,1) -> E (20)

im zweiten Schritt sollen B und D zusammenkommen

A (1,1) -> B (3,175) -> E (20)

im dritten Schritt soll nichts mehr gemacht werden und die Prozedure abbrechen.....

So mein Quellcode:

ZUR Erklärung:

Die beiden Boolean Files Durchlauf und gefunden, dienen einfach als Kriterium ob die While Do Schleifen weiter müssen
- Durchlauf steht dafür, dass wenn bei einem Durchlauf kein Element zusammengeführt wurde die While Do Procedure abgebrochen werden soll
- gefunden gibt zurück wenn innerhalb der zweiten While Do Schleife zwei Elemente zusammengelegt wurden und deshalb von vorne alles nochmal durchsucht werden soll.

die Große IF Then Anweisung bildet von beiden Werten den Mittelwert und guckt ob die beiden Werte jeweils in einem Streubereich enthalten sind.... habe diese IF THEN Anweisung stark zusammengefasst, damit sie keine so großen Probleme darstellt....

Delphi-Quellcode:

 While Durchlauf Do
   Begin
     Element := Dummy; // Bei jedem Start des Durchlaufs soll wieder auf von vorne gesucht werden
     Durchlauf := False; // wenn nichts gefunden wird, soll die Schleife abgebrochen werden
     gefunden := false; // da die schleife wieder von vorne anfängt, soll erstmal die zweite while do schleife laufen
     While (Element^.nd<> NIL) and (Gefunden = false) do // wenn er ende erreicht soll abgebrochen werden
       Begin
         Element:= Element^.nd; // immer ein Element weiter
         gefunden := true; // hier schonmal auf true setzen
         // in der IF Then Anweisung werden die Werte des aktuellen mit dem nächsten vergleicht.. jeweils 20% kleiner/ größer
         // dürfen die Einzelwerte sein, damit die beiden Elemente zusammengelegt werden
         If (Element.Nummer [1] < (((Element.Nummer [1]+Element^.Nummer [1]) / 2) * 1.2)) and
            (Element.Nummer [1] > (((Element.Nummer [1]+Element^.Nummer [1]) / 2) * 0.8)) and
            (Element^.Nummer [1] < (((Element.Nummer [1]+Element^.Nummer [1]) / 2) * 1.2)) and
            (Element^.Nummer [1] > (((Element.Nummer [1]+Element^.Nummer [1]) / 2) * 0.8)) Then
           Begin 
             // Sind die beiden Elemente in dem Bereich, dann soll der erste als Wert den Mittelwert beider bekommen
             Element.Nummer := (Element.Nummer [1]+Element^.Nummer [1]) / 2;
             // hier soll dann der Zeiger übergeben werden wenn ich die IF anweisung drinnen halte, dann ist es eine endlosschleife
             // wenn ich sie rausnehme, kommt es zu einem Fehler
             IF Element^.nd^.nd<> NIL Then
               Element^.nd:= Element^.nd^.nd;
             Durchlauf := true;
           End
           Else gefunden := false; //soll weiter suchen, bis die andere While anforderung erfühlt ist.....
       End;
   End;

Ich weiß, dass ich hier sicherlich einiges abverlange, aber ich drehe noch durch..... ist für meine Diplomarbeit und leider kommen ständig probleme, die man durch solche Lösungen ab zuschwächen probiert....

Ich freue mich schon auf eure Lösung ;)