48 - Estructuras dinámicas: 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)
lista ordenada
listaOrdenada.Insertar(5)
lista ordenada
listaOrdenada.Insertar(7)
lista ordenada
listaOrdenada.Insertar(50)
lista ordenada

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:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ListaOrdenada1
{
    class ListaOrdenada
    {
        class Nodo
        {
            public int info;
            public Nodo sig;
        }

        private Nodo raiz;

        public ListaOrdenada()
        {
            raiz = null;
        }

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

        public void Imprimir() 
        {
            Nodo reco = raiz;
            while (reco != null) 
            {
                Console.Write (reco.info + "-");
                reco = reco.sig;
            }
            Console.WriteLine();
        }


        static void Main(string[] args)
        {
            ListaOrdenada lo = new ListaOrdenada();
            lo.Insertar(10);
            lo.Insertar(5);
            lo.Insertar(7);
            lo.Insertar(50);
            lo.Imprimir();
            Console.ReadKey();
        }
    }
}

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, lo insertamos inmediatamente:

            if (raiz==null) 
            {
                raiz=nuevo;
            } 
            else 
            {

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

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