Estructura de Datos - Trabajo Final

...

[pic 18][pic 19]

Método Burbuja

En este método se toma los elementos de un array empezando con el primero y se comparan de par en par, desplazándose de acuerdo al criterio hasta que lleguen al final del array o el elemento adyacente ya no es mayor o menor dependiendo del orden requerido.

[pic 20][pic 21]

Método Quicksort

Este algoritmo consta de: Elegir un elemento de la lista de elementos a ordenar, ordenar los demás elementos de la lista a cada lado del elemento seleccionado, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al elemento seleccionado pueden ser colocados en cualquiera de los dos lados. En este momento, el elemento seleccionado ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublista, una formada por los elementos a la izquierda del elemento seleccionado, y otra por los elementos a su derecha. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

[pic 22][pic 23][pic 24]

[pic 25]

Método Heapsort:

Este método consiste en almacenar todos los elementos del vector a ordenar en un conjunto, y luego extraer el nodo que queda como nodo raíz de la cima en sucesivas iteraciones obteniendo el conjunto ordenado. De acuerdo al criterio buscado la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, recoloca en la cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad del conjunto del árbol. Pero, a continuación realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente altera el nodo en el árbol restaurando la propiedad montículo del árbol y dejando paso a la siguiente extracción del nodo raíz.

[pic 26][pic 27]

Listas:

Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un enlace o puntero que apunta al siguiente elemento de la lista.

Para demostrar cada tipo de lista se hizo un programa que deja al usuario crear una lista y hacer las siguientes funciones con ella:

- Eliminar el primer elemento

- Eliminar el elemento final

- Eliminar el elemento colocado en medio de la lista

- Colocar un nuevo elemento en medio de dos elementos dados

- Revisar si la lista se encuentra actualmente vacía

Las listas pueden ser calcificadas en cuatro categorías:

- Lista simplemente enlazada: Esta lista tiene un principio y un fin definido y al llegar al último nodo su puntero apunta a un vacío identificado como el fin de la lista

- Lista doblemente enlazada: Igual que a la primera lista pero cada elemento tiene un segundo puntero que apunta al nodo anterior. Y en el caso del primero elemento el puntero que apunta al elemento anterior apunta a un vacío lo cual la identifica como el principio de la lista.

- Lista Circular simplemente enlazada: Esta consta en una lista a simplemente enlazada cuyo puntero del elemento final señala el elemento siguiente como el primer elemento de l lista.

- Lista Circular doblemente enlazada: Como la lista doblemente enlazada pero el puntero anterior del primer elemento apunta al último elemento y el puntero siguiente del último elemento apunta al primer elemento.

- [pic 28][pic 29]

Pilas

Una pila es una estructura de datos del mismo tipo, secuencial y de tamaño variable. Sólo es posible un modo de acceso a esta estructura: a través de la cabeza de la pila.

En el caso de expresiones aritméticas hay tres formas de expresarlas de acuerdo a una pila:

- Infija

- Posfija

- Prefija

A partir de estas definiciones se hicieron dos programas, uno para demostrar una pila básica y otra para una pila con una expresión aritmética y que tuviera el poder de ordenarla de acuerdo a la preferencia del usuario.

La segunda se logró usando un seudocódigo usado para una tarea de clase que consta de: buscar el elemento más alto béquicamente de la expresión primero dentro del paréntesis más profundo después dentro de un paréntesis simple y luego la expresión aritmética más cercana. En cada paso agarrando las variables asociadas con la expresión. (Primer () dentro de () luego () independientes y luego ^, * o /, + o – en ese orden.

[pic 30][pic 31]

Colas

Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista. S inserta en la cola (Final) de la lista y se suprime o elimina por la frente (Principio) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.

En el caso de una cola de arreglo circular, se identifica un frente y una cola. Este tipo de cola se usa para que no se creen espacios vacíos inaccesibles ya que la cola y el frente está entrelazado siempre que haya suficientes elementos para que exista una cola y un frente. La cola no se identifica como el límite del arreglo sino el último elemento accesible.

Sea realizaron dos programas para demostrar una cola simple y otra circular ambos con casos de la vida real. El primero siendo un banco donde los cajeros están libres y por lo tanto vacíos y el otro una cola donde el final no es el cupo sino el cliente que se encuentre al final.

[pic 32][pic 33]

Arboles

Son estructuras no lineales, al contrario de los arreglos y listas enlazadas, que constituyen