View
7
Download
1
Category
Preview:
DESCRIPTION
Localizacion Rapida de Datos en Un Archivo
Citation preview
Marzo 2014.M. en C. Violeta del Rocío Becerra Velázquez.
Localización rápida de datos en un archivo.
Búsqueda por conjetura.
• El algoritmo de búsqueda binaria localiza una llave en una lista, dividiéndola a la mitad, y formando una lista nueva y más pequeña a partir de la mitad que contiene la llave. Este proceso continúa hasta que el elemento seleccionado sea la llave que se buscaba.
Búsqueda por conjetura
Nombre
Adriana
Ángel
Carlos
Fernando
Gabriel
Isabel
Julián
Luisa
Marcia
Tomas
Se divide la lista a la mitadNombre
Itzel
Julián
Luisa
Marcia
Tomas
Nombre
Adriana
Andrea
Carlos
Fernando
Gabriel
Llave a buscar: Julián
Búsqueda por conjetura
Nombre
Itzel
Julián
Luisa
Marcia
Tomas
Nombre
Adriana
Andrea
Carlos
Fernando
Gabriel
Julián < Gabriel
Compara la llave a buscar y se queda con la nueva lista mas pequeña
Búsqueda por conjetura
Nombre
Itzel
Julián
Luisa
Marcia
Tomas
Nombre
Marcia
Tomas
Julián < Luisa
Se repite la operación hasta que se encuentra la llave o se llega al final.
Nombre
Itzel
Julián
Luisa
Clasificación de un archivo en memoria RAM
1. Leer los registros del archivo de entrada en el arreglo REGISTROS.
2. Extraer las llaves, construyendo el arreglo NODOSLLAVE.
3. Construir un arreglo INDICE de subíndices de NODOSLLAVE[] y REGISTROS[]
4. Ordenar INDICE[] con base en los valores NODOSLLAVE[]
5. Usar el nuevo INDICE[] ordenado para transcribir REGISTROS[] al nuevo archivo, conforme al orden clasificado.
Registros de datos después de cargar el archivo en el arreglo REGISTROS
REGISTROS
Becerra | Violeta | Florida 34….
Marin | Carlos | Magenta 893 ….
Velázquez | César | Cantaros 232 ….
Marino | Mario | Reforma 21….
…….
Andrade | Jorge | Huerta 89….
Vista del arreglo de llaves y del arreglo de registros.
REGISTROS
Becerra | Violeta | Florida 34….
Marin | Carlos | Magenta 893 ….
Velázquez | César | Cantaros 232 ….
Marino | Mario | Reforma 21….
…….
Andrade | Jorge | Huerta 89….
LLAVE NRR
BECERRA VIOLETA 1
MARIN CARLOS 2
VELAZQUEZ CESAR 3
MARINO MARIO 4
…….
ANDRADE JORGE k
Vista del arreglo de apuntadores, del arreglo de llaves y del arreglo de
registros.
REGISTROS
Becerra | Violeta | Florida 34….
Marin | Carlos | Magenta 893 ….
Velázquez | César | Cantaros 232 ….
Marino | Mario | Reforma 21….
…….
Andrade | Jorge | Huerta 89….
LLAVE
BECERRA VIOLETA
MARIN CARLOS
VELAZQUEZ CESAR
MARINO MARIO
…….
ANDRADE JORGE
1
2
3
4
k
Vista del arreglo de apuntadores, del arreglo de llaves y del arreglo de registros, después
de la clasificación.
REGISTROS
Becerra | Violeta | Florida 34….
Marin | Carlos | Magenta 893 ….
Velázquez | César | Cantaros 232 ….
Marino | Mario | Reforma 21….
…….
Andrade | Jorge | Huerta 89….
LLAVE
BECERRA VIOLETA
MARIN CARLOS
VELAZQUEZ CESAR
MARINO MARIO
…….
ANDRADE JORGE
k
1
2
4
3
Limitaciones de la Búsqueda Binaria y de la Clasificación en
Memoria RAM.
• Requiere de más de uno o dos accesos.
• Mantener un archivo ordenado es muy costoso.
• Una clasificación en Memoria RAM funciona solo con archivos pequeños.
Clasificación por Llave
• Se denomina clasificación por marca, y es una modificación de la clasificación en memoria RAM. La diferencia es que no se leen los registros reales en memoria; se leen sólo las llaves canónicas.
En Memoria RAM
REGISTROS
Becerra | Violeta | Florida 34….
Marin | Carlos | Magenta 893 ….
Velázquez | César | Cantaros 232 ….
Marino | Mario | Reforma 21….
…….
Andrade | Jorge | Huerta 89….
LLAVE
BECERRA VIOLETA
MARIN CARLOS
VELAZQUEZ CESAR
MARINO MARIO
…….
ANDRADE JORGE
1
2
3
4
k
En Almacenamiento Secundario
Indirección
• Termino que describe el proceso de referir información de manera indirecta, mediante el uso de una serie de apuntadores u otros tipos de localizadores.
Registro Fijo
• Se dice que un registro esta fijo cuando existen otros registros o estructuras de archivos referidas a él mediante su posición física. Está fijo en el sentido de que no se tiene la libertad de alterar la posición física del registro, ya que al hacerlo se destruiría la validez de las referencias físicas al registro. Estas referencias se convierten en apuntadores suspendidos inútiles.
Recommended