Problem bei eigener LinkedList
-
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; }
-
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
-
Ahhh cool danke. Ich denke ich habe es jetzt so langsam geschnitten. Muss ja haufen malarbeit gewesen sein
Danke nochmal 
-
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
-
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
-
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.
-
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?!
-
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.
-
Auch
Von dem und von der Methode operator[] wie die besser gestaltet werden könnte EDIT:Asso...ok dann muss ich das nochmal überarbeiten
-
Achsooooo (siehe auch mein EDIT im Post oben).
Da kannst Du beruhigt sein: Bei einer verketteten Liste ohne zusätzlichen Verwaltungsschnickschnack kann der Indexoperator nicht besser implementiert werden. Deshalb bietet die Standardbibliothek auch keinen op[] für std::list an. Wenn Du sowas mit std::list nachbilden willst, muss auch durchgezählt werden.
-
Alles klar, danke dir
Dann schmeiße ich mein operator[] raus, wenn er nicht mal in der std::list vorgesehen ist, brauche ich den erst recht nicht
-
Sorry ich brauche nochmal eure Hilfe bei der Swap Funktion, ich tue mich ein wenig Schwer mit dem Zeigerwirrwarr. Zurzeit sieht es so hier aus:
template<class T> LinkedList<T>& LinkedList<T>::swap_list(const LinkedList& list) { Item* temp = this->first; this->first = list->first; list->first = temp; return this; }Leider führt das nur zu Fehlern
-
Was für Fehler?
Das alleine kann ja schon nicht gehen.
return this;
Nutzt doch einfach std::swap:
template<class T> LinkedList<T>& LinkedList<T>::swap_list(const LinkedList& list) { std::swap (this->first, list.first); return *this; }
-
hmm --.-- ich dummkopf, danke dir
-
const ?
-
Habe ich mich auch gerade gefragt, weil mit const geht es leider nicht :(Und auch ohne Const kriege ich eine Segmentation Fault
-
Firefighter schrieb:
Habe ich mich auch gerade gefragt, weil mit const geht es leider nicht
Darf ich das unter "Redewendungen, die ihr hasst" zitieren? :
Firefighter schrieb:
Und auch ohne Const kriege ich eine Segmentation Fault
Was heißt auch? Du kriegst den segfault auch mit const?