C: creazione dell'elenco ordinato controllando 2 valori

Question

Sono nuovo di C quindi abbi pazienza con me se vedi qualche errore di newbie nel mio codice!

Come parte di un compito a casa, ho bisogno di creare un elenco ordinato per memorizzare alcuni dati. Quello che ho fatto finora è quello di creare la struct che rappresenterà ogni nodo della lista (firstNode è una variabile globale che fa riferimento al primo nodo della lista):

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

Node *firstNode = NULL; 

Dopo che ho creato una funzione che inserisce un nuovo nodo nell'elenco controllando i valori dei nodi. I nodi con valori più piccoli dovrebbero essere prima degli altri. Quindi quello che ho fatto è stato questo:

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; 
    } 
} 

Il problema con il codice di cui sopra è che a volte il programma si blocca, ma non riesco a trovare l'errore!

Inoltre, quello che sto cercando di fare dopo è, se alcuni nodi hanno lo stesso valore, quindi sono ordinati in base al loro id (i nodi con ID più piccoli vengono prima). Come posso fare questo? Sono veramente confuso!

Answer 1

il programma si blocca a causa della condizione del ciclo while, non controlli se la temperatura è uguale a NULL. In altre parole, se si tenta di inserire un nuovo nodo con un valore maggiore rispetto a tutti gli altri già presenti nell'elenco, temp raggiunge la fine dell'elenco (quindi temp equivale a NULL) e si tenta di ottenere il valore di quel nodo ! Quindi, una correzione potrebbe essere:

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

Per quanto riguarda l'id dei nodi, si potrebbe estendere la vostra mentre condizione del ciclo come questo:

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

Inoltre, il primo se-dichiarazione, in cui si controlla se firstNode è NULL, non è necessario nel tuo caso. Se è NULL, il programma non entrerà nel ciclo while e passerà direttamente alla prima istruzione if dopo il ciclo while.

A proposito, bel codice per un nuovo programmatore in C :-)

Answer 2

1.

if(firstNode == NULL) { 
     newNode->next = firstNode; 
     firstNode = newNode; 
     return; // done with inserting the first node...need not continue. 
    } 

2.

// ensure temp is not null only then access its value. 
while(temp && (temp->value < nodeId->value)) { 
     tempPrev = temp; 
     temp = temp->next; 
    } 

Answer 3

per una cosa, voi hanno NodeID -> valore in là. NodeID è un int, quindi questo non funzionerà.

Answer 4

Come metodo di debug, vorrei creare un semplice cablaggio di test. In altre parole, un programma di test che scrivi che attraversa tutti gli scenari comuni a cui puoi pensare (ovvero test delle unità). Ogni unit test controlla per assicurarsi che funzioni correttamente e generi l'output atteso. In questo modo, puoi essere sicuro che se tutto va bene, sei a posto. Se un test unitario fallisce, sai esattamente cosa è rotto.

Answer 5

Vorrei suggerire la costruzione di un paio di casi di test che controllano le condizioni al contorno (ad esempio, aggiungere un elemento a una lista vuota, aggiungere un elemento che dovrebbe finire in primo piano in un elenco esistente, aggiungere un elemento che va a finire alla fine di un elenco esistente, aggiungi un elemento che dovrebbe finire da qualche parte nel mezzo di un elenco esistente). Crea una funzione di "stampa" che stamperà gli elementi nell'elenco alla console per il debug. Questo almeno ti aiuterà a restringere il contesto del tuo incidente. Una possibilità (non so quante aggiunte si sta facendo) è che il programma esaurisce la memoria e malloc fallisce. È possibile verificarlo perché penso che malloc restituisca NULL se non riesce ad allocare la memoria richiesta.

Node *newNode = (Node*) malloc(sizeof(Node)); 
if(newNode == NULL) 
{ 
    printf("Out of Memory!"); 
    return; 
}