Frage C++ einfach verkettete Liste

T3c4n01d · 15. August 2005

Wie lösche ich in einer einfach verketteten Liste?

ich habe die Liste wie folgt angelegt:

struct S{...};

struct Knoten{

S Inhalt;
Knoten *next;};

struct G{
int akt;
Knoten *anker;};

typedef Knoten* Position;

//...

void entfernen(G & g, Position p){

for (p;p->next!=0;p=p->next){

p->Inhalt=p->next->Inhalt;}

Aber irgendwie muss ich dann ja noch den Speicherplatz am Ende der Liste wieder freigeben... bloss wie? Oder gibts da eine ganz andere Lösung?

MfG

Anzeige

kain0015 · 15. August 2005

free(p);
bzw.
free(p->next);

jenachdem wie du's brauchst. sollte so funzen.
mfg

T3c4n01d · 16. August 2005

Nein das funzt leider nicht.

Problem bei dem Code ist, dass zwar der Inhalt verschoben wird, aber der letzte Platz nicht wieder freigegeben wird.

die Ausgabe sieht dann folgendermaßen aus:

vor entfernen des 2. Knotens:

Data1 2 2
Data2 3 4 <-hier ist der 2. Knoten
Data3 4 3
Data4 4 5

(die Zahlen haben hier nur Inhaltliche Bedeutung)

nach entfernen:

Data1 2 2
Data3 4 3
Data4 4 5
Y3)Y3( 0 0 <-hier liegt das Problem.

leg ich einen neuen Knoten an, dann wird das als Inhalt betrachtet.

die ausgabe sieht dann so aus:

Data1 2 2
Data3 4 3
Data4 4 5
Y3)Y3( 0 0
Data5 3 3

Any Hints?

kain0015 · 20. August 2005

aso meinst.
erst musst ne temp variable von dem typ, von dem auch deine andern Daten sind (int, oder halt deine eigene struktur).
dann wenn du vor dem zu löschenden bist (das zu löschende is p->next):
temp = p->next;
p = temp->next;
free(temp);

wenn ichs richtig verstanden hab müsste es so funzen.
mfg

T3c4n01d · 21. August 2005

Knoten* tmp;

tmp=p->next;
p->next=p->next->next;
free(tmp);

wenn ich so mache siehts schon ganz gut aus. Problem ist nur dass dann der Nachfolger gelöscht wird.

Schreib ichs so:

Knoten* tmp;

tmp=p;
p=p->next;
free(tmp);

dann gibts einen Zuordnungsfehler.

THX4Help.

10er hast du.

MfG

kain0015 · 21. August 2005

also bin jetzt bissl verwirrt
bei deiner funktion
void entfernen(G & g, Position p){ ... }
ist da das Position p das was du löschen willst? (und für was brauchst das g?)
und hast bevor du p an die funktion übergibst überprüft ob es p überhaupt gibt?
Weil normalerweise, wenn p das zu löschende element ist, und du weist das es existiert, müsste es so wie du geschrieben hast funzen:

tmp=p;
p=p->next;
free(tmp);

nur musst danach halt noch restlichen elemente nach vorne verschieben.

T3c4n01d · 22. August 2005

g wird eigentlich nur übergeben um die Variable g.akt zu verändern. Also die aktuelle Anzahl der Knoten.

Wenn ich jetzt auf den Vorgänger mittels Schleife springen könnte wärs ja gar nicht so schlecht.

dachte da an :

Position i;
for(i=g.anker;i->next=p;i=i->i->next);

p=i;
tmp=p;
p=p->next;
free(tmp);

nur dann wird immer die erste Position gelöscht. Da haut wohl was mit der Schleife nicht hin?!

Oder liegts an der Ausgabefunktion?

//...
P anfang(G g){return g.anker->next;}

P ende(G g){
P i; for(i=g.anker;i->next!=0;i=i->next);
return i;}

P naechste(G g, P p){
return p->next;
}
//...
void katalog(G g)
{ for(P p=anfang(g); p!= ende(g); p=naechste(g, p) )
{ S t;

t=lesen(g, p);
printS(t);

kain0015 · 22. August 2005

irgendwie verwirrst du mich immer mehr
aber mir is grad was aufgefallen.
Bei deiner funktion:
void entfernen(G & g, Position p)
ist das g nur dazu da um die anz. der knoten zu ändern.
Jetzt hab ich ne Frage: Zeigt Position p auf den Knoten den du löschen willst, oder ist p die liste, aus der du was löschen willst??
Weil irgendwas fehlt da... ersteres würde sinn ergeben wenn du irgendwo ne liste global angelegt hast.
Zweitest ergibt für mich gar keinen sinn, weil du dann net weist welches du löschen willst.
Also klär mich bitte nur mal über die Parameter deiner Funktion auf, sonst kann ich mir irgendwie kein bild vom ganzen machen
Edit: hast du msn oder icq?? Wenn ja schreib pn. So könnten wir dass ganze in 10 min lösen.
mfg

T3c4n01d · 23. August 2005

So ich habs jetzt.

void entfernen(G & g, P p) {

KN* tmp=new KN;
P i;
if (p->next==g.anker->next->next){

g.anker->next=p->next;

}
else{
for(i=anfang(g);i->next->next!=p->next;i=naechste(g,i));
p=i;

tmp=p->next;
p->next=p->next->next;}
free(tmp);
g.akt--;

}

Wer eventuell noch eine elegantere Lösung kennt der kann sie ja noch posten.

Big THX an kain0015 für die Unterstützung.

MfG

Nützliche Suchen

Frage C++ einfach verkettete Liste

Videos zum Themenbereich