Diccionario, - Tabla de búsqueda_lineal (tabla look-up) - estructura de datos La tabla de búsqueda_lineal economiza almacenamiento a expensas de la efectividad o velocidad de acceso a la tabla. Consiste en almacenar de forma consecutiva cada elemento con su clave. Y para encontrar un elemento de la tabla se iría analizando la clave hasta que coincidiera, realizándose a continuación la operación solicitada. Por ejemplo, en el caso del centro escolar anterior se utilizaría, como clave del alumno un número identificativo (por ejemplo el número de matrícula, el DNI si es posible, etc.) único para cada alumno, que se incorporaría con el nombre y apellidos y otra información de interés del alumno. TABLA LINEAL DE ALUMNOS 24365 Alonso Fernández, Javier 23200 Alvarez Martínez, Luisa … … 32200 Zuazu Pérez, Fernando 34405 Bustos Soto, María El acceso a un determinado alumno consistiría en ir comparando el número identificativo del alumno con su clave en la tabla hasta encontrarlo. Por ejemplo, si se solicitan los datos del alumno «32 200», se entraría por el principio de la tabla y se compararía este valor con las claves 24 365, 23 200, …, hasta encontrar la 32 200 que corresponde al alumno Zuazu Pérez, Fernando. Importa notar la simplicidad que presenta añadir nuevos alumnos a la tabla; bastará con incluirles en la primera posición vacía de la tabla. El dar de baja un alumno consistiría simplemente en poner a cero la clave e información de ese elemento de la tabla. Como se ve, el hecho de que las inserciones se realicen en cualquier punto de la tabla que esté vacío produce una tabla que no tiene ningún orden en sus claves, hecho que retarda mucho la búsqueda. La función que trata una tabla de búsqueda_lineal, como la que se acaba de describir, tendría la siguiente codificación: búsqueda_lineal (tabla_centro, operación, clave, información): Inicio_búsqueda_lineal Si operación=1 (búsqueda), 2 (actualización), 3 (eliminación) ó 4 (inserción) Entonces I=1 T= Falso Mientras (I£longitud de la tabla) y (T=Falso) Si (tabla_centro [I,1]=clave) o (tabla_centro [I,1]=0) Entonces Si tabla_centro [I,1]= clave Entonces Si operación=1 // búsqueda Entonces información=tabla_centro [I,2] Si no Si operación=2 // actualización Entonces tabla_centro [I,2]= información Si no Si operación=3 // eliminar Entonces tabla_centro [I,1]=tabla_ centro [I,2]=0 Si no // inserción Mostrar “error. elemento ya insertado” Retorna 1 Fin_si Fin_si Fin_si T= Cierto Si no Si operación=4 //inserción Entonces tabla_centro [I,1]= clave tabla_centro [I,2]= información T= Cierto Fin_si Fin_si Si no I=I+1 Fin_si Fin_mientras Si T= Falso Entonces Mostrar “error.-elemento no encontrado” Retornar 2 Si no // operación correcta Retorna 0 Fin_si Si no Mostrar “Operación no implementada” Retornar 3 Fin_si Fin_búsqueda_lineal La función búsqueda_lineal tiene los mismos cuatro argumentos que la de acceso directo descrita anteriormente. — La tabla_centro es, en este caso, una matriz de dos dimensiones, y vendrá definida como: tabla_centro: matriz [1…205] [2] de strings de caracteres — Operación, señala la operación a realizar en la tabla: 1. Se busca un elemento y se obtiene su información (nombre y apellidos). 2. Se actualiza la información del elemento. 3. Se elimina un elemento de la tabla. Se pone su clave e información a cero. 4. Se inserta (añade) un alumno a la tabla. Recordar que la inserción se realiza en el primer hueco (con clave e información a cero) que tenga la tabla. otro valor. Es una operación errónea, no existe. — Clave. Es el número identificativo de cada alumno, y ocupa la primera columna de la tabla. — Información. Es el nombre y apellidos de cada alumno y ocupa la segunda columna de la tabla. Al igual que en el caso del acceso _directo, si la operación es de búsqueda (1) el campo información recibe el contenido de la «tabla_centro»; si es de actualización (2) el valor de información se incorpora a la «tabla_centro», y si es de inserción (4) el valor de la clave y de información pasan a la «tabla_centro». Durante la operación de eliminación (3), el contenido de información no tiene ninguna relevancia. La función búsqueda_lineal recibe estos cuatro argumentos, y si la operación es una búsqueda (1), actualización (2), eliminación (3) o inserción (4), empieza a localizar la clave desde el principio de la «tabla_centro» (I=1) hasta el final de la tabla (I_longitud de la tabla). Si encuentra al elemento clave, realiza la operación solicitada si el valor de la operación es una búsqueda, actualización o eliminación del elemento. En el caso de que la operación sea una inserción, muestra un mensaje de «error.-elemento ya insertado» ya que al existir la clave quiere decir que en esa posición está ya el alumno por lo que no se puede volver a insertar ese alumno, y finaliza la ejecución de la función retornando un 1. Si encuentra una clave vacía (existe un hueco) y la operación es una inserción, entonces coloca en esa posición el valor de la clave y de la información de un nuevo alumno (tabla_centro [I, 1]= clave, y tabla_centro [I, 2]= información), y finaliza el proceso haciendo T= Cierto. Si en esa posición de la tabla no encuentra el elemento clave, pasa a la siguiente fila de la tabla (I=I+1) para volver a repetir las mismas operaciones. Si alcanza el final de la tabla sin encontrar el elemento buscado, entonces muestra el mensaje de «error- elemento no encontrado», y finaliza la ejecución de la función retornando un 2. Por último, si la operación solicitada no es una búsqueda, actualización, eliminación o inserción de un alumno, muestra el mensaje «operación no implementada» y finaliza la ejecución retornando un 3. Y si la operación se ha realizado correctamente entonces retorna un 0. Pero ¿para qué sirve el valor de retorno que devuelve la función? Pues, simplemente para comunicar al programa principal, que utiliza esta función, qué ha ocurrido durante el proceso de búsqueda. Por ejemplo, un programa principal que utilice esta función sería el siguiente: // Buscar elementos de una tabla y visualizarlos en pantalla Inicio tabla_centro: matriz [1..205] [2] de strings de caracteres Mientras haya_operaciones Mostrar en pantalla: ¿ Indique la operación que desea realizar, y para finalizar teclee un 0 ? Leer operación Si operación=0 Entonces Mostrar “Fin de la búsqueda” Stop Si no Si operación=1 // búsqueda Entonces Leer clave búsqueda_lineal (tabla_centro, operación, clave, información) Si el retorno=0 Entonces Mostrar “búsqueda realizada:” clave e información Si no Mostrar “la búsqueda de la clave no se ha podido realizar” Fin_si Si no Si operación=2 // actualizar Entonces Leer clave e información búsqueda_lineal (tabla_centro, operación, clave, información) Si el retorno=0 Entonces Mostrar “actualización realizada.” Si no Mostrar “la actualización de la clave no se ha podido realizar” Fin_si Si no Si operación=3 // eliminación Entonces Leer clave búsqueda_lineal (tabla_centro, operación, clave, información) Si retorno=0 Entonces Mostrar “se ha eliminado el alumno”, clave Si no Mostrar “la eliminación de la clave no se ha podido realizar” Fin_si Si no Si operación=4 // inserción Entonces Leer clave e información búsqueda_lineal (tabla_centro,operación, clave, información) Si el retorno=0 Entonces Mostrar “se ha incorporado el alumno”, clave e información Si no Mostrar “la incorporación del alumno (clave) no ha sido posible” Fin_si Si no Mostrar “la operación que se solicita no es correcta” Fin_si Fin_si Fin_si Fin_si Fin_si Fin_mientras Fin Este programa define primero la «tabla_centro» de 205 alumnos, con la clave y la información de cada alumno. Seguidamente, solicita por la pantalla de la computadora ¿qué operación se desea realizar? El usuario del programa escribe un 1, 2, 3 ó 4 si desea realizar una operación de búsqueda, actualización, eliminación o inserción, o un 0 si desea finalizar la ejecución del programa. En el caso de que la operación sea de búsqueda (1), el programa solicita leer la clave. Seguidamente llama a la función búsqueda_lineal, codificada anteriormente, y si retorna un 0 quiere decir que la búsqueda de ese alumno ha sido correcta y visualiza la clave y la información del alumno; en caso contrario, muestra un mensaje de error. Si la operación es una actualización (2) o una inserción (4), el programa pide leer la clave y la información a actualizar o insertar del alumno. Posteriormente, llama a la función búsqueda_lineal y si ésta retorna un 0, muestra por pantalla que la actualización o inserción han sido correctas. Si el retorno ha sido diferente de 0, visualiza que la operación no ha sido posible. Si la operación es una eliminación (3) es decir, dar de baja a un alumno, entonces el programa pide leer la clave del alumno a dar de baja y llama a la función búsqueda_lineal. Si la función retorna 0 (eliminación correcta), el programa muestra por pantalla que se ha eliminado al alumno y su clave. En caso contrario, visualiza un mensaje de error. El lector habrá podido comprobar que el programa se ha codificado con varias instrucciones condicionales dobles del tipo: «Si Entonces… Si no». Evidentemente, se podría haber utilizado una instrucción condicional múltiple del tipo: «Según operación…», reduciendo con ello la codificación, como se hizo en la tabla de acceso directo. No obstante, se ha querido hacer así para que el lector vea mejor la secuencialidad del programa. Las tablas organizadas con búsqueda_lineal presentan las siguientes características: — Es muy sencillo realizar la inserción y eliminación de un elemento. Basta con encontrar el primer hueco para la inserción, o crear un hueco en el caso de la eliminación, sin preocuparse de nada más. — La búsqueda y actualización resultan muy costosas porque hay que ir chequeando clave tras clave hasta encontrar la solicitada. Este es un proceso muy caro, lo que hace que este tipo de tablas no sean muy utilizadas en informática. Interesa recordar que en las tablas de acceso directo la búsqueda es inmediata ya que al primer acceso a la tabla se encuentra el elemento solicitado; mientras que en este tipo de tabla la búsqueda se hace interminable si la tabla es muy grande.Enciclopedia, México, Colima, Revista Electronica Fumarola, Noticias LeeColima, Lee Colima
...
  Inicio  http://twitter.com/leecolima   http://www.facebook.com/pages/leecolimacommx/     | Pad Noticias | Windows Mobile Noticias
 
Tabla de búsqueda_lineal (tabla look-up) - estructura de datos
  
 



          Sugerencia ... Búsqueda personalizada.