Estructura de Datos

Los siguientes enlaces te dirigen al tema al que quieras recurrir:

LISTAS
PILAS
COLAS
RECURSIVIDAD
ARBOLES
GRAFOS
ORDENAMIENTO
BUSQUEDA

LISTAS:

Una lista es una estructura de datos dinámica que cumple las siguientes características:

Dispone de un numero variable de elementos (desde cero hasta "n"). Su tamaño únicamente se limita por la cantidad de memoria que haya disponible en el sistema. Si la lista tiene cero elementos recibe el nombre de "Lista vacía".
El primer elemento de la lista, cuando ésta no está vacía es conocido y se puede acceder a él siempre que se desee.
Los elementos de la lista guardan una relación de orden (o precedencia), de forma que para cada uno de ellos es posible saber cual es su "elemento siguiente".

TIPOS DE LISTAS:

Lista simplemente enlazada

Lista doblemente enlazada

Lista circular

LISTA SIMPLEMENTE ENLAZADA

Las listas enlazadas o encadenadas son aquellas listas cuyos elementos se encuentran almacenados en posiciones de memoria no contiguas. En este tipo de listas, los nodos tienen la estructura de auténticos registros divididos en unidades de tratamiento mas pequeñas denominadas campos.

Cada nodo está formado por un mínimo de dos campos:

a) Campo información (Campo que contiene el dato)

b) Campo indicador o puntero (Campo que actúa de enlace con el siguiente nodo de la lista en secuencia lógica).

Por convenio:

a) Cuando se crea una lista, esta debe estar inicialmente vacía.

b) El campo puntero correspondiente al ultimo nodo de la lista apunta a un valor Nulo.

c) Para acceder a un nodo de la lista, se parte del nodo inmediatamente anterior, a excepción del primer nodo, al cual se accede a través de un enlace especial o puntero externo a la lista.

LISTA DOBLEMENTE ENLAZADA

Son aquellas que pueden recorrerse en amabas direcciones gracias a que los nodos que la componen están formados por tres campos:

a) Campo información

b) Campo enlace que apunta al nodo anterior ( el cual nos permite retroceder o recorrer la lista hacia atrás).

c) Un segundo campo enlace que apunta al nodo siguiente de la lista.

LISTAS CIRCULARES

Se caracterizan porque el campo puntero del último nodo, en lugar de apuntar a un valor Nulo, apunta al primer nodo o elemento de la lista, convirtiéndose en una estructura de datos circular.

OPERACIONES CON LISTAS

a) Crear una lista.

Lista = Nulo

b) Insertar un nodo a la lista

c) Eliminar un elemento de la lista

Aplicación de Listas: Recolección de Basura y Compactación

En un ambiente de computadores multi-procesos, muchos programas residen en memoria al mismo tiempo. Diferentes programas tiene diferentes requerimientos de memoria. Así un programa puede requerrir 60K o 300K de memoria. En cualquier momento que el sistema necesite memoria, necesita localizar memoria continua del tamaño deseado. Cuando la ejecución de un programa es terminada, la memoria que ha sido ocupada debe ser liberada y disponible para otro programa. Más aún, bloques de memoria pueden ser liberados en una secuencia diferente a la que fueron solicitados.

Suponga por ejemplo el siguiente caso:

Se tiene una memoria de 100000 palabras y 5 programasa P1, P2, P3, P4, y P5 que requieren bloques de memoria de tamaños 10000, 15000, 6000, 8000 y 20000. La vista de la memoria al localizar el programa P5 sería:

Asuma ahora que el programa P4 y P2 completaron su ejecución y que por lo tanto la memoria es liberada:

Ahora se tienen 3 bloques de memoria contigua libres y tres ocupados. Con el propósito de seguir permitiendo la localización de memoria, es necesario mantener registro de los bloques que no están en uso. Para eso se usa un lista de bloques de memoria que no están en uso.

El proceso de recolección de basura es llevado a cabo en dos pasos: (1) marcación de los bloques que están en uso y (2) compactación de los bloques libres a memoria disponible. Este segundo paso es trivial si los bloques son de igual tamaño llegando a ser de O(n), siendo n el número de nodos.

Cuando existe un tamaño variable por nodo, es deseable compactar la memoria de manera que todos los nodos libres queden en memoria contigua, lo que se llama compactación de memoria. La compactación de memoria reduce el tiempo de recuperación.

ALGORITMO PROGRAMA DE LISTA ENLAZADA SIMPLE

Empezaremos creando la clase que nos permitira recorrer la lista, a esta le asignaremos el nombre de Nodo

public class Nodo {
 Nodo nodoDer;
 int  dato;
 
public  Nodo(int dato) {
 this.dato = dato;
 this.nodoDer = null;
 }
 
}

Nesesitaremos un nodo para agregar a la lista este metodo ira agregando todo al final de la misma:

public  ListaS addLast(int dato) {
 if(siVacio()) {
 Nodo nuevo = new Nodo(dato);
 primero = nuevo;
 ultimo = nuevo;
 nuevo.nodoDer =  nuevo;
 }
 else {
 Nodo nuevo = new Nodo(dato);
 nuevo.nodoDer =  null;
 ultimo.nodoDer =  nuevo;
 ultimo = nuevo;
 }
 this.tamano++;
 return  this;
 }

De igual forma se nesesita un metodo para borrar datos de la lista:

public  Nodo deleteLast() {
 Nodo eliminar = null;
 if(siVacio()) {
JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
 return  null;
 }
 if(primero == ultimo) {
 primero = null;
 ultimo = null;
 }
 else {
 Nodo actual = primero;
 while(actual.nodoDer !=  ultimo) {
 actual = actual.nodoDer;
 }
 eliminar = actual.nodoDer;
 actual.nodoDer =  null;
 
ultimo = actual;
 }
 this.tamano--;
 return  eliminar;
 }

Nuestro codigo completo quedaria de la siguiente manera:

Classe principal:

import javax.swing.JOptionPane;
 
public class ListaS {
    private Nodo primero;
    private Nodo ultimo;
    private int tamano;
 
    public ListaS() {
        this.primero = null;
        this.ultimo = null;
        this.tamano = 0;
    }
 
//Metodo utilizado para denotar que la lista se encuentra vacia.
    public boolean siVacio() {
        return (this.primero == null);
    }
 
//Metodo para agregar al final de la lista.
    public ListaS addLast(int dato) {
        if(siVacio()) {
            Nodo nuevo = new Nodo(dato);
            primero = nuevo;
            ultimo = nuevo;
            nuevo.nodoDer = nuevo;
        }
        else {
            Nodo nuevo = new Nodo(dato);
            nuevo.nodoDer = null;
            ultimo.nodoDer = nuevo;
            ultimo = nuevo;
        }
        this.tamano++;
        return this;
    }
 
//Metodo para borrar al final de la lista.
    public Nodo deleteLast() {
        Nodo eliminar = null;
        if(siVacio()) {
            JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
            return null;
        }
        if(primero == ultimo) {
            primero = null;
            ultimo = null;
        }
        else {
            Nodo actual = primero;
            while(actual.nodoDer != ultimo) {
                actual = actual.nodoDer;
            }
            eliminar = actual.nodoDer;
            actual.nodoDer = null;
 
            ultimo = actual;
        }
        this.tamano--;
        return eliminar;
    }
 
//Metodo que imprime el tamaño de la lista.
    public void tamano() {
        JOptionPane.showMessageDialog(null, "El tamaño es:\n " + this.tamano);
    }
 
//Metodo que imprime la lista y los valores ingresados.
    public void imprimir() {
        if(tamano != 0) {
            Nodo temp = primero;
            String str = "";
            for(int i = 0; i < this.tamano; i++) {
                str = str + temp.dato + "\n";
                temp = temp.nodoDer;
            }
            JOptionPane.showMessageDialog(null, str);
        }
    }
}

