Discussion :

[emikori]

Bonjour, je souhaite implémenter l'algorithme de Gale-Shapley. Dans un premier temps je comptais effectuer la saisie des données par l'utilisateur (le nombre d'hommes/femmes, la liste des préferences de chaque personne) pour enfin y appliquer l'algorithme de Gale-Shapley. Cependant, à l'éxécution du bout de code ci-dessus, la saisie du deuxième choix de la première personne n'aboutit pas et le programme ne m'affiche que le restant des printf sans la possibilité de saisie sachant que j'arrive à faire des saisies avec les deux premières boucles. J'ai essayé d'utiliser fgets mais celà me génère un segfault.. j'ai aussi essayer fflush(stdin) mais cela reste inefficace.

Je prendrai volontière vos propositions, votre aide m'est indispensable (j'ai passé plus de 24h à essayer de trouver une solution )

Merci par avance

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
78
79
80
81
82
83
84
85
86
87
 
#include <stdio.h>
#include <stdlib.h>
 
int N;
 
struct person{
  char *name;
  int id;
  int *preference;
};
 
int search_for_person_with_id(struct person *tab, char *s){
  for(int i = 0; i < N; i++)
    if(tab[i].name == s)
      return tab[i].id;
  return -1;
}
 
void enter_information(struct person *tab){
 
  int i, j;
  char *c1 = NULL;
 
  for(i = 0; i < N; i++){
    printf("Enter the name of male number %d \n", i+1);
    scanf(" %s", tab[i].name); 
    tab[i].id = i;
  }
 
  for(j = 0; j < N; j++){
    printf("Enter the name of female number %d \n", j+1);
    scanf("\t%s", tab[j+N].name); 
    tab[j+N].id = j;
  }
 
 
   printf("Now enter the list of male preferences for each female \n ");
 
  for(i = 0; i < N; i++){
    printf("- For %s : \n", tab[i].name);
    for(j = 0; j < N; j++){
      printf(" %d choice \n", j + 1);
      //fflush(stdin); 
      scanf(" %s", c1);
      tab[i+N].preference[j] = search_for_person_with_id(tab, c1);
      c1 = NULL;
      //fflush(stdin); 
    }
  }
 
 
   printf("Now enter the list of female preferences for each male \n");
 
  for(i = 0; i < N; i++){
    printf("- For %s : \n", tab[i].name);
    for(j = 0; j < N; j++){
      printf(" %d choice \n", j + 1);
      scanf(" %s", c1);
      tab[i].preference[j] = search_for_person_with_id(tab, c1);
      c1 = NULL;
    }
  }
}
 
int main(){
  int i;
  printf("Enter the number of males and females: ");
  scanf("%d", &N);
 
  struct person *tab;
 
  tab = malloc(sizeof(struct person)* (2 * N));
  for(i = 0; i < 2*N; i++){
     tab[i].name = malloc(sizeof(char));
     tab[i].preference = malloc(sizeof(int)*N);
  }
 
  enter_information(tab);
 
  for(i = 0; i < 2*N; i++){
     free(tab[i].name) ;
     free(tab[i].preference) ;
   }
   free(tab);
  return 1;
}

P-S : voilà le résultat obtenu lors de l'éxecution

[imperio]

N'étant pas un grand connaisseur de scanf, je dirais que c'est cette ligne qui pose problème :

Code :

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

scanf("\t%s", tab[j+N].name);

Autre chose, fgets correspond bien mieux à ce que tu cherches à faire. Relis mieux le man.

[Invité]

Je plussoie Imperio ci-dessus.

Pour allez un peu plus loin, la fonction fflush() ne doit jamais s'utiliser pour purger le flux d'entrée. Cette fonction a été créé dans le but de purger un flux, en particulier celui de sortie (le stdout). L'utilisation de cette fonction avec stdin est "Implementation Undefined" selon la norme, c'est à dire qu'elle est laissé à la libre appréciation du système de l'implémenter ou non.
Si tu es sur un système type Unix, cela produit un comportement indéfinie.
Pour purger le stdin, tu peux regarder ceci : FaqC -- Comment vider le buffer clavier

