Dans le problème, nous manipulons des graphes, dont les noeuds sont des entiers :
Code:
1
2
3
4
5
6
7
8
9
| typedef struct noeud {
int n;
struct noeud **tab; /*Tableau de pointeurs sur d'autres noeuds
transitions sortantes du noeud)*/
}Noeud;
typedef struct {
Noeud *racine;//Designe un noeud du graphe
}Graphe; |
On supposera que tous les noeuds du graphe sont accessibles à partir de celui désigné par par le pointeur racine de la structure Graphe.
Sur la figure, le noeud racine contient 1 (montré par la flèche entrante). Même si ce n'est pas le cas sur la figure, deux noeuds différents peuvent contenir le me entier.
Code:
1
2
3
4
5
6
7
8
9
10
|
--------|
| |
| 5---->4
| ^ \ ^^
v/ \ / |
->1 / |
\ / \ |
v / vv
3---->2 |
Dans la suite du problème on supposera que tous les graphes ont un nombre de noeuds majorés par MAXNOEUDS.
On souhaite sauvegarder et relire la structure de graphe dans un fichier texte. Les noeuds y sont décrits en parenthèses. L'entier contenu dans le noeud est écrit après la parenthèse ouvrante. Ensuite, chacun des noeuds fils(peu importe l'ordre), à nouveau entre parenthèse. La sauvegarde est réalisée en effectuant un parcours en profondeur du graphe. Au fur et à mesure que les noeuds sont rencontrés pendant le parcours, ils sont mis dans une table de hachage, qui permet :
-de savoir qu'on est déjà passé par le noeud
-de lui associer un numéro de passage(le premier noeud par lequel le parcours en profondeur est passé a numéro 1, le second 2, etc)
Quand le fils d'un noeud a déjà été rencontré lors du parcours en profondeur, on le remplace par son numéro de passage, écrits entre crochets, dans le fichier.
Par exemple, si le parcours en profondeur passe dans l'ordre par les noeuds contenant 1,3,2,4 et 5, le contenu du fichier sera (1(3(2(4[3][1]))[4])(5[2][4])
Pour éviter d'implanter les tables de hachages, on fait une recherche sur le Web, et on trouve un module C implantant les tables de hachages de manière générique. Le module est composé de 2 fichiers,
tableHachage.h et
tableHachage.c. Le fichier
tableHachage.h est le suivant :
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
| #ifndef _TABLEHACHAGE_H
#define _TABLEHACHAGE_H
/* Ici pleins de typedef qui ne nous interessent pas, y compris celui
pour un type s'appelant _tableHachage, que nous n'utiliserons jamais
*/
...
/* Le type pour les tables de hachage: c'est un pointeur, mais on ne sait pas
exactement comment sont implantées les tables de hachage, et d'ailleurs on s'en moque
*/
typedef _tableHachage * tableHachage;
/* Cette fonction crée une table de hachage dont on précise la taille.
Retourne 1 si tout se passe bien, 0 sinon;
Au retour de la fonction, *th désigne la table de hachage crée
*/
extern int creerTableHachage(size_t taille,
unsigned int (*fonctionHachage)(void *clef),
unsigned int (*cmpClefs)(void *clef1, void *clef2),
tableHachage *th);
/*Cette fonction insère l'association entre clef et valeur dans la table de hachage th.
Si la clef était déjà présente dans la table, l'ancienne valeur qui lui était associée est écrasé
par la nouvelle.
Elle retourne 1 si l'insertion s'est bien déroulé, 0 sinon
*/
extern int insereDansTableHachage(const void *clef,
const void *valeur,
tableHachage th);
/*Cette fonction retourne un pointeur sur la valeur associée à clef si elle existe, NULL sinon
*/
extern void *rechercheDansTableHachage(const void *clef,
const tableHachage th);
/*Libération de l'espace mémoire pris par une table de hachage
Au retour de la fonction, *th vaut NULL
*/
extern void libereTableHachage(tableHachage *th);
#endif |
Dans la suite, nous nous interdisons de modifier les fichiers récupérés sur le Web
Exercices :
-Ecrire une fonction
int ecrireGraphe(const Graphe *g, FILE *fdo) qui écrit le graphe désigné par
g dans le flot
fdo qu'on suppose ouvert dans le bon mode
