Problem bei eigener LinkedList

Firefighter

Ich muss doch nochmal stören, könnt ihr mir vieleicht beim erstellen des Kopierkonstruktors ein wenig helfen?

Zur Zeit sieht mein Konstrukt so aus, leider fährt er sich fest,d.h. er rast in eine Endlosschleife.

template<class T>
LinkedList<T>::LinkedList(const LinkedList &link)
{

    this->m_length = link.m_length;
    while(link.first->next != NULL)
    {        //std::cout<<link.first->data<<std::endl;
        this->first = link.first;
        this->first = this->first->next;
    }

}

Ich muss doch zuerst die Größe der neuen Liste an meine alte zuweisen. Und dann muss ich doch Knotenweiße kopieren oder sehe ich das falsch?

camper

Firefighter schrieb:

Ich muss doch zuerst die Größe der neuen Liste an meine alte zuweisen. Und dann muss ich doch Knotenweiße kopieren oder sehe ich das falsch?

Nein. Allerdings sehe ich weder eine Schleife, die jemals abbrechen könnte (wenn sie es nicht sofort tut), noch den Versuch, irgendetwas zu kopieren.

LordJaxom

Genau hinschauen hilft oft!

Du fragst in der Schleife ab, ob der erste Knoten der rechten Liste einen Nachfolger hat. Du änderst die rechte Liste (bzw. das, was in der Bedingung geprüft wird) aber nirgendwo, folglich kann sich das Ergebnis der Bedingung nie ändern.

Zunächst mal möchtest Du über alle Knoten der rechten Liste gehen. Da die rechte Liste konstant ist (Du möchtest den Inhalt der rechten Liste kopieren, das Original dabei aber in Ruhe lassen), brauchst Du eine eigene Laufvariable dafür, und kannst nicht link.first direkt nehmen. Dann möchtest Du das jeweils aktuelle Element kopieren, solange ein aktuelles Element da ist (wichtig für die Abbruchbedingung!).

Item const* lauf = link.first; // Laufvariable
while (/* _aktueller_ Knoten gültig, sprich != 0? */) {
    /* kopiere Element aus lauf in die this-Liste */

    /* und weiterzählen der Laufvariable (ändern von lauf), damit sich das Ergebnis der Bedingung auch mal ändert, wäre auch nicht verkehrt */
}

Den Rest lasse ich erstmal wieder zur Übung

Firefighter

EDIT: Ich hab Müll geschrieben. Lord hat mal wieder den Tag gerettet... Danke so eine Erklärung hilft wirklich beim Lernen.

LordJaxom

In dem Beispiel hast Du in der Bedingung aber die Knoten der this-Liste. Du möchtest aber doch eine Schleife über die Knoten der link-Liste?!

Zu den beiden Zeilen in der Schleife bringe ich mal folgendes Beispiel:

i = 10; // (1)
i = 12; // (2)
// Welche Wirkung hat Zeile (1)? Richtig, garkeine, i wäre nach Zeile (2) == 12, egal ob Zeile (1) existiert oder nicht

Aber Du hast doch Funktionen zum Einfügen einzelner Elemente, die auch m_length mit hochzählen, oder? Ich denke das meinte Camper mit "nein [du brauchst die Länge nicht zuerst zu kopieren]"?

Firefighter

Ja klar, die Funktionen habe ich und die zählen auch hoch, damit ergibt das "Nein" von camper auch für mich Sinn

Firefighter

Aber Lord sollte ich da nicht einen Fehler bekommen?? wenn ich das hier versuche

template<class T>
LinkedList<T>::LinkedList(const LinkedList &link)
{
    Item const* lauf = link.first;

    while(lauf != NULL)
    {
        this->first = lauf;
        lauf = lauf->next;

    }

}

Dann ist es doch eine Invalid Conversion von this->first(nicht const) und lauf(const)??

Werner Salomon

Firefighter schrieb:

.. Dann ist es doch eine Invalid Conversion von this->first(nicht const) und lauf(const)??

Das ist korrekt, aber der Fehler wird erst vom Compiler berücksichtigt, wenn er versucht den Kopy-Konstruktor zu instanziieren. D.h. wenn Du in dem main kein Copy machst, wird kein Fehler gemeldet.

Mach Dir doch mal 'ne Zeichnung - bitte ...

am Anfang ist die Situation wie folgt

link.first (const)
 |
 v
 +-------+   +->+-------+   +->+-------+
 |  x1   |   |  |  x2   |   |  |  x3   |
 |  p1-------+  |  p2-------+  |  0    |
 +-------+      +-------+      +-------+

 first
 |
 v
 ?

und am Ende des Copy-Construktors sollte es so aussehen:

link.first (const)
 |
 v
 +-------+   +->+-------+   +->+-------+
 |  x1   |   |  |  x2   |   |  |  x3   |
 |  p1-------+  |  p2-------+  |  0    |
 +-------+      +-------+      +-------+

 first
 |
 v
 +-------+   +->+-------+   +->+-------+
 |  x1   |   |  |  x2   |   |  |  x3   |
 |  p1-------+  |  p2-------+  |  0    |
 +-------+      +-------+      +-------+

d.h. für jedes Item-Objekt der ursprüngliche Liste muss eine Kopie angelegt werden.
Und zwischendurch nach Anlegen des zweiten Item-Objekt sähe es so aus:

link.first      lauf
 |               |
 v               v
 +-------+   +->+-------+   +->+-------+
 |  x1   |   |  |  x2   |   |  |  x3   |
 |  p1-------+  |  p2-------+  |  0    |
 +-------+      +-------+      +-------+

 first          ende
 |              |
 v              v
 +-------+   +->+-------+
 |  x1   |   |  |  x2   |
 |  p1-------+  |  p2----->?
 +-------+      +-------+

Um das nächste (hier das dritte) Item-Objekt anzuhängen muss man den next-Pointer des aktuell letzten Item-Objekts beschreiben, also braucht man einen zweiten Item-Pointer, der immer auf das aktuell letzte Objekt zeigt (hier 'ende')

Gruß
Werner

Firefighter

Hmm es ist mir einleuchtend was das Problem ist, nur ich hab irgendwie gar kein Plan wie ich es umsetzen müsste Trotzdem danke für deinen Aufwand Werner.

LordJaxom

Naja, die Schleife stimmt ja schonmal soweit (bis auf das ominöse Umbiegen des first-Zeigers, womit Du ja immer nur das aktuelle Element der link-Liste zum ersten Element Deiner Liste machst). Jetzt hast Du in jedem Schleifendurchlauf doch einen Knoten der link-Liste in lauf. Der Knoten enthält das Element. Das Element soll an die this-Liste angefügt werden. Für's Anfügen hast Du bereits eine Funktion (und selbst wenn Du diese nicht benutzen wollen würdest, wüsstest Du durch diese Funktion, wie man ein Element an die Liste anfügt).

So, mehr Hilfe gibt's jetzt aber wirklich nicht

Firefighter

Lord du bist ein Schatz...soweit habe ich mal wieder nicht gedacht, auf jedenfall klappt es jetzt schon fast, ich kriege zwar noch ein Segmentation Fault, aber das kriege ich jetzt alleine hin, danke an alle von denen ich die Nerven strapaziert habe