[Elijha]

Bonjour,

Je pense que ton problème vient de la taille de la chaine de caractères allouée.

Code :

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

tab[i].name = malloc(sizeof(char));

Telquel, tu as une chaine d'une taille de 1 octet.
IMPORTANT: Il faut aussi tester le retour du malloc, car s'il est NULL, tu vas direct au segfault en tentant d'écrire dans ce tableau.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
#define MAXSIZESTR      100
.
.
tab[i].name = malloc(MAXSIZESTR*sizeof(char));
if(tab[i].name==NULL) {
    fprintf(stderr, "erreur d'allocation mémoire\n") ;
    /* Libérer toute la mémoire précédemment allouée */
    return 1 ;  /* Code de sortie d'erreur */
}
.
.

Pour éviter la "lourdeur" de l'allocation, tu peux redefinir ta structure comme ceci, qui limite à N-1 caractères le nom.

Code :

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

1
2
3
4
5
struct person{
  char name[MAXSIZESTR];    /* Limite à N-1 caractères pour le nom (La fin de chaine étant représenté par \x0 */
  int id;
  int *preference;
};

Pour le scanf, le format "%s" ne permet que la saisie de chaine de caractères SANS espace. Comme imperio et archMqx t'ont précédemment dit, préfère l'utilisation de la fonction fgets.
Pour exemple

Code :

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

1
2
3
4
5
6
  for(i = 0; i < N; i++){
    printf("Enter the name of male number %d \n", i+1);
    /* Limite la saisie à MAXSIZESTR-1 caractères, donc pas de risque de dépassement */
    fgets(tab[i].name, MAXSIZESTR, stdin) ;     /* Attention, fgets enregistre aussi le retour chariot '\n' */
    tab[i].id = i;
  }

Voila pour le moment et bonne continuation

[emikori]

Merci pour vos réponses qui m'ont été d'une grande aide et qui m'ont permis d'apprendre de nouvelles choses (je suis un peu novice en C ). J'ai un peu près modifié mon code entièrement, laissant tombé l'allocation dynamique pour celle automatique dans la pile et cela tout en gardant la fonction de scanf (fgets bizarrement semble ne pas marcher.. ) J'ai aussi récupérer la fonction proposée par archMqx et qui purge le stdin et ça a ainsi résolu mon problème. Cependant les ennuies avec fgets semblent ne jamais terminer

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int N;
 
void clean_stdin(){ 
  int c; 
  do { 
    c = getchar(); 
  } while (c != '\n' && c != EOF); 
}
 
void enter_information(char name[2*N][20],int pref[2*N][N]){
  int i, j;
  char *c1 = NULL;
  for(i = 0; i < N; i++){
    printf("Enter the name of male number %d (his id is %d) \n", i+1, i);
    scanf(" %s", name[i]);
    clean_stdin();  
  }
  for(j = 0; j < N; j++){
    printf("Enter the name of female number %d (her id is %d) \n", j+1, j+N);
    scanf(" %s", name[j+N]);
    clean_stdin(); 
  }
  printf("Now enter the list of id's of male preferences for each female \n ");
  for(i = 0; i < N; i++){
    printf("- For %s : \n", name[i]);
    for(j = 0; j < N; j++){
      printf(" %d choice \n", j + 1);
      scanf(" %d", &pref[i][j]);
      clean_stdin(); 
    }
  }
  printf("Now enter the list of id's of female preferences for each male \n");
  for(i = 0; i < N; i++){
    printf("- For %s : \n", name[i+N]);
    for(j = 0; j < N; j++){
      printf(" %d choice \n", j + 1);
      scanf(" %d", &pref[i][j]);
      clean_stdin();
    }
  } 
//Boucle pour la vérification du contenu de pref[][]
 for(i = 0; i < 2*N; i++){
   printf("for %i tab de pref is \n", i);
  for(j = 0; j < N; j++){
    printf("%d   ", pref[i][j]);
  }
  printf("\n");
}
  printf("enter info ok \n");  
}
 
