Enlaces




Frase

"Aquel que pregunta una vez es tonto una vez, aquel que no pregunta nunca es tonto siempre".

Libros de Interes

Libros interesantes

Online Demos

¿Qué es una Estructura de Datos?

Las estructuras de datos nos han estado rodeando desde la era de la programación estructurada. Una definición de esa era: una estructura de datos es un conjunto de tipos, un tipo diseñado partiendo de ese conjunto de tipos, un conjunto de funciones, y un conjunto de axiomas. Esta definición implica que una estructura de datos es un tipo con implementación. En nuestra era de la programación orientads a objetos, tipo con implementación significa clase.
La definición "una estructura de datos es una clase" es demasiado amplia porque supone que Empleado, Vehículo, Cuenta, y otras muchas clases específicas de entidades del mundo real son estructuras de datos. Aunque esas clases estructuran varios ítems de datos, describen entidades del munto real (en la forma de objetos) en lugar de describir contenedores de objetos para otras entidades objetos (y posiblemente otro contenedor). Esta idea de contenido da una definición más apropiada para una estructura de datos: una estructura de datos es una clase contenedora que proporciona almacenamiento para ítems de datos, y capacidades para almacenar y recuperar estos datos. Algunos ejemplos de estructuras de datos son los arreglos, las listas enlazadas, las pilas y las colas.

¿Qué es un Algoritmo?

Normalmante los algoritmos se asocian con estructuras de datos. Un algoritmo es una secuencia de instrucciones que realizan una tarea en un periodo de tiempo finito. El algoritmo recibe cero o más entradas, produce al menos una salida, consiste en instrucciones claras y poco ambiguas, termina después de un número finito de pasos, y es lo suficientemente básico que una persona puede llevar a cabo el algoritmo utilizando lápiz y papel. Por el contrario, un programa no es necesariamente finito: el programa, como un servidor Web, podría no terminar nunca si no hay intervención externa. Algunos ejemplos de algoritmos asociados con estructuras de datos son: búqueda-lineal, ordenación-de-burbuja, búsqueda-binaria, concatenación-de-listas-enlazadas, etc.

Arreglos

Un arreglo es un tipo de estructura de datos que consta de un número fijo de elementos del mismo tipo. En una máquina, dichos elementos se almacenan en posiciones contiguas de memoria. Estos elementos pueden ser variables o estructuras. Para definirlos se utiliza la expresión:

tipo_de_elemento nombre_del_arreglo[número_de_elementos_del_arreglo];
int mapa[100];

Cada uno de los elementos de los que consta el arreglo tiene asignado un número (índice). El primer elemento tiene índice 0 y el último tiene índice número_de_elementos_del_arreglo-1. Para acceder a ese elemento se pone el nombre del arreglo con el índice entre corchetes:

nombre_del_arreglo[índice]
mapa[5]

Los elementos no tienen por qué estar determinados por un solo índice, pueden estarlo por dos (por ejemplo, fila y columna), por tres (p.e. las tres coordenadas en el espacio), o incluso por más. A estos arrays definidos por más de un índice se le llaman arreglos multidimensionales o matrices, y se definen:
tipo_de_elemento nombre_del_arreglo[número1] [número2]... [númeroN];
int mapa[100][50][399];
Y para acceder a un elemento de índices i1,i2,...,iN, la expresión es similar:
nombre_del_arreglo[i1][i2]...[iN]
mapa[34][2][0]

Arreglos de Una Dimensión
El tipo de arreglo más simple tiene una dimensión: cada elemento se asocia con un único índice. Java proporciona tres técnicas para crear un array de una dimensión: usar sólo un inicializador, usar sólo la palabra clave new, y utilizar la palabra clave new con un inicializador.
El siguiente fragmento ilustra como crear un arreglo de animales:

// Create an array of animals.
String animals [] = { "Tiger", "Zebra", "Kangaroo" };

La siguiente figura ilustra los elementos y la variable arreglo uni-dimensional resultante:


Arreglos de Dos Dimensiones
Un arreglo de dos dimensiones, también conocido como tabla o matriz, donde cada elemento se asocia con una pareja de índices, es otro arreglo simple. Conceptualizamos un arreglo bi-dimensional como una cuadrícula rectángular de elementos divididos en filas y columnas, y utilizamos la notación (fila, columna) para identificar un elemento específico. La siguiente figura ilustra esta visión conceptual y la notación específica de los elementos:



Esta técnica requiere una de estas sintaxis:
type variable_name '[' ']' '[' ']' '=' '{' [ rowInitializer [ ',' ... ] ] '}' ';'

type '[' ']' '[' ']' variable_name '=' '{' [ rowInitializer [ ',' ... ] ] '}' ';'

Donde rowInitializer tiene la siguiente sintaxis:
'{' [ initial_value [ ',' ... ] ] '}'

El siguiente código usa sólo un inicializador para crear un arreglo bi-dimensional que almacena datos basados en un tipo primitivo:
double [][] temperatures = { { 20.5, 30.6, 28.3 },
{ -38.7, -18.3, -16.2 } }; // Celsius temperatures

Detrás de la escena, se asigna memoria y se inicializan esto datos. El operador igual-a asigna la referencia del arreglo bi-dimensional a temperatures. La siguiente figura ilustra el arreglo bi-dimensional resultante desde un punto de vista conceptual y de memoria.

Listas

