Doppelt verkettete Liste sortieren



  • Für ein Projekt muss ich eine Funktion erstellen, welche die Elemente in einer doppelt verketteten Liste sortiert. Leider fällt mir dazu kein Ansatz ein. Könnt ihr mir weiterhelfen?

    typedef struct _Person
        {
        int     Alter;
        float   Groesse;
        float   Gewicht;
        char    Name[Zeichenkettenlaenge];
        } Person;
    
        typedef struct _ListenElem
        {
        Person        Listenperson;
        struct _ListenElem  *prev;
        struct _ListenElem  *next;
        } ListenElem;
    
        typedef struct _Liste
        {
        int         anz;
        ListenElem  *root;
        ListenElem  *end;
        } Liste;
    
    


  • Es wird dir vermutlich keiner deine Hausaufgaben machen.



  • Das war auch nicht meine Intention.
    Meine erste Idee klappt leider nicht und ich komme nicht weiter, bzw. finde keine Antwort.
    Hier der Code meiner anfänglichen Überlegung:

                                    ListenElem *ptr1;
                                    ListenElem *ptr2;
                                    ListenElem *temp1;
                                    ListenElem *temp2;
    
                                     if(Personen.anz != 0 && Personen.anz >1)  //ist in der Liste mindestens 2 drin?
                                     {
                                         ptr1 = Personen.root;
                                         ptr2 = ptr1->next;
                                         temp1 = ptr1;
                                         temp2 = ptr2;
    
                                         //wird solange durchlaufen bis ptr2 das Ende ist
                                         while (ptr2 != NULL)
                                         {
                                            //folgende Schleife schiebt den ptr2 so weit nach vorne, bis er der Anfang der Liste ist oder vor ihm der name kleiner
                                            while (strcmp(ptr1->Listenperson.Name, ptr2->Listenperson.Name)>0) //Tritt ein, wenn ptr2.Name kleiner als ptr1.Name ist
                                            {
                                                temp1 = ptr1;
                                                temp2 = ptr2;
                                                ptr1->prev = temp2->prev;
                                                ptr1->next = temp2->next;
    
                                                ptr2->prev = temp1->prev;
                                                ptr2->next = temp1->next;
    
                                                if (Personen.root == ptr1)    //Für den Fall, dass der ptr1 der Beginn der Liste ist und mit ptr2 vertauscht werden muss
                                                {
                                                    Personen.root = ptr2;
                                                }
                                                if (Personen.end == ptr2)     //Für den Fall, dass ptr2 das Ende der Liste ist und nun mit ptr1 vertauscht werden soll
                                                {
                                                    Personen.end = ptr1;
                                                }
    
                                                if (!ptr2->prev)
                                                {
                                                    ptr1 = ptr2->prev;
                                                }
                                                ptr1 = ptr2->prev;
                                            }
    
                                         }
    

  • Mod

    • Erklär mal, was Zeile 36-40 machen. Erst beschreibst du, was du erreichen möchtest, dann beschreibst du unabhängig davon, was der Code macht.
    • Angenommen ptr2 steht nun an der richtigen Stelle. Wie geht es weiter?
    • Zusatzfrage: Wie weißt du, ob du fertig bist?

    Allgemein ist es ein gutes Vorgehen in der Programmierung, wenn man Probleme in kleinere, logisch abgeschlossene Teilprobleme zerlegt. Dann kann man diese einmal richtig lösen und immer wieder neu benutzen. Hier zum Beispiel benutzt du das Vertauschen von zwei Listenelementen. Das ist ein Schritt, der mit dem Sortieren erst einmal nicht direkt zu tun hat, aber dein Sortierprogramm ist total unübersichtlich, weil es zusätzlich auch noch Listenelemente vertauschen muss, und man muss bei der Fehlersuche genau hingucken, ob dieser Teil so auch richtig ist und welchen Wert welche Variable an welcher Stelle genau hat, was unnötig Gehirnressourcen belegt. Ebenso Vergleiche, etc. Wäre viel einfacher, wenn du so etwas schreiben könntest in der Art von

    while(less(ptr, ptr2))
       swap(ptr1, ptr2);
    

    Dann könntest du dich stärker auf das wesentliche konzentrieren und kannst besser erkennen, woran es hakt.

    Das hier ist ja auch sicher nicht der erste Teil der Aufgabe, dass ihr direkt sortieren sollt. Vertauschen von zwei Elementen ist sicher vorher schon dran gekommen. Nutze die Lösungen der vorherigen Aufgaben!

    Man muss natürlich sicher sein, dass diese Teillösungen auch richtig sind. Aber da die Teilprobleme kleiner und einfacher sind, ist das leichter als wenn man alles auf einmal gleichzeitig lösen muss



  • Vielen Dank für die Hilfe @SeppJ
    Grundlegend möchte ich den ptr2 so oft mit ptr1 tauschen, bis ptr2 an der richtigen Stelle in der Liste steht. Quasi von links nach rechts tauschen, wenn die Liste links beginnt. (Hoffe man kann meinen Gedanken folgen)
    Ich merke gerade, Zeile 36 bis 40 ist Unsinn.

    Das ist mein Problem, dass ich nicht weiß wie ich weiter machen kann, wenn ptr2 an der richtigen Stelle ist.

    Das ist ein guter Tipp, mit den kleineren Programmen. Wir hatten aber keine Aufgabe zum umtauschen der Elemente.


  • Mod

    @Dome204 sagte in Doppelt verkettete Liste sortieren:

    Das ist mein Problem, dass ich nicht weiß wie ich weiter machen kann, wenn ptr2 an der richtigen Stelle ist.

    Nun, es gibt ja sicher einen Grund, wieso ich die Frage gestellt habe 🙂
    Was fallen dir denn für Möglichkeiten ein? Bevor du konkret wirst, solltest du darüber nachdenken, was überhaupt der nächste große Meilenstein wäre. Wie du dahin kommst, kann man sich leichter ausmalen, wenn man erst einmal weiß, wo man hin will.



  • @SeppJ sagte in Doppelt verkettete Liste sortieren:

    was überhaupt der nächste große Meilenstein wäre

    Ein größerer Meilenstein wäre, überhaupt keine verk. Listen zu benutzen, denn Sortieren für verk.Listen - bzw. der Masochismus verlangenden Implementierung - ist ein Beleg für deren Sinnfreihalt außerhalb von akademischen Kontexten.


  • Mod

    @Wutz sagte in Doppelt verkettete Liste sortieren:

    @SeppJ sagte in Doppelt verkettete Liste sortieren:

    was überhaupt der nächste große Meilenstein wäre

    Ein größerer Meilenstein wäre, überhaupt keine verk. Listen zu benutzen, denn Sortieren für verk.Listen - bzw. der Masochismus verlangenden Implementierung - ist ein Beleg für deren Sinnfreihalt außerhalb von akademischen Kontexten.

    Im Prinzip ja, aber dies ist ja wohl ziemlich eindeutig ein akademischer Kontext. Ich habe ja auch absichtlich versucht den Fragesteller hin zu den allgemein anwendbaren Fähigkeiten zu lenken, etwa die Abstraktion des Designs. Irgendeine verkette Liste hin zu hacken ist nutzlos. Aber eine richtig gut gemachte verkettete Liste zu schreiben lehrt einen, wie man gut programmiert. Gerade bei verketten Listen ist der Unterschied zwischen einer guten und einer schlechten Implementierung ziemlich hoch. Hoch ist auch der Schmerz, wenn man der schlechten Implementierung neue Funktion hinzufügen will. Daher gar kein so schlechtes Beispiel, wenn man Lernende motivieren will, was gutes Design in der Praxis bringt. Und es eignet sich gut, die Leute auszusieben, die es nicht können.



  • Vielen Dank für eure Hilfe.
    Hier ist meine Funktion, um zwei Elemente zu vertauschen:

    int switchelem (Liste *liste, ListenElem *ptr1, ListenElem *ptr2) //Funktion um zwei Elemente zu vertauschen
    {
        ListenElem *temp1 = ptr1;
        ListenElem *temp2 = ptr2;
    
        if (liste->root == ptr1)
        {
            liste->root = ptr2;
        }
        if (liste->root == ptr2)
        {
            liste->root = ptr1;
        }
        if (liste->end == ptr1)
        {
            liste->end = ptr2;
        }
        if (liste->end == ptr2)
        {
            liste->end = ptr1;
        }
        ptr1->next = temp2->next;
        ptr1->prev = temp2->prev;
        ptr2->next = temp1->next;
        ptr2->prev = temp1->prev;
        return 0;
    

    Und hier nun der Programmabschnitt um die Liste zu sortieren:

    if(!strncmp(nachricht, "Name", 4))//Wenn nachricht "Name" ist, liefert die funktion eine 0 weshalb das if ausgeführt wird
                                {
                                    ListenElem *ptr1;
                                    ListenElem *ptr2;
                                     if(Personen.anz != 0 && Personen.anz >1)  //ist in der Liste mindestens 2 drin?
                                     {
                                        ptr1 = Personen.root;
    
                                        if (ptr1->next)
                                        {
                                            ptr2 = ptr1->next;
                                        }
    
                                         //wird solange durchlaufen bis ptr2 das Ende ist
                                         while (ptr2 != NULL)
                                         {
                                            //folgende Schleife schiebt den ptr2 so weit nach vorne, bis er der Anfang der Liste ist oder vor ihm der name kleiner
                                            while (strcmp(ptr1->Listenperson.Name, ptr2->Listenperson.Name)>0) //Tritt ein, wenn ptr2.Name kleiner als ptr1.Name ist
                                            {
                                                switchelem(&Personen, ptr1, ptr2);
                                                if (Personen.root != ptr2)
                                                {
                                                    ptr1 = ptr2->prev;
                                                }
                                            }
                                            ptr1 = ptr2;
                                            ptr2 = ptr1->next;
    
                                         }
    
    
                                       memset(nachricht, 0, sizeof(nachricht));
                                       strcpy(nachricht, "Erfolgreich nach Namen sortiert");
                                     }
                                     else
                                     {
                                         memset(nachricht, 0, sizeof(nachricht));
                                         strcpy(nachricht, "!NICHT! Erfolgreich nach Namen sortiert");
                                     }
    

    Allerdings wird die while-Schleife in der der Name verglichen wird nicht verlassen. Kann mir da jemand weiterhelfen und sagen warum?


  • Mod

    Was ist nachricht? Warum erwartest du, dass das jemals auf "Name" zeigt? Welche while-Schleife?

    Was soll das mit dem Namen und der Nachricht überhaupt mit Sortieren zu tun haben? Hast du direkt schon alles über spezialisierte Funktionen wieder vergessen?



  • Das ganze soll ein TCP/IP Programm sein und der aktuelle Programm-Code ist auf der Serverseite.
    "nachricht" wird immer vom Client empfangen und dann verglichen, nach welchem Kriterium sortiert werden soll.
    Wenn "Name" eingegeben wird, soll danach sortiert werden.
    Diese while-Schleife:

     while (strcmp(ptr1->Listenperson.Name, ptr2->Listenperson.Name)>0) //Tritt ein, wenn ptr2.Name kleiner als ptr1.Name ist
                                            {
                                                switchelem(&Personen, ptr1, ptr2);
                                                if (Personen.root != ptr2)
                                                {
                                                    ptr1 = ptr2->prev;
                                                }
                                            }
    

  • Mod

    @Dome204 sagte in Doppelt verkettete Liste sortieren:

    Diese while-Schleife:

     while (strcmp(ptr1->Listenperson.Name, ptr2->Listenperson.Name)>0) //Tritt ein, wenn ptr2.Name kleiner als ptr1.Name ist
                                            {
                                                switchelem(&Personen, ptr1, ptr2);
                                                if (Personen.root != ptr2)
                                                {
                                                    ptr1 = ptr2->prev;
                                                }
                                            }
    

    Szenario: Die Bedingung im if ist unwahr (ptr2 steht nun ganz vorne). Was soll nun passieren? Was passiert tatsächlich?

    Das ganze soll ein TCP/IP Programm sein und der aktuelle Programm-Code ist auf der Serverseite.
    "nachricht" wird immer vom Client empfangen und dann verglichen, nach welchem Kriterium sortiert werden soll.
    Wenn "Name" eingegeben wird, soll danach sortiert werden.

    Das mit Abstraktion und spezialisierten Funktionen habe ich nicht zum Spaß gesagt. Dein Code oben ist zu über 50% Rauschen, das überhaupt nichts mit Sortieren zu tun hat, aber man muss trotzdem alles lesen und verstehen, um deine Sortierfunktion zu korrigieren. Das ist nicht gut!



  • @SeppJ Vielen Dank für deine Hilfe.
    Leider kann ich deinen Worten nur schwer folgen. Ich weiß leider nicht wie ich weiter vorgehen kann.
    Kannst du mir weitere Tipps geben, die für Laien verständlich sind?


  • Mod

    Du deckst den Fall nicht richtig ab, wenn du ganz vorne angekommen bist. Du prüfst zwar, ob du ganz vorne bist, aber wenn du dort bist, dann machst du nichts. Daher haben ptr1 und ptr2 immer noch den gleichen Wert wie vor dem Tausch, und die Laufbedingung ist weiterhin wahr. Daher bricht die Schleife nie ab.


Anmelden zum Antworten