Element vorher einfügen?

[Shade Of Mine]

vip@r schrieb:

Das vorher einzufügende Element muss einfach an das "eigentlich" erste Element angefügt werden. Und das ist einfach mein Problem.

Jep, das ist das Problem.

Es muss naemlich nicht als 1. Element eingefuegt werden sondern vor das gesuchte Element.

Wenn wir

A -> C -> D

als liste haben und du willst B for C einfuegen musst du folgendes machen:
C suchen und dir den Vorgaenger von C merken. Dann (Vorgaenger von C)->next = B setzen und B->next gleich C setzen.

Sobald das geht, musst du dich mit dem spezialfall befassen dass du vor A einfuegen willst. Das ignoriere aber fuers erste mal.

[krümelkacker]

Reduziere den Quellcode auf das Wesentliche, so dass da noch ein vollständiges Programm übrig bleibt. Zeige dieses Programm komplett. Beschreibe, welche Ausgabe du erwartest und wie die Ausgabe von deiner Erwartung abweicht.

[22_38h]

Warum iterierst Du eigentlich über die Liste, ( curr=curr->next ), wenn Du doch immer an der gleichen Stelle einfügst (oder nie) ( insertNode->next = head )?

Fragend um 22:38h

[camper]

Node* insertNode = new Node;
insertNode->value = val;

insertNode->next = head;

Bitte nicht. Solchen Code darfst du schreiben, wenn du Kernel-Hacker spielen willst.
In C++ haben wir verstanden, dass Klassen Abstraktionsmechanismen darstellen, und ein Objekt mehr ist als die Summe seiner Teile (Member). Damit sollte auch eine einfache Klasse wie Node sich selbst um ihre Initialisierung kümmern. Gib Ihr also einen Konstruktor und vermeide direkte Zuweisungen an Member.
Da damit auch der uninteressantere Teil (die eigentliche Zuweisung) aus deiner Funktion verschwindet, wird es viel leichter, zu sehen, warum es so offenbar nicht funktionieren kann (Pluspukt immerhin dafür, dass Zeiger gleich initialisiert wurden...).

Node::Node(int val, Node* next) : val(val), next(next) {}
...
        if(curr->value == beforeElem)
        {
            Node* insertNode = new Node( val, head );
            return;
        }
...

Aha... der neue Knoten soll vor dem zuvor gesuchten eingefügt werden, taucht aber gar nicht als Konstruktorargument auf. head hat hier klar nichts verloren.

Node* insertNode = new Node( val, curr );

Besser, aber der neue Knoten hängt immer noch in der Luft.
Gehen wir also, wie Shade vorgeschlagen hat, vor, und merken wir uns den Vorgänger

void List::insertBefore(int beforeElem, int val)
{
    for ( Node* before = head, curr = before->next; curr != nullptr; before = next, next = next->next )
    {
        if ( curr->value == beforeElem )
        {
            before->next = new Node( val, curr );
            return;
        }
    }
}

Soweit so gut, setzt aber voraus, dass die Liste mindestens ein Element hat und das gesuchte Element nicht das erste ist. Also prüfen wir noch diese Spezialfälle zuerst:

void List::insertBefore(int beforeElem, int val)
{
    if ( head == nullptr )
        return;
    if ( head->value == beforeElem )
    {
        head = new Node( val, head );
        return;
    }
    for ( Node* before = head, curr = before->next; curr != nullptr; before = next, next = next->next )
    {
        if ( curr->value == beforeElem )
        {
            before->next = new Node( val, curr );
            return;
        }
    }
}

Das funktioniert soweit, ist aber nicht besonders schön. Wenn wir before haben, können wir next daraus jederzeit ermitteln, eine Variable ist also überflüssig:

void List::insertBefore(int beforeElem, int val)
{
    if ( head == nullptr )
        return;
    if ( head->value == beforeElem )
    {
        head = new Node( val, head );
        return;
    }
    for ( Node* before = head; before->next != nullptr; before = before->next )
    {
        if ( before->next->value == beforeElem )
        {
            before->next = new Node( val, before->next );
            return;
        }
    }
}

Warum benötigen wir before? Um den darin enthaltenen Zeiger next ändern zu können, wenn das neue Element eingefügt wird. Wir könnten also before als Zeiger auf Node durch ein before, das auf den darin enthaltenen Zeiger verweist, ersetzen:

