Ubuntu-fr

Mister

Allocation de matrice

Bonjour,

je voudrais savoir si quelqu'un pouvait m'indiquer le code C qu'il faut que j'écrive pour avoir la figure si dessus en utilisant les structures suivantes

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.

 

 
   --------|
  |        |
  |  5---->4
  | ^ \   ^^
  v/   \ / |
->1     /  |
   \   / \ |
    v /   vv
     3---->2

Voici ce que j'ai fait :

int main(void)
{
  Graphe g1,g2,g3,g4,g5;
  g1->racine->n = 1;
  g->racine->tab[0] = g5->racine;
  g->racine->tab[1] = g3->racine;
  
  g5->racine->n = 5;
  g->racine->tab[0] = g2->racine;
  g->racine->tab[1] = g4->racine;
 
  /* etc..*/
  return 0;
}

Le problème que j'ai, est que je ne sais pas comment alloué les arcs.
Avec ce que j'ai érit, ça me fait une erreur de segmentation.

Est-ce que quelqu'un pourrait m'indiquer comment doit ce faire l'allocation ?

Merci

lunique

Re : Allocation de matrice

Deja, tu definis 5graphes alors que tu as 1 seul graphe et 5 noeud donc :

int main()
{
/*un graphe*/
Graphe g1;
/*5 pointeur vers des noeuds*/
Noeud*n1,n2,n3,n4,n5;
/*On alloue de la place pour les 5noeud*/
n1=(Noeud *)malloc(sizeof(Noeud));
n2=(Noeud *)malloc(sizeof(Noeud));
n3=(Noeud *)malloc(sizeof(Noeud));
n4=(Noeud *)malloc(sizeof(Noeud));
n5=(Noeud *)malloc(sizeof(Noeud));
/*On donne la valeurs de chaque racine*/
(*n1).n=1;
(*n2).n=5;
(*n3).n=4;
(*n4).n=3;
(*n5).n=2;
/*On definit le graphe*/
g1.racine=n1;
/*On alloue la place pour les arcs*/
(*n1).tab=(Noeud **)malloc(2*sizeof(Noeud*));
(*n2).tab=(Noeud **)malloc(2*sizeof(Noeud*));
(*n3).tab=(Noeud **)malloc(1*sizeof(Noeud*));
(*n4).tab=(Noeud **)malloc(2*sizeof(Noeud*));
(*n5).tab=(Noeud **)malloc(1*sizeof(Noeud*));

/*et maintenant, on les mets*/
(*n1).tab[0]=n2;
(*n1).tab[1]=n4;
(*n2).tab[0]=n3;
(*n2).tab[1]=n5;

/*etc*/
}

En fait, on devrait definir un type graphe avec un ensemble de fonction et pareil avec les noeud (histoire que ce soit un peu dynamique. On doit pouvoir rajouter un arc sans avoir a faire le malloc avant à la main)
mais sinon, l'idée est là.

coffee

Re : Allocation de matrice

L'erreur de segmentation vient du fait que tu n'as pas compris la notion de pointeur. Reviens en arrière dans ton bouquin, il faut absolument comprendre cette notion en C sinon c'est mort.

L'exemple de lunique devrait marcher meme si je pense qu'on peut complétement se passer des mallocs au début pour un exemple aussi statique (et au passage ils ont tous 2 arcs dans l'exemple)

J'ai pas compris cette phrase dans l'énoncé: Même si ce n'est pas le cas sur la figure, deux noeuds différents peuvent contenir le me entier. Ça veut dire qu'on peut avoir 2 noeuds 5? O_o

Enfin bon je pense que si tu veux faire quelque chose de vraiment dynamique, il faudrait recreer les structure car je ne vois pas bien comment les free dynamiquement car on perd l'info du nombre de noeud suivant pendant la création de ceux-ci.

Bon allez j'arrete de taquiner mais j'aimerai bien savoir d'où vient cette exercice stp.

---

Nom d'un tupperware habillé en streetware mangeant de la confiture de pouère et qui se dite où est-ce que je suis ouère !
Tiens mon blog
Les blagues sous forme de fausses aides sont susceptible de ban (ex: rm)

Mister

Re : Allocation de matrice

L'erreur de segmentation vient du fait que tu n'as pas compris la notion de pointeur. Reviens en arrière dans ton bouquin, il faut absolument comprendre cette notion en C sinon c'est mort.

L'exemple de lunique devrait marcher meme si je pense qu'on peut complétement se passer des mallocs au début pour un exemple aussi statique (et au passage ils ont tous 2 arcs dans l'exemple)

C'est les pointeurs ** utilisant des structures que je n'arrive pas à comprendre mais apparement, cela se passe comme pour des char **
Pour les char **tab les allocations se passe de cette maniere (sans faire de test sur le retour des malloc)

tab = (char **)malloc(nb*sizeof(char*));//avec nb le nombre d'élts du tableau
for(i=0;i<nb;i++){
tab[i] = (char*)malloc(strlen(mot)+1);//mot est mot quelqonque
strcpy(tab[i],mot);
}

Pourquoi dans l'exemple de lunique, il n'y a pas comme pour l'allocation struct noeud **tab les 2 étapes d'allocations comme pour les char ** ?

J'ai pas compris cette phrase dans l'énoncé: Même si ce n'est pas le cas sur la figure, deux noeuds différents peuvent contenir le me entier. Ça veut dire qu'on peut avoir 2 noeuds 5? O_o

C'est bien ça

Enfin bon je pense que si tu veux faire quelque chose de vraiment dynamique, il faudrait recreer les structure car je ne vois pas bien comment les free dynamiquement car on perd l'info du nombre de noeud suivant pendant la création de ceux-ci.

Bon allez j'arrete de taquiner mais j'aimerai bien savoir d'où vient cette exercice stp.

L'exo vient dancien sujet d'examen qui ont été donné dans la fac ou je suis et j'essaye de les refaire à titre d'entrainement c'est pour ça que je souhaite avoir des aides concernant le sujet et les structures qui sont imposées, sans les modifier

lunique

Re : Allocation de matrice

Pour les char **tab les allocations se passe de cette maniere (sans faire de test sur le retour des malloc)
Code:

tab = (char **)malloc(nb*sizeof(char*));//avec nb le nombre d'élts du tableau
for(i=0;i<nb;i++){
tab[i] = (char*)malloc(strlen(mot)+1);//mot est mot quelqonque
strcpy(tab[i],mot);
}

Pourquoi dans l'exemple de lunique, il n'y a pas comme pour l'allocation struct noeud **tab les 2 étapes d'allocations comme pour les char ** ?

mettons que j'ai deja un pointeur vers un mot
char * mot;
mot=(char*)malloc(strlen("plop")+1);
strcpy(mot,"plop");
on peut ecrire directement (enfin, apres le  tab = (char **)malloc(nb*sizeof(char*));)
tab[0]=mot;
là, c'est pareil, j'ai d'abord crée des pointeurs vers des noeuds, je les ai remplis, et apres, je les stocke dans les liste de noeud, donc j'ai bien les 2 etapes d'allocation, mais faite à deux endroits differents.

P.S. je me suis trompé pour le noeud de valeur 4, il a bien 2 arcs, mais celui de valeurs 2 n'en as qu'un

Mister

Re : Allocation de matrice

Je met la suite pour que vous puissiez m'aider à répondre aux questions.
Merci par avance

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 :

#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 interdison de modifier les fichiers récupérés sur le Web

Exercices :
-L'interface proposé pour les tables de hachage permet-elle de dire si les tables vont faire des copies interne des clefs et des valeurs qu'on y insère ?
Dans les exercices suivants toutes les fonctions retournent un code d'erreur en cas de problème, 0 sinon.

-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

-Ecrire une fonction int libereGraphe(Graphe **g) qui libère un graphe qui a entièrement été alloué dynamiquement. Avant de retourner, la fonction doit remettre le pointeur désignant le graphe a NULL

coffee

Re : Allocation de matrice

P.S. je me suis trompé pour le noeud de valeur 4, il a bien 2 arcs, mais celui de valeurs 2 n'en as qu'un

Exact

Je me suis trompé sur la taille du tableau (sizeof(tab)/sizeof(tab[0])) donne sa taille. Pour la fonction détruire, après chaque free(pointeur), pense à faire pointeur=NULL; comme ça tu peux tester si tu as libérer ou non le pointeur.

Mais sinon où bloque-tu?

---

Nom d'un tupperware habillé en streetware mangeant de la confiture de pouère et qui se dite où est-ce que je suis ouère !
Tiens mon blog
Les blagues sous forme de fausses aides sont susceptible de ban (ex: rm)

Mister

Re : Allocation de matrice

P.S. je me suis trompé pour le noeud de valeur 4, il a bien 2 arcs, mais celui de valeurs 2 n'en as qu'un

Exact

Je me suis trompé sur la taille du tableau (sizeof(tab)/sizeof(tab[0])) donne sa taille. Pour la fonction détruire, après chaque free(pointeur), pense à faire pointeur=NULL; comme ça tu peux tester si tu as libérer ou non le pointeur.

Mais sinon où bloque-tu?

Pour l'écriture de int ecrireGraphe(), je ne sais pas très bien comment me servir des fonctions fournies pour écrire la fonction demandée ...