Verkettete Listen - Listen Addieren

[SeppJ]

@Schlangenmensch sagte in Verkettete Listen - Listen Addieren:

@WillyWilson sagte in Verkettete Listen - Listen Addieren:

Insgesamt finde ich die Frage nach dem zusammenführen von zwei Listen aber spannend. Eigentlich ist ja eben, das Knoten einfügen und entfernen die Stärke von Listen. Wenn ich jetzt zwei Ketten zu einer dritten zusammen füge, sollen dann Kopien angelegt werden? So, dass die anderen beiden Listen dann wie vorher bestehen? Dann ist das eine recht aufwendige Operation. Man kann aber recht einfach die zweite Liste an die erste "dran hängen". Dann muss man nur aufpassen, dass die einzelnen Knoten nicht doppelt freigegeben werden können.
Ich gehe davon aus, das std::list nicht von ungefähr nur ein "merge" kennt, welches die zweite Liste leert.

Deswegen kennt std::list auch zwei verschiedene Operationen: insert und splice. Das was du beschreibst ist ein Splice. An sich macht eine insert-Operation mit nur speziell einer Liste als Argument auch nicht viel Sinn. Schließlich könnte man jede allgemeine Sequenz von Werten einfügen, egal ob aus anderen Listen oder sonstwoher. Daher ist std::list::insert auch nicht spezialisiert für andere Listen, sondern arbeitet ganz allgemein auf Iteratoren, wohingegen std::list::splice zwingend eine gleichartige Liste voraussetzt.

Der Threadersteller wäre gut beraten, sich an übliche Sprachregelungen, Konventionen, und Funktionssignaturen zu halten. Die vorhandenen Container in der STL sind immer sehr gute Vorbilder. Das was der Threadersteller oben beschreibt mit dem Verändern einer zweiten Liste bei einer Methode namens insert ist ganz sicher etwas, das kein Mensch auf der Welt bei einer Funktion mit Namen insert erwartet. Ganz schlecht.

[WillyWilson]

liefert this innerhalb der Funktion void List::insertFront(List & _List) eine andere adresse als die Referenz zu dem Objekt das übergeben wird? Sprich ist hier this != &_List ? wenn ja könnte man doch einfach sagen dass &_List = this + _List ist oder nicht?

[Swordfish]

struct foo {
    int bar;
    void qux(foo const &other)
    {
        // hier zeigt this auf a,
        // other ist eine referenz auf ein konstantes b

        bar;        // a.bar
        this->bar;  // a.bar;
        other.bar;  // b.bar;
    }
};

int main()
{
    foo a;
    foo b;

    a.qux(b);
}

[wob]

@WillyWilson sagte in Verkettete Listen - Listen Addieren:

liefert this innerhalb der Funktion void List::insertFront(List & _List) eine andere adresse als die Referenz zu dem Objekt das übergeben wird? Sprich ist hier this != &_List ?

this liefert die Adresse des eigenen Listen-Objektes. Dein &_List (Unterstrich+Großbuchstabe ist immer noch reserviert, solltest du also NICHT verwenden) ist die Adresse der übergebenen Liste.
Das wird meistens unterschiedlich sein, aber wenn du dich selbst insertest, dann sind die Adressen gleich. Also bei
List l; l.insertFront(l);.

wenn ja könnte man doch einfach sagen dass &_List = this + _List ist oder nicht?

hier habe ich dich verloren. Warum sollte das gehen? Du kannst doch nicht irgendwelche Adressen addieren wollen?!

[WillyWilson]

wenn ja könnte man doch einfach sagen dass &_List = this + _List ist oder nicht?

hier habe ich dich verloren. Warum sollte das gehen? Du kannst doch nicht irgendwelche Adressen addieren wollen?!

ich dachte es wird nur das Objekt an der Adresse verändert, nicht die Adresse selbst. Sorry!

