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