printf une structure hashtable

Version imprimable

Bonjour à tous,

Voici transcrit de K&Ritchie:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
static struct nlist *hashtab[HASHSIZE];
---------------------------------
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 definiition  */
   if ((np->defn = strdup(defn)) == NULL)
                        return NULL;
return np;
}
---------------------------------
void printHtable(struct nlist *np)
{
   for (; np != NULL; np = np->next)
     printf ("print   %-15s %-35s\n",np->defn, np->name);
}

---------------   main  ------------------
char *zero[4][2] = {
   {"Zero, world.", "zero"},
   {"Il était une fois dans la prairie.", "un"},
   {"Il était deux fois dans la prairie.", "deux"},
   {"Il était trois fois dans la prairie.", "trois"}
};
for (i=0; i<4;   i++){
         hashtab[i] = install(zero[i][0], zero[i][1]);
         printf ("for   %-15s %-35s\n",hashtab[i]->defn, hashtab[i]->name);
}

printHtable(hashtab[0]);
----------  fin de main -----------------------

printHtable et main sont de moi.

Quelle est la façon de faire pour mettre les 4 phrases dans un hashtable et ensuite l'imprimer?
:oops:

14/05/2009, 11h34
Médinoc

Je ne comprends pas la question.
14/05/2009, 13h53
J4e8a16n

Code:

printf ("print %-15s %-35s\n",np->defn, np->name);

Printf n'imprimera que la première ligne {"Zero, world.", "zero"} envoyée dans la hashtable et pas les autres.

Pourquoi?

Tu dois imbriquer cette boucle dans une boucle qui parcoure le tableau:

Code:

1
2
3
4
5
6
7
8
9
10
void printHtable(struct nlist **table)
{
   size_t i;
   for(i=0 ; i<HASHSIZE ; i++)
   {
      struct nlist *nb;
      for(np = table[i] ; np != NULL ; np = np->next)
         printf ("print   %-15s %-35s\n",np->defn, np->name);
   }
}

14/05/2009, 18h08
J4e8a16n

Mais de cette façon, on doit parcourir toute la table même si elle n'est remplie qu'au quart?

JPD
14/05/2009, 18h09
Médinoc

Oui, car tu ne sais pas quelles cases sont remplies.
14/05/2009, 18h24
J4e8a16n

J'imagine que ce n'est efficace que pour un nombre de données minimum.

JPD
14/05/2009, 19h08
Médinoc

N'oublie pas qu'une table de hachage n'est pas faite à la base pour être parcourue: Elle est faite pour être consultée.

Et la consultation est (taille de la table) fois plus rapide que sur une liste chaînée.
Paradoxalement, on ne devrait pas dire que ça réduit la complexité, pourtant, pour une table de hachage correctement dimensionnée* (et avec une fonction de hachage), on assimile la complexité d'une consultation de table de hachage à O(1).

*Note que je n'ai aucune idée du rapport idéal entre taille de la table et nombre d'éléments qu'on prévoit d'y mettre. Sans doute un peu plus que 1:1 ...
14/05/2009, 22h29
J4e8a16n

Évidemment là . . .

c'est la joie.
:D