Clase Nodo:

public class Nodo {
 Nodo nodoDer;
 int  dato;
 
public  Nodo(int dato) {
 this.dato = dato;
 this.nodoDer = null;
 }
 
}

PILAS

-Concepto de pila

Una pila es una estructura de datos lineal en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.

Trabajan con filosofía LIFO (Last In- First Out ).

-Tipos de pilas

*Estatica

*Dinamica

-Operaciones con pilas

PUSH (insertar).- Agrega un elementos a la pila en el extremo llamado tope.

POP (remover).- Remueve el elemento de la pila que se encuentra en el extremo llamado tope.

VACIA.- Indica si la pila contiene o no contiene elementos.

LLENA.- Indica si es posible o no agregar nuevos elementos a la pila.

-Aplicaciones de pilas

Las pilas son utilizadas ampliamente para solucionar una amplia variedad de problemas. Se utiliza en compiladores, sistemas operativos y en programasde aplicación. Su implementación se puede hacer mediante Arrays Y Mediante listas enlazadas.

Un ejemplo de sus aplicaciones podrían ser los siguientes:

Los Navegadores en Internet almacenan en una pila las direcciones de los sitios más recientemente visitados.

Los editores de texto proporcionan normalmente un botón deshacer que cancela las operaciones de edición recientes y restablece el estadoanterior del documento.

-Programa con operaciones de pilas

