Compartir entrada

jueves, 13 de junio de 2013

Curso básico de C 9/10: Listas dinámicas (II)

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.

Curso básico de C 9/10: Listas dinámicas (II)
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.

¿Qué otras operaciones con listas se te ocurren?

 
Google+