listen (kopfzerbrechend)
-
moinsen, ich hab da mal ein problem, mit listen...
ich möchte aus einer liste einen eintrag löschen ( unterscheidung auf die eigenschaften der liste(einziges element, letztes, erstes,garkeins).
dat* dat::del() { dat *tmp = NULL; if(prev == NULL & next != NULL) { } if(prev == NULL & next == NULL) { } if(prev != NULL & next != NULL) { } if(prev != NULL & next == NULL) { } }jedoch fällt mir das handhaben von listen nicht gerade leicht
könnt ihr mir helfen??
-
Es macht sich immer gut, wenn man sich die einzelnen Fälle mit Papier und Bleistift klarmacht. Paar Kästchen und Pfeile malen, vorher - nachher, und dann passt das.
-
Morgen,
------- ------- ------- ------- ------- |elem1| -> |elem2| -> |elem3| -> |elem4| -> |elem5| ------- | ------- | ------- | ------- | ------- | next| -- | next| -- | next| -- | next| -- | next| ------- ------- ------- ------- ------- | prev| <- | prev| <- | prev| <- | prev| <- | prev| ------- ------- ------- ------- -------Nun, wie du siehst, kann man jetzt schon sehr leicht erkennen, wie die Liste
arbeitet. Was muessen wir also machen, wenn wir elem3 loeschen wollen?Das ist ganz einfach, zu erst einmal machen wir uns eine temp-Variable, welche
auf elem3 zeigt:------- ------- |temp | --> |elem3| ------- ------- | next| | next| ------- ------- | prev| | prev| ------- -------Nun duerfen next von elem2 und prev von elem4 nicht mehr auf elem3 zeigen, da
wir elem3 loeschen wollen:---------------------- | \|/ ------- ------- | ------- ------- ------- |elem1| -> |elem2| | |elem3| -> |elem4| -> |elem5| ------- | ------- | ------- | ------- | ------- | next| -- | next| -- | next| -- | next| -- | next| ------- ------- ------- ------- ------- | prev| <- | prev| <- | prev| --| prev| <- | prev| ------- ------- ------- | ------- ------- /|\ | |----------------------Man sieht jetzt sehr schoen, dass das naechste Element nach elem2 elem4 ist
und das Vorgaengerelement von elem4 ist jetzt elem2. Wir haben die noetige
Arbeit getan und koennen nun elem3, welches wir zuvor in einer temp-Variablen
gespeichert haben oder, richtiger gesagt, die temp-Variable auf elem3 haben
zeigen lassen, loeschen.Die Liste sieht jetzt so aus:
------- ------- ------- ------- |elem1| -> |elem2| -> |elem4| -> |elem5| ------- | ------- | ------- | ------- | next| -- | next| -- | next| -- | next| ------- ------- ------- ------- | prev| <- | prev| <- | prev| <- | prev| ------- ------- -------- -------Ich liebe Ascii-Zeichnungen
mfg
v R
-
ok, ich denke jetzt hab ich es
aber ob das alles so richtig ist
dat* dat::del() { dat *temp = NULL; if(prev == NULL & next != NULL) { temp = next; next->prev = NULL; delete this; return(temp); } if(prev == NULL & next == NULL) { delete this; return(NULL); } if(prev != NULL & next == NULL) { temp = prev; prev->next = NULL; delete this; return(temp); } if(prev != NULL & next != NULL) { temp = next; prev->next = next; next->prev = prev; delete this; return(temp); } }
-
nur & durch && ersetzen.
-
ups
thx
-
KoF schrieb:
jedoch fällt mir das handhaben von listen nicht gerade leicht
könnt ihr mir helfen??ja.
böse sind die fallunterscheifungen. also die ifs. die müssen weg. alle.bisher machst du ne doppelt verkettete liste. die hat einen anfang und ein ende. manchmal sind anfang und ende auch gleich. und manchmal sind beide nicht da.
Plan A): mach zuerst mal einen ring daraus. und kümmere dich nicht darum, daß der ring leer sein könnte. nimm einfach an, es würde immer mindestens ein element geben. und du hast in der liste nicht mehr anfangs- und end-zeiger, sondern nur noch einen zeiger auf den ersten ringknoten.
der code wird so ähnlich wie
static void Ring::del(Node* toDel)
{
toDel->prev=toDel->next->prev;
toDel->next=toDel->prev->next;
delete toDel;
}Plan B): lass deine liste immer einen knoten besitzen, der halt unbenutzt ist. damit kannst garantieren, daß die liste nie leer wird. und hast bereits 0 fallunterscheidungen für löschen eines beliebigen knotens, einfügen am anfang und einfügen am ende.
Plan C): mach ne klasse für knoten (die verlinkungszeiger und die daten) und ne klasse für leere knoten (nur die verlinkungszeiger). lass die dicke klasse von der kleinen klasse erben.
Plan D): hau an geeigneten stellen static_cast in den code, damit der unbenutze knoten der liste ein kleiner knoten sein darf.