Algoritmos y Progamación II - 1C2023

TP2: Michelle Chen - 105506 - mchen@fi.uba.ar

• Para compilar:

gcc -std=c99 -Wall -Wconversion -Wtype-limits -pedantic -Werror -O0 -g src/*.c tp2.c -o tp2

• Para ejecutar:

./tp2

• Para ejecutar con valgrind:

valgrind --leak-check=full --track-origins=yes --show-reachable=yes --error-exitcode=2 --show-leak-kinds=all --trace-children=yes ./tp2

---

Funcionamiento

Para este tp2 se implementaron dos TDAs:

• TDA Hospitales: Para el manejo de un conjunto de TDA hospital_t. Crea hospitales hospital_t a partir de nombres de archivos en forma de string y los almacena. La estrcutra hospitales_t contiene las siguientes variables:

  • *hash_t archivos_hospitales: Un hash_t que tiene como CLAVE el número único asociado a cada archivo (tipo de dato char *) y tiene como VALOR el nombre del archivo (tipo de dato char *) para la creación del hospital_t.

  • *hash_t hospitales: Un hash_t que tiene como CLAVE el número único asociado a cada archivo (tipo de dato char *) y que tiene como VALOR el hospital_t creado.

  • size_t cantidad: Variable contador de la cantidad de hospitales almacenados en hospitales_t.

  • lista_t activos: Variable del tipo lista_t que almacenan los números (tipo de dato char) asociados a cada hospital activo.

  • *lista_t nombres_archivos: Variable lista_t para los nombres de los archivos cargados. Variable para faciliar la verificación de nombre de archivos repetidos.

Las operaciones implementadas para el TDA HOSPITALES son:

• hospitales_t *hospitales_crear(size_t capacidad): La función crea un hospitales_t. Con la capacidad pasada como parámetro creo los hash_t que necesitan una capacidad inicial. Si la capacidad pasada es menor que 3 la capacidad sería de 3. Si las variables no fueron creadas de manera exitosa se devuelve NULL.

• bool hospitales_verificar_existencia(hospitales_t *hospital, char *nombre_archivo, char *numero_archivo): La función verifica la existencia de un archivo a partir de su nombre o del número asociado. Se debe pasar sí o sí o nombre del archivo o número asociado al archivo, si no se pasa alguno de los dos, se devuelve false.

Para verificar si el nombre del archivo es uno de los ya cargados se utliza la función lista_buscar_elemento del TDA Lista ya implementada. Creo una función int comparador_strings(void *numero_activos, void *numero) y paso como aux al nombre del archivo a buscar para buscar si el nombre del archivo pasado está en *lista_t nombres_archivos. Si la función lista_buscar_elemento devuelve el nombre del archivo significa que el nombre del archivo ya existe, y hospitales_verificar_existencia devuelve true.

Para verificar si el número de archivo es uno de los ya cargados se utliza la función hash_contiene del TDA Hash ya implementada. hash_contiene se fija en archivos_hospitales (CLAVE: Número de archivo / VALOR: Nombre de archivo) con el número de archivo pasado como clave. Si devuelve true significa que el número ya es usado para algún archivo.

• hospitales_t *hospitales_cargar_hospital(hospitales_t *hospital, char *nombre_archivo): La función recibe un hospitales_t y un nombre de archivo para cargar al archivos_hospitales y agregar el hospital creado con el nombre de archivo pasado, si es que se pudo crear, a hospitales, y agregar el nombre del archivo a la lista de nombres_archivos, y por último incrementar cantidad.

Si no se logra crear el hospital_t devuelve NULL. Si el nombre de archivo ya fue cargo anteriormente, se destruye el hospital_t creado con hospital_destruir y se devuelve el hospitales_t original.

Si se creó el hospital_t correctamente y el nombre del archivo no fue uno cargado y carga el nombre del archivo con su número asociado a archivos_hospitales, el número asociado y el hospital_t a hospitales y el nombre del archivo a nombres_archivos y se incrementa la cantidad en 1.

Para el número asociado a cada archivo uso la cantidad de archivos almacenados en archivos_hospitales, ya que cada archivo es único.

Como el hash_t solamente recibe clave del tipo de dato string, implmenté una función numero_a_string para convertir el tipo de dato size_t a char *.

• bool hospitales_activo(hospitales_t *hospital, char *numero_archivo): Función para verificar si un archivo está activo o no. Recibe un hospitales_t y un numero de archivo, usa la función lista_buscar_elemento para averiguar si el número de archivo está presente en la lista, si está presente significa que el archivo está activo y devuelve true. Si no lo encuentra significa que no fue activado, devuelve false.

• bool hospitales_activar(hospitales_t *hospital, char *numero_archivo): Función que se encarga de activar un hospital_t. Verifica si el archivo está cargado en hospitales_t, si no está cargado devuelve false. Si el archivo fue cargado, entonces lo puedo activar y agrega el número de archivo a la lista de los activos, devuelve true.

• hospital_t *hospitales_hospital_buscar(hospitales_t *hospital, char *numero_archivo): Busca el hospital_t asociado al número de archivo pasado como parámetro. Usa la función hash_obtener para buscar, si lo encuentra devuelve el hospital_t, si no, devuelve NULL.

• void lista_hospitales_estados_imprimir(hospitales_t *hospital): Imprime el estado de los archivos cargados al hospitales_t. Usa la función hash_con_cada_clave que recorre cada par <CLAVE, VALOR> de archivos_hospitales y aplica la función auxliar implementada hospitales_todos_imprimir e imprime los archivos junto con su número. Si está activo se agrega una A al final.

• bool nombres_pokemones_mostrar(hospitales_t *hospital, char *numero_hospital): Muestra la lista de nombres de los pokemones de un hospital_t. Recibe el número de asociado al hospital y verifica si el número está en la lista de los activos. Obtiene el hospital_t con la función hash_obtener e imprime los nombres de los pokemones con la función hospital_a_cada_pokemon usando la función auxiliar pokemon_nombre_mostrar que imprime el nombre de cada pokemón presente en el hospital_t.

• bool datos_pokemones_mostrar(hospitales_t *hospital, char *numero_hospital): Funciona mas o menos de la misma manera que la función nombres_pokemones_mostrar, pero imprime todos los datos de un pokemón.

• bool hospital_activo_destruir(hospitales_t *hospital, char *numero_hospital): La función destruye un hospital_t activo. Si no está activo devuelve false. Interpreto a destruir un hospital activo como destruir el archivo completo. Entonces la función elimina de archivos_hospitales el par <número de archivo, nombre de archivo>, de activos el número de archivo, de hospitales el par <número de archivo, hospital> y de nombres_archivos el nombre de archivo y por último se decrementa cantidad en 1.

• void hospitales_destruir(hospitales_t *hospital): Destruye un hospitales_t. Libera la memoria pedida para cada variable de la estructura. Para archivos_hospitales se destruye con hash_destruir_todo pasándole la función free para la liberación de la memoria pedida para el nombre del archivo. Se destruye hospitales con hash_destruir_todo pasándole la función destructor_hospital para la destrucción de cada uno de los hospital_t. Con lista_destruir_todo se destruye activos pasándole la función free para la memoria pedida para cada número de archivo. Con lista_destruir se destruye nombres_archivos, y por último se libera el hospitales_t con free.

---

• TDA Menu: Se crea este TDA para el manejo de las opciones. El TDA Menu tiene 3 variables:

  • *hash_t opciones: Es un hash_t que tiene como clave el símbolo de una opción y tiene como valor el nombre completo de la opción.

  • *char seleccion: Es un **char *** que almacena el símbolo de la opción seleccionada por el usuario.

  • *char salir: Es un **char *** que almacena el símobolo de salida predeterminada.

Las operaciones implementadas para el TDA MENU son:

• **menu_t *menu_crear(char **simbolos, char nombres_opciones, size_t cantidad): Crea un menu_t con pidiendo memoria para las variables de la estructura y carga las listas de simbolos y nombres completos de las opciones al menu. Usa la función hash_insertar para agregar el par <simbolo, nombre completo de la opción>. Devuelve el menu_t creado si el pedido de memoria fue exitoso, devuelve NULL si hubo algún error.

• menu_t *menu_opcion_agregar(menu_t *menu, char *simbolo, char *nombre_completo): Función que permite agregar un par <simbolo, nombre completo de la opción> a opciones.

• void menu_seleccion_cargar(menu_t *menu, char *opcion): Carga la selección al menu.

• void menu_salir_cargar(menu_t *menu, char *opcion_salir): Carga el símbolo de salida eleigido al menu.

• char *menu_salir(menu_t *menu): Devuelve el símbolo de salida cargado.

• bool menu_contiene(menu_t *menu, char *simbolo): Función para verificar la existencia de una opción. Recibe un símbolo y verifica si esa opción está en opciones, si no existe, devuelve false.

• void menu_imprimir(menu_t *menu): Imprime todas el nombre completo de todas las opciones cargadas usando hash_con_cada_clave que recorre por todas las claves del hash_t aplicando la función auxliar opciones_imprimir que imprime las opciones en el formato determinado.

• void menu_destruir(menu_t *menu): Destruye un menu_t liberando la memoria pedida para las variables. Se destruye opciones con hash_destruir. Se libera salir y seleccion con free. Y por último se libera menu_t con free.

TP2

Se crearon dos menus menu_principal y menu_hospital ya que hay una parte de las operaciones que solamente aparecen cuando hay hospitales cargados. Se creó un hospitales_t. Se loopea con un while hasta que el usuario ingrese la opción s para salir del programa. Si el usuario elige salir del programa, se sale del while loop y se destruye los dos menu_t y el hospitales_t.

Una vez que arranca el programa, se explica brevemente el funcionamiento del programa y se pregunta al usuario si desea arrancancarlo. Si el usuario ingresa s no se arranca el prgrama. Con cualquier otra cosa que no sea s se arranca el programa.

Si la cantidad de archivos_hospitales no es 0 significa que el usuario ha cargado algún archivo. Entonces la selección del usuario debe ser guardada en el menu menu_hospital. En caso contrario, no hay hospitales cargados y el menu sigue siendo menu_principal.

La función void input_usuario(menu_t *menu_principal, menu_t *menu_hospital) pide input del usuario, si la opción está contenida en opciones de menu_princial, se carga la opción en seleccion. Si la opción no está cargada en menu_principal, no es la opción de salida, pero está cargada en menu_hospital entonces se carga la opción en seleccion de menu_hospital.

En la función de interaccion se evalúa la seleccion del menu derivando a las respectivas funciones que cumple con cada opción elegida. Si falla algún pedido de memoria devuelve false y si algún input fue inválido o que se pudo terminar de ejecutar las funciones se devuelve true y se pide devuelta que el usuario ingrese alguna operación.

---

Respuestas a las preguntas teóricas

Reemplazo del vector dinámico de pokemones con ABB (Árbol Binario de Búsqueda)

Como algunas de las funciones del tp1.c tienen involucradas el problema del orden de prioridad (hospital_a_cada_pokemon y hospital_obtener_pokemon) elijo reeplazar el vector dinámico de pokemones con un ABB, de esta manera, los pokemones quedan ordenados a medida que los vaya insertando.

Como para el tp1.c el orden de los pokemones gira alrededor de la salud de cada pokemón, el comparador pasado como parámetro para la creación de un abb_t sería un comparador que compare la salud de los pokemones.

Reemplazo del vector dinámico de pokemones con HEAP BINARIO

Teniendo en cuenta el tema del orden, el segundo TDA elegido para reemplazar al vector de dinámico sería un TDA HEAP BINARIO implementada con un vector dinámico.

Como para las funciones del tp1.c se necesitan pokemones de menor salud, debería usar un HEAP MAXIMAL en la que la raíz sería siempre el pokemón con mayor salud para después realizar HEAPSORT y tener a los pokemones ordenados de menor a mayor salud.

Tabla de Complejidades para Reemplazo con ABB

Función	Complejidad ABB	Justificación
hospital_crear_desde_archivo	O(N2) / O(N LOG N)	Se crean los pokemones desde el archivo para insertar al hospital leyendo cada línea del archivo. Si el archivo contiene N líneas, entonces se crean N pokemones para la inserción y se loopea N veces para insertar a cada uno de ellos. Para insertar en un ABB, empleamos la función abb_insertar que tiene complejidad O(N) en el peor de los casos. Como para recorrer e insertar a los pokemones, se loopea N veces abb_insertar, la complejidad en el peor de los casos sería O(N2). En este caso nos ahorramos el paso de ordenamiento, ya que los pokemones quedan ordenados en el proceso de inserción. Pero si consideramos a la operación de abb_insertar en su caso promedio, la complejidad de insertar en un ABB sería O(LOG N) entonces la complejidad sería de O(N LOG N).
hospital_cantidad_pokemones	O(1)	La complejidad de obtener la cantidad sería O(1), ya que la estructura hospital_t tiene una variable que registra la cantidad de pokemones en el hospital.
hospital_a_cada_pokemon	O(N)	Esta función que recorre los pokemones del hospital aplicando la función pasada por parámetro mientras que la función devuelva true podría ser implementada con abb_con_cada_elemento con recorrido INORDEN que recorre los pokemones de menor salud a mayor aplicándoles la función pasada. Como abb_con_cada_elemento tiene complejidad O(N) ya que tiene que recorrer todos los elementos del ABB.
hospital_aceptar_emergencias	O(N2) / O(N LOG N)	Se debe ingresar los pokemones que están contenidos en un vector al hospital. Si suponemos que la cantidad de pokemones que llegan con la ambulacia como N, entonces debemos hacer N veces abb_insertar al hospital. Si considero el peor caso de abb_insertarla complejidad para hospital_aceptar_emergencias sería O(N2) y si considero la complejidad de abb_insertar en su caso promedio que sería O(LOG N), realizando N inserciones sería O(N LOG N).
hospital_obtener_pokemon	O(N)	No podría usar la función abb_buscar porque para poder usarlo necesito el elemento buscado que en este caso tengo solamente la prioridad. La podría implementar usando la función abb_recorrer de manera INORDEN y limitar el tamaño del array pasado como parámetro a abb_recorrer para que sea igual a la prioridad. De esta manera puedo obtener el pokemón con la prioridad requerida a través del array. Como abb_recorrer en el peor de los casos tienen complejidad O(N), la complejidad de hospital_obtener_pokemon sería de O(N).
hospital_destruir	O(N)	Para destruir el hospital se podría utilizar la función abb_destruir_todo que recorre todos los pokemones del hospital y aplica un destructor de pokemones a cada uno de ellos, y por último libera el hospital. Como la función abb_destruir_todo debe liberar a todos los pokemones del ABB la complejidad sería O(N).

Tabla de Complejidades para Reemplazo con HEAP BINARIO

Función	Complejidad HEAP BINARIO	Justificación
hospital_crear_desde_archivo	O(N LOG N)	Para la inserción de pokemones podríamos utilizar la función de inserción del heap binario, se inserta en el primer espacio libre del último nivel del heap binario y le aplico sift-up al pokemon. Como necesitamos a que los pokemones estén ordenados de menor salud a mayor salud, una forma sería tener un heap maximal para que cuando le aplique heapsort al heap quede de menor a mayor, o, otra forma sería tener un heap minimal ya que puedo ir quitando pokemones desde la raíz, que en un heap minimal la raíz siempre será el elemento con menor valor. La operación de inserción de un heap tiene complejidad O(LOG N) en el peor caso y si tengo N pokemones para insertar, la complejidad de la función hospital_crear_desde_archivo será O(N LOG N).
hospital_cantidad_pokemones	O(1)	El uso de heap binario para no afecta ya que la estructra del hospital mantiene una variable contador para la cantidad de pokemones
hospital_a_cada_pokemon	O(N LOG N)	Como hospital_a_cada_pokemon debe aplicar la función pasada por parámetro a los pokemones siguiendo la prioridad (primero los pokemones de menor salud) se me ocurre dos maneras de encararlo: 1. Tener un heap minimal. Como la raíz del heap minimal siempre será el pokemón con menor salud dentro de todos los pokemones, podría ir quitando el pokemón de la raíz e aplicarle la función dada y después insertarlos en un heap mininal auxliar vacío. Se debe aplicar a cada pokemón la operación de eliminación de complejidad O(LOG N) y la operación de inserción de complejidad O(LOG N), s{O(LOG N), O(LOG N)}, la complejidad sería O(LOG N) para las dos operaciones. Como hay N pokemones, la complejidad sería de O(N LOG N) 2. Tener un heap maximal y aplicarle heapsort para que quede de menor a mayor y después recorrerlos para aplicarle la función dada. La complejidad de heapsort sería O(N LOG N) y aplicarle la función a cada pokemon tiene complejidad O(N), las dos operaciones se aplican de manera separada, S{O(N LOG N), O(N)}, la operación de mayor complejidad sería O(N LOG N)
hospital_aceptar_emergencias	O(N LOG N)	Se insertan los pokemones que llegan con la ambulacia al hospital. La complejidad de la operación de inserción es de O(LOG N) y como debería insertar N pokemones de la ambulancia, la complejidad sería O(N LOG N).
hospital_obtener_pokemon	O(N LOG N)	Para el caso de tener un heap maximal y aplicarle heap sort, de O(N LOG N), para obtener un vector de pokemones de menor a mayor salud, y para acceder al pokemon de prioridad dada sería de complejidad O(1), entonces la complejidad sería O(N LOG N). Para el caso de tener un heap minimal debería quitar el pokemón de la raíz la cantidad de veces que indique la prioridad, que en el peor de los casos sería N, la operación de eliminación tiene complejidad O(LOG N) por lo que la complejidad para este caso sería O(N LOG N).
hospital_destruir	O(N LOG N)	La operación de eliminación de un pokemón de un heap tiene complejidad O(LOG N), como debería eliminar todos los pokemones del heap, la complejidad sería de O(N LOG N).