Markus Pitha: C++ Verkettete Liste sortieren (sehr knifflig)

Hallo,
ich habe eine Logikfrage. Ich tüftle schon seit 2 Tagen an einer Sortierfunktion für eine verkettete Liste herum aber es scheint nicht ganz zu funktionieren.
Ziel ist es, dass nach einem Inhalt der Elemente (Katalognummern) sortiert wird, wobei das Element gleich richtig in der Liste eingefügt werden soll, nachdem die Daten über die Tasatur eingelesen wurden, sodass die Elemente nach Katalognummern ansteigend sortiert werden. Das Kuriose ist, dass es nur dann, und wirklich nur dann nicht funktioniert, wenn ich das erste Mal eine kleinere Katalognummer einlese, als die, die bereits vorhanden sind. Dieses Element wird nämlich an 2. Stelle von "vorne" eingefügt, also wenn zB 6 und 8 bereits exisitiert, wird 2 zwischen 6 und 8 eingehängt und nicht vor 6. Wenn ich dann weiter Daten einlesen, wird ab diesem Zeitpunkt richtig sortiert. Hier ist mal der relevante Codeabschnitt:
.
.
schueler *kopfzeiger;
.
.

void hinzufuegen()    {
char temp[20];
int katnr, aktuelle_katalognr; //aktuelle_katalognr wird beim vergleichen benötigt, katnr zum Einlesen.
schueler *marker_schueler;
schueler *aktuell;
schueler *neuer_schueler;

std::cout << "Katalognummer: ";
std::cin >> katnr;

while (checkkatnr(katnr) != 0)    { //Check ob Katalognummer bereits exisitert.
   std::cout << "Diese Katalognummer existiert bereits!\n";
   std::cout << "Katalognummer: ";
   std::cin >> katnr;
   }
  neuer_schueler = new schueler; //Neue Instanz erzeugen.
  neuer_schueler->katalognummer = katnr;
         std::cout << "Vorname: ";
         std::cin >> temp;
         strcpy(neuer_schueler->vorname, temp);
         std::cout << "Nachname: ";
         std::cin >> temp;
         strcpy(neuer_schueler->nachname, temp);
         std::cout <<"\n";

aktuell = kopfzeiger;
marker_schueler = kopfzeiger;
   if (aktuell != NULL)    {
      while (aktuell != NULL)    {
      aktuelle_katalognr = aktuell->katalognummer;
            if (aktuelle_katalognr < katnr)    {
            marker_schueler = aktuell;
            }
       aktuell = aktuell->next;
       }
   neuer_schueler->next = marker_schueler->next;
   marker_schueler->next = neuer_schueler;
   }  else  {
   neuer_schueler->next = kopfzeiger;
   kopfzeiger = neuer_schueler;
   }

}

Hier habe ich einen Mitschnitt des seltsamen Verhaltens:

http://tools.acid4u.com/prog.txt

Ich hoffe jemand weiß, was zu tun ist, sodass die Liste richtig sortiert wird.

Markus.

