Element vorher einfügen?

camper

vip@r schrieb:

Der "überflüssige Zeiger" ist der, der vor dem Umbiegen von B nach D gezeigt hat. Das hab ich schlecht ausgedrückt, sorry!

und jetzt auf C zeigt, und das ist ja keineswegs überflüssig.
Schematisch sieht das Ganze ungefähr so aus

Ausgangssituation:
!------------------!                  !------------------!
!         B        !                  !         D        !
!------------------!                  !------------------!
!  val    !  next  !----------------->!  val    !  next  !
!------------------!                  !------------------!

----------------------------------------------------------
1. Schritt: Node* c = new Node

!------------------!                  !------------------!
!         B        !                  !         D        !
!------------------!                  !------------------!
!  val    !  next  !----------------->!  val    !  next  !
!------------------!                  !------------------!

                   !------------------!
                   !         C        !
                   !------------------!
                   !         !        !
                   !------------------!

----------------------------------------------------------
2. Schritt: c->val = x

!------------------!                  !------------------!
!         B        !                  !         D        !
!------------------!                  !------------------!
!  val    !  next  !----------------->!  val    !  next  !
!------------------!                  !------------------!

                   !------------------!
                   !         C        !
                   !------------------!
                   !  val    !        !
                   !------------------!

----------------------------------------------------------
3. Schritt: c->next = &D

!------------------!                  !------------------!
!         B        !                  !         D        !
!------------------!                  !------------------!
!  val    !  next  !----------------->!  val    !  next  !
!------------------!                  !------------------!
                                               ^
                                               |
                                               |
                   !------------------!        |
                   !         C        !        |
                   !------------------!        |
                   !  val    !  next  !--------|
                   !------------------!

----------------------------------------------------------
4. Schritt: B.next = c

!------------------!                  !------------------!
!         B        !                  !         D        !
!------------------!                  !------------------!
!  val    !  next  !                  !  val    !  next  !
!------------------!                  !------------------!
              |                                ^
              |                                |
              |                                |
              |    !------------------!        |
              |    !         C        !        |
              |--->!------------------!        |
                   !  val    !  next  !--------|
                   !------------------!

Kurz
1. Schritt: Node* c = new Node
2. Schritt: c->val = x
3. Schritt: c->next = &D
4. Schritt: B.next = c

Ist die Reihenfolge signifikant? Abgesehen davon, dass nat. das zuerst der neue Knoten erzeugt werden muss, im Prinzip nicht.
Sofern allerdings die Adresse D nicht extra zwischengespeichert wird, darf nat. der 4. Schritt nicht vor dem 3. erfolgen, weil nach der Veränderung von B.next ja das Element D nicht mehr über diesen Zeiger gefunden werden kann (es gibt noch einen anderen Grund, weshalb der Zeiger in B so spät wie möglich modifiziert werden sollte, das ist aber besser an einer komplexren Datenstruktur zu erläutern).
Schritte 1-3 haben zudem die Eigenschaft, dass sie alle nur das neue Objekt modifizieren, solange nur ein Teil dieser Schritte durchgeführt wurde, ist der neue Knoten unvollständig initialisiert und damit unbrauchbar. Und hier kommt der Konstruktor ins Spiel, der sorgt dafür dass diese 3 Schritte zusammenausgeführt werden. Der aufrufende Code hat also zu keinem Zeitpunkt mit einem nicht oder nur teilweise initialisierten Objekt zu tun, was die Logik erheblich vereinfacht.
Zudem liefert new seinen Zeiger erst nachdem das neue Objekt erzeugt und initialisiert wurde.

p = new Foo(p)

steht also: erzeuge ein neues Foo mit dem (alten) Inhalt von p und weise die Adresse des neuen Objektes p im Anschluss zu.

vip@r schrieb:

Ich hab jetzt das Problem, dass ich noch eine Funktion insertAfter() schreiben will. Ich hab damit schon angefangen:
if(head->value == afterElem)
	{
		head = new Node(val, head->next); //Warum werden damit die Zeiger nicht so umgebogen wie ich es will? DAS ist mein Problem!
		return;
	}
