Les ensembles (tableau dynamique/statique)

Bonjour,

Je doit Définir une structure permettant la gestion d'un ensemble d'élement, ensuite des fonctions add,remove,size,Trie(sort),intersection,union,diff (différence de 2 ensembles), include(si un ensemble inclus dans un autre) et équal (si 2 ensembles sont indentique).
Une version avec tableau statique et une autre dynamique.
Alors pour la version dynamique j'ai une question:

1- Pour la fonction add, je ne peut pas utilisé malloc mais realloc car si j'ai bien comprit malloc permet d'alloué un bloc d'une certaine taille (par exemple un tableau de taille n).
Tandis que realloc permet de réalloué un bloc pour modifié sa taille (par exemple utile pour faire évolué la taille d'un tableau).

Mais avec un autre code, le malloc marche très bien pour le même genre d'utilisation:

Code:

1
2
3
4
5
6
7
8
9
 
int *init(int *tab,int n){
  int i;
  for(i=0;i<n;i++){
    tab=malloc(sizeof(int *)+i); 
    tab[i]=i;
  }
  return tab;
}

Tableau statique:

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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
#include<stdio.h>
#include<stdlib.h>
typedef struct ensemble{
  int tab[50];
  int taille;
}liste;
 
void init(liste *l){
  l->taille=0;
}
 
void add(liste *l,int val){
  if(!belong(*l,val)){
    l->tab[l->taille]=val;
     l->taille++;
  }
}
 
void affiche(liste l){
  int i;
  for(i=0;i<l.taille;i++)
    printf("%d\n",l.tab[i]);
}
int size(liste l){
  return l.taille;
}
 
int belong(liste l,int val){
  int i;
  for(i=0;i<=l.taille-1;i++){
    if(l.tab[i]==val)
      return 1;
  }
  return 0;
}
 
void remove2(liste *l,int val){
  int j,i=0;
  if(!belong(*l,val))
    return;
  while(i<=l->taille-1){
    if(l->tab[i]==val){
      for(j=i;j<=l->taille-1;j++)
	l->tab[i]=l->tab[i+1];
      l->taille--;
    }
      i++;
  }
}
 
void sort(liste *l){
  int i,j,save;
  for(i=0;i<l->taille-1;i++)
    for(j=i+1;j<l->taille;j++){
      if(l->tab[j]<l->tab[i]){
	save=l->tab[i];
	l->tab[i]=l->tab[j];
	l->tab[j]=save;
      }
    }
}
 
 
void intersection(liste l1, liste l2,liste *l3){
  int i;
  init(l3);
  for(i=0;i<l1.taille;i++)
    if(belong(l2,l1.tab[i]))
      add(l3,l1.tab[i]);
}
 
void union2(liste l1,liste l2,liste *l4){
  int i;
  init(l4);
  for(i=0;i<l1.taille;i++)
    add(l4,l1.tab[i]);
  for(i=0;i<l2.taille;i++)
    add(l4,l2.tab[i]);
}
 
void diff(liste l1,liste l2,liste *l5){
  int i;
  init(l5);
  for(i=0;i<l1.taille;i++){
    if(!belong(l2,l1.tab[i]))
      add(l5,l1.tab[i]);
  }
}
 
int include(liste l1,liste l2){
  int i;
  for(i=0;i<l1.taille;i++)
    if(!belong(l2,l1.tab[i]))
      return 0;
  return 1;
}
 
int equal(liste l1,liste l2){
  return (include(l1,l2)&&include(l2,l1));
}
 
 
int main(void){
  liste l;
  liste l2,l3,l4;
  init(&l);
  init(&l2);
  add(&l,5);
  add(&l,4);
  add(&l,6);
  add(&l,2);
  add(&l2,2);
  add(&l2,6);
  add(&l2,8);
  add(&l2,5);
  printf("l\n");
  affiche(l);
  printf("l2\n");
  affiche(l2);
  printf("REMOVE\n");
  remove2(&l,6);
  affiche(l);
  printf("TRIE\n");
  sort(&l);
  affiche(l);
  printf("INTERSECTION\n");
  intersection(l,l2,&l3);
  affiche(l3);
  printf("DIFF\n");
  diff(l,l2,&l4);
  affiche(l4);
  printf("INCLUDE\n");
  printf("%d\n",include(l,l2));
  printf("EQUAL\n");
  printf("%d\n",equal(l,l2));
  return 0;
}

avec allocation dynamique:

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
 
typedef struct ensemble{
  int *tab;
  int taille;
}liste;
void init(liste *l){
  l->taille=0;
  l->tab=NULL;
}
 
void add(liste *l,int val){
  if(!belong(*l,val)){
    l->tab=realloc(l->tab,sizeof(int)*(l->taille+1));
    l->tab[l->taille]=val;
    l->taille++;
  }
}    
void remove2(liste *l,int val){
  int j,i=0;
  if(!belong(*l,val))
    return;
  while(i<=l->taille-1){
    if(l->tab[i]==val){
      for(j=i;j<=l->taille-1;j++)
	l->tab[i]=l->tab[i+1];
      l->taille--;
    }
      i++;
  }
}

Merci d'avance pour votre aide.

pour la fonction init ,si tu veux creer un tableau de taille n et le remplir de 0 jusqu'a n-1 le tous dans une fonction alors c'est pas ce que tu es entrain de faire .
mais plutot comme sa :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <stdio.h> #include<stdlib.h> void init(int **tab,int n){ int i; *tab=malloc(n*sizeof(int)); for(i=0;i<n;i++) (*tab)[i]=i; } int main(){ int *tableau; int i,n = 10; /* taille 10 par exemple **/ init(&tableau,n); for(i=0;i<n;i++) printf("%d ",tableau[i]); return 0; }

Ha ok bizarre, j'arrive à faire aller les 2, celle que tu propose et celle que j'ai écrit.

Je crois que tu as oublié de poser ta question.