Forma rápida de implementar el diccionario en C

Question

Una de las cosas que echo de menos al escribir programas 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?

Answer 1

Sección 6.6 del The C Programming Language presenta una sencilla estructura de datos del diccionario (tabla hash). 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 hashes de dos cadenas chocan entre sí, que puede conducir a un tiempo O(n) búsqueda. Puede reducir la probabilidad de colisiones aumentando el valor de HASHSIZE. Para una discusión completa de la estructura de datos, consulte el libro.

Answer 2

La manera más rápida sería utilizar 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.

Answer 3

Una tabla hash es la implementación tradicional de un simple "Diccionario". Si no le importa la velocidad o el tamaño, solo google for it. Hay muchas implementaciones disponibles libremente.

here's the first one I saw - 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 "realloc" la memoria de la tabla a medida que crece.)

¡buena suerte!

Answer 4

Crea una función hash simple y algunas listas de estructuras vinculadas, dependiendo del hash, asigna la lista vinculada para insertar el valor. Usa el hash para recuperarlo también.

Hice una aplicación sencilla algún tiempo atrás:

 
... 
#define K 16 // chaining coefficient 

struct dict 
{ 
    char *name; /* name of key */ 
    int val; /* value */ 
    struct dict *next; /* link field */ 
}; 

typedef struct dict dict; 
dict *table[K]; 
int initialized = 0; 


void putval (char *,int); 

void init_dict() 
{ 
    initialized = 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]; 
    table[hsh] = ptr; 

} 


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

Answer 5

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.

Answer 6

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

Answer 7

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); 
} 

Answer 8

aquí hay un implemento rápido, lo usé para obtener una 'Matriz' (sruct) de una cuerda. se puede tener una variedad más grande y cambiar sus valores en la carrera 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; 
} 

Answer 9

GLib y gnulib

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

• GLib: https://developer.gnome.org/glib/ por el proyecto GNOME. Varios contenedores documentados en: https://developer.gnome.org/glib/stable/glib-data-types.html incluyendo "tablas hash" y "árboles binarios equilibrados". Licencia: LGPL

• gnulib: https://www.gnu.org/software/gnulib/ por el proyecto GNU. Debes copiar pegar la fuente en tu código. Varios contenedores documentados en: https://www.gnu.org/software/gnulib/MODULES.html#ansic_ext_container incluyendo "rbtree-list", "linkedhash-list" y "rbtreehash-list". Licencia GPL.

Consulte también: Are there any open source C libraries with common data structures?

Answer 10

me sorprende que nadie ha mencionado hsearch/hcreate conjunto de bibliotecas que si bien no está disponible en Windows, pero es estándar con Linux/GNU

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