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 que pueden 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 que ocupan.
-
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
una nueva 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 podemos trabajar como cualquier
variable tipo puntero
strcpy(cadena,
“Hola pepe); preal[10] = 3.1416;
pdato->edad =
15;
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.
ESTRUCTURAS DINÁ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 y consultar 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.
La mayor
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;
LISTAS ENCADENADAS
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 posterior,
-
Una lista puede crecer o
decrecer con facilidad sin tener que desplazar su elementos, está limitada por
la cantidad máxima de memoria que disponga el
proceso.
-
Las listas se pueden
implementación mediante estructuras autoreferenciadas o mediante una tablas,
estando limitado en este caso el número máximo de elementos al tamaño de la tabla.
Implementación mediante estructuras autoreferenciadas:
typedef int
TipoDato; // TipoDato puede ser cualquier tipo. struct SEle{
TipoDato valor;
struct SEle *sig;
};
typedef
struct SEle Elemento;
Elemento *Base; Representación Gráfica:
Base
Operaciones Básicas:
1.
Creación
2. Primero
3. Ultimo
4. Poner Al principio
5. Poner Al Final
6. Borrar Al principio
7. Borrar Al final
8. Borrar Toda la Lista
9. Inserta Elemento
10. Borrar Elemento
Ejercicios propuestos:
·
Unir dos listas.
·
Crear dos listas una de pares y otra de impares
ceder elemento de una a otra.
·
Crear una lista a partir de una cadena de
caracteres.
·
Invertir una lista.
|
/*
------------------------------------------------------------ */
|
|
}
|
|
*/
|
|
|
|
/*
------------------------------------------------------------ */
|
|
/*----------------------------------------------------------------*/
|
|
|
|
|
|
#include <stdio.h>
|
|
boolean Vacia(void)
|
|
|
{
|
/* ------------------------------------------------- */
/* ------------------------------------------------- */
boolean PonAlFinal (TipoDato Dato); boolean PonAlPrincipio
(TipoDato Dato); boolean BorrarAlFinal (void);
boolean
InsertarEnOrden (TipoDato Dato ); boolean BorrarElemento
(TipoDato Dato ); void VerLista (void);
/*----------------------------------------------------------------*/
{
return ( Base == NULL)?TRUE:FALSE;
}
/*----------------------------------------------------------------*/
/* ‹ evuelve el valor
almacenado en el primer elemento de la Lista
*/
TipoDato Primero(void)
{
return Base->valor;
}
/*----------------------------------------------------------------*/
/*
Devuelve el valor almacenado en el
último elemento de la Lista */
TipoDato Ultimo(void)
{
Elemento *paux; paux = Base;
while (
paux->sig != NULL )
{
paux = paux->sig;
}
return paux->valor;
}
Base = NULL;
}
}
while (
paux->sig != NULL )
{
paux = paux->sig;
}
/*
El puntero siguiente del último elemento
señala al nuevo */
paux->sig = pnuevo;
}
else
{
/*
La lista está vacia */
/*
Base señala al nuevo elemento */
Base =
pnuevo;
}
return TRUE;
}
/*----------------------------------------------------------------*/
/* Elimina el
primer elemento de la lista */
boolean
BorrarAlPrincipio (void)
{
{
{
return FALSE;
}
{
paux = Base;
Elemento *paux;
paux = Base; if
( !Vacia() )
{
/*
Señala al siguiente y libero memoria */
Base = Base->sig;
free(paux);
return TRUE;
}
return FALSE;
}
return FALSE;
}
else
{
else
}
return TRUE;
}
{
if ( pnuevo ==
NULL )
{
return FALSE;
}
pnuevo->valor
= Dato;
/*
Si está vacia */ if ( Base == NULL )
{
Base = pnuevo;
pnuevo->sig = NULL;
}
else
{
/*
Si está antes del primero */ if ( Base->valor > pnuevo->valor )
{
pnuevo->sig
= Base; Base = pnuevo;
}
else
{
paux1 = Base; /* Primero */ paux2
= Base->sig; /* Segundo */ while (
paux2 != NULL )
{
if (
paux2->valor > pnuevo->valor )
{
break;
}
paux1 = paux2;
paux2 = paux2->sig;
}
// Inserto
paux1->sig =
pnuevo; pnuevo->sig = paux2;
}
}
return TRUE;
}
/*----------------------------------------------------------------*/
Elemento *paux1,*paux2;
return FALSE;
}
else
}
{
}
else
{
}
}
/*----------------------------------------------------------------*/
/* Muestra el
contenido de la lista */ void
VerLista ( void )
{
Elemento *paux;
printf("\n
LISTA: ["); paux = Base;
while ( paux !=
NULL )
{
printf("->%d ",paux->valor); paux = paux->sig;
}
printf("]\n");
}
/*----------------------------------------------------------------*/
/* Borrar todos
los elemento de la lista */ void VaciarLista(void)
{
Elemento *paux; while ( Base != NULL )
{
paux = Base;
Base = Base->sig; free(paux);
}
}
return TRUE;
} 
No hay comentarios:
Publicar un comentario