Public class Pilaestatica{

Public static void main (String [] args){

Int dato;

Int pila[] = new int [5];

Scanner captura = new Scanner(System.in);

For(int tope=0; tope<4; tope++)

{

System.out.println(“Proporcione datos para la pila:”);

Dato= captura.nextInt();

Pila[tope]=dato;

}

For int(tope=4; tope>=0; tope--)

System.out.println(“La pila tiene los siguientes datos:” +pila[tope]);

}

COLAS:

Las colas también son llamadas FIFO (First In First Out), que quiere

decir “el primero que entra es el primero que sale”.

COLAS SIMPLES:

Se inserta por un sitio y se saca por otro, en el caso de la cola simple se

inserta por el final y se saca por el principio. Para gestionar este tipo de cola

hay que recordar siempre cual es el siguiente elemento que se va a leer y cual

es el último elemento que se ha introducido.

COLAS CIRCULARES:

En las colas circulares se considera que después del último elemento se

accede de nuevo al primero. De esta forma se reutilizan las posiciones

extraídas, el final de la cola es a su vez el principio, creándose un circuito

cerrado.

APLICACIONES DE COLAS:

Las colas se utilizan en muchos algoritmos y en situaciones en las que el rendimiento de dos sistemas que se cruzan datos entre sí es más eficiente cuando no se intercambian indicativos y señales de control (handshaking) en cada transferencia.

• También almacenan temporalmente la transferencia de información, lo que permite procesarla en origen y en destino a tasas independientes.

- Se utilizan en los slideshows de imagenes.

RECURSIVIDAD

Es una técnica de programación muy potente que permite definir un objeto

(problemas, estructuras de datos) en términos de si mismo.

•Una función o procedimiento recursivo es aquel que se llama a si mismo.

TIPOS DE RECURSIVIDAD

Recursividad Directa: Cuando un método P contiene dentro de si un llamado a si mismo.
Recursividad Indirecta: Cuando un método P contiene dentro de si un llamado a otro método Q que contiene llamados (directos o indirectos) a P.

Ejemplo de Recursividad. Programa Fibonacci

import java.util.Scanner;
public class FibonacciR {
public static long fib(int n){
if(n<=1) return n;
else return fib(n-1)+fib(n-2);
}
public static void main(String[] args) {
int n;
Scanner teclado = new Scanner(System.in);
System.out.println("Ingrese el numero");
n= teclado.nextInt();
System.out.println("------------");
for(int i =1; i<= n;i++){
System.out.println(i +": "+fib(i));
}
}
}

Ejemplo de Recursividad. Programa Factorial

import java.util.*;
public class factorial {
public static double n, h;
public static double factorial(double n){
if(n==0){
return 1;
}
else
h=1;
return n*factorial(n-1);

}
public static void main(String[] args) {
System.out.println("Â¿CuÃ¡l es el nÃºmero?");
Scanner cap = new Scanner(System.in);
n= cap.nextDouble();
if(n==0){
System.out.println("\nFactorial:1");
}
factorial f = new factorial();
f.factorial(n);
if(h==1){
System.out.println("\n Factorial="+n*factorial(n-1));
}
}
}

ARBOLES

Un árbol es una estructura de datos no lineal jerarquizada, cada dato reside en un nodo, y existen relaciones de parentesco entre nodos en la que cada nodo puede apuntar a uno o varios nodos.

*Una coleccion de dos o mas arboles se llama BOSQUE.

Los árboles constituyen estructuras de datos jerarquizados, y tienen multitud de aplicaciones, como
por ejemplo:
• Análisis de circuitos, Representación de estructuras de fórmulas matemáticas
• Organización de datos en bases de datos
• Representación de la estructura sintáctica en compiladores.
• En muchas otras áreas de las ciencias del computador.
Un árbol está constituido por una colección de elementos denominados nudos, uno de los cuales se
distingue con el nombre raíz, junto con una relación de 'parentesco' que establece una estructura jerárquica
sobre los nudos. Cada nudo tiene un padre (excepto el raíz) y puede tener cero o más hijos. Se denomina
hoja a un nudo sin hijos. Como ejemplo se muestra en la figura superior la tabla de contenidos de un libro.

Se definen varios conceptos:

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

ARBOLES BINARIOS

Un árbol binario es un árbol orientado y ordenado, en el que cada nodo puede tener un hijo izquierdo y un hijo derecho.

RECORRIDOS

Recorrido en preorden

En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.

En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

Recorrido en postorden

En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Recorrido en inorden

En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 9, 4.

CONVERSIÓN DE UN ÁRBOL GENERAL EN ÁRBOL BINARIO

Dado que los árboles binarios son de estructura fundamental en la teoría de los árboles, será preciso disponer de algún mecanismo que permita la conversión de un árbol general en árbol binario.

“Los árboles binarios son más fáciles de programar que los generales”. En esto es imprescindible deducir cuántas ramas o caminos se desprenden de un nodo en un momento dado. Por ello, y dado que de los árboles binarios siempre se cuelgan como máximo dos subárboles, su programación será más sencilla.

Afortunadamente, existe una técnica para convertir un árbol general a formato de un árbol binario. Ejemplo:

Supongamos que se tiene el árbol A y se quiere convertir en un árbol binario B. El árbol de conversión tiene 3 pasos fáciles:

1. - La raíz de B es la raíz de A

2. -

a) Enlazar un nodo raíz con el camino que conecta el nodo más a la izquierda (su hijo).

,. b) Enlazar éste nodo con los restantes descendientes del nodo raíz en su camino con lo que se forma el nivel 1.

c) A continuación, repetir los pasos a y b con los nodos del nivel 2, enlazando siempre en un mismo camino todos los hermanos (descendientes del mismo nodo). Repetir estos pasos hasta llegar al nivel más alto.

3.- Girar el diagrama resultante 45° para diferenciar entre los subárboles izquierdos y derecho.

CLASE JTREE EN JAVA

. El JTree nos permite mostrar información jerárquica, es excelente para mostrar datos como un árbol familiar o la estructura del sistema de archivos.

El JTree es el componente java visual (como los botoncitos, listas, menús, etc) que nos permite visualizar un árbol. En él podemos ver el típico árbol de datos en el que podemos abrir cada uno de los nodos para ver qué tiene dentro, cerrarlos, etc.

