miércoles, 15 de febrero de 2017

LISTAS DOBLES

En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se muestra en la figura.


Creación de la clase Nodo
Comenzaremos creando la clase Nodo con sus dos enlaces.

/**
 *
 * @author Jhon
 */
public class Nodo {
public int info;
public Nodo sgte;
public Nodo ante;
public Nodo(){

}
public Nodo (int x){
this.info = x;
this.sgte = null;
this.ante = null;
}
}

Como podemos apreciar la clase nodo tiene dos punteros los cuales están inicializados con nullsgte que apunta al ultimo nodo, y ante que apunta a primer nodo.



Operaciones con listas enlazadas:
Se pueden realizar muchas operaciones con estas listas, según sea el caso que se lo requiera aqui les presentamos las mas importantes:

Insertar un elemento al inicio de la lista.
Insertar un elemento al final de la lista.
Insertar después.
Visualizar los elementos de la lista.
Buscar.
Eliminar.
Insertar Inicio: Declaramos el nodo cab(cabezera) y Nodo ptr(puntero), luego los inicializamos a null.


private Nodo cab;
private Nodo ptr;
public ListaDoblementeEnlazada()
{
cab=ptr=null;
}
}

Declaramos un método para conocer si la lista esta vacía;


boolean estaVacia() {
boolean vacia = false;
if (cab == null)
{
vacia = true;
}
return vacia;
}

Método para insertar al inicio.

public ListaDoblementeEnlazada InsertarInicio(int x)
{
Nodo nuevo = new Nodo(x);
if (estaVacia()) {
cab = ptr = nuevo;
} else {
nuevo.sgte =cab;
cab.ante = nuevo;
cab = nuevo;
}
return this;
}

Insertar fin:

public ListaDoblementeEnlazada InsertarFin(int x)
{
Nodo nuevo = new Nodo(x);
if (estaVacia()) {
cab = ptr = nuevo;
} else {
ptr.sgte = nuevo;
nuevo.ante = ptr;
ptr = nuevo;
}
return this;
}

Insertar Después:

public ListaDoblementeEnlazada InsertarDespues(Nodo anterior ,int x)
{
Nodo nuevo = new Nodo(x);
nuevo.sgte = anterior.sgte;
if (anterior.sgte != null)
{
anterior.sgte.ante = nuevo;
}
anterior.sgte = nuevo;
nuevo.ante = anterior;
return this;
}

Imprimir la lista: Se declara un nodo n al cual se le asigna la cabecera de la lista, con la estructura de control while se va imprimiendo todos los nodos asta que la cabecera sea nula.

public void Visualizar()
{
Nodo n;
n = cab;
while (n != null)
{
System.out.print("<- n.info="">");
n = n.sgte;
}
}

Eliminar Nodo:

public void Eliminar(int entrada)
{
Nodo actual;
boolean encontrado = false;
actual = cab;
while ((actual != null) && (!encontrado))
{
encontrado = (actual.info == entrada);
if (!encontrado)
{
actual = actual.sgte;
}
}
if (actual != null){//distingue entre nodo cabecera o resto de la lista
if (actual == cab)
{
cab = actual.sgte;
if (actual.sgte != null)
{
actual.sgte.ante = null;
}
}
else if (actual.sgte != null) // No es el último nodo
{
actual.ante.sgte = actual.sgte;
actual.sgte.ante = actual.ante;
}
else // último nodo
{
actual.ante.sgte = null;
}
if (actual == ptr)
{
ptr = actual.ante;
}
actual = null;
}
}

Buscar Nodo: Se recorre la lista comparando si el valor ingresado(dato), es igual a alguno valore de la lista, en caso de encontrarlo lo retorna.

public Nodo Buscar(int dato)
{
Nodo indice;
for (indice = cab; indice != null; indice = indice.sgte)
{
if (dato == indice.info)
{
return indice;
}
}
return null;
}

Referencia concepto : Leonel Belduma http://iccbeldumaleonel.blogspot.pe/
Publicado por en No hay comentarios:
LISTAS SIMPLES 

Las listas son estructuras de datos que permiten tener cierta flexibilidad en su manejo, pueden crecer o acortarse según se lo requiera, existen varias formas de implementar una lista en Java en este caso se presenta un ejemplo en código utilizando punteros mediante la referencia a objetos.

