Ver Mensaje Individual
  #25 (permalink)  
Antiguo 16/10/2005, 23:21
Avatar de stock
stock
 
Fecha de Ingreso: junio-2004
Ubicación: Monterrey NL
Mensajes: 2.390
Antigüedad: 20 años
Puntos: 53
Tema: Estructura de datos

Pregunta: Que son y como se comen las Lista dinámicas simples??

Respuesta: Ok, pongo este FAQ para beneficio de todos!! Una lista simple es una estructura de datos donde los elementos de esta están enlazados en forma secuencial, a diferencia de las pilas y las colas, puedes acceder a cualquier elemento de la lista. Para agregar nuevos elementos ala lista hay diferentes maneras, por ejemplo puedes agregar un elemento al final o al principio de la lista, o también siguiendo un orden ascendente o descendente de los elementos, en fin, eso depende de lo que necesites hacer con las listas, el criterio de acceso también es de acuerdo a las necesidades.



Lo que haremos en esta ocasión será hacer una lista con la opción de agregar nodos al final, podremos sacar los nodos dándole el numero de nodo que querremos sacar, un método para imprimir la lista, un método que nos dirá cuantos nodos tenemos, un método que eliminara un nodo de la lista.



OK, aquí los métodos:

add(Nodo nodo) -> Agrega nodos al final de la lista
get(int index) -> Obtener el nodo de acuerdo al indice requerido
size() -> nos dira el numero de nodos que hay en la lista
print() -> imprimira la lista
remove(int index) -> Eliminara un nodo de la lista


Ok, nuestra lista será algo asi:

7 -> 2-> 5 ->1 -> null
^
Root

Si queremos agregar el número 10, la lista quedaría así:


7 -> 2-> 5 ->1 -> 10 -> null
^
Root

Ok, pasemos a JAVA, vamos a lista con información de clientes. Aquí el Nodo.java

Código PHP:
/*
* Author: Crysfel Villa
* Created: Sunday, October 17, 2005 11:20:45 PM
* Modified: Sunday, October 17, 2005 11:20:45 PM
*/ 


