C: Creación de lista ordenada al marcar 2 valores

Question

Soy nuevo en C así que sea paciente conmigo si ve algún error realmente novato en mi código.

Como parte de una tarea, necesito crear una lista ordenada para almacenar algunos datos. Lo que he hecho hasta ahora es crear la estructura que representará a cada nodo de la lista (firstNode es una variable global que apunta al primer nodo de la lista):

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

Node *firstNode = NULL; 

Después de eso he creado una función que inserta un nuevo nodo en la lista al verificar los valores de los nodos. Los nodos con valores más pequeños deben estar antes que otros. Así que lo que hice fue lo siguiente:

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

El problema con el código anterior es que a veces los errores en el programa, pero no puedo encontrar el error!

Además, lo que intento hacer a continuación es que, si algunos nodos tienen el mismo valor, se ordenan de acuerdo con su id. (Los nodos con ID más pequeños son los primeros). ¿Cómo puedo hacer esto? ¡Estoy realmente confundido!

Answer 1

El programa se bloquea debido a la condición en bucle while, que no comprueban si la temperatura es igual a NULL. En otras palabras, si intenta insertar un nuevo nodo con un valor mayor que todos los demás que ya están dentro de la lista, la temperatura llega al final de la lista (por lo que la temperatura es igual a NULL) e intenta obtener el valor de ese nodo ! Por lo que una solución sería:

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

En cuanto a la identificación de los nodos, se podría ampliar su condición de bucle, mientras que de esta manera:

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

Además, la primera sentencia if, donde se comprueba si firstNode es NULL, no es necesario en su caso. Si es NULL, el programa no entrará en el ciclo while y irá directamente a la primera instrucción if después del ciclo while.

Por cierto, el código agradable para un nuevo programador en 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

por un lado, que tienen nodeID -> valor en ese país. NodeID es un int, por lo que esto no funcionará.

Answer 4

Como método de depuración, crearía un arnés de prueba simple. En otras palabras, un programa de prueba que escribe recorre todos los escenarios comunes que puede pensar (también conocido como prueba de unidad). Cada prueba de unidad comprueba para asegurarse de que se ejecuta correctamente y genera el resultado esperado. De esta manera, puede estar seguro de que si todo funciona bien, estará listo. Si falla una prueba unitaria, sabrá exactamente qué está roto.

Answer 5

Sugeriría construir un par de casos de prueba que verifiquen las condiciones de contorno (por ejemplo, agregar un elemento a una lista vacía, agregar un elemento que debe aparecer al principio de una lista existente, agregar un elemento que termine al final de una lista existente, agregue un elemento que debería terminar en algún lugar en el medio de una lista existente). Haga una función de "impresión" que imprimirá los elementos en la lista a la consola para la depuración. Eso al menos lo ayudará a reducir el contexto de su caída. Una posibilidad (no sé cuántas adiciones está haciendo) es que el programa se queda sin memoria y malloc falla. Puede verificarlo porque creo que malloc devuelve NULL si no puede asignar la memoria requerida.

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