Table de hachage de listes
Bonjour,
J'étudie le C depuis début Septembre dernier dans le cadre de mes études, et dernièrement, j'ai reçu comme projet d'élaborer un programme utilisant une table de hachage. Ayant déjà réalisé un programme utilisant un tel procédé je ne me suis pas trop inquiété. Toutefois, si je viens vers vous aujourd'hui c'est que je bloque!
Le principe est le suivant, on dispose d'un fichier de mots (ici "dico1.txt") qui sont organisés un par ligne, et on doit les rentrer dans la table de hachage sous forme de liste chaînée histoire d'éviter les collisions. Seulement cela est utilisé pour implémenter plus tard des successeurs de ces mots qui représentent des mots différant d'une lettre du mot précédent. On a donc plusieurs structures:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
typedef struct t_sommet {
char* mot;
struct l_succ {
struct t_sommet * val;
struct l_succ* suiv;
}* liste_succ;
} T_SOMMET; // Un sommet est à la base de la table de hachage, il contient le mot et la liste des successeurs
typedef struct l_succ* L_SUCC;
typedef L_SUCC L_SOMMET;
typedef L_SOMMET Liste; |
J'ai donc réalisé un ensemble de programmes permettant d'implanter ces mots dans la fameuse table:
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
int hashcode(unsigned char* chaine, int taille_table){
int i = 1, j = 31;
unsigned int tot = (unsigned int) chaine[0];
while (chaine[i] != '\0'){
tot = (tot + j*(tolower(chaine[i])))%taille_table;
j = (j*31)%taille_table;
i++;
}
return tot;
} // Prend un mot en argument ainsi que la taille de la table et renvoi l'ID de la table de hachage
T_SOMMET* creer_psommet(char* mot){
T_SOMMET* new = calloc(1, sizeof(T_SOMMET));
if(new == NULL)
{
perror("Error allocating sommet");
return(NULL);
}
new->mot = mot;
new->liste_succ = NULL;
return new;
} // Alloue la place mémoire pour un pointeur de sommet et lui donne la val mot
L_SOMMET* hashtable(L_SOMMET* table, char* fichier, int taille_table){
int n;
unsigned int k; // ID de la table de hachage
L_SOMMET p;
FILE* dictionnaire = fopen(fichier, "r"); // Ouverture du dictionnaire de mots
if(dictionnaire == NULL)
{
perror("Error opening file");
return(NULL);
}
unsigned char * word = malloc(1*sizeof(unsigned char)); // Allocation du char* pour le parcours
if(word == NULL)
{
perror("Error allocating mot");
return(NULL);
}
while (fgets(word, 64, dictionnaire) != NULL){ // On parcours le fichier texte
n = strlen(word);
if (word[n-1] < 32) word[n-1] ='\0'; // On enlève le caractère si celui-ci est un saut de ligne, espace,...
k = hashcode(word, taille_table);
printf("Hashcode: %i, ", k);
p = table[k];
if(table[k] == NULL){ // Si la liste à l'ID k est nulle alors on alloue une place mémoire pour une liste L_SOMMET et on lui ajoute le T_SOMMET* avec le mot lu
table[k] = malloc(1*sizeof(L_SOMMET));
if (table[k] == NULL){
perror("Erreur d'allocation ajouter_queue");
return NULL ;
}
table[k]->val = creer_psommet(word);
table[k]->suiv = NULL;
}
else{ // Sinon on va au dernier élément de la liste et on lui rajoute le T_SOMMET* créé
while(p->suiv != NULL)
{
p = p->suiv;
}
table[k] = malloc(1*sizeof(L_SOMMET));
if (table[k] == NULL){
perror("Erreur d'allocation ajouter_queue");
return NULL ;
}
table[k]->val = creer_psommet(word);
table[k]->suiv = NULL;
}
//ajouter_queue(mot, table[k]);
printf("mot de la table: %s\n", (table[k]->val)->mot);
printf("ID 3: %s\n", (table[3]->val)->mot);
}
printf("ID 4: %s\n", (table[4]->val)->mot);
fclose(dictionnaire);
return table;
} |
Et enfin voici mon main qui sert juste de test:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
main()
{
char* mot = calloc(1, sizeof(char));
int taille_table = 10, k;
L_SOMMET* table = malloc(taille_table*sizeof(L_SOMMET));
table = hashtable(table, "dico1.txt" , taille_table);
table[1]->val->mot = "test"; // Test d'écriture d'un mot dans la table ERREUR génère un segfault
printf("mot à l'id 1: %s", table[1]->val->mot); // Lecture du mot rentré ligne au-dessus
printf("mot à l'id 2: %s", table[2]->val->mot); // Lecture d'un autre mot
printf("Entrez l'id:");
scanf("%i", &k);
while(k != 20){
printf("mot à l'id %i: %s", k, table[k]->val->mot); // Lecture de mots dans la table de hachage
scanf("%i", &k);
}
} |
J'ai une erreur de segmentation en fin de programme qui vient du test d'écriture dans le main. De plus, je me suis rendu compte que tous les mots changent quelque soit leur ID lorsque j'écris un nouveau mot (ie table[k]->val = creer_psommet(word);).
Le code compile lorsque j'utilise seulement -o mais lorsque je met -Wall il me met: /usr/bin/ld: erreur dans test(.eh_frame); aucune table .eh_frame_hdr ne sera créée.
Je ne sais pas d'où vient cette erreur et je suis un peu perdu! Je vous joins en plus mon Makefile dans l'espoir que vous puissiez m'aider!
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
test: main.o liste.o mots.o
gcc -g main.o liste.o mots.o -o -Wall test
main.o: main.c liste.c mots.c
gcc -c main.c liste.c mots.c
liste.o: liste.c
gcc -c liste.c
mots.o: mots.c liste.c
gcc -c mots.c liste.c
clean:
rm *.o |
Cordialement,
Un étudiant en détresse.
