Moyen rapide D'implémenter le dictionnaire en C

L'une des choses qui me manquent lors de l'écriture de programmes en C est une structure de données de dictionnaire. Quel est le moyen le plus pratique d'en implémenter un en C? Je ne cherche pas la performance, mais la facilité de le coder à partir de zéro. Je ne veux pas que ce soit générique non plus-quelque chose comme string - >int fera l'affaire. Mais je veux qu'il soit capable de stocker un nombre arbitraire d'éléments.

C'est plutôt un exercice. Je sais qu'il existe des bibliothèques 3ème partie disponibles que l'on peut utiliser. Mais considérons un instant, qu'ils n'existent pas. Dans une telle situation, quel est le moyen le plus rapide de mettre en œuvre un dictionnaire répondant aux exigences ci-dessus.

90
demandé sur Rohit 2010-12-08 08:08:20

10 réponses

Section 6.6 de le langage de programmation C présente une structure de données de dictionnaire simple (hashtable). Je ne pense pas qu'une implémentation de dictionnaire utile pourrait être plus simple que cela. Pour votre commodité, je reproduis le code ici.

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

Notez que si les hachages de deux chaînes entrent en collision, cela peut conduire à un temps de recherche O(n). Vous pouvez réduire la probabilité de collisions en augmentant la valeur de HASHSIZE. Pour une discussion complète de la structure des données, veuillez consulter le livre.

90
répondu Vijay Mathew 2014-12-22 15:21:33

Le moyen le plus rapide serait d'utiliser une implémentation déjà existante, comme uthash .

Et {si vous[2]}vraiment voulez coder vous-même, les algorithmes de uthash peut être examiné et ré-utilisés. Il est sous licence BSD donc, autre que l'exigence de transmettre l'avis de copyright, vous êtes assez bien illimité dans ce que vous pouvez faire avec elle.

12
répondu paxdiablo 2017-08-20 19:39:30

Pour faciliter la mise en œuvre, il est difficile de battre naïvement la recherche dans un tableau. Mis à part une vérification d'erreur, il s'agit d'une implémentation complète (non testée).

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);
}
4
répondu Paul Hankin 2013-04-21 08:08:57

Créez une fonction de hachage simple et certaines listes de structures liées , en fonction du hachage, attribuent la liste liée à insérer la valeur . Utilisez le hachage pour le récupérer aussi .

J'ai fait une implémentation simple il y a quelque temps:

...
#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;
}
3
répondu abc def foo bar 2010-12-08 05:25:17

Voici un implémentation rapide, je l'ai utilisé pour obtenir une 'Matrix'(sruct) à partir d'une chaîne. vous pouvez avoir un grand tableau et changer ses valeurs sur la course aussi:

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;
}
2
répondu dagoltz 2013-05-04 12:07:35

Une table de hachage est l'implémentation traditionnelle d'un simple "dictionnaire". Si vous ne vous souciez pas de la vitesse ou de la taille, juste google pour cela . Il existe de nombreuses implémentations disponibles gratuitement.

Voici le premier que j'ai vu -- en un coup d'œil, ça me semble correct. (c'est assez basique. Si vous voulez vraiment qu'il contienne une quantité illimitée de données, vous devrez ajouter de la logique à "realloc" la mémoire de la table à mesure qu'elle grandit.)

Bonne chance!

1
répondu Lee 2010-12-08 05:15:49

GLib et gnulib

Ce sont vos meilleurs paris si vous n'avez pas d'exigences plus spécifiques, car ils sont largement disponibles, portables et probablement efficaces.

Voir Aussi: Existe-t-il des bibliothèques C open source avec des structures de données communes?

1

Je suis surpris que personne n'ait mentionné hsearch / hcreate Ensemble de bibliothèques qui n'est pas disponible sur windows, mais qui est mandaté par POSIX, et donc disponible dans les systèmes Linux / GNU.

Le lien a un exemple de base simple et complet qui explique très bien son utilisation.

Il a même thread variante sûre, est facile à utiliser et très performant.

1
répondu fayyazkl 2018-04-26 10:14:01

Le hachage est la clé. Je pense utiliser la table de recherche et la clé de hachage pour cela. Vous pouvez trouver de nombreuses fonctions de hachage en ligne.

0
répondu ashmish2 2010-12-08 05:27:07

La méthode la plus rapide serait d'utiliser l'arbre binaire. Son pire cas est également seulement O (logn).

0
répondu cprogrammer 2013-04-21 06:18:44