Clases Java implicadas

Por un lado tenemos "la vista", que es la clase java que se ve. Esta clase es el JTree y es lo que se ve en la pantalla, en nuestra ventana.

Por otro lado tenemos el "modelo de datos". Esta clase de java puede ser cualquier clase que implemente la interface TreeModel, pero java nos ofrece ya implementada la clase DefaultTreeModel. Esta clase es la que contiene los datos que queremos visualizar en "la vista". Contiene los datos que visualizaremos en el JTree.

¿Qué datos admite el DefaultTreeModel?. Puesto que vamos a hacer un árbol, admite datos que se puedan asociar entre sí como padres e hijos. No valen datos cualesquiera. Esos datos deben implementar la interface TreeNode. Cualquier clase que implemente esta interface, tendrá métodos para interrogarle sobre quién es su padre, si tiene hijos, etc. Estos métodos será los que acabe usando JTree para saber qué debe pintar, quién es hijo de quién y quién es padre de quién.

Existe otro tipo de dato también importante, el MutableTreeNode. Este es igual que el anterior, pero además tiene métodos para modificar las asociaciones entre padres e hijos. Permite añadir nuevos hiijos a los padres, cambiar el padre de los hijos y cualquier otro tipo de indecencia que se nos ocurra. Si nuestro árbol va a cambiar sobre la marcha, nos interesa usar datos (nodos) que implementen esta interface.

Java nuevamente nos ofrece una clase que ya implementa MutableTreeNode y por tanto tiene todos los métodos necesarios para saber quién es hijo de quién y los métodos necesarios para cambiar estas asociaciones. Esta clase es DefaultMutableTreeNode. Tiene además un método intereseante, que es setUserObject(). Este método nos permite guardar dentro la información que queramos. Esta información será nuestro dato real, lo que realmente nos interesa. DefaultMutableTreeNode únicamente nos ahorrará escribir el código necesario para mantener asociaciones entre padres e hijos, además de hacer de almacén de nuestro dato.

Ejemplo de visualizacion:

PROGRAMA - ARBOLES

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
public class SimpleTree
{ public static void main(String[] args)
   { JFrame frame = new SimpleTreeFrame();
      frame.show();
   }
}
class SimpleTreeFrame extends JFrame
{
   DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");
   DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");
   DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");
   DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");
   DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");
   DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");
   DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");
   DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");
   DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");
   DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");
   DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");
   DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");
   DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");
   DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");
   public SimpleTreeFrame()
   { setTitle("SimpleTree");
      setSize(300, 200);
      addWindowListener(new WindowAdapter()
         { public void windowClosing(WindowEvent e)
            { System.exit(0);
            }
         } );
      root.add(arge);                                                   // Enlazado de nodos
      arge.add(sant);                                                   // Enlazado de nodos
      sant.add(rafa);                                                   // Enlazado de nodos
      sant.add(rosa);                                                   // Enlazado de nodos
      sant.add(safe);                                                   // Enlazado de nodos
      sant.add(vena);                                                   // Enlazado de nodos
      sant.add(vill);                                                   // Enlazado de nodos
      arge.add(cord);                                                   // Enlazado de nodos
      cord.add(codo);                                                   // Enlazado de nodos
      cord.add(cbro);                                                   // Enlazado de nodos
      cord.add(rcua);                                                   // Enlazado de nodos
      arge.add(chac);                                                   // Enlazado de nodos
      chac.add(resi);                                                   // Enlazado de nodos
      chac.add(vang);                                                   // Enlazado de nodos
      root.add(chil);                                                   // Enlazado de nodos
      chil.add(regi);                                                   // Enlazado de nodos
      regi.add(schi);                                                   // Enlazado de nodos
      JTree tree = new JTree(root);
      Container contentPane = getContentPane();
      contentPane.add(new JScrollPane(tree));
      Enumeration hijos = sant.children();                              // Enumeracion de hijos
      while ( hijos.hasMoreElements() )                                 // Enumeracion de hijos
      {                                                                 // Enumeracion de hijos
        System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos
      }                                                                 // Enumeracion de hijos
      boolean hoja = vena.isLeaf();                                     // Consulta Hoja
      System.err.println("Es Venado Tuerto hoja : "+hoja);              // Consulta Hoja
      Enumeration breadth = root.breadthFirstEnumeration();             // Enumeracion Nodos
      while ( breadth.hasMoreElements() )                               // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Breadth First : "+breadth.nextElement());   // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration depth = root.depthFirstEnumeration();                 // Enumeracion Nodos
      while ( depth.hasMoreElements() )                                 // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Depth First : "+depth.nextElement());       // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration preorder = root.preorderEnumeration();                // Enumeracion Nodos
      while ( preorder.hasMoreElements() )                              // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Pre Order : "+preorder.nextElement());      // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration postorder = root.postorderEnumeration();              // Enumeracion Nodos
      while ( postorder.hasMoreElements() )                             // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Post Order : "+postorder.nextElement());    // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
   }
}

