41 - Estructuras dinámicas:en C++ 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:

listaOrdenada->insertar(10);

listaOrdenada->insertar(5)

listaOrdenada->insertar(7)

listaOrdenada->insertar(50)

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

Programa:

#include <iostream>

using namespace std;

class ListaGenericaOrdenada {
private:
    class Nodo {
    public:
        int info;
        Nodo *sig;
    };

    Nodo *raiz;
public:
    ListaGenericaOrdenada();
    ~ListaGenericaOrdenada();    
    void insertar(int x);
    void imprimir();
};

ListaGenericaOrdenada::ListaGenericaOrdenada()
{
    raiz = NULL;
}

ListaGenericaOrdenada::~ListaGenericaOrdenada()
{
    Nodo *reco = raiz;
    Nodo *bor;
    while (reco != NULL)
    {
        bor = reco;
        reco = reco->sig;
        delete bor;
    }
}

void ListaGenericaOrdenada::insertar(int x)
{
    Nodo *nuevo = new Nodo();
    nuevo->info = x;
    if (raiz == NULL) 
    {
        raiz = nuevo;
    }
    else 
    {
        if (x<raiz->info) 
        {
            nuevo->sig = raiz;
            raiz = nuevo;
        }
        else 
        {
            Nodo *reco = raiz;
            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;
            }
        }
    }
}

void ListaGenericaOrdenada::imprimir()
{
    Nodo *reco = raiz;
    cout << "Listado completo.\n";
    while (reco != NULL)
    {
        cout << reco->info << "-";
        reco = reco->sig;
    }
    cout << "\n";
}


int main()
{
    ListaGenericaOrdenada *lista = new ListaGenericaOrdenada();
    lista->insertar(10);
    lista->insertar(5);
    lista->insertar(7);
    lista->insertar(50);
    lista->imprimir();
    delete lista;
    return 0;
}

Este proyecto lo puede descargar en un zip desde este enlace : ListaGenericaOrdenada.zip

El método insertar lo resolvemos de la siguiente forma:

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

    Nodo *nuevo = new Nodo();
    nuevo->info = x;
 

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)

            Nodo *reco = raiz;
            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;
            }

Retornar