Una lista que se mantiene ordenada

Si cada dato entra en su sitio, la lista nunca hay que ordenarla.

1Por qué

En la lección 17 añadías siempre por delante, y la lista salía al revés del orden en que entraban los datos. Sirve, pero para casi nada de lo que se pide en un taller.

Para que salga ordenada hay que meter cada dato en su sitio: avanzar hasta encontrar el primero que sea mayor, y colarse justo antes. El problema es lo que eso significa en C.

Colar un nodo entre dos exige cambiar el sig del anterior. Y si el sitio resulta ser el principio, no hay anterior: hay que cambiar la cabeza. Escrito de la forma obvia, salen dos casos distintos y un if para separarlos — que es donde se cuelan la mitad de los errores.

Hay una forma de que sea un solo caso, y es bonita: en vez de ir guardando el nodo anterior, se va guardando la dirección del puntero que hay que cambiar. Al principio esa dirección es la de la cabeza; después, la del sig de cada nodo. Los dos son lo mismo —un puntero a nodo que hay que reapuntar— y por eso el código no necesita distinguirlos.

Es la idea de la lección 21 usada a fondo. Si p = &(*p)->sig te marea, léelo despacio: p deja de apuntar a la cabeza y pasa a apuntar al sig del primero. Sigue siendo la dirección del puntero que toca cambiar.

2Míralo andar

Este programa funciona. Léelo, y después ejecútalo sin cambiar nada.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *sig;
} Nodo;
 
void insertar(Nodo **p, int x)
{
    while (*p != NULL && (*p)->valor < x)
        p = &(*p)->sig;
 
    Nodo *n = malloc(sizeof(Nodo));
    n->valor = x;
    n->sig = *p;
    *p = n;
}
 
int main(void)
{
    Nodo *lista = NULL;
 
    insertar(&lista, 5);
    insertar(&lista, 2);
    insertar(&lista, 9);
 
    for (Nodo *q = lista; q != NULL; q = q->sig)
        printf("%d ", q->valor);
    printf("\n");
 
    while (lista != NULL)
    {
        Nodo *s = lista->sig;
        free(lista);
        lista = s;
    }
    return 0;
}

línea 11
Avanza mientras lo que hay sea menor. Al salir, *p es el primero que va DESPUÉS del nuevo.
línea 12
Aquí está el truco. p pasa a ser la dirección del sig del nodo actual. Sigue siendo «el puntero que hay que cambiar», por eso no hacen falta dos casos.
línea 16
El nuevo apunta a lo que venía; y la línea de abajo hace que lo anterior apunte al nuevo. En ese orden, siempre.
línea 22
Entra el 2, que es menor que el 5: se cuela al principio. Sin la idea de arriba, este sería el caso especial.

3Ahora tú

A esta inserción le falta avanzar, así que mete todo al principio. Escribe la línea que avanza, para que salga: 2 5 9

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Nodo {
    int valor;
    struct Nodo *sig;
} Nodo;
 
void insertar(Nodo **p, int x)
{
    while (*p != NULL && (*p)->valor < x)
    {
        
    }
 
    Nodo *n = malloc(sizeof(Nodo));
    n->valor = x;
    n->sig = *p;
    *p = n;
}
 
int main(void)
{
    Nodo *lista = NULL;
 
    insertar(&lista, 5);
    insertar(&lista, 2);
    insertar(&lista, 9);
 
    for (Nodo *q = lista; q != NULL; q = q->sig)
        printf("%d ", q->valor);
    printf("\n");
 
    while (lista != NULL)
    {
        Nodo *s = lista->sig;
        free(lista);
        lista = s;
    }
    return 0;
}

↖︎ Tu línea va aquí. Tiene que mover p al puntero siguiente, no al nodo siguiente.

Una lista que se mantiene ordenada

1Por qué

2Míralo andar

3Ahora tú

Ejecutar

Lo que dice tu programa

Qué pasó

4Qué guarda tu programa

Memoria