sábado, 11 de agosto de 2007

** TAD PILAS **

Hola a todos… primero quiero agradecer a la persona que me invito a se parte de esta vaina y espero que sirva mucho esta información, son materiales que prepare hace un par de años con la esperanza que pudieran facilitar el aprendizaje de los TAD espero que las personas que tengan contacto con estos materiales puedan utilizarlos y les facilite el estudio de los mismos, yo recopile información de muchas buenas paginas en Internet y la que mas utilice fue la “Aclamada c.conclase” excelente sitio lo recomiendo abrió para mi todo un panorama de los TAD la verdad es como mi mas grande y profunda fuente de inspiración, e hizo que el estudio de estos para mi fuera fácil y divertido porque cualquiera que antes haya trabajado con ellos no me dejara mentir en cuanto a que son un VERDADERO PASATIEMPOS y te ayudan a desarrollar la lógica de una manera sorprendente no hacen milagros... pero si te facilita el pensamiento y como que se activa la materia gris, el análisis y todas esas ondas se facilitan.

Quiero advertir que si alguien estuvo en la UDB habrán visto estos materiales pues si para aquellos que me odiaron profundamente o me apreciaron en Progra 3 y 4 “I say you Hi…. =)” son mis materiales de clases….whatever no mas palabras y la acción yo pienso estructurar la info. Así:

1- Comenzar escribiendo algunos conceptos básicos.
2- Mostrar una explicación en forma grafica.
3- Y posteriormente ejemplos de aplicación de los TAD PILA.



Obviamente esto no sera algo que este listo ya hoy...no!, sera poco a poco y obvio los comentarios son bienvenidos aunque no creo que estos cambien mi forma de pensar =) pero sientanse libres de liberar sus emociones..... ¬¬


***********************+++++++++++++++++++++++++++++++++++****************++

PILAS

Una pila es una lista ordenada de elementos en la que todas las inserciones y supresiones se realizan por un mismo extremo de la lista. A una pila se le pueden añadir y retirar nuevos nodos únicamente de su parte superior. Por esta razón, se conoce una pila como una estructura de datos LIFO por last-in, first-out, es decir último en entrar primero en salir.

Se referencia una pila mediante un apuntador al elemento superior de la misma. El miembro de enlace en el último nodo de la pila se define a NULL, para indicar que se trata de la parte inferior de la pila misma. Vea una representación gráfica de la PILA:


Note que las pilas y las listas enlazadas se representan en forma idéntica. La diferencia entre las pilas y las listas enlazadas es que en una lista enlazada las inserciones y borrados pueden ocurrir en cualquier parte, pero en una pila únicamente en su parte superior.

Las funciones primarias utilizadas para manipular una pila son push y pop. La función push crea un nuevo nodo y lo coloca en la parte superior de la pila (tope). La función pop sirve ya sea para leer o elimina un nodo de la parte superior de la pila, liberando la memoria que fue asignada al nodo retirado, y regresando el valor retirado.

Las pilas pueden implementarse con arrays pero este debe ser lo suficientemente amplio para poder contener el máximo previsto de elementos de la pila. Un extremo del array se considera el fondo de la pila, que permanecerá fijo. La implementación dinámica de una pila se hace almacenando los elementos como nodos de una lista enlazada, con la particularidad de que siempre que se quiera meter (empujar) un elemento se hará por el mismo extremo que se extraerá. Esta realización tiene la ventaja de que el tamaño se ajusta exactamente a los elementos de la pila. Sin embargo, para cada elemento es necesaria más memoria, ya que hay que guardar el campo de enlace.



Antes de analizar el código quiero advertir que en algunos casos las imagenes tienen un literal en color rojo entre parentesis o un literal encerrado en cuadrito en rojo, seguido de la imagen que contenga estos literales esta la explicación o el significado de la línea de código junto a la cual esta el literal. Es decir vean la imagen y luego la explicación para que sepan que hace cada línea de código , obviamente el programa tiene comentarios pero para entrar mas en detalle he querido colocar una explicación extra. A continuación analizaremos el código en c++ que permite implementar una pila:







Representación gráfica

La clase nodo contiene el código que permitirá crear cada nodo para implementar la pila. Cada nodo tendrá un valor (dato que se almacena dentro del nodo en la pila) y un puntero apuntando al siguiente nodo o elemento de la pila. Graficamente podriamos decir que esta clase genera una serie de cajitas que se iran uniendo unas a otras para formar la pila, estas cajitas podrian ser algo como lo siguiente:






La clase Pila encierra el código de la Pila este código permitirá crear la pila dentro de la cual se colocara cada nodo. Esta clase es la base de la pila gracias a ella sabemos donde comienza la pila y donde acaba y solamente genera un puntero que apuntará a la primera cajita de la pila si no crearamos esta clase no sabriamos donde comienza la pila. Recuerden que estamos trabajando con memoria dinamica lo que implica el necesario uso de los lindos PUNTEROS que son los responsables de decirme cual es la ubicacion de mis elementos dentro de la memoria, una memoria que no puedo controlar igual que controlo un vector, arreglo o array. Es igual pero en el vector yo digo posición 0,1,2,...n y en la memoria dinamica se asigna dinamicamente y no exactamente si mis elementos estan en la ubicación de memoria FFX001, etc. Por esto necesito saber donde comienza mi pila y luego me voy desplazando por cada nodo de la pila gracias al puntero que cada nodo tiene.




**Bueno algo enrredadito ¿no? =( al principio suena bien macabro pero despues se entiende bien esta
vaina es cuestion de practica =). Pero animo que estamos al principio conforma avancemos se facilita la
cosa. Y a medida que lo entiendan se van a sentir bien poderosos....**


...En fin graficamente la clase pila genera algo como lo siguiente:









ANALISIS DE FUNCION CONSTRUCTOR





Representación gráfica




1- El constructor inicializa el fondo de la pila, poniendo a ultimo (puntero de la pila) apuntado a NULL. Ahora ya esta creada la pila.


ANALISIS DE FUNCION PUSH (INSERTAR NUEVO NODO A LA PILA EN EL TOPE)

( A continuación se muestra la representación grafica de este segmento de código ubique el (1) y el (2) en la imagen para que sepan la presentación de estas lineas de codigo y en la respectiva explicación el significado de las mismas. )

Representación gráfica

(1) Para las pilas solo se pueden insertar elementos al tope, por lo tanto lo único que hacemos es crear el nuevo nodo pasando como parámetro el valor que guardar y pasándole el valor al que apunta en ese momento ultimo, como ultimo antes de agregar el nodo apunta a NULL entonces siguiente apuntara a NULL.
(2) Le indicamos a ultimo (puntero de la pila) que apunte al nodo que se acaba de agregar.


Bueno por hoy es todo .......continuara....















































miércoles, 1 de agosto de 2007

Tipos Abstractos de Datos: Introduccion

Al programar trabajamos constantemente con distintos tipos de dato en nuestras operaciones, usualmente estos tipos de dato son parte del lenguaje y tienen un significado concreto para nosotros, como por ejemplo un valor entero (int ) o un caracter (char).

La Programación Orientada a Objetos (POO) introduce el concepto de objeto como un nuevo tipo de dato, pero estos datos dejan de ser concretos y pasan a ser definidos por el usuario. Cada nueva clase es una plantilla para un objeto completamente distinto, por lo que es también un nuevo tipo de dato abstracto.

Los tipos abstractos de datos (TAD) son esencialmente, tipos de datos definidos por el usuario, usualmente a través de objetos. Sin embargo, este término se usa sobre todo para definir una colección de estructuras abstractas que suelen ser utilizadas con frecuencia. Estas estructuras, usadas adecuadamente, pueden sustituir las estructuras comunes como los arreglos y permiten la reutilización de código para resolver ciertos procesos sencillos.

El lenguaje C++ no proporciona por defecto este tipo de estructuras, por lo que estas deben ser implementadas por el programador, pero se recomienda mejor la reutilización de código utilizando las librerías STL (Librería de Plantillas Estándar) de C++ o las LibTad de su servidor, que contienen estas estructuras listas para ser simplemente implementadas. Este tipo de estructuras hacen amplio uso interno de punteros y memoria dinámica, por lo que son propensas a errores al diseñarlas, también es posible que su utilidad se vea reducida a ciertas situaciones específicas.

En los lenguajes de programación más modernos, muchas veces estas estructuras vienen incluidas dentro del lenguaje disfrazadas con otros nombres, lo que le ha dado a mucha gente la falsa impresión de que no se utilizan. Es importante sobre todo saber implementar aprender a implementarlas adecuadamente y aprovecharlas al máximo, esto simplifica muchos procesos y puede evitar algunos procesos complicados, como por ejemplo trabajar con arreglos.