Doppelt verkettete Liste sortieren



  • 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.


Log in to reply