Alles was mir hier geraten wurde ist sehr schlüssig, wenn auch nicht ganz für einen Anfänger wie mich wie für fortgeschrittene wie euch. Das ganze gehört zu einer Aufgabe die so abgegeben und vorgestellt werden soll. Ich sollte also an den meisten Funktionen nichts verändern, sondern diese so wie sie geschrieben wurden zum Laufen bringen

deshalb auch 2 mal die gleiche Funktion nur einmal mit *übergebenem und einem &übergebenem Parameter. Ich denke mal das dient dem Zweck des Verständnisses?

die Funktion void List::insertFront(List & _List) soll also so bleiben. Deshalb verstehe ich nicht wie ich das in der Form hinkriegen soll und wie das ganze funktioniert. Die Funktion bekommt die Referenz einer liste übergeben, heißt also die Liste kann verändert werden. Wie hänge ich denn jetzt eine schon bereits erstellte Liste an die übergebene Liste, ohne ein ganz neues Objekt zu erstellen?

[wob]

@WillyWilson Nochmal: die normale Erwartungshaltung ist, dass die übergebene Liste an die Liste angehängt wird.

Du musst in deiner Liste zum letzten Node gehen und dort den next-Pointer auf die erste Node der anzuhängenden Liste setzen. Und auf der anzuhängenden Liste muss bei der ersten Node der previous-Pointer entsprechend angepasst werden. Danach musst du noch sicherstellen, dass die jetzt angehängte Liste nicht mehr auf irgendwelche Nodes verweist, d.h. du musst die Ankernode auf nullptr setzen.

deshalb auch 2 mal die gleiche Funktion nur einmal mit *übergebenem und einem &übergebenem Parameter. Ich denke mal das dient dem Zweck des Verständnisses?

Keine Ahnung, was das für ein Zweck haben sollte, außer zu zeigen, was man NICHT tun sollte.

[WillyWilson]

@wob sagte in Verkettete Listen - Listen Addieren:

@WillyWilson Nochmal: die normale Erwartungshaltung ist, dass die übergebene Liste an die Liste angehängt wird.

Du musst in deiner Liste zum letzten Node gehen und dort den next-Pointer auf die erste Node der anzuhängenden Liste setzen. Und auf der anzuhängenden Liste muss bei der ersten Node der previous-Pointer entsprechend angepasst werden. Danach musst du noch sicherstellen, dass die jetzt angehängte Liste nicht mehr auf irgendwelche Nodes verweist, d.h. du musst die Ankernode auf nullptr setzen.

Darauf bin ich auch schon gekommen, allerdings hindert mich ein Kommentar zur Aufgabenstellung daran:

/*
	Die einzufügenden Knoten werden übernommen (nicht kopiert)
	Die einzufügende Liste _List ist anschließend leer.
	Es darf keine Schleife und kein new benutzt werden. 	
*/
/*
	Es wird ein Objekt übergeben in dem Knoten vorhanden sein können.
	Diese Knoten (koplette Kette) werden an den Anfang der Liste (this) übertragen ohne sie zu kopieren!
*/

[wob]

@WillyWilson Was hindert dich daran? Das entspricht doch genau der normalen Erwartungshaltung.

[WillyWilson]

@wob sagte in Verkettete Listen - Listen Addieren:

@WillyWilson Was hindert dich daran? Das entspricht doch genau der normalen Erwartungshaltung.

Wie komme ich ohne Schleife zum letzten Node der Liste? _List->head_tail->prev = this->head_tail->next funktioniert nicht.
Ich hab hier eine echte Denkblockade wie es scheint.. tut mir echt leid, falls die Lösung für euch so offensichtlich erscheint.

[Schlangenmensch]

Deine Liste wird als Referenz übergeben:

List::insertFront(List & _List) {
//_List.head_tail->prev letzter Knoten von _List
_List.head_tail->prev->next = head_tail->next; //du willst ja nicht den letzten Knoten überschreiben
}

