UNIVERSIDAD PRIVADA TELESUP

BSQUEDA EN UNA LISTA ENLAZADA

Sea LISTA una lista enlazada, almacenada en memoria. En esta seccin discutimos dos algoritmos de bsqueda que localizan la posicin del nodo (LUG) en el cual un elemento dado (ELEMENTO) aparece por primera vez en la lista. El primer algoritmo no necesita que la lista este ordenada, mientras que el segundo si lo exige.

Si ELEMENTO es un valor de clave y buscamos en el archivo para encontrar el registro que lo contiene, este solo puede aparecer una vez en la lista.

Lista no ordenadas

Supongamos que los datos de lista no estn ordenados (necesariamente). En este caso podremos localizar ELEMENTO sin ms que recorrer LISTA utilizando el puntero PTR y comparando ELEMENTO con el contenido INFO [PTR] de cada nodo. Cada vez que actualicemos PTR mediante la asignacin PTR: = ENLACE [PTR], necesitamos dos comprobaciones. Primero necesitamos ver si hemos alcanzado el final de la lista, es decir comprobamos si PTR = NULO, si no, entonces comprobamos si INFO [PTR] = ELEMENTO.

Las dos comprobaciones no podemos realizarlas simultneamente, puesto que si PTR = NULO no existir INFO [PTR]. De acuerdo con esto utilizamos la primera comparacin para controlar la ejecucin de un ciclo y realizamos la segunda comparacin dentro de este.

Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

LISTA es una lista enlazada almacenada en memoria. el algoritmo encuentra la posicin LUG del nodo donde ELEMENTO aparece por primera vez en lista y devuelve LUG = NULO.

1. PTR: = COMIENZO.

2. repetir paso 3 mientras PTR != NULO:

3. si ELEMENTO = INFO[PTR], entonces: LUG: = PTR y salir.

4. si no: PTR: = ENLACE [PTR]. [PTR apunta ahora al nodo siguiente].

5. [final de la estructura condicional].

6. [final del ciclo del paso 2].

7. [la busqueda es fallida]. LUG: = NULO.

8. salir

Lista ordenada

Supongamos que los datos de LISTA estn ordenados. De nuevo buscamos ELEMENTO en la lista recorriendo la misma utilizando una variable puntero y comparando ELEMENTO con el contenido de INFO[PTR] nodo a nodo. en este caso, sin embargo, podremos finalizar la bsqueda una vez que ELEMENTO sea mayor que INFO[PTR]. Algoritmo: BUSQ(INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

LISTA es una lista ordenada que se encuentra en memoria. El algoritmo encuentra la posicin LUG del nodo donde se encuentra por primera vez ELEMENTO o bien devuelve LUG = NULO.

1. PTR:= COMIENZO.

2. repetir paso 3 mientras PTR != NULO:

3. si ELEMENTO < INFO[PTR], entonces:

4. PTR: = ENLACE [PTR]. [PTR apunta al siguiente nodo].

5. si no, si ELEMENTO = INFO[PTR], entonces:

6. LUG = PTR y salir. [la busqueda es satisfactoria].

7. si no: LUG: = NULO y salir. [ELEMENTO es mayor que INFO[PTR]].

8. [final de la estructura condicional]

9. [final del ciclo del paso 2]

10. LUG: = NULO.

11. salir.

ELIMINACIN DEL NODO SUCESOR DE UNO DETERMINADOSea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de LISTA el nodo N que ocupa el lugar LUG y que conocemos el lugar LUGP del nodo que precede a N en la lista o bien si el nodo N es el primer LUG = NULO. El algoritmo siguiente elimina N de la lista. Algoritmo: BOR (INFO, ENLACE, COMIENZO, DISP, LUG, LUGP)

El algoritmo elimina de la lista el nodo N que ocupa la posicin LUG, siendo LUGP la posicin del nodo que precede a N o bien LUGP = 0 si N es el primero de la lista.

1. si LUGP = NULO. Entonces:

2. COMIENZO: = ENLACE[COMIENZO]. [Elimina el primer nodo].

3. Si no:

4. ENLACE[LUGP]: = ENLACE[LUG]. [Elimina el nodo N].

5. [Final de la estructura condicional].

6. [Devolvemos el nodo a la lista DISP].

7. ENLACE[LUG]: = DISP Y DISP: = LUG.

8. Salir.CURSO: ALGORITMIA Y ESTRUCTURA DE DATOS

CARRERA: INGENIERIA DE SISTEMAS E INFORMATICA