Moyen rapide D'implémenter le dictionnaire en C

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.

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

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

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

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!

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.

• GLib: https://developer.gnome.org/glib/ par le projet GNOME. Plusieurs conteneurs documentés à: https://developer.gnome.org/glib/stable/glib-data-types.html y compris "Tables de hachage" et "arbres binaires équilibrés". 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 à: 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?

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.

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.

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