Verkettete Listen - Listen Addieren



  • Hallo zusammen, ich bin recht neu im Programmieren und habe noch nicht alle Grundlagen drauf. Momentan hänge ich so ziemlich am Anfang der OOP und möchte nun eine Klasse Programmieren, die eine doppelt verkettete Liste als Datenstruktur verwaltet und manipulieren kann. Soweit funktioniert auch alles recht gut. Allerdings möchte ich jetzt zwei Methoden schreiben, die eine bereits erstellte Liste an den Anfang bzw. an das Ende einer anderen Liste setzt.

    Mein Problem: ich weiß nicht wie ich die beiden Objekte mit denen ich arbeite voneinander unterscheiden soll. Ich übergebe meiner Methode

    void List::insertFront(List & _List){...}

    ein bereits erstelltes Object (oder doch 2??) und erstelle daraus ein neues 3. Objekt?? Ich komme mit meiner bisherigen Denkweise da nicht ganz weiter.. hoffe ich konnte mich klar genug ausdrücken. Sollte das nicht der Fall gewesen sein werde ich mich bemühen das ganze noch besser zu formulieren.

    btw. wo liegt eigentlich der Unterschied ob ich der Methode die Referenz des Objekts oder einen Pointer auf das Objekt übergebe?
    Sprich statt void List::insertFront(List & _List) -> void List::insertFront(List * _List)

    Vielen Dank im Voraus

    MfG



  • @WillyWilson sagte in Verkettete Listen - Listen Addieren:

    void List::insertFront(List & _List){...}

    Identifier die mit einem Underscore und einem Großbuchstaben beginnen sind reserviert und dürfen nicht verwendet werden. Guckst Du Identifiers. Nenn den Parameter anders, zb.

    void List::insertFront(List &other)
    

    Da die übergebene liste nicht verändert werden soll:

    void List::insertFront(List const &other)
    

    Deine Funktion hat sicher auch eine Funktion, die ein einzelnes Element am Anfang der Liste einfügt? Sowas wie push_front(whatever value)?
    Dann klapperst Du einfach in insertFront() die Elemente von other von hinten nach vorne ab und rufst für jeden Wert push_front() auf.

    @WillyWilson sagte in Verkettete Listen - Listen Addieren:

    btw. wo liegt eigentlich der Unterschied ob ich der Methode die Referenz des Objekts oder einen Pointer auf das Objekt übergebe?
    Sprich statt void List::insertFront(List & _List) -> void List::insertFront(List * _List)

    Zeiger können ungültig sein oder auf "nichts" (nullptr) zeigen, Referenzen nicht. Deshalb verwendet man Pointer wenn das übergebene Dingsti optional ist, also nullptr sein kann.


  • Mod

    Um zwei Listen zusammen zu fügen, brauchst du logischerweise zwei Listen. Ob du sie zu einer dritten Liste zusammenfügen möchtest oder ob du eine der beiden Listen veränderst, bleibt dir überlassen. Von einer Klassenmethode mit Namen insert würde ich erwarten, dass sie das this Objekt verändert. Für den Fall, dass eine dritte Liste erstellt werden soll, würde man eher eine freie Methode mit einem Namen wie operator+ erwarten.

    Bei der von dir vorgeschlagene Signatur void List::insertFront(List & _List) spricht tatsächlich viel dafür, dass wohl etwas beim this verändert werden soll. Dafür spricht

    • Der Name insert
    • Dass die Methode void zurück gibt
    • Dass die Methode nicht const ist
      Dagegen spricht, dass das Argument _List keine const Referenz ist. Übersehen? Eine nicht-const Referenz impliziert nämlich eigentlich eine Änderung an einem Parameter. Sieht man aber eher selten. Wahrscheinlich meinst du hier also void List::insertFront(const List & _List).

    Pointer statt Referenzen nutzt man dann und nur dann wenn das Argument optional ist. Ich kann mir kein sinnvolles Szenario vorstellen, wo das Ding, das bei einem insert eingefügt werden soll, optional sein sollte.



  • der übergebene Parameter soll tatsächlich verändert werden. Die Liste die ich der Methode übergebe soll nach dem Aufruf aus 2 Listen bestehen, sprich die zweite Liste hänge ich an den Anfang der übergebenen Liste.

    Deine Funktion hat sicher auch eine Funktion, die ein einzelnes Element am Anfang der Liste einfügt? Sowas wie push_front(whatever value)?

    genau

    void List::insertFront(int key){...}
    

    Dann klapperst Du einfach in insertFront() die Elemente von other von hinten nach vorne ab und rufst für jeden Wert push_front() auf.

    das klappt ganz gut, aber das muss doch auch ohne Schleife gehen oder?

    Dagegen spricht, dass das Argument _List keine const Referenz ist. Übersehen? Eine nicht-const Referenz impliziert nämlich eigentlich eine Änderung an einem Parameter. Sieht man aber eher selten. Wahrscheinlich meinst du hier also void List::insertFront(const List & _List)

    Okay, ich möchte also keine dritte Liste erstellen, sondern tatsächlich das übergebene Objekt verändern. Und dafür brauche ich also den this operator?

    Um zwei Listen zusammen zu fügen, brauchst du logischerweise zwei Listen. Ob du sie zu einer dritten Liste zusammenfügen möchtest oder ob du eine der beiden Listen veränderst, bleibt dir überlassen. Von einer Klassenmethode mit Namen insert würde ich erwarten, dass sie das this Objekt verändert. Für den Fall, dass eine dritte Liste erstellt werden soll, würde man eher eine freie Methode mit einem Namen wie operator+ erwarten

    Das mit dem this operator hab ich anscheinend noch nicht ganz verstanden. Der ist doch ein Pointer auf das aktuell verwendete Objekt oder? Das würde also bedeuten, dass dieser in dem Fall auf das Objekt _List zeigt?

    Wie kann ich mit dessen Hilfe das Objekt um ein anderes Objekt erweitern und Positionen bzw. die Struktur der Datensätze innerhalb der Objekte verändern?



  • @WillyWilson sagte in Verkettete Listen - Listen Addieren:

    das muss doch auch ohne Schleife gehen oder?

    In einer Liste kommt man nur an die einzelnen Elemente wenn man sich von einem zum nächsten hangelt (von Skiplists mal abgesehen). Das ist ja gerade der Unterschied zu Containern mit wahlfreiem Zugriff (engl: random access).

    @WillyWilson sagte in Verkettete Listen - Listen Addieren:

    Okay, ich möchte also keine dritte Liste erstellen, sondern tatsächlich das übergeben Objekt verändern.

    Das ist aber dann total unintuitiv. Welches Objekt verändert denn Dein List::insertFront(int key)?

    Und dafür brauche ich also den this operator?

    this ist kein Operator sondern ein Zeiger auf die "aktuelle" (möglicherweise konstante) Instanz der Class/Struct, für die eine Methode aufgerufen wird:

    struct foo {
        int bar;
        void qux()
        {
            this->bar = 42;  // this ist vom Typ foo *
    
            // ist dasselbe wie
    
            bar = 42;
        }
    
        void hugo() const
        {
            // this ist hier vom Typ foo const *
    
            bar = 42;   // ist hier ungueltig, weil ein konstantes Objekt
                       // nicht verändert werden darf.
        }
    };
    


  • Das ist aber dann total unintuitiv. Welches Objekt verändert denn Dein List::insertFront(int key)?

    Die Methode fügt einen Knoten an den Anfang einer Instanz der Klasse List mit dem Wert Key. Sprich, ich setze einen Wert an den Anfang einer Liste.

    Die Methode die 2 Listen zusammenfügen soll, soll anhand der ihr übergebenen Parameter erkennen ob jetzt nur ein Knoten, oder doch eine ganze Liste an den Anfang gesetzt werden soll. Deshalb haben die beiden den selben namen

    Ich versuche es mal in Pseudo-Code auszudrücken:
    Ist übergebener Parameter vom Typ int? -> dann insertFront(int key){...}
    Ist übergebener Parameter vom Typ List? -> dann insertFront(List & _List){...}

    ich verstehe nur nicht wie ich mit dem this-pointer jetzt 2 Listen zusammenführen kann.
    this->insertFront(_List); macht irgendwie nicht viel sinn..



  • Du stehst wirklich auf einer Leitung. Zeig' mal Deine Liste, also, was Du bis jetzt hast. Vielleicht fällt mir dann ein wie man Deinen Knoten im Hirn aufbekommt.



  • @Swordfish sagte in Verkettete Listen - Listen Addieren:

    Du stehst wirklich auf einer Leitung. Zeig' mal Deine Liste, also, was Du bis jetzt hast. Vielleicht fällt mir dann ein wie man Deinen Knoten im Hirn aufbekommt.

    #ifndef _LIST_H
    #define _LIST_H
    #include "Node.h"
    #include <string>
    #include <iostream>
    
    class List
    {
    	/*
    	Die Klasse List dient zur Verwaltung von Knoten (Node). Mit Hilfe der Klasse List
    	kann ein Stapel oder Warteschlange realisiert werden.
    	*/
    private:
    	struct form { std::string start = "<< "; std::string zwischen = ", "; std::string ende = " >>\n"; } list_form;
    	Node * head_tail;						// Zeiger auf Kopf- und End-Element -> next der 1. Knoten; -> prev der letzte Knoten
    	int list_size;							// Länge der Kette
    	bool temp;								// normalerweise false; ist true, wenn es sich um eine temoräre Liste handelt
    											// die innerhalb der überladenen Operatoren angelegt wird
    public:
    	List();
    	List(const List & _List);				// Kopie Konstruktor
    	List(const List * _List);				// Kopie Konstruktor
    	~List();
    	void insertFront(int key);				// Einfügen eines Knotens am Anfang
    	void insertFront(List & _List);			// Einfügen einer vorhandenen Liste am Anfang
    	void insertFront(List * _List);			// Einfügen einer vorhandenen Liste am Anfang
    	void insertBack(int key);				// Einfügen eines Knotesn am Ende
    	void insertBack(List & _List);			// Einfügen einer vorhandenen Liste am Ende
    	void insertBack(List * _List);			// Einfügen einer vorhandenen Liste am Ende
    	bool getFront(int & key);				// Entnehmen eines Knoten am Anfang
    	bool getBack(int & key);				// Entnehmen eines Knoten am Ende
    	bool del(int key);						// löschen eines Knotens [key]
    	bool search(int key);					// Suchen eines Knoten
    	bool swap(int key1, int key2);			// Knoten in der Liste vertauschen
    	int size(void);							// Größe der Lise (Anzahl der Knoten)
    	bool test(void);						// Überprüfen der Zeigerstruktur der Liste
    	void format(const std::string & start, const std::string & zwischen, const std::string & ende);
    	// Mit der format-Methode kann die Ausgabe gesteuert werden: operator <<
    	// start: stirng vor der Ausgabe der Liste
    	// zwischen: string zwischen Listenknoten
    	// ende: string am Ende der Liste
    	List & operator = (const List & _List);						// Zuweisungsoperator definieren
    	List & operator = (const List * _List);						// Zuweisungsoperator definieren
    	List & operator + (const List & List_Append);				// Listen zusammenführen zu einer Liste
    	List & operator + (const List * List_Append);				// Listen zusammenführen zu einer Liste
    	friend std::ostream & operator << (std::ostream & stream, List const & Liste);		// Ausgabeoperator überladen
    	friend std::ostream & operator << (std::ostream & stream, List const * Liste);		// Ausgabeoperator überladen
    	friend Node* get_anker(List& l);
    	friend int get_AnzahlNodes(List& l);
    };
    
    #endif
    


  • Ja, ne, schon das ganze Ding mit Node und auch die Implementierung der Funktionen. Etwas, das compiliert.



  • @Swordfish sagte in Verkettete Listen - Listen Addieren:

    Ja, ne, schon das ganze Ding mit Node und auch die Implementierung der Funktionen. Etwas, das compiliert.

    Sorry, oben hast du die List.h

    main.cpp

    #include <iostream>
    //#define CATCH_CONFIG_RUNNER
    //#include "catch.hpp"
    #include "List.h"
    using namespace std;
    
    int main(void)
    {
    	//int result = Catch::Session().run();
    	int i;
    	List MyList;
    
    	for (i = 0; i < 10; i++) {
    		MyList.insertFront(i + 1);
    		MyList.insertBack(i + 100);
    	}
    
    	cout << MyList;
    
    	cout << "100: " << (MyList.search(100) ? "gefunden" : "nicht gefunden") << endl;
    	cout << "99: " << (MyList.search(99) ? "gefunden" : "nicht gefunden") << endl << endl;
    
    	while (MyList.getBack(i))
    		cout << i << " ";
    	cout << endl << endl;
    
    	List MyList1, MyList2, MyList3;
    	List * MyList_dyn = new List;
    
    	for (i = 0; i < 10; i++) {
    		MyList1.insertFront(i + 1);
    		MyList2.insertBack(i + 100);
    	}
    
    	MyList1.format("MyList1\n<<", ", ", ">>\n\n");
    	cout << MyList1;
    
    	MyList_dyn->format("MyList_dyn\n<<", ", ", ">>\n\n");
    	MyList_dyn->insertFront(-111);
    	cout << MyList_dyn;
    
    	MyList2.format("MyList2\n<<", ", ", ">>\n\n");
    	cout << MyList2;
    
    	MyList3 = MyList1 + MyList_dyn + MyList2;
    
    	delete MyList_dyn;
    
    	cout << "Groesse von MyList3: " << MyList3.size() << endl << endl;
    
    	MyList3.format("MyList3\n<<", ", ", ">>\n\n");
    	cout << MyList3 << endl;
    
    	MyList3.swap(8, 103);
    
    	cout << MyList3;
    
    	if (MyList3.test())
    		cout << "MyList3: Zeiger OK\n\n";
    	else
    		cout << "MyList3: Zeiger ******Error\n\n";
    
    	system("PAUSE");
    	return 0;
    }
    

    List.cpp

    #include "List.h"
    
    List::List()
    {
    	// Konstruktor für eine leere Liste
    	head_tail = new Node;
    	list_size = 0;
    	temp = false;
    	head_tail->next = head_tail;
    	head_tail->prev = head_tail;
    	head_tail->key = 0;
    }
    
    List::List(const List & _List)
    {
    	// Konstruktor mit Übergabe einer Liste, die dann kopiert wird.
    	// in dem Objekt _List sind die Knotenwerte enthalten, die Kopiert werden sollen.
    	list_form = _List.list_form;
    	head_tail = new Node;
    	list_size = 0;
    	temp = _List.temp;
    	head_tail->next = head_tail;
    	head_tail->prev = head_tail;
    	Node * tmp_node;
    	tmp_node = _List.head_tail->next;
    	while (tmp_node != _List.head_tail)
    	{
    		head_tail->prev = new Node(tmp_node->key, head_tail->prev->next, head_tail->prev);
    		head_tail->prev->prev->next = head_tail->prev;
    		list_size++;
    		tmp_node = tmp_node->next;
    	}
    	if (_List.temp) delete & _List;		// ist die Übergebene Liste eine temporäre Liste? -> aus Operator +
    }
    
    List::List(const List * _List)
    {
    	// Konstruktor mit Übergabe einer Liste, die dann kopiert wird.
    	// in dem Objekt _List sind die Knotenwerte enthalten, die Kopiert werden sollen.
    	list_form = _List->list_form;
    	head_tail = new Node;
    	list_size = 0;
    	temp = _List->temp;
    	head_tail->next = head_tail;
    	head_tail->prev = head_tail;
    	Node * tmp_node;
    	tmp_node = _List->head_tail->next;
    	while (tmp_node != _List->head_tail)
    	{
    		head_tail->prev = new Node(tmp_node->key, head_tail->prev->next, head_tail->prev);
    		head_tail->prev->prev->next = head_tail->prev;
    		list_size++;
    		tmp_node = tmp_node->next;
    	}
    	if (_List->temp) delete _List;		// ist die Übergebene Liste eine temporäre Liste? -> aus Operator +
    }
    
    List::~List()
    {
    	// Dekonstruktor
    	// Alle Knoten der Liste müssen gelöscht werden, wenn die Liste gelöscht wird.
    	if (head_tail->next != head_tail && head_tail->prev != head_tail) {
    		Node *tmp = this->head_tail;
    
    		while (tmp != head_tail) {
    			tmp = tmp->next;
    			delete tmp->prev;
    		}
    		std::cout << "Destruktor aufgerufen\n" << std::endl;
    	}
    }
    
    void List::insertFront(int key)
    {
    	// Einfügen eines neuen Knotens am Anfang der Liste
    	Node *ptr = new Node;
    	ptr->next = head_tail;
    	ptr->prev = head_tail;
    	head_tail->next->prev = ptr;
    	ptr->next = head_tail->next;
    	head_tail->next = ptr;
    	ptr->key = key;
    	list_size++;
    }
    
    void List::insertFront(List & _List)
    {
    	// Einfügen einer vorhandenen Liste am Anfang
    	
    	
    }
    
    void List::insertFront(List * _List)
    {
    	// Einfügen einer vorhandenen Liste am Anfang
    	
    	
    }
    
    void List::insertBack(int key)
    {
    	// Einfügen eines neuen Knotens am Ende der Liste
    	Node *ptr = new Node;
    	ptr->next = head_tail;
    	ptr->prev = head_tail;
    	head_tail->prev->next = ptr;
    	ptr->prev = head_tail->prev;
    	head_tail->prev = ptr;
    	ptr->key = key;
    	list_size++;
    }
    
    void List::insertBack(List & _List)
    {
    	// Einfügen einer vorhandenen Liste am Ende
    	
    }
    
    void List::insertBack(List * _List)
    {
    	// Einfügen einer vorhandenen Liste am Ende
    	
    }
    
    bool List::getFront(int & key)
    {
    	// entnehmen des Knotens am Anfang der Liste
    	// der Wert wird als Parameter zurückgegeben
    	// der Knoten wird entnommen
    	Node *ptr = head_tail->next;
    	key = ptr->key;
    
    	head_tail->next = ptr->next;
    	ptr->next->prev = head_tail;
    	delete ptr;
    
    	if (head_tail->next == head_tail || head_tail->prev == head_tail)
    		return false;
    
    	return true;
    }
    
    bool List::getBack(int & key)
    {	// entnehmen des Knotens am Ende der Liste
    	// der Wert wird als Parameter zurückgegeben
    	// der Knoten wird entnommen
    	Node *ptr = head_tail->prev;
    	key = ptr->key;
    
    	ptr->prev->next = head_tail;
    	head_tail->prev = ptr->prev;
    	delete ptr;
    
    	if (head_tail->next == head_tail || head_tail->prev == head_tail)
    		return false;
    
    	return true;
    }
    
    bool List::del(int key)
    {
    	// Löschen eines gegebenen Knotens
    	Node *ptr = head_tail->next;
    	while (ptr != head_tail) {
    		if (key == ptr->key)
    			break;
    		ptr = ptr->next;
    	}
    
    	if (ptr == head_tail)
    		return false;
    
    	ptr->next->prev = ptr->prev;
    	ptr->prev->next = ptr->next;
    	delete ptr;
    	return true;
    }
    
    bool List::search(int key)
    {
    	// suchen eines Knotens
    	Node *ptr = head_tail->next;
    	while (ptr != head_tail) {
    		if (key == ptr->key)
    			return true;
    		ptr = ptr->next;
    	}
    	if (ptr == head_tail)
    		return false;
    }
    
    bool List::swap(int key1, int key2)
    {
    	// Vertauschen von zwei Knoten
    	// Dabei werden die Zeiger der Knoten und deren Nachbarn verändert.
    	Node *ptr = head_tail->next;
    	Node *ptr1 = head_tail->next;
    
    	while (ptr1 != head_tail && key1 != ptr1->key) {
    		ptr1 = ptr1->next;
    	}
    
    	Node *ptr2 = head_tail->next;
    	while (ptr2 != head_tail && key2 != ptr2->key) {
    		ptr2 = ptr2->next;
    	}
    
    	if (ptr1 == head_tail || ptr2 == head_tail)
    		return false;
    
    	if (ptr1->next == ptr2 || ptr2->next == ptr1) {
    		Node *tmp = ptr1->prev;
    
    		ptr1->next = ptr2->next;
    		ptr1->next->prev = ptr1;
    
    		ptr2->prev = tmp;
    		ptr2->next = ptr1;
    
    		ptr1->prev = ptr2;
    		tmp->next = ptr2;
    	}
    	else {
    		ptr = ptr2->prev;
    		ptr2->prev = ptr1->prev;
    		ptr1->prev->next = ptr2;
    		ptr1->prev = ptr;
    		ptr->next = ptr1;
    		ptr = ptr1;
    		ptr = ptr1->next;
    		ptr1->next = ptr2->next;
    		ptr2->next = ptr;
    		ptr1->next->prev = ptr1;
    		ptr->prev = ptr2;
    	}
    	return true;
    }
    
    int List::size(void)
    {
    	// Rückgabe der Knoten in der Liste mit O(1)
    	Node *ptr = head_tail->next;
    	int anzahl = 0;
    	while (ptr != head_tail) {
    		anzahl++;
    		ptr = ptr->next;
    	}
    	return anzahl;
    }
    
    bool List::test(void)
    {
    	// Testmethode: die Methode durchläuft die Liste vom Anfang bis zum Ende und zurück
    	// Es werden dabei die Anzahl der Knoten gezählt.
    	// Stimmt die Anzahl der Knoten überein liefert die Methode true
    	Node * tmp = head_tail->next;
    	int i_next = 0, i_prev = 0;
    	while (tmp != head_tail) {
    		tmp = tmp->next;
    		if (i_next > list_size) return false;
    		i_next++;
    	}
    	if (i_next != list_size) return false;
    	tmp = head_tail->prev;
    	while (tmp != head_tail) {
    		tmp = tmp->prev;
    		if (i_prev > list_size) return false;
    		i_prev++;
    	}
    	return i_prev == i_next;
    }
    
    List & List::operator = (const List & _List)
    {
    	// in dem Objekt _List sind die Knotenwerte enthalten, die Kopiert werden sollen.
    	// Kopiert wird in das Objekt "this"
    	if (this == &_List) return *this;		//  !! keine Aktion notwendig
    	list_form = _List.list_form;
    	Node * tmp_node;
    	if (list_size)
    	{
    		Node * tmp_del;
    		tmp_node = head_tail->next;
    		while (tmp_node != head_tail)		// Alle eventuell vorhandenen Knoten in this löschen
    		{
    			tmp_del = tmp_node;
    			tmp_node = tmp_node->next;
    			delete tmp_del;
    		}
    		list_size = 0;
    		head_tail->next = head_tail;
    		head_tail->prev = head_tail;
    	}
    	tmp_node = _List.head_tail->next;		// Die Listen-Knotenwerte werden kopiert
    	while (tmp_node != _List.head_tail)
    	{
    		insertBack(tmp_node->key);
    		tmp_node = tmp_node->next;
    	}
    	if (_List.temp) delete & _List;			// ist die Übergebene Liste eine temporäre Liste? -> aus Operator +
    	return *this;
    }
    
    List & List::operator = (const List * _List)
    {
    	// in dem Objekt _List sind die Knotenwerte enthalten, die Kopiert werden sollen.
    	// Kopiert wird in das Objekt "this"
    	if (this == _List) return *this;		//  !! keine Aktion notwendig
    	list_form = _List->list_form;
    	Node * tmp_node;
    	if (list_size)
    	{
    		Node * tmp_del;
    		tmp_node = head_tail->next;
    		while (tmp_node != head_tail)		// Alle eventuell vorhandenen Knoten in this löschen
    		{
    			tmp_del = tmp_node;
    			tmp_node = tmp_node->next;
    			delete tmp_del;
    		}
    		list_size = 0;
    		head_tail->next = head_tail;
    		head_tail->prev = head_tail;
    	}
    	tmp_node = _List->head_tail->next;
    	while (tmp_node != _List->head_tail)	// Die Listen-Knotenwerte werden kopiert
    	{
    		insertBack(tmp_node->key);
    		tmp_node = tmp_node->next;
    	}
    	if (_List->temp) delete _List;			// ist die Übergebene Liste eine temporäre Liste? -> aus Operator +
    	return *this;
    }
    
    List & List::operator + (const List & List_Append)
    {
    	// Die Methode +
    	// Es werden zwei Listen aneinander gehangen.
    	// Dabei werden beide Ursprungslisten nicht verändert. Es entsteht eine neue Ergebnisliste.
    	Node * tmp_node;
    	List * tmp;
    	if (temp) {										// this ist eine temporäre Liste und kann verändert werden
    		tmp = this;
    	}
    	else {
    		tmp = new List(this);						// this ist keine temporäre Liste -> Kopie erzeugen
    		tmp->temp = true;							// Merker setzten, dass es sich um eine temporäre Liste handelt
    	}
    	if (List_Append.list_size) {					// anhängen der übergebenen Liste an tmp
    		tmp_node = List_Append.head_tail->next;
    		while (tmp_node != List_Append.head_tail) {
    			tmp->insertBack(tmp_node->key);
    			tmp_node = tmp_node->next;
    		}
    	}
    	if (List_Append.temp) delete & List_Append;		// wurde eine temporäre Liste übergeben, dann wird diese gelöscht						
    	return *tmp;
    }
    
    List & List::operator + (const List * List_Append)
    {
    	// Die Methode +
    	// Es werden zwei Listen aneinander gehangen.
    	// Dabei werden beide Ursprungslisten nicht verändert. Es entsteht eine neue Ergebnisliste.
    	Node * tmp_node;
    	List * tmp;
    	if (temp) {										// this ist eine temporäre Liste und kann verändert werden
    		tmp = this;
    	}
    	else {
    		tmp = new List(this);						// this ist keine temporäre Liste -> Kopie erzeugen
    		tmp->temp = true;							// Merker setzten, dass es sich um eine temporäre Liste handelt
    	}
    	if (List_Append->list_size) {					// anhängen der übergebenen Liste an tmp
    		tmp_node = List_Append->head_tail->next;
    		while (tmp_node != List_Append->head_tail) {
    			tmp->insertBack(tmp_node->key);
    			tmp_node = tmp_node->next;
    		}
    	}
    	if (List_Append->temp) delete List_Append;		// wurde eine temporäre Liste übergeben, dann wird diese gelöscht					
    	return *tmp;
    }
    
    void List::format(const std::string & start, const std::string & zwischen, const std::string & ende)
    {
    	// Setzen des Formates für die Ausgabesteuerung der Liste bei cout
    	// das Format wird für den überladenen Operator << verwendet
    	list_form.start = start;
    	list_form.zwischen = zwischen;
    	list_form.ende = ende;
    }
    
    std::ostream & operator<<(std::ostream  & stream, List const & Liste)
    {
    	// Ausgabe der Liste mit cout
    	stream << Liste.list_form.start;
    	for (Node * tmp = Liste.head_tail->next; tmp != Liste.head_tail; tmp = tmp->next)
    		stream << tmp->key << (tmp->next == Liste.head_tail ? Liste.list_form.ende : Liste.list_form.zwischen);
    	if (Liste.temp) delete & Liste;			// wurde eine temporäre Liste übergeben, dann wird diese gelöscht
    	return stream;
    }
    
    std::ostream & operator << (std::ostream & stream, List const * Liste)
    {
    	// Ausgabe der Liste mit cout
    	stream << Liste->list_form.start;
    	for (Node * tmp = Liste->head_tail->next; tmp != Liste->head_tail; tmp = tmp->next)
    		stream << tmp->key << (tmp->next == Liste->head_tail ? Liste->list_form.ende : Liste->list_form.zwischen);
    	if (Liste->temp) delete Liste;			// wurde eine temporäre Liste übergeben, dann wird diese gelöscht
    	return stream;
    }
    

    Node.h

    #ifndef _NODE_H
    #define _NODE_H
    class Node
    {
    public:
    	int key;
    	Node * next, *prev;
    public:
    	Node();
    	Node(int key, Node * next = 0, Node * prev = 0);
    	~Node();
    };
    #endif
    

    Node.cpp

    #include "Node.h"
    Node::Node()
    {
    	next = 0;
    	prev = 0;
    }
    Node::Node(int key, Node * next, Node * prev)
    {
    	this->key = key;
    	this->next = next;
    	this->prev = prev;
    }
    Node::~Node()
    {
    }
    


  • Whew!?!

    Wer hat dir denn beigebracht, dass man alle Funktionen doppelt für Pointer und Referenzen bereitstellt?

    	List(const List & _List);				// Kopie Konstruktor
    	List(const List * _List);				// Kopie Konstruktor
    

    Der Kopierkonstruktor ist der hier:

    	List(const List & list);
    

    Siehe auch hier: https://en.cppreference.com/w/cpp/language/copy_constructor

    Was der Konstruktor mit List* soll, erschließt sich mir nicht. Es ist jedenfalls kein Kopierkonstruktor im Sinne von C++ (siehe den Link: A copy constructor of class T is a non-template constructor whose first parameter is T&‍, const T&‍, volatile T&‍, or const volatile T&‍, and either there are no other parameters, or the rest of the parameters all have default values.).

    Am besten entfernt du alle Funktionen mit *.

    Und wie @Swordfish schon gesagt hat: vom Namen her würde ich immer erwarten, dass insertFront die übergebene Liste an den Anfang "meiner" Liste inserted und die übergebene Liste nicht ändert.

    (Man könnte sich noch einen Move-Parameter (Liste &&rhs) vorstellen, bei dem man einfach den Inhalt der übergebenen Liste klauen kann und nicht kopieren muss - aber ich vermute mal, dass du move-Semantik noch nicht kennst)

    Das hier: int size(void); ist C-Stil. In C++ wird kein void zur Makierung von leerer Parameterliste benötigt.

    Dein operator+ hat ebenfalls eine falsche Signatur. Man erwartet bei + nicht, dass sich irgendein Objekt ändert. operator+ sollte keine Referenz zurückgeben, sondern eine neue Liste, die aus beiden Listen aneinandergehängt besteht.

    List & operator + (const List & List_Append);
    //besser:
    List operator+(const List& other);
    

    Du kannst operator+ auch als freie Funktion definieren (außerhalb deiner Klasse):
    List operator+(const List &lhs, const List &rhs);
    Dann hast du kein this, aber die beiden Seiten links und rechts vom Plus. Gerade bei Operatoren mit 2 Argumenten finde ich Namen wie "lhs" und "rhs" (left/right hand side) angenehm. Aber diese Umbenennung brauchst du nicht machen. Wenn ich einen Parameter habe, ist als Kontrast zu "this" auch "other" ein guter Name (finde ich).
    Viel wichtiger aber: das & muss weg!



  • Das da:

    	// ...
    	friend Node* get_anker(List& l);
    	friend int get_AnzahlNodes(List& l);
    };
    

    ist wohl auch ein Ausdruck Deiner Konfusion. Warum sind das friends? Anstatt

    	// ...
    	Node* get_anker() const { return head_tail->next; }  // *)
    	int get_AnzahlNodes() const { return list_size; }
    };
    

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

    Mal mit Node anfangen:

    struct Node
    {	// in einer struct ist die sichtbarkeit per default public
    	int key;
    	Node *next;
    	Node *prev;
    
    	Node(int key = int{}, Node * next = nullptr, Node * prev = nullptr)
    	: key  { key  },  // initialization list anstatt Zuweisung im body
    	  next { next },
    	  prev { prev }
    	{}
    };
    

    Einen Destruktor der nichts tut braucht man auch nicht hinschreiben.



  • @Swordfish Wenn du in Node alle Member private machst und außer dem Konstruktor keine anderen Methoden hast, kommst du nicht mehr an die Werte ran, die in deiner Node gespeichert sind. Warum also private? Die Node wird doch nur intern von der List benötigt als Hilfskonstrukt.



  • @wob Uuups. Ich schlaf' wohl noch halb. Fixed.



  • @WillyWilson sagte in Verkettete Listen - Listen Addieren:

    Dein Destruktor funktioniert so nicht:

    Node *tmp = this->head_tail;
     
    while (tmp != head_tail)
    

    tmp ist gleich head_tail, daher kommst du nie in die Schleife rein.

    Insgesamt sähe mein Design einer doppelt verketten Liste etwas anders aus:
    Meine Liste würde wirklich auf das erste Element der Liste Zeigen (Head oder root, oder was auch immer). Ich würde auch keinen "Kreis" da einbauen. Das erste Element->prev würde dann auf nullptr zeigen, sowie das letzte Element->next auch.

    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.



  • @Swordfish sagte in Verkettete Listen - Listen Addieren:

    Das da:

    	// ...
    	friend Node* get_anker(List& l);
    	friend int get_AnzahlNodes(List& l);
    };
    

    ist wohl auch ein Ausdruck Deiner Konfusion. Warum sind das friends? Anstatt

    	// ...
    	Node* get_anker() const { return head_tail->next; }  // *)
    	int get_AnzahlNodes() const { return list_size; }
    };
    

    Es dient zu Übungszwecken. Ich habe vor, das Programm noch zu erweitern und da ich lernen möchte wie die Vererbung funktioniert, sind es "Friends".

    Und wie @Swordfish schon gesagt hat: vom Namen her würde ich immer erwarten, dass insertFront die übergebene Liste an den Anfang "meiner" Liste inserted und die übergebene Liste nicht ändert.
    (Man könnte sich noch einen Move-Parameter (Liste &&rhs) vorstellen, bei dem man einfach den Inhalt der übergebenen Liste klauen kann und nicht kopieren muss - aber ich vermute mal, dass du move-Semantik noch nicht kennst)

    Richtig, soweit bin ich noch nicht. Ich versuche gerade lediglich diese art von Funktion mit meinem aktuellen Kenntnisstand auf die Reihe zu bekommen.. Stehe leider immer noch auf dem Schlauch.

    Dein operator+ hat ebenfalls eine falsche Signatur. Man erwartet bei + nicht, dass sich irgendein Objekt ändert. operator+ sollte keine Referenz zurückgeben, sondern eine neue Liste, die aus beiden Listen aneinandergehängt besteht.

    Der zweck dahinter war, dass ich keine neue Liste zurück geben möchte, sondern eine bereits vorhandene (aber verändert).

    Du kannst operator+ auch als freie Funktion definieren (außerhalb deiner Klasse):

    List operator+(const List &lhs, const List &rhs);

    Dann hast du kein this, aber die beiden Seiten links und rechts vom Plus. Gerade bei Operatoren mit 2 Argumenten finde ich Namen wie "lhs" und "rhs" (left/right hand side) angenehm. Aber diese Umbenennung brauchst du nicht machen. Wenn ich einen Parameter habe, ist als Kontrast zu "this" auch "other" ein guter Name (finde ich).

    Viel wichtiger aber: das & muss weg!

    das probier ich gleich mal aus

    @Schlangenmensch danke für den Hinweis mit dem Destruktor, habe es soeben behoben!



  • @WillyWilson sagte in Verkettete Listen - Listen Addieren:

    Der zweck dahinter war, dass ich keine neue Liste zurück geben möchte, sondern eine bereits vorhandene (aber verändert).

    Dann verwendet man in der Regel den operator+= und nicht +. Bei += erwartet man, dass das aktuelle Objekt geändert wird (und dann auch per Referenz zurückgegeben wird).

    Es ist allerdings eher unüblich, dass die rechte Seite von += sich ändern kann (daher würde ich es auch nicht machen). Allerdings hat @Schlangenmensch recht, dass es bei Listen die sinnvollere Operation ist. Ich würde dann aber auch eine benannte Funktion nehmen und nicht den Operator überraschend anders verwenden, als man das normalerweise erwartet.

    Ich fände ein List::append(List &&other) eigentlich am klarsten. Dann wird man auf Aufruferseite gezwungen, move zu verwenden und sieht dann leichter, dass die anzuhängende Liste danach nicht mehr existiert.


  • Mod

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



  • 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?



  • 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);
    }
    

Log in to reply