Arboles Binarios

Unidad 7: Estructuras Dinámicas Unidad 7 ESTRUCTURAS DINÁMICAS Desarrollo de la unidad : Prácticas : Implementación de algoritmo de lista en C , Pilas y Colas, Ejercicios : Cola de Impresión, Servidor de Internet, Invertir un fichero Conceptos: Memoria dinámica, tablas con memoria dinámica, Listas encadenadas: Listas, Anillos, Dobles, Pilas y Colas Árboles, Binarios, Ordenados, EquilibradosGrafos Introducción

1

Cuando definimos en un programa una variable estática estamos fijado previamente cual va a ser su espacio en memoria y cuales van a ser los posibles valores que puede tomar a lo largo de la ejecución del programa. Existen problemas complejos que se resuelven más eficazmente mediante la utilización de variables que cambien dinámicamente la cantidad o el tipo de datos quepueden contener. Este tipo de estructuras de datos se denomina estructuras dinámicas. Características: - Pueden variar el tamaño ( Número de datos ) a lo largo de la ejecución el programa - Se adaptan mejor a la naturaleza del problema, aprovechando más eficientemente los recursos de memoria. - Son más complejas de manejar pues debemos controlar el crecimiento o reducción del espacio de memoria queocupan. - Se almacenan en memoria principal - Una vez definidas se utilizan como cualquier variable estática. Operaciones especiales Creación : Petición al sistema de una cantidad determinada de memoria para almacenar la nueva variable En Lenguaje C disponemos de la función malloc ( alloc memory ) pedir memoria, nos devuelve la dirección de memoria donde podemos guardar los datos, un puntero a unanueva zona de memoria o NULL en caso de que no exista memoria disponible. Ejemplo: char *cadena; float *preal; TipoDato *pdato; cadena = ( char * ) malloc ( 30 * sizeof(char) ); Espacio para 30 caracteres preal = ( float * ) malloc ( 100 * sizeof(float)); Espacio para 100 número reales pdato = ( TipoDato *) malloc ( sizeof(TipoDato); Espacio para una variable de TipoDato Una vez asignadas podemostrabajar como cualquier variable tipo puntero

Unidad 7: Estructuras Dinámicas strcpy(cadena, “Hola pepe); preal[10] = 3.1416; pdato->edad = 15;

2

Destrucción: Devolución de la memoria, una vez libera la memoria no podemos volver a utilizar la variable, hasta que no reservemos de nuevo espacio. free ( puntero ); free (cadena ); cadena[3] = ‘a’; // Produciría error de ejecución. ESTRUCTURASDINÁMICAS Tablas dinámicas: Tablas donde se define su tamaño en tiempo de ejecución.

No son estructuras dinámicas puras pues una vez definidas no permiten el cambio de tamaño. Ejemplos de la web: 1. Crear un una tabla de un tamaño determinado y mostrar su contenido 2. Unir Tablas char * UnirCadenas ( char *cad1, char * cad2); 3. Cargar un fichero de texto con información de configuración yconsultar su contenido 4. Ordenar un fichero de texto con una tabla de cadenas creadas por memoria dinámica Estructuras dinámicas verdaderas La tablas creadas mediante memoria dinámica no son verdaderas estructuras dinámicas pues una vez definidas en tiempo de ejecución, no pueden cambiar su tamaño, sólo liberarse todo el espacio que ocupas y volver a definirse. Tipos: Listas, árboles y grafos. Lamayor parte de la estructura dinámicas se realizan mediante estructuras auto-referenciadas. Son un tipo de estructuras que contienen punteros a elementos de su mismo tipo Ej.struct SElemento { TipoDato dato; struct SElemento *sig; // Un puntero a estructuras del su mismo tipo }; struct Melemento { TipoDato dato; struct Melemento *pun[4]; // 4 Punteros } typedef struct SElemento TipoDinámicoAuto1;typedef struct Melemento TipoDinámicaAuto4; Dato

Dato

Unidad 7: Estructuras Dinámicas LISTAS ENCADENADAS

3

Definición: Es una secuencia de cero o más elementos de un mismo tipo, en donde cada elemento tiene un elemento anterior y un posterior o siguiente. El orden de los elementos se establece mediante punteros. Existe un primer elemento que no tiene anterior y un último que no posee...