Hasta aqui va mi tutorial sobre estructuras de datos, he publcado los postes en el foro de oneble.. entren!!

Introducción a las estructuras de Datos

TDA
Un TDA, o Tipo Abstracto de Datos es básicamente un conjunto de datos de un mismo tipo que poseen operaciones para manipularlos, tales como comparaciones, asignaciones etc... Un TDA, posee una especificación lógica (independiente de su implementación) y una implementación (en un lenguaje dado). El acceso con el usuario en un TDA es limitado/nulo, los usuarios de este, solo deben conocer el nombre de las operaciones y su descripción no como llevan a cabo las tareas ni como almacenan la información para que cualquier cambio sobre estos no afecte a las aplicaciones que de el dependen.
Existen dos tipos de TDA's
Mutables: Existen operaciones que modifican sus datos
Inmutables: Las únicas operaciones de modificación son las de creación y destrucción

Estructura de datos
La técnica de abstracción de datos, nos dice que al diseñar una nueva estructura de datos, esta pasa automáticamente a ser un TDA que podrá ser implementado. La especificación lógica de una estructura, puede ser separada en los siguientes pasos..
________________________________________
1- Identificar los datos que se almacenaran en la estructura
En este paso se analiza que tipo datos se necesita que almacene la estructura..
________________________________________
2- Identificar la forma en que estos datos se organizaran:
Identificamos en este paso de que manera se relacionaran los datos dentro de la estructura.
Existen cuatro formas básicas de organizar la información
Organización lineal: los datos conforman una relación de "cadena" en la que cada elemento esta relacionado con otro de su tipo a través de una relación de uno a uno
Organización Jerárquica: en este tipo de organización la relación entre los datos es de uno a varios.
Organización en forma de Red: en este tipo de organización los elementos posen una relación de varios a varios formando una red de elementos
Organización Sin relación: en este tipo de organización los datos no tienen una relación directa, solo están dispersos en la estructura.
________________________________________
3- Definir las operaciones

Las operaciones de una estructura se pueden detallar de manera
Informal:
En la cual se escribiría un pequeño texto describiendo el funcionamiento de la operación y las pre y post condiciones
(el nombre de la operación )
(una breve descripción)
(la condición que debe tener la estructura para llevar a cabo la op)
(la modificacion que recibe la estructura luego de ejecutar la operación)

Formal: en la cual se utilizaría el lenguaje algebraico de la siguiente manera:
{Pre}Op{post} donde, pre son las precondiciones, Op es el nombre de la operación y post son las postcondiciones
________________________________________
Niveles de Abstracción
Podemos distinguir, en el desarrollo de una estructura, 3 niveles de abstracción
1- Un nivel lógico, es el nivel correspondiente a la especificación lógica de la estructura, en el nivel lógico se exponen las ideas separadas de su implementación
2- Un nivel Físico, es el nivel en el que se pasa a implementar la especificación desarrollada, en un lenguaje particular.
3- Un nivel de aplicación, es el nivel en el que se utiliza la estructura para resolver algún problema dado.

Bien hasta aquí tenemos 2 ideas separadas, la especificación lógica(independiente del lenguaje) y la implementación (en un lenguaje dado) pero como se relacionan estas dos ideas??..
veamos ahora las distintas formas de representar una estructura.

Formas de representar una estructura
La representación de una estructura es el punto de conexión entre la especificación lógica y la implementación. En esta etapa, se lleva al nivel de abstracción lógica al inicio del nivel físico, aquí se decide como se representaran las estructuras en memoria para poder explotar sus características.
Las estructuras se pueden almacenar de dos formas básicamente:

-Almacenamiento continuo: los datos de la estructura se almacenan en memoria en locaciones continuas de la siguiente manera
[1] [2] [3] .... [n]
donde cada [] representa una localidad de memoria, 1,2,... ,n los datos almacenados las relaciones están dadas según la posición en la que se encuentran

-Almacenamiento disperso: los datos se encuentran en distintos lugares de memoria pero están relacionados por enlaces que le indican dónde se encuentra el sig. elemento
[(k+1)|d(k+2)]...[1|d(2)] [3|d(4)] [4|d(k)] [2|d(3)]... [K|d(k+1)]....
esto es, en cada locación de memoria se almacena, el dato, y la dirección "d" del siguiente dato de la estructura

Ventajas y desventajas de un almacenamiento continuo
Por un lado, el almacenamiento continuo permite, una gran facilidad de recorrido, y muchas veces gran eficiencia a la hora de verificar propiedades sobre la estructura, pero se caen de manera drástica a la hora de insertar y eliminar elementos, ya que como no existe un espacio entre cada elemento, la única forma de insertar un elemento entre medio de 2 existentes es desplazar la estructura completamente, al igual que al eliminar un elemento, se deben mover todos los elementos para ocupar el espacio libre

Ventajas y desventajas del almacenamiento disperso
El almacenamiento disperso posee como principal ventaja, el hecho de que la memoria se utiliza de forma mucho mas eficiente, y se pueden insertar y eliminar elementos de la estructura sin tener que desplazar el resto de los ya insertados. Po r otro lado, una representación dispersa presenta una caída en eficiencia espacial, por el hecho de que cada localidad almacena dos componentes, un dato y una referencia al siguiente dato de la estructura.

Conclusiones finales
Por lo general, cualquier estructura puede ser representada usando almacenamientos continuos o dispersos, pero muchas veces uno sobrepasa al otro por alguna característica particular. Es decir, en algunas estructuras necesitaremos un rápido recorrido sin importar el tiempo de inserción o preferiremos una rápida inserción y eliminación, esto dependerá de la estructura que se este creando y de la capacidad de diseño del programador...
Memoria estática y Memoria Dinámica
Bueno, aquí posteando nuevamente.. en este post analizaremos las diferencias entre la memoria estática y la memoria dinámica
Memoria RAM de una computadora
Bueno, para comenzar con la memoria estática, debemos primero hacer una breve intro al concepto de memoria RAM. Bien la memoria RAM (Random Acces Memory) es la memoria temporal de una computadora, todo lo que se almacena en RAM se pierde automáticamente al cortarse el suministro de electricidad hacia esta. Traten de imaginar a la memoria como una serie de cajas alineadas a la cual se le asigna una dirección especifica en base hexadecimal, algo como lo que sigue
.... [0x001 ] [0x002] [0x003]...
la computadora accede a las localidades de memoria a través de esas direcciones hexa.. podemos distinguir dos tipos de almacenamiento a la hora de programar, el almacenamiento en memoria estática y el almacenamiento en memoria dinámica

Memoria estática
Al escribir un programa, declaramos las variables y constantes que este usara, y las utilizamos a nuestro placer sabiendo que siempre tendremos ese lugar para guardar valores, pero por que podemos asegurar esto???.. Pues bien. A la hora de compilar, el compilador evalúa la cantidad de variables y constantes que este contiene y reserva para su ejecución el espacio de memoria necesario para realizar los almacenamientos sin tener que solicitar más. Esta memoria, que se reserva en tiempo de compilación se conoce como Memoria Estática, la memoria estática no puede crecer ni achicarse en tiempo de ejecución (cuando se esta corriendo el programa) lo que nos presenta una inmensa desventaja. Cuando un programador calcula el espacio de memoria que puede llegar a ocupar su programa, decimos que este esta evaluando cuanto puede "escalar" su programa, es decir como se comportara el programa frente a entradas de distintos tamaños. El uso de memoria estática produce programas que no escalan bien, pues por lo general no se conca el tamaño de entrada que puede llegar a manejar un programa por lo que se podrían tomar dos decisiones, una seria reservar un espacio lo suficientemente grande como para almacenar y procesar cualquier entrada, pero esto significaría un inmenso desperdicio de memoria si el programa no llega a entradas grandes durante una de sus ejecuciones, y por mas grande que lo hagamos, igualmente se presentaría una limitación en algún punto distante, la otra opción y la que por lo general se debe utilizar es el uso de la Memoria Dinámica..
Memoria Dinámica
Bien, como dijimos la memoria estática presenta una gran limitación para proyectos que deben escalar. Entonces como podemos solucionar el problema de no conocer hasta la cantidad de datos que manejara nuestro programa?.. pues bien, la respuesta es la memoria dinámica, pues como funciona??
La memoria RAM , posee un espacio denominado HEAP, este espacio esta reservado para los pedidos de memoria del sistema operativo. El crecimiento y decrecimiento del HEAP, esta determinado por el decrecimiento y crecimiento (respectivamente) de la pila de ejecución. Ahora bien, en memoria estática, los valores se almacenaban directamente en la posición de memoria reservada, en un almacenamiento continuo cuyo tamaño esta dado por el tamaño que utiliza el tipo de datos para almacenarse en memoria, por ejemplo supongamos que un entero ocupa 5 bytes, entonces se reservan 5 bytes de memoria, y el valor almacenado ocupa esas 5 locaciones, de la siguiente forma.
[ val ] [val ] [val ] [val ] [val ]
0x001 0x002 0x003 0x004 0x005
La memoria dinámica, se asigna en tiempo de ejecución cuando el programa la solicita, es decir con el uso de esta memoria, se crean espacios de de memoria mientras el programa se esta ejecutando, pero ahora bien, como creamos accedemos a estos espacios??..
La creación de valores en memoria dinámica se hace pidiendo al SO (sistema operativo de ahora en mas) que permita el acceso a una de las locaciones disponibles del HEAP para almacenar nuestros datos, ahora nuestros programas solo estarán limitados por la capacidad del HEAP, y no por el limite que fijamos en tiempo de programación. Pero como podemos acceder a estos espacios creados?
Como estos espacios se crean en tiempo de ejecución, no tienen una etiqueta asociada necesariamente, por lo que necesitamos una forma de ubicarlos dentro del HEAP, por lo que entra en juego un concepto muy importante de programación, los punteros.
Punteros
El concepto de un puntero puede resultar bastante difícil de entender al principio, pero es indispensable una buena comprensión de este.
Un puntero no es nada mas ni nada menos que una variable que almacena una dirección de memoria. Es decir, un puntero guarda una referencia a una posición que almacena un elemento dado, es decir si usáramos un puntero para referenciar la variable propuesta en el ejemplo anterior
[ val ] [val ] [val ] [val ] [val ]
0x001 0x002 0x003 0x004 0x005
El puntero debería apuntar a la dirección donde comienza el dato almacenado, esto seria,
Puntero a val-- [0x001]
Los punteros se pueden utilizar para referenciar las direcciones que creamos en el HEAP, cuando una variable en memoria dinámica pierde su referencia se dice que se produjo una fuga de memoria o (Memory Leak) , es muy importante evitar las fugas de memoria, por lo que debemos tener muy en claro como estamos referenciando los espacios de memoria creados. Entonces, si tenemos un puntero a un elemento, lo único que tenemos es almacenada la dirección donde se encuentra el elemento, pues bueno, entonces podemos tener varios punteros que contengan el mismo valor?
La respuesta es si, varios punteros que apuntan a un objeto conforman muchas referencias a un mismo elemento por lo que modificar cualquiera de los punteros modifica al elemento en si. Las estructuras de datos tiene una gran base en el uso de punteros, pues nos permitirán que las estructuras crezcan y se achiquen según necesitemos. Es muy importante también saber que si solicitamos una localidad de memoria HEAP debemos ser buenos y devolverla en algún momento para que esta quede a disposición del SO nuevamente y pueda ser reutilizada.

Bien esto concluye una breve intro a los conceptos de memoria estática y dinámica, muy importantes para poder continuar con el desarrollo del curso. En próximos posts comenzaremos con el análisis de las primeras estructuras básicas nativas de todo lenguaje, los arreglos.