C: Erstellung einer sortierten Liste durch Überprüfung von 2 Werten

Question

Ich bin neu in C, also sei geduldig mit mir, wenn du einen wirklich newbiefehler in meinem Code siehst!

Im Rahmen einer Hausaufgabe muss ich eine sortierte Liste erstellen, um einige Daten zu speichern. Was ich bisher getan habe, ist die Erstellung der Struktur, die jeden Knoten der Liste darstellt (firstNode ist eine globale Variable, die auf den ersten Knoten der Liste zeigt):

typedef struct Node {
    struct Node *next;
    int id;
    int value;
}Node;

Node *firstNode = NULL;

Danach habe ich eine Funktion erstellt, die einen neuen Knoten in die Liste einfügt, indem sie die Werte der Knoten überprüft. Knoten mit kleineren Werten sollten vor anderen stehen. Also habe ich das gemacht:

void addNewNode(int nodeId, int nodeValue) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    Node *temp, *tempPrev;
    newNode->id = nodeId;
    newNode->value = nodeValue;

    if(firstNode == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
    }
    temp = firstNode;
    tempPrev = NULL;
    while(temp->value < newNode->value) {
        tempPrev = temp;
        temp = temp->next;
    }
    if(tempPrev == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
    } 
    else {
        tempPrev->next = newNode;
        newNode->next = temp;
    }
}

Das Problem mit dem obigen Code ist, dass das Programm manchmal abstürzt, aber ich kann den Fehler nicht finden!

Was ich als nächstes versuche, ist, dass, wenn einige Knoten den gleichen Wert haben, sie nach ihrer ID geordnet werden (Knoten mit kleineren IDs kommen zuerst). Wie kann ich das machen? Ich bin wirklich verwirrt!

Answer 1

Das Programm stürzt ab, weil in der Bedingung der while-Schleife nicht überprüft wird, ob temp gleich NULL ist. Mit anderen Worten, wenn Sie versuchen, einen neuen Knoten mit einem höheren Wert als alle bereits in der Liste vorhandenen einzufügen, erreicht temp das Ende der Liste (also temp gleich NULL) und Sie versuchen, den Wert dieses Knotens abzurufen! Eine Lösung wäre also:

while(temp!=NULL && temp->value>newNode->value)
{
    ....
}

Was die id der Knoten betrifft, könnten Sie Ihre while-Schleifenbedingung wie folgt erweitern:

while(temp!=NULL && (temp->valuevalue || (temp->value==newNode->value && temp->idid))
{
    ....
}

Außerdem ist die erste If-Anweisung, in der überprüft wird, ob firstNode NULL ist, in Ihrem Fall nicht notwendig. Wenn es NULL ist, wird das Programm nicht in die while-Schleife gelangen und direkt zur ersten If-Anweisung nach der while-Schleife gehen.

Übrigens, schöner Code für einen neuen Programmierer in C :-)

Answer 2

1.

if(firstNode == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
        return; // Fertig mit dem Einsetzen des ersten Knotens...muss nicht fortgesetzt werden.
    }

2.

// Stellen Sie sicher, dass temp nicht null ist, um auf dessen Wert zugreifen zu können.
while(temp && (temp->value < nodeId->value)) {
        tempPrev = temp;
        temp = temp->next;
    }

Answer 3

Erstens, haben Sie dort nodeID -> Wert. NodeID ist eine ganze Zahl, also wird das nicht funktionieren.

Answer 4

Als Methode zum Debuggen würde ich ein einfaches Testharness erstellen. Mit anderen Worten, ein Testprogramm, das Sie schreiben, das alle gängigen Szenarien durchläuft, die Ihnen einfallen (auch bekannt als Unittesting). Jeder Unittest überprüft, ob er ordnungsgemäß ausgeführt wird und den erwarteten Output generiert. Auf diese Weise können Sie sicher sein, dass, wenn alles in Ordnung ist, Sie bereit sind. Wenn ein Unittest fehlschlägt, wissen Sie genau, was kaputt ist.

Answer 5

Ich würde vorschlagen, ein paar Testfälle zu erstellen, die Ihre Randbedingungen überprüfen (z. B. ein Element zu einer leeren Liste hinzufügen; ein Element hinzufügen, das am Anfang einer vorhandenen Liste landen sollte; ein Element hinzufügen, das am Ende einer vorhandenen Liste landen sollte; ein Element hinzufügen, das irgendwo in der Mitte einer vorhandenen Liste landen sollte). Erstellen Sie eine "print"-Funktion, die die Elemente in der Liste zur Konsole für Debugging ausgibt. Das wird Ihnen zumindest helfen, den Kontext Ihres Absturzes einzugrenzen. Eine Möglichkeit (ich weiß nicht, wie viele Elemente Sie hinzufügen) ist, dass das Programm den Speicher erschöpft und malloc fehlschlägt. Sie können das überprüfen, weil ich glaube, dass malloc NULL zurückgibt, wenn es nicht gelingt, den erforderlichen Speicher zuzuweisen.

Node *newNode = (Node*) malloc(sizeof(Node)); 
if(newNode == NULL)
{
  printf("Kein Speicher mehr verfügbar!");
  return;
}