Arboles


 Árboles binarios.
Los árboles de grado 2 tienen una especial importancia. Se les conoce con el nombre de árboles binarios. Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vació o está formado por una raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la raíz.
En los apartados que siguen se considerarán únicamente árboles binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.
Ejemplo:

Operaciones básicas.- Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol.Esta operación se considera entonces como un parámetro de una taré más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tres formas: Preorden, orden central y postorden.
Preorden: Raiz, subárbol izquierdo y subárbol derecho.
Orden central: Subarbol izquierdo, raiz, subarbol derecho.
Postorden: Subarbol izquierdo, subarbol derecho, raiz.
Ejemplo:
Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47
Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47
Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20
Ejemplo:
Preorden: / + a b * c d Notación polaca
Orden central: a + b / c * d Notación infija
Postorden: a b + c d * / Notación polaca inversa
Estructura de datos
Variables
Las variables son estructura de datos usados para almacenar información. Hay dos tipos de información que puede ser almacenada: Números y texto. Antes de usar una variable ésta, deberá primero ser definida:
Dim nombre_de_variable As Tipo
Ejemplo:
Dim precio As Long
Dim nombre_de_articulo As String
Tipo
Rango permitido
Integer
-32,768 a 32,767
Long
-2,147,483,648 a 2,147,483,647
Single
-3.402823E38 a -1.401298E-45
1.401298E-45 a 3.402823E38
Double
-1.79769313486232D308 a -4.94065645841247D-324
4.94065645841247D-324 a 1.79769313486232D308
Currency
-922337203685477.5808 a 922337203685477.5807
String
0 a 65,000 bytes
Variant
Valores de fechas: 1/1/0000 a 12/32/9999
Numérico: igual que Double
Texto: Igual que String
Si una nueva variable es declarada sin especificación VB por default la deberá tomar como tipo Variant
Una vez que una variable se ha creado, se le puede asignar un valor. Para esto se usa el operador ' = '. En el primer ejemplo de abajo a una variable se le asigna un valor constante, mientras que en el segundo se le asigna el contenido de una variable multiplicada por 10.
Ejemplo 1: precio = 29.95
Ejemplo 2: precio_total = precio * 10
El Alcance de una variable es definido como su rango de operación. Hay tres tipos de alcance en una variable:
  1. Local - La variable solo puede ser usada en el procedimiento actual ( use Dim dentro del procedimiento requerido).
  2. Módulo - La variables pueden ser accesadas desde cualquier procedieminento de la forma actual (use Dim dentro de la sección de Declaraciones Generales de la forma).
  3. Global - Pueden ser accesados desde cualquier procedimiento y desde cualquier forma. (usa Global dentro de la sección de Declaraciones Generales de un módulo).