[WillyWilson]

@Schlangenmensch sagte in Verkettete Listen - Listen Addieren:

Deine Liste wird als Referenz übergeben:

List::insertFront(List & _List) {
//_List.head_tail->prev letzter Knoten von _List
_List.head_tail->prev->next = head_tail->next; //du willst ja nicht den letzten Knoten überschreiben
}

soweit kann ich folgen, aber da ich ja 2 Listen habe, habe ich auch 2 Anfangsknoten(head_tail). Wie unterscheide ich die beiden voneinander?

[Swordfish]

@WillyWilson: Schau nochmal.

[Schlangenmensch]

@WillyWilson
Hier nochmal dasselbe, etwas anders geschrieben

List::insertFront(List & _List) {
//_List.head_tail->prev letzter Knoten von _List
_List.head_tail->prev->next = this->head_tail->next; //du willst ja nicht den letzten Knoten überschreiben
}

[WillyWilson]

@Swordfish sagte in Verkettete Listen - Listen Addieren:

@WillyWilson: Schau nochmal.

Ich glaube ich hab viel zu kompliziert gedacht. This gilt also immer für das aktuell aufgerufene Objekt.

Oh man, danke

[Swordfish]

Und für Deine ganzen Varianten mit Zeigern

SOME_TYPE foo(TYPE &bar)
{
    // ...
}

SOME_TYPE foo(TYPE *bar)
{
    foo(*bar);  // ruft die variante mit Referenz auf

    // oder evtl, falls das Ding was zurueckgeben soll:
    return foo(*bar);
}

dann brauchst Du denselben Käse nicht zweimal schreiben.

[WillyWilson]

Frage noch @Swordfish

[*] Nein, natürlich nicht!! Man gibt interna der Klasse nie nicht raus!

Wie ist das gemeint? Mir wurde beigebracht die Interna seines Codes niemals preis zu geben

Habe eine ListTest.cpp zum Testen der Klasse und deren Instanzen bekommen die mir 3 Fehler ausgibt. Einer davon im Destruktor

#include "catch.hpp"
#include "List.h"
#include "Node.h"
#include <string>

using namespace std;

// Friend-Methode fuer Testroutine
Node* get_anker(List& l) {
	return l.head_tail;
}

int get_AnzahlNodes(List& l) {
	return l.list_size;
}

TEST_CASE("List Testing", "[List]") {

	List test_list;
	List second;

	SECTION("Hinzufuegen und Suche von Nodes - simple") {
		test_list.insertFront(5);
		test_list.insertFront(7);

		test_list.insertBack(9);
		test_list.insertBack(4);

		REQUIRE(test_list.size() == 4);

		REQUIRE(test_list.search(7) == true);
		REQUIRE(test_list.search(8) == false);
		REQUIRE(test_list.search(3) == false);
		REQUIRE(test_list.search(9) == true);

		int key;
		test_list.getBack(key);
		REQUIRE(key == 4);
		test_list.getFront(key);
		REQUIRE(key == 7);
	}

	SECTION("Hinzufuegen von Nodes aus zweiter Liste am Ende") {
		test_list.insertFront(5);
		test_list.insertFront(7);

		test_list.insertBack(9);
		test_list.insertBack(4);

		second.insertFront(5);
		second.insertFront(5);

		second.insertBack(5);
		second.insertBack(5);

		test_list.insertBack(second);

		REQUIRE(test_list.size() == 8);		
		
		Node* tmp = get_anker(test_list);
		tmp = tmp->next;
		int key = tmp->key;
		REQUIRE(key == 7);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 9);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 4);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);
		
		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		for (int i = 0; i < 8; i++)
			tmp = tmp->prev;

		//head_tail wieder erreicht
		key = tmp->key;
		REQUIRE(key == 0);
	}

	SECTION("Hinzufuegen von Nodes aus zweiter Liste am Anfang") {
		test_list.insertFront(5);
		test_list.insertFront(7);
		test_list.insertBack(9);

		second.insertFront(5);
		second.insertFront(5);
		second.insertBack(5);

		test_list.insertFront(second);

		REQUIRE(test_list.size() == 6);

		Node* tmp = get_anker(test_list);
		tmp = tmp->next;
		int key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 7);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 5);

		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 9);

		for (int i = 0; i < 6; i++)
			tmp = tmp->prev;

		//head_tail wieder erreicht
		key = tmp->key;
		REQUIRE(key == 0);
	}

	SECTION("Hinzufuegen und Loeschen von Nodes - simpel") {
		test_list.insertFront(5);
		test_list.insertFront(7);
		test_list.insertFront(9);
		test_list.insertFront(4);

		test_list.insertBack(3);
		test_list.insertBack(2);
		test_list.insertBack(4);
		test_list.insertBack(1);

		REQUIRE(test_list.size() == 8);

		REQUIRE(test_list.del(8) == false);
		REQUIRE(test_list.del(4) == true);
		REQUIRE(test_list.del(1) == true);
		REQUIRE(test_list.del(5) == true);

		REQUIRE(test_list.size() == 5);

		int key;
		test_list.getBack(key);
		REQUIRE(key == 4);
		test_list.getFront(key);
		REQUIRE(key == 9);
	}

	SECTION("Vertauschen von zwei Elementen und testen der Zeiger") {
		test_list.insertFront(5);
		test_list.insertFront(7);
		test_list.insertFront(9);
		test_list.insertFront(4);

		test_list.insertBack(3);
		test_list.insertBack(2);
		test_list.insertBack(4);
		test_list.insertBack(1);

		REQUIRE(test_list.size() == 8);
		//////////////////////////////////////////////////////////////
		//Fall 1: Zwei Knoten aus der Mitte, nicht nebeneinander	//
		//////////////////////////////////////////////////////////////
		REQUIRE(test_list.swap(7, 2) == true);
		Node* tmp = get_anker(test_list);
		//prüfe ob 2 an neuem Platz
		for (int i = 0; i < 3; i++)
			tmp = tmp->next;
		int key = tmp->key;
		REQUIRE(key == 2);
		//Prüfe ob 7 an neuem Platz
		for (int i = 0; i < 3; i++)
			tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 7);
		tmp = tmp->next;
		//Prüfe ob Anker wieder erreichbar
		for (int i = 0; i < 7; i++)
			tmp = tmp->prev;
		key = tmp->key;
		REQUIRE(key == 0);

		//////////////////////////////////////////////////////////////////////////
		//Fall 2: Erster Knoten mit einem aus der Mitte, nicht nebeneinander	//
		//////////////////////////////////////////////////////////////////////////
		REQUIRE(test_list.swap(4, 5) == true);
		tmp = tmp->next;
		//Prüfe ob neuer erster richtig
		key = tmp->key;
		REQUIRE(key == 5);
		//Prüfe ob 4 an neuem Platz
		for (int i = 0; i < 3; i++)
			tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 4);
		tmp = tmp->next;
		//Prüfe ob Anker wieder erreichbar
		for (int i = 0; i < 5; i++)
			tmp = tmp->prev;
		key = tmp->key;
		REQUIRE(key == 0);

		//////////////////////////////////////////////////////////////////////////
		//Fall 3: Letzter Knoten mit einem aus der Mitte, nicht nebeneinander	//
		//////////////////////////////////////////////////////////////////////////
		REQUIRE(test_list.swap(1, 3) == true);
		for(int i = 0; i < 5; i++)
			tmp = tmp->next;
		//Prüfe ob 1 an neuem Platz
		key = tmp->key;
		REQUIRE(key == 1);
		//Prüfe ob neuer letzter richtig
		for (int i = 0; i < 3; i++)
			tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 3);
		tmp = tmp->next;
		//Prüfe ob Anker wieder erreichbar
		for (int i = 0; i < 9; i++)
			tmp = tmp->prev;
		key = tmp->key;
		REQUIRE(key == 0);

		//////////////////////////////////////////////////////
		//Fall 4: Zwei Knoten aus der Mitte, nebeneinander	//
		//////////////////////////////////////////////////////
		REQUIRE(test_list.swap(2, 4) == true);
		for (int i = 0; i < 3; i++)
			tmp = tmp->next;
		//Prüfe ob 4 an neuem Platz
		key = tmp->key;
		REQUIRE(key == 4);
		//Prüfe ob 1 an neuem Platz
		tmp = tmp->next;
		key = tmp->key;
		REQUIRE(key == 2);
		tmp = tmp->next;
		//Prüfe ob Anker wieder erreichbar
		for (int i = 0; i < 5; i++)
			tmp = tmp->prev;
		key = tmp->key;
		REQUIRE(key == 0);
	}
}

Das Ergebnis ist also das Selbe.. Wo ist der Unterschied ob ich einen Parameter mit Referenz oder als *Pointer übergebe?

[Swordfish]

@WillyWilson sagte in Verkettete Listen - Listen Addieren:

Wie ist das gemeint? Mir wurde beigebracht die Interna seines Codes niemals preis zu geben

Das ist so gemeint, daß eine Liste einen Node* niemals rausgeben sollte. Aber wenn das vom Testcode so gefordert ist mit friend get_anker() ...

[WillyWilson]

Noch etwas zu der insertFront Funktion. In der Aufgabenstellung steht "Die einzufügende Liste _List ist anschließend leer." Wie genau kann man das bewerkstelligen ohne eine Kopie zu erzeugen? Wenn ich den Inhalt der Liste leere ist der in der angefügten Liste doch auch weg?

irgendwas scheint mit dem Destructor nicht in Ordnung zu sein

List::~List()
{
	// Destruktor
	// Alle Knoten der Liste müssen gelöscht werden, wenn die Liste gelöscht wird.
	Node * ptr = head_tail->next;

	while (ptr != head_tail) {
		Node * tmp = ptr;
		ptr = ptr->next;
		delete tmp;		
	}

	std::cout << "Destruktor aufgerufen\n" << std::endl;	
}

Habe jetzt schon mehrere varianten Probiert. Erhalte jedes mal am Ende einen Fehler "Aufgabe 1.exe hat einen Haltepunkt ausgelöst. " und der debugger zeigt auch keine genauen angaben

[Schlangenmensch]

Hi, wenn du mit dem Umhängen fertig bist, also die Knoten aus deiner zweiten Liste vor den Knoten deiner ersten Liste hängen, sollte dein "head_tail" der zweiten Liste mit next und previous auf sich selbst zeigen. Damit ist die Liste leer. Du sollst nicht den Destruktor aufrufen, dass löscht die Liste und alle enthaltenen Knoten. Und wenn womöglich zwei Listen auf die gleichen Knoten zeigen, dann rufst du nachher noch den Destruktor für einen Knoten doppelt auf, dass kann dann zu einem Crash führen.

Außerdem musst du im Destruktor head_tail auch noch löschen, sonst entsteht da ein memory leak.

Was der Debugger anzeigt hängt von deinen Compiler Einstellungen ab. Wenn du ohne Optimierungen und mit Debug Symbolen kompilierst solltest du im Debugger sehr genau sehen, was schief läuft.

[Jockelx]

@Schlangenmensch sagte in Verkettete Listen - Listen Addieren:

sollte dein "head_tail" der zweiten Liste mit next und previous auf sich selbst zeigen. Damit ist die Liste leer.

Bei einer Liste würde ich erwarten, dass die auf nullptr zeigen. Schliesslich will ich da ggf. mal durch iterieren.