ESTRUCTURA DE DATOS LINEALES PARA BUSQUEDA DE INFORMACION

¿Como realizar eficientemente una busqueda?

para ordenar la informacion es necesaria el ordenamiento segun uno (varios) de los campos  que conforman cada registro de informacion. El campo que determina el ordenamiento d se denomina llave, ya que distingue de manera  únicamente registro.

 La llave puede ser simple, si  se forma  con un solo campo(como ka matricula de un alumno en la universidad)

 o  compuesta, se forma por varios campos (nombre, apellido y dirección de una persona), por lo que la estructura  de datos para la búsqueda  de información no se guardara información repetida.

¿Que opciones de representacion en memoria  existen para una estructura de datos para la busqueda de infomracion?

Si se deasa  utilizar una estructura temporal y ilimitado, para obtner accesis rapidos, se debera pensar en memoria principales.

si se desea utilizar una estructura permanente e ilimitada para almacenar grades volumenes de informacion, se deberia utilizar la memoria  secundaria.

Posibles representaciones lineales en memoria principales en la memoria  estatica se puede utilizar un arrelge  que guarde la informacion en forma ordenada. esta representacion , tipicamente, se conoce con el nombre de tabla.

En memoria dinamica se puede utilizar  una lista encadenadas  que  guarde ordenadamente la informacion.  Esta  representacion, generalment se llama lista Ordenadas.

¿como se pueden implementar el proceso de búsqueda en una estructura lineal?

 La busqueda secuencial:

• Los algoritmos de búsqueda lineal y binaria son 2 de los algoritmos más usados para encontrar elementos en una estructura de datos.La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado. Entonces este algoritmo tiene una complejidad de O(n).

La búsqueda binaria:

• Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmo más eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer.
  Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado (o con suerte igual), sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí.