| |
En el capítulo de 'Asignación dinámica de memoria' vimos que para ahorrar memoria podíamos reservarla dinámicamente (sobre la marcha). En mayor parte de los ejemplos que hemos visto hasta ahora reservábamos la memoria que íbamos a usar al comenzar el programa (al definir las variables).
El problema surge a la hora de hacer un programa al estilo de una agenda. No sabemos a priori cuántos nombres vamos a meter en la agenda, así que si usamos un array para este programa podemos quedarnos cortos o pasarnos. Si por ejemplo creamos una agenda con un array de mil elementos (que pueda contener mil números) y usamos sólo 100 estamos desperdiciando una cantidad de memoria importante. Si por el contrario decidimos crear una agenda con sólo 100 elementos para ahorrar memoria y necesitamos 200 nos vamos a quedar cortos. La mejor solución para este tipo de programas son las listas enlazadas.
En una lista enlazada la memoria se va tomando según se necesita. Cuando queremos añadir un nuevo elemento reservamos memoria para él y lo añadimos a la lista. Cuando queremos eliminar el elemento simplemente lo sacamos de la lista y liberamos la memoria usada.
Las listas enlazadas pueden ser simples, dobles o circulares. En este capítulo y el siguiente vamos a ver sólo las listas simples.
Para crear una lista necesitamos recordar nuestros conocimientos sobre estructuras y asignación dinámica de memoria. Vamos a desarrollar este tema creando una sencilla agenda que contiene el nombre y el número de teléfono.
Una lista enlazada simple necesita una estructura con varios campos, los campos que contienen los datos necesarios (nombre y teléfono) y otro campo que contiene un puntero a la propia estructura. Este puntero se usa para saber dónde está el siguiente elemento de la lista, para saber la posición en memoria del siguiente elemento.
struct _agenda {
char nombre[20];
char telefono[12];
struct _agenda *siguiente;
}; Comprobado con DJGPPPodríamos representar la estructura algo así:
Ahora supongamos que añadimos un elemento a la lista, por ejemplo mis datos: nombre="Gorka Urrutia", telefono="99 429 31 23" (el teléfono es totalmente falso :-). Lo primero que debemos hacer es reservar (con la función malloc que ya hemos visto) un espacio en memoria para almacenar el elemento. Supongamos que se almacena en la posición 3000 (por decir un número cualquiera). El puntero siguiente debe apuntar a NULL, ya que no hay más elementos en la lista. El elemento quedaría así:
Ahora añadimos un nuevo elemento: nombre="Alberto López" telefono="99 999 99 99". Hay que reservar (con malloc) memoria para este nuevo elemento. Vamos a imaginar que este elemento se guarda en la posición de la memoria número 3420. La lista quedaría así:
Lo primero que debemos hacer es reservar la memoria para el elemento, luego se le rellenan los datos, se pone el puntero siguiente apuntando a NULL (porque será el último), y decir al elemento anterior que apunte al elemento que hemos añadido.
Si quisiéramos mostrar en pantalla la lista comenzaríamos por el primer elemento, lo imprimiríamos y con el puntero siguiente saltaríamos al segundo elemento, y así hasta que el puntero siguiente apunte a NULL.
Siempre debemos tener un puntero del tipo _agenda para recordar la posición en memoria del primer elemento de la lista. Si perdemos este puntero perderemos la lista completa, así que mucho cuidado. Este puntero se definiría así:
struct _agenda primero;
Añadiendo otro elemento más:
Para estudiar el funcionamiento de una lista simple vamos a usar el programa agenda que hemos comentado arriba. Existen otras formas de implementar una lista simple, pero la que uso en el programa me ha parecido la más sencilla para exlicar su funcionamiento. El programa utiliza dos funciones muy importantes:
Estas dos funciones se explican en los siguientes apartados. Echa una ojeada al código y pasa al siguiente apartado.
Para controlar la lista usamos dos punteros, *primero y *ultimo. Como podrás imaginar el primero guarda la posición del primer elemento y el segundo la del último.
#include <stdio.h>
struct _agenda {
char nombre[20];
char telefono[12];
struct _agenda *siguiente;
};
struct _agenda *primero, *ultimo;
void mostrar_menu() {
printf("\n\nMenú:\n=====\n\n");
printf("1.- Añadir elementos\n");
printf("2.- Borrar elementos\n");
printf("3.- Mostrar lista\n");
printf("4.- Salir\n\n");
printf("Escoge una opción: ");fflush(stdout);
}
/* Con esta función añadimos un elemento al final de la lista */
void anadir_elemento() {
struct _agenda *nuevo;
/* reservamos memoria para el nuevo elemento */
nuevo = (struct _agenda *) malloc (sizeof(struct _agenda));
if (nuevo==NULL) printf( "No hay memoria disponible!\n");
printf("\nNuevo elemento:\n");
printf("Nombre: "); fflush(stdout);
gets(nuevo->nombre);
printf("Teléfono: "); fflush(stdout);
gets(nuevo->telefono);
/* el campo siguiente va a ser NULL por ser el último elemento
de la lista */
nuevo->siguiente = NULL;
/* ahora metemos el nuevo elemento en la lista. lo situamos
al final de la lista */
/* comprobamos si la lista está vacía. si primero==NULL es que no
hay ningún elemento en la lista. también vale ultimo==NULL */
if (primero==NULL) {
printf( "Primer elemento\n");
primero = nuevo;
ultimo = nuevo;
}
else {
/* el que hasta ahora era el último tiene que apuntar al nuevo */
ultimo->siguiente = nuevo;
/* hacemos que el nuevo sea ahora el último */
ultimo = nuevo;
}
}
void mostrar_lista() {
struct _agenda *auxiliar; /* lo usamos para recorrer la lista */
int i;
i=0;
auxiliar = primero;
printf("\nMostrando la lista completa:\n");
while (auxiliar!=NULL) {
printf( "Nombre: %s, Telefono: %s\n",
auxiliar->nombre,auxiliar->telefono);
auxiliar = auxiliar->siguiente;
i++;
}
if (i==0) printf( "\nLa lista está vacía!!\n" );
}
int main() {
char opcion;
primero = (struct _agenda *) NULL;
ultimo = (struct _agenda *) NULL;
do {
mostrar_menu();
opcion = getch();
switch ( opcion ) {
case '1': anadir_elemento();
break;
case '2': printf("No disponible todavía!\n");
break;
case '3': mostrar_lista(primero);
break;
case '4': exit( 1 );
default: printf( "Opción no válida\n" );
break;
}
} while (opcion!='4');
}Reproducimos aquí de nuevo el código de la función anadir_elemento.
Lo primero creamos un puntero que apuntará al nuevo elemento que vamos a añadir:
struct _agenda *nuevo;
Una vez creado el puntero tenemos que reservar un espacio en memoria donde se almacenará el nuevo elemento. Este espacio debe ser del tamaño de la estructura, que lo conocemos usando "sizeof(struct _agenda)". Hacemos que el puntero guarde la posición de ese espacio reservado.
Por supuesto comprobamos el valor del puntero para saber si la operación se ha realizado con éxito. Si no hay memoria suficiente para el puntero éste tomará el valor NULL.
/* reservamos memoria para el nuevo elemento */
nuevo = (struct _agenda *) malloc (sizeof(struct _agenda));
if (nuevo==NULL) printf( "No hay memoria disponible!\n");
El siguiente paso es pedir al usuario del programa que meta los datos. Estos datos se almacenarán directamente en la memoria que hemos reservado gracias al puntero que usamos.
printf("\nNuevo elemento:\n");
printf("Nombre: "); fflush(stdout);
gets(nuevo->nombre);
printf("Teléfono: "); fflush(stdout);
gets(nuevo->telefono);
El último elemento de la lista siempre va a apuntar a NULL, de esta forma sabemos cuál es el último elemento. Dado que en este ejemplo vamos a meter los elementos siempre al final de la lista, el campo siguiente tiene que ser NULL.
/* el campo siguiente va a ser NULL por ser el último elemento
de la lista */
nuevo->siguiente = NULL;
El último paso es meter el elemento dentro de la lista (hasta ahora sólo teníamos un elemento aislado, que nada tenía que ver con la lista).
Antes de meterlo en la lista debemos comprobar si ya existía algún elemento antes. Para ello vamos a comprobar el valor del puntero primero que debería apuntar al primer elemento. Si primero es NULL eso significa que no hay ningún elemento en la lista, así que el nuevo elemento será a la vez el primero y el último de la lista:
/* ahora metemos el nuevo elemento en la lista. lo situamos
al final de la lista */
/* comprobamos si la lista está vacía. si primero==NULL es que no
hay ningún elemento en la lista. también vale ultimo==NULL */
if (primero==NULL) {
printf( "Primer elemento\n");
primero = nuevo;
ultimo = nuevo;
}
Si ya existía algún elemento, debemos situar el nuevo elemento después del último. Para ello hacemos que el campo siguiente del último elemento apunte al nuevo elemento (ultimo->siguiente = nuevo;). Una vez hecho esto hacemos que el nuevo elemento sea el último de la lista (ultimo = nuevo;).
else {
/* el que hasta ahora era el último tiene que apuntar al nuevo */
ultimo->siguiente = nuevo;
/* hacemos que el nuevo sea ahora el último */
ultimo = nuevo;
}
}
Ya tenemos la forma de añadir elementos a una lista, ahora vamos a ver cómo recorrer la lista y mostrar su contenido.
Para recorrer la lista usaremos un puntero auxiliar al que en un ataque de rabiosa originalidad llamaremos auxiliar.
Para comenzar debemos hacer que 'auxiliar' apunte al primer elemento de la lista (auxiliar=primero). Para recorrer la lista usamos un bucle while y comprobamos el valor de 'auxiliar'. Hemos visto que el campo 'siguiente' del último elemento apuntaba a NULL, por lo tanto, cuando 'auxiliar' sea NULL sabremos que hemos llegado al final de la lista.
En cada vuelta del ciclo mostramos el elemento actual y saltamos al siguiente. El campo 'siguiente' del puntero 'auxiliar' contiene la dirección del siguiente elemento. Si hacemos que 'auxiliar' salte a la dirección almacenada en 'auxiliar->siguiente' estaremos en el siguiente elemento.
Es importante no olvidar saltar al siguiente elemento, puesto que si no lo hacemos así no habrá forma de salir del bucle (estaremos siempre en el primer elemento).
Como curiosidad se ha añadido una variable i con la que se cuenta el número de elementos de la lista. Si al final del bucle 'i' es cero, significa que no hay elementos en la lista.
void mostrar_lista() {
struct _agenda *auxiliar; /* lo usamos para recorrer la lista */
int i;
i=0;
auxiliar = primero;
printf("\nMostrando la lista completa:\n");
while (auxiliar!=NULL) {
printf( "Nombre: %s, Telefono: %s\n",
auxiliar->nombre,auxiliar->telefono);
auxiliar = auxiliar->siguiente;
i++;
}
if (i==0) printf( "\nLa lista está vacía!!\n" );
}