Element aus der verketteten Liste entfernen

Namal

Hallo,

Ich habe eine verkettete Liste, bei der die Wörter an das Ende angehängt werden. Nun möchte ich ein Wort aus der Liste Löschen und habe das hier gefunden
http://perlgeek.de/de/artikel/einfach-verkettete-listen

Allerdings wenn ich es versuche umzusetzen

void Delete (Elem * &Anker, const string &wort){

for (Elem *h=Anker;h!=NULL; h=h->next)
		if ((*h).wort==wort){
			h = Anker->next;
			Anker->next = Anker->next->next;						

			delete h;
		}
}

Werden auch alle vorherigen Wörter bis auf das erste Element gelöscht. Was mache ich falsch

Nathan

-> http://www.cplusplus.com/reference/forward_list/forward_list/
und
-> http://www.cplusplus.com/reference/list/

Namal schrieb:

Hallo,

Ich habe eine verkettete Liste, bei der die Wörter an das Ende angehängt werden. Nun möchte ich ein Wort aus der Liste Löschen und habe das hier gefunden
http://perlgeek.de/de/artikel/einfach-verkettete-listen
[...]
Werden auch alle vorherigen Wörter bis auf das erste Element gelöscht. Was mache ich falsch

Moin!
Nimm Dir Papier und Bleistift, und mal die Liste mal auf. Überleg Dir wie z.B. Anker(wenn überhaupt) sich ändert, wenn angehängt wird. Und was Du tun musst um ein Element auszuhängen.
Ausserdem würde ich die Vorgänge Aushängen und Suchen trennen.

Glückauf!

Namal

Na meine Liste wird so erzeugt

Elem * h= new Elem;
	(*h).wort=wort;
	(*h).next=NULL;

	if(Anker == NULL)
  	Anker = h;   
	else{
		Elem *e = new Elem;
		e = Anker;
		while(e->next!=NULL){
			e=e->next;
		}

		e->next=h;

Das erste Element wird vor den NULL Zeiger gesetzt und alle weiteren werden nach vorne bis zu dem NULL Zeiger geschoben.

Das entfernen des ersten Elementes habe ich so geschafft.

if((*Anker).wort==wort)
    Anker = (*Anker).next;

Aber wenn es mitten in der Liste ist, dann muss ich doch den next Zeiger des vorherigen Elementes durch den next Zeiger des zu entfernenden Elements ersetzen? Doch wie mach ich das, ich kann ja nicht wie bei den Vektoren einfach zurückgehen.

Swordfish

...

Namal

Swordfish schrieb:

Zeile 8 würd' ich überdenken ...

so?

Elem *e = Anker;

Namal schrieb:

Aber wenn es mitten in der Liste ist, dann muss ich doch den next Zeiger des vorherigen Elementes durch den next Zeiger des zu entfernenden Elements ersetzen? Doch wie mach ich das, ich kann ja nicht wie bei den Vektoren einfach zurückgehen.

Stimmt, Du kannst nicht zurückgehen, wenn Du also beim iterieren auf dem Element landest, dass Du löschen willst, bist Du schon eins zu weit. In Deinem usrprünglichen Code ist also zu prüfen, ob h->next.wort == wort um dann den Knoten h->next auszuhängen.

In Anbetracht dessen ist wahrscheinlich auch mein Vorschlag, suchen und aushängen zu trennen unsinnig, es sei denn suchen() gibt den Knoten vor dem gesuchten aus...

Namal

Ich glaube ich habe es gelöst und mir ist ein Licht aufgegangen, deshalb frag ich nochmal nach.

Elem * temp = NULL;
	for(Elem *h=Anker;h!=NULL; h=h->next){
		if(h->wort!=wort)
	  	Append(temp,(*h).wort); 
    else
        delete h;
	}

	Anker = temp;

Wobei durch Append einfach eine neue Liste erstellt wird.

Ist es nun richtig, dass durch Zeile 6 dieses Element aus dem Speicher gelöscht wird?

camper

Furble Wurble schrieb:

In Anbetracht dessen ist wahrscheinlich auch mein Vorschlag, suchen und aushängen zu trennen unsinnig, es sei denn suchen() gibt den Knoten vor dem gesuchten aus...

Interessant ist nicht der vorherige Knoten, sondern der Zeiger, der den gesuchten Knoten besitzt. Der liegt ja ggf. nicht selbst in einem Knoten, wenn es um den Listenanfang geht. Also ungefähr

Elem*& find(Elem*& Anker, const string& wort) {
    Elem** p = &Anker;
    while ( *p && (*p)->wort != wort )
        p = &(*p)->next;
    return *p;
}

void Delete (Elem * &Anker, const string &wort) {
   if ( Elem*& p = find( Anker, wort ) ) {
       Elem* q = p;
       p = p->next;
       delete q;
   }
}