void List::insertBefore(int beforeElem, int val)
{
    if ( head == nullptr )
        return;
    if ( head->value == beforeElem )
    {
        head = new Node( val, head );
        return;
    }
    for ( Node** link = &head->next; *link != nullptr; link = &( *link )->next )
    {
        if ( ( *link )->value == beforeElem )
        {
            *link = new Node( val, *link );
            return;
        }
    }
}

Wenn wir jetzt noch genau hinschauen, stellen wir fest, dass es gar nicht darauf ankommt, ob sich der Zeiger, auf den link zeigt, in einem Nodeobjekt befindet, head und leere Listen sind gar keine Spezialfälle.

void List::insertBefore(int beforeElem, int val)
{
    for ( Node** link = &head; *link != nullptr; link = &( *link )->next )
    {
        if ( ( *link )->value == beforeElem )
        {
            *link = new Node( val, *link );
            return;
        }
    }
}

Es ist schon spät, deshalb Schachtelsätze...

[vip*r]

@camper:

for ( Node* before = head, curr = before->next; curr != nullptr; before = next, next = next->next )
    {

    }

Ich verstehe den Schleifenkopf nicht. Was machst du da? Wenn ich diese for-Schleife in mein VS2010 kopiere, dann bekomme ich unzählige Fehler.

Ich hab nun mal deinen Code geändert, dass ich ihn auch verstehe:

void List::insertBefore(int beforeElem, int val)
{
	Node* before = head;
	Node* curr;
	Node* next;

	for(curr = before->next; curr != nullptr; before = next, next = next->next)
	{
		if(curr->value == beforeElem)
		{

		}
	}
}

Nun hab ich aber das Problem, dass mir der Compiler den Fehler ausgibt, dass next nicht initialisiert sei... Mit was muss ich next initialisieren? Vieleicht mit head? Oder head->next?

Edit: Das Erzeugen eines neuen Node Objekts wurde uns in der Vorlesung so gezeigt und als gängige Methode beigebracht. Man solle ein Objekt erzeugen, dann die Zeiger des vorhergehenden Objekts auf das neue Objekt umbiegen und den Zeiger des neuen Objekts auf das nachfolgende Objekt umbiegen. Danach den überflüssigen Zeiger löschen.

[Shade Of Mine]

vip@r schrieb:

Ich verstehe den Schleifenkopf nicht. Was machst du da? Wenn ich diese for-Schleife in mein VS2010 kopiere, dann bekomme ich unzählige Fehler.

Was fuer Fehler und was verstehst du nicht?

Ich hab nun mal deinen Code geändert, dass ich ihn auch verstehe:

void List::insertBefore(int beforeElem, int val)
{
	Node* before = head;
	Node* curr;
	Node* next;

	for(curr = before->next; curr != nullptr; before = next, next = next->next)
	{
		if(curr->value == beforeElem)
		{

		}
	}
}

Nein.
Zeichne das ganze mit Papier und Stift auf.
A->B->C->D
wenn before=A ist, dann ist curr=B und dein erster Vergleich im if betrifft B->value==beforeElement aber du vergleichst nie auf A.

Ich meine das ernst. Leg die Tastatur auf die Seite und nimm dir ein Stueck papier und schreibe die Operationen die notwendig sind C in diese Liste einzufuegen:
A->B->D->E

Edit: Das Erzeugen eines neuen Node Objekts wurde uns in der Vorlesung so gezeigt und als gängige Methode beigebracht. Man solle ein Objekt erzeugen, dann die Zeiger des vorhergehenden Objekts auf das neue Objekt umbiegen und den Zeiger des neuen Objekts auf das nachfolgende Objekt umbiegen. Danach den überflüssigen Zeiger löschen.

In C++ haben wir Konstruktoren.

Wenn du immer:
n=new Node();
n->value=value;
n->next=next;

schreibst, kannst du ja gleich nen Ctor dafuer verwenden:
n=new Node(value, next);

[Shade Of Mine]

vip@r schrieb:

Ich verstehe den Schleifenkopf nicht. Was machst du da? Wenn ich diese for-Schleife in mein VS2010 kopiere, dann bekomme ich unzählige Fehler.

Was fuer Fehler und was verstehst du nicht?