Variables Estáticas
El declarar variables y arreglos como local en un procedimieneto/función es muy usado, porque esto minimíza los efectos extraños que pueden ocurrir cuando se usan variables globales. Sin embargo, cuando usamos una variable local en un procedimiento VB crea un espacio de memoria para mantener el valor de esta variable , esto sucede cuando lee el estatuto Dim, pero cuando llega al final del procedimiento (End Sub) VB libera el espacio asigndo para el valor de la variable local. Agrega el siguiente código a un botón de comando y observa que valores son impresos:
Sub Command1_Click ()
Dim numero As Integer ' Crea una variable Local normal
numero = numero + 1
Print numero
End Sub
Después de dar clic varias veces al botón de comando deberás ver una columna de unos en el lado izquierdo de la forma. El valor nunca será arriba de uno a pesar de que el valor de la variable se incrementa en uno cada vez. Esto es porque cada vez que el procediemineto es llamado, haciendo clic en el botón, VB esta trabajan con una variable diferente. Esta tiene exactamente el mismo nombre en el programa pero es una variable completamente diferente. Para que esto no suceda así, introduce Staticen el lugar de Dim:
Sub Command1_Click ()
Static numero As Integer ' Crea una variable estática local
numero = numero + 1
Print numero
End Sub
Ahora en vez de que el valor de la variable se pierda cuando el procedimiento termina, con este cambio (static) su valor permanecerá hasta que todo el programa termine. De esta manera, podemos ver una lista de números que se incrementan en uno cada vez que se le da clic al botón de comando.
Nota: La nueva variable estática es una variable de alcance local, si cualquier procedimiento trata de accesar esta variable no prodrá lograrlo. Agrega a la forma un nuevo botón de comando, el cual deberá tener un nuevo procedimiento 'Click', y trata de corregir o imprimir el valor de la variable estática que contiene el primer botón.
El contenido de un arreglo local, también puede mantenerse mientras el programa se ejecute. Para hacer esto agrega el estatuto 'Static' en lugar de 'Dim' como lo hicimos en el ejemplo de arriba.
Static salarios(199) As Long
Las constantes son similares a una variable pero tienen un valor determinado que se mantiene igual en toda la ejecución del programa. El contenido de una varible puede cambiar tantas veces sea necesario. ¿Porque usar una constante si no puede cambiar de valor?. Hacemos esto cuando deseamos usar un mismo número o una palabra (string) varias veces. Por ejemplo, en un programa para calcular los impuestos de todo el año, deberá hacer referencia a un valor en varias partes del programa, que puede ser el por ciento de impuesto mensual con respecto a las ganancias. Par ello podemos usar una variable llamada IMP, que mantendrá el valor en el evento Form_Load.
En el siguiente ejemplo definimos una contante llamada ' IMP ' y le asignamos el valor de 1.175. Ese es usado en estatuto Print con la variable pago_total para calcular la cantidad total a pagar. Note que en lugar de escribir 1.175 en la fórmula nos referimos a el nombre de la constante.
Ejemplo:
Const IMP = 1.175 ' Declara y asigna un valor a la constante
Dim pago_total As Currency ' Declara una variable local para almacenar el total a pagar
pago_total = 560.95
Print "Total = "; pago_total * IMP
Como las variables las constantes también tiene reglas de alcance. Hay constantes globales que pueden ser accesadas por cualquier módulo o cualquier forma del proyecto, las constantes de módulo solo son accesadas por la foma que los contiene, y las contantes locales son accesadas solamente por el objeto actual o procedimiento/función.
  1. Local - usa 'Const' dentro del procedimiento requerido.
  2. Módulo - usa 'Const' dentro de la sección deDeclaraciones Generales de una forma o módulo.
  3. Global - usa 'Global Const' dentro de la sección deDeclaraciones Generales de un módulo (ésto es Module1.bas).
Arreglos (arrays)
La variables son muy usadas para lamacenar pequeñas cantidades de información, pero no son convenientes para grandes cantidades de información muy similar. Por ejemplo, para almacenar los salarios de doscientos empleados, necesitaremos 200 variables diferentes. Una mejor forma de almacenar esta información será usra una estructura de datos llamada arreglos array.
Un arreglo es similar a las celdas en un panal de abejas. Todo el arreglo tiene un nombre, y cada celda tiene una dirección. Para el problema de los salarios planteado arriba, un arreglo el cual tiene 200 elementos (celdas) , usaremos el comando Dim para cerar un nueva variable, pero marcaremos también el tamaño de esta variable .
Dim nombre_del_arreglo (tamaño) [As Tipo]
Ejemplo: Dim salarios(199) As Long
En el ejemplo de arriba creamos un arreglo con 200 elementos. El tamaño marcado es de 199 porque por default VB empieza la numeración con 0.
Si sabemos que el nombre 'Jaime ' es el empleado número 24 y tiene un salario de 25,000 pesos mensuales, podemos lintroducir esta cantidad en el arreglo de la siguiente forma:
salarios(23) = 25000
Contrario a lo anterior, si deseamos saber cula es el salario del empleado número 189, podemos usar:
lblvalor.Caption = salarios(188)


Leia Mais

Grafos


Grafo (estructura de dat

Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto degrafo TAD desciende directamente del concepto matemático de grafo.
Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.
Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.

En Teoría de grafos, las aristas, junto con los vértices, forman los elementos principales con los que trabaja esta disciplina, siendo consideradas las aristas las uniones entre nudos o vértices.

Existen diferentes implementaciones del tipo grafo: con una matriz de adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).
  • Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementos de la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.
Matriz de adyacencia.jpg
  • Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.
Listas de adyacencia.jpg

Especificación de los tipos abstractos de datos de un grafo no dirigido


Generadores

