Introducción

Una de las aplicaciones más interesantes y potentes de la memoria dinámica y de los punteros son, sin duda, las estructuras dinámicas de datos. Las estructuras básicas disponibles en C y C++ (structs y arrays) tienen una importante limitación: no pueden cambiar de tamaño durante la ejecución. Los arrays 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 crear arrays dinámicos, pero una vez creados, tu tamaño también será fijo, y para hacer que crezcan o disminuyan de tamaño, deberemos reconstruirlos desde el principio.

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, la estructura 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 nodo.

Una estructura básica de un nodo para crear listas de datos seria:

struct nodo {
   int dato;
   struct nodo *otronodo;
};

El campo "otronodo" puede apuntar a un objeto del tipo nodo. De este modo, cada nodo puede usarse como un ladrillo para construir listas de datos, y cada uno mantendrá ciertas relaciones con otros nodos.

Para acceder a un nodo de la estructura sólo necesitaremos un puntero a un nodo.

Durante el presente curso usaremos gráficos para mostrar la estructura de las estructuras de datos dinámicas. El nodo anterior se representará asi:

gráfico de nodo
Nodo

Las estructuras dinámicas son una implementación de TDAs o TADs (Tipos Abstractos de Datos). En estos tipos el interés se centra más en la estructura de los datos que en el tipo concreto de información que almacenan.

Dependiendo del número de punteros y de las relaciones entre nodos, podemos distinguir varios tipos de estructuras dinámicas. Enumeraremos ahora sólo de los tipos básicos:

  • Listas abiertas: cada elemento sólo dispone de un puntero, que apuntará al siguiente elemento de la lista o valdrá NULL si es el último elemento.
  • Pilas: son un tipo especial de lista, conocidas como listas LIFO (Last In, First Out: el último en entrar es el primero en salir). Los elementos se "amontonan" o apilan, de modo que sólo el elemento que está encima de la pila puede ser leído, y sólo pueden añadirse elementos encima de la pila.
  • Colas: otro tipo de listas, conocidas como listas FIFO (First In, First Out: El primero en entrar es el primero en salir). Los elementos se almacenan en fila, pero sólo pueden añadirse por un extremo y leerse por el otro.
  • Listas circulares: o listas cerradas, son parecidas a las listas abiertas, pero el último elemento apunta al primero. De hecho, en las listas circulares no puede hablarse de "primero" ni de "último". Cualquier nodo puede ser el nodo de entrada y salida.
  • Listas doblemente enlazadas: cada elemento dispone de dos punteros, uno a punta al siguiente elemento y el otro al elemento anterior. Al contrario que las listas abiertas anteriores, estas listas pueden recorrerse en los dos sentidos.
  • Arboles: cada elemento dispone de dos o más punteros, pero las referencias nunca son a elementos anteriores, de modo que la estructura se ramifica y crece igual que un árbol.
  • Arboles binarios: son árboles donde cada nodo sólo puede apuntar a dos nodos.
  • Arboles binarios de búsqueda (ABB): son árboles binarios ordenados. Desde cada nodo todos los nodos de una rama serán mayores, según la norma que se haya seguido para ordenar el árbol, y los de la otra rama serán menores.
  • Arboles AVL: son también árboles de búsqueda, pero su estructura está más optimizada para reducir los tiempos de búsqueda.
  • Arboles B: son estructuras más complejas, aunque también se trata de árboles de búsqueda, están mucho más optimizados que los anteriores.
  • Tablas HASH: son estructuras auxiliares para ordenar listas.
  • Grafos: es el siguiente nivel de complejidad, podemos considerar estas estructuras como árboles no jerarquizados.
  • Diccionarios.

Al final del curso también veremos estructuras dinámicas en las que existen nodos de distintos tipos, en realidad no es obligatorio que las estructuras dinámicas estén compuestas por un único tipo de nodo, la flexibilidad y los tipos de estructuras sólo están limitados por tu imaginación como programador.

Comentarios de los usuarios (16)

Wladimir
2009-12-10 14:53:51

Excelente contribución tanto para los profesores como a los estudiantes, los felicito por tan grandiosa iniciativa.

tandazo salinas
2010-02-02 17:09:56

excelente trabajo muy buen trabajo.

Luis Tovar
2010-05-05 16:25:39

Esta muy bueno y completo el apunte............ pero hace falta un pequeño example sobre el tema

Anónimo
2010-06-18 16:59:15

Muy buena contribucion esta pagina de verdad que sirve para los alumnos que estudian informaticaa =) MUCHAS GRACIAS

Javier
2011-02-16 18:55:40

Excelente página. Os felicito.

Anonimo
2011-10-21 23:47:37

Excelente página, es muy explicativa y muy completa, me leí todo el curso de C++ desde lo más básico del C, hasta el manejo de excepciones de C++, me di el trabajo de leer todo con calma, para entender correctamente los temas, ahora estoy terminando de ver arboles y ya tendría listo el curso de E.D.D.

Yo estudio para informatica, pero realmente en este curso he aprendido a programar, pues en mi universidad es muy lamentable la calidad de los profesores, por ejemplo todos enseñan a reservar memoria con el operador new, pero nadie dice que hay que liberarla, eso me parece una actitud muy irresponsable como programadores que son los profesores, por eso no me fío mucho de lo que dicen, por lo menos en programación prefiero ser autodidacta en mis conocimientos, ya que al parecer, hay muchos profesores que no aprendieron bien como funciona c++, en fin, muchas gracias por haberme enseñado bien, aqui es donde estoy aprendiendo realmente a programar, saludos y muchas gracias.

guillermo
2012-01-15 05:53:23

lei todo el curso de c++ con clase.net pero no encontre nada de Sublistas, en la U me pidieron algo sobre Lista con SubLista, utilizando dos Estructuras.

Struct Lista{

char dato1[10];

struct Lista *siguiente;

struct Sublista *sig;

};

Struct Sublista{

char dato2[10];

struct Sublista *sig;

};

Podrian ayudarme a crear la insercion o talvez orientarme como hacer dicha insercion!.

guillermo
2012-01-16 17:33:05

ya logre hacerlo, era una estructura anidada.

Diego
2012-03-20 22:32:17

Esta página es Excelente. Todo lo que he leído aquí:

- Curso C++

- E.D.D.

- Archivos en C/C++

- Algoritmos de ordenamiento

- y algunas funciones de biblioteca estándar

Está muy bien explicado.

Gracias a esta página pude aprender de verdad los temas que se tratan. Seguramente por el único hecho de que la información está clara y sencilla, osea, bien explicada.

Pongo mi comentario aquí, porque me gustaría saber si tratarán los temas de las estructuras de datos que faltan,

se que Árboles B, está en algoritmos de la sección de artículos, sin embargo, no he encontrado tablas Hash ni Grafos, me gustaría mucho si escribieran algo sobre eso.

De todas formas la página es increíble y aun queda mucho por aprender de lo que sale aquí, como la API de windows y el curso de Gráficos.

Muchas gracias por todo.

fabricio
2012-11-14 01:45:41

hola..!! muy buena la pagina.!! me ayudo un montón en esto de listas....si pudieras agregar la explicación de listas de listas seria buenísimo...saludos...!! sigan así.!!

Steven R. Davidson
2012-11-14 02:20:37

Hola Fabricio,

La verdad es que no hay diferencia entre la implementación de una lista de enteros y una lista de listas de enteros, por ejemplo. La lista dinámicamente enlazada sirve para guardar cualquier valor de cualquier tipo de dato, en cada nodo. Da igual si se trata de un entero como de un puntero, o una lista de punteros a enteros.

En C++, podemos usar plantillas y así generar el tipo de lista que nos interesa. Sugiero que eches un vistazo al ejemplo de C++ con plantillas al final del capítulo 1. Puedes ir directamente a: http://c.conclase.net/edd/?cap=001h#1_11

Espero que esto te oriente.

Steven

Ian
2013-11-12 00:59:03

Los árboles AVL no están diseñados para mejorar la búsqueda, están diseñados para mejorar la insercción y borrado respecto al árbol binario, pues la complejidad de la búsqueda es logaritmica en los 2, pero la insercción y borrado solo es logarítmica en el AVL, en el otro es N.

allan
2013-12-03 02:46:00

Hola que tal quisiera saber si tienen alguna información acerca de las listas delta(sistemas operativos)

muchas gracias

Steven R. Davidson
2013-12-03 06:38:06

Hola Allan,

Sirve para guardar la diferencia de tiempos - los deltas - entre varios procesos para mantener eventos de alertas. La idea es guardar los deltas en lugar de guardar los tiempos absolutos ni los tiempos relativos. Los deltas son la diferencia entre un tiempo y el anterior. Por ejemplo, el tiempo actual es 1000,

Absoluto: 1012, 1025, 1030, 1031, 1059

Relativo: 12, 25, 30, 31, 59

Delta: 12, 13, 5, 1, 28

La ventaja es que no hace falta actualizar todos los tiempos en la lista, como ocurre con los tiempos absolutos y relativos. Puedes pensar que una lista delta se usa como un tipo de cola con prioridad.

Para más información, puedes consultar este enlace (está en inglés): http://www.cs.unc.edu/~dewan/242/s04/notes/int.PDF

Espero que esto te oriente.

Steven

melissa
2014-01-23 03:14:21

Hola muchas gracias

Misael Alberto Moneró Thompson
2014-03-30 05:53:58

Muchas gracias! exelentes ejemplos, algo enrredadizo a primera vista pero luego de estudiar la logica un momento es algo exlente! gracias amigos por compartir sus conocimientos!