Programar

ESTRUCTURAS DINÁMICAS DE DATOS
EN LENGUAJE C

Realizado por Ismael Camarero
icamarero@gmail.com
Forma parte de la web:
http://programandoenc.webcindario.com
Junio de 2005.

ESTRUCTURAS DINÁMICAS DE DATOS EN LENGUAJE C

Ismael Camarero S.

http://programandoenc.webcindario.com

2

ESTRUCTURAS DINÁMICAS DE DATOS EN LENGUAJE C

Ismael Camarero S.http://programandoenc.webcindario.com

Generalidades:
Introducción:
Hasta ahora, hemos empleado diferentes tipos de datos: int, char, float… y agrupaciones de estos como
pueden ser los arrays, struct… Sin embargo, pese a su utilidad, presentan un problema: deben ser
declarados en todo su tamaño. Si declaramos un array como:
float array[100[100];
estamos declarando un array de 100x100 elementos flotantes que van aocupar
100x100xsizeof(float) bytes de memoria.
El tamaño se decide en la declaración de la variable, no en el momento en que lo necesitamos.
Pero ¿qué sucede si sólo queremos guardar un elemento? Que desaprovechamos el resto de la memoria
reservada para 10000 elementos float. Es un derroche que, aunque con las memorias actuales se pueda
permitir, no debemos hacer.
Además ¿qué sucedería si en unmomento necesitamos cambiar la cantidad de datos a almacenar?
Una de las aplicaciones más interesantes y potentes de la memoria dinámica y los punteros son las
estructuras dinámicas de datos. Las estructuras básicas disponibles en C y C++ tienen una importante
limitación: no pueden cambiar de tamaño durante la ejecución. Los arreglos están compuestos por un
determinado número de elementos,número que se decide en la fase de diseño, antes de que el programa
ejecutable sea creado.
En muchas ocasiones se necesitan estructuras que puedan cambiar de tamaño durante la ejecución del
programa. Por supuesto, podemos hacer 'arrays' dinámicos, pero una vez creados, tu tamaño también
será fijo, y para hacer que crezcan o diminuyan de tamaño, deberemos reconstruirlas desde el principio(funciones calloc(), malloc() y realloc())
Vamos a ver una nueva forma de gestionar datos: ESTRUCTURAS DINAMICAS DE DATOS
Las estructuras dinámicas nos permiten crear estructuras de datos que se adapten a las necesidades reales
a las que suelen enfrentarse nuestros programas. Pero no sólo eso, como veremos, también nos
permitirán crear estructuras de datos muy flexibles, ya sea en cuanto al orden, laestructura interna o las
relaciones entre los elementos que las componen.
Las estructuras de datos están compuestas de otras pequeñas estructuras a las que llamaremos nodos o
elementos, que agrupan los datos con los que trabajará nuestro programa y además uno o más punteros
autoreferenciales, es decir, punteros a objetos del mismo tipo tipo.
3

ESTRUCTURAS DINÁMICAS DE DATOS EN LENGUAJE CIsmael Camarero S.

http://programandoenc.webcindario.com

Dentro de los datos de este tipo de datos podemos hablar de:
•

Listas.

•

Pilas.

•

Colas.

•

Árboles.

•

Grafos

LISTAS ENLAZADAS
Una lista lineal enlazada es un conjunto de elementos u objetos de cualquier tipo, originariamente vacía
que, durante la ejecución del programa va creciendo o decreciendoelemento a elemento según las
necesidades previstas.
En una lista lineal cada elemento apunta al siguiente, es decir, cada electo tiene información de dónde
esta el siguiente. Por este motivo también se le llama lista enlazada.
Gráficamente se puede representar en la forma:

c
sig

sig

sig

NULL

Las estructuras dinámicas son una implementación de TDAs o TADs (Tipos Abstractos deDatos).
Dependiendo del número de punteros y de las relaciones entre nodos, podemos distinguir varios tipos
de estructuras dinámicas:
Listas simplemente enlazadas (o abiertas):
Cada elemento (nodo) sólo dispone de un puntero, que apuntará al siguiente elemento de la lista o
valdrá NULL si es el último elemento. Sólo se pueden recorrer hacia delante.

4

ESTRUCTURAS DINÁMICAS DE DATOS EN...