Crear un grafo vacío: Devuelve un grafo vacío.
  • op crearGrafo : -> Grafo [ctor] .
Añadir una arista: Dado un grafo, añade una relación entre dos nodos de dicho grafo.
  • op añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .
Añadir un nodo: Dado un grafo, incluye un nodo en el en caso en el que no exista previamente.
  • op añadirNodo : Grafo Nodo -> Grafo [ctor] .


Constructores

Borrar nodo: Devuelve un grafo sin un nodo y las aristas relacionadas con él. Si dicho nodo no existe se devuelve el grafo inicial.
  • op borrarNodo : Grafo Nodo -> Grafo .
Borrar arista: Devuelve un grafo sin la arista indicada. En caso de que la arista no exista devuelve el grafo inicial.
  • op borrarArista : Grafo Nodo Nodo -> Grafo .


Grafo Vacio: Comprueba si un grafo no tiene ningún nodo.
  • op esVacio : Grafo -> Bool .
Contener Nodo: Comprueba si un nodo pertenece a un grafo.
  • op contiene : Grafo Nodo -> Bool .
Adyacentes: Comprueba si dos nodos tienen una arista que los relacione.
  • op adyacentes : Grafo Nodo Nodo -> Bool .
Para la especificación de un grafo dirigido tenemos que modificar algunas de las ecuaciones de las operaciones borrarArista y añadirArista para que no se considere el caso de aristas bidireccionales.
Leia Mais

PRACTICA


crear un sistema que simule la aduana.

package adb;

/**
 *
 * @author Romina
 */
public class Aduana {
    private String nombre;
    private String tipo;
    private String chasis;
    private String motor;
    private int modelo;
    private String color;
    private double costo;
  
    public Aduana(){
        nombre = "";
        tipo = "";
        chasis = "";
        motor = "";
        modelo = 0;
        color = "";
        costo = 0.0;
      
    }
    public Aduana(String nombre, String tipo, String chasis,
          String motor, int modelo, String color, double costo){
        this.nombre = nombre;
        this.tipo = tipo;
        this.chasis = chasis;
        this.motor = motor;
        this.modelo = modelo;
        this.color = color;
        this.costo = costo;
    }
    public void setNombre(String nombre){
        this.nombre = nombre;
    }
    public void setTipo(String tipo){
        this.tipo = tipo;
    }
    public void setChasis(String chasis){
        this.chasis = chasis;
    }
    public void setMotor(String motor){
        this.motor = motor;
    }
    public void setModelo(int modelo){
        this.modelo = modelo;
    }
    public void setColor(String color){
        this.color = color;
    }
    public void setCosto(double costo){
        this.costo = costo;
    }
  
    public String getNombre(){
        return nombre;
    }
    public String getTipo(){
        return tipo;
    }
    public String getChasis(){
        return chasis;
    }
    public String getMotor(){
        return motor;
    }
    public int getModelo(){
        return modelo;
    }
    public String getColor(){
        return color;
    }
    public double getCosto(){
        return costo;
    }
    public double getCostoNacionalizacion(){
 
        if((modelo >= 2010)&&(modelo <= 2012)){
            costo = costo * 0.30;
        }
        if((modelo >= 2005)&&(modelo <= 2009)){
            costo = costo * 0.50;
        }
        if((modelo >= 1990)&&(modelo <=2004)){
            costo = costo * 0.60;
        }
        return costo;
    }
 
}

* To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adb;

import adb.Lista.ExcepcionListaVacia;

/**
 *
 * @author Romina
 */
public class Cola {
    private Lista listaCola;
  
    public Cola(){
     listaCola = new Lista("cola");
    }
    public void enqueue(Object objeto){
      listaCola.insertarAlFinal(objeto);
    }
  
    public Object dequeue() throws ExcepcionListaVacia{
      return listaCola.eliminarDelFrente();
    }
    public boolean estaVacia(){
     return listaCola.estaVacia();
    }
    public void imprimir(){
     listaCola.imprimir();
    }
}
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adb;

/**
 *
 * @author Romina
 */
public class Hilo extends Thread {

    Splashcreen ref;

    public Hilo(Splashcreen ref) {
        this.ref = ref;
    }

    @Override
    public void run() {
        while (true) {
            try {
                Thread.sleep(100);
                ref.Llenar_Barra();

            } catch (InterruptedException ex) {

            }
        }
    }
    
}
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adb;

