Verkettete Listen - Listen Addieren



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


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



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



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



  • @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!
    */
    


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



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



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


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





  • @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
    }
    

Anmelden zum Antworten