45 - Estructuras dinámicas en C: Listas genéricas ordenadas

 Listas genéricas ordenadas

Una lista genérica es ordenada si cuando insertamos información en la lista queda ordenada respecto al campo info (sea de menor a mayor o a la inversa)

Ejemplo:

insertar(10);

insertar(5)

insertar(7)

insertar(50)

Podemos observar que si recorremos la lista podemos acceder a la información de menor a mayor.
No se requiere una función para ordenar la lista, sino que siempre permanece ordenada, ya que se inserta ordenada.

Programa: programa168.c

Ver video

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct nodo {
    int info;
    struct nodo *sig;
};

struct nodo *raiz=NULL;


void liberar()
{
    struct nodo *reco = raiz;
    struct nodo *bor;
    while (reco != NULL)
    {
        bor = reco;
        reco = reco->sig;
        free(bor);
    }
}

int vacia()
{
    if (raiz == NULL)
        return 1;
    else
        return 0;
}


void imprimir()
{
    struct nodo *reco=raiz;
    printf("Lista completa.\n");
    while (reco!=NULL)
    {
        printf("%i ",reco->info);
        reco=reco->sig;
    }
    printf("\n");
}


void insertar(int x)
{
    struct nodo *nuevo;
    nuevo=malloc(sizeof(struct nodo));
    nuevo->info = x;
    nuevo->sig=NULL;
    if (raiz == NULL)
    {
        raiz = nuevo;
    }
    else
    {
        if (x<raiz->info)
        {
            nuevo->sig = raiz;
            raiz = nuevo;
        }
        else
        {
            struct nodo *reco = raiz;
            struct nodo *atras = raiz;
            while (x >= reco->info && reco->sig != NULL)
            {
                atras = reco;
                reco = reco->sig;
            }
            if (x >= reco->info)
            {
                reco->sig = nuevo;
            }
            else
            {
                nuevo->sig = reco;
                atras->sig = nuevo;
            }
        }
    }
}


int main()
{
    insertar(10);
    insertar(5);
    insertar(7);
    insertar(50);
    imprimir();
    liberar();
    getch();
    return 0;
}

La función insertar la resolvemos de la siguiente forma:

Creamos primeramente el nodo, ya que siempre se insertará la información en la lista:

    struct nodo *nuevo;
    nuevo=malloc(sizeof(struct nodo));
    nuevo->info = x;
    nuevo->sig=NULL;
 

Se puede presentar las siguientes situaciones, si está vacía la lista, lo insertamos inmediatamente:

    if (raiz == NULL) 
    {
        raiz = nuevo;
    }

Si no está vacía la lista, verificamos si lo debemos insertar en la primera posición de la lista (analizamos si la información a insertar es menor a lo apuntado por raiz en el campo info):

        if (x<raiz->info) 
        {
            nuevo->sig = raiz;
            raiz = nuevo;
        }

Sino analizamos si lo debemos insertar en medio o al final de la lista.
Mientras la información a insertar sea mayor o igual a la información del nodo que visitamos ( x>=reco->info) y no lleguemos al final de la lista (reco->sig!=NULL) avanzamos reco al siguiente nodo y fijamos un puntero en el nodo anterior (atras)

            struct nodo *reco = raiz;
            struct nodo *atras = raiz;
            while (x >= reco->info && reco->sig != NULL)
            {
                atras = reco;
                reco = reco->sig;
            }

Cuando salimos del while si la condición (x>=reco->info) continua siendo verdadera significa que se inserta al final de la lista, en caso contrario se inserta en medio de la lista:

            if (x >= reco->info) 
            {
                reco->sig = nuevo;
            }
            else
            {
                nuevo->sig = reco;
                atras->sig = nuevo;
            }

Problema propuesto

• Se tiene la siguiente declaración de nodo:

  struct nodo {
      char usuario[51];
      struct nodo *sig;
  };
  

  Implementar una lista ordenada con respecto al campo usuario.

  Ver video

SOLUCION 

programa169.c

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

struct nodo {
    char usuario[41];
    struct nodo *sig;
};

struct nodo *raiz=NULL;


void liberar()
{
    struct nodo *reco = raiz;
    struct nodo *bor;
    while (reco != NULL)
    {
        bor = reco;
        reco = reco->sig;
        free(bor);
    }
}

int vacia()
{
    if (raiz == NULL)
        return 1;
    else
        return 0;
}


void imprimir()
{
    struct nodo *reco=raiz;
    printf("Lista completa.\n");
    while (reco!=NULL)
    {
        printf("%s -",reco->usuario);
        reco=reco->sig;
    }
    printf("\n");
}


void insertar(char *x)
{
    struct nodo *nuevo;
    nuevo=malloc(sizeof(struct nodo));
    strcpy(nuevo->usuario,x);
    nuevo->sig=NULL;
    if (raiz == NULL)
    {
        raiz = nuevo;
    }
    else
    {
        if (strcmp(x,raiz->usuario)<0)
        {
            nuevo->sig = raiz;
            raiz = nuevo;
        }
        else
        {
            struct nodo *reco = raiz;
            struct nodo *atras = raiz;
            while (strcmp(x,reco->usuario)>0 && reco->sig != NULL)
            {
                atras = reco;
                reco = reco->sig;
            }
            if (strcmp(x,reco->usuario)>0)
            {
                reco->sig = nuevo;
            }
            else
            {
                nuevo->sig = reco;
                atras->sig = nuevo;
            }
        }
    }
}


int main()
{
    insertar("juan");
    insertar("ana");
    insertar("luis");
    insertar("carlos");
    imprimir();
    liberar();
    getch();
    return 0;
}