Listas

Listas enlazadas

14.3.7. Búsqueda de un elemento

I

Dado que una función en C puede devolver un puntero, el algoritmo que sirva para localizar un elemento en una lista enlazada puede devolver un puntero a ese elemento.

5.75

41

101.43

La función utiliza una variable puntero denominada indice que va recorriendo la lista nodo a nodo. Mediante un bucle, Indice apunta a los nodosde la lista de modo que si se encuentra el nodo buscado, se devuelve un puntero al nodo buscado con la sentencia de retorno (return); en el caso de no encontrarse el nodo buscado la función debe devolver NULL (return NULL)
Código C
Nodo* (Nodo" cabeza, destino) cabeza: puntero de cabeza de una lista enlazada. destino: dato que se busca en la lista. indice: valor de retorno, puntero que apunta alprimer nodo q u e contiene el destino (elemento buscado); si no existe el nodo, se devuelve puntero nulo.
*/

Nodo "indice; for (indice cabeza; indice NULL; indice indice siguiente)

if (destino índice return indice;

dato)

Ejemplo 14.5 En este ejemplo se escribe una lista enlazada. para encontrar la dirección de un nodo dada su posición en

Análisis El nodo o elemento se especificapor su posición en la lista; para ello se considera posición la correspondiente al nodo de cabeza, posición 2, la correspondiente siguiente nodo, y así sucesivamente. El algoritmo de búsqueda del elemento comienza con el recorrido de la lista mediante un puntero indice que comienza apuntando al nodo cabeza de la lista. Un bucle mueve el indice hacia adelante el número correcto de sitios (lugares). Acada iteración del bucle se mueve el puntero indice un nodo hacia adelante. El bucle termina cuando se alcanza la posición deseada e indice apunta al nodo correcto. El bucle también se puede terminar si indice apunta a NULL,lo que indicará que la posición solicitada era más grande que el número de nodos de la lista.
Código C
Nodo* "cabeza, size-t posicion) / * El programa que llame a estafunción ha de incluir biblioteca (para implementar tipo size-t)
*/

Nodo "indice;

Programación en

Metodología, algoritmos y estructura de datos

size-t i ; if ( O posicion) / * posición ha de ser mayor que O * / return NULL; indice cabeza; for 1 posición) (indice NULL) ; indice = indice siguiente; return indice;

I

14.3.8. Supresión de un nodo en una lista
La operación de eliminar unnodo de una lista enlazada supone enlazar el nodo anterior con el nodo siguiente al que se desea eliminar y liberar la memoria que ocupa. El algoritmo para eliminar un nodo que contiene un dato se puede expresar en estos pasos:

1. Búsqueda del nodo que contiene el dato. Se ha de tener la dirección del nodo a eliminar y la dirección del anterior. 2. El puntero siguiente del nodo anterior ha deapuntar al siguiente del nodo a eliminar. 3. En caso de que el nodo a eliminar sea el primero, cabeza,se modifica cabeza para que tenga la dirección del nodo siguiente. 4. Por último, se libera la memoria ocupada por el nodo.
A continuación se escribe una función que recibe la cabeza de la lista y el dato del nodo que se quiere borrar.
void eliminar (Nodo** cabeza, item entrada)

Nodo* actual,"anterior; int encontrado O;
actual *cabeza; anterior NULL; / * Bucle de búsqueda while (!encontrado)) encontrado = (actual->dato if (!encontrado) entrada);

anterior = actual; siguiente; actual = actual

I
/ * Enlace de nodo anterior con siguiente * / if (actual ! = NULL)

,
/ * Se distingue entre que el nodo sea el cabecera o del

resto de la lista * /

if (actual
"cabeza*cabeza) actual->siguiente; siguiente = actual ->siguiente

I
else anterior

Listas enlazadas

Ejercicio 14.2

Se desea crear una lista enlazada de números enteros ordenada. La lista va estar organizada de tal forma que el nodo cabecera tenga el elemento, así en orden creciente los demás nodos. creada la lista, se recorre escribir datos por pantalla.

Análisis La función añade los nuevos...