tema 20. búsqueda secuencial en ficheros y...

1Diego Gutiérrez

Tema 20. Búsqueda secuencial en ficheros y vectores

2Diego Gutiérrez

En lecciones anteriores se han presentado los mecanismos de definición de ficheros secuenciales y de vectores. Ambos constituyen representaciones algorítmicas válidas del concepto formal de secuencia de datos de un mismo tipo (si bien los vectores tienen un tamaño predefinido que limita la longitud de las secuencias representables). Sobre estas estructuras de datosse han estudiado ya operaciones de recorrido.

En esta lección se considera una nueva clase de problemas: la búsqueda de un determinado elemento de una secuencia, representada bien mediante un vector o mediante un fichero secuencial.

3Diego Gutiérrez

Por qué algoritmos de búsqueda?

4Diego Gutiérrez

5Diego Gutiérrez

Su solución se construirá como un procedimiento parametrizado. Con ello se logra evitar que el usuario de tales operaciones deba conocer la estructura interna de los datos y los detalles sobre cómo se implementan operaciones básicas.

6Diego Gutiérrez

Un problema de búsqueda puede concluir con éxito o fracaso, en función de haber logrado alcanzar el objetivo planteado en el criterio de búsqueda correspondiente. Esta circunstancia habráque tenerla en cuenta a la hora de abordar su resolución.

7Diego Gutiérrez

Índice:Búsqueda secuencial o lineal en un fichero secuencial:

Con garantía de éxitoSin garantía de éxito

Búsqueda secuencial o lineal en una tabla:Con garantía de éxitoSin garantía de éxitoBúsqueda lineal con centinela

8Diego Gutiérrez

En el caso general, no tenemos ninguna garantía sobre la ordenación o no de los elementos sobre los que realizamos la búsqueda…

…una búsqueda que empiece por el primer elemento de la misma es tan eficiente como cualquier otro método

Avanzaremos elemento a elemento hasta que encontremos el buscado o nos quedemos sin más elementos: éxito o fracaso de la búsqueda

http://www.cosc.canterbury.ac.nz/mukundan/dsal/LSearch.html

9Diego Gutiérrez

En general, asociado a cada elemento (tanto en ficheros como en tablas) suele existir un campo relevante que lo distingue y sobre el que basamos la búsqueda

PIN de un estudiante

A este campo se le llama clave

En nuestro contexto:La clave de un dato simple es el propio datoLa clave de un dato estructurado de tipo registro es uno de sus campos

Los algoritmos de búsqueda funcionan comparando la clave de cada uno de los elementos con la que buscamos

10Diego Gutiérrez




11Diego Gutiérrez

Búsqueda secuencial en un fichero:

La clase de problemas que se va a estudiar concierne la búsqueda de uno de los datos de la secuencia almacenada en un fichero talque satisfaga una condición determinada.

En los esquemas algorítmicos que se presentan en este apartado se propone que la satisfacción de la condición de búsqueda pueda ser comprobada mediante la aplicación de la función booleanacondiciónDeBusqueda al valor del dato correspondiente, dato:

condiciónDeBusqueda(dato)

12Diego Gutiérrez

Búsqueda lineal en un fichero secuencial con garantía de éxito

buscarDato1, asume como precondición que el fichero sobre el que se realiza la búsqueda almacena una secuencia que contiene, al menos, un dato que satisface la condición de búsqueda.

La búsqueda no debe extenderse necesariamente hasta que todos los datos del fichero hayan sido leídos, sino que se interrumpirátras leer el primer dato que satisfaga el criterio de búsqueda.

13Diego Gutiérrez

algoritmo buscarDato1 (ES f:tpFichD; ES datoBuscado:tpD){ Pre: La secuencia de datos almacenada en “f” contiene al menos un dato

que satisface la condición de búsqueda.Post: El valor de “datoBuscado” es el del primer dato almacenado en el fichero “f” que satisface la condición de búsqueda }

principioiniciarLectura(f);{ El fichero “f” almacena, al menos, un dato }leer(f,datoBuscado);mientrasQue ¬condiciónDeBúsqueda(datoBuscado) hacer

{ Lee un nuevo dato del fichero “f” }leer(f, datoBuscado);

