Problem bei eigener LinkedList
-
Hallo Gemeinde hier erstmal die Klasse vereinfacht
.h
template<class T> class LinkedList { private: struct Item { T data; Item* next; }; Item* first; Item* last; unsigned long m_length; public: LinkedList(); ~LinkedList(); void pushfront(T& newdata); void popfront(); T operator[](int index); void setlength(); int size(); void sort_list();//Bei dieser Methode habe ich Probleme }hier einmal die funktion, abgesehen davon das sie so wie sie jetzt ist noch nicht funktionsfähig ist, wollte ich fragen, ob es hier logisch ist wenn ich die methode sort_list() statisch mache um sie auf die ganze klasse anzuwenden und nicht auf ein Objekt. Fals ich bei dieser Überlegung falsch liege bitte korrigiert mich und schlagt mir einen ordentlicheren Weg vor.
template<class T> void LinkedList<T>::sort_list() { Item* temp = this->first; int swapped; T tempdata; do { swapped = 0; while(temp->next != NULL) { if(temp->data > temp->next->data) { tempdata = temp->data; temp->data = temp->next->data; temp->next->data = tempdata; swapped = 1; } temp = temp->next; this->first = temp; } } while(swapped); }Ich hoffe es ist so einigermaßen klar gewurden.
Ich freue mich auf euere Kommentare.
-
ob es hier logisch ist wenn ich die methode sort_list() statisch mache um sie auf die ganze klasse anzuwenden und nicht auf ein Objekt
Also das macht für mich überhaupt keinen Sinn.
Schlussendlich werden ja immer Objekte sortiert und keine Klassen.
Nach deiner ersten Aussage, wie ich sie verstehe, willst du sort_list static deklarieren und dann ALLE Objekte vom Typ LinkedList sortieren?! - Das macht für mich ebenso wenig Sinn.
sort_list soll einfach das Objekt, für dass die Funktion aufgerufen worden ist sortieren.
-
@drakon...
Logisch
Daran habe ich gar nicht gedacht. Natürlich ist es richtig das ich nur das Objekt sortieren will. Aber kannst du mir eventuell noch auf die Sprünge helfen was an meiner sortierfunktion falsch ist? Weil sie will nicht so sortieren wie sie soll, eigentlich sortiert sie gar nicht?! Und es der Ansatz mit dem Tempobjekt in meiner Funktion richtig, ich glaube das habe ich eher falsch gemacht, weil ich will ja das originalobjekt haben, stimmts?
-
Firefighter schrieb:
@drakon...
Logisch
Daran habe ich gar nicht gedacht. Natürlich ist es richtig das ich nur das Objekt sortieren will. Aber kannst du mir eventuell noch auf die Sprünge helfen was an meiner sortierfunktion falsch ist? Weil sie will nicht so sortieren wie sie soll, eigentlich sortiert sie gar nicht?! Und es der Ansatz mit dem Tempobjekt in meiner Funktion richtig, ich glaube das habe ich eher falsch gemacht, weil ich will ja das originalobjekt haben, stimmts?Schau dir mal gängige Sortieralgorithmen an.
Ist sehr praktisch dabei:
http://www.site.uottawa.ca/~stan/csi2514/applets/sort/sort.htmlKannst auch mal schauen, wie es die Standardbibliothek macht. std::sort z.B.
-
bei deinem Link bekomme ich ein Fehler " Fehler beim Laden des Java-Applets"
-
http://de.wikipedia.org/wiki/Kategorie:Sortieralgorithmus
Du hast am ehesten sowas, wie den Bubble Sort.
Die Standardbibliothek (MSVC) nutzt afaik Quicksort.
-
Ich komm einfach beim Sortieren zu keinem ergebnis könnte mir eventuell jemand einen Tip geben was ich falsch mache, hier nochmal der aktuelle Code
template<class T> void LinkedList<T>::sort_list() { Item* temp = this->first; T tempdata; int swapp ; do { swapp = 0; while(temp->next != NULL) { if(temp->data > temp->next->data) { tempdata = temp->data; temp->data = temp->next->data; temp->next->data = tempdata; swapp = 1; } temp = temp->next; } }while(swapp); this->first = temp; }Danke im Voraus
EDIT:Fehler: Segmentation Fault
-
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
-
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.
-
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?
-
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.
-
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
-
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.
-
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?
-
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 
-
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?