3. Verkettete Listen - Listen Addieren

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.

    0
    W
     1 Antwort
  • W

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

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

    0
    W
     1 Antwort
  • W

    @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()
{
}
    0
  • W

    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!

    0

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

    0
    W
    W
     2 Antworten
  • W

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

    0 1 Antwort

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

    0
  • S

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

    0 1 Antwort
  • W

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

    0
    W
     1 Antwort
  • W

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

    0
  • 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.

    0
  • W

    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?

    0
    W
     1 Antwort 

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

    @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?!

    0
    W
     1 Antwort
  • W

    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?

    0
    W
     1 Antwort
  • W

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

    0
    W
     1 Antwort
  • W

    @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!
*/
    0
    W
     1 Antwort
  • W

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

    0
    W
     1 Antwort
  • W

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

    0
Anmelden zum Antworten