Moyen rapide de mettre en Œuvre Dictionnaire en C

Question

L'une des choses qui me manque alors que l'écriture de programmes en C est un dictionnaire de données de la structure. Quel est le moyen le plus pratique de mettre en œuvre un dans C? Je ne recherche pas la performance, mais la facilité de codage à partir de zéro. Je ne veux pas qu'il soit générique, soit -- quelque chose comme string->int fera. Mais je ne veux pas qu'il soit capable de stocker un nombre quelconque d'éléments.

C'est à considérer plus comme un exercice. Je sais qu'il y a de la 3e partie de bibliothèques 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, vous pouvez mettre en œuvre un dictionnaire de satisfaire les exigences ci-dessus.

Answer 1

La Section 6.6 du Langage de Programmation C présente un simple dictionnaire (hashtable) structure de données. Je ne pense pas qu'un dictionnaire de la mise en œuvre pourrait obtenir pas 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 valeurs de hachage de deux chaînes de collision, il peut conduire à un O(n) temps de recherche. Vous pouvez réduire la probabilité d'capot de collisions par l'augmentation de la valeur de HASHSIZE. Pour une discussion complète de la structure de données, veuillez consulter le livre.

Answer 2

Le plus rapide serait d'utiliser un existant déjà mise en œuvre, comme le Lever du soleil ou, à un niveau légèrement inférieur, uthash.

Et, si vous 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'obligation de transmettre les avis de droit d'auteur, vous êtes assez bien illimité dans ce que vous pouvez faire avec lui.

Answer 3

Créer une simple fonction de hachage et dont certains sont liés à des listes de structures , en fonction de la table de hachage , d'attribuer liste liée à insérer la valeur dans . Utiliser le hachage de la récupérer .

J'ai fait une simple mise en œuvre il y a quelque temps :

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

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

typedef struct dict dict;
dict *tableau[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,key_name);


 ptr->suivant = (struct dict *)tableau[sas];
 tableau[sas] = ptr;

}


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

Answer 4

voici un rapide à mettre en œuvre, je l'ai utilisé pour obtenir une "Matrice" (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;
}

Answer 5

Une table de hachage est la traditionnelle mise en œuvre d'un simple "Dictionnaire". Si vous n'avez pas de soins sur la vitesse ou la taille, il suffit de google pour cela. Il ya beaucoup de disponibles gratuitement implémentations.

voici le premier que j'ai vu -- en un coup d'œil, il semble ok pour moi. (c'est assez basique. Si vous voulez vraiment de tenir une quantité illimitée de données, alors vous aurez besoin d'ajouter un peu de logique à "realloc" la table de la mémoire à mesure qu'il grandit.)

bonne chance!