http://www.buenastareas.com/ensayos/Documentologia-Mecanografia/2970028.html

Objetivos
• Asignar y liberar memoria dinámicamente para objetos de datos.
• Formar estructuras de datos por medio de apuntadores, de estructuras autorreferenciadas y de recursividad.
• Crear y manipular listas ligadas, colas, pilas y árboles binarios.
• Comprender diversas aplicaciones importantes de las estructuras de datos ligadas
Estructuras autorreferenciadasUna estructuraautorreferenciada contiene un miembro apuntador, el cual apunta hacia una estructura del mis- mo tipo. Por ejemplo, la definición
struct nodo { int dato; struct nodo *ptrSiguiente; }; define un tipo, struct nodo. Una estructura del tipo struct nodo tiene dos miembros; el miembro ente- ro dato y el miembro apuntador ptrSiguiente. El miembro ptrSiguiente apunta hacia la estructura de tipo struct nodo; unaestructura del mismo tipo que la que estamos declarando aquí, y de ahí el término “estructura autorreferenciada”. El miembro ptrSiguiente se conoce como liga, es decir, este miembro pue- de utilizarse para “unir” una estructura del tipo struct nodo con otra estructura del mismo tipo. Las estruc- turas autorreferenciadas pueden ligarse entre sí para formar estructuras de datos útiles, como listas,colas, pilas y árboles. La figura 12.1 ilustra dos objetos del tipo de estructuras autorreferenciadas ligadas para formar una lista. Observe que se coloca una diagonal (que representa un apuntador NULL) en el miembro liga de la según- da estructura autorreferenciada, para indicar que la liga no apunta hacia otra estructura. [Nota: La diagonal se utiliza sólo para efectos de ilustración; nocorresponde al carácter de diagonal invertida de C.] Un apuntador NULL generalmente indica el final de una estructura de datos, tal como el carácter nulo indica el final de una cadena.
Asignación dinámica de memoria
Crear y mantener estructuras de datos dinámicas requiere de la asignación dinámica de memoria; es decir, la habilidad de un programa para obtener más espacio de memoria en tiempo deejecución, para almacenar nue- vos nodos, y para liberar espacio que ya no es necesario. El límite para la asignación dinámica de memoria pue- de ser tan grande como la cantidad de memoria físicamente disponible en la computadora, o la virtualmente disponible en un sistema de memoria virtual. Con frecuencia, los límites son mucho más pequeños debido a que la memoria debe compartirse entre muchasaplicaciones. Las funciones malloc y free, y el operador sizeof son básicos para la asignación dinámica de me- moria. La función malloc toma como un argumento al número de bytes que van a asignarse, y devuelve un apuntador de tipo void* (apuntador a void) hacia la memoria asignada. Un apuntador void* puede asig- narse a una variable de cualquier tipo de apuntador. La función malloc normalmente se utilizacon el apun- tador sizeof. Por ejemplo, la instrucción
ptrNuevo = malloc( sizeof( struct nodo ) ); evalúa a sizeof( struct nodo ) para determinar el tamaño en bytes de una estructura del tipo struct nodo, para asignar una nueva área en memoria que coincida con ese número de bytes, y para almacenar un apuntador a la memoria asignada a la variable prtNuevo. La memoria asignada no se inicializa. Sino hay memoria disponible, malloc devuelve NULL. La función free libera memoria, es decir, la memoria se devuelve al sistema para que ésta pueda reasig- narse en el futuro. Para liberar memoria dinámicamente asignada por la llamada anterior a malloc, utilice la instrucción free ( ptrNuevo );

Las siguientes secciones explican las listas, pilas, colas y árboles, cada una de las cuales se crea y seman- tiene por medio de estructuras autorreferenciadas y asignación dinámica de memoria.
Listas ligadas
Una lista ligada es una colección lineal de estructuras autorreferenciadas, llamadas nodos, conectadas por me- dio de ligas apuntador; de aquí el término lista “ligada”. Se accede a una lista ligada a través de un apuntador al primer nodo de la lista. Se accede a los nodos subsiguientes a...