Mini manual java

Estructuras de datos y algoritmos en C/C++: Listas y Colas

Cambiando un poco el objetivo del sitio vamos a investigar un poco sobre las estructuras de datos y algoritmos en C/C++. Para esto vamos a comenzar trabajando con estructuras de datos simples como listas y colas, para luego pasar a estructuras como árboles, árboles binarios de búsqueda, AVLs, Hash y algoritmos complejos.

Para poderseguir los ejemplos les recomiendo utilizar Cygwin si usan Windows para tener todas las herramientas de compilado (g++, archivo make, librerias, etc). Si tienen Linux simplemente instalen los paquetes devel.

Trabajaremos construyendo los tipos abstractos de datos (TADs) que nos permitirán abstraernos de la estructura de punteros y trabajar con operaciones que se encargan de hacer el trabajosucio =). Esto nos libera de estar revisando detalles de la estructura para poder concentrarnos en como resolver problemas.

Comenzaremos trabajando con las dos estructuras más simples, listas y colas. En las dos estructuras de datos encadenamos elementos en forma simple, la diferencia está en la forma en que una vez que ingresamos los mismos, luego podemos sacarlos. En la lista insertamos en lacabeza y sacamos elementos desde la misma cabeza, este orden es conocido como último en entrar, primero en salir (LIFO siglas en inglés). En el caso de la cola utilizamos el otro orden, primero en entrar primero en salir (FIFO siglas en inglés).

Veamos la definición del tipo de datos para la lista:

typedef struct lista {
int valor;
lista * sig;
};

Con esta definición podemos ir enlazandolos nodos de la lista, poniendo en el último el valor NULL en el puntero a sig indicando que termina la lista.

El siguiente paso es definir la lista de operaciones con las cuales vamos a poder trabajar sobre este tipo de datos. Definiremos las siguientes funciones:

lista * ListaCrearVacia();
// Crear una lista de nodos vacia.

bool ListaEsVacia(lista * l);
// Devuelve true si la listaes vacia y false en caso contrario.

void ListaAgregar (lista *& l, int n);
// Agrega el elemento n al comienzo de la lista.

int ListaPrimero(lista * l);
// Devuelve el primer elemento de la lista.

lista * ListaResto(lista * l);
// Devuelve un alias al resto de la lista.

void ListaDestruir(lista * l);
// Libera la memoria asociada a la lista.

Dadas estas operaciones podremostrabajar sobre el tipo de datos con comodidad, creando, insertando, recorriendo y eliminando la estructura sin necesidad de preocuparnos por los punteros que la componen. Por ejemplo si queremos recorrer una lista que tiene elementos podríamos hacer lo siguiente (debemos verificar que no sea vacia primero):

while (!ListaEsVacia(listaDatos)) {
int valor = ListaPrimero(listaDatos);
printf(“\nDato:%d”,valor);
listaDatos= ListaResto(listaDatos);
}

Noten que deberíamos guardar una copia del puntero inicial de la lista para poder volver a recorrerla o bien poder eliminar la memoria de la misma. Si no tenemos este puntero habremos perdido el comienzo de la lista =P.

Entrando un poco en la construcción del TAD, en el caso de la lista tendremos que insertar el elemento al principio de lamisma, mientras que en la cola insertamos al final. Esto nos lleva a ver en el caso de la lista si insertamos al comienzo podremos hacerlo rápidamente aunque la lista sea muy grande. Simplemente modificaremos la cabeza de la lista y pondremos el nuevo dato como comienzo. Veamos un ejemplo:

void ListaAgregar (lista *& l, int n) {
lista* nuevoNodo = new lista;
nuevoNodo->valor = n;nuevoNodo->sig = l;
l = nuevoNodo;
return;
}

Lo que hacemos es crear el nuevo nodo, asignar el valor de entero y luego encadenamos la lista “vieja” como siguiente elemento del nuevo nodo. Esto nos deja la lista l con el nuevo nodo al comienzo.

La definición de las otras funciones es simple, veamos algunas:

lista * ListaCrearVacia() {
lista* l = NULL;
return l;
}

bool ListaEsVacia(lista *...