Listas Enlazadas en Borland C++
Punteros (Listas Enlazadas)
Se trata de combinar las estructuras con los punteros para acabar por fin con la limitación de los arrays, ya no hará falta indicar el tamaño del array al principio. Después comentaremos los pros y los contras de las listas enlazas respecto a los arrays.
Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento. Una lista enlazada es un tipo de dato auto referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante, pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas y Listas Enlazadas Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C, C++ o Java disponen de referencias para crear listas enlazadas.
Las listas enlazadas pueden ser simples, dobles o circulares. De momento veremos las simples. Estas listas tendrán una estructura como la de la figura:
Para crear listas necesitaremos estructuras asignación dinámica de memoria. Vamos a ver como utilizar una lista en el ejemplo de la agenda:
struct _agenda {
char nombre[20];
char telefono[12];
struct _agenda *siguiente;
}; Memoria dinámica
Para optimizar la memoria, lo ideal sería reservar memoria en el momento que la necesitásemos y no como hasta la fecha, que lo hacíamos al principio del programa.
Malloc y free
Estas dos funciones nos servirán para asignar dinámicamente memoria. Estas 2 funciones se encuentran en la librería
malloc(); Reserva memoria y devuelve la posición de memoria del comienzo de ésta, por lo que deberemos guardar el resultado en un puntero (más información de punteros en el número 13 de la revista de hackxcrack) . Si no se ha podido reservar memoria, malloc devolverá el valor NULL, así que el puntero apuntará a NULL. Es importante asegurarnos de que se ha podido reservar la memoria, haremos algo así:
puntero = (Tipo_variable *) malloc (bytes_reservar);
if(puntero = (int *) malloc (sizeof(char)))
{puts (“Correcto”);}
| free() | Cuando ya no necesitemos el espacio que habíamos reservado, liberaremos la memoria, haremos: |
free(puntero);
Descarga el ejemplo para mayor compresion del tema:
Nota: El ejemplo se realizo en Borland C++.
http://rapidshare.com/files/118472102/menu.rar.html
Saludos... Su colega y amigo Zanabria
Zanabria_Talledos@hotmail.com
Zanabriata@yahoo.com.mx
1 comentario
Donaldo -