ejercicios_busqueda

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

#include <stdio.h>
#include <stdlib.h>
#include "listas.h"
/** 
 * Crear una función que compruebe si un array está ordenado o no
 *
 * ENTRADA:
 * lista: array con los valores
 * tamLista: tamaño del array 'lista'
 *
 * SALIDA:
 * 1 si el array 'lista' está ordenado en orden ascendente y 0 si no lo está 
 */
int estaOrdenada(int *lista, int tamLista)
{
}
/** 
 * Crear una función que busque un valor en un array mediante búsqueda lineal
 *
 * ENTRADA:
 * valor: valor a buscar en la lista
 * lista: array con los valores
 * tamLista: tamaño del array 'lista'
 *
 * SALIDA:
 * Índice del valor si se encuentra el 'valor' en la 'lista'
 * -1 si no se encuentra
 */
int busquedaLineal(int valor, int *lista, int tamLista)
{
}
/** 
 * Crear una función que busque un valor en un array mediante búsqueda binaria
 *
 * ENTRADA:
 * valor: valor a buscar en la lista
 * lista: array con los valores
 * tamLista: tamaño del array 'lista'
 *
 * SALIDA:
 * Índice del valor si se encuentra el 'valor' en la 'lista'
 * -1 si no se encuentra
 */
int busquedaBinaria(int valor, int *lista, int inf, int sup)
{
}
/**
 * Crear una función hash que devuelva el valor hash de una clave numérica
 * mediante la operación de módulo
 *
 * ENTRADA:
 * tamanio_tabla: tamaño de la tabla. El valor devuelto no puede ser igual o
 * superior a este valor 
 * clave: valor de la clave sobre la que hay que calcular el hash
 *
 * SALIDA:
 * Valor del hash
 */
int hash_modulo(int tamanio_tabla, int clave)
{
}
/**
 * Crear una función hash que devuelva el valor hash de una clave numérica
 * mediante la operación de multiplicacion usando la proporción aurea
 *
 * ENTRADA:
 * tamanio_tabla: tamaño de la tabla. El valor devuelto no puede ser igual o
 * superior a este valor 
 * clave: valor de la clave sobre la que hay que calcular el hash
 *
 * SALIDA:
 * Valor del hash
 */
int hash_multiplicacion(int tamanio_tabla, int clave)
{
}
/**
 * Crear una función que mida el tiempo que tarda en buscar todos los valores
 * de una tabla de tamaño ‘tamanio_tabla’ usando búsqueda lineal.
 *
 * Se debe:
 * Crear una lista sin ordenar
 * comenzar medida de tiempos
 * buscar todos los elementos de la lista con búsqueda lineal
 * finalizar medida de tiempos
 * liberar lista
 * devolver tiempo
 */
int mide_tiempos_lineal(int tamanio_tabla)
{
}
/**
 * Crear una función que mida el tiempo que tarda en buscar todos los valores
 * de una tabla de tamaño ‘tamanio_tabla’ usando búsqueda binaria.
 *
 * Se debe implementar de forma equivalente al anterior
 */
int mide_tiempos_binaria(int tamanio_tabla)
{
}
/**
 * Crear una función que mida el tiempo que tarda en buscar todos los valores
 * de una tabla de tamaño ‘tamanio_tabla’ usando búsqueda lineal.
 *
 * Nota: se debe usar el TAD thash incluido en el zip
 *
 * Se debe:
 * Crear una lista sin ordenar
 * Crear un hash que empareje el numero de cada posición de la lista 
 * (que será la clave en thash) con su posición en la lista
 * (que será el valor en thash)
 * comenzar medida de tiempos
 * recuperar todas las posiciones de todos los elementos de la lista con la
 * tabla hash
 * finalizar medida de tiempos
 * liberar lista
 * devolver tiempo
 *
 * Ejemplo de como crear una tabla hash, insertar un elemento y recuperarlo.
 * Se inserta un elemento con clave 100 y valor 0:
 *
 * hash_table *t;
 *
 * t = new_hashtable(1000, hash_modulo);
 * insert_hashtable(t, 100, 0);
 * printf("El valor para la clave %d es %d\n", 100, find_hashtable(t, 100));
 * destroy_hashtable(t);
 * 
 */
int mide_tiempos_hash(int tamanio_tabla)
{
}
/* Puedes modificar este valor para probar arrays de diferentes tamaños */
#define TAM 100
/**
 * Crea un array de enteros de tamaño 'tam' y lo inicializa con números 
 * aleatorios
 */
int *crearArray(int tam) 
{
 int *lista, i;
 
 if (tam<=0) return NULL;
 
 lista = (int*)malloc(sizeof(int)*tam);
 if (!lista) return NULL;
 
 for (i = 0; i < tam; i++) {
 lista[i] = rand();
 }
 
 return lista;
}
/**
 * Crea un array de enteros de tamaño 'tam' y lo inicializa con números 
 * aleatorios y lo devuelve ordenado. Para ordenarlo usa la función fcomp,
 * que compara el valor de dos enteros
 */
int fcomp(const void * a, const void * b)
{
 return *(int*)a - *(int*)b;
}
int *crearArrayOrdenado(int tam) 
{
 int *lista;
 
 lista = crearArray(tam);
 if (!lista) return NULL;
 qsort(lista, tam, sizeof(int), fcomp);
 
 return lista;
}
/**
 * Libera la memoria del array
 */
void borrarArray(int *lista)
{
 free(lista);
}
/**
 * Función para probar las búsquedas
 */
void prueba_busqueda(int *lista, int tam)
{
 int i, num;
 printf("-----------------------------------------------------------------\n");
 printf("La lista: ");
 for (i = 0; i < tam; i++) {
 printf("%d ", lista[i]);
 }
 printf("\n¿Está ordenada? %s\n", estaOrdenada(lista, tam) ? "SI" : "NO");
 
 /* Test busqueda */
 printf("Elige un numero a buscar: ");
 scanf("%d", &num);
 i = estaOrdenada(lista, TAM) ? busquedaBinaria(num, lista, 0, tam-1) :
 busquedaLineal(num, lista, tam);
 if (i < 0) printf("El valor %d no ha sido encontrado\n", num);
 else printf("El valor %d está en la posición %d de la lista\n", num, i+1); 
 
}
/**
 * Main
 */
int main(int argc, char *argv[])
{
 int *lista;
 /* Test segundo ejercicio */
 lista = crearArray(TAM);
 prueba_busqueda(lista, TAM);
 borrarArray(lista);
 
 /* Test primer ejercicio */
 lista = crearArrayOrdenado(TAM);
 prueba_busqueda(lista, TAM);
 borrarArray(lista);
 /* Test madir tiempos */
 printf("El tiempo para buscar todos los elementos de una "
 "tabla de tamaño %d es %d\n", TAM, mide_tiempos_lineal(TAM));
 printf("El tiempo para buscar todos los elementos de una "
 "tabla de tamaño %d es %d\n", TAM, mide_tiempos_binaria(TAM));
 printf("El tiempo para buscar todos los elementos de una "
 "tabla de tamaño %d es %d\n", TAM, mide_tiempos_hash(TAM));
 
}