Forma rápida de implementar el diccionario en C

Una de las cosas que echo de menos al escribir progtwigs en C es una estructura de datos del diccionario. ¿Cuál es la forma más conveniente de implementar uno en C? No busco el rendimiento, sino la facilidad de codificarlo desde cero. No quiero que sea genérico tampoco, algo así como string-> int servirá. Pero sí quiero que sea capaz de almacenar una cantidad arbitraria de elementos.

Esto es más como un ejercicio. Sé que hay bibliotecas de terceros disponibles que se pueden usar. Pero considera por un momento que no existen. En tal situación, ¿cuál es la forma más rápida de implementar un diccionario que satisfaga los requisitos anteriores?

La Sección 6.6 de The C Programming Language presenta una estructura de datos simple de diccionario (hashtable). No creo que una implementación útil del diccionario pueda ser más simple que esto. Para su comodidad, reproduzco el código aquí.

struct nlist { /* table entry: */ struct nlist *next; /* next entry in chain */ char *name; /* defined name */ char *defn; /* replacement text */ }; #define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* pointer table */ /* hash: form hash value for string s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } /* lookup: look for s in hashtab */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* found */ return NULL; /* not found */ } char *strdup(char *); /* install: put (name, defn) in hashtab */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if ((np = lookup(name)) == NULL) { /* not found */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* already there */ free((void *) np->defn); /*free previous defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; } char *strdup(char *s) /* make a duplicate of s */ { char *p; p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */ if (p != NULL) strcpy(p, s); return p; } 

Tenga en cuenta que si los valores hash de dos cadenas colisionan, puede llevar a un tiempo de búsqueda O(n) . Puede reducir la probabilidad de colisiones aumentando el valor de HASHSIZE . Para una discusión completa de la estructura de datos, consulte el libro.

La forma más rápida sería usar una implementación ya existente, como uthash .

Y, si realmente quiere codificarlo usted mismo, los algoritmos de uthash pueden examinarse y reutilizarse. Tiene licencia de BSD, por lo que, aparte del requisito de transmitir el aviso de copyright, tiene bastante buen límite en cuanto a lo que puede hacer con él.

Para facilitar la implementación, es difícil superar ingenuamente la búsqueda a través de una matriz. Aparte de algunas comprobaciones de errores, esta es una implementación completa (no probada).

 typedef struct dict_entry_s { const char *key; int value; } dict_entry_s; typedef struct dict_s { int len; int cap; dict_entry_s *entry; } dict_s, *dict_t; int dict_find_index(dict_t dict, const char *key) { for (int i = 0; i < dict->len; i++) { if (!strcmp(dict->entry[i], key)) { return i; } } return -1; } int dict_find(dict_t dict, const char *key, int def) { int idx = dict_find_index(dict, key); return idx == -1 ? def : dict->entry[idx].value; } void dict_add(dict_t dict, const char *key, int value) { int idx = dict_find_index(dict, key); if (idx != -1) { dict->entry[idx].value = value; return; } if (dict->len == dict->cap) { dict->cap *= 2; dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s)); } dict->entry[dict->len].key = strdup(key); dict->entry[dict->len].value = value; dict->len++; } dict_t dict_new(void) { dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))}; dict_t d = malloc(sizeof(dict_s)); *d = proto; return d; } void dict_free(dict_t dict) { for (int i = 0; i < dict->len; i++) { free(dict->entry[i].key); } free(dict->entry); free(dict); } 

Cree una función hash simple y algunas listas de estructuras vinculadas, dependiendo del hash, asigne a qué lista vinculada insertar el valor. Usa el hash para recuperarlo también.

Hice una implementación simple hace un tiempo:

 ...
 #define K 16 // coeficiente de encadenamiento

 struct dict
 {
     nombre del personaje;  / * nombre de la clave * /
     int val;  / * valor * /
     struct dict * next;  / * campo de enlace * /
 };

 typedef struct dict dict;
 dict * tabla [K];
 int inicializado = 0;


 void putval (char *, int);

 void init_dict ()
 {   
     inicializado = 1;
     int i;  
     for (i = 0; iname = (char *) malloc (strlen (key_name) +1);
     ptr-> val = sval;
     strcpy (ptr-> name, key_name);


     ptr-> next = (struct dict *) table [hsh];
     tabla [hsh] = ptr;

 }


 int getval (char * nombre_clave)
 {   
     int hsh = hash (nombre_clave);   
     dict * ptr;
     para (ptr = tabla [hsh]; ptr! = (dict *) 0;
         ptr = (dict *) ptr-> siguiente)
     if (strcmp (ptr-> name, key_name) == 0)
         return ptr-> val;
     return -1;
 }

Aquí hay un implemento rápido, lo usé para obtener una ‘Matriz’ (fructificación) de una cadena. puedes tener una matriz más grande y cambiar sus valores en la ejecución también:

 typedef struct { int** lines; int isDefined; }mat; mat matA, matB, matC, matD, matE, matF; /* an auxilary struct to be used in a dictionary */ typedef struct { char* str; mat *matrix; }stringToMat; /* creating a 'dictionary' for a mat name to its mat. lower case only! */ stringToMat matCases [] = { { "mat_a", &matA }, { "mat_b", &matB }, { "mat_c", &matC }, { "mat_d", &matD }, { "mat_e", &matE }, { "mat_f", &matF }, }; mat* getMat(char * str) { stringToMat* pCase; mat * selected = NULL; if (str != NULL) { /* runing on the dictionary to get the mat selected */ for(pCase = matCases; pCase != matCases + sizeof(matCases) / sizeof(matCases[0]); pCase++ ) { if(!strcmp( pCase->str, str)) selected = (pCase->matrix); } if (selected == NULL) printf("%s is not a valid matrix name\n", str); } else printf("expected matrix name, got NULL\n"); return selected; } 

Una tabla hash es la implementación tradicional de un simple “Diccionario”. Si no te importa la velocidad o el tamaño, busca en Google . Hay muchas implementaciones disponibles libremente.

esta es la primera que vi , a primera vista, me parece bien. (es bastante básico. Si realmente quieres que contenga una cantidad ilimitada de datos, entonces necesitarás agregar algo de lógica para “reallocar” la memoria de la tabla a medida que crece).

¡buena suerte!

GLib y gnulib

Estas son sus mejores apuestas si no tiene requisitos más específicos, ya que están ampliamente disponibles, son portátiles y probablemente eficientes.

Ver también: ¿Hay alguna biblioteca C de código abierto con estructuras de datos comunes?

Me sorprende que nadie haya mencionado el conjunto de bibliotecas hsearch / hcreate , que aunque no está disponible en Windows, sí lo exige POSIX y, por lo tanto, está disponible en sistemas Linux / GNU.

El enlace tiene un ejemplo básico simple y completo que explica muy bien su uso.

Incluso tiene una variante segura de subprocesos, es fácil de usar y muy eficiente.

Hashing es la clave. Creo que usar la tabla de búsqueda y la clave hash para esto. Puede encontrar muchas funciones de hash en línea.

El método más rápido sería usar un árbol binario. Su peor caso también es solo O (logn).