finMQFin.

14Diego Gutiérrez

Este no es el caso general ya que hay problemas de búsqueda en los que no hay certeza de la existencia del dato que se busca…

…necesitamos un esquema más general que contemple esa posibilidad!

15Diego Gutiérrez

Búsqueda lineal en un fichero secuencial sin garantía de éxito

buscarDato2 incorpora un nuevo parámetro de salida al algoritmo de nombre éxito y de tipo booleano.

La misión de este parámetro es informar si la búsqueda ha tenido éxito, mediante un valor cierto, o en caso contrario, mediante unvalor falso.

En este último caso el valor del parámetro de salida datoBuscado no tiene interés ya que no es portador de información relevante.

16Diego Gutiérrez

algoritmo buscarDato2 (ES f:tpFichero; ES éxito:booleano; ES datoBuscado:tpD)

{ Pre: ---Post: El valor de “éxito” es cierto si y sólo si hay almacenado en el fichero “f”

algún dato que satisface la condición de búsqueda; si tal circunstancia se da, el valor de “datoBuscado” es el del primer dato almacenado en el fichero “f” que satisface la condición de búsqueda }

principioiniciarLectura(f); éxito:=falso;mientrasQue ¬finFichero(f) Y ¬éxito hacer

{ Lee un nuevo dato del fichero “f” y verifica si se trata del dato buscado }leer(f,datoBuscado);éxito:=condiciónDeBúsqueda(datoBuscado);

finMQFin.

17Diego Gutiérrez

Búsqueda en ficheros secuenciales

Búsqueda lineal en ficheros secuenciales ordenados:

Si el fichero sobre el que se efectúa la búsqueda está ordenadocon respecto a la condición de búsqueda, el problema de la búsqueda se puede resolver de un modo más eficiente

No será necesario recorrer todos los datos: la condición de terminación viene impuesta por la aparición del dato buscado, o por la aparición de un dato que indique que ya no va a ser posible encontrar el dato buscado (varía con respecto a la anterior)

18Diego Gutiérrez

Búsqueda en ficheros secuenciales

Ejemplo: Dada la estructura de datos definida abajo, escribir unprocedimiento que liste los ingresos correspondientes a una persona definida por su DNI, suponiendo que las personas están ordenadas por su DNI.

Tipostipo_reg = registro

ingresos, deuda : real;clave : entero;información : tpInfo

freg;Variables

tipo_fich = fichero de tipo_reg;

19Diego Gutiérrez

algoritmo buscarDato3(ES f:tipo_fich; E miclave:entero; ES reg:tipo_reg; ES éxito:booleano)

{Pre: El fichero está ordenado por orden creciente de clavePost: El valor de “éxito” es cierto si y sólo si hay almacenado en el fichero “f” algún dato que satisface la condición de búsqueda; si tal circunstancia se da, el valor de “reg” es el del primer dato almacenado en el fichero “f” que satisface la condición de búsqueda }

variables finBúsqueda:booleano;principioiniciarLectura(f);finBúsqueda:= falso;mientrasQue ¬finFichero(f) AND ¬finBúsqueda hacer

leer(f,reg);finBúsqueda:= (reg.clave>=miclave)

fmq{ Se discrimina si ha habido éxito en la búsqueda }si finBúsqueda entonces

éxito:=reg.clave=miclave ;sino éxito := falso

fsiFin.

20Diego Gutiérrez

Determinar si los datos almacenados en un fichero secuencial están ordenados de menor a mayor según la relación de orden “≤”.

1 2 5 5 14 17 13 19 23

21Diego Gutiérrez


1 2 5 5 14 17 13 19 23

22Diego Gutiérrez


1 2 5 5 14 17 13 19 23 24 31 33 67 79…

23Diego Gutiérrez


El problema se puede plantear como un problema de búsqueda

24Diego Gutiérrez


El problema se puede plantear como un problema de búsquedadel primer par de datos consecutivos que no respeten el criterio de ordenación: gestión los valores de los pares de datos consecutivos (penúltimo y último) de una secuencia

En el caso de que tal búsqueda no tenga éxito se concluirá que los datos del fichero están ordenados: búsqueda sin garantía de éxito

