Discussion :

[étoile de mer]

bonjour à tous,
J'ai une question à proppos des tableaux dynamiques:
J'ai crée une tableau de hachage où j'ai stockes des paires de mots à partir d'un fichier texte lu, et là on me conseille de faire des tableau dynamiques pour cette table de hachage ou je vais stocker des pointeurs de structures de mots.
Là franchement je vois pas pourkoi des tableau et pourquoi pas un seul tableau dynamiques .
merci

[AndreiS]

Si je comprends bien, c'est le problème de conflits de hachage: la fonctionne de hachage peut retourner le même résultat pour deux mots différents. Donc dans ton tableau pour chacun 'hash' tu stockes plusieurs paires de mots et quand on cherche la valeur pour une clé, il faut que tu vérifie tous les pairs stockées pour son 'hash'.

[étoile de mer]

Re,
Là j'ai creé un tableau dynamique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct tableauDynamique_struct
{
	int *tab;
	size_t taille;
	size_t capacite;
};

où je vais stocker la listes de structure

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
struct  Dsequence
{
MotCompact *p2seq;
MotCompact *pMotGauche;
 MotCompact *pMotDroit;
};

je trouve un probleme dans l'operation du remplissage du tableau :
en fait je parcours la table de hachage qui contient des paires de mots et là je dois remplir la structure par ces paire de mots
voilà la fonction où je bloque qui ajoute un element au tableau dynamique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit))
{
	assert(pThis->taille <= pThis->capacite);
 
	/* Agrandir le tableau si besoin est. */
	if(pThis->taille == pThis->capacite)
	{
		size_t nouvelleCapacite = (pThis->capacite < 4 ? 4 : (size_t)(pThis->capacite*1.5));
		if(realloc_int(&pThis->tab, nouvelleCapacite) >= 0)
		{
			pThis->capacite = nouvelleCapacite;
		}
		else
			return -1;
 
	}
 
	/* ajouter */
	pThis->tab[ pThis->taille++ ] = nouvelleValeur;
	return 0;
}

pour ajouter je vois pas quoi faire?
des idées svp?
merci

[LittleWhite]

Bonjour,

Pour le fonction d'ajout, il y a deux manières de voir la chose.

Une que je dirai de dangereuse, qui serai de remplir une structure avec directement les pointeurs qui sont passer à la fonction:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit))
{
     // ...
 
     /* ajouter */
     {
          Dsequence ds;
          ds.p2seq = seq;
          ds.pMotGauche = pMotGauche;
          ds.pMotDroit = pMotDroit;
 
         pThis->tab[ pThis->taille++ ] = ds;
     }
}

Sinon, avec une gestion de la mémoire moins risqué, mais qui prend un peu de temps, et qui faut faire aussi très attention à la libération:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
int TableauDynamique_struct_ajouter(struct tableauDynamique_int *pThis,char *seq,char *pMotGauche,char *pMotDroit))
{
     // ...
 
     /* ajouter */
     {
          Dsequence ds;
          ds.p2seq = malloc ( strlen(seq) * sizeof(char) );
          if ( ds.p2seq == NULL )
         {
                  return -1;
         }
         strcmp(ds.p2seq, p2seq);
 
          ds.pMotGauche = malloc ( strlen(pMotGauche) * sizeof(char) );
          if ( ds.pMotGauche == NULL )
         {
                  return -1;
         }
         strcmp(ds.pMotGauche, pMotGauche);
 
          ds.pMotDroit = malloc ( strlen(pMotDroit) * sizeof(char) );
          if ( ds.pMotDroit == NULL )
         {
                  return -1;
         }
         strcmp(ds.pMotDroit, pMotDroit);
 
         pThis->tab[ pThis->taille++ ] = ds;
     }
}

Sinon, AndreiS a soulevé un bon point, qu'il ne faut pas oublier dans les table de hachage. Lorsque l'on tombe sur deux mêmes clés, il faut garder les deux valeurs pour cette clé ( utilisation d'une liste chainée de préférence ).

[étoile de mer]

Re,
Là on ma dit qu'il faut plusieurs tableau dynamiques, parce que c'est sur ça que repose une table de hachage: Elle sert à répartir les données sur différents conteneurs de même type, pour accélérer la recherche.

[Médinoc]

attention étoile de mer, "tab" n'a pas le bon type ici.
Il faut un pointeur de struct Dsequence, pas un pointeur de int...