So wie's momentan steht, fügt er mir den Wert so ein wie bei beforeElement.

Wenn du nach einem Element einfügst, ist das eingefügte Elemnt logischerweise niemals das erste einer Liste. Folglich kann an der Zuweisung

head = ...

von vornherein etwas nicht stimmen.

hustbaer

camper schrieb:

Ja, den Fehler habe ich noch übersehen, soll nat.
for ( Node* before = head, curr = before->next; curr != nullptr; before = curr, curr = curr->next )

Vor curr fehler vermutlich noch ein Stern

camper

hustbaer schrieb:

camper schrieb:
Ja, den Fehler habe ich noch übersehen, soll nat.
for ( Node* before = head, curr = before->next; curr != nullptr; before = curr, curr = curr->next )
Vor curr fehler vermutlich noch ein Stern

Genau...
Jeder Compiler wird allerdings unmittelbar darauf hinweisen.
Da der Originalcode unvollständig ist, ist die Syntaxprüfung nicht meine Aufgabe.

vip*r

Danke Leute,

für eure Super antworten, insbesondere an Camper für seine wahnsinnig ausführliche Darstellung!

Das einfügen funktioniert soweit.

Jetzt hab ich aber das Problem, dass ja auch Elemente löschen will. Dazu hab ich schon mal das hier geschrieben:

void List::deleteAfter(int afterElem)
{
	while(head->value != afterElem)
	{
		head = head->next;	//head steht nun auf dem Element VOR dem zu Löschenden Element

		if(head->value == afterElem)	//steht head wirklich VOR dem zu Löschenden Element?
		{
			head->next = head->next->next;
		}
	}
}

Letzten Endes hab ich wieder das gleiche Problem. Ich weiß innerhalb der Fallabfrage nicht, wie ich meine Gedanken mit C++ ausdrücken kann...

Ich will hier nun den next-Zeiger vom aktuellen Element, das das Element ist VOR dem zu löschenden ist, auf das Element nach dem zu Löschenden umstellen. Quasi das zu Löschende aushängen. Wenn ich jetzt bspw. diese Liste habe 010000, dann macht mir mein Code das hier draus: 10000. Das ist falsch. Wobei ich doch mit head->next = head->next->next; genau das ausgedrückt habe. Der nächste (->next) vom aktuellen Element. Soll der Übernächste (->next->next) vom aktuellen Element werden...

Edit:

3. Schritt: c->next = &D

Das hier verstehe ich nicht so ganz. Wenn ich wie ich eine initialisierte Liste mit lauter gleichen Einträgen habe, kann ich nicht einfach &0 schreiben. Dann weiß der Compiler ja nicht, welche 0!

Shade Of Mine

Dein Problem ist einfach nur, dass du head aenderst. Du darfst head nicht aendern! Nur wenn du ein Element an 1. Stelle einfuegst.

Teile deinen Code vielleicht in mehrere Funktionen auf. So dass du zB nur noch:

Node* node=findElement(val);
node->next=node->next->next;

schreiben musst.

PS:
zu deiner Edit-Frage: mit &D meint camper einen Zeiger auf die Node D. D ist ja nur ein Platzhalter fuer irgendeinen Wert. In der Liste A->B->C->D waere &D einfach ein Zeiger auf das 4. Element.

vip*r

Danke für den Tip. findElement() wär eine Idee, aber das muss ich doch auch irgendwie so kapieren. Ich hab jetzt übrigens nach stundenlagem Sinieren eine Möglichkeit gefunden wie's geht, allerdings nur, wenn die zu Löschende Stelle genau einer Position ist. Problem dabei ist, die letzte Zeile Code:

void List::deleteAfter(int afterElem)
{
	Node* tmp = head;
	Node* iter = head;

	while(iter->value != afterElem)
	{
		iter = iter->next;	//iterator weiterschalten

		if(iter->value == afterElem)	//steht head wirklich VOR dem zu Löschenden Element?
		{
			tmp = tmp->next;
			tmp = tmp->next->next;
		}
	}

	head->next->next = tmp;
}