25Diego Gutiérrez

algoritmo ordenado (ES f:tpFichero; ES estáOrdenado:booleano){ Pre: ---Post: El valor de “estáOrdenado” es cierto si y sólo si los datos almacenados en el

fichero “f” están ordenados por “≤” }variables

penúltimo,último: tpD;principio

iniciarLectura(f);si ¬finFichero(f) entonces

leer(f,último); estáOrdenado:=cierto;mientrasQue ¬finFichero(f) Y estáOrdenado hacer{ Lee un nuevo dato del fichero “f” y verifica si mantiene la ordenación }

penúltimo:=último; leer(f,último);estáOrdenado:=(penúltimo≤último);

finMQsi_no

estáOrdenado:=cierto;finSi

Fin.

26Diego Gutiérrez




27Diego Gutiérrez

Acceso indexado!

28Diego Gutiérrez

Planteamiento del problema:

Búsqueda de un dato d que satisfaga un determinado criterio de búsquedaEl dato está almacenado en una tabla de índice único.La condición de búsqueda pueda ser determinada mediante una función booleana, condiciónDeBúsqueda(d) que devuelve un valor cierto si y sólo si el dato d satisface la condición.Trabajamos con datos de tipo tpTabla que responden a la siguiente definición:

constantesn = ... ; { Dimensión de las tablas }

tipostpÍndice = 1..n; { Índices de las tablas }tpTabla = tabla[tpÍndice] de tpDato;

29Diego Gutiérrez

Búsqueda secuencial en una tabla con garantía de éxito:

Al igual que con ficheros, se asume como precondición que la tabla sobre la que se realiza la búsqueda contiene, al menos, un dato que satisface la condición de búsqueda.

La búsqueda no debe extenderse necesariamente hasta que todos los datos de la tabla hayan sido leídos, sino que se interrumpirátras leer el primer dato que satisfaga el criterio de búsqueda.

30Diego Gutiérrez

algoritmo buscarEnTabla (E T:tpTabla; ES datoBuscado:tpDato){ Pre: existe en “T” al menos un dato que satisface la condición de búsqueda

Post: el valor de “datoBuscado” es igual a uno de los datos almacenados en “T” que satisfacen la condición de búsqueda }

variablesíndice: tpÍndice;

principio{ La búsqueda empieza por el índice menor }índice:=1;{ Realiza una búsqueda lineal en T }mientrasQue ¬condiciónDeBúsqueda(T[índice]) hacer

índice:=índice+1;finMQ{ Se satisface condiciónDeBúsqueda(T[índice]) }datoBuscado:=T[índice];

Fin.

31Diego Gutiérrez

Búsqueda secuencial en una tabla sin garantía de éxito:

algoritmo buscarEnTabla (E T:tpTabla; ES éxito:booleano; ES datoBuscado:tpDato){ Pre: n≥1Post: el valor de “éxito” es cierto si y sólo si alguno de los datos almacenados en “T”

satisface la condición de búsqueda; en tal caso el valor de “datoBuscado” es igual a uno de ellos y, en caso contrario, su valor queda indefinido }

variablesíndice: tpÍndice;

principio{ La búsqueda empieza por el índice menor }índice:=1;{ Realiza una búsqueda lineal en T }mientrasQue ¬(índice=n) Y ¬condiciónDeBúsqueda(T[índice]) hacer

índice:=índice+1;finMQ

{ Discrimina si ha habido éxito en la búsqueda }si condiciónDeBúsqueda(T[índice])

entonces datoBuscado:=T[índice]; éxito:=cierto;si_no éxito:=falso;

finSiFin.

32Diego Gutiérrez

El algoritmo, tal como expresa su precondición (Pre: n>=1), sólo es válido para tablas que almacenen al menos un dato.

¿Cómo podemos evitar esa exigencia en búsquedas sin garantía de éxito?

Forzando esa garantía!

Búsqueda con centinela

Dos versiones: 1. Modificando la estructura de datos de partida2. Sin modificarla

33Diego Gutiérrez

Algoritmo clásico de búsqueda lineal con centinela

Ampliación de la tabla con un elemento adicional en su última posición [índice n+1]

