Knoten aus LinkedList löschen

mathon

Hallo,

ich habe mir gedacht, dass ich dafür einen eigenen Thread aufmache weil es sich um ein spezifisches problem handelt. Ich habe jetzt allen notwendigen Methoden für die LinkedList implementiert und sie auch ausreichend getestest. Das einzige wo ich noch einen Fehler bekomme ich beim Löschen von Knoten. Meine remove-Methode sieht derzeit so aus:

void sequence::remove_current( )
{
	if(!(is_item()))
		return;

	node *target_ptr;

	if(cursor != tail_ptr && many_nodes > 1)
	{
		cout << "Cursor != tail_ptr" << endl;
		target_ptr = cursor;
		cursor = cursor->link();
		precursor->set_link(cursor);
		delete target_ptr;
		node* cursor1;
		node* precursor1;
		for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
		{
			precursor1 = cursor1;
		}
		tail_ptr = precursor1;
		--many_nodes;
		return;
	}

	else if(cursor == tail_ptr)
	{
		delete cursor;

		--many_nodes;
		return;
	}
	else if (many_nodes == 1)
	{
		list_head_remove(head_ptr);
		start();
		--many_nodes;
		return;
	}
}

Also ich habe das dreigeteilt - wenn ein Knoten mitten in der Liste gelöscht werden soll, wenn es sich um den letzten Knoten der Liste handelt oder wenn nur mehr ein Knoten in der Liste vorhanden ist. Leider habe ich Probleme bei dem zweiten Fall wo der letzte Knoten der Liste gelöscht werden soll. Der Fehler tritt auf bei dem Statement
delete cursor;

Fehler:
Debug Assertion Failed!
Program: ...
File: dbgdel.cpp
Line: 52

Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse)

For information on how your program can cause an assertion failure, see the Visual C++ documentation on asserts.

Wieso lässt er mich nicht einfach mit delete den letzten Knoten der Liste löschen? - weiß jemand wie das korrekt definiert gehört?

matti

PS: Ja der cursor pointer zeigt immer auf den aktuellen Knoten in der Liste, der precursor auf den Knoten vor dem auf den der pointer zeigt. tail_ptr zeigt immer auf den letzten Knoten in der Liste.

Kuldren

Sentinels?
...->Also zwei Fixe Anfangs und Endknoten?
Dann löscht du nur Knoten in der Liste also bei dir der erste Fall...

Vorweg ein paar Dinge die mit dem eigentlichen Problem nix zu tun haben, aber dir (und anderen) die Arbeit an dem Programm erleichtern könnten:

Kennzeichne Membervariablen irgendwie. Üblich ist "m_name", aber du kannst auch was anderes verwenden. Verwirrend ist nur wenn du für alles (Klassen, Funktionen, Member, Parameter, Locals) die "klein geschrieben, mit Underscores zum Trennen, ohne Prefix" Variante verwendest.
Kennzeichne Klassennamen irgendwie. Muss nicht sein, hilft aber. Viele C++ Programme/Libs verwenden "CamelCase" (mit grossem Anfangsbuchstaben) für Klassen und Funktionen und "camelCase" (mit kleinem Anfangsbuchstaben) für Variablen.
Verwende beschreibende Namen. Tust du schon fast, aber "many_nodes" sollte vielleicht doch besser "node_count" oder eben "m_nodeCount" heissen. Ich musste erst an ein paar Stellen gucken um draufzukommen für was "many_nodes" steht.

So. Nu ein paar Sachen zu der Liste/dem Code selbst.
0) Mit so unnvollständigem Code machst du dich unbeliebt

Willst du wirklich eine single-linked-list machen? Eine double-linked-list ist im Allgemeinen wesentlich einfacher, und darüberhinaus noch schneller beim Einfügen/Löschen/Rückwärts-Steppen.
Willst du wirklich die Listen-Klasse und den Iterator darauf in eine Klasse zusammenwursteln?

So. Nu zu deinem Code (Kommentare im Code):

