Implementar diccionario en C

Este artículo demostrará varios métodos sobre cómo implementar un diccionario en C.

Utilice hcreate, hsearch y hdestroy para implementar la funcionalidad del diccionario en C

Generalmente, la biblioteca estándar de C no incluye una estructura de datos de diccionario incorporada, pero el estándar POSIX especifica rutinas de administración de tablas hash que se pueden utilizar para implementar la funcionalidad del diccionario. A saber, hcreate, hsearch y hdestroy proporcionan funciones como crear una tabla hash, insertar elementos en ella, buscar el elemento en una tabla y desasignar toda la estructura de datos. Aunque la funcionalidad implementada es la mínima, puede resolver muchos escenarios de problemas.

Al principio, es necesario llamar a la función hcreate para crear una tabla hash con un número máximo de elementos dado, que se pasa como único argumento. Tenga en cuenta que la capacidad no se puede modificar después de la llamada hcreate; por lo tanto, el usuario debe tener en cuenta este problema en la estructura del código. Una vez que se crea la tabla, se puede llamar a la función hsearch para agregar elementos en ella. Toma 2 argumentos; el primero es de tipo ENTRY, definido como struct de char* para la clave y void* para los datos correspondientes. El segundo parámetro es de tipo ACTION, que es esencialmente una enumeración que consta de dos elementos, FIND y ENTER. Los últimos valores se utilizan para indicar qué operación realizar en la mesa.

#include <search.h>
#include <stdio.h>
#include <stdlib.h>

static char *companies[] = {"Intel",   "AMD",      "ARM", "Apple",
                            "Marvell", "Qualcomm", "IBM", "Nvidia"};

static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
                        "ThunderX2",   "Kryo",  "z15", "Ampere"};

int main(void) {
  ENTRY e;
  ENTRY *ep;

  const size_t capacity = sizeof companies / sizeof companies[0];
  hcreate(capacity);

  for (size_t i = 0; i < capacity - 2; i++) {
    e.key = companies[i];
    e.data = (void *)uarch[i];

    ep = hsearch(e, ENTER);

    if (ep == NULL) {
      fprintf(stderr, "entry failed\n");
      exit(EXIT_FAILURE);
    }
  }

  e.key = "Intel";
  ep = hsearch(e, FIND);
  printf("%s -> %s\n", e.key, (char *)ep->data);

  hdestroy();
  exit(EXIT_SUCCESS);
}

Producción :

Intel -> Willow Cove

Observe que los ejemplos de código demuestran los pares clave-valor representados por texto sin cifrar, pero el usuario puede emplear algoritmos hash para crear claves y almacenarlas en la tabla. En este caso, agregamos 6 elementos a la tabla usando la iteración simple y omitimos los dos últimos elementos. El siguiente bucle for, sin embargo, consulta todos los elementos del array original e imprime los datos correspondientes.

La función hdestroy se utiliza para liberar memoria de la tabla hash, pero no libera los búferes en los objetos ENTRY, que normalmente es creado por el usuario. Por lo tanto, si los punteros en estos objetos apuntan a la memoria dinámica, la persona que llama es responsable de mantener los identificadores para ellos y desasignarlos antes de que salga el programa. Tenga en cuenta que las entradas individuales no se pueden eliminar de la tabla.

#include <search.h>
#include <stdio.h>
#include <stdlib.h>

static char *companies[] = {"Intel",   "AMD",      "ARM", "Apple",
                            "Marvell", "Qualcomm", "IBM", "Nvidia"};

static char *uarch[] = {"Willow Cove", "Zen 3", "A78", "A14",
                        "ThunderX2",   "Kryo",  "z15", "Ampere"};

int main(void) {
  ENTRY e;
  ENTRY *ep;

  const size_t capacity = sizeof companies / sizeof companies[0];
  hcreate(capacity);

  for (size_t i = 0; i < capacity - 2; i++) {
    e.key = companies[i];
    e.data = (void *)uarch[i];

    ep = hsearch(e, ENTER);

    if (ep == NULL) {
      fprintf(stderr, "entry failed\n");
      exit(EXIT_FAILURE);
    }
  }

  for (size_t i = 0; i < capacity; i++) {
    e.key = companies[i];
    ep = hsearch(e, FIND);

    ep ? printf("%s -> %s\n", e.key, (char *)ep->data)
       : printf("%s -> %s\n", e.key, "Entry not found");
  }

  hdestroy();
  exit(EXIT_SUCCESS);
}

Producción :

Intel -> Willow Cove
AMD -> Zen 3
ARM -> A78
Apple -> A14
Marvell -> ThunderX2
Qualcomm -> Kryo
IBM -> Entry not found
Nvidia -> Entry not found