/**
 *
 * @author Romina
 */
public class Lista {
   private Nodo primerNodo;
    private Nodo ultimoNodo;
    private String nombre;
    Object datoRemover;
    int pos = 0;      
    public Lista(){
        this("lista");
    }
    public Lista(String nombreLista){
        nombre = nombreLista;
        primerNodo = ultimoNodo = null;
    }
    public boolean estaVacia(){
        return primerNodo == null;
    }
    public void insertarAlFrente(Object elementoInsertar){
        
        if(estaVacia())
            primerNodo = ultimoNodo = new Nodo(elementoInsertar);
        else
            primerNodo = new Nodo(elementoInsertar, primerNodo);
    }
    public void insertarAlFinal(Object elementoInsertar){
        
        if(estaVacia())
            primerNodo = ultimoNodo = new Nodo(elementoInsertar);
        else 
            ultimoNodo = ultimoNodo.siguienteNodo = new Nodo(elementoInsertar);
    }
    public Object eliminarDelFrente() throws ExcepcionListaVacia{
        if(estaVacia())
            
            throw new ExcepcionListaVacia(nombre);
            
        Object elementoEliminado = primerNodo.datos;
        
        if(primerNodo == ultimoNodo)
            primerNodo = ultimoNodo = null;
        else
            primerNodo = primerNodo.siguienteNodo;
        return elementoEliminado;
    }
    public void insertarNpos(Object elementoInsertar, int pos){
        if(estaVacia())
            //insertarAlFrente();
        if(pos == 1){
            //insertarAlFrente();
        }
        if(pos == cantNodo()){
            //insetarAlFinal();
        }
        else{
            Nodo actual = primerNodo;
            for(int i = 0 ; i < pos - 1; i++){
                actual = actual.siguienteNodo;
                Nodo nuevo = new Nodo(elementoInsertar, actual.siguienteNodo);
            }
        }
    }
    public Object eliminarDelFinal() throws ExcepcionListaVacia{
        
        if(estaVacia())
            
            throw new ExcepcionListaVacia(nombre);
            
        Object elementoEliminado = ultimoNodo.datos;
            
        if(primerNodo == ultimoNodo)
            primerNodo = ultimoNodo = null;
        else{
            Nodo actual = primerNodo;
            
             
        while(actual.siguienteNodo != ultimoNodo)
            actual = actual.siguienteNodo;
        
        ultimoNodo = actual;
        actual.siguienteNodo = null;
        }
       return elementoEliminado;
    }
    public Object eliminarNpos() throws ExcepcionListaVacia{
        
        if(estaVacia())
            
            throw new ExcepcionListaVacia(nombre);
            
              
                if(pos == 1){
                    eliminarDelFrente();
                }
                else{
                if(pos == cantNodo()){
                    eliminarDelFinal();
                }
                }
                
                   Object elementoEliminado = ultimoNodo.datos;
                
              if(primerNodo.equals(ultimoNodo)){
                    primerNodo = ultimoNodo = null;
                    
                    return elementoEliminado;
              }
                
                    
                    Nodo actual = primerNodo;
                    for(int i = 1 ; i < pos ; i++){
                        actual = actual.siguienteNodo;
                         elementoEliminado  = (actual.siguienteNodo).datos;
                        actual.siguienteNodo = (actual.siguienteNodo).siguienteNodo;
                        (actual.siguienteNodo).siguienteNodo = null;
                        
                    
                    }
                
                    return elementoEliminado;
                }
                
    public void imprimir(){
        
        if(estaVacia()){
            System.out.printf("%s Vacia\n", nombre);
        return;
    }
        System.out.printf("La %s es: ", nombre);
        Nodo actual = primerNodo;
        
        while(actual != null){
            System.out.printf("%s ", actual.datos);
            actual = actual.siguienteNodo;
        }
        System.out.println("\n");
    }

    public int cantNodo() {
        Nodo actual = primerNodo;
        int cant = 0;
        while(actual != null){
            cant++;
            actual = actual;
        }
        return cant;
    }

        public class ExcepcionListaVacia extends RuntimeException{
        