void sequence::remove_current( )
{
    if(!(is_item()))
        return;

    node *target_ptr;

    if(cursor != tail_ptr && many_nodes > 1)
    {
        cout << "Cursor != tail_ptr" << endl;
        target_ptr = cursor;
        cursor = cursor->link(); // cursor auf nächste node stellen
        precursor->set_link(cursor); // "next" link in der node vor der alten cursor-position "fixen"
        delete target_ptr; // node an der alten cursor position löschen
        // soweit, so gut. alles was jetzt kommt halte ich für schwachsinn :)
        // kannst du bis auf "many_nodes--" alles wegtun
        node* cursor1;
        node* precursor1;
        // hier suchst du die letzte node - keine ahnung wozu
        for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
        {
            precursor1 = cursor1;
        }
        // hier setzt du nun tail_ptr neu, aber der wert wird sich nicht geändert haben.
        tail_ptr = precursor1;
        --many_nodes; // ok, das brauchen wir wieder
        return;
    }

    else if(cursor == tail_ptr)
    {
        delete cursor;
        // du musst hier den "link" vom vorletzten knoten auf 0 setzen
        // und dann tail_ptr und precursor entsprechend anpassen
        --many_nodes;
        return;
    }
    else if (many_nodes == 1)
    {
        list_head_remove(head_ptr);
        start();
        // ob nach start() noch "many_nodes--" kommen soll oder darf ... kann ich aus dem code-schnipsel nicht erraten. sieht aber komisch aus.
        --many_nodes;
        return;
    }
}

Oder probier einfach mal so:

void sequence::remove_current( )
{
    if(!(is_item()))
        return;

    if((many_nodes == 0) || (cursor == 0))
        return;

    node* next_node = cursor->link();
    if(cursor == head_ptr)
    {
        // precursor muss 0 sein, dafür müssen wir "head_ptr" fixen:
        assert(precursor == 0);
        head_ptr = next_node;
    }
    else
    {
        assert(precursor != 0);
        precursor->set_link(next_node);
    }

    // element löschen und cursor aufs nächste element setzen
    delete cursor;
    cursor = next_node;

    if(cursor == 0)
    {
        // wir haben das letzte element gelöscht.
        // jetzt müssen wir wohl tail_ptr anpassen:
        tail_ptr = precursor;
        // wo sollen wir jetzt cursor hinsetzen? da es kein element nach
        // dem gelöschten mehr gibt setzen wir den cursor einfach ungültig.
        // 'cursor' ist schon 0, fehlt nur noch precursor:
        precursor = 0;
    }

    --many_nodes;
    if(many_nodes == 0)
    {
        // liste ist jetzt leer
        start();
    }
}

Da ich aber die "Randbedingungen" deiner Impl. nicht kenne kann ich nicht sagen ob das so passt. Also z.B. wo zeigt "precursor" hin wenn "cursor == head_ptr". Oder wo soll "cursor" hinzeigen nachdem man das letzte Element gelöscht hat? Solche Dinge.

Tip: mach eine Ringliste. Ringlisten sind schnell und schön und toll und überhaupt. Oder verwende die von Kuldren vorgeschlagenen Sentinels. Oder mach zumindest eine double-linked-list draus.

mathon

super danke, das hat funktioniert. ich hätte vielleicht noch ein paar fragen zu deiner version:

1)Du hast hier diese Zeile geschrieben

node* next_node = cursor->link();

Das heiß next_node soll auf den nächsten Knoten also dem Knoten nach dem cursor zeigen. Aber wenn jetzt die Liste nur einen Knoten hat und cursor auf diesen zeigt, dann kann next_node ja nicht auf den nächsten Zeigen weil es keinen nächsten gibt, dann müsste doch ein fehler geworfen werden oder?

2)Du schreibst in dem einen if

head_ptr = next_node;

und im else zweig

precursor->set_link(next_node);

Könnte ich da im else-zweig nicht auch das statt des oberen statements schreiben?

precursor = next_node

Äh. Hab ich ein Posting/einen Thread übersehen wo du schreibst dass es sich um eine Hausübung handelt oder sowas?!?

Ich verstehe einfach nicht wie man eine single-linked-list implementieren kann (die bis auf die remove Funktion anscheinend auch funktioniert) und dann diese Fragen stellen... *grübel*