Las listas básicamente se forman del enlace de nodos los cuales funcionan como contenedores para almacenar el valor y enlace al siguiente nodo.

ESTRUCTURA DE UN NODO

Valor: valor del dato a guardar.
Enlace: apunta a la dirección en memoria del siguiente nodo.

LISTA SIMPLEMENTE ENLAZADA:




Características:

1) El último nodo de la lista no apunta a ningún a ninguno (null).
2) Se accede a la lista mediante el primer nodo o también llamado inicio de la lista.
3) No tiene acceso aleatorio es decir para acceder a un valor se debe recorrer toda la lista.

Ejemplo :

CLASE NODO

package Trabajo;

/**
 *
 * @author Jhon
 */
public class nodo {
    
    private int valor;
    
    private nodo siguiente;
   
    public void nodo(){
        this.valor = 0;
        this.siguiente = null;
    }
    
        
    public int getValor() {
        return valor;
    }

    public void setValor(int valor) {
        this.valor = valor;
    }

    public nodo getSiguiente() {
        return siguiente;
    }

    public void setSiguiente(nodo siguiente) {
        this.siguiente = siguiente;
    }  
}

CLASE LISTA

package Trabajo;
/**
 *
 * @author Jhon
 */
public class Lista {
     
    private nodo inicio;    
    private int tamanio;
    
    
    public void Lista(){
        inicio = null;
        tamanio = 0;
    }
   
    public boolean esVacia(){
        return inicio == null;
    }    
    public int getTamanio(){
        return tamanio;
    }
    
    public void agregarAlFinal(int valor){        
        nodo nuevo = new nodo();        
        nuevo.setValor(valor);        
        if (esVacia()) {           
            inicio = nuevo;        
        } else{           
            nodo aux = inicio;          
            while(aux.getSiguiente() != null){
                aux = aux.getSiguiente();
            }           
            aux.setSiguiente(nuevo);
        }        
        tamanio++;
    }
    
    
    public void agregarAlInicio(int valor){       
        nodo nuevo = new nodo();       
        nuevo.setValor(valor);
       
        if (esVacia()) {           
            inicio = nuevo;      
        } else{           
            nuevo.setSiguiente(inicio);            
            inicio = nuevo;
        }        
        tamanio++;
    }
    
    
    public void insertarPorReferencia(int referencia, int valor){        
        nodo nuevo = new nodo();       
        nuevo.setValor(valor);
       
        if (!esVacia()) {           
            if (buscar(referencia)) {                
                nodo aux = inicio;                
                while (aux.getValor() != referencia) {
                    aux = aux.getSiguiente();
                }                
                nodo siguiente = aux.getSiguiente();                
                aux.setSiguiente(nuevo);               
                nuevo.setSiguiente(siguiente);  
                
                tamanio++;
            }
        }
    }
   
    
    public void insrtarPorPosicion(int posicion, int valor){        
        if(posicion>=0 && posicion<=tamanio){
            nodo nuevo = new nodo();
            nuevo.setValor(valor);           
            if(posicion == 0){                
                nuevo.setSiguiente(inicio);
                inicio = nuevo;
            }
            else{                
                if(posicion == tamanio){
                    nodo aux = inicio;                   
                    while(aux.getSiguiente() != null){
                        aux = aux.getSiguiente();
                    }                   
                    aux.setSiguiente(nuevo);              
                }
                else{                    
                    nodo aux = inicio;                    
                    for (int i = 0; i < (posicion-1); i++) {
                        aux = aux.getSiguiente();
                    }                   
                    nodo siguiente = aux.getSiguiente();                   
                    aux.setSiguiente(nuevo);                    
                    nuevo.setSiguiente(siguiente);
                }            }           
            tamanio++;
        }
    }
   
    public int getValor(int posicion) throws Exception{        
        if(posicion>=0 && posicion<tamanio){            
            if (posicion == 0) {                
                return inicio.getValor();
            }else{               
                nodo aux = inicio;                
                for (int i = 0; i < posicion; i++) {
                    aux = aux.getSiguiente();
                }                
                return aux.getValor();
            }        
        } else {
            throw new Exception("Posicion inexistente en la lista.");
        }
    }
    
