Discussion :

[RedDrak]

Bonjour à tous,

étant nouveau ici j'espère m'exprimer au bon endroit et surtout de la bonne façon.

Je vous explique mon problème :

je suis sur un projet qui consiste à programmer (de façon modulaire) des Ensembles (de n'importe quel type). Je dois pour cela implémenté une (ou plusieurs ?) structure de façon à avoir un tableau d'un type définie par un typedef le nombre de fois qu'apparait cet l'élément dans le tableau et un itérateur permettant de lire les différents éléments de l'ensemble.

Pour tout ca j'en suis pour l'instant là :

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
 
typedef int TElement;
#define TElementFormat "%d"
 
struct EnsembleP;
typedef struct EnsembleP * Ensemble;
typedef const struct EnsembleP * constEnsemble;
 
/****STRUCTURES****/
typedef struct Tab{
  TElement element;
  int nboccu;
}Tab;
 
struct EnsembleP{
  Tab *tabelement;
  int iterateur;
};
 
/****METHODES****/
 
Ensemble ensembleCreerDefaut()
{
  Ensemble self;
  self = malloc(sizeof(*self));
  if(self == NULL)
  {
    printf("ERREUR\n");
    exit(EXIT_FAILURE);
  }
  else
  {
    printf("C'est ok\n");
    return self;
  }
}
 
void ensembleDetruire(Ensemble *self)
{
  free(*self);
  *self = NULL;
}

en ce qui concerne les 2 structures je suis pas sûr que ca soit la bonne solution mais ce que j'ai pu voir sur le net c'est possible. Mon autre idée concernant cette partie du code donnerai tout simplement ceci :

Code :

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

1
2
3
4
5
 
typedef struct EnsembleP{
  TElement **tab;
  int iterateur;
}

Il me reste tout de même un gros problème c'est que quelle que soit la solution je n'arrive tout simplement pas à ajouter un élément à l'ensemble. Est-ce mon malloc() qui est mal fait ou autre chose... A vous de me dire .

Cordialement.

[prypiat]

J'ai exactement le même projet à faire^^ Pour ma part j'ai choisi ta deuxième solution. Mais pour ce qui est de l'itérateur, comment s'en servir ?? Je suis un peu largué là dessus^^ mais pour moi, il doit s'agir d'un pointeur non ?

[diogene]

La façon dont tu exposes ton problème n'est pas très précise.

Ce que je comprend :
- tu as à construire une collection d'éléments. Chaque élément est constitué d'une donnée d'un type donné quelconque. Pour tenir compte qu'une même donnée peut être présente plusieurs fois dans la collection, au lieu de la placer plusieurs fois dans la collection, on lui associe un entier représentant le nombre de fois où cette donnée est censée être présente dans la collection.
- à cette collection, tu dois associer un mécanisme (itérateur) permettant de se déplacer dans la collection.

Il faut d'abord définir comment représenter la collection.
On a plusieurs choix possibles : tableau (d'éléments ? de pointeurs sur éléments ?), liste (d'éléments ? de pointeurs sur éléments ?) simplement ou doublement chainée selon qu'on veut se déplacer uniquement dans un sens ou dans les deux.
Si on forme un tableau d'éléments ou une liste d'éléments, alors, la collection ne sera utilisable que pour des données de ce type. Si on peut avoir plusieurs collections avec des éléments de type différent, on sera amené à reproduire plusieurs fois un code qui sera quasi identique et pour lequel seul le type de données différera. Si on forme un tableau ou une liste de pointeurs sur éléments, on peut utiliser un pointeur banalisé, void *, et le code de la collection (et de l'itérateur) devient indépendant du type des données.

1- Si on connait le nombre maximum d'éléments et qu'on consent à avoir peut-être de la mémoire sous-utilisée, l'utilisation d'un tableau de pointeurs void* sur élément est simple et rapide.
2- Sinon, utiliser un tableau demandera de le redimensionner éventuellement en fonction des ajouts/suppressions d'éléments. La suppression totale d'un élément demandera de déplacer des éléments du tableau avant redimensionnement. Il faudra également mémoriser la taille du tableau.
3- L'utilisation d'une liste doublement chainée est, à mon avis, plus générale et plus simple à mettre en oeuvre même si l'occupation mémoire s'en trouve accrue à cause des pointeurs de chainage.

Par exemple, dans le cas 3, on a alors

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct TElement
{
  void* element;
  int nboccu;
  struct TElement * suivant;
  struct TElement * preced;
}TElement;
 
typedef struct
{
  TElement * tete;
//  .... autres éléments utiles pour définir la collection
//  .... et se déplacer dans la collection.
} TEnsemble;

Il faut donc d'abord faire un choix en fonction des données précises du problème (et de tes capacités en C). La question de l'itérateur se posera ensuite, une fois ce choix fait.

[RedDrak]

Tout d'abord merci pour votre réponse rapide, je pense opter pour la 2ème solution que vous m'avez proposé ce qui devrait correspondre à peu près à ce que j'ai pu écrire moi même dans ma 1ère solution.

Je vais essayer de mieux expliquer ce que je suis sensé produire :

on a un ensemble d'élément qui doivent être comme ca : {{element1,nb_occu_elem1},{element2,nb_occu_elem2},{element3,nb_occu_elem3}, etc...}
Chaque ensemble sera du même type défini en début de programme.

chaque ensemble d'élément possède un itérateur permettant de pointer sur n'importe quel élément, on doit pouvoir le placer en début/fin d'ensemble et également l'avancer. Dans ces fonctions l'ensemble passé en paramètre doit être passé en const.

Je dois également écrire des fonctions d'ajout d'élément/suppression d'élément.

D'où l'idée d'avoir fait une structure principale avec un iterateur qui et un tableau de structure comprenant elle l'élément et son nombre d'occurence.

Déjà ce dont je ne suis pas sûr c'est ce qui concerne le malloc(), est-ce que j'alloue la mémoire pour toute ma structure et surtout pour mon tableau de structure qui n'est pas contraint ? Ensuite pour pouvoir écrire dans la structure je n'arrive pas a écrire dans le tableau de structure, mais seulement l'itérateur.

Voilà sur quoi j'ai pu avancer :

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
 
#include <stdlib.h>
#include <stdio.h>
 
typedef int TElement;
#define TElementFormat "%d"
 
struct EnsembleP;
typedef struct EnsembleP * Ensemble;
typedef const struct EnsembleP * constEnsemble;
 
/****VARIABLES****/
static int nbcrees = 0;
static int nbactifs = 0;
 
/****STRUCTURES****/
 
typedef struct Tab{
  TElement element;
  int nboccu;
}Tab;
 
struct EnsembleP{
  Tab *tabelement;
  int iterateur;
};
 
/****METHODES****/
 
Ensemble ensembleCreerDefaut()
{
  Ensemble self;
  self = malloc(sizeof(Ensemble));
  if(self == NULL)
  {
    printf("ERREUR\n");
    exit(EXIT_FAILURE);
  }
  else
  {
    nbcrees++;
    nbactifs++;
    printf("C'est ok\n");
    self->iterateur = 0;
    printf("%d\n",self->iterateur);
    self->tabelement[0]->nboccu = 5; /*erreur ici*/
    return self;
  }
}

Je précise que ce qui se trouve avant ***VARIABLE*** se trouve dans mon .h

Ce qui pose problème dans ce code c'est : self->tabelement[0]->nboccu = 5;
il faut écrire ca autrement mais je ne vois vraiment pas...

Voilà en espérant avoir été plus claire sur mon problème et que pour l'instant ce que j'ai pu faire ai bon. Merci d'avance.

Cordialement.

[ArnaudD]

tabelement se trouve être un pointeur, or celui ci n'est jamais initialisé voilà d'où vient l'erreur

[prypiat]

Essaie ca :

Code :

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

1
2
3
Tab t;
t.nboccu=5;
self->tabelement[0]=t;

chez moi ca marche... enfin ca a l'air^^

[diogene]

1- il faut éliminer ces variables glogales nbcrees et nbactifs (sauf si elles ne sont là que provisoirement pour tester)

2- C'est une mauvaise idée de masquer un pointeur dans un typedef comme ici :

Code :

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

1
2
typedef struct EnsembleP * Ensemble;
typedef const struct EnsembleP * constEnsemble;

C'est nuisible pour la clarté.

3- Si ton ensemble est un tableau redimensionnable, il faut conserver le nombre d'éléments alloués à ton tableau.

4-

Code :

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

self = malloc(sizeof(Ensemble));

est certainement faux : tu alloue de la place pour un pointeur (puisque Ensemble est un pointeur)

5- Je pense que tu as intérêt à une structure du type :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct
{
  TElement element;
  int nboccu;
}Tab;
typedef struct
{
  Tab *tabelement;
  unsigned int nbElement;
  int iterateur; // ??
}Ensemble;

Il n'est pas sûr qu'il soit astucieux de mélanger dans une même structure l'ensemble et l'itérateur : tu ne pourras alors avoir qu'un seul itérateur par Ensemble.

La fonction de création d'un ensemble (vide) doit alors ressembler à

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Ensemble * CreerEnsemble(void)
{
  Ensemble * self = malloc(sizeof *self);
  if(self != NULL)
  {
    self->tabelement = NULL;
    self->nbElement = 0;
    self->iterateur = 0; // ??
  }
  return self;
}

6- Ensuite, il faudra écrire une fonction d'ajout d'un élément à un Ensemble (éventuellement vide). Il faudra qu'elle commence par chercher si l'élément existe déjà dans l'Ensemble (écrire une fonction pour ça). Si c'est le cas, il suffit d'incrémenter le compteur nboccu, sinon, il faudra redimensionner le tableau tabelement.

[RedDrak]

Merci pour vos réponses,

pour le 1 c'était pour des test oui ^^.

pour le 2, en fait c'est un code donné par mon prof et doit se servir de ca donc...

pour le 4, il faut écrire self = malloc(sizeof(struct EnsembleP)) du coup ?
parce que selon les quelques test que j'ai pu effectuer ca avait l'air de fonctionner

pour le 5, si il me faut un itérateur par Ensemble c'est fait pour pouvoir naviguer entre les éléments

pour le 6, j'ai écris ce code :

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
 
void ensembleAjouterElement(Ensemble self, TElement elt)
{
  ensembleIterateurDebut(self);
  do
  {
    if(self->tabelement[self->iterateur].element == elt)
    {
	self->tabelement[self->iterateur].nboccu++;
    }
    if(ensembleIsIterateurFin(self) == true)
    {
      self->tabelement[self->iterateur].element = elt;
      self->tabelement[self->iterateur].nboccu++;
      int taille = self->iterateur;
      Couple *p_tmp = realloc (self->tabelement, taille * sizeof(Couple));
 
      if (p_tmp != NULL)
      {
	self->tabelement = p_tmp;
      }
    }
    ensembleIterateurAvancer(self);
  }while(ensembleIsIterateurFin(self) == false);
}

ensembleIterateurDebut(self); met l'itérateur de self à 0
ensembleIterateurAvancer(self); incrémente de 1 l'itérateur

Au niveau du realloc() je suis pas trop sûr de ce que j'ai fais étant donné que c'est la 1ère fois que je m'en sers.

J'ai fais des test et ca n'ajoute pas d'élément donc il doit y avoir un problème quelques part. Ce que j'ai pu voir c'est qu'il n'avance pas l'itérateur.

Voilà le code de ensembleIterateurAvancer(self) :

Code :

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

1
2
3
4
5
6
7
 
void ensembleIterateurAvancer(constEnsemble self)
{
  assert(ensembleIsIterateurFin(self) == true);
  Ensemble selfNonConst = (Ensemble) self;
  selfNonConst->iterateur++;  
}

Pour info je suis obliger de mettre constEnsemble (demandé dans mon sujet).

Voilà en espérant avoir été complet et d'avoir aider d'autre personne .

Cordialement.

[prypiat]

RedDrak : Ton souci vient certainement du

Code :

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

 assert(ensembleIsIterateurFin(self) == true);

Si je me trompe pas, assert renvoie une erreur si l'expression booléenne qu'il y a dedans est fausse... en gros, ici si l'itérateur n'est pas en fin d'ensemble, ca plante...

Personnellement j'ai des soucis pour récupérer la taille de l'ensemble (qui sert notamment dans IsIterateurFin...) quelle solution as-tu choisie ?

[diogene]

pour le 2, en fait c'est un code donné par mon prof et doit se servir de ca donc...

Donc, tu n'as pas le choix, même si ce n'est pas une bonne idée.

pour le 4, il faut écrire self = malloc(sizeof(struct EnsembleP)) du coup ?
parce que selon les quelques test que j'ai pu effectuer ca avait l'air de fonctionner

Puisque self est un struct EnsembleP *, oui. Le fait que cela ait l'air de fonctionner sur un exemple peut être trompeur.
Et il faut penser ensuite à initialiser les différents champs de la structure créée, y compris self->tabelement.

pour le 5, si il me faut un itérateur par Ensemble c'est fait pour pouvoir naviguer entre les éléments

Bien sûr, mais cette construction ne permet d'avoir qu'un seul itérateur par ensemble et pas plusieurs.

Je ne vois pas comment tu peux écrire la fonction ensembleIsIterateurFin(constEnsemble self) si la structure pointée par self ne contient pas le nombre d'éléments du tableau

void ensembleIterateurAvancer(constEnsemble self)

Le seul fait d'être obligé de faire le transtypage const -> non const rend suspect le prototype de cette fonction ou la conception de l'itérateur comme membre de la structure EnsembleP. De plus, comme je l'ai dit plus haut, cette construction ne permet d'avoir qu'un seul itérateur par ensemble et pas plusieurs. Mais si c'est une contrainte imposée par le prof, on n'y peut rien.
Personnellement, je l'aurais plutôt vu sur le principe suivant :

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
typedef struct
{
   constEnsemble ensemble;
   int iterateur;
} Iterateur;
 
Iterateur * CreerIterateur(constEnsemble ensemble)
{
   Iterateur * p = malloc(sizeof *p);
   if(p!= NULL)
   {
      p->ensemble = ensemble;
      p->iterateur = 0;
   }
   return p;
}
 
void DetruireIterateur( Iterateur * iterateur)
{
   free(iterateur);
}
 
void ensembleIterateurAvancer(Iterateur * iterateur)
{
  if(iterateur->iterateur < iterateur->ensemble->nbElement-1)iterateur->iterateur++;
} 
 
Iterateur iterateurself ={self,0};
ensembleIterateurAvancer(&iterateurself);
Tab * p = GetElement(&iterateurself);
 
Iterateur *pautreiterateurself = CreerIterateur(self);
if(pautreiterateurself != NULL)ensembleIterateurAvancer(pautreiterateurself);
DetruireIterateur(pautreiterateurself);

[RedDrak]

Bon et bien merci pour votre aide, notre programme (à mon collègue et moi) marche à peu près encore quelques trucs à modifier et ca devrait aller. Encore merci .