mathon

Nein hast du nicht, aber wie du siehst hat es leider funktioniert...ich habe auch dazu ein buch verwendet wo ich ein paar sachen übernehmen konnte...

könntest du mir vielleicht trotzdem diese fragen beantworten, auch wenn sie für dich lächerlich erscheinen...?

matti

ad 1: wenn es funktioniert, dann wird cursor->link() wohl 0 zurückliefern wenn es keinen weiteren Knoten mehr gibt. Da der Rest des Codes nicht nur damit klarkommt sondern auch erwartet dass das passiert... funktioniert es eben.

ad 2: nein. nein-nein-nein-nein. precursor ist der ZEIGER auf die "node vor dem cursor". precursor = next_node würde den ZEIGER namens "precursor" auf eine andere Node zeigen lassen. precursor->set_link(next_node) tut etwas anderes.

p.S.: das "precursor = 0" im "if(cursor == 0)" kannst du im übrigen streichen, das darf eigentlich nie notwendig sein.

mathon

ad 2: nein. nein-nein-nein-nein. precursor ist der ZEIGER auf die "node vor dem cursor". precursor = next_node würde den ZEIGER namens "precursor" auf eine andere Node zeigen lassen. precursor->set_link(next_node) tut etwas anderes.

Ich mein es ist ja schön, dass dies was anderes macht, nur würde ich halt auch gerne wissen, was es dann anderes macht? - denn für micht wird damit mit set_link der precursor pointer auf den next_node gesetzt....was macht dieses nun anderes, als precursor = next_node...??

Oh Mann...

Also. Ich bin "precursor", ein Zeiger. Ich stehe rum und zeige mit dem Finger auf ... ein Haus. Als Zeiger ist das schliesslich mein Job. Das Haus ist "irgendeine node". Es ist grün. In dem Haus steht ... Reinhold Messner. Reinhold Messner ist auch ein Zeiger. Er tut auch seinen Job - er zeigt aus dem Fenster auf ein anderes Haus, wir wissen aber nicht auf welches. Reinhold Messner ist "link". Neben mir steht dann noch Nina Hagen, sie ist auch ein Zeiger, und sie zeigt auf ein kleines rotes Haus. Nina Hagen ist "next_node". Nina Hagen und ich stehen übrigens in einem grossen Autobus der Marke "sequence".

Du bist "die CPU", ein Aktionskünstler mit seltsamem Namen, und der Angewohnheit seltsame Dinge zu tun wie Leuten die Hand zu verdrehen.
Wir alle spielen ein Stück.

---

Bühnenstück: precursor->set_link(next_node);

Du kommst zu mir, guckst mich schief an und siehst dass ich auf ein grünes Haus zeige. Du guckst Nina Hagen an und siehst dass sie auf ein kleines rotes Haus zeigt. Du merkst dir beides. Du setzt dir eine Kappe der Marke "set_link" auf. Du gehst in das grüne Haus. Ende 1. Akt.
2. Akt: Du suchst und findest Reinhold Messner, und verdrehst seine Hand so dass er nun auch, gleich wie Nina Hagen, auf das kleine gelde Haus zeigt. Du verlässt das grüne Haus wieder.
Ich zeige nach wie vor auf das grüne Haus, Reinhold Messner zeigt aber auf das kleine rote Haus. Nina Hagen singt vor sich hin.
Vorhang, Applaus, Ende.

---

Bühnenstück: precursor = next_node;

Du kommst zu mir, guckst garnicht was ich so macht, sondern guckst Nina Hagen an. Du siehst dass sie auf ein kleines rotes Haus zeigt, und verdrehst meine Hand so dass ich auch auf das kleine rote Haus zeige.
Ich zeige jetzt auf das kleine rote Haus, Reinhold Messner zeigt aber immernoch dorthin wo immer er auch zu beginn des Stückes hingezeigt hat Haus. Nina Hagen tanzt.
Vorhang, Buh-Rufe, Ende.

---

Anders gesagt ... der Unterschied ist:

precursor->set_link(next_node)
// ist gleichbedeutend mit
precursor->link = next_node;