--
sh:( fo:| ch:? rl:( br:> n4:( ie:{ mo:) va:) de:] zu:) fl:( ss:| ls:] js:|
  1. wenn zB 6 und 8 bereits exisitiert, wird 2 zwischen 6 und 8 eingehängt und nicht vor 6.

    aktuell = kopfzeiger;
    marker_schueler = kopfzeiger;
    if (aktuell != NULL) {
       while (aktuell != NULL) {
          aktuelle_katalognr = aktuell->katalognummer;
          if (aktuelle_katalognr < katnr) {
             marker_schueler = aktuell;
          }
          aktuell = aktuell->next;
       }
       neuer_schueler->next = marker_schueler->next;
       marker_schueler->next = neuer_schueler;

    Wie kannst Du etwas vor dem ersten Objekt (im Beispiel: 6) eintragen, wenn Du immer nur nach einem Objekt einfügst (letzte Zeile, 6->next = 2)?

    Davon unabhängig ist es Zeitverschwendung, die while-Schleife immer bis zum Ende der Liste durchzulaufen anstatt sie beim ersten Treffer zu beenden.

    if (kopfzeiger == NULL) { // Liste ist noch leer
       kopfzeiger = neuer_schueler;
    }
    else {
       letzter = NULL;        // Vorgänger von aktuell
       aktuell = kopfzeiger;

    while ((aktuell != NULL) && (aktuell->katalognummer < neuer_schueler->katalognummer)) {
          letzter = aktuell;
          aktuell = aktuell->next;
       }

    // Aktuell zeigt jetzt auf das erste Element, das gleich oder größer als neuer_schueler ist, oder ist NULL, falls am Ende der Liste. neuer_schueler muss vor diesem Element eingehängt werden.

    neuer_schueler->next = aktuell;
       if (letzter != NULL) { // neuer_schueler wird nicht erster Eintrag
          letzter->next = neuer_schueler;
       }
       else { // kein Vorgänger, neuer_schueler wird erster Eintrag
          kopfzeiger = neuer_schueler;
       }
    }

    So ungefähr. Ich persönlich stehe ja auf doppelt verkettete Listen, die sind etwas praktischer.

    1. Hallo,
      vielen Dank, es funktkioniert endlich. Ich habe allerdings noch eine Frage dazu:

      if (kopfzeiger == NULL) { // Liste ist noch leer
         kopfzeiger = neuer_schueler;
      }

      Warum muss ich hier nicht zusätzlich vor kopfzeiger = neuer_schueler "neuer_schueler->next = kopfzeiger"; schreiben (Da der Wert von Kopfzeiger noch NULL ist). Ich dachte, dass das letzte Element stets auf NULL zeigen muss, und da kopfzeiger bis dato noch NULL ist, weise ich es dem next Zeiger des neuen Elements zu (welches hier natürlich das allererste Element der Liste ist)
      Also ich stelle mir das so vor:

      Vorher:
      _____
      KOPF|
      NEXT|-> NULL
      ____|

      Jetzt neuen Schüler einhängen, in dem ich zuerst dem neuen Schüler das Ende (NULL) zuweise:
      _____
      KOPF|
      NEXT|--------> NULL
      ____|         ^
                    |
      _____________ |
      NEUERSCHÜLER| |
              NEXT|--
      ____________|

      Jetzt Kopfzeiger auf neuen Schüler richten:
      _____
      KOPF|
      NEXT|--+                      NULL
      ____|  |                      ^
             |      _____________   |
             |_____>|NEUERSCHÜLER|  |
                    |        NEXT|--
                    |____________|

      Nachher:

      ____
      KOPF|   ____________
      NEXT|->|NEUERSCHÜLER|
      ____|  |        NEXT|->NULL
             |____________|

      Markus.

      --
      sh:( fo:| ch:? rl:( br:> n4:( ie:{ mo:) va:) de:] zu:) fl:( ss:| ls:] js:|
      1. Vorher:
        _____
        KOPF|
        NEXT|-> NULL
        ____|

        Ganz einfach, es gibt kein kopf->next.
        Kopf ist ein Zeiger AUF das nächste Element, deshalb brauchst du kein kopf->next.
        Wenn du ein neues Element an eine Liste anhängen willst in der noch kein Element existiert (kopf == null), musst du so vorgehen:

        pAllok *T_Schueler = new(T_Schueler);
        pAllok->next = NULL;
        pKopf = pAllok;

        Fertisch.

        1. Hi,

          pAllok *T_Schueler = new(T_Schueler);
          pAllok->next = NULL;
          pKopf = pAllok;

          ..womit ich aber wieder bei der ursprünglichen Frage wäre. Warum funktioniert das Programm trotzdem, obwohl diese zeile fehlt?

          » pAllok->next = NULL; (bzw ..->next = kopfzeiger, weil dieser ja am Anfang noch NULL ist)

          Markus.

          --
          sh:( fo:| ch:? rl:( br:> n4:( ie:{ mo:) va:) de:] zu:) fl:( ss:| ls:] js:|
          1. ..womit ich aber wieder bei der ursprünglichen Frage wäre. Warum funktioniert das Programm trotzdem, obwohl diese zeile fehlt?

            IMHO Zufall.
            Mit new(T_Schueler) wird ja neuer Speicher allokiert, zufälligerweise ist der Speicherbereich dann eben NULL, könnte auch anders kommen.

      2. if (kopfzeiger == NULL) { // Liste ist noch leer
           kopfzeiger = neuer_schueler;
        }

        Warum muss ich hier nicht zusätzlich vor kopfzeiger = neuer_schueler "neuer_schueler->next = kopfzeiger"; schreiben (Da der Wert von Kopfzeiger noch NULL ist).

        Da ich ganz kühn davon ausgehe, dass Du Deine Schüler beim Erzeugen reinlichst initialisierst und neuer_schueler->next deshalb bereits NULL ist, habe ich diese Zeile weggelassen.
        Diese Arbeitseinsparung kann man aber in der Tat bemängeln, das gibt Abzüge in der B-Note. Asche auf mein Haupt.

        Ich dachte, dass das letzte Element stets auf NULL zeigen muss, und da kopfzeiger bis dato noch NULL ist, weise ich es dem next Zeiger des neuen Elements zu

        Mein Rat: Tue sowas niemals. Wenn Du einer Variable den Wert X zuweisen willst, dann weise ihr den Wert X zu und nicht den Inhalt einer anderen Variable, von der Du annimmst, sie würde X enthalten. Natürlich kannst Du jetzt einwenden, dass es in diesem Fall eindeutig ist, dass die andere Variable X enthält, und das ist auch vollkommen richtig. Aber Du weißt nie, wie Du Deinen Code in Zukunft umstellst, solche Sachen sind die Keimzellen der beknacktesten Fehler und können in den Wahnsinn treiben.
        Außerdem sparst Du ein paar Takte, wenn Du den Prozessor den Speicher direkt mit einem fest im Maschinencode verankerten Wert beschreiben lässt anstatt ihn zu nötigen, diesen Wert erst noch aus einer anderen Speicherzelle laden zu müssen. Für das Nullsetzen von Speicher gibt es obendrein meist gesonderte, noch kürzere Befehle. Nicht, dass das in heutigen Zeiten lebensnotwendig wäre, aber wer hat schon etwas gegen schnellen Code, wenn er so einfach zu erreichen ist?

        Also, füge ein 'neuer_schueler->next = NULL;' ein.

        1. Hi,
          danke nochmal, alles klar.

          Markus.

          --
          sh:( fo:| ch:? rl:( br:> n4:( ie:{ mo:) va:) de:] zu:) fl:( ss:| ls:] js:|
    2. Davon unabhängig ist es Zeitverschwendung, die while-Schleife immer bis zum Ende der Liste durchzulaufen anstatt sie beim ersten Treffer zu beenden.

      je nach größe der liste ist auch ein sequentielles suchen mit abbruch nicht das gelbe vom ei. bei größeren listen wäre eine suche mit dem halbschrittverfahren die bessere lösung.