/* MAIN FUNCTION */
 
int main(){
 
  int i;
  printf("Enter the number of males and females: ");
  scanf("%d", &N);
  clean_stdin(); 
 
  char name[2*N][20];
  int pref[2*N][N];
 
  enter_information(name, pref);
 
  return 0;
}

En vérifiant si le tableau d'int pref à deux dimensions est bien rempli, je trouve que ces valeurs ne sont pas en concordance avec celles rentrées.. d'où le bug du à la fonction scanf

[fred1599]

Avec les lacunes que tu as, tu devrais faire une chose après l'autre, commence par une étape, contrôle que ça fonctionne et passe à l'étape suivante !

J'ai vu des choses comme la comparaison de 2 chaînes de caractères avec l'opérateur == (ligne 15 de ton premier code), qui est impossible en C (utiliser la fonction strcmp ou créer sa propre fonction de comparaison)

la liste des préferences de chaque personne

Conceptuellement ça fonctionne comment ?

[emikori]

@fred1599 vous avez parfaitement raison en ce qui concerne l'égalité des deux chaînes de caractères, je m'en suis rendue compte juste après mon post. Il faut bel et bien utiliser la fonction strcmp mais malheureusement ce n'est pas là où réside mon problème majeur.
En gros ce qu'il faut faire c'est que je remplisse manuellement deux tableaux différents, le premier est un tableau de chaine de caractères (il contient respectivement les noms d'une liste d'homme et de femme où le numéro de chaque case représente l'id de la personne). Après il est demandé de remplir un tableau à deux dimensions ( 2N x N) où la ligne № i représente la personne avec l'id i et contient la liste (avec N éléments) de ses préférences parmi les personnes du sexe opposé.
Pour l'instant il me semble que tout fonctionne correctement à part le bug lors de la saisie de la matrice des préférences.
Voili voilou en bref ce que j'espère obtenir, merci pour votre réponse !

[fred1599]

mais malheureusement ce n'est pas là où réside mon problème majeur

Le problème c'est qu'il y a pas mal d'erreurs, j'ai conseillé de travailler par étape...

En gros ce qu'il faut faire c'est que je remplisse manuellement deux tableaux différents, le premier est un tableau de chaine de caractères (il contient respectivement les noms d'une liste d'homme et de femme où le numéro de chaque case représente l'id de la personne).

Comme tu l'expliques, ne connaissant pas le nombre de personnes à ajouter dans la liste d'hommes et femmes, elles seront donc ajouter dynamiquement ou je me trompe ?

et contient la liste (avec N éléments) de ses préférences parmi les personnes du sexe opposé.

Le problème est que preferences est un tableau d'entiers, c'est pour cela que je demande des explications sur cette donnée... Pourquoi des entiers ? Comment ça va fonctionner ce type de données concrètement ? Peut-on avoir un exemple concret (sans code) ?

Pour l'instant il me semble que tout fonctionne correctement

Souvent on le croit

--------------------------------------------------

D'autres questions

1. Comment est créé une personne (initialisation de person) ?
2. Où se trouve la fonction permettant de lire les renseignements d'une personne ?
3. Comment déduire de la structure person, qu'une personne est un homme ou une femme ?

je ne vois pas comment éviter un attribut donnant le renseignement sur le genre d'une personne

Code :

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

1
2
3
4
5
6
7
8
typedef struct{
 
 
    enum SEX {M, F} sex;
 
 
    /* attributes */
} Person;

4. De la question précédente, comment en déduire ses préférences (homme ou femme ou ...) ?

La clarté du problème

Le problème n'est pas clair, dans le sens où si le problème n'est pas bien exprimé, c'est que peut-être une incompréhension s'est installée dans sa résolution...
Il faudrait sur papier, ou d'autres outils exprimer les besoins en ayant eu une réflexion avant code, afin de résoudre, puis quand on sait que sur papier ça roule, créer des étapes comme

• créer une personne
• ajouter une personne dans la liste des hommes ou femmes
• ajouter les préférences de la personne
• ...

En conclusion, là où je n'ai pas été clair, c'est que je conseillais de reprendre tout ça à zéro et à tête reposée, en étant aidé par une partie du forum pour la conception et une autre partie du forum pour la syntaxe du langage.

Si la conception est mauvaise, le reste suit !

[emikori]

Bonjour à vous @fred1599

Effectivement j'ai tout repris à zéro et j'ai reposté mon nouveau code (vous pouvez le retrouver un peu plus haut). J'ai carrément laissé tomber la structure personne car finalement elle ne me semblait pas nécessaire ni adéquate.

Pour l'implémentation de Gale-Shapley j'aurai pas besoin de lire les renseignements (qui se limitent à l'id, au nom et la liste de preférences) d'une personne mais juste les rentrer manuellement.

Ainsi le but final n'est pas de lire les informations mais plutôt de les rentrer afin de le leurs appliquer l'appariement de Gale-Shapley et pour cela j'aurai seulement besoin d'une matrice d'entiers int pref[2*N][N][ et d'un tableaux de chaînes de caractères char name[2*N][20]

Je m'excuse de ne pas avoir répondu à l'intégralité de vos questions, mais ces dernières ne se posent plus forcement dans le cadre de la nouvelle version de mon code. J'espère que vous allez y jeter un coup d'oeil et que j'aurai des retours et des remarques par rapport à cette dernière.

Merci par avance

[fred1599]

J'ai carrément laissé tomber la structure personne car finalement elle ne me semblait pas nécessaire ni adéquate.

Ça me semble contradictoire par rapport à cette phrase

(qui se limitent à l'id, au nom et la liste de preférences)

Rien que pour cela, la structure semble adapté...

Pour rentrer une valeur dans une matrice, ça semble pas bien difficile, concrètement ce code fait cela

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
int main(void){
 
    int matrice[50][50] = {{0}}; /* création et initialisation de ma matrice */
    int i;
 
 
    matrice[0][15] = 5; /* assigne la valeur 5 à la ligne 0 et colonne 15 */
 
 
    for (i=0; i<50; i++)
        printf("%d ", matrice[0][i]); /* affichage de la ligne 0 */
 
 
    return 0;
}

C'est peut-être quelque chose que tu sais déjà...

[emikori]

Je m'excuse je me suis mal exprimée, je n'ai pas besoin d'un structure dans la mesure où je n'ai pas besoin d'accéder aux informations relatives à une unique personne mais plutot de regrouper chaque type d'information dans un tableau qui permetrra un accès direct à la matrice de préférence et c'est exactement ce dont j'ai besoin .

De surplus, l'utilisateur rentre les informations lors de l'éxecutation à travers stdin et du coup la fonction proposée de votre part ne m'aide pas à remédier au problème du scanf
Car vérifiant si le tableau d'int pref à deux dimensions est bien rempli, je trouve que ces valeurs ne sont pas en concordance avec celles rentrées..

[BufferBob]

Si quelqu'un pourrait m'aider

edit: t'as modifié entre temps, j'ai du passer au mauvais moment

[emikori]

t'as modifié entre temps, j'ai du passer au mauvais moment

Effectivement t'es passé au mauvais moment. Par la même occasion, le participe passé du verbe devoir s'écrit comme suit : dû.
Merci pour ton aide !

[Bktero]

Tu devrais (condionnnel du verbe devoir ) nous montrer ton code mis à jour si tu souhaites de l'aide concrète

[emikori]

Pour le premier bug j'y ai remédié à l'aide de la fonction clean_stdin() (son code est fourni là-haut). Pour le deuxième bug, je n'écrivais pas là où il fallait dans la dernière boucle contenant le scanf . Il a suffit que je change &pref[i][j] en &pref[i+N][j].
Voili voilouu! J'espère être d'une aide à quelqu'un