![]() |
Löschen eines Elementes in einer einfachen Liste
Hallo Leute,
ich habe eine kleine Frage: Wenn ein Element am Tailbereich einer einfach verketteten Liste steht und ich es löschen möchte, wie mache ich das am besten? Die Liste ist im OOP-Stil programmiert, ohne Zeiger.
Delphi-Quellcode:
Wie ihr sieht habe ich das Taillöschen programmiert, aber ich bin der Meinung, dass dies überhaupt nicht effizient ist, da man ja durch die Liste durchgehen muss (bis zum vorletzen Element). Bei 100000 Datensätzen kann dies einwenig länger dauern. Wie kann man dies lösen?
procedure TElist.delete;
var p: TLElement; // private rechts: TLElement; {Zeigt das nächste Element} Data : Integer; {Dort wird die Information gespeichert} begin if aktuell = head then // Wenn der Zeiger aktuell sich bei Head befindet, dann ... begin head := aktuell.GetRechts; // erhält Head den nächsten Element durch die Methode GetRechts aktuell.Free; // Arbeitsspeicher wird freigegeben aktuell:= head; // Aktuell befindet sich wieder bei Head end else begin if aktuell= tail then // Wenn der Zeiger aktuell sich bei Tail befindet, dann ... begin p := head; while(p <> NIL) and (p.GetRechts <> aktuell) do //geht man mit Hilfe einer Variable durch die ganze Liste bis man vor Tail steht p := p.GetRechts; p.setRechts(aktuell.GetRechts); //Das Element vor Tail erhält den Wert GetRechts (In dem Fall = NIL) aktuell.Free; // Arbeitsspeicher wird freigegeben aktuell:= p; // Aktuell befindet sich wieder bei p (das vorletzte Element) tail:= p; // tail ist dann p end else begin // Wenn Aktuell zwischen Head und Tail sich befindet p := aktuell.GetRechts; // Wird einfach das Element, welches gelöscht werden soll, mit dem nächsten Element vertauscht aktuell.setData(p.GetData); // aktuell erhält den Wert des nächsten Elementes (vertauscht) aktuell.setRechts(p.GetRechts); // Der Zeiger zeigt auf das übernächste Element p.Free; // p wurde deleted ;D end; end; dec(count); end; Eine Idee hätte ich, man erzeugt eine doppelverkettete Liste, also ein Zeiger der zum vorherigen Element zeigt. Leider darf ich das nicht machen. Es muss eine einfach verkettete Liste sein. Wenn ihr fragen habt, fragt einfach. Es kann alles verwirrend sein :) Sarte |
Re: Löschen eines Elementes in einer einfachen Liste
Hallo,
wie ich gesehen habe, führst Du eine Variable count mit. Dann müßte das Ende doch: ende = head + count * sizeOf(pointer) sein. Wenn ich mich nicht ganz irre. [edit] wenn denn keine Lücken in der Liste sind [/edit] Grüße Klaus |
Re: Löschen eines Elementes in einer einfachen Liste
Dieses Problem hast Du bei einer einfach verketteten Liste aber immer. Ich wüsste jetzt auch nicht, wie man das anders machen könnte.
[edit] @Klaus: Ich kann mich irren, aber IIRC müssen verkettete Listen nicht unbedingt in einem zusammenhängenden Block im Speicher stehen. [/edit] |
Re: Löschen eines Elementes in einer einfachen Liste
wie ist TElement definiert?
und wie ohne Zeiger? :shock: (bin ich blind, oder denk ich nur welche zu sehn) [add] OK, sind wohl Objekte, aber kommt auf's Selbe raus und kannst du die Struktur nicht doch noch etwas ändern? |
Re: Löschen eines Elementes in einer einfachen Liste
Zitat:
Ein Beispiel: Liste: 3 | 4 | 5 | 6 | 9 | Wenn aktuell sich bei 4 befindet, dann vertausche ich die 4 mit der 5: 3 | 5 | 4 | 6 | 9 | Und kann dann das Element mit der 4 Löschen, sonst müsste ich zur 3 gehen und dort seinen Zeiger zum nächsten Element ändern. Wenn aber aktuell bei Tail steht, also die 9 3 | 4 | 5 | 6 | 9 | -> NIL dann kann ich das nicht so einfach machen, weil da ja NIL steht. |
Re: Löschen eines Elementes in einer einfachen Liste
Zitat:
Delphi-Quellcode:
Ja ich soll das ohne Zeiger machen -.-
type
TLElement = class private rechts: TLElement; Data : Integer; public procedure setData(Daten: Integer); procedure setRechts(next: TLElement); function GetRechts:TLElement; function GetData:Integer; end; Die Struktur soll leider so bleiben. |
Re: Löschen eines Elementes in einer einfachen Liste
Zitat:
Trotzdem danke an euch ;), wenn jemand aber eine Idee hat, bitte melden. |
Re: Löschen eines Elementes in einer einfachen Liste
Wie gesagt, ob Record/Pointer oder Object, ist doch eigentlich egal,
aber wenn du z.B. noch "links" einführst, dann kannst da ganz schnell arbeiten, da von dem Object auf alle nötigen Elemente direkt zugegriffen werden kann. ansonsten bleibt dir wohl nix anderes übrig, außer (im Notfall) die ganze Liste durchzugehn :?
Delphi-Quellcode:
head entspricht hier wohl dem Owner
TComp = Record/Object
... Owner: ...; Prev, Next: PComp; End; If Comp.Owner.FirstComp = Comp Then Comp.Owner.FirstComp := Comp.Next; If Assigned(Comp.Prev) Then Comp.Prev.Next := Comp.Next; If Assigned(Comp.Next) Then Comp.Next.Prev := Comp.Prev; Comp.Free; |
Re: Löschen eines Elementes in einer einfachen Liste
head entspricht wahrscheinlich dem ersten Listenelement (irgendwo muss man ja anfangen, sich durchzuhangeln).
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:43 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz