Continuamos con la segunda parte del noveno
capítulo del curso básico de C. En la primera parte definíamos el concepto de
nodo, de estructura dinámica, tipos de estructuras dinámicas, comenzábamos con
las listas enlazadas dinámicamente y veíamos cuatro operaciones sencillas para
realizar con ellas. Ahora continuamos con la segunda parte donde veremos más
operaciones con listas de enlace simple.
 |
| Foto tomada de freedigitalphotos.net |
Si en la primera parte podíamos ver las
operaciones de inserción y borrado en la cabeza y en la cola de la lista hoy
vamos a ver otras operaciones también de mucha utilidad, como la búsqueda de un
elemento, la modificación, la inserción o borrado de un nodo concreto u otras
operaciones elementales. Además los códigos que veremos ya vendrán con los
controles de lista con un nodo o lista vacía. Comencemos.
Tamaño de una lista.
Habrá ocasiones en las que nos sea necesario
conocer el tamaño de una lista completa, este programa es bastante sencillo
puesto que sólo debemos ir contando los nodos que existen. Recordemos que la
mejor forma de recorrer una lista es mediante un bucle while.
El programa sería así:
{
struct Nodo * aux;
int cont = 0;
aux=lista;
while( aux != NULL)
{
cont++;
aux = aux->siguiente;
}
return cont;
}
Acceso a los campos de un nodo.
De nada nos sirve montar una estructura
dinámica de datos si no podemos acceder o modificar los datos que se están
almacenando. El acceso es bastante sencillo, tan sólo hay que localizar un nodo
concreto (recorriendo la lista con el puntero *aux hasta que encontremos el que
deseamos) y acceder a los datos para operar con ellos mediante el operador
->.
Un código de ejemplo que muestra en pantalla
el valor de los datos:
{
struct Nodo * aux;
aux=lista;
while( aux != NULL)
{
printf ("%d\n", aux->dato1);
aux = aux->siguiente;
}
}
Un código de ejemplo que multiplica por dos
un valor si éste es par:
{
struct Nodo * aux;
aux=lista;
while( aux != NULL)
{
if (aux->dato1%2==0)
{
aux->dato1= aux->dato1*2;
}
aux = aux->siguiente;
}
}
Buscar un elemento en una lista.
Otro algoritmo bastante sencillo, se trata
de que dado un valor de tipo entero, recorramos la lista y busquemos ese
elemento, si lo hemos encontrado antes de llegar al final devolvemos un valor,
sino devolvemos otro valor.
El código de ejemplo es el siguiente:
{
struct Nodo * aux;
aux=lista;
while( aux != NULL)
{
if (aux->dato1
== valor)
{
return 1;
}
aux =
aux->siguiente;
}
return 0;
}
Esto puede usarse de varias formas, como por
ejemplo para modificar un valor, o pintarlo en pantalla, el código puede
modificarse al gusto.
Borrado de un nodo cualquiera.
De nuevo volvemos a complicar los algoritmos
un poco. Ya hemos visto cómo borrar el primer nodo y el último de la lista,
ahora vamos a ver cómo borrar un nodo cualquiera dentro de la lista basándonos
en un dato concreto.
La idea es que dado un dato se localice y
borre el nodo. Aquí debemos ir aplicando ciertos conocimientos que ya hemos
adquirido, como el uso de un segundo puntero auxiliar que vaya por detrás del
puntero *aux.
¿Por qué utilizar un segundo puntero
auxiliar?
Planteemos el siguiente caso: Tenemos una
lista de 10 nodos con valores enteros que van del 1 al 10 respectivamente,
queremos borrar el nodo número 5.
Necesitamos el puntero *aux para poder encontrar
el nodo 5, y necesitamos también el nuevo nodo *atras para ir apuntando al nodo
inmediatamente anterior, de tal forma que cuando borremos el nodo 5 el *atras
apunte al nodo 4 y podamos enlazarlo con el aux-> siguiente, que apuntará al
nodo 6, así no perderemos el resto de la lista.
El código es el siguiente:
{
struct Nodo *
aux, * atras ;
atras=NULL;
aux=lista;
while (aux != NULL)
{
if (aux->dato1
== valor) {
if (atras ==
NULL)
{
lista = aux-> siguiente;
}
else
{
atras-> siguiente = aux-> siguiente;
}
free(aux);
return lista;
}
atras = aux;
aux =
aux->siguiente;
}
return lista;
}
El planteamiento es sencillo:
-
Inicializar *aux al inicio de la lista,
*atrás a NULL.
-
Recorre la lista, *atras toma el valor de
*aux y después *aux toma el valor del nodo siguiente. De esta forma *atras
siempre estará situado en el nodo inmediatamente anterior a *aux.
-
Si se encuentra el dato.
-
Si *atras vale NULL significa que el que
ha encontrado es el primer nodo de la lista, por lo que lo único que hay que
hacer es como en el borrado al principio, situar *lista en aux-> siguiente.
-
Si *atras no vale NULL significa que el
nodo a eliminar está en una posición determinada de la lista, por lo que se
hace que atras -> siguiente apunte a aux-> siguiente, quedando la lista
completamente enlazada.
-
Se libera *aux, eliminando así el nodo.
Si nos fijamos en el código, está construido
de tal forma que sirve también tanto para un borrado en cabeza como para un borrado en
cola además de para un borrado de un nodo cualquiera. Por lo que los códigos de
borrados de la primera parte pueden ser sustituidos por éste de forma opcional.
Borrado de todos los nodos que coincidan con
un valor.
Ahora planteemos el siguiente caso:
imaginemos que tenemos una lista de 10 nodos, con valores 1 y 2 de forma
aleatoria, queremos borrar todos los nodos que tengan el valor 1.
Para poder abordar éste caso el código
anterior no nos es suficiente, ya que sólo borra la primera aparición. Podemos
hacer dos cosas:
1 – Llamar al código anterior tantas veces
como sea necesario. Es una opción nada optima, pero una solución, recomendaría
usarla sólo en el caso de no saber abordar el problema.
2 – Realizar una función parecida a la
anterior pero haciendo que *aux apunte a atrás-> siguiente una vez realizado
el borrado, de ésta forma podemos continuar recorriendo la lista.
Para la segunda solución el código es el
siguiente:
{
struct Nodo *
aux, * atras ;
atras = NULL;
aux = lista;
while (aux != NULL) {
if (aux->dato1
== valor) {
if (atras ==
NULL)
{
lista = aux-> siguiente;
}
else
{
atras-> siguiente = aux-> siguiente;
}
free(aux);
if (atras ==
NULL)
{
aux = lista;
}
else
{
aux = atras->siguiente;
}
}
else {
atras = aux;
aux = aux->
siguiente;
}
}
return lista;
}
He eliminado el retorno de lista que había
después del free(aux) debido a que queremos seguir recorriendo la lista y el
return cortaría el proceso. En vez de eso, la lista se devuelve al final, por
lo que hasta que no se ha recorrido toda la lista no termina la ejecución.
Borrado completo de una lista.
El caso es simple, deseamos borrar una lista
completa, pero asegurando que toda la memoria quedará libre. El proceso es
sencillo, se utilizan dos auxiliares y se recorre la lista borrando el nodo
anterior a *aux.
{
struct Nodo *aux,
*atras;
aux = lista;
atras=NULL;
while (aux !=
NULL)
{
atras = aux;
aux = aux-> siguiente;
free(atras);
}
}
De ésta forma la lista queda completamente
vacía.
Inserción en una posición de la lista.
A este código le pasa como al del borrado,
nos sirve tanto para inserción en cabeza como en cola.
Para insertar un nuevo elemento dentro de la
lista en una posición cualquiera primero debemos poner el puntero *aux en la
posición que necesitemos, pero vigilando que no sobrepasemos la longitud de la
lista, después es tan sencillo como que el *nuevo-> siguiente apunte a *aux
y el *atras apunte a *nuevo.
El código es el siguiente:
{
struct Nodo *
aux, * atras, * nuevo;
int i=0;
nuevo = malloc(sizeof(struct Nodo));
nuevo->dato1 =
valor;
atras=NULL;
aux=lista;
//para
posicionarnos
while(i < pos && aux != NULL)
{
i++;
atras = aux;
aux = aux-> siguiente;
}
nuevo->
siguiente = aux;
if (atras ==
NULL)
{
lista = nuevo;
}
else
{
atras->siguiente = nuevo;
}
return lista;
}
Conclusiones.
Con esto damos por finalizado el noveno
capítulo del curso básico de C. Las listas con enlace simple dan todavía para
mucho más, no obstante con todos estos ejemplos se puede ir operando
perfectamente con ellas. Los tipos de estructuras dinámicas que se pueden
montar son muy numerosas, pero en un futuro curso de C de nivel intermedio
podremos verlas todas con detenimiento.
Ya sólo falta el último capítulo del curso
básico de C, en el siguiente capítulo veremos un tema que es de práctica
obligatoria a la hora de estudiar un lenguaje de programación: Los ficheros.