Verkettete Listen - Listen Addieren

[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

[Schlangenmensch]

@WillyWilson

Du hängst ja auch nur die erste Liste an die zweite... damit hat sich an liste 1 gar nichts getan.

void List::insertFront(List & _List)
{
	// Einfügen einer vorhandenen Liste am Anfang
      List.head_tail->prev->next = this->head_tail->next; //letzte Element vom _List zeigt auf das erste von this
      this->head_tail->next->prev = _List.head_tail->prev; //prev vom erste nelement von this zeigt auf das letzte von Liste 
      //Jetzt sind beide Listen verbunden. Und zwar in _List, sollen aber in this
      this.head_tail->next = _List.head_tail->next;
      this.head_tail->prev = _List.head_tail->prev;
      //jetzt  zeigen beide Listen auf die selben Elemente, also zweite Liste noch leeren
      _List.head_tail->next = _List.head_tail;
       this.head_tail->prev =  _List.head_tail;
      
}

ich hoffe, ich bin mit dem Head_tail Kram nicht durcheinander gekommen, wie schon mehrfach geschrieben, würde man das normalerweise anders machen und am Ende jeweils auf nullptr zeigen.

[WillyWilson]

@Schlangenmensch sagte in Verkettete Listen - Listen Addieren:

@WillyWilson

Du hängst ja auch nur die erste Liste an die zweite... damit hat sich an liste 1 gar nichts getan.

void List::insertFront(List & _List)
{
	// Einfügen einer vorhandenen Liste am Anfang
      List.head_tail->prev->next = this->head_tail->next; //letzte Element vom _List zeigt auf das erste von this
      this->head_tail->next->prev = _List.head_tail->prev; //prev vom erste nelement von this zeigt auf das letzte von Liste 
      //Jetzt sind beide Listen verbunden. Und zwar in _List, sollen aber in this
      this.head_tail->next = _List.head_tail->next;
      this.head_tail->prev = _List.head_tail->prev;
      //jetzt  zeigen beide Listen auf die selben Elemente, also zweite Liste noch leeren
      _List.head_tail->next = _List.head_tail;
       this.head_tail->prev =  _List.head_tail;
      
}

ich hoffe, ich bin mit dem Head_tail Kram nicht durcheinander gekommen, wie schon mehrfach geschrieben, würde man das normalerweise anders machen und am Ende jeweils auf nullptr zeigen.

@Schlangenmensch okay, hab es verstanden und hingekriegt. insertBack funktioniert jetzt auch. Es macht nur noch der destruktor probleme. Mal sehen ob ich es alleine gelöst bekomme

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;		
	}
	delete head_tail;
	std::cout << "Destruktor aufgerufen\n" << std::endl;	
}

Danke vielmals für die zahlreichen Antworten

Edit: habe jetzt auch herausgefunden was mit dem Destruktor los war. Er hat trotz Begrenzung versucht über den Endknoten (head_tail) hinaus zu deleten. Habe jetzt mit der Knotenanzahl der Liste die Grenze gesetzt und es scheint zu funktionieren:

List::~List()
{
	// Destruktor
	// Alle Knoten der Liste müssen gelöscht werden, wenn die Liste gelöscht wird.
	Node *ptr = head_tail->next;
	Node *tmp = ptr;
	int anz = 0; // Darf nicht größer-gleich sein als anzahl der datensätze(nodes) in der Liste

	while (ptr != head_tail && anz < this->list_size) {
		ptr = ptr->next;
		delete tmp;
		tmp = ptr;
		anz++;
	}
	delete head_tail; // Liste komplett gelöscht

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

Es gibt keine Memoryleaks und die Liste ist danach vollständig gelöscht.