         public ExcepcionListaVacia(){
            this("lista");
        }
         public ExcepcionListaVacia(String nombre){
             super(nombre + "Esta Vacia");
         }
         
    }
 }
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adb;

/**
 *
 * @author Romina
 */
public class Nodo {
    Object datos;//los datos para este nodo
    Nodo siguienteNodo;//referencia al siguiente nodo de la lista
    
    //el constructor crea un objeto Nodo que hace referencia al objeto
    Nodo(Object objeto){
        this(objeto, null);
    }
    Nodo(Object objeto, Nodo nodo){
        datos = objeto;
        siguienteNodo = nodo;
    }
    Object obtenerObject(){
        return datos;
    }
    Nodo obtenerSiguiente(){
        return siguienteNodo;
    }
}
*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adb;

/**
 *
 * @author Romina
 */
public class Pila extends Lista{
    
    public Pila(){
        super("pila");
    }
    public void push(Object objeto){
        insertarAlFrente(objeto);
    }
    public Object pop() throws ExcepcionListaVacia{
        return eliminarDelFrente();
    }
}
Leia Mais

COLA

COLA
Una cola es simplemente un lugar para almacenar cosas, donde esas cosas se insertan una detrás de otra y para extraer siempre se lo hace por adelante de la cola donde se encuentra el primer elemento. Una cola funciona como una fila o cola de personas, que esperan su turno para ser atendidas, la primera persona atendida es siempre la primera de la fila y cuando llega una persona y queremos incorporarla a cola o adicionarla debemos hacerlo por detrás de la ultima persona en la cola.




/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package estructurasdatosdinamicas;


/**
 *
 * @author Administrador
 */
public class Cola extends ListaEnlazada{
    
    public Cola(){
        super("cola 1");
    }
    public void Encolar(Object obj){
        super.InsertAtras(obj);
    }
    public Object Decolar(){
        return super.DeleteFrente();
    }
    public Boolean colaVacia(){
        return super.Lvacia();
    }
}




Una cola circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden cosultarse, añadirse y eliminarse unicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

BICOLAS

Es una cola en la se puede "sacar" y "meter" elementos tanto de la delantera de la cola como e la cola. Si una cola, como estructura de datos abstracta, tiene dos operaciones llamadas "push" (que inserta un elemento al final de la cola) y "pop" (que extrae un elemento del principio de la cola), entonces una bicola tiene dos operaciones adicionales llamadas "push_front" y "pop_back".
Toda operación debería implementarse en un tiempo amortizado constante O(1). Al igual que la cola regular, la implementación e un array no es correcta por el costo del espacio o bien el shift de desencolar.
A diferencia de la cola simple, la lista enlazada no es suficiente. La implementación es trivial en una lista doblemente enlazada pero tiene el problema del acceso aleatorio a un elemento del medio de la cola. La implementación apropiada es un buffer circular con crecimiento dinámico.
Existen implementaciones listas en todos los lenguajes de programación. c++ tiene std::deque, java tiene la interfaz java.util.Deque, perl permite las operaciones pollback y pollfront en todos los arrays, etc. etc.


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package estructurasdatosdinamicas;

/**
 *
 * @author Administrador
 */
public class Bicola extends ListaEnlazada{
    
    public Bicola(){
        super("bicola 1");
    }
    public void PushAtras(Object obj){
        super.InsertAtras(obj);
    }
    public Object PopFrente(){
        return super.DeleteFrente();
    }
    public void PushFrente(Object obj){
        super.InsertFrente(obj);
    }
    public Object PopAtras(){
        return super.DeleteAtras();
    }
    public Boolean BicolaVacia(){
        return super.Lvacia();
    }
    
}



Leia Mais

PILAS


pilas

una pila es una lista que tiene establecida ciertas restricciones en cuanto a la forma de extraer  o colocar en ella nuevo elementos. la lista se utiliza siempre se que desea recuperar una serie de elementos en orden inverso a como se introdujeron .

package estructurasdatosdinamicas;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Administrador
 */
public class Pila extends ListaEnlazada{
    
    public Pila(){
         super("Pila 1");
                 }
    public void Push(Object obj){
        super.InsertAtras(obj);
    }
    public Object Pop(){
        return super.DeleteAtras();
    }
    public Boolean PilaVacia(){
        return super.Lvacia();
    }
}



