Discussion :

[Layno]

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 :

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

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 :

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
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 :

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
 
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 :

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

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.

[sambia39]

Bonsoir

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:

Une table de hachage est un tableau qui contient des clés permettant d'identifier de façon unique une valeur et c'est clé ne sont pas ranger dans l'ordre . Quant à la gestion des collisions dont vous parler , ce n'est rien d'autre que la création d'une liste chainée à l'endroit de la collision rencontrer.
Sans trop lire le code sources, avez-vous pensé à allouer de la mémoire pour le stockage de vos mots ?

Code :

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

1
2
3
4
5
	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  ?????

[Layno]

Bonsoir,

Merci de votre réponse, ça venait effectivement de l'allocation mémoire pour le mot ainsi que la copie du mot et pas du pointeur. Enfin bref, je vous remercie de votre aide!