dagegen:

precursor = next_node;

ist (und macht) eben ganz was anderes.
Wie um alles in der Welt kann man diesen Unterschied nicht verstehen?

BTW: die Rollenverteilung zu Beginn unseres Stückes:

Grosser Autobus:        "(*this)"             Typ: 'sequence'
    "Ich":              "precursor"           Typ: Zeiger auf 'node'
    Nina Hagen:         "next_node"           Typ: Zeiger auf 'node'

Grünes Haus:            "(*precursor)"        Typ: 'node'
    Reinhold Messner:   "(*precursor).link"   Typ: Zeiger auf 'node'

Kleines rotes Haus:     "(*next_node)"        Typ: 'node'
    uncredited          "(*next_node).link"   Typ: Zeiger auf 'node'

Nu lies es nochmal von vorne.

Wenn dus dann noch nicht verstanden hast dann lass es dir von jmd. anderem erklären oder hänge C++ und das Programmieren an den Nagel.

Kuldren

Oh Mann...

Also. Ich bin "precursor", ein Zeiger. Ich stehe rum und zeige mit dem Finger auf ... ein Haus. Als Zeiger ist das schliesslich mein Job. Das Haus ist "irgendeine node". Es ist grün. In dem Haus steht ... Reinhold Messner. Reinhold Messner ist auch ein Zeiger. Er tut auch seinen Job - er zeigt aus dem Fenster auf ein anderes Haus, wir wissen aber nicht auf welches. Reinhold Messner ist "link". Neben mir steht dann noch Nina Hagen, sie ist auch ein Zeiger, und sie zeigt auf ein kleines rotes Haus. Nina Hagen ist "next_node". Nina Hagen und ich stehen übrigens in einem grossen Autobus der Marke "sequence".

Du bist "die CPU", ein Aktionskünstler mit seltsamem Namen, und der Angewohnheit seltsame Dinge zu tun wie Leuten die Hand zu verdrehen.
Wir alle spielen ein Stück.

---

Bühnenstück: precursor->set_link(next_node);

Du kommst zu mir, guckst mich schief an und siehst dass ich auf ein grünes Haus zeige. Du guckst Nina Hagen an und siehst dass sie auf ein kleines rotes Haus zeigt. Du merkst dir beides. Du setzt dir eine Kappe der Marke "set_link" auf. Du gehst in das grüne Haus. Ende 1. Akt.
2. Akt: Du suchst und findest Reinhold Messner, und verdrehst seine Hand so dass er nun auch, gleich wie Nina Hagen, auf das kleine gelde Haus zeigt. Du verlässt das grüne Haus wieder.
Ich zeige nach wie vor auf das grüne Haus, Reinhold Messner zeigt aber auf das kleine rote Haus. Nina Hagen singt vor sich hin.
Vorhang, Applaus, Ende.

---

Bühnenstück: precursor = next_node;

Du kommst zu mir, guckst garnicht was ich so macht, sondern guckst Nina Hagen an. Du siehst dass sie auf ein kleines rotes Haus zeigt, und verdrehst meine Hand so dass ich auch auf das kleine rote Haus zeige.
Ich zeige jetzt auf das kleine rote Haus, Reinhold Messner zeigt aber immernoch dorthin wo immer er auch zu beginn des Stückes hingezeigt hat Haus. Nina Hagen tanzt.
Vorhang, Buh-Rufe, Ende.

Ok...Ich hab keine Ahnung wie lange es her ist dass ich SO gelacht habe

Mist! Das "kleine gelde Haus" muss natürlich das kleine ROTE Haus sein. Hatte erst grün und gelb -- gelb dann aber auf rot geändert weil grün und gelb sich so ähnlich sind - farblich so wie sprachlich. Sch*** Tippfehler!

mathon

danke jetzt habe ich es verstanden!...sorry für die ausführliche erklärung...:( anscheinend sollte ich das programmieren an den nagel hängen..

trotzdem danke nochmal für die erklärung!

lg matti

hustbaer

Nu mal Kopf hoch, wenn du's nicht verstanden hättest hiess es