GRAFOS

GRAFOS
Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada
arco en un grafo se especifica por un par de nodos.
El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A,
C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo

Si los pares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o

dígrafo.

TERMINOLOGÍA

*.-Al número de nodos del grafo se le llama orden del grafo.

*.-Un grafo nulo es un grafo de orden 0 (cero).

*.-Dos nodos son adyacentes si hay un arco que los une.

*.-En un grafo dirigido, si A es adyacente de B, no necesariamente B es adyacente de A

*.-Camino es una secuencia de uno o mas arcos que conectan dos nodos.

*.-Un grafo se denomina conectado cuando existe siempre un camino que une dos

nodos cualesquiera y desconectado en caso contrario.

*.-Un grafo es completo cuando cada nodo esta conectado con todos y cada uno de los

nodos restantes.

*.-El camino de un nodo así mismo se llama ciclo.

ORDENAMIENTO

¿Qué es ordenamiento?

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento.
El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia, tal que represente un orden, el cual puede ser numérico, alfabético o alfanumérico, ascendente o descendente.
El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado.
El método de ordenamiento es conviene usar Cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Métodos de Ordenamiento

Existen diferentes métodos de ordenamiento de datos como lo son:

Método Burbuja:

El metodo de la burbuja es uno de los mas simples, es tan facil como comparar todos

los elementos de una lista contra todos, si se cumple que uno es mayor o menor a

otro, entonces los intercambia de posición.

Por ejemeplo, imaginemos que tenemos los siguientes valores:

Lo que haria una burbuja simple, seria comenzar recorriendo los valores de izq. a

derecha, comenzando por el 5. Lo compara con el 6, con el 1, con el 0 y con el 3, si

es mayor o menor (dependiendo si el orden es ascendiente o descendiente) se

intercambian de posicion. Luego continua con el siguiente, con el 6, y lo compara con

todos los elementos de la lista, esperando ver si se cumple o no la misma condicion

que con el primer elemento. Asi, sucesivamente, hasta el ultimo elemento de la lista.

Programa de Burbuja :

class OrdenaAlgoritmo {

public static void ordenarMejorado( int [] arreglo) {
int pasadas = 0;
int comparaciones = 0;
boolean hayCambios = true;
for (int i = 0; hayCambios ; i++) {
++pasadas;
hayCambios = false;
for (int j = 0; j < arreglo.length - 1; j++) {
++comparaciones;
if (arreglo[j] > arreglo[j + 1]) {
intercambiar(arreglo, j, j+1);
hayCambios = true;
}
}
}
estadisticas(pasadas, comparaciones);
}

private static void intercambiar(int [] arreglo, int a, int b) {
int tmp = arreglo[a];
arreglo[a] = arreglo[b];
arreglo[b] = tmp;
}

private static void estadisticas( int pasadas, int comparaciones) {
System.out.println( "Pasadas: " + pasadas );
System.out.println( "Comparaciones: " + comparaciones );
}
}

public class OrdenaBurbuja {
public static void main (String args[]) {

int [] valores = {15,35,01,05,04,03,19,45,13,02,55,8,
78,997,451,546,12,16,24,103,99,784,
4541,15};

//OrdenaAlgoritmo.ordenar(valores);
OrdenaAlgoritmo.ordenarMejorado(valores);
// Mostrar arreglo.
for (int i = 0; i < valores.length ; i++)
System.out.println ( "valores["+i+"]: "+ valores[i]);

}
}

Método Quicksort

Sin duda, este algoritmo es uno de los mas eficientes. Este metodo es el mas rapido
gracias a sus llamadas recursivas, basandose en la teoria de divide y vencerás.
Lo que hace este algoritmo es dividir recurvisamente el vector en partes iguales,
indicando un elemento de inicio, fin y un pivote (o comodin) que nos permitira
segmentar nuestra lista. Una vez dividida, lo que hace, es dejar todos los mayores que
el pivote a su derecha y todos los menores a su izq. Al finalizar el algoritmo, nuestros
elementos estan ordenados.

En esta figura se ilustra de mejor manera un vector con mas elementos, usando como
pivote el primer elemento:

Programa de Quicksort

public class Ordenador {

public int[] quicksort(int numeros[])
//El metodo recibe los datos del arreglo
{
return quicksort(numeros,0,numeros.length-1);
//Llama al metodo quicksort para ordenar los datos
}
public int[] quicksort(int numeros[],int izq,int der)
//Recibe los valores del arreglo, el valor 0, y el tamano del arreglo
{
if(izq>=der)
return numeros;
/*Si izq que es igual a cero es mayor o igual a der que es el tamano del arreglo,
* el metodo regresa el arreglo.
*/
int i=izq,d=der;
//Se le asignan los valores de izq (0) & der(tamano del arreglo) a las variables i & d.
if(izq!=der)
//Si izq es diferente a der entonces se realiza lo siguiente
{
int pivote;
int aux;
pivote = izq;
while(izq!=der)
{imprimeArreglo(numeros);
while(numeros[der]>=numeros[pivote] && izq<der)
der--;
while(numeros[izq]<numeros[pivote] && izq<der)
izq++;
if(der!=izq)
{
aux = numeros[der];
numeros[der]= numeros[izq];
numeros[izq]=aux;}
}
if(izq==der){
quicksort(numeros,i,izq-1);
quicksort(numeros,izq+1,d);
}
}
else
return numeros;
return numeros;
}

public void imprimeArreglo(int arreglo[])
{
String imp="";
for(int i=0;i<arreglo.length;i++)
{
if(i!=arreglo.length-1)
imp=imp+arreglo[i]+",";
else
imp=imp+arreglo[i]+"";
}
System.out.println(imp);
}
public static void main(String[] args) {
int array[] ={4,2,5,7,6,1,3}; //Declaracion del arreglo
Ordenador a = new Ordenador();//Crea un objeto de la clase ordenador
a.quicksort(array);//Llama al metodo quicksort, con los datos del arreglo
}
}

Método ShellSort
Ordena subgrupos de elementos separados K unidades (respecto de su posición en el arreglo) del arreglo original. El valor K es llamado incremento.
Después de que los primeros K subgrupos han sido ordenados (generalmente utilizando INSERCION DIRECTA), se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Al principio del proceso se escoge la secuencia de decrecimiento de incrementos; el último valor debe ser 1.
"Es como hacer un ordenamiento de burbuja pero comparando e intercambiando elementos."
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.

Programa ShellSort

public class ShellSort