Ich meine das ernst. Leg die Tastatur auf die Seite und nimm dir ein Stueck papier und schreibe die Operationen die notwendig sind C in diese Liste einzufuegen:
A->B->D->E

Edit: Das Erzeugen eines neuen Node Objekts wurde uns in der Vorlesung so gezeigt und als gängige Methode beigebracht. Man solle ein Objekt erzeugen, dann die Zeiger des vorhergehenden Objekts auf das neue Objekt umbiegen und den Zeiger des neuen Objekts auf das nachfolgende Objekt umbiegen. Danach den überflüssigen Zeiger löschen.

In C++ haben wir Konstruktoren.

Wenn du immer:
n=new Node();
n->value=value;
n->next=next;

schreibst, kannst du ja gleich nen Ctor dafuer verwenden:
n=new Node(value, next);

[vip*r]

Shade of mine, ich hab jetzt wirklich mal die Tastatur auf die Seite gelegt und mir Gedanken zum Ablauf gemacht:

1.: Das neue Objekt C erstellen
2.: In C val schreiben
3.: Auf B iterieren (Kriterium: solange curr != D)
4.: Zeiger von B auf das neue Objekt C biegen
5.: Zeiber von C auf das nachfolgende Objekt D zeigen lassen
6.: Übriggebliebenen Zeiger löschen

Das mit dem Konstruktor ist natürlich ein wertvoller Tip! Ich werde ab erstmal die Funktion versuchen ohne Ctor zu implementieren. Ich weiß, es ist umständlich aber diese Ctor-Geschichte überlastet mich (noch) immer etwas. Ich hab da immer Angst, dass der Ctor mehr oder das falsche macht was ich jetzt überhaupt will und deshalb mein Code nicht funktioniert...

Stimmt die Ablaufbeschreibung oben?

[camper]

vip@r schrieb:

@camper:

for ( Node* before = head, curr = before->next; curr != nullptr; before = next, next = next->next )

Ich verstehe den Schleifenkopf nicht. Was machst du da? Wenn ich diese for-Schleife in mein VS2010 kopiere, dann bekomme ich unzählige Fehler.

Ja, den Fehler habe ich noch übersehen, soll nat.

for ( Node* before = head, curr = before->next; curr != nullptr; before = curr, curr = curr->next )

vip@r schrieb:

Edit: Das Erzeugen eines neuen Node Objekts wurde uns in der Vorlesung so gezeigt und als gängige Methode beigebracht. Man solle ein Objekt erzeugen, dann die Zeiger des vorhergehenden Objekts auf das neue Objekt umbiegen und den Zeiger des neuen Objekts auf das nachfolgende Objekt umbiegen. Danach den überflüssigen Zeiger löschen.

Was für ein überflüssiger Zeiger?

vip@r schrieb:

1.: Das neue Objekt C erstellen
2.: In C val schreiben
3.: Auf B iterieren (Kriterium: solange curr != D)
4.: Zeiger von B auf das neue Objekt C biegen
5.: Zeiber von C auf das nachfolgende Objekt D zeigen lassen
6.: Übriggebliebenen Zeiger löschen

Ich kann nur vemuten, dass Nr. 6 für den Fall da ist, das C in Nr.1 erstellt wurde, aber gar kein passendes Element in der Liste zu finden ist, dass dem Suchkriterium entspricht?

[vip*r]

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

Kannst du mir vielleicht ganz ausführlich erklären, wie man in C++ mit meinen gegeben Konstrukten "Zeiger umhängt"? Denn genau diese Stelle verstehe ich nicht. Das würde mir sehr weiterhelfen!

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. Ich will das aber nach einem Element haben. Quasi so: 00000 wird nach afterElement() zu: 010000. Wie muss ich das nun im Rumpf des if's ausdrücken? Könnt ihr mich dabei unterstützen? So wie der Code oben steht passiert folgendes: 00000 wird zu 10000.

Edit:
Kurz zum Kommentar: Das neu erzeugte Objekt "head" soll als Wert den übergebenen Wert 1 bekommen. Das Funktionier so. Als Zeiger soll es den nächsten des "eigentlichen" head bekommen, das soll das head->next im Argument des new-Operators ausdrücken! Aber WARUM geht das so offensichtlich nicht und überschreibt mir einfach den "echten" head?

[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...