Einfach verkettete Liste / Methode Liste aufsteigend sortieren



  • Ich komme einfach bei einer Funktion nicht weiter welche eine Liste
    aufsteigend sortieren soll.
    Beispielliste: 2-4-1-6-8-0
    Gewünschtes Ergebniss 0-1-2-4-6-8

    Meine Datenstruktur

    class Liste_einfach_verkettet {
    public:
        int Element;  // Daten der Liste
        Liste_einfach_verkettet *Next; // Referenz auf das nächste Listenelement
        Liste_einfach_verkettet() : Next(0), Element(0) {} // Konstruktor
        Liste_einfach_verkettet(int Data, Liste_einfach_verkettet *Node = 0) : Element(Data), Next(Node) {}
    
        //Methodenprototypen( Beschreibung und Implementierung in zugehöriger liste.cpp Datei
        void sortiere_liste_aufsteigend(Liste_einfach_verkettet z);
    }
    ;
    

    Mein Funktionsversuch

    void Liste_einfach_verkettet::sortiere_liste_aufsteigend(Liste_einfach_verkettet z)
        {
            Liste_einfach_verkettet  *tmp = Next;
            Liste_einfach_verkettet *zwischenspeicher;
    
            //Liste_einfach_verkettet *p3 = p2->Next;
            Liste_einfach_verkettet *p1 = tmp;
            Liste_einfach_verkettet *p2 = tmp->Next;
    
            int sortiercounter = 0;
    
            while (tmp->Next != 0 )
            {
                    //Liste_einfach_verkettet *tmp = Next;
                Liste_einfach_verkettet *p1 = tmp;
                Liste_einfach_verkettet *p2 = tmp->Next;
    
                if (p1->Element > p2->Element)
                {
    
                    zwischenspeicher = p1;
    
                    p2 = zwischenspeicher;
                    p1 = p2->Next;
                    //p3 = p1->Next;
                    sortiercounter++;
    
                }
    
                tmp = tmp->Next;
    
            }
        }
    

    Ich habe mir gedacht ich gehe die Liste durch, kontrolliere ob das jeweils rechte-Listengleid grö0er ist, wenn ja tausche ich und erhöhe einen COunter.
    Wenn nichts passiert am counter bin ich fertig( hab ich noch nicht implementiert, weil es im ansatz noch nicht funktioniert hat das überhaupt mal was umsortiert wird)
    Jedoch macht die funktion einfach nicht was ich möchte, ich komm einfach nicht weiter 😞



  • Ist die verkettete Liste eine eigene Übung/Hausaufgabe? Wenn nicht dann solltest du auf eine existierende Datenstruktur der stl zurückgreifen.



  • daddy_felix schrieb:

    Ist die verkettete Liste eine eigene Übung/Hausaufgabe? Wenn nicht dann solltest du auf eine existierende Datenstruktur der stl zurückgreifen.

    Ist eine Übung, daher stl darf nicht benutzt werden.
    lg



  • #include <iostream>
    
    class list
    {
    	list * next;
    	int data;
    
    	friend std::ostream & operator<<( std::ostream & os, list const & l );
    
    	public:
    		list() : next{ nullptr }, data{} {};
    		list( int value ) : next{ nullptr }, data{ value } {};
    		list( list const & ) = delete;
    		~list() { delete next; }
    
    		void push_back( int value ) {
    			list * cur = this;		
    			while( cur->next )
    				cur = cur->next;
    			cur->next = new list{ value };
    		}
    
    		void sort_asc()
    		{
    			bool sorted;
    			do {
    				sorted = true;
    
    				for( list * cur = this; cur && cur->next && cur->next->next; cur = cur->next ) {
    
    					if( cur->next->data > cur->next->next->data ) {
    
    						list * A = cur;
    						list * B = cur->next;
    						list * C = cur->next->next;
    						list * D = cur->next->next->next;
    
    						// A, B, C, D --> A, C, B, D
    						A->next = C;
    						A->next->next = B;
    						A->next->next->next = D;
    
    						sorted = false;
    					}
    				}
    
    			} while( !sorted );
    		}
    };
    
    std::ostream & operator<<( std::ostream & os, list const & l )
    {
    	for( list const * i = l.next; i; i = i->next )
    		os << i-> data << ' ';
    
    	return os;
    }
    
    int main()
    {
    	list l;
    	l.push_back( 2 );
    	l.push_back( 4 );
    	l.push_back( 1 );
    	l.push_back( 6 );
    	l.push_back( 8 );
    	l.push_back( 0 );
    
    	std::cout << l << '\n';
    
    	l.sort_asc();
    
    	std::cout << l << '\n';
    }
    


  • Glaub die Lösung ist viel zu advanced für mich. Sowas kann ich nicht abgeben und möchte ich auch nicht, da ich diesen Code überhaupt nicht verstehe.
    Könntest du mir aufzeigen wo mein Fehler in meinem COde liegt oder was ich falsch mache das ich meinen Code anpassen kann?
    lg



  • Vielleicht versuchst erstmal den Code zu verstehen? Nachfragen hilft.

    Ich zB. verstehe nicht, warum Du Deiner Methode zum sortieren void Liste_einfach_verkettet::sortiere_liste_aufsteigend(Liste_einfach_verkettet z) eine Liste_einfach_verkettet als Parameter übergeben willst, wo doch die zu sortierende Liste schon die ist, für die Du die Methode aufrufst.

    Liste_einfach_verkettet EineListe;
    // ...
    EineListe.sortiere_liste_aufsteigend( /* wozu der parameter? */ );
    

    Warum also machst Du das?



  • Das hab ich mich auch schon gefragt. Weil in der Funktion kann ich ja gar nicht
    z *tmp=Next schreiben
    daher wohl einfach Parameter freilassen ()



  • Wohl wahr.

    Als nächstes verstehe ich nicht, wozu Du schon mit Pointern rumspielst

    as1as schrieb:

    Liste_einfach_verkettet::sortiere_liste_aufsteigend(Liste_einfach_verkettet z)
        {
            Liste_einfach_verkettet  *tmp = Next;
            Liste_einfach_verkettet *zwischenspeicher;
     
           
            //Liste_einfach_verkettet *p3 = p2->Next;
            Liste_einfach_verkettet *p1 = tmp;
            Liste_einfach_verkettet *p2 = tmp->Next;
     
            int sortiercounter = 0;
     
            while (tmp->Next != 0 )
            {
    // ...
    

    bevor Du überhaupt (in der Sortierschleife) weißt, was womit vertauscht werden soll. Warum machst Du das?



  • Ich dachte ich brauche einen Hilfspointer um mir dann im Falle
    wenn ich was vertauschen muss, den einen Wert speichern kann.

    Ich habe ja meine Liste
    Beispielliste: 2-4-1-6-8-0

    tmp ist ja am Anfang meine 2
    und p2 meine 4.

    Nun gehe ich in die while-Schleife
    und schaue ob p1->Element größer als p2-> Element ist.
    Das ist ja am anfang noch nicht gegeben bei 2 und 4.
    Nun wird tmp zu tmp->next.
    p1 ist ja nun meine 4 und p2 meine 1.
    Nun ist der if Fall ja true und ich müsste nun die beiden Listenelemente vertauschen.
    dort setze ich nun eine zwischenspeichervariable auf p1.
    p2 soll ja nun zu p1 werden, also zum zwischenspeicher
    und p1 zu p2. also p1=p2->next.
    aber irgendwie funktioniert das bei mir nicht



  • as1as schrieb:

    Ich dachte ich brauche einen Hilfspointer um mir dann im Falle
    wenn ich was vertauschen muss, den einen Wert speichern kann.

    Variablen deklariert man nicht, wenn man sie nicht braucht, bzw. eben dort, wo man sie braucht.

    as1as schrieb:

    Nun gehe ich in die while-Schleife

    Die einmal bis zum Listenende läuft? Hast Du denn nicht schon herausgefunden, daß die Sortierschleife sooft laufen muss, bis die Sortierung abgeschlossen ist, also nichts mehr vertauscht werden musste?

    also

    do {
        for( Liste_einfach_verkettet current = this; current != nullptr; current = current->Next ) {
            // check was ...
            //    vertausch ggf. was ...
        }
    } while( sortiercounter != 0 );
    


  • Ich habe den Code mal umgeschrieben. Geht das so?
    Nun bin ich jedoch wieder bei meinem Anfangsproblem.
    Das tauschen von p1 und p2.

    Liste_einfach_verkettet  *tmp = Next;
     int sortiercounter =1;
    do {
        for( ; tmp != nullptr; tmp = tmp->Next ) {
    
                if (tmp->Element > tmp->Next->Element)
                {// vertausche }
    
        }
    sortiercounter--;
    
    } while( sortiercounter != 0 );
    


  • if (tmp->Element > tmp->Next->Element) 
       std::swap(tmp->Element, tmp->Next->Element) ;
    


  • @manni: ich glaub fast, das hat sich der Aufgabensteller anders gedacht 😉



  • Swordfish schrieb:

    @manni: ich glaub fast, das hat sich der Aufgabensteller anders gedacht 😉

    Möglich 😉



  • as1as schrieb:

    int sortiercounter = 1;
        do {
            // ...
        }
        sortiercounter--;
    } while( sortiercounter != 0 );
    

    Die Logik check ich noch nicht.



  • Hab mich heute morgen nochmal drangesetzt aber komme einfach nicht auf ein Ergebniss. Richtig frustierend 😞

    Mein Sortieralgorithmus soll ja einfach nur durch die verkettete Liste gehen.
    Beispiel 2 4 1 6 8
    Man geht von links nach rechts. Ist das Linke Element größer als das Rechte wird getauscht. Also ist 2>4 nein, also weiter 4>1 ja, also tausch, und weiter in der Liste.
    Man geht immer von Anfang bis zum Ende der Liste. Gab es nur einen einzigen Tausch oder mehr wiederholt man den Vorgang. Gab es in einem kompletten Durchlauf keinen einzigen Tausch mehr ist man fertig.

    Mein neuer Code sieht nun so aus

    void Liste_einfach_verkettet::sortiere_liste_aufsteigend()
        {
            int sortiercounter=1;
            do 
            {
            int sortiercounter = 1;
            Liste_einfach_verkettet  *tmp = Next;
            Liste_einfach_verkettet *zwischenspeicher = 0;
    
            while (tmp->Next != 0 )
            {
    
                if (tmp->Element > tmp->Next->Element)
                {
                    //vertausche listeneinträge
                    Liste_einfach_verkettet *z = tmp->Next;
                    zwischenspeicher = tmp;
                    tmp = z;
                    tmp->Next = zwischenspeicher;
    
                    //erhöhe Sortiercounter
                    sortiercounter++;
                }
                tmp = tmp->Next;
            }
            sortiercounter--;
            } while (sortiercounter !=0);
        }
    

    Jedoch terminiert mein Programm bei der 2 4 1 6 8 Liste nicht 😞



  • Wie viele sortiercounter hast du definiert?



  • Ich hatte erst nur einen in do. aber dann habe ich einne fehler bekommen in meiner while bedinugng vom do das sortiercounter nicht gefunden werden kann.
    daher hab ichnoch einen davor gemacht. dann könnte ich quaso den in der do rausnehmen. hilft mir und meinem problem aber vermutlich nicht weiter.
    lg



  • as1as schrieb:

    hilft mir und meinem problem aber vermutlich nicht weiter.

    Dann erklär mal, wie die äußere Schleife sonst jemals terminieren soll.



  • ich hatte mir das sogedacht das der counter ja am anfang 1 ist. wenn es was zu sortieren gibt geht er ja höher, 2, 3 ect. wenn es nichts mehr zu sortieren gibt, bleibt er ja auf 1 und wird dann um -- reduziert, ist also 0 und ich komme aus meiner to do schleife raus.


Log in to reply