Una lista está formada por un número variable de datos (elementos) de un mismo tipo, ordenados según una secuencia lineal. Cada elemento, salvo el primero, tiene un predecesor en la lista. Todos los elementos, salvo el último, tienen un sucesor. La lista es una estructura dinámica.
Podemos definir una lista como una estructura de datos formada por registros de, al menos, dos campos, en que uno de ellos contiene información que permite localizar al siguiente registro en la lista según una secuencia dada. La lista no es direccionable, tan sólo se puede recuperar un elemento accediendo previamente a los que le anteceden, y por tanto, en cada momento hay sólo un elemento en disposición de ser procesado.
Un tipo de lista especialmente importante es la pila o lista de LIFO, en que se añaden y eliminan elementos sólo en un extremo; es decir, no se puede eliminar más que el elemento que ocupa el primer lugar de la lista en ese momento. Las pilas se utilizan en hardware y software para almacenar las direcciones de instrucciones desde las que se hacen llamadas a subrutinas.
Se denominan cola o listas FIFO a una lista en que las inserciones se realizan sólo en el final y sólo se puede acceder o eliminar en un instante dado el primer elemento de la lista.
Las listas se memorizan utilizando punteros.


Representación de una lista


Listas Enlazadas
una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio.





Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares



Lista de Enlace Simple
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene null para indicar el final de la lista. a la variable de referencia se la suele llamar top. . La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:


Un algoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo está implicado de alguna forma porque tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlace simple no existe.

DECLARE CLASS Node
DECLARE STRING name
DECLARE Node next
END DECLARE
DECLARE Node top = NULL

Este pseudocódigo declara una clase auto-referenciada llamada Node con un campo no de enlace llamado name y un campo de enlace llamado next. También declara una variable de referencia top (del tipo Node) que contiene una referencia al primer Node de una lista de enlace simple. Como la lista todavía no existe, el valor inicial de top es NULL. Cada uno de los siguientes cuatro casos asume las declaraciones de Node y top.


La lista de enlace simple no existe
Este es el caso más simple. Se crea un Node, se asigna su referencia a top, se inicializa su campo no de enlace, y se asigna NULL a su campo de enlace. El siguiente pseudocódigo realiza estas tareas:
  • top = NEW Node
  • top.name = "A"
  • top.next = NULL


En la siguiente imagen se puede ver la lista de enlace simple que emerge del pseudocódigo anterior:



El nodo debe insertarse antes del primer nodo
Se crea un Node, se inicialia su campo no de enlace, se asigna la referencia de top al campo de enlace next, y se asigna la referencia del Node recien creado a top. El siguiente pseudocódigo (que asume que se ha ejecutado el pseudocódigo anterior) realiza estas tareas:
DECLARE Node temp
temp = NEW Node
temp.name = "B"
temp.next = top
top = temp

El resultado del listado anterior aparece en la siguiente imagen:


El nodo debe insertarse detrás del último nodo

Se crea un Node, se inicializa su campo no de enlace, se asigna NULL al campo de enlace, se atraviesa la lista de enlace simple hasta el último Node, y se asigna la referencia del Node recien creado al campo next del último nodo. El siguiente pseudocódigo realiza estas tareas:

temp = NEW Node
temp.name = "C"
temp.next = NULL
DECLARE Node temp2
temp2 = top
// We assume top (and temp2) are not NULL
// because of the previous pseudocode
WHILE temp2.next IS NOT NULL
temp2 = temp2.next
END WHILE
// temp2 now references the last node
temp2.next = temp

La siguiente imagen revela la lista después de la inserceción del nodo C después del nodo A.



El nodo se debe insertar entre dos nodos
Este es el caso más complejo. Se crea un Node, se inicializa su campo no de enlace, se atraviesa la lista hasta encontrar el Node que aparece antes del nuevo Node, se asigna el campo de enlace del Node anterior al campo de enlace del Node recien creado, y se asigna la referencia del Node recien creado al campo del enlace del Node anterior. El siguiente pseudocódigo realiza estas tareas:

temp = NEW Node
temp.name = "D"
temp2 = top
// We assume that the newly created Node is inserted after Node
// A and that Node A exists. In the real world, there is no
// guarantee that any Node exists, so we would need to check
// for temp2 containing NULL in both the WHILE loop's header
// and after the WHILE loop completes.
WHILE temp2.name IS NOT "A"
temp2 = temp2.next
END WHILE
// temp2 now references Node A.
temp.next = temp2.next
temp2.next = temp

La siguiente imagen muestra la inserción del nodo D entre los nodos A y C.



El siguiente listado presenta el equivalente Java de los ejemplos de pseudocódigo de insercción anteriores:

// SLLInsDemo.java
class SLLInsDemo {
static class Node {
String name;
Node next;
}

public static void main (String [] args) {
Node top = null;

// 1. The singly linked list does not exist
top = new Node ();
top.name = "A";
top.next = null;

dump ("Case 1", top);

// 2. The singly linked list exists, and the node must be inserted
// before the first node

Node temp;
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;

dump ("Case 2", top);

// 3. The singly linked list exists, and the node must be inserted
// after the last node
temp = new Node ();
temp.name = "C";
temp.next = null;

Node temp2;
temp2 = top;

while (temp2.next != null)
temp2 = temp2.next;

temp2.next = temp;

dump ("Case 3", top);

// 4. The singly linked list exists, and the node must be inserted
// between two nodes
temp = new Node ();
temp.name = "D";

temp2 = top;

while (temp2.name.equals ("A") == false)
temp2 = temp2.next;
temp.next = temp2.next;
temp2.next = temp;

dump ("Case 4", top);
}

static void dump (String msg, Node topNode) {
System.out.print (msg + " ");

while (topNode != null) {
System.out.print (topNode.name + " ");
topNode = topNode.next;
}
System.out.println ();
}
}

Borrar el Primer nodo
Asigna el enlace del campo next del nodo referenciado por top a top:
• top = top.next; // Reference the second Node (or NULL if there is only one Node)
La siguiente imagen presenta las vistas anterior y posterior de una lista donde se ha borrado el primer nodo. en esta figura, el nodo B desaparece y el nodo A se convierte en el primer nodo.



Borrar cualquier nodo que no sea el primero
Localiza el nodo que precede al nodo a borrar y le asigna el enlace que hay en el campo next del nodo a borrar al campo next del nodo que le precede. El siguiente pseudocódigo borra el nodo D:


