Problem bei eigener LinkedList

Andy2211

Hi,
wenn ich das richtig sehe gehst du hin und kopierst data von einem Element in das nächste, in der Regel werden beim Sortieren eher die Elementreferenzen getauscht, also das gesamte "Element-Objekt" wird einfach umgehängt (Die next und previous Zeiger verbiegen).

Nach welchem Sortierverfahren willst du eig. sortieren?

Gruß Andy

Firefighter

Kommando zurück ich habe gerade gemerkt der Fehler liegt nicht an meinem sortieralgo sondern er liegt an der Ausgabe die nach dem Algo kommt. Ich habe auch einen eigenen [] operator definiert und anscheint fliegt dort diese Exception bei der erneuten Ausgabe Jetzt muss ich mal da gucken, trotzdem großes Dankeschön.

Firefighter

Vieleicht sollte ich doch mal den selbstgeschriebenen Operator zeigen

template<class T>
T LinkedList<T>::operator[](int index)
{
    Item* temp = this->first;

    if(temp == NULL || index >=this->m_length)
    {
        return NULL;
    }
    for(int i = 0;i<index;i++)
    {
        temp = temp->next;
    }

    return temp->data;
}

Habe ich da was falsch gemacht? Anscheind oder?

LordJaxom

Ich denke der Fehler liegt doch im Sortieralgorithmus (nichtmal dort, sondern in der Nacharbeit nach dem Algo) - am Ende setzt Du "first" auf "temp". "temp" würde aber zu dem Zeitpunkt das letzte Element sein, da Du "temp" in der Schleife zum Iterieren benutzt.

Andy2211

Hi,
also wenn in m_length die größe drin steht z.B. 5 Einträge dann sollte es eher heißen > m_length, da von 0 ab gezählt wird.

Ansonsten gibt man in der Regel eher eine Referenz zurück als das Objekt selbst.

Kann es wirklich das Problem sein, dass temp das letzte Element ist\wäre?
Das letzte Element zeigt ja wieder auf das Erste in der Linked List.

Gruß Andy

Firefighter

d.h. ich muss das element vor temp nehmen? stimmts? Komischer weiße kommt der Fehler aber nicht wenn ich die Ausgabe nach meinem sortieren auskomentiere. Ist die Ausgabe drinne dann kommt der Fehler wieder.

LordJaxom

Firefighter schrieb:

d.h. ich muss das element vor temp nehmen? stimmts?

Wie wär's mit dem ersten Element der Liste?

Komischer weiße kommt der Fehler aber nicht wenn ich die Ausgabe nach meinem sortieren auskomentiere. Ist die Ausgabe drinne dann kommt der Fehler wieder.

Ja, weil Du (nach meiner Ansicht) eine Liste durchliest, die viel kürzer ist als m_length. Nehmen wir an, die Liste ist 10 Elemente lang. First zeigt auf das erste.

Nach dem Sortierdurchlauf ist m_length immernoch 10 und first zeigt auf das letzte Element. Im operator[] versuchst Du nun z.B. das fünfte Element anzusprechen. Da 5 < m_length, versucht er, vom letzten Element aus fünf Elemente weiter zu zählen (ohne dabei zu prüfen ob next != 0). Ahnst Du was dabei passiert?

Andy2211 schrieb:

Kann es wirklich das Problem sein, dass temp das letzte Element ist\wäre?
Das letzte Element zeigt ja wieder auf das Erste in der Linked List.

Mag sein dass ich das übersehen habe, aber tut es das? In welcher hier geposteten Füllroutine oder Erläuterung wurde das festgelegt?

Firefighter

ein

temp = this->first;

in dem sortieralgo hat es wirklich behoben. Super Lord du hast mir mal wieder Prima geholfen Das hat erstmal alle Probleme behoben

Firefighter

Ja ich nochmal,

ich habe nochmal ein Problem und zwar beim löschen eines beliebigen Elementes.
Meine löschen Routine beruht auf der Rückgabe einer vorher angewendeten find_at() routine. Diese Routine gibt auch die richtige Position des gesuchten Elements zurück.

Nur hängt sich meine Löschen routine leider manchmal auf. Ich wollte euch mal fragen wo der Logikfehler in meiner Routine ist.

template<class T>
bool LinkedList<T>::delete_item(int index)
{
    Item* temp = this->first;
    if(index == -1)
    {
        return false;
    }
    else
    {
        m_length--;
        for(int i = 0;i<index-1;i++)
        {
            temp = temp->next;
        }
        this->first = temp->next;

        delete temp;
        return true;
    }
}

Der Index ist die Position die die find_at() Methode zurückgibt.Ich habe das gefühl das ich anscheind die Restliche Liste nicht wieder Ordnungsgemäß an den Rest ranhänge wenn ich mitten drinne lösche? Über Hilfe wäre ich sehr dankbar.

Mal Dir doch mal Listen-Bildchen, so wie in diesem Thread. Dann siehst Du schnell wo Dein Fehler ist.
Ansonsten ginge es so:

template<class T>
bool LinkedList<T>::erase( int index )
{
    if( index < 0 )
        return false;
    assert( index < m_length );

    Item* pToDel;
    if( index == 0 )
    {   // Sonderbehandlung für das Löschen des 1.Elements
        pToDel = first;
        first = pToDel->next;
    }
    else
    {
        Item* prev = first;
        for( int i = 1; i < index; ++i )
            prev = prev->next;
        pToDel = prev->next;    // prev zeigt auf den Vorgänger
        prev->next = pToDel->next;
    }
    delete pToDel;
    --m_length;
    return true;
}

Firefighter

