SoloCodigo

Programación General => Java => Mensaje iniciado por: Diamante_Loco en Sábado 11 de Julio de 2009, 03:35

Título: Ordenar e invertir una lista ligada
Publicado por: Diamante_Loco en Sábado 11 de Julio de 2009, 03:35

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.  

Título: Re: Ordenar e invertir una lista ligada
Publicado por: robertogt en Viernes 14 de Agosto de 2009, 09:40

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.