1
Búsqueda secuencial en tabla ordenada.
Estructura de datos
Estructura de datos
2 Búsqueda secuencial
La búsqueda secuencial es la técnica más simple para buscar un elemento en un arreglo. Consiste en
recorrer el arreglo elemento a elemento e ir comparando con el valor buscado (clave). . La
búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún
registro con esa llave. Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas.
Estructura de datos
3
Si el arreglo no está en ningún orden en particular, existe la misma probabilidad de que el valor se encuentra ya sea en el primer elemento, como en el último. Por lo tanto, en promedio, el programa tendrá que comparar el valor buscado con la mitad de los elementos del arreglo.
Estructura de datos
4
Búsqueda secuencial
Ejemplo: Vectores no ordenados
5
Llenar un vector de 9 datos
1 2 3 4 5 6 7 8 9
Dato encontrado en las posiciones
Dato a buscar
Llave N =
0 1 2 3 4 5 6 7 83 5 18 3 5 16 4 22 5
5
1 2 3 4 5 6 7 83 5 18 3 5 16 4 22 5
Estructura de datos
Estructura de datos
6Búsqueda secuencial Lineal
Ejemplo: Tabla no ordenada
7 40534 Mauricio Villalobos 7 8 8
Código Nombre Dirección Notas
1 2 3
98034 Lorena Castillo 10 7 8
12590 Carlos Orellana 6 5 9
45633 Karla Pérez 5 10 10
22349 Julio Martínez 7 7 8
Dato a buscar
Mauricio Villalobos 7 8 8
Lorena Castillo 10 7 8
Carlos Orellana 6 5 9
Karla 5 10 10
Julio Martínez 7 7 8
=45633
40534
98034
12590
22349
45633 Pérez
Dato encontrado
Estructura de datos
Estructura de datos
8 Desventaja de búsqueda secuencial lineal.
El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.
Este método de búsqueda es muy lento, pero si los datos no están en orden, es el único método que puede emplearse para hacer las búsquedas. Para poder agilizar la búsqueda en arreglos se implementan las siguientes mejoras:
Estructura de datos
9 Mejoras en la eficiencia de la búsqueda secuencial
Muestreo de acceso: Este método consiste en
observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas
Movimiento hacia el frente:
Este esquema consiste en que la lista de registros se reorganice dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que él.
Estructura de datos
10
Transposición:
Consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre más accesos tenga el registro, más rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere más tiempo de actividad para reorganizar al conjunto de registros..
Ordenamiento: Ordenar los registros en base al
valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.
Estructura de datos
11 Búsqueda en tabla ordenada.
Los métodos de búsquedas presentan un inconveniente, cuando no se encuentra el elemento buscado, pues el recorrido en tablas de mayor
tamaño consume más tiempo, para ello, un método simple consiste en colocar los elementos dentro de la tabla de acuerdo con algún orden sobre sus llaves, de esta manera, cuando se busca un elemento, es posible identificar la posición que debería ocupar la llave, y si no se
localiza en ella, es porque no se encuentra en la tabla.
El ordenamiento de las llaves exige que, dados los valores de dos llaves y , se cumplan una y solo una de las siguientes condiciones (Propiedad
de tricotomía sobre los valores de las llaves ):
la ley de tricotomía es una propiedad de algunos conjuntos ordenados, por la cual todos sus elementos son comparables entre sí.
Estructura de datos
12 Búsqueda exhaustiva
Se puede recorrer la tabla desde uno de sus extremos, hasta encontrar la posición en que debería estar la llave buscada, de acuerdo al orden que mantenga la tabla.
13 1234 Mauricio Villalobos 7 8 8
Código Nombre Dirección Notas
1 2 3
1422 Lorena Castillo 10 7 8
3245 Carlos Orellana 6 5 9
4567 Karla Pérez 5 10 10
4606 Julio Martínez 7 7 8
Dato a buscar
Mauricio Villalobos 7 8 8
Lorena Castillo 10 7 8
Carlos Orellana 6 5 9
Karla 5 10 10
Julio Martínez 7 7 8
=3245
1234
1422
3245
4606
4567 Pérez
Dato encontrado
Estructura de datos
1
2
3
5
4
Posición
3
14 Búsqueda con centinela en tablas ordenadas.
Una vez más, se puede eliminar la condición compuesta de control del ciclo, colocando la llave buscada en uno de los extremos de la tabla, que no se utilice normalmente para almacenar los datos.
Estructura de datos
Luego se compara si el índice retornado corresponde al valor buscado.
Estructura de datos
15
Búsqueda Secuencial Indexada
Estructura de datos
16 Búsqueda Secuencial Indexada
Registros
Un archivo es un conjunto de datos en una colección de registros, que constan de diferentes entidades de nivel más bajo denominadas campos.
17 Búsqueda Secuencial Indexada
Estructura de datos
Registros Un registro es una colección de campos lógicamente relacionados un
ejemplo puede ser la información de un libro que contiene los campos de título, autor, editorial, fecha de edición, entre otros.
18 Búsqueda Secuencial Indexada
Estructura de datos
Campo clave Una clave es un campo que identifica al registro y lo diferencia de otros
registros. Normalmente los registros se organizan según un campo clave.
Ej. son números de identificación, nombres; en general puede ser una clave de cualquier campo que admita relaciones de comparación.
19 Búsqueda Secuencial Indexada
Estructura de datos
Partes del Archivo S.I.
La clave se asocia con la dirección (posición) del registro de datos en el archivo principal.
Área de datos. Contiene los registros de datos en forma secuencial, sin dejar huecos intercalados.
Área de índices. Es una tabla que contiene la clave identificativa y la dirección de almacenamiento.
20 Búsqueda Secuencial Indexada
Estructura de datos
Indice Es una referencia que nos permite obtener de forma automática la
ubicación de la zona del archivo físico donde se encuentra el registro buscado. Este permite localizar un registro por medio de su clave sin recorrer previamente todos los que le preceden.
Cada archivo S.I. consta de dos archivos el de índices y el de datos, el primero es secuencial y contiene las claves del último registro de cada bloque físico del archivo y la dirección de acceso al primer registro del bloque y en el segundo, los registros de datos, clasificados en orden ascendente por el campo clave.
21 Búsqueda Secuencial Indexada
Estructura de datos
22 Búsqueda Secuencial Indexada
Estructura de datos
Ventajas Importantes
Rápido acceso, y que la gestión de archivos se encarga de relacionar la posición de cada registro con su contenido mediante la tabla de índices.
Inconveniente
Es el espacio adicional para guardar el área de índices.
23
Integrantes
Estructura de datosESTRUCTURA DE DATOS NOV -2013
Chavarría Segovia, Edwin Geovanny
Hernández Álvarez, José Nehemías
Jiménez Álvarez, Jackeline Elizabeth
Membreño Cañas, Eduardo Leonel
Romero, Lucio Alberto
Top Related