Danke Werner, aber duch diesen Codeabschnitt:

pToDel = prev->next;    // prev zeigt auf den Vorgänger
prev->next = pToDel->next;

Steige ich nicht so richtig durch, was machst du da genau? Speichertechnisch?

Firefighter schrieb:

Danke Werner, aber duch diesen Codeabschnitt:
pToDel = prev->next;    // prev zeigt auf den Vorgänger
prev->next = pToDel->next;
Steige ich nicht so richtig durch, was machst du da genau? Speichertechnisch?

nach der ersten Zeile hat man folgende Situation:

prev           pToDel
    |              |
    v              v
 +-------+   +->+-------+   +->+-------+
 |  x0   |   |  |  x1   |   |  |  x    |
 | next------+  | next------+  | next---->...
 +-------+      +-------+      +-------+
                  ^
                 index (zu löschen)

und nach der zweiten Zeile:

+-----------------+
             |                 |
   prev      |    pToDel       |
    |        |     |           |
    v        |     v           v
 +-------+   |  +-------+   +->+-------+
 |  x0   |   |  |  x1   |   |  |  x    |
 | next------+  | next------+  | next---->...
 +-------+      +-------+      +-------+
                  ^
                 index (zu löschen)

.. mal selber; das übt

Gruß
Werner

Firefighter

Ahhh cool danke. Ich denke ich habe es jetzt so langsam geschnitten. Muss ja haufen malarbeit gewesen sein Danke nochmal

Firefighter

Mal so eine Frage nebenbei? Wie müsste denn bei der Klasse der Copyctor aussehen?? Kann ich da eventuell meinen [] operator nutzen oder muss ich da was beachten?

Firefighter schrieb:

Wie müsste denn bei der Klasse der Copyctor aussehen?? Kann ich da eventuell meinen [] operator nutzen oder muss ich da was beachten?

So weit ich das gesehen und Dein Konzept verstanden habe, läufst Du in dem operator[] in einer Schleife vom Anfang (first) bis zu i'ten Element.
Wenn Du nun den operator[] im Copy-Konstruktor einsetzt, so wurde Du bei 2 Elementen 3 mal durch diese Schleife im operator[] laufen. Bei 10 Elementen wären es 55 und bei 100 Elementen bereits über 5000 Durchläufe. Mit anderen Worten - Dein Copy-Konstruktor hätte die Komplexität O(n^2).

Das sollte man vermeiden. Also implementiere lieber eine Schleife mit 'Item* p; p = p-> next ..'.

Noch ein Tipp: Implemntiere auch eine swap-Methode für die LinkedList (das sollte trivial sein) und nutze im Zuweisungs-operator den Kopie-und-Swap-Trick.

LinkedList& LinkedList::operator=( const LinkedList& other )
{
  LinkedList temp(other);
  LinkedList::swap(temp);
  return *this;
}

Gruß
Werner

Firefighter

Das sollte man vermeiden. Also implementiere lieber eine Schleife mit 'Item* p; p = p-> next ..'.

wie meinst du das? Wie kann ich denn eine solche Schleife gestalten irgendwie muss ich ja mit dem Index arbeiten oder sehe ich das gerade falsch?
Aber die restlichen Tips waren sehr gut danke. wobei ich mir noch nicht 100% schlüssig bin wie ich die swap gestalten sollte

LordJaxom

Firefighter schrieb:

Das sollte man vermeiden. Also implementiere lieber eine Schleife mit 'Item* p; p = p-> next ..'.

wie meinst du das? Wie kann ich denn eine solche Schleife gestalten irgendwie muss ich ja mit dem Index arbeiten oder sehe ich das gerade falsch?

Du hast doch in der operator[]-Funktion eine Schleife, die vom ersten zum i'ten Element zählt. So eine Schleife ist gemeint, nur vom ersten bis zum letzten Element (Analogieübung: Ersetze i durch m_length-1 :D).

Zum Swap: Wenn Du den Inhalt zweier Listen tauschen möchtest, musst Du die Daten, die diese Liste verwaltet, tauschen. Die Daten innerhalb der Liste liegen als Zeiger auf das erste Element vor, also kann diese Tauschoperation sehr günstig erreicht werden.

Firefighter

Du hast doch in der operator[]-Funktion eine Schleife, die vom ersten zum i'ten Element zählt. So eine Schleife ist gemeint, nur vom ersten bis zum letzten Element (Analogieübung: Ersetze i durch m_length-1 :D).

Wenn ich das doch so mache, dann laufe ich ja jedesmal bis zum Ende durch und gebe das Letzte Element zurück? Stehe ich gerade aufem Schlauch?!

LordJaxom

Firefighter schrieb:

Wenn ich das doch so mache, dann laufe ich ja jedesmal bis zum Ende durch und gebe das Letzte Element zurück? Stehe ich gerade aufem Schlauch?!

Vielleicht: Ein Konstruktor gibt nichts zurück. Wir reden doch vom Copy-Konstruktor, oder?

EDIT:
Nochmal langsam: Du möchtest in einem Copy-Konstruktor an die einzelnen Elemente. Dein Vorschlag war, über den op[] an diese Elemente heranzugehen. Der Einwand war, dass das zu langsam sein könnte, weil dann für jedes Element von Anfang bis zum Element durchgezählt wird. Der Alternativvorschlag war, statt op[] eine Schleife zu verwenden, die wie die in op[] aufgebaut ist. Du solltest nicht op[] verändern.

Firefighter

Auch Von dem und von der Methode operator[] wie die besser gestaltet werden könnte

EDIT:Asso...ok dann muss ich das nochmal überarbeiten