Ich ändere jetzt auch nirgends, bis auf die letzte Zeile, head.

Shade Of Mine

Lass head aus dem Spiel.
Warum willst du dauernd head aendern?

head ist der Kopf/Start deiner Liste. Den fasst man nicht an.

Wie wuerdest du findElement() implementieren? findElement(val) liefert dir einen Zeiger auf die Node die val als Value hat.

vip*r

So würd ich das machen:

Node* List::findElementAfter(int val)
{
	Node* tmp = head;

	while(tmp->value != val)
	{
		tmp = tmp->next;
	}

return tmp->next;	//Jetzt steht Zeiger VOR dem zu Löschenden Element
}

Problem dabei find ich da jetzt nur, dass ich für deleteAfter und deleteBefore ZWEI Methoden mit dem fast gleichen Code brauche!

Shade Of Mine

In dem Fall wuerdest du 1 nach dem gesuchten Element stehen. Alles korrekt, nur dein Kommentar nicht

Nur dass ich mit findElement das gesuchte Element haben wollte. Denn das Problem mit findElementAfter ist, dass du ja schon auf dem zuloeschenden Element stehst - wir brauchen aber den vorgaenger (sprich das Element mit dem Value val).

Aber wenn wir nun das gesuchte Element haben:

Node* node=findElement(val);
node->next=node->next->next;

Wenn du dann soweit bist dass das funktioniert - kannst du findElement ja durchaus wieder in deleteElementAfter() integrieren.

Ich persoenlich finde es aber oft einfacher eine komplexe Aufgabe in kleine unter aufgaben zu zerlegen und diese systematisch durchzuarbeiten.

PS:
und wie du siehst, fasst du in diesem Code head nicht an. Genauso soll es sein

vip*r

Ich kapier das einfach nicht. Das "Zusammenbauen" der beiden teile.

Ich hab diese Liste: 010000. findElementAfter() macht daraus: 0000.

Ich will die die zweite 0 vonlinks aushängen. Und jetzt hab ich von der Programmierung das Problem, wie ich die auf die 3. 0 von links verbinde...

Vor allem: Von welcher Stelle aus von links auf die Stelle verbunden werden soll die findElementAfter() liefert, verstehe ich nicht, da das ja von Fall zu Fall unterschiedlich ist!

Edit:

Node* List::findElementAfter(int val)
{
	Node* tmp = head;

	while(tmp->value != val)
	{
		tmp = tmp->next;
	}

return tmp;
}

void List::deleteAfter(int afterElem)
{

	Node* node = findElementAfter(afterElem);
	node->next = node->next->next;
}

So wie's jetzt dasteht hab ich das beste Ergebnis: 1000. Mir fehlt aber immer noch die Null an der Stelle ganz links...

Edit vom Edit:

So wie der Code jetzt ob steht funktioniert das ganze mit dieser Ausgabefunktion:

void List::printList()
{
	Node* curr = head;

	while(curr != NULL)
	{
		std::cout << curr->value;
		curr = curr->next;
	}

	std::cout << std::endl;
}

Jetzt versteh ich gar nix mehr...

vip*r

Ich hab dann mal die findElementAfter() wieder in die eigentliche Funktion integriert:

void List::deleteAfter(int afterElem)
{
	Node* tmp = head;
	Node* node;

	while(tmp->value != afterElem)
	{
		tmp = tmp->next;
	}

	node = tmp;

	node->next = node->next->next;
}

Ist da jetzt noch was überflüssiges drin?

Shade Of Mine

vip@r schrieb:

Jetzt versteh ich gar nix mehr...

Was genau ist dir unklar?

vip@r schrieb:

Ist da jetzt noch was überflüssiges drin?

node=tmp;
stattdessen kannst du ja gleich tmp weiter verwenden.

Und du musst noch beachten was passiert wenn afterElement das letzte Element ist.
Und natuerlich die Node selber muss noch per delete geloescht werden.
Und du musst noch beachten was passiert wenn afterElement nicht gefunden wird in der Liste.

Aber prinzipiell funktioniert das so.