Table de hachage
stroumpf
-
stroumpf -
stroumpf -
Bonjour,
jai un ptit probleme, je dispose d'une liste chainée contenant des mots et la liste des positions et le liste des elements. et compte les stocker dans une table de hachage.
ya til quelqun qui peut m'aider
merci
jai un ptit probleme, je dispose d'une liste chainée contenant des mots et la liste des positions et le liste des elements. et compte les stocker dans une table de hachage.
ya til quelqun qui peut m'aider
merci
Configuration: Windows Vista Internet Explorer 7.0
8 réponses
-
Salut,
Pour faire une table de hachage chaînée tu dois tous d'abord d'écrire une fonction de hash.
Ensuite tu dois créer un tableau de pointeur de type d'élément de ta liste
Quand tu va passer le terme à insérer à la fonction de hash l'entier retourner sera l'index de tableau de pointeur où ton élément sera inséré
En bref chaque élément de ton tableau de pointeur sera la tête d'une liste chaînée.
typedef struct L { char donnee[100]; struct *suivant; }Liste; Liste **TdH; TdH = (Liste **) malloc (conteneurs * sizeof(Liste *);
// le nombre de conteneurs doit être choisi en général comme un nombre premier assez eloigné d'une puissance de deux
Il ne faut pas non plus oublié le facteur de charge d'une table de hash
F = éléments / conteneurs
si tu as 10000 éléments et le nombre de conteneurs sera par exemple 997 le facteur de charge
F = 10000 / 997 = 10
ce qui veut dire que un conteneur peut s'attendra à contenir au maximum 10 éléments.
En réalité on n'obtiendra pas une table de hash uniforme, mais on arrive plus au moins à la valeur de facteur de charge. -
Par exemple une insertion donnera quelque chose comme ça
cle = hash(donnee); InsertionEnTete(TdH[cle],donnee);
-
Si tu diras d'où collecte tu les données et comment tu veux les insérer dans la table de hash, ça sera plus facile de comprendre. ;-)
-
ok; merci, c'est gentil de ta part.
jai fait la 1ere partie du programme, ne fait je possede maintenant un liste des mots , leurs positions dans la phrase et leurs num de ligne, donc maintenant il me reste de placer ces mots dans une table de hachage avec leurs informations(leurs positions dans la phrase et leurs num de ligne)
voila , c tout, ce travail est pour demain ;)
merci
-
-
As-tu écrit ta fonction de hash?
-
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question -
Bon pas encore, mais lami je trouve un souci c'est que je pense que le mot lui meme devient la clé de hachage, non?
té d'accords? -
Exactement. C'est comme ça que tu trouves l'index du tableau où tu dois insérer le mot
-
Voici un exemple avec une fonction simple
lami20j@debian:~/trash$ gcc -o hash_cle hash_chaine.c lami20j@debian:~/trash$ ./hash_cle Entrez une clé : azerty Cle = azerty; Valhash : 96 lami20j@debian:~/trash$ ./hash_cle Entrez une clé : lami20j Cle = lami20j; Valhash : 8 lami20j@debian:~/trash$ ./hash_cle Entrez une clé : hashage Cle = hashage; Valhash : 15 lami20j@debian:~/trash$ ./hash_cle Entrez une clé : stroumpf Cle = stroumpf; Valhash : 60 lami20j@debian:~/trash$
Donc tu remarque bien que pour chaque terme j'ai obtenu un indice de tableau où le mot sera insérer
-
-
voila ce que j'ai trouvé comme exemple:
int func_h(ELEMENT c,struct table_hachage *h,int a)
{
double res=0;
int i;
ELEMENT p=c;/*copie de c pour ne pas le modifier lors du calcul*/
for(i=0;*p!='\0';p++,i++)
{
res+= pow(a,i)*(*p);/*calcul de la somme de proche en proche*/
}
i=abs((int)res%(h->N));/*res peu etre negatif d'où l'utilisation de abs(),on convertit le resultat en entier*/
return i;/* on retourne un entier en non un entier double precision*/
}
mais je comprends pas son fonctionnement
merci
-
-
Voici un exemple
#include<stdio.h> #include<stdlib.h> #define TAILLE 997 unsigned hash_cle(char *chaine); int main() { char *chaine; unsigned int val; if((chaine = (char *) malloc (50 * sizeof(char))) == NULL) return -1; printf("Entrez une clé : "); scanf("%s",chaine); val = hash_cle(chaine); printf("Cle = %s; ValeurHash : %u\n",chaine,val); return -1; } unsigned hash_cle(char *chaine){ unsigned i; for(i=0;*chaine != '\0';++chaine) i = *chaine + 31 * i; return i%TAILLE; }-
-
Bonsoir Lami,
jai essayé mais ca na pas marché :(
il maffiche rien en faite, ni la valeur de la clé, ni rien.
merci
int fonctHachage(liste_mot* s)
{ int val;
liste_mot* m=s;
char *mot;
mot=m->mot;
while(m!=NULL)
{
val = hash_cle(mot);
}
printf("%d", val);
printf("gggggggggggggggggggggggggg");
return(val);
}
unsigned hash_cle(char *chaine){
unsigned i;
for(i=0;*chaine != '\0';++chaine)
i = *chaine + 31 * i;
return i%TAILLEMAX;
}
int main(int argc, char *argv[])
{ char c;
int A;
int val;
liste_mot* s =NULL;
Trouver_mots (&s,"C:\\Documents\\text.txt" );
Affiche_mots(s);
printf("\n\n la liste filtree \n\n");
frequent( &s , 1);
Affiche_mots(s);
//calcul_nbre_mot(s);
// printf("%d",A);
val=fonctHachage(s);
scanf("%c",c);
return 0;
}
La fonction ne marche pas, il naccede pas a la fonction
je c pas pk?
-