temp = top
WHILE temp.name IS NOT "A"
temp = temp.next
END WHILE
// We assume that temp references Node A
temp.next = temp.next.next
// Node D no longer exists

La siguiente figura presenta las vistas anterior y posterior de una lista donde se ha borrado un nodo intermedio. En esa figura el nodo D desaparece.


El siguiente listado representa el equivalente Java a los pseudocódigos de borrado anteriores:

// SLLDelDemo.java
class SLLDelDemo {
static class Node {
String name;
Node next;
}

public static void main (String [] args) {
// Build Figure 6's singly linked list (i.e., B A D C)

Node top = new Node ();
top.name = "C";
top.next = null;

Node temp = new Node ();
temp.name = "D";
temp.next = top;
top = temp;

temp = new Node ();
temp.name = "A";
temp.next = top;
top = temp;

temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;

dump ("Initial singly-linked list", top);

// 1. Delete the first node
top = top.next;

dump ("After first node deletion", top);

// Put back B
temp = new Node ();
temp.name = "B";
temp.next = top;
top = temp;

// 2. Delete any node but the first node
temp = top;

while (temp.name.equals ("A") == false)
temp = temp.next;
temp.next = temp.next.next;

dump ("After D node deletion", top);
}

static void dump (String msg, Node topNode) {
System.out.print (msg + " ");

while (topNode != null) {
System.out.print (topNode.name + " ");
topNode = topNode.next;
}
System.out.println ();
}
}


Lista Doblemente Enlazada/span>
Las listas de enlace simple restringen el movimiento por lo nodos a una sóla dirección: no puede atravesar una lista de enlace simple en dirección opuesta a menos que primero utilice el algoritmo de inversión para invertir los enlaces de los nodos, lo que lleva tiempo. Después de atraversarlos en dirección opuesta, problamente necesitará repetir la inversión para restaurar el orden original, lo que lleva aún más tiempo. Un segundo problema implica el borrado de nodos: no puede borrar un nodo arbitrario sin acceder al predecesor del nodo. Estos problemas desaperecen cuando se utiliza una lista doblemente enlazada.
Una lista doblemente enlazada es una lista enlazada de nodos, donde cada nodo tiene un par de campos de enlace. Un campo de enlace permite atravesar la lista hacia adelante, mientras que el otro permite atravesar la lista haca atrás. Para la dirección hacia adelante, una variable de referencia contiene una referencia al primer nodo. Cada nodo se enlaza con el siguiente mediante el campo de enlace next, excepto el último nodo, cuyo campo de enlace next contiene null para indicar el final de la lista (en direccion hacia adelante). De forma similar, para la dirección contraria, una variable de referencia contiene una referencia al último nodo de la dirección normal (hacia adelante), lo que se interpreta como el primer nodo. Cada nodo se enlaza con el anterior mediante el campo de enlace previous, y el primer nodo de la direccion hacia adelante, contiene null en su campo previous para indicar el fin de la lista. La siguiente figura representa una lista doblemente enlazada de tres nodos, donde topForward referencia el primer nodo en la direccion hacia adelante, y topBackward referencia el primero nodo la dirección inversa.


El siguiente listado muestra la inserción de nodos para crear la lista de la figura anterior, el borrado de nodos ya que elimina el nodo B de la lista, y el movimiento por la lista en ambas direcciones:


// DLLDemo.java
class DLLDemo {
static class Node {
String name;
Node next;
Node prev;
}

public static void main (String [] args) {
// Build a doubly linked list

Node topForward = new Node ();
topForward.name = "A";

Node temp = new Node ();
temp.name = "B";

Node topBackward = new Node ();
topBackward.name = "C";

topForward.next = temp;
temp.next = topBackward;
topBackward.next = null;

topBackward.prev = temp;
temp.prev = topForward;
topForward.prev = null;

// Dump forward singly linked list

System.out.print ("Forward singly-linked list: ");

temp = topForward;
while (temp != null){
System.out.print (temp.name);
temp = temp.next;
}

System.out.println ();

// Dump backward singly linked list

System.out.print ("Backward singly-linked list: ");

temp = topBackward;
while (temp != null){
System.out.print (temp.name);
temp = temp.prev;
}

System.out.println ();

// Reference node B

temp = topForward.next;

// Delete node B

temp.prev.next = temp.next;
temp.next.prev = temp.prev;

// Dump forward singly linked list

System.out.print ("Forward singly-linked list (after deletion): ");

temp = topForward;
while (temp != null){
System.out.print (temp.name);
temp = temp.next;
}

System.out.println ();

// Dump backward singly linked list

System.out.print ("Backward singly-linked list (after deletion): ");

temp = topBackward;
while (temp != null){
System.out.print (temp.name);
temp = temp.prev;
}
System.out.println ();
}
}
[+/-] Leer más...

Pilas

Una pila es una estructura de datos de acceso restrictivo a sus elementos. Se puede entender como una pila de libros que se amontonan de abajo hacia arriba. En principio no hay libros; después ponemos uno, y otro encima de éste, y así sucesivamente. Posteriormente los solemos retirar empezando desde la cima de la pila de libros, es decir, desde el último que pusimos, y terminaríamos por retirar el primero que pusimos, posiblemente ya cubierto de polvo.

Como el último elemento insertado es el primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas como pilas LIFO (last-in, first-out).
Los datos se push (insertan) dentro y se pop (recuperan/borran) de la parte superior de la pila. La siguiente figura ilustra una pila con tres String cada uno insertado en la parte superior de la pila.




Implementación mediante array
Esta implementación es estática, es decir,...

Esta implementación es estática, es decir, da un tamaño máximo fijo a la pila, y si se sobrepasa dicho límite se produce un error. La comprobación de apilado en una pila llena o desapilado en una pila vacía no se han hecho, pero sí las funciones de comprobación, que el lector puede modificar según las necesidades de su programa.
- Declaración:
struct tpila
{
int cima;
int elementos[MAX_PILA];
};
Nota: MAX_PILA debe ser mayor o igual que 1.

- Procedimiento de Creación:
void crear(struct tpila *pila)
{
pila->cima = -1;
}

- Función que devuelve verdadero si la pila está vacía:
int vacia(struct tpila *pila)
{
return (pila->cima == -1);
}

- Función que devuelve verdadero si la pila está llena:
int llena(struct tpila *pila)
{
return (pila->cima == MAX_PILA);
}

- Procedimiento de apilado:

void apilar(struct tpila *pila, int elem)
{
pila->elementos[++pila->cima] = elem;
}

- Procedimiento de desapilado:
void desapilar(struct tpila *pila, int *elem)
{
*elem = pila->elementos[pila->cima--];
}

Programa de prueba:
#include

int main(void)
{
struct tpila pila;
int elem;

crear(&pila);
if (vacia(&pila)) printf("\nPila vacia.");
if (llena(&pila)) printf("\nPila llena.");
apilar(&pila, 1);
desapilar(&pila, &elem);
return 0;
}


[+/-]Leer más...

Implementación mediante lista enlazada
Para hacer la implementación se utiliza una lista..


Para hacer la implementación se utiliza una lista con cabecera ficticia (ver apartado de listas). Dado el carácter dinámico de esta implementación no existe una función que determine si la pila está llena. Si el usuario lo desea puede implementar un análisis del código devuelto por la función de asignación de memoria.

- Declaración:
struct tpila
{
int clave;
struct tpila *sig;
};
- Procedimiento de creación:
void crear(struct tpila **pila)
{
*pila = (struct tpila *) malloc(sizeof(struct tpila));
(*pila)->sig = NULL;
}
- Función que devuelve verdadero si la pila está vacía:
int vacia(struct tpila *pila)
{
return (pila->sig == NULL);
}

- Procedimiento de apilado (apila al comienzo de la lista):
void apilar(struct tpila *pila, int elem)
{
struct tpila *nuevo;

nuevo = (struct tpila *) malloc(sizeof(struct tpila));
nuevo->clave = elem;
nuevo->sig = pila->sig;
pila->sig = nuevo;
}
- Procedimiento de desapilado (desapila del comienzo de la lista):
void desapilar(struct tpila *pila, int *elem)
{
struct tpila *aux;

aux = pila->sig;
*elem = aux->clave;
pila->sig = aux->sig;
free(aux);
}

Programa de prueba:
int main(void)
{
struct tpila *pila;
int elem;

crear(&pila);
if (vacia(pila)) printf("\nPila vacia!");
apilar(pila, 1);
desapilar(pila, &elem);

return 0;
}

[+/-] Leer más...

Elegir entre implementación con listas o con arrays
El uso del array es idóneo cuando se conoce de antemano el número máximo


El uso del array es idóneo cuando se conoce de antemano el número máximo de elementos que van a ser apilados y el compilador admite una región contigua de memoria para el array. En otro caso sería más recomendable usar la implementación por listas enlazadas, también si el número de elementos llegase a ser excesivamente grande.
La implementación por array es ligeramente más rápida. En especial, es mucho más rápido a la hora de eliminar los elementos que hayan quedado en la pila. Por lista enlazada esto no es tan rápido. Por ejemplo, piénsese en un algoritmo que emplea una pila y que en algunos casos al terminar éste su ejecución deja algunos elementos sobre la pila. Si se implementa la pila mediante una lista enlazada entonces quedarían en memoria una serie de elementos que es necesario borrar. La única manera de borrarlos es liberar todas las posiciones de memoria que le han sido asignadas a cada elemento, esto es, desapilar todos los elementos. En el caso de una implementación con array esto no es necesario, salvo que quiera liberarse la región de memoria ocupada por éste.

El siguiente listado presenta una implementación de Stack utilizando una lista de enlace simple:
// LinkedListStack.java

package com.javajeff.cds;

public class LinkedListStack implements Stack {
private static class Node {
Object o;
Node next;
}

private Node top = null;

public boolean isEmpty () {
return top == null;
}

public Object peek () {
if (top == null)
throw new java.util.EmptyStackException ();
return top.o;
}

public void push (Object o) {
Node temp = new Node ();
temp.o = o;
temp.next = top;
top = temp;
}

public Object pop () {
if (top == null)
throw new java.util.EmptyStackException ();
Object o = top.o;
top = top.next;
return o;
}
}

[+/-] Leer más...

Colas

Una cola 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 (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

La siguiente figura ilustra las colas lineal y circular:


La cola lineal de la figura anterior almacena cuatro enteros, con el entero 1 en primer lugar. Esa cola está llena y no puede almacenar más datos adicionales porque rear identifica la parte final de la cola. La razón de la posición vacía, que identifica front, implica el comportamiento lineal de la cola. Inicialmente, front y rear identifican la posición más a la izquierda, lo que indica que la cola está vacía. Para almacenar el entero 1, rear avanza una posición hacia la derecha y almacena 1 en esa posición. Para recuperar/borrar el entero 1, front avanza una posición hacia la derecha.

  • Crear: se crea la cola vacía.
  • Enqueue (añadir, entrar, push): se añade un elemento a la cola. Se añade al final de esta.
  • Dequeue (sacar, salir, pop): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
  • Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primero elemento que entró.




El siguiente listado presenta una a implementación de Queue de una cola lineal basada en un array uni-dimensional:

// ArrayLinearQueue.java

package com.javajeff.cds;

public class ArrayLinearQueue implements Queue {
private int front = -1, rear = -1;
private Object [] queue;

public ArrayLinearQueue (int maxElements) {
queue = new Object [maxElements];
}

public void insert (Object o) {
if (rear == queue.length - 1)
throw new FullQueueException ();
queue [++rear] = o;
}

public boolean isEmpty () {
return front == rear;
}

public boolean isFull () {
return rear == queue.length - 1;
}

public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
return queue [++front];
}
}

[+/-] Ejemplo...

Tablas Hash

Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.
Las tablas hash se suelen implementar sobre arrays de una dimensión, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de búsqueda promedio O,[1] sin importar el número de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en función del número de elementos.

Comparada con otras estructuras de arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes cantidades de información.

Las tablas hash almacenan la información en posiciones pseudo-aleatorias, así que el acceso ordenado a su contenido es bastante lento. Otras estructuras como árboles binarios auto-balanceables son más lentos en promedio (tiempo de búsqueda O(log n)) pero la información está ordenada en todo momento.


Ejemplo
Para comenzar pensemos en esta tabla como un arreglo:


Para saber donde vamos a guardar a nuestro jugador modulamos la clave por el tamaño de la tabla




Con este algoritmo si quisiéramos accesar un jugador en particular usaremos una ecuación simple como: player = table[key % 10];
Este algoritmo nos daría el elemento inmediatamente y tuviera una notación de gran O de O(c)
Uno de los problemas con tablas hash es que choques pueden ocurrir frecuentemente.
Por ejemplo intenten insertar los jugadores con las claves 143,674 y 645,394
No se puede por que los dos tratarían de ocupar la celda 4
Para resolver esto utilizamos una función de hashing o modificamos la tabla para que choques no ocurran


Una alternativa sería de sumar los dígitos
143,674 = 1 + 4 + 3 + 6 + 7 + 4 = 25
645,394 = 6 + 4 + 5 + 3 + 9 + 4 = 31
9 + 9 + 9 + 9 + 9 + 9 = 54
Hashing doble
Utilizar el mismo algoritmo u otro para hash la clave obtenida la primera vez

143,674 = 1 + 4 + 3 + 6 + 7 + 4 = 25
645,394 = 6 + 4 + 5 + 3 + 9 + 4 = 31
25 = 2 + 5 = 7
31 = 3 + 1 = 4

Hay muchas funciones de hashing que se pueden hacer sobre enteros pero es imposible de que no ocurran choques en las tablas
El otro tipo de dato que usualmente se le aplica hashing es a las cadenas de caracteres
El siguiente algoritmo hace un buen trabajo en hash cadenas en enteros con muy pocos choques

unsigned long int StringHash( const char* p_string )
{
unsigned long int hash = 0;
int i;
int length = strlen( p_string );
for( i = 0; i < onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"

Así que ninguna tabla hash es perfecta lo mas seguro es que nos vamos a encontrar con choques. Simplemente hay que encontrar maneras de manejar los choques.
Uno de los métodos comunes es de sobreflujo lineal (linear overflow.) Este método simplemente chequea si el índice está lleno y si lo está sube el valor del índice por uno hasta que encuentre uno vacío.

Este método no sirve para nada y destruye lo que una tabla hash quiere hacer. Vuelve el algoritmo de hash de O(c) a O(n). También existe el sobre flujo cuadrático
1 exp 2 (1) and then 2 exp 2 (4) and then 3 exp 2 (9)



Unos de los mejores métodos es el de sobreflujo enlazado
Este método realiza una lista enlazada en cada celda de la tabla
Supongamos que tenemos un arreglo de 10 celdas y utilizamos el algoritmo de módulo 10 sobre la clave para insertar objetos en el arreglo
Player 1: 345,752
Player 2: 546,182
Player 3: 798,500
Player 4: 123,430

Las claves se simplifican a 2, 2, 0, 0
Antes esto nos habría dado problemas pero como ahora tenemos una lista enlazada en cada celda no hay dificultades

Un Ejemplo


[+/-] Ejemplo...

Recursividad

En su forma más simple recursividad se define como la habilidad de una función de llamarse a si mismo. Es un concepto bastante fácil de aprender pero difícil de aplicar.

#include
#include
#include
#include
#include

class Matematicas
{
public:
void Tablas(int T,int B)
{

if(B<11) n="="> "<:Fin<:endl; return; } Torres(N-1,Inicio,Fin,Aux); cout<:Inicio<<" --> "<:Fin<:endl; Torres(N-1,Aux,Inicio,Fin); return; } }tec; main() { int t,b,op=0; while(op!=5) { clrscr(); cout<<"\n1) Tablas de Multiplicar\n2) Factorial de un Numero\n"; cout<<"3) Formula Lineal\n4) Torres de Hanoi\n5) Salida"<:endl; gotoxy(1,1); cout<<"Que deseas hacer: "; cin>>op;

clrscr();
switch(op)
{
case 1:

cout<<"Que Tabla de Multiplicar deseas Imprimir?"<>t;
cout<<"Desde que Numero deseas empezar a multiplicar (Menor que 10)"<>b;
tec.Tablas(t,b);
break;

case 2:

cout<<"Que Factorial deseas conocer"<>t;
cout<:t<<"! = "<:tec.Factorial(t)<:endl; break; case 3: cout<<"f(x) = x^3 + 2x + 3"<:endl; cout<<"Escribe la Base (Menor de 10)"<>t;
tec.Formula(t);
break;

case 4:
cout<<"Cuantos discos deseas mover?"<>t;
tec.Torres(t,'A','B','C');
break;

case 5:

cout<<"Salida..."; break; default: cout<<"Opcion Erronea..."; break; } getch(); } }

[+/-] Ejemplo de Recursividad...

Características
  • Ser una herramienta muy potente en determinadas aplicaciones,sobre todo de cálculo, pudiendo ser utilizada como alternativa a la repetición o estructura repetitiva.
  • Toda función/método recursivo debe tener dos partes:

  • i. una parte de terminación en la que se deja de hacer llamadas (es lo que denominaremos caso base) y que constituye la condición de terminación de la función,
  • permitiendo así que no se produzca una recursión infinita.
  • ii. y una llamada recursiva con sus propios parámetros, en los que éstos sufrirán alguna variación.
  • Cuando una función se llama así misma, se denomina función recursiva y denominaremos a la llamada a sí misma llamada recursiva.


Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva.

FUNCIÓN Factorial(n)
INICIO
SI (n<2) factorial =" 1;" factorial =" n" style="font-weight: bold;">Torres de Hanoi
Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.
El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.
Las reglas son:
  • Sólo se puede mover un disco cada vez.
  • Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
  • Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:

  1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
  2. Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
  3. mover disco n a destino //mover la ficha grande hasta la varilla final
  4. hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
  5. terminar

Veamos el algoritmo en pseudo código

Hanoi( int n, int start, int destination, int open )
Hanoi( n - 1, start, open, destination )
Move( n, start, destination )
Hanoi( n - 1, open, destination, start )

Árboles

Los árboles se pueden definir como un tipo restringido de grafo. Un árbol es una estructura jerarquica de datos que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.


Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura.

Árboles Binarios

Un árbol binario es una estructura de datos en la cual cada nodo:
* No tiene hijos (hoja).
* Tiene un hijo izquierdo y un hijo derecho.
* Tiene un hijo izquierdo.
* Tiene un hijo derecho.



Tipos de árboles binarios
  • Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.



  • Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
  • Balance—Un árbol binario está balanceado si existen el mismo número de nodos hijos derechos como nodos hijos izquierdos



  • Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
  • A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Recorridos sobre árboles binarios
El arbol binario puede ser recorrido mediante los recorridos: Preorden, Postorden e implenta el Inorder.
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. En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4.

Preorden( nodo )
procesan nodo )
Preorden( nodo.izquierdo )
Preorden( nodo.derecho )
Fin Preorden

Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Postorden( nodo )
Postorden nodo.izquierdo )
Postorden( nodo.derecho )
procesar( nodo )
Fin Postorden

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 árbol de búsqueda binaria este recorrido daría los valores de clave ordenados de menor a mayor. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4 y 9.

Inorden nodo )
Inorden( nodo.izquierdo)
procesar( nodo )
Inorden( nodo.derecho)
Fin Inorden

[+/-]Recorridos de un árbol binario...

Árboles Binarios de Búsqueda

Un árbol binario de búsqueda es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol.

Un árbol binario de búsqueda (ABB) es un árbol binario definido de la siguiente forma:

Todo árbol vacío es un árbol binario de búsqueda.

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el
subárbol izquierdo sea un árbol binario de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el
subárbol derecho sea un árbol binario de búsqueda.

Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.

Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación este definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.

El interés de los árboles binarios de búsqueda radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.



Búsqueda
La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. El número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log2(N+1)] y N, siendo N el numero de nodos. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.


data Buscar_ABB(abb t,clave k)
{
abb p;
dato e;
e=NULL;
p=t;
if (!estaVacio(p))
{
while (!estaVacio(p) && (p->k!=k) )
{
if (k <>k)
{
p=p->l;
}
if (p->k < p="p-">r;
}
}
if (!estaVacio(p) &&(p->d!=NULL) )
{
e=copiaDato(p->d);
}
}
return e;
}
[+/-] Ejemplo Iterativo de busqueda ...

Véase ahora la versión recursiva en ese mismo lenguaje:

int buscar(tArbol *a, int elem)
{
if (a == NULL)
return 0;
else if (a->clave <>hDerecho, elem);
else if (a->clave > elem)
return buscar(a->hIzquierdo, elem);
else
return 1;
}

Inserción
La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el subárbol izquierdo y si es mayor se inserta en el subárbol derecho. De esta forma las inserciones se hacen en las hojas.

Borrado
La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:

--Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.

Nodo a eliminar 74

--Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.

Nodo a eliminar 70

--Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:

Nodo a eliminar 59


El siguiente algoritmo en C realiza el borrado en un ABB. El procedimiento reemplazar busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar.

void borrar(tArbol **a, int elem)
{
void reemplazar(tArbol **a, tArbol **aux);
tArbol *aux;

if (*a == NULL)
return;

if ((*a)->clave <>hDerecho, elem);
else if ((*a)->clave > elem)
borrar(&(*a)->hIzquierdo, elem);
else if ((*a)->clave == elem)
{
aux = *a;
if ((*a)->hIzquierdo == NULL)
*a = (*a)->hDerecho;
else if ((*a)->hDerecho == NULL)
*a = (*a)->hIzquierdo;
else
reemplazar(&(*a)->hIzquierdo, &aux);

free(aux);
}
}

void reemplazar(tArbol **a, tArbol **aux)
{
if ((*a)->hDerecho == NULL)
{
(*aux)->clave = (*a)->clave;
*aux = *a;
*a = (*a)->hIzquierdo;
}
else
reemplazar(&(*a)->hDerecho, aux);
}


Recorridos
Se puede hacer un recorrido de un árbol en profundidad o en anchura.

Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.

El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden.

Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.

Ejemplo árbol binario de búsqueda

Resultado de hacer el recorrido en:

Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].
Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].
Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

[+/-] Leer más...

Colas de prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

Este tipo especial de colas tienen las mismas operaciones que las colas FIFO, pero con la condición de que los elementos se atienden en orden de prioridad.

Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.

Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

Hay 2 formas de implementación:
  1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
  2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
Existe 2 tipos de colas de prioridad:
  • Colas de prioridades con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad.
  • Colas de prioridades con ordenamiento descendente: son iguales que la colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.



    package colaPrioridadSimpleEnlazada;
    import colaException.*;

    public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {
    class Celda {
    Object elemento;
    int prioridad;
    Celda sig;
    }
    private Celda cola;
    public ColaPrioridad() {
    cola = new Celda();
    cola.sig = null;
    }
    public boolean vacia() {
    return (cola.sig==null);
    }
    public Object primero() throws ColaVaciaException {
    if (vacia()) throw new ColaVaciaException();
    return cola.sig.elemento;
    }
    public int primero_prioridad() throws ColaVaciaException {
    if (vacia()) throw new ColaVaciaException();
    return cola.sig.prioridad;
    }
    public int primero_prioridad() throws ColaVaciaException {
    if (vacia()) throw new ColaVaciaException();
    return cola.sig.prioridad;
    }
    public void inserta(Object elemento, int prioridad) {
    Celda p,q;
    boolean encontrado = false;
    p = cola;
    while((p.sig!=null)&&(!encontrado)) {
    if (p.sig.prioridad:prioridad)
    encontrado = true;
    else p = p.sig;
    }
    q = p.sig;
    p.sig = new Celda();
    p = p.sig;
    p.elemento = elemento;
    p.prioridad = prioridad;
    p.sig = q;
    }
    public void suprime() throws ColaVaciaException {
    if (vacia()) throw new ColaVaciaException();
    cola = cola.sig;
    }
    } // fin clase ColaPrioridad
    [+/-] Ejemplo en Java...
  • Montón o Heap

    La estructura heap es frecuentemente usada para implementar colas de prioridad. En este tipo de colas, el elemento a ser eliminado (borrados) es aquél que tiene mayor (o menor) prioridad. En cualquier momento, un elemento con una prioridad arbitraria puede ser insertado en la cola. Una estructura de datos que soporta estas dos operaciones es la cola de prioridad máxima (mínima).


    Existen tres categorías de un heap: max heap, min heap y min-max heap.

    Un max (min) tree es un árbol en el cual el valor de la llave de cada nodo no es menor (mayor) que la de los valores de las llaves de sus hijos (si tiene alguno). Un max heap es un árbol binario completo que es también un max tree. Por otra parte, un min heap es un árbol binario completo que es también un min tree.
    De la definición se sabe que la llave del root de un min tree es la menor llave del árbol, mientras que la del root de un max tree es la mayor.

    Si la llave (key) de cada nodo es mayor que o igual a las llaves de sus hijos, entonces la estructura heap es llamada max heap.


    Si la llave (key) de cada nodo es menor que o igual a las llaves d esus hijos, entonces la estructura heap es llamada min heap.


    En una estructura min-max heap, un nivel satisface la propiedad min heap, y el siguiente nivel inferior satisface la propiedad max heap, alternadamente. Un min-max heap es útil para colas de prioridad de doble fin.


    Las operaciones básicas de un heap son:
    • Creación de un heap vacío
    • Inserción de un nuevo elemento en la estructura heap.
    • Eliminación del elemento más grande del heap.

    Su único requisito es que sólo es posible acceder a ellos a través de un puntero.

    Ventajas:
    • Soporta las operaciones insertar y suprimir en tiempo O(log N) en el caso peor.
    • Soporta insertar en tiempo constante en promedio y primero en tiempo constante en el peor caso.

    Un heap tiene las siguientes tres propiedades:

    • Es completo, esto es, las hojas de un árbol están en a lo máximo dos niveles adyacentes, y las hojas en el último nivel están en la posición leftmost.
    • Cada nivel en un heap es llenado en orden de izquierda a derecha.
    • Está parcialmente ordenado, esto es, un valor asignado, llamado key del elemento almacenado en cada nodo (llamado parent), es menor que (mayor que) o igual a las llaves almacenadas en los hijos de los nodos izquierdo y derecho.

    Grafos

    Es una estructura de datos que consiste en un conjunto de nodos y un conjunto de arcos que establecen relaciones entre los nodos. Cada arco en un grafo se especifica por medio de un par de nodos.

    Exploración de grafos
    A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.
    En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.


    Tipos de Grafos

    Grafos Bi-direccionales
    El mas simple de los grafos en donde cada arco apunta exactamente a dos nodos.

    Grafos unidireccional
    Cada arco apunta a un solo nodo.

    Cada nodo puede apuntar a otro nodo a través de otro arco.

    Grafos de Peso
    En este grafo introducimos un nuevo nivel de complejidad al introducir un peso al arco que conecta los nodos.
    Imaginémonos los vuelos entre aeropuertos de cierta línea aérea.

    La distancia entre cada ciudad, es el peso del arco que conecta los nodos.


    Implementación de Grafos

    Tablas adyacentes
    Siempre son cuadradas. Expresan la intersecciones de nodos ligados.

    Tablas de Dirección
    Está relacionado con la tabla adyacente. Este método asume que hay un número limitado de direcciones a las cuales se puede ir desde un nodo en particular.

    Grafos Bi-Direccionales
    La forma más simple de realizar esto sería de tener dos estructuras, un nodo y un arco. Tendríamos un arreglo o lista de nodos y un arreglo o lista de arcos.

    Para encontrar si un nodo está apuntando a otro tendríamos que buscar a través de todos los nodos para encontrar la conexión. Podríamos arreglar este problema adjuntando una lista de punteros a arcos.

    Grafos Uni-Direccionales
    Este es el método más común y más flexible. La estructura es igual una clase nodo y una clase arco. Pero la estructura grafo tendrá una lista o arreglo de nodos no de arcos. El arco simplemente será un puntero a otro nodo.

    Recorrer un grafo
    Hay dos maneras de las cuales podemos recorrer un grafo:
    • Recorrer por profundidad primero

    • Recorrer por anchura primero

    La diferencia de recorrer un grafo y un árbol es que en el árbol empezamos en la raíz en un grafo empezamos donde sea.
    Procesamos todos los nodos que están accesibles desde un nodo en particular o paramos cuando encontramos un nodo específico.

    Búsqueda profundidad primero
    Esta búsqueda es casi exactamente igual a la búsqueda pre-orden de un árbol.





    El pseudocódigo es asi:
    DepthFirst( Node )
    Process( Node )
    Mark( Node )
    For Every Child of Node
    If NotMarked( Child )
    DepthFirst( Child )
    End If
    End For
    End Function

    búsqueda de ancho primero
    Mientras la búsqueda de profundidad procesaba todos los nodos de una rama la búsqueda de ancho procesa solo los elementos por su distancia al nodo original.
    Se buscan todos los nodos a un paso del nodo después todos los nodos a dos pasos del nodo después tres pasos y sucesivamente.


    Notemos como los nodos conectados al 0 se procesan primero. Después los nodos conectados al 1 y después todos conectados al 2 etc Esta es una búsqueda que va hacia afuera.

    El pseudocódigo es asi:
    BreadthFirst( Node )
    Queue.Enqueue( Node )
    Mark( Node )
    While( Queue.IsNotEmpty )
    Process( Queue.Front )
    For Each Child of Queue.Front
    if NotMarked( Child )
    Queue.Enqueue( Child )
    Mark( Child )
    end if
    end For
    Queue.Dequeue()
    End While
    End Function
    [+/-]Leer más....

    Algoritmo de Burbuja

    Este es el algoritmo de ordenamiento más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian.

    Análisis del algoritmo.
    Éste es el análisis para la versión no optimizada del algoritmo:
    Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto es estable.
    Requerimientos de Memoria: Este algoritmo sólo requiere de una variable adicional para realizar los intercambios.
    Tiempo de Ejecución: El ciclo interno se ejecuta n veces para una lista de n elementos. El ciclo externo también se ejecuta n veces. Es decir, la complejidad es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n2).

    Ventajas:
    • Fácil implementación.
    • No requiere memoria adicional.

    Desventajas:
    • Muy lento.
    • Realiza numerosas comparaciones.
    • Realiza numerosos intercambios.


    Un ejemplo
    Vamos a ver un ejemplo. Esta es nuestra lista:
    4 - 3 - 5 - 2 - 1
    Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos:
    3 - 4 - 5 - 2 - 1
    Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos:
    3 - 4 - 2 - 5 - 1
    Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente:
    3 - 4 - 2 - 1 - 5
    Repitiendo este proceso vamos obteniendo los siguientes resultados:
    3 - 2 - 1 - 4 - 5
    2 - 1 - 3 - 4 - 5
    1 - 2 - 3 - 4 - 5
    [+/-]Ejemplo...

    Algortimo Quicksort

    Es probablemente la técnica de ordenamiento más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
    El algoritmo fundamental es el siguiente:
    1. Eliges un elemento de la lista. Puede ser cualquiera (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.
    2. Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).
    3. Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre).
    4. Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.
    5. Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste:
    6. Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).
    7. Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias.
    8. Repites esto hasta que se crucen los índices.
    9. El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).
    10. Al finalizar este procedimiento el elemento de división queda en una posición en que todos los elementos a su izquierda son menores que él, y los que están a su derecha son mayores.

    Análisis del algoritmo.
    Estabilidad: No es estable.
    Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.
    Tiempo de Ejecución:
    • Caso promedio. La complejidad para dividir una lista de n es O(n). Cada sublista genera en promedio dos sublistas más de largo n/2. Por lo tanto la complejidad se define en forma recurrente como:
    f(1) = 1
    f(n) = n + 2 f(n/2)
    La forma cerrada de esta expresión es:
    f(n) = n log2n
    Es decir, la complejidad es O(n log2n).
    • El peor caso ocurre cuando la lista ya está ordenada, porque cada llamada genera sólo una sublista (todos los elementos son menores que el elemento de división). En este caso el rendimiento se degrada a O(n2). Con las optimizaciones mencionadas arriba puede evitarse este comportamiento.
    Ventajas:
    • Muy rápido
    • No requiere memoria adicional.
    Desventajas:
    • Implementación un poco más complicada.
    • Recursividad (utiliza muchos recursos).
    • Mucha diferencia entre el peor y el mejor caso.



    Un ejemplo
    Esta vez voy a cambiar de lista ;-D
    5 - 3 - 7 - 6 - 2 - 1 - 4
    Comenzamos con la lista completa. El elemento divisor será el 4:
    5 - 3 - 7 - 6 - 2 - 1 - 4
    Comparamos con el 5 por la izquierda y el 1 por la derecha.
    5 - 3 - 7 - 6 - 2 - 1 - 4
    5 es mayor que cuatro y 1 es menor. Intercambiamos:
    1 - 3 - 7 - 6 - 2 - 5 - 4
    Avanzamos por la izquierda y la derecha:
    1 - 3 - 7 - 6 - 2 - 5 - 4
    3 es menor que 4: avanzamos por la izquierda. 2 es menor que 4: nos mantenemos ahí.
    1 - 3 - 7 - 6 - 2 - 5 - 4
    7 es mayor que 4 y 2 es menor: intercambiamos.
    1 - 3 - 2 - 6 - 7 - 5 - 4
    Avanzamos por ambos lados:
    1 - 3 - 2 - 6 - 7 - 5 - 4
    En este momento termina el ciclo principal, porque los índices se cruzaron. Ahora intercambiamos lista[i] con lista[sup] (pasos 16-18):
    1 - 3 - 2 - 4 - 7 - 5 - 6
    Aplicamos recursivamente a la sublista de la izquierda (índices 0 - 2). Tenemos lo siguiente:
    1 - 3 - 2
    1 es menor que 2: avanzamos por la izquierda. 3 es mayor: avanzamos por la derecha. Como se intercambiaron los índices termina el ciclo. Se intercambia lista[i] con lista[sup]:
    1 - 2 - 3
    Al llamar recursivamente para cada nueva sublista (lista[0]-lista[0] y lista[2]-lista[2]) se retorna sin hacer cambios (condición 5.).Para resumir te muestro cómo va quedando la lista:
    Segunda sublista: lista[4]-lista[6]
    7 - 5 - 6
    5 - 7 - 6
    5 - 6 - 7
    Para cada nueva sublista se retorna sin hacer cambios (se cruzan los índices).
    Finalmente, al retornar de la primera llamada se tiene el arreglo ordenado:
    1 - 2 - 3 - 4 - 5 - 6 - 7
    [+/-] Ejemplo...
     
    Subir a Inicio