UC3M

Grado en Ing. Telemática/Sist. Audiovisuales/Sist. de Comunicaciones

Arquitectura de Sistemas

Septiembre 2017 - Enero 2018

7.9.8. Insertando y persistiendo una tabla-hash

Recursos

  • Conocimientos sobre estructuras de datos dinámicas.

Plan de trabajo

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.

  1. 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.

  2. 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.