constantesn = ... ;

tipostpÍndiceAmpliado = 1..n+1;tpTabla = tabla[tpÍndiceAmpliado] de tpDato;

constantesn = ... ;

tipostpÍndice = 1..n; tpTabla = tabla[tpÍndice]

de tpDato;

34Diego Gutiérrez

En el elemento añadido a la tabla (T[n+1]) se almacenará un dato centinela de tipo tpDato que satisfaga la condición de búsqueda condiciónDeBúsqueda(centinela).

…Lo hemos convertido en un algoritmo de búsqueda lineal con garantía de éxito: el centinela constituye la garantía del éxito de la búsqueda!

Una vez terminada la búsqueda (con éxito, claro): ver si el dato encontrado está entre los n primeros o es el centinela

35Diego Gutiérrez

algoritmo buscarEnTabla (E T:tpTabla; ES éxito:booleano; ES datoBuscado:tpDato){ Pre: existe un dato “CENTINELA” que satisface condiciónDeBúsqueda(CENTINELA)

Post: el valor de “éxito” es cierto si y sólo si alguno de los n-primeros datos almacenados en “T” satisface la condición de búsqueda; en tal caso el valor de “datoBuscado” es igual al primero de ellos y, en caso contrario, su valor queda indefinido }

variablesíndice:tpÍndice;

principioT[n+1]:=CENTINELA; { Almacena en T[n+1] un valor ”centinela” }índice:=1;{ Realiza una búsqueda lineal en T }mientrasQue ¬condiciónDeBúsqueda(T[índice]) hacer

índice:=índice+1;finMQ{ Discrimina si ha habido éxito en la búsqueda }si índice≤n

entonces datoBuscado:=T[índice]; éxito:= cierto;si_no éxito:= falso;

finSiFin.

36Diego Gutiérrez

¿Y si no podemos alterar los datos originales, o no conocemos “a priori” el valor de un dato que satisfaga la condición de búsqueda? ¿No podemos usar una idea similar?

constantesn = ... ;

tipostpÍndice = 1..n; tpTabla = tabla[tpÍndice]

de tpDato;

Esto se logra mediante la variable limiteÍndice que establece inicialmente el límite de la búsqueda en el elemento centinela virtual de la posición n+1 y que, en caso de alcanzar el éxito enla búsqueda, toma el valor del índice en la tabla del dato buscado.

37Diego Gutiérrez

algoritmo buscarEnTabla (E T:tpTabla; S éxito:booleano; S datoBuscado:tpDato){ Pre: ---

Post: el valor de “éxito” es cierto si y sólo si alguno de los datos almacenados en “T” satisface la condición de búsqueda; en tal caso el valor de “datoBuscado” es igual a uno de ellos y, en caso contrario, su valor queda indefinido }

tipostpÍndiceAmpliado = 1..n+1;

variablesíndice,limiteÍndice:tpÍndiceAmpliado;

principioíndice:=1;{ Realiza una búsqueda lineal con centinela virtual }limiteÍndice:=n+1;mientrasQue ¬(índice=limiteÍndice) hacer

si condiciónDeBúsqueda(T[índice])entonces limiteÍndice:=índice;si_no índice:= índice+1;

finSifinMQ{ Discrimina si ha habido éxito en la búsqueda }si índice≤n

entonces datoBuscado:=T[índice]; éxito:= cierto;si_no éxito:= falso;

finSiFin.

38Diego Gutiérrez

Y por qué hacemos todo esto???

Evitar la exigencia de que la búsqueda se plantee sobre una tabla no vacía de datos.

En búsqueda sin garantía de éxito (sin centinela), teníamos:

mientrasQue ¬(índice=n) Y ¬condiciónDeBúsqueda(T[índice]) hacer

Con centinela (real o “ficticio”):

mientrasQue ¬condiciónDeBúsqueda(T[índice]) hacer

39Diego Gutiérrez

Conclusiones:

Búsqueda lineal en tablas ordenadas: mismo razonamiento que para ficheros…… pero si la tabla está ordenada: nuevos métodos más eficientes!

Búsqueda dicotómica

tema 20. búsqueda secuencial en ficheros y...

Documents