Webmaster Workers utiliza cookies. Lea nuestra Política de Privacidad para obtener más información. Para eliminar este mensaje, haga clic en el siguiente botón: Acepto el uso de cookies


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



Opciones
Estadísticas
Creado 01.01.1970 a las 00:00 hs
Categoría C#

  • Medallas
  • 0
    Favoritos
  • 9692
    Visitas
  • 0
    Puntos
  • 0
    Seguidores
Comentarios
0
Cargando comentarios espera un momento...
No tienes permisos para comentar.

Para poder comentar necesitas estar Registrado. O.. ya tienes usuario? Logueate!
Autor del post
Ver perfil de Administrador Administrador
Hombre Administrador  Mensaje
43 1,352 1
Medallas
No tiene medallas
Tags
Posts relacionados