public class Nodo{
    
//puntero al siguiente nodo
    
public Nodo ptr;
    
// puedes poner todos los datos que quieras
    
public String nombre;
    public 
String apellido;
    public 
int edad;
    
//constructor por default es NULL, porque sera el ultimo de la lista
    
public Nodo(){
        
ptr null;
    }



OK, ahora hagamos la lista.java

Código PHP:


/*
* Author: Crysfel Villa
* Created: Sunday, October 17, 2005 11:30:26 PM
* Modified: Sunday, October 17, 2005 11:30:26 PM
*/ 

public class Lista{
    
//el puntero al primer elemento
    
private Nodo root;
    
//el total de nodos en la lista
    
private int numNodos;

    
//el constructor inicializa las variables
    
public Lista(){
        
root null;
        
numNodos 0;
    }

    
//Agrega un nodo a la lista
    
public void add(Nodo newNodo){
        
//puntero temporal para recorreme en la lista
        
Nodo tmp root;

        
//si la lista esta vacia
        
if(tmp==null){
            
//lo agregamos al root
            
root newNodo;
        }else{
            
//de lo contrario nos recorremos hasta el ultimo
            
while(tmp.ptr!=null)
                
tmp tmp.ptr;
            
//en el ultimo hacemos el enlace 
            
tmp.ptr newNodo;
        }
        
//incrementamos el numero de nodos
        
numNodos++;
    }
    
    
//regresa un nodo dela lista deacuerdo al indice dado
    
public Nodo get(int index){
        
Nodo info null;
        
//revisamos que el indice este dentro del rango
        
if(index numNodos && index >= 0){
            
//puntero para recorrenos desde el principio hasta el indice
            
Nodo tmp root;
            
//revisamos que la lista no este vacia
            
if(tmp==null)
                
System.out.println("La lista esta vacia");
            else if(
index == numNodos-1){
                
//si es el ultimo nodo el que queremos, nos movemos hasta el final
                
while(tmp.ptr!=null)
                    
tmp tmp.ptr;
                
//hacemos la copia
                
info tmp;
            }else{
                
//nos recorremos hasta donde el indice nos permita
                
int i=0;
                do{
                    
info tmp;
                    
tmp tmp.ptr;
                    
i++;
                }while(
i<=index);
            }
        }else{
            
System.out.println("Fuera del rango");
        }
        
//regresamos el nodo
        
return info;
    }
    
    
//elimina un nodo deacuerdo al indice dado
    
public void remove(int index){
        
//revisamos que el indice este dentro del rango
        
if(index numNodos && index >= 0){
            
//puntero para movernos en la lista
            
Nodo tmp root;
            
//ravisamos que no este vacia
            
if(tmp==null)
                
System.out.println("La lista esta vacia");
            else if(
index == numNodos-&& index>0){
                
//si es el ultimo nodo de la lista
                
while(tmp.ptr.ptr!=null)
                    
//nos movemos hasta uno antes del final
                    
tmp tmp.ptr;
                
//eliminamos el enlace
                
tmp.ptr null;
                
//decrementamos el total de nodos
                
numNodos--;
                
System.out.println("Borrado con exito!!");
            }else{
                
//si es el primer nodo
                
if(index == 0){
                    
//movemos el root al siguiente nodo, entonces el primero lo perdemos
                    
root tmp.ptr;
                }else{
                    
//nos movemos hasta un nodo antes del indice
                    
int i=0;
                    while(
i<index-1){
                        
tmp tmp.ptr;
                        
i++;
                    }
                    
//enlazamos el nodo anterior al indice, haciendo una especie de salto
                    //al nodo que querremos eliminar, de tal manera que el que queremos eliminar
                    //quede afuera de la lista
                    
tmp.ptr tmp.ptr.ptr;
                }
                
//decrementamos el total de nodos
                
numNodos--;
                
System.out.println("Borrado con exito");
            }
        }else{
            
System.out.println("Fuera del rango");
        }
    }
    
    
//regresa el numero de nodos en la lista
    
public int size(){
        return 
numNodos;
    }
    
    
//imprime la lista de nodos
    
public void print(){
        
//puntero que se movera sobre la lista
        
Nodo tmp root;
        
//sercirandonos que no este vacia
        
if(tmp==null){
            
System.out.println("La lista esta vacia :(");
        }else{
            
//nos movemos hasta el final imprimiendo nodo por nodo
            
int i=0;
            do{
                
System.out.println("-------------");
                
System.out.println("Indice-> "+i);
                
System.out.println(tmp.nombre);
                
System.out.println(tmp.apellido);
                
System.out.println(tmp.edad);
                
System.out.println("------\\/------");
                
tmp tmp.ptr;
                
i++;
            }while(
tmp.ptr!=null);
            
//imprimimos el ultimo nodo que visitamos
            
System.out.println("-------------");
            
System.out.println("Indice-> "+i);
            
System.out.println(tmp.nombre);
            
System.out.println(tmp.apellido);
            
System.out.println(tmp.edad);
            
System.out.println("------\\/------");
        }
    }



ahora, vamos a hacer una aplicacion que utilice nuestra lista, Implementa.java

Código PHP:
/*
* Author: Crysfel Villa
* Created: Sunday, October 17, 2005 11:58:15 PM
* Modified: Sunday, October 17, 2005 11:58:15 PM
*/ 

public class Implementa {
    public static 
void main(String arg[]){
        
Lista lista = new Lista();
        
//llenamos la lista
        
for(int i=0;i<10;i++){
            
Nodo nodo = new Nodo();
            
nodo.nombre "nombre"+i;
            
nodo.apellido "apellidos";
            
nodo.edad 10+i;
            
//vamos agregandole nodos
            
lista.add(nodo);
        }
        
        
System.out.println("elementos-> "+lista.size());
        
lista.print();
        
lista.remove(9);
        
lista.remove(0);
        
lista.remove(10);
        
lista.remove(5);
        
System.out.println("elementos-> "+lista.size());
        
lista.print();
        
System.out.println("----------");
        
Nodo sacado lista.get(2);
        if(
sacado!=nullSystem.out.println(sacado.edad);
        
sacado lista.get(9);
        if(
sacado!=nullSystem.out.println(sacado.edad);
        
sacado lista.get(0);
        if(
sacado!=nullSystem.out.println(sacado.edad);
        
sacado lista.get(100);
        if(
sacado!=nullSystem.out.println(sacado.edad);
        
System.out.println("elementos-> "+lista.size());
    }

Bueno, espero que halla quedado claro el concepto y que le pueda servir a alguien!!

have funnnnnnnnn

Última edición por stock; 24/03/2006 a las 13:12