Conocimientos sobre estructuras de datos dinámicas.
En SAUCEM Labs le piden participar en el diseño de una aplicación eficiente para alumnos donde
la información se almacena en una matriz asociativa (tabla hash). La información que contiene de cada alumno
(almacenada en una estructura de tipo struct datos) es un nombre (name
) y el nia
de cada alumno.
Internamente, la matriz asociativa se representa con un vector (array) de listas descritas mediante nodos de
tipo struct element_t. Cada uno de estos nodos forma parte de una de las listas del vector (array). Cada
elemento struct element_t contiene un puntero a los datos a almacenar, la clave asociada al elemento, y un puntero
al siguiente elemento. De igual manera también se almacena internamente el tamaño del vector (array) de la matriz
asociativa y un puntero (**tabla) al vector donde comienzan dichos elementos.
00: struct datos { 01: char *name; 02: int nia; 03: }; 04: struct elemento_t { 05: struct datos* valor; 06: int clave; 07: struct elemento_t *next; 08: }; 09: struct tabla_type { 10: int tamanho; 11: int num_elementos; 12: struct elemento_t **tabla; 13: };
La figura mostrada más abajo ejemplifica una matriz asociativa (tabla hash) que almacena la información de tres alumnos llamados Eva (con NIA: 33997), Paul (con NIA: 33993) y Juan (con NIA: 3399). El ejemplo asume que tanto Eva como Paul han sido insertados con clave 0, mientras que Juan lo ha hecho con clave 32.
Haciendo uso de toda esta información le piden que implemente la siguiente función:
void dump_hash_table_to_file(struct tabla type* htable, char* file_name).
Dicha función recibe un puntero a la matriz asociativa (htable) y el nombre del fichero (file_name) donde volcar los resultados
de la tabla. Utilizando las funciones de escritura en fichero (fwrite) la función ha de escribir el contenido de todos los estudiantes
(nia y nombre) en un fichero binario. Si el fichero no se puede abrir, la función retornará inmediatamente.
Con la misma estructura de datos del apartado anterior le piden también implementar la siguiente función de inserción:
void insert_element_into_hash_table (int clave, struct datos* valor,struct tabla_type *htable)
Dicha función se encarga de insertar un nuevo elemento en la tabla hash apuntada desde htable. La función recibe una clave numérica
(clave) que indica la posición del vector en la cual se insertará el elemento. A efectos prácticos puede asumir que clave siempre
es menor que el tamaño del vector (no hace falta que lo compruebe). La función también recibe los datos del alumno a insertar
en memoria dinámica a través de un puntero llamado valor.