Moyen rapide d'implémenter le dictionnaire en C

Une des choses qui me manque 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 recherche pas la performance, mais la facilité de le coder à partir de zéro. Je ne veux pas non plus que ce soit générique - quelque chose comme string-> int fera l'affaire. Mais je veux qu'il puisse stocker un nombre arbitraire d'articles.

Il s'agit plutôt d'un exercice. Je sais qu'il existe des bibliothèques tierces disponibles que l'on peut utiliser. Mais considérez un instant qu'ils n'existent pas. Dans une telle situation, quel est le moyen le plus rapide d'implémenter un dictionnaire répondant aux exigences ci-dessus.

La section 6.6 du langage de programmation C présente une structure de données de dictionnaire simple (table de hachage). Je ne pense pas qu'une implémentation de dictionnaire utile puisse ê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 entraîner un O(n)temps de recherche. 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.

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

Et, si vous voulez vraiment le coder vous-même, les algorithmes de uthashpeuvent être examinés et réutilisés. Il est sous licence BSD, donc, mis à part l'obligation de transmettre l'avis de droit d'auteur, vous êtes pratiquement illimité dans ce que vous pouvez en faire.

Pour faciliter la mise en œuvre, il est difficile de battre naïvement la recherche dans un tableau. Outre une vérification des erreurs, 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);
}

Créez une fonction de hachage simple et des listes de structures liées, en fonction du hachage, attribuez la liste liée dans laquelle insérer la valeur. Utilisez également le hachage pour le récupérer.

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

...
#define K 16 // coefficient de chaînage

struct dict
{
    char * nom; / * nom de la clé * /
    int val; /* valeur */
    struct dict * suivant; / * champ de lien * /
};

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


void putval (char *, int);

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


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

}


int getval (char * nom_clé)
{   
    int hsh = hash (nom_clé);   
    dict * ptr;
    pour (ptr = table [hsh]; ptr! = (dict *) 0;
        ptr = (dict *) ptr-> suivant)
    if (strcmp (ptr-> nom, nom_clé) == 0)
        return ptr-> val;
    return -1;
}

GLib et gnulib

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

• GLib: https://developer.gnome.org/glib/ par le projet GNOME. Plusieurs conteneurs documentés à l' adresse : https://developer.gnome.org/glib/stable/glib-data-types.html, y compris «Hash Tables» et «Balanced Binary Trees». Licence: LGPL

• gnulib: https://www.gnu.org/software/gnulib/ par le projet GNU. Vous êtes censé copier-coller la source dans votre code. Plusieurs conteneurs documentés sur: https://www.gnu.org/software/gnulib/MODULES.html#ansic_ext_container, y compris "rbtree-list", "linkedhash-list" et "rbtreehash-list". Licence GPL.

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

voici un outil rapide, je l'ai utilisé pour obtenir une 'Matrix' (sruct) à partir d'une chaîne. vous pouvez également avoir un tableau plus grand et modifier ses valeurs en cours d'exécution:

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

Je suis surpris que personne n'ait mentionné l' ensemble de bibliothèques hsearch / hcreate qui, bien que n'étant pas disponible sur Windows, mais 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 une variante thread-safe, est facile à utiliser et très performant.

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, recherchez simplement sur Google . Il existe de nombreuses implémentations disponibles gratuitement.

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

bonne chance!

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

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