Exo sur Graphe

Exo sur Graphe - C - Programmation

Marsh Posté le 10-08-2006 à 10:21:51    

Bonjour,
 
J'aurais besoin d'aide pour savoir si le code que j'ai écrit est correct.
Je ne peux pas le vérifier par moi-même car dans l'énoncé, il n'y a que le prototype des fonctions et pas leur code
 
Merci par avance
 

Citation :


Dans le problème, nous manipulons des graphes, dont les noeuds sont des entiers :  

Code :
  1. typedef struct noeud {
  2.   int n;
  3.   struct noeud **tab; /*Tableau de pointeurs sur d'autres noeuds  
  4.   transitions sortantes du noeud)*/
  5. }Noeud;
  7. typedef struct {
  8.   Noeud *racine;//Designe un noeud du graphe
  9. }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.
 
 
 

 
   --------|
  |          |
  |  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. #ifndef _TABLEHACHAGE_H
  2. #define _TABLEHACHAGE_H
  4. /* Ici pleins de typedef qui ne nous interessent pas, y compris celui  
  5. pour un type s'appelant _tableHachage, que nous n'utiliserons jamais
  6. */
  7. ...
  9. /* Le type pour les tables de hachage: c'est un pointeur, mais on ne sait pas  
  10. exactement comment sont implantées les tables de hachage, et d'ailleurs on s'en moque
  11. */
  13. typedef _tableHachage * tableHachage;
  15. /* Cette fonction crée une table de hachage dont on précise la taille.
  16. Retourne 1 si tout se passe bien, 0 sinon;
  17. Au retour de la fonction, *th désigne la table de hachage crée
  18. */
  19. extern int creerTableHachage(size_t taille,
  20.                                          unsigned int (*fonctionHachage)(void *clef),
  21.                                          unsigned int (*cmpClefs)(void *clef1, void *clef2),
  22.                                          tableHachage *th);
  24. /*Cette fonction insère l'association entre clef et valeur dans la table de hachage th.
  25. Si la clef était déjà présente dans la table, l'ancienne valeur qui lui était associée est écrasé
  26. par la nouvelle.
  27. Elle retourne 1 si l'insertion s'est bien déroulé, 0 sinon
  28. */
  29. extern int insereDansTableHachage(const void *clef,
  30.                                   const void *valeur,
  31.                                   tableHachage th);
  33. /*Cette fonction retourne un pointeur sur la valeur associée à clef si elle existe, NULL sinon
  34. */
  35. extern void *rechercheDansTableHachage(const void *clef,
  36.                                        const tableHachage th);
  38. /*Libération de l'espace mémoire pris par une table de hachage
  39. Au retour de la fonction, *th vaut NULL  
  40. */
  41. extern void libereTableHachage(tableHachage *th);
  43. #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


Code :
  1. /*0:OK, 1:erreur*/
  2. int ecrireGraphe(const Graph *g, FILE *fdo)
  3. {
  4.   tableHachage th;/*table de hachage*/
  5.   int i;/*indice de boucle*/
  6.   char *val;/*valeur associee a une cle*/
  8.   /*Creation de la table hachage*/
  9.   if((creerTableHachage(MAXNOEUDS, (*fonctionHachage)(void *),
  10.   (*cmpClefs)(void *, void *), &th)) == 0)
  11.     return 1;
  12.  
  13.   val = recherche(g->racine->n,th);
  14.   /*le noeud n'a pas encore ete visite*/
  15.   if(val == NULL)
  16.     {
  17.       /*on insere dans la table car non present*/
  18.       if(insereDansTableHachage(g->racine->n,val,th) == 0)
  19. return 1;
  20.       /*affichage du noeud dans le flux*/
  21.       fprintf(fdo,"(%d",g->racine->n);
  22.     }
  23.   /*le noeud a deja ete visite*/
  24.   else
  25.     {
  26.       /*affichage du numero de passage*/
  27.       fprintf(fdo,"[%d]",val);
  28.     }
  29.   /*parcours des fils*/
  30.   for(i=0; i<MAXNOEUDS; i++)
  31.     return ecrireGraphe(g->racine->tab[i], fdo);
  32.   fprintf(fdo," )" );
  34.   return 0;
  35. }

Message cité 1 fois
Reply

Marsh Posté le 10-08-2006 à 10:21:51   

Reply

Marsh Posté le 10-08-2006 à 10:23:44    

Gattuso a écrit :

Je ne peux pas le vérifier par moi-même car dans l'énoncé, il n'y a que le prototype des fonctions et pas leur


 
Comment ca tu ne peux pas vérifier ton code ?
Tu ne peux pas faire un prog qui appelle ta fonction ?

Message cité 1 fois
Reply

Marsh Posté le 10-08-2006 à 10:41:44    

_darkalt3_ a écrit :

Comment ca tu ne peux pas vérifier ton code ?
Tu ne peux pas faire un prog qui appelle ta fonction ?


Je peux écrire un main mais il ne fonctionnera pas car la fonction ecrireGraphe utilise des fonctions qui sont données dans l'énoncé sans leur code.
Dans le cadre de l'exo, les fonctions données n'ont pas à être implémentée
Je voudrais juste savoir si le code que j'ai écrit correspond à ce qui est demandé ou s'il y a des modifications à faire


Message édité par Gattuso le 10-08-2006 à 10:44:02
Reply

Marsh Posté le 10-08-2006 à 13:00:20    

il faut lire l'ennoncé c'est à dire :
1) récupérer les fichiers tableHachage.h et tableHachage.c
2) puis penser à faire #include "tableHachage.h" dans ton source principal
3) compiler
4) lire les messages d'erreurs
5) corriger
 
Si ça ne marche pas à l'étape 5, alors, tu seras le bienvenu pour poster ici ton problème, mais pas avant...

Message cité 1 fois
Reply

Marsh Posté le 10-08-2006 à 14:30:52    

pains-aux-raisins a écrit :

il faut lire l'ennoncé c'est à dire :
1) récupérer les fichiers tableHachage.h et tableHachage.c
2) puis penser à faire #include "tableHachage.h" dans ton source principal
3) compiler
4) lire les messages d'erreurs
5) corriger
 
Si ça ne marche pas à l'étape 5, alors, tu seras le bienvenu pour poster ici ton problème, mais pas avant...


Je crois que je me suis mal exprimé.
L'exo que j'essaye de faire est tiré d'un sujet d'examen qui est en principe à faire par écrit
Dans l'énoncé, il est écrit ceci

Citation :

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 :


Je ne peut donc pas compiler le code car il n'y a rien à part la signature des méthodes
C'est pourquoi je voudrai que quelqu'un m'indique si ce que j'ai écrit est correct ...

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed