Guía de estudio para Estructuras de Datos

ESTRUCTURAS DE DATOS

Son métodos para solucionar situaciones donde no bastan las variables sencillas, almacenando la información de forma especial en la memoria.

Las ciencias informáticas proponen para esto, las estructuras de datos y los algoritmos, siendo el primero el que afectará al uso de la memoria, y los algoritmos (que interactúan con esas ED), al tiempo del procesador.

Algunas veces puede ocurrir una relación inversa entre el uso de memoria y el tiempo de CPU:

Memoria > ED - ALG > CPU: Dado que procesa tipos primitivos u objetos mediante referencias.

Memoria < ED - ALG < CPU: El procesamiento tiende a ser más rápido.

PILAS

Las pilas son listas de elementos o ED lineales (sus componentes ocupan lugares sucesivos) que tienen restricciones en cuanto a la posición para realizar una inserción o eliminación; cualquiera de estas acciones solo podrá hacerse por un extremo (tope) de la pila, en orden inverso al que fuesen añadidos, es decir, el último en entrar es el primero en salir (LIFO o UEPS).

Ejemplos: Pila de platos, latas superpuestas una encima de otra, baterías de un foco de mano, etc.

Nota: Para las pilas se puede utilizar Listas Enlazadas, pero en este caso utilizaremos arreglos, para definir así el tamaño máximo, y también declararemos una variable auxiliar llamada TOPE que apuntará al último elemento insertado en la pila (además de MAX Y BAND para respuesta).

[pic 2]

DESVENTAJAS

1. Los arreglos tienen la limitante de espacio de memoria reservada, es decir, una vez dado el #MAX de elementos a almacenar, no se puede insertar más, y si se intentara, se produciría un desbordamiento (overflow).
2. No siempre se puede saber la cantidad de elementos a tratar, por lo que siempre es posible cometer un error overflow, o bien, hacer uso ineficiente de la memoria (en los casos en que se da más espacio del necesario por la incertidumbre).

Nota: Otro error que puede ocurrir es el de underflow o subdesbordamiento, al intentar eliminar de una pila vacía.

ALGORITMOS

[Estos algoritmos verifican en dependencia de su función asignando un valor de verdad (bool) a la variable BAND]

PILA LLENA

Método PILALLENA (PILA, TOPE, MAX, BAND)

SI TOPE = MAX

Entonces        BAND = true [La pila está llena]

Si no                BAND = false

PILA VACÍA

Método PILAVACIA (PILA, TOPE, BAND)

SI TOPE = 0 [Verifica si no hay elementos en la pila]

Entonces        BAND = true

Si no                BAND = false [La pila no está vacía]

INSERTAR

INSERTAR (PILA, TOPE, MAX, DATO)

Llamar a PILALLENA con PILA, TOPE, MAX y BAND

SI BAND = true

Entonces        Escribir “Desbordamiento”

Si no                TOPE = TOPE + 1 [Actualiza TOPE]

PILA [TOPE] = DATO [Pone el nuevo elemento en el TOPE de pila]

ELIMINAR

ELIMINAR (PILA, TOPE, DATO)

Llamar a PILAVACIA con PILA, TOPE y BAND

SI BAND = true

Entonces        Escribir “Subdesbordamiento”

Si no                DATO = PILA [TOPE]

TOPE = TOPE – 1 [Actualiza TOPE]

EJEMPLO DE PILA EN CONSOLA C#

[pic 3]

[pic 4]

[pic 5]

[pic 6]

[pic 7]

[pic 8]

[pic 9]

[pic 10]

[pic 11]

[pic 12]

[pic 13]

[pic 14]

[pic 15]

[pic 16]

[pic 17]

[pic 18]

[pic 19]

[pic 20]

[pic 21]

[pic 22]

OPERACIONES CON PILAS DE FORMA GRÁFICA[pic 23][pic 24]

[pic 25][pic 26]

[pic 27]

COLAS

Una COLA es una lista de elementos que se insertan por un extremo y se extraen por el otro, es decir, el primero en entrar es el primero en salir (FIFO o PEPS), lo que las diferencia de las pilas, y al igual que estas, también se utilizan arreglos y listas enlazadas.

Ejemplos: La fila en un banco, un inventario de productos perecederos o una fila de autos avanzando en un solo carril.

Para representar una COLA, utilizaremos un arreglo y tres variables para controlar dicha ED; la primera será FRENTE la cual almacenará la posición del primer elemento en la COLA, FINAL para guardar la posición del último y MAX para el tamaño de la cola.

[pic 28]

OPERACIONES CON COLAS

Las operaciones con COLAS son las mismas que las de las PILAS: Insertar y quitar un elemento. La inserción se da por el FINAL y la eliminación por el FRENTE.

ALGORITMOS

INSERTAR

INICIO

SI FINAL < MAX Entonces

FINAL ← FINAL + 1

Leer Cola [FINAL]

SI FINAL = 1 Entonces

FRENTE ← 1

FIN SI

Si no

        Escribir “Desbordamiento”

FIN SI

FIN

ELIMINAR

SI FRENTE > 0 Entonces

DATO ← Cola [FRENTE]

SI FRENTE = FINAL Entonces

FRENTE ← 0

FINAL ← 0

Si no

FRENTE ← FRENTE + 1

FIN SI

Si no

Escribir “Subdesbordamiento”

FIN

COLA DE FORMA GRÁFICA

PRIMERA PARTE – INVOCACIONES EN FORM1

(En program.cs se manda a llamar con Application.Run(new frmMenu());)

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

...