    public boolean buscar(int referencia){        
        nodo aux = inicio;       
        boolean encontrado = false;        
        while(aux != null && encontrado != true){            
            if (referencia == aux.getValor()){               
                encontrado = true;
            }
            else{               
                aux = aux.getSiguiente();
            }
        }       
        return encontrado;
    }
    
    public int getPosicion(int referencia) throws Exception{        
        if (buscar(referencia)) {            
            nodo aux = inicio;           
            int cont = 0;            
            while(referencia != aux.getValor()){               
                cont ++;                
                aux = aux.getSiguiente();
            }           
            return cont;       
        } else {
            throw new Exception("Valor inexistente en la lista.");
        }
    }
    
    public void editarPorReferencia(int referencia, int valor){
       
        if (buscar(referencia)) {           
            nodo aux = inicio;            
            while(aux.getValor() != referencia){
                aux = aux.getSiguiente();
            }           
            aux.setValor(valor);
        }
    }
   
    public void editarPorPosicion(int posicion , int valor){        
        if(posicion>=0 && posicion<tamanio){            
            if(posicion == 0){                
                inicio.setValor(valor);
            }
            else{               
                nodo aux = inicio;               
                for (int i = 0; i < posicion; i++) {
                    aux = aux.getSiguiente();
                }               
                aux.setValor(valor);
            }
        }
    }
    
    public void removerPorReferencia(int referencia){        
        if (buscar(referencia)) {            
            if (inicio.getValor() == referencia) {                
                inicio = inicio.getSiguiente();
            } else{                
                nodo aux = inicio;                
                while(aux.getSiguiente().getValor() != referencia){
                    aux = aux.getSiguiente();
                }               
                nodo siguiente = aux.getSiguiente().getSiguiente();                
                aux.setSiguiente(siguiente);  
            }           
            tamanio--;
        }
    }   

      
    public void removerPorPosicion(int posicion){       
        if(posicion>=0 && posicion<tamanio){           
            if(posicion == 0){                
                inicio = inicio.getSiguiente();
            }          
            else{              
                nodo aux = inicio;               
                for (int i = 0; i < posicion-1; i++) {
                    aux = aux.getSiguiente();
                }               
                nodo siguiente = aux.getSiguiente();               
                aux.setSiguiente(siguiente.getSiguiente());
            }
            
            tamanio--;
        }
    }
        
    public void listar(){       
        if (!esVacia()) {           
            nodo aux = inicio;            
            int i = 0;            
            while(aux != null){               
                System.out.print(i + ".[ " + aux.getValor() + " ]" + " ->  ");                
                aux = aux.getSiguiente();               
                i++;
            }
        }
    }
}

CLASE MAIN

package Trabajo;

/**
 *
 * @author Jhon
 */
public class Main {
     public static void main(String[] args) throws Exception {
        Lista lista = new Lista();
        
        System.out.println("<<-- Ejemplo de lista simple -->>\n");
        
        // Agregar al final de la lista
        lista.agregarAlFinal(12);
        lista.agregarAlFinal(15);
        lista.agregarAlFinal(9);
        // Agregar in inicio de la lista
        lista.agregarAlInicio(41);
        lista.agregarAlInicio(6);
        
        System.out.println("<<-- Lista -->>");
        lista.listar();
        
        System.out.println("\n\n<<-- Tamaño -->");
        System.out.println(lista.getTamanio());
        
        System.out.println("\n<<-- Obtener el valor del nodo en la posicion 3 -->>");
        System.out.println(lista.getValor(3));
        
        System.out.println("\nInsrta un nodo con valor 16 despues del 15");
        lista.insertarPorReferencia(15, 16);
        lista.listar();
        System.out.print(" | Tamaño: ");
        System.out.println(lista.getTamanio());
        
        System.out.println("\n\nInsrta un nodo con valor 44 en la posición 3");
        lista.insrtarPorPosicion(3, 44);
        lista.listar();
        System.out.print(" | Tamaño: ");
        System.out.println(lista.getTamanio());
        
        System.out.println("\nActualiza el valor 12 del tercer nodo por 13");
        lista.editarPorReferencia(12, 13);
        lista.listar();
        System.out.print(" | Tamaño: ");
        System.out.println(lista.getTamanio());
        
        System.out.println("\nActualiza el valor nodo en la posición 0 por 17");
        lista.editarPorPosicion(0, 17);
        lista.listar();
        System.out.print(" | Tamaño: ");
        System.out.println(lista.getTamanio());
        
        System.out.println("\nElimina el nodo con el valor 41");
        lista.removerPorReferencia(41);        
        lista.listar();
        System.out.print(" | Tamaño: ");
        System.out.println(lista.getTamanio());
        
        System.out.println("\nElimina el nodo en la posición 4");
        lista.removerPorPosicion(4);        
        lista.listar();
        System.out.print(" | Tamaño: ");
        System.out.println(lista.getTamanio());
        
        System.out.println("\nConsulta si existe el valor 30");
        System.out.println(lista.buscar(30));
        
        System.out.println("\nConsulta la posicion del valor 9");
        System.out.println(lista.getPosicion(9));
        
//        System.out.println("\nElimina la lista");
//        lista.eliminar();
        
        System.out.println("\nConsulta si la lista está vacia");
        System.out.println(lista.esVacia());
        
        System.out.println("\n\n<<-- Fin de ejemplo lista simple -->>");
    }   
}