Leia Mais

LISTAS

LISTAS



Una lista es un conjunto de elementos con un
orden concreto:
– Puede tener una longitud arbitraria.
– Ofrece la posibilidad de insertar o
eliminar un elemento en cualquier
ubicación.
– Ofrece la posibilidad de recorrer la lista de
forma ordenada, de elemento en elemento.



package estructurasdatosdinamicas;


creación de Nodo




/**
 *
 * @author Administrador
 */
public class Nodo {
    
    public Object Datos;
    public Nodo sgte;
    public Nodo anterior;
    public int CI;
    public int edad;
    
    
    
        public Nodo()
        {
            Datos = sgte = anterior = null;
            
        }
    public Nodo (Object obj)
    {
        Datos = obj;
        sgte = anterior = null;
    }
    public Nodo (Object obj, Nodo sig)
    {
        Datos = obj;
        sgte = sig;
    }
    public void GetDatos(Object cd)
    {
        Datos = cd;
    }
    public void SetAnterior(Nodo ant)
    {
        anterior = ant;
    }
    public void SetSgte(Nodo sg)
    {
        sgte = sg;
    }
    public Nodo SetSgte()
    {
        return sgte;
    }
    public Nodo GetAnteruior()
    {
        return anterior;
    }
}






Lista enlazada



• Las listas enlazadas son como trenes de mercancías.
• Cada elemento que que se va a poner en la lista está
contenido en una instancia de un nuevo tipo de
objeto, llamado enlace, que equivale a un vagón
del tren.
• En una lista enlazada sencilla, el enlace no sólo
contiene el elemento de la lista, sino que
también apunta al siguiente elemento de la
lista, al igual que un vagón de mercancías está
acoplado al siguiente.
• El último enlace de la lista no apunta a nada.


package estructurasdatosdinamicas;


/**
 *
 * @author Administrador
 */
public class ListaEnlazada {
    
    protected String Nombre;
    protected Nodo Primero;
    protected Nodo Ultimo;
    
    public ListaEnlazada(String n)
    {
        Nombre = n;
        Primero = Ultimo = null;
    }
    
    public ListaEnlazada()
    {
        this.Nombre = "Lista";
        
    }
    
    public Boolean Lvacia()
    {
        return Primero ==null;
    }
    
    public String getNombre(){
      
        return Nombre;
    }
    public Nodo getPrimero(){
        
        return Primero;
        
    }


    public Nodo getUltimo(){
    
        return Ultimo;
    }


    public void InsertFrente(Object obj){
           if(Lvacia())
         Primero=Ultimo= new Nodo(obj);
           else
         Primero=new Nodo (obj, Primero);
        
    }
        
    public void InsertAtras(Object obj){
           if(Lvacia())
         Primero=Ultimo= new Nodo(obj);
           else
         Ultimo=Ultimo.sgte=new Nodo (obj);
    
    }
    
    public Object DeleteFrente(){
    
           Object DatoRemovido = null;
           
           if(Lvacia())
               System.out.println("Vacia");
           DatoRemovido= Primero.Datos;
           if(Primero.equals(Ultimo)) 
                 Primero = Ultimo = null;
           else
               Primero = Primero.sgte;
           return DatoRemovido;
    }


    public  Object DeleteAtras(){
        
        Object DatoRemovido = null;
        if (Lvacia()){
            System.out.println("Vacia");
        }
        DatoRemovido = Ultimo.Datos;
        
           if(Primero.equals(Ultimo)){
        
               Primero = Ultimo = null;
        }
           else{
           Nodo Actual = Primero;
               while (Actual.sgte != Ultimo)
                     Actual = Actual.sgte;
               Ultimo = Actual;
               Actual.sgte= null;
           }
           
           return DatoRemovido;
    }
     
    public Object getElementoDeIndice(int Posicion){
        
        if(Lvacia()){
           return null;
        }
        else{
             Nodo actual = Primero;
                  int  cont = 1;
                    while((actual != null)&& (cont < Posicion)){
                      actual = actual.sgte;
                      cont++;
                    }
                    if((actual != null) && (cont == Posicion - 1)){
                           return actual.Datos;
                    }
                    else{
                      return null;
                    }
               }
          }
        
