C ++ - Segmentierungsfehler in der bedingten Anweisung der Analyse der verknüpften Liste der while-Schleife zum geordneten Einfügen

Question

Dies ist eine Klassenzuweisung zum geordneten Einfügen in eine sortierte verknüpfte Liste.Ich habe den Zugriff auf Nullzeiger vermieden und einige Zeilen Debugging-Ausgabe hinzugefügt, um den Seg-Fehler auf die bedingte Anweisung der while-Schleife selbst zu beschränken.

Ich kann einen Knoten zur leeren Liste hinzufügen und Knoten mit kleineren Schlüsseln zum Kopf der Liste hinzufügen, aber beim Hinzufügen eines Schlüssels am Ende einer nicht leeren Liste tritt ein Seg-Fehler auf.Wie in der Debug-Ausgabe angezeigt, läuft die problematische while-Schleife erfolgreich ab, bis Cursor-> next== NULL angezeigt wird.Das ist, wenn es den Seg-Fehler wirft.Ich versuche nicht, auf den leeren Zeiger zuzugreifen, soweit ich das beurteilen kann.Ich bin wirklich ziemlich ratlos und würde mich über jede Hilfe freuen.Danke!

Ich habe die störende Zeile im folgenden Code angegeben.

// Headers
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

struct Node {
  int id;
  string initials;
  double score;
  Node* next;
};
const int ESC = -9999;
const int ID_LIMIT = 1000000000;

int main(){  
  // initialize variables
  int temp_id = 0;  // temporary input
  Node* Start=NULL; // first node in linked list

  // get input until escape value is entered or input stream fails
  while ( temp_id != ESC && !cin.fail() ){
    cout << "\nPlease enter the student id, or "
         << ESC << " to finish inputing: ";
    cin >> temp_id;
    if ( temp_id >=0 && temp_id < ID_LIMIT ) { 
      // if valid input, continue input & create node
      string temp_inits;
      double temp_score;
      cout << "Please enter the student initials: " ;
      cin >> temp_inits;
      cout << "Please enter the student's test score: " ;
      cin >> temp_score;

      // create new node with input values
      Node* temp = new Node;
      temp->id = temp_id;
      temp->initials = temp_inits;
      temp->score = temp_score;
      temp->next = NULL;

      // TASK 4: SORTED INPUT
      if ( Start == NULL ) {  // if first node to be input
        Start = temp;         // point the first pointer to it
      }else{                  // otherwise
        if( temp->id < Start->id ){  // if new node should go before Start,
          temp->next = Start;        // move start after temp
          Start = temp;              // and reassign Start
        }else{
          Node* cursor = Start; // parse list for proper place or end
          cout << "\nDEBUG: while ( cursor-id:" << cursor->id ;
          cout << " < temp-id:" << temp->id;
          cout << " && cursor-next:" << cursor->next << " != NULL )";
// I THINK THE NEXT LINE IS THE CULPRIT
          while ( cursor->id < temp->id && cursor->next != NULL ) {
            cout << "\nDEBUG: { old cursor:" << cursor->id ;
            cursor = cursor->next;
            cout << ", new cursor:" << cursor->id << " }";
            cout << "\nDEBUG: while ( cursor-id:" << cursor->id ;
            cout << " < temp-id:" << temp->id;
            cout << " && cursor-next:" << cursor->next << " != NULL )";
          }
          cout << "\nDEBUG: insert temp-id:" << temp->id 
               << " after cursor-id:" << cursor->id ;
          temp->next = cursor->next;
          cursor->next = temp;  // inject new node into list.
          cursor = temp->next;
          cout << " before id " << cursor->id;
        }
      }
      cout << "Node with id=" << temp->id << ", initials=" << temp->initials 
           << ", and test score=" << temp->score << " added to the list.\n";

    }else{ // if invalid input & not escape value, print error
      if ( temp_id != ESC ) cout << "!!! Invalid input !!!\n";
    }   
  }

  return 0;
}

Ausgabe:

Please enter the student id, or -9999 to finish inputing: 654
Please enter the student initials: abc
Please enter the student's test score: 99.9
Node with id=654, initials=abc, and test score=99.9 added to the list.

Please enter the student id, or -9999 to finish inputing: 312
Please enter the student initials: qwe
Please enter the student's test score: 54.8
Node with id=312, initials=qwe, and test score=54.8 added to the list.

Please enter the student id, or -9999 to finish inputing: 987
Please enter the student initials: rty
Please enter the student's test score: 87.5

DEBUG: while ( cursor-id:312 < temp-id:987 && cursor-next:0x1c26040 != NULL )
DEBUG: { old cursor:312, new cursor:654 }
DEBUG: while ( cursor-id:654 < temp-id:987 && cursor-next:0 != NULL )
Segmentation fault

Ich habe auch die Schleife mit ( ... cursor->next != 0 ) und ( ... cursor->next ) ausprobiert

Answer 1

Das Problem liegt darin, dass Sie die while () - Schleife verlassen haben:

  1>    temp->next = cursor->next;
  2>    cursor->next = temp;  // inject new node into list.
  3>    cursor = temp->next;
  4>    cout << " before id " << cursor->id;

Sie erreichen die obigen Zeilen mit dem Cursor-> next== null (Ende der Liste) und temp-> next ist ebenfalls null.Zeile 1 macht daher in diesem Fall nichts.Zeile 2 kopiert die Adresse des Temps in den Cursor-> next.An diesem Punkt haben wir:

temp: Die ursprüngliche Adresse von temp, temp-> next== NULL Cursor: Originaladresse des Cursors, Cursor-> next== Originaladresse des Temps

Dann kopieren Sie temp-> next in den Cursor (uhoh!), aber temp-> next ist null, sodass der Cursor jetzt null ist. Wenn Sie also Zeile 4 ausführen und Cursor-> ID abrufen, wird versucht, "null-> ID" zu lesen, und es stürzt ab.

Answer 2

  while ( cursor->id < temp->id && cursor->next != NULL )
  {
      cursor = cursor->next;
  }

  temp->next = cursor->next;
  cursor->next = temp;  // inject new node into list.
  cursor = temp->next;
  cout << " before id " << cursor->id;

Wenn die Schleife ausgeführt wird, bis cursor auf den letzten Knoten zeigt, ist cursor->next null.Nach dem Einfügen des neuen Knotens (es scheint mir an der falschen Stelle, aber egal) ist der neue Knoten der letzte und hat temp->next als Nullzeiger.Dann setzt cursor = temp->next cursor auf null, und die folgende Debug-Ausgabeanweisung, die cursor über cursor->id dereferenziert, stürzt ab.

Natürlich sollte ich es in einem Debugger ausführen.

Und das ist ein starker Vorschlag, den ich für Sie habe: Verwenden Sie den Debugger, nicht nur das Gehirn.:-)

Zweiter starker Vorschlag: Verwenden Sie die Abstraktion, benennen Sie fast alles, was in Sicht ist .Was bedeutet, kleine Funktionen zu definieren, z.zum Einfügen von Listen.Dann ist es viel einfacher, Dinge zu analysieren.