Objekt-Attribute ändern sich

Random123

Hallo,

ich bin Umsteiger nach C++ (von C#) und wollte mich nun mal dran probieren eine verkettete Liste zu schreiben. Die Klasse List hat das Attribut first, welches vom Typ ListNode* ist. ListNode hat die Attribute next (ebenfalls ListNode*) und value (int) zum Speichern der Inhalte. Nun habe ich mich ans Einfügen von Werten gemacht:

void List::add(int value)
{
	if(!first)
		first = &ListNode(value);
	else
	{
		ListNode* tmp = first;
		while(tmp->next != NULL)
			tmp = tmp->next;
		tmp->next = &ListNode(value);
	}
}

'first' wird absolut richtig belegt.
Wenn ich jetzt aber noch ein Element hinzufügen will (sprich das Programm springt in den else-Zweig mit der Schleife), hat first plötzlich einen anderen Wert bei 'value', und 'next' ist 0xcccccccc. Per Google hab ich schon herausgefunden, dass es öfters mal Probleme damit gibt, eine Lösung aber nicht.

Woran liegt es also nun, dass first sich ändert? Sollte man für Attribute überhaupt Pointer verwenden (in C# sind Klassen ja automatisch Referenztypen, man braucht sowas also nicht)?

MfG
Random123

314159265358979

Random123 schrieb:

first = &ListNode(value);
'first' wird absolut richtig belegt.

Autsch. Leider nein. Du erzeugst ein temporäres Objekt, dessen Adresse du in first ablegst, danach wird das Objekt zerstört und du has einen dangling pointer.

cooky451

Das wäre auch in C++ ein Fall für new. Am besten zusammen mit unique_ptr, aber zum üben geht's auch ohne. (Man würde ja eh std::list nutzen in echtem Code.)

krümelkacker

Random123 schrieb:

first = &ListNode(value);

Das ist kein Standard-C++. Das sage ich unter der Annahme, dass Du den Adressoperator nicht für die Klasse überladen hast. ListNode(value) erzeugt nämlich ein temporäres Objekt was mit dem Semikolon wieder verschwindet. Dass das hier mit dem Adressoperator überhaupt funktioniert hast Du Microsoft zu verdanken; denn die hielten das für eine voll dufte Idee, dass man sich die Adresse eines temporären Objekt holen kann. Sie bieten das als "Erweiterung" an, eine Erweiterung die eher sinnfrei und gefährlich ist. Man kann diesen Schmarn auch abschalten. Allerdings weiß ich nicht, ob dann auch all die anderen viel nützlicheren C++11-Features deaktiviert werden. Ich habe nicht so viel Erfahrung mit diesem Compiler.

Random123

Hallo und vielen Dank!

So funktioniert es nun:

void List::add(int value)
{
	if(!first)
		first = new ListNode(value);
	else
	{
		ListNode* tmp = first;
		while(tmp->next != NULL)
			tmp = tmp->next;
		tmp->next = new ListNode(value);
	}
}

Nun habe ich noch eine weitere Frage, und zwar folgende: Wenn ich einem ListNode beim erstellen gleich seinen Nachfolger mitgeben will (per Konstruktor), sollte ich dann nur das Objekt, einen Pointer drauf oder eine Referenz übergeben?

314159265358979

Du musst die Knoten übrigens im Destruktor auch löschen, nur falls du das nicht weißt.

pumuckl

Random123 schrieb:

Nun habe ich noch eine weitere Frage, und zwar folgende: Wenn ich einem ListNode beim erstellen gleich seinen Nachfolger mitgeben will (per Konstruktor), sollte ich dann nur das Objekt, einen Pointer drauf oder eine Referenz übergeben?

Also

Das Objekt übergeben geht schonmal nicht. Du kannst als Funktionsparameter nur Pointer, Referenzen oder aber Kopien übergeben. Nie das Objekt selber. Am nächsten käme da eine Referenz heran.
Eine Referenz ginge, da allerdings erstens der Nachfolger im Knoten per Pointer gehalten wird und zweitens es nicht unbedingt einen Nachfolger geben muss, würde ich am ehesen zu 3) tendieren:
Per Pointer. Damit kannst du sowohl den Fall "hat einen nachfolger" als auch "hat keinen Nachfolger" erschlagen:

ListNode::ListNode(int value, ListNode* nex = NULL);

Random123

Danke pumuckl, dann mach ich es mit einem Pointer.

Random123

Hallo,

ich hab nochmal eine Frage beim entfernen (folgender Code funktioniert, hat aber keine delete):

int List::removeAt(int index)
{
	int value = 0;
	if(index == 0)
	{
		value = first->value;
		first = first->next;
	}
	else
	{
		ListNode* pre = first;
		while(index > 1)
		{
			pre = pre->next;
			index--;
		}
		value = pre->next->value;
		pre->next = pre->next->next;
	}

	length--;
	return value;
}

Ich will ein ListNode, das irgendwo in der Mitte (bzw. auch am Anfang oder Ende) liegt löschen. Sprich: Der Vorgängers des zu löschenden Knoten soll als Nachfolger den Nachfolger des zu löschenden Knotens bekommen, sodass ich den zu löschenden Knoten auch wirklich löschen kann (delete). Wenn ich das tue, wird aber auch dessen Nachfolger entfernt (anscheinend, liege ich damit richtig?). Selbst wenn ich den Pointer auf den Nachfolger des zu löschenden Knotens nicht direkt übernehme, sondern einen neuen erstelle funktioniert das nicht. Wie also macht man das?

Ich hoffe ihr konntet meine Sätze verstehen

MfG Random123

camper

Random123 schrieb:

Wenn ich das tue, wird aber auch dessen Nachfolger entfernt (anscheinend, liege ich damit richtig?).

Wissen wir nicht. Das hängt davon ab, wie du ListNode geschrieben hast. Falls jeder seinen Nachfolger besitzt und im Destruktor zerstört, wirst du vor dem Löschen eines einzelnen Knotens offensichtlich den Zeiger auf den Nachfolger auf 0 setzen müssen.
Übrigens ist es eleganter, über die Zeiger auf den Folgeknoten zu iterieren statt über die Knoten selbst. Auf diese Weise entfällt das Löschen des Anfangs als Spezialfall. Also ungefähr so

int List::removeAt(int index)
{
    ListNode** link = &first;
    for ( int i = 0; i != index; ++i ) // Halte ich persönlich für leichter lesbar als index zu dekrementieren - wenn du das Ganze auf Papier machst, zählst du ja wahrscheinlich auch nicht rückwärts
    {
        assert( *link != nullptr );
        link = &(*link)->next;
    }
    ListNode* node = *link;
    assert( node != nullptr );
    *link = node->next;    // Knoten isolieren
    node->next = nullptr;  // ggf. notwendig, s.o.
    int value = node->value;
    delete node;
    --length;
    return value;
}

Random123

Danke camper,
dein Code funktioniert, und ich glaube ich bin auch dahintergekommen, wie.

In Zeile 11 von deinem Code manipuliere ich einen Pointer, der auch ein Next-Pointer eines Knotens ist (außer index ist 0). Habe ich das richtig verstanden?

Vielen Dank,
Random123