• Domingo 14 de Abril de 2024, 03:00

Autor Tema:  Ordenar e invertir una lista ligada  (Leído 7961 veces)

Diamante_Loco

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
Ordenar e invertir una lista ligada
« en: Sábado 11 de Julio de 2009, 03:35 »
0
Hola buenas tardes/noches
ps mi duda es la siguiente:

Tengo este programa de Listas Doblemente Ligadas
Inserta e elimina nodos
imprime la lista de izquierda a derecha.

lo q quiero que tmb haga es ordenar la lista
por ejemplo si esta es la lista:
4 5 1 0 8
q la ordene d menor a mayor:
0 1 4 5 8
pero no tengo mucha idea d como hacerloo

la otra duda es que invierta la lista
por ejemplo si esta es la lista:
4 5 1 0 8

al momento de invertir la lista quedaria asi:
8 0 1 5 4

pero tampoco me salee Confused

Les pongo el codigo que tengo :

espero q me puedan ayudar!

Código: Java
  1.  
  2.  
  3.  import java.io.*;
  4.  
  5. class Nodo
  6. {
  7.    public int info;
  8.    public Nodo sig, ant;
  9.    
  10.    public Nodo(int x)
  11.    {
  12.       info = x;
  13.       sig = ant = null;
  14.    }
  15. }
  16.  
  17. class ListaDoblementeLigada
  18. {
  19.    private Nodo inicio, fin;
  20.  
  21.     public ListaDoblementeLigada()
  22.     {
  23.        inicio = fin = null;
  24.     }
  25.    
  26.     public void inserta(int x)
  27.     {
  28.        Nodo temp = new Nodo(x);
  29.        if(inicio == null && fin == null)
  30.           inicio = fin = temp;
  31.           else
  32.           {
  33.              temp.ant = fin;
  34.              fin.sig = temp;
  35.              fin = temp;
  36.           }
  37.     }
  38.    
  39.     public void recorreIzq()
  40.     {
  41.        Nodo aux;
  42.        aux = inicio;
  43.        while(aux != null)
  44.        {
  45.           System.out.print(aux.info + "   ");
  46.           aux = aux.sig;
  47.        }
  48.     }
  49.    
  50.        
  51.     public void elimina()
  52.     {
  53.        Nodo aux, aux2;
  54.        aux = aux2 = fin;
  55.        fin = fin.ant;
  56.        aux2 = fin;
  57.        System.out.println("Dato eliminado: " + aux.info);
  58.        aux2.sig = null;
  59.           aux.ant = null;
  60.     }
  61.    
  62.     public void menu()
  63.     {
  64.        System.out.println("");
  65.        System.out.println("Menu");
  66.        System.out.println("1.- Insertar");
  67.        System.out.println("2.- Recorrer de Izquierda a Derecha");
  68.        System.out.println("3.- Invertir lista");
  69.        System.out.println("4.- Eliminar");
  70.        System.out.println("5.- Salir");
  71.        System.out.print("Opcion: ");
  72.        
  73.     }
  74.     public static void main(String a[])throws IOException
  75.     {
  76.        InputStreamReader isr = new InputStreamReader(System.in);
  77.        BufferedReader entrada = new BufferedReader(isr);
  78.        
  79.        int cantidad, opc, dato;
  80.        ListaDoblementeLigada L1 = new ListaDoblementeLigada();
  81.        do
  82.        {
  83.        
  84.        L1.menu();
  85.        
  86.        opc = Integer.parseInt(entrada.readLine());
  87.        
  88.        if (opc == 1)
  89.        {
  90.        
  91.        System.out.print("Cantidad de nodos de la lista 1: ");
  92.        cantidad = Integer.parseInt(entrada.readLine());
  93.        for(int i = 1; i <= cantidad; i++)
  94.            {
  95.           System.out.print("Da el dato "+ i + ": ");
  96.           dato = Integer.parseInt(entrada.readLine());
  97.          
  98.           L1.inserta(dato);
  99.           }
  100.        }
  101.        
  102.        if(opc == 2)L1.recorreIzq();
  103.        if(opc == 4)L1.elimina();
  104.        }while(opc != 5)  ;
  105.     }
  106.    
  107.    
  108. }
  109.  
  110.  
  111.  

robertogt

  • Miembro activo
  • **
  • Mensajes: 97
  • Nacionalidad: gt
    • Ver Perfil
    • http://robertux.wordpress.com
Re: Ordenar e invertir una lista ligada
« Respuesta #1 en: Viernes 14 de Agosto de 2009, 09:40 »
0
Para invertir la lista lo que tenés que hacer es parecido a lo que tienes en

Código: Java
  1.  public void recorreIzq()
  2.      {
  3.         Nodo aux;
  4.         aux = inicio;
  5.         while(aux != null)
  6.         {
  7.            System.out.print(aux.info + "   ");
  8.            aux = aux.sig;
  9.         }
  10.      }
  11.  

para recorrerla de derecha a izquierda seria algo asi

Código: Java
  1.  public void recorreDerecha()
  2.      {
  3.         Nodo aux;
  4.         aux = fin;
  5.         while(aux != null)
  6.         {
  7.            System.out.print(aux.info + "   ");
  8.            aux = aux.ant;
  9.         }
  10.      }
  11.  

Para ordenar la lista de menor a mayor tendrías que usar algun algoritmo, como el de burbuja para ordenar los números, recorriendo varias veces la lista e insertando los números en otra lista, podriá ser una solución.
Un dia sin sol es como, ya sabes, ... noche