Referencia Concepto : Bryan Acosta estudiante de Ingeniería en Informática de la Universidad Central del Ecuador.


Publicado por en No hay comentarios:
PILAS Y COLAS

Las pilas y colas son estructuras de datos que se utilizan generalmente para simplificar ciertas operaciones de programación. Estas estructuras pueden implementarse mediante arrays o mediante listas enlazadas; en estos ejemplos solo trabajaremos con arrays

PILAS : Una pila (stack en inglés) es parte de los TDA (Tipos Abstractos de Datos) es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (último en entrar, primero en salir) que permite almacenar y recuperar datos.

COLAS : Una cola (también llamada fila) es otro TDA, es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO , debido a que el primer elemento en entrar será también el primero en salir.

Ejemplo de mostrar por Pila

/**
 *
 * @author Jhon
 */
public class usoPila {
private pila Pila;
private int tamPila;
public usoPila()
{
this.tamPila = 10;
this.Pila = new pila(this.tamPila);
}
public usoPila(int tp)
{
this.tamPila = tp;
this.Pila = new pila(this.tamPila);
}
public void LLenarPilaAleatorio(int rango)
{
while(this.Pila.Apilar((int)(Math.random()*rango))){}
}
        public void momstrarPila(){
            for (int i = 0; i < Pila.getCabPila(); i++) {
                System.out.println(" "+(this.Pila.getRepPila()[i]));
            }
        }
        
        public static void main(String[] args) {
        usoPila up=new usoPila(8);
        up.LLenarPilaAleatorio(10);
        up.momstrarPila();
     
        
    }    
}



Ejemplo de mostrar por Cola
/**
 *
 * @author Jhon
 */
public class UsoCola {
private cola Cola;
private int tamCola;
private cola tempcola;
private int tamcola1;

    public UsoCola() {
        this.tamCola = 10;
        this.Cola = new cola(this.tamCola);
    
    }

    public UsoCola(int tp) {
        this.tamCola = tp;
        this.Cola = new cola(this.tamCola);
    }

    public void LLenarColaAleatorio(int rango) {
        while (this.Cola.Meter((int) (Math.random() * rango))) {
        }
    }

    public void momstrarCola() {
        for (int i = 0; i < Cola.getCabCola(); i++) {
            System.out.println(" " + (this.Cola.getRepCola()[i]));
        }
    }
    public void pasar_otra_cola()
    {for(int i=0;i<this.tempcola.getMaxCola();i++)
        {this.tempcola.Meter(this.Cola.sacar());}
    }
    
    public void momstrarCola1() {
        for (int i = 0; i < Cola.getCabCola(); i++) {
            System.out.println(" " + (this.Cola.getRepCola()[i]));
        }
    }

    public static void main(String[] args) {
        UsoCola up = new UsoCola(8);
        up.LLenarColaAleatorio(10);
        up.momstrarCola();
        up.pasar_otra_cola();
        up.momstrarCola1();

    }
}

Referencia de Concepto : Ing. Juan Astudillo R.
Publicado por en No hay comentarios:
Suscribirse a: Comentarios (Atom)