INTRODUCCION
TIPOS DE DATO ABSTRACTOS
ESTRUTURAS DE DATOS BASICAS
    PILAS
    COLAS
    LISTAS
    ARBOLES BINARIOS
    GRAFOS
    EJERCICIOS
ESTRUCTURAS DE DATOS AVANZADAS
    MONTICULOS
    TABLAS DE DISPERSION
    ARBOLES AVL
    ARBOLES DESPLEGADOS
    ARBOLES B
    ARBOLES INDEXADOS BINARIAMENTE
    EJERCICIOS
Presentaciones
Flash - OMI
Recorriendo Árbol en Orden
Recorriendo Árbol en Post-Orden
Recorriendo Árbol en Pre-Orden
Recorriendo Montículo
©César Arturo Cepeda García. Última modificación 7 abril 2004.
Las computadoras adquieren su nombre de su capacidad de computar, esto quiere decir que las computadoras son capaces de realizar cálculos sobre un conjunto de datos.
En su inicio, las computadoras se inventaron con el fin de facilitar y agilizar el procesamiento de datos, la primera computadora, la ENIAC, se empezó a construir durante la segunda guerra mundial, con el objetivo de cálcular los parámetros correctos de disparo de la artillería aliada, tomando en cuenta diferentes constantes, como lo eran la altitud, la velocidad del aire, etc. Posteriormente, la UNIVAC se comercializó para universidades, dependencias de gobierno y empresas grandes con el fin de facilitar el procesamiento de datos, ya que era capaz de realizar algunos miles de sumas y restas por segundo. La UNIVAC era capaz de hacer incluso algunas decenas de divisiones por segundo!
Hoy en día las computadoras se utilizan para una gran cantidad de aplicaciones, juegos de video, relojes, calculadoras portátiles, hornos de microondas, automóviles, laboratorios de investigación, procesamiento de imágenes, etc. Sin embargo, aún cuando podría parecer que las computadoras han perdido el rumbo de su finalidad original, esto no es cierto. Todas las aplicaciones actuales de las computadoras siguen siendo básicamente la manipulación y procesamiento de datos!
Por ejemplo, en un juego de video, la computadora debe procesar una serie de datos que representán un mundo virtual, como son, posiciones de los personajes, orientación de los mismos, puntos de vida, capacidad de ataque, etc. con base en estos datos y la entrada del usuario, la computadora realizará operaciones sobre los mismos y determinará para el siguiente instante, que caracteres siguen vivos, cuales han cambiado sus puntos de vida, etc.
En un automóvil la computadora recibe datos de los sensores del auto y con base en los mismos, determina la cantidad de combustible y aire que debe introducir a los pistones para el óptimo rendimiento del carro.
Y así, por inverosímil que parezca, todas las aplicaciones de las computadoras en el mundo actual se basan en el procesamiento de los datos adquiridos para obtener el resultado buscado.
Ya sabemos que el principal objetivo de las computadoras es el de realizar cálculos a un conjunto de datos, pero, ¿De dónde obtiene los datos? ¿Los recibe uno por uno, o todos a la vez? ¿Dónde los almacena? ¿Los procesa todos de manera simúltanea o uno por uno?
Aunque existen varios modelos computacionales, el más común cuenta con un espacio de almacenamiento llamado "memoria" y una Unidad Central de Procesos (CPU). En la memoria se almacenan los datos y el programa que procesa los mismos, la Unidad Central de Procesos se encarga de ejecutar los comandos del programa, al final de la ejecución los datos han sido procesados.
La memoria no es mas que un medio de almacenamiento capaz de "recordar" una serie de datos, lo común es que los datos almacenados en una memoria sean datos binarios, es decir, una serie de '1' y '0's que representan algo. Sin embargo, conocer el contenido de la memoria, sirve de muy poco si no sabes de antemano lo que los datos representan. Por ejemplo, la cadena binaria
0110111101101100011010010110110101110000011010010110000101100100
seguramente no te dice mucho, sin embargo si te indican que cada 8 dígitos binarios representan un caracter ASCII, entonces podrías darte cuenta de que la cadena anterior representa la palabra
olimpiad
o si supieras que la cadena binaria representa números enteros , dependiendo del tamaño de los números enteros, la cadena representaría
Bytes (8 dígitos por entero): 111, 108, 105, 109, 112, 105,
97, 100
Entero corto (16 dígitos): 27759,
28009, 26992, 25697
Entero largo (32 dígitos): 1835625583,
1684105584
Entero cuádruple (64 dígitos): 7016998964367026544
la misma cadena también representa
Flotante (32 dígitos):
4.5150685 e+27, 1.663246 e+22
Double (64 dígitos):
3.4451882 e+175
Fecha DOS (16 dígitos):
15-03-2034
Hora DOS (16 dígitos):
13:35:30
y dependiendo de lo que se haya preestablecido, la misma cadena puede representar miles de datos diferentes.
Todos los ejemplos anteriores (enteros, flotantes, cadenas de caracteres, fechas, etc) se conocen como Tipos de Dato, además de los tipos de dato, existen las Estructuras de Datos.
Las Estructuras de Datos sirven para organizar un conjunto de datos, pero a diferencia de los Tipos de Dato, las Estructuras de Datos no son un objeto pasivo, ya que una Estructura de Datos es un objeto que puede realizar una serie de operaciones sobre el conjunto de datos, en general estas operaciones son insertar, remover, acceder, buscar, etc.
Existe una gran cantidad de estructuras de datos, cada una es útil para diferente tipo de aplicaciones. Su estudio es muy importante, ya que el uso correcto de las estructuras de datos adecuadas al problema que quieran resolver, puede facilitarles de manera increíble la codificación, o puede mejorar el desempeño de su programa drásticamente.
A menudo resulta más sencillo describir las estructuras de datosen función de las operacioens efectuadas, en lugar de hacerlo en términos de los detalles de la implementación. Cuando se define de esta forma una estructura de datos, se denomina tipo de datos abstracto. La idea es separar el "concepto" de lo que debe hacer la estructura de datos de cualquier implementación particular.
Cuando una estrutura de datos se define de manera completa, es decir, no únicamente con la descripción de las operaciones, sino con la implementación de las mismas se conoce como tipo de datos concreto.
En estos apuntes se analízaran varias estructuras de datos. Todas las estructuras se verán desde un punto de vista abstracto en su definición y posteriormente se presentará una implementación de las operaciones para una estructura de datos que maneje enteros.
Es importante observar que aunque el tipo de datos concreto se presentará con números enteros, ustedes pueden modificar la implementación para que soporte cualquier tipo de datos, inclusive, tipos de dato compuestos. Lo importante es que cumpla con la definición del tipo de datos abstracto.
La PILA es quizá la estructura de datos común con un acceso más restrictivo, y sin embargo es quizá también la más usada en el funcionamiento diario de cualquier programa de cómputo.
La PILA cuenta únicamente con dos operaciones básicas: se puede insertar un dato al inicio de la pila, y se puede remover un dato del inicio de la pila.
La pila, como puede inferirse, deriva su nombre de que los datos se apilan uno sobre otro, ocasionando que en cualquier momento únicamente se tenga acceso al dato superior de la pila. La pila funciona como si hicieran una pila de cajas de refrescos, cuando llega una nueva caja, la ponen hasta arriba de la pila, ya que sería mucho trabajo levantar todas las cajas para poder meterla nueva caja hasta abajo. Cuando se necesita un refresco se retira de la caja superior, si esta se vacía, entonces se remueve y se prosigue con la siguiente caja. Como se habrán dado cuenta, existe la posibilidad de que una caja de refrescos quede olvidada en la parte inferior de la pila y se eche a perder. ¡Sin embargo, un taquero con éxito, debe ser capaz de terminar con toda la pila sin que ningún refresco se le eche a perder!
A las pilas se les conoce en la literatura como estructuras LIFO por sus siglas en inglés (Last In - First Out), que quiere decir, que el último que entro es el primero que sale. De ahí el consabido dicho de "Los últimos serán los primeros".
Las pilas tienen un campo de aplicación muy grande en los programas, el más común es la recursividad, aunque tal vez no lo notaron, ya que el compilador lo hace por ustedes, para poder implementar cualquier rutina recursiva es necesario contar con una pila. En la sección de ejercicios se revisarán aplicaciones de una pila para implementar recursión y para analizar una sentencia.
Una buena implementación de pila debe de tomar en cuenta dos puntos. El primero es que no debe permitir el remover un dato cuando la pila esta vacía, y el segundo es que no debe permitir que se inserten datos a la pila si esta ya esta llena.
A continuación se muestra la implementación de una pila en C y en Pascal utilizando memoria estática.
Pascal | C |
program
Pila; const MAXPILA : 100; // TAMAÑO MAXIMO DE LA PILA var MemPila : array[0..MAXPILA] of integer; SP : integer; // ESTA VARIABLE NOS SERVIRA PARA // SABER CUAL ES EL ELEMENTO SUPERIOR // DE LA PILA procedure Insertar(dato : integer); begin // LA VARIABLE SP, APUNTA A LA PRIMERA POSICION // VACIA DE LA PILA. MemPila[SP]:=dato; Inc(SP); if SP > MAXPILA then begin // AQUI VA UN ERROR INDICANDO QUE SE SOBREPASO // EL LIMITE DE LA PILA. end; end; function Remover : integer; begin Dec(SP); // DECREMENTA EL INDICE DE LA PILA if SP > 0 then begin Remover:=MemPila[SP]; end else begin // AQUI VA UN ERROR INDICANDO QUE LA PILA ESTA // VACIA Y NO SE PUEDE REMOVER NINGUN DATO end; end; begin SP:=0; // INICIALIZA EL INDICE DE LA PILA // AQUI DEBEN DE PONER SU CODIGO PARA USAR LA PILA end. |
#include<stdio.h>;
#define MAXPILA 100; (* TAMAÑO MAXIMO DE LA PILA *) int MemPila[MAXPILA + 1]; int SP; // ESTA VARIABLE NOS SERVIRA PARA // SABER CUAL ES EL ELEMENTO SUPERIOR // DE LA PILA void Insertar(int dato) { (* LA VARIABLE SP, APUNTA A LA PRIMERA POSICION VACIA DE LA PILA *) MemPila[SP++]=dato; if (SP > MAXPILA){ (* AQUI VA UN ERROR INDICANDO QUE SE SOBREPASO EL LIMITE DE LA PILA *) } } int Remover(void) { (* DECREMENTA EL INDICE DE LA PILA *) if (--SP > 0) then { return(MemPila[SP]); } else { (* AQUI VA UN ERROR INDICANDO QUE LA PILA ESTA VACIA Y NO SE PUEDE REMOVER NINGUN DATO *) } } int
main(void) { |
Las COLAS, al igual que las pilas, son una estructura de datos de acceso restrictivo. Al igual que en una pila únicamente se cuenta con 2 operaciones, la operación insertar y la operación remover.
La diferencia entre una cola y una pila es que en la cola (como en una cola para comprar boletos), el primero que llegó es al primero que se atiende, es decir, una cola tiene un inicio y un final, los nuevos elementos que llegan se agregan al final de la cola, cuando se remueve un elemento, se remueve del inicio de la misma.
A las colas se les conoce como estructuras FIFO (First In - First Out), que quiere decir que el primero que entra, es el primero que sale.
Existe una implementación muy común de la cola que se conoce como cola circular, esta implementación aprovecha el espacio en memoria de la computadora de la siguiente forma: inicialmente aparta un espacio para la cola, conforme llegan los elementos los va agregando al final, cuando remueve un elemento lo hace del inicio de la cola, una vez que ha terminado con el espacio de memoria que había apartado, revisa si ya se liberó el espacio al inicio de la cola y "da la vuelta" para aprovechar el espacio al máximo, la implementacion que se presenta a continuación es la de una cola circular.
Al igual que en la pila, en la cola es muy importante revisar si todavía hay espacio para seguir guardando elementos, o si la cola esta vacía.
Pascal | C |
program
Cola; const MAXCOLA : 100; // TAMAÑO MAXIMO DE LA COLA var MemCola : array[0..MAXCOLA] of integer; Inicio : integer; // INICIO DE LA COLA Fin : integer; // FIN DE LA COLA procedure Insertar(dato : integer); begin // LA VARIABLE FIN, APUNTA A LA PRIMERA POSICION // VACIA DE LA COLA. MemCola[Fin]:=dato; Inc(Fin); if Fin > MAXCOLA then begin // SI YA SE LLENO TODA LA MEMORIA HAY QUE // DAR LA VUELTA Fin:=0; end; if Inicio = Fin then begin // SI EL FIN ALCANZO AL INICIO, QUIERE DECIR QUE // DIO TODA LA VUELTA Y YA NO HAY ESPACIOS // LIBRES, POR LO QUE HAY QUE MARCAR UN ERROR // DE QUE LA COLA ESTA LLENA end; end; function Remover : integer; begin if Inicio = Fin then begin // EL INICIO ES IGUAL AL FIN, QUIERE DECIR QUE // NO HAY DATOS EN LA COLA, POR LO TANTO // MANDA UN ERROR DE COLA VACIA end else begin Remover:=MemCola[Inicio]; // EL DATO A DEVOLVER // ES EL QUE ESTA AL INICIO DE LA COLA Inc(Inicio); // MUEVE EL INICIO DE LA COLA if Inicio > MAXCOLA then begin // SI LLEGO AL FINAL, DA LA VUELTA Inicio:=0; end end; end; begin Inicio:=0; // INICIALIZA EL INICIO DE LA COLA Fin:=0; // INICIALIZA EL FINAL DE LA COLA // AQUI DEBEN DE PONER SU CODIGO PARA USAR LA COLA end. |
#include<stdio.h>;
#define MAXCOLA 100; (* TAMAÑO MAXIMO DE LA COLA *) int MemCola[MAXCOLA + 1]; int Inicio; (* INICIO DE LA COLA *) int Fin; (* FIN DE LA COLA *) void Insertar(int dato) { (* LA VARIABLE FIN, APUNTA A LA PRIMERA POSICION VACIA DE LA COLA *) MemCola[Fin++]=dato; if (Fin > MAXCOLA) { (* SI YA SE LLENO TODA LA MEMORIA HAY QUE DAR LA VUELTA *) Fin=0; } if (Inicio == Fin) { (* SI EL FIN ALCANZO AL INICIO, QUIERE DECIR QUE DIO TODA LA VUELTA Y YA NO HAY ESPACIOS LIBRES, POR LO QUE HAY QUE MARCAR UN ERROR DE QUE LA COLA ESTA LLENA *) } } int Remover(void) { if (Inicio == Fin) { (* EL INICIO ES IGUAL AL FIN, QUIERE DECIR QUE NO HAY DATOS EN LA COLA, POR LO TANTO MANDA UN ERROR DE COLA VACIA *) } else { Remover=MemCola[Inicio++]; (*EL DATO A DEVOLVER ES EL QUE ESTA AL INICIO DE LA COLA *) (* MUEVE EL INICIO DE LA COLA *) if (Inicio > MAXCOLA) { (* SI LLEGO AL FINAL, DA LA VUELTA *) Inicio=0; } } } int main(void){ Inicio=0; (* INICIALIZA EL INICIO DE LA COLA *) Fin=0; (* INICIALIZA EL FINAL DE LA COLA *) (* AQUI DEBEN DE PONER SU CODIGO PARA USAR LA COLA*) } |
MONTICULOS
: Visita la página http://ce.azc.uam.mx/profesores/franz/omi/monticulo.html
INICIO