{

private long[] data;

private int len;

public ShellSort(int max) {

data = new long[max];

len = 0;

}

public void insert(long value)

{

data[len] = value;

len++;

}

public void display()

{

System.out.print("Datos:");

for (int j = 0; j < len; j++)

System.out.print(data[j] + " ");

System.out.println("");

}

public void shellSort()

{

int inner, outer;

long temp;

//find initial value of h

int h = 1;

while (h <= len / 3)

h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

while (h > 0) // decreasing h, until h=1

{

// h-sort the file

for (outer = h; outer < len; outer++)

{

temp = data[outer];

inner = outer;

// one subpass (eg 0, 4, 8)

while (inner > h - 1 && data[inner - h] >= temp)

{

data[inner] = data[inner - h];

inner -= h;

}

data[inner] = temp;

}

h = (h - 1) / 3; // decrease h

}

public static void main(String[] args)

{

int maxSize = 10;

ShellSort arr = new ShellSort(maxSize);

for (int j = 0; j < maxSize; j++)

{

long n = (int) (java.lang.Math.random() * 99);

arr.insert(n);

}

System.out.println("Datos no Ordenados");

arr.display();

arr.shellSort();

arr.display();

}

BUSQUEDA

Este método puede considerarse como una generalización de la clasificación por urnas. Aprovecha

la estrategia de la forma más antigua de clasificación manual, consistente en hacer diversos montones de fichas, cada uno caracterizado por tener sus componentes un mismo dígito (letra, si es

alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte de

nuevo en montones según el siguiente dígito de la clave.

Programa Radix

public class ORDENAMIENTO_RADIX{
   public static void radixSort(int[] arr){
       if(arr.length == 0)
           return;
       int[][] np = new int[arr.length][2];
       int[] q = new int[0x100];
       int i,j,k,l,f = 0;
       for(k=0;k<4;k++){
           for(i=0;i<(np.length-1);i++)
               np[i][1] = i+1;
           np[i][1] = -1;
           for(i=0;i<q.length;i++)
               q[i] = -1;
           for(f=i=0;i<arr.length;i++){
               j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
               if(q[j] == -1)
                   l = q[j] = f;
               else{
                   l = q[j];
                   while(np[l][1] != -1)
                       l = np[l][1];
                   np[l][1] = f;
                   l = np[l][1];
               }
               f = np[f][1];
               np[l][0] = arr[i];
               np[l][1] = -1;
           }
           for(l=q[i=j=0];i<0x100;i++)
               for(l=q[i];l!=-1;l=np[l][1])
                       arr[j++] = np[l][0];
       }
   }
   public static void main(String[] args){
       int i;
       int[] arr = new int[15];
       System.out.print("original: ");
       for(i=0;i<arr.length;i++){
           arr[i] = (int)(Math.random() * 1024);
           System.out.print(arr[i] + " ");
       }
       radixSort(arr);
       System.out.print("\nsorted: ");
       for(i=0;i<arr.length;i++)
           System.out.print(arr[i] + " ");
       System.out.println("\nDone ;-)");
   }
}

Búsqueda Secuencial

Definición:

Está diseñada para localizar un elemento con ciertas propiedades dentro de una estructura de datos; por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos, o el mejor movimiento en una partida de ajedrez.

La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave.

En una búsqueda secuencial (a veces llamada búsqueda lineal), los elementos de una lista o vector

se exploran (se examinan) en secuencia, uno después de otro. La búsqueda secuencial es necesaria,

por ejemplo, si se desea encontrar la persona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad. Los directorios de teléfonos están organizados alfabéticamente

por el nombre del abonado en lugar de por números de teléfono, de modo que deben explorarse

todos los números, uno después de otro, esperando encontrar el número 958-220000.

El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda

Programa

public class BSecuencial {

public static void main(String[] args) throwsIOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};

System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar

for (int i=0; i<VectorNombres.length;i++){

if(nombre.equalsIgnoreCase(VectorNombres[i])){

JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}

if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de búsqueda, encontrados "+encontrados+" elementos iguales");

Búsqueda Hash

Función Hash

En informática, hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo

Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.