    public void InsertarElementoEnIndice(int Posicion, Object obj){
    Nodo nuevo;
    Nodo actual;
            
              if(Lvacia()){
                 return;
              }
              else{
                  actual = Primero;
                  int cont = 1;
                    
                     while((actual != null) && (cont == Posicion -1)){
                         actual = actual.sgte;
                         cont++;
                     }
                     if ((actual != null) && (cont == Posicion - 1)){
              
               nuevo = new Nodo(obj , actual.sgte);
                 actual.sgte= nuevo;
              
          }
       }
    }


    public Object DeleteElementoDeIndice (int Posicion){
        
        Object DatoRemovido;
        Nodo actual;
        
        if(Lvacia()==true){
         return null;
        }
        else{
            if(Posicion == 1){
                  DatoRemovido=Primero.Datos;
                  Primero=Primero.sgte;
                  return DatoRemovido;
            }
            else{
             actual=Primero;
             int cont=1;
             
             while((actual != null) && (cont<Posicion-1)){
              actual=actual.sgte;
              cont++;
             }
             if((actual !=null)&&(cont==Posicion-1)){
              DatoRemovido=actual.sgte.Datos;
              
              actual.sgte=actual.sgte.sgte;
              return DatoRemovido;
             }
            }
            return null;
        }
    }
    
}


lista doble circular
Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples
La asignación de memoria es hecha al momento de la ejecución. 

En cambio, en relación a la  listas enlazadas simples el enlace entre los elementos se hace gracias a dos punteros.



public class ListaDobleCircular {
  
    private Nodo actual;
    private Nodo ultimo;
    private long numeroElemento;
    private long posicion;
  
    public ListaDobleCircular(){
        actual = ultimo = null;
        numeroElemento = 0;
        posicion = 0;
    }
    public long tamañoLista(){
         return numeroElemento;
    }
  
public void incertarlistadobleE(Object obj){
     Nodo q;
    
      if(ultimo == null){
          ultimo = new Nodo();
          ultimo.anterior = ultimo;
          ultimo.sgte = ultimo;
          ultimo.Datos = obj;
          actual = ultimo;
          posicion = 0;
 }
      else{
     q = new Nodo();
          actual.sgte.anterior = q;
          q.sgte = actual.sgte;
          actual.sgte = q;
          q.anterior = actual;
          q.Datos = obj;
          posicion++;
     if(actual == ultimo){
          ultimo = q;
     }
         actual = q;
        numeroElemento++;
     }
 }
 public Object BorrarListaDobleE(){

     Nodo q;
     Object obj;
    
     if(ultimo == null){
         return null;
     }
       if(actual == ultimo){
           if(numeroElemento == 1){
              obj = ultimo.Datos;
              ultimo = actual=null;
              numeroElemento = 0;
              posicion = 0;
      }
           else{
              actual = ultimo.anterior;
               ultimo.sgte.anterior = actual;
               actual.sgte = ultimo.sgte;
               obj = ultimo.Datos;
               ultimo = actual;
               posicion--;
               numeroElemento--;
             }
       }
          else {
                q = actual.sgte;
                actual.anterior.sgte = q;
                q.anterior = actual.anterior;
                obj = actual.Datos;
                actual = q;
                numeroElemento--;
       }
           return obj;
    }
 public void irSgte(){
     if(posicion < numeroElemento - 1){
         actual = actual.sgte;
         posicion++;
     }
 }
 public void irAnterior(){
     if(posicion > 0){
         actual = actual.anterior;
         posicion--;
     }
 }
 public void irPrincipio(){
     actual = ultimo.sgte;
     posicion = 0;
 }
 public void irFinal(){
     actual = ultimo;
     posicion = numeroElemento - 1;
 }
 public Boolean irAl(long i){
     if(i >= numeroElemento){
         return false;
     }
     irPrincipio();
     for(long n = 0 ; n < i;n++){
         irSgte();
     }
     return true;
 }
 public Object obtener(){
     if(ultimo == null){
         return null;
     }
     return actual.Datos;
 }
 public Object obtenerDe(long i){
     if(!irAl(i)){
         return null;
     }
     return obtener();
 }
 public void Modificar(Object NuevoDato){
     if(ultimo == null){
         return;
     }
     actual.Datos = NuevoDato;
 }
}

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.










Leia Mais