Verkettete Listen - Listen Addieren

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.

Schlangenmensch

@Jockelx Ja, ich eigentlich auch. Aber bei der Aufgabenstellung zeigt der letzte next auf head_tail und der prev vom ersten auch. Daher sind die überprüfungen auf Anfang oder Ende immer ob der next Pointer auf head_tail bzw. der prev Pointer auf head_tail zeigt.
Ich habe irgendwo oben schon mal geschrieben, dass ich das anders machen würde, aber da ich weder Aufgabensteller noch der dadrunter leidende Student / Schüler bin, versuche ich im Rahmen dessen was ich von der Aufgabenstellung weiß, zu helfen.

Jockelx

@Schlangenmensch Oh, sorry, nicht alles gelesen.

WillyWilson

diese Aufgabe treibt mich langsam an den Rand des Wahnsinns.. wenn ich die Funktion mit list1.insertFront(list2);
Aufrufe und die Liste list2 ausgeben lasse bekomme ich eine Endlosschleife....

void List::insertFront(List & _List)
{
	// Einfügen einer vorhandenen Liste am Anfang
	_List.head_tail->prev->next = this->head_tail->next;
	_List.head_tail->next->prev = this->head_tail;
}

Meine Fresse ist diese Aufgabe dämlich.. list1 = list1+list2 bzw. list1 = list2+list1 liefert exakt das gewünschte ergebnis aber nein, wir müssen es auf die dumme art und weise machen