[Débutant] Fusion de tableau

Version imprimable

Salut,

Voila, j'ai un ex a faire en C, il faut que je réalise la fusion de 2 tableaux dans un seukl tableau trié, je vous demande pas de me faire mon ex a ma place bien au contraire mais juste de m'aider a comprendre ou je fait erreur :)
En passant j'ai trouver ça mais ça ne me convient pas :)

Voila ce que j'ai commencer à faire :

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
/*                    			**
**                     			**   
**   Auteur   :   Oyo         		**
**   Fichier   :   Ex 23 FuTab 	**
**                    			**
**  Fusion 2 tableaux        		**
**  ~> 20 x 2                 		**
**  ~~> 1 tab 40 val tri ASC 	**
**                    			 */
#include <stdio.h>
#include <stdlib.h>
 
#define N 2
#define O 2
#define Z 4
 
int main()
{
	float tab[N],ztab[O], ytab[Z];
	int j, i, temp;
 
	printf("\n~~~~ Saisi Tableau 1 ~~~~\n\n");
	for(i = 0; i < N; i++)
	{
		printf("Essai %d: ", i + 1);
		fflush (stdout);
		scanf("%f", &tab[i]);
	}   
	printf("\n~~~~ Saisi Tableau 2 ~~~~\n\n");
	for(i = 0; i < O; i++)
	{
		printf("Essai %d: ", i + 1);
		fflush (stdout);
		scanf("%f", &ztab[i]);
	}
 
	for(i = 0; i < N-1; i++)
	{
		for(j = i+1; j < N; j++)
		{
			if (tab[i]>tab[j])
			{
				temp = tab[j];
				tab[j] = tab[i];
				tab[i] = temp;
				fflush (stdout);
				}
			}
	}
 
	for(i = 0; i < O-1; i++)
	{
		for(j = i+1; j < O; j++)
		{
			if (ztab[i]>ztab[j])
			{
				temp = ztab[j];
				ztab[j] = ztab[i];
				ztab[i] = temp;
				fflush (stdout);
			}
		}
	}
 
	printf("\n --------------------------------\n"   
		"| Tri Tableau 1 | Tri Tableau 2  |\n"
		"|--------------------------------|\n"
		"|      OK       |        OK      |\n"
		" --------------------------------\n"
		);
 
	for ( i = 0 ; i <Z ; i++)
	{
		ytab[i] = tab[i];
		ytab[i] = ztab[i]; 
		fflush (stdout);
	}
 
	printf("|      Fusion Tableau 1 & 2      |\n"
		" --------------------------------\n"
		"|              OK                |\n"
		" --------------------------------\n"
		"|         Tri Tableau 3          |\n"
		" --------------------------------\n"
		"|              OK                |\n"
		" --------------------------------\n\n"
		);
 
	for(i = 0; i < Z; i++)
	{
		for(j = i+1; j < Z; j++)
		{
			if (ytab[i]>ytab[j])
			{
				temp = ytab[j];
				ytab[j] = ztab[i];
				ytab[i] = temp;
				fflush (stdout);
			}
		}
		printf(" %.0f", ytab[i]);
	}
 
	printf("\n\n");
	system("pause");
	return 0;
}

Mon code block sur strcpy(), je pensais que c'était une bonne solution de copier et puis de concaténer les tableaux pour n'en avoir plus qu'un.. mais bon ça semble pas fonctionner :/

J'avais vu que est du type char *strcpy(char *but, const char *source) mais j'ai du mal à comprendre a quoi cela correspond réelement..

Merci par avance,
Cordialement.

23/01/2006, 23h57
leonardoo

la strcpy copie une chaine de caractere dans un tableau, je sais pas si je me trompe, mais je pense que y aura le caractere "/o" qui va causer des probleme. Enfin, pourquoi tu fais pas une boucle tout simplement pour fusionner les deux tableaux.
24/01/2006, 00h51
Darkenshin

Salut,

Merci de ta réponse ;), donc en gros dans ce que je fait il est impossible de fusionner un tableau remplis de chiffre, il faudrai donc passer par une boucle mais je ne vois pas tellement comment :/

Merci par avance,
Cordialement.
24/01/2006, 01h06
leonardoo

dans ce cas les tableaux sources sont connus de tailles fixe, donc tout simplement tu peux faire du genre :
for ( i = 0 ; i <N ; i++)
ytab[i] = tab [i];

puis faire la meme chose pour l'autre pour terminer, pis appliquer le tri sur le tableau ytab, mais c'est la façon la plus simpliste . par contre , de façon plus generaliste, tu peux faire une boucle que tu lui passe deux pointeurs sur les deux tableaux, elle prend le 1er, copie dans le tableau resultant tant que le dernier caractere n'est pas atteint (dans le cas des chaines c'est "/o", pis passer a l'autre (un while sera approprié) et apres tu trie. Cordialement.
24/01/2006, 02h51
Darkenshin

Salut,

Suite a ton idée, j'ai refait mon code il semble que cela fonctionne comme je le souhaite ;)

Si quelqu'un de meilleur que moi pouvez éventuellement me dire si ce que j'ai fait est juste et pas du au simple hazard ça serai gentil ^^

Merci encore leonardoo,
Cordialement.

Re: [Débutant] Fusion de tableau

Citation:

Envoyé par Darkenshin

Voila, j'ai un ex a faire en C, il faut que je réalise la fusion de 2 tableaux dans un seukl tableau trié, je vous demande pas de me faire mon ex a ma place bien au contraire mais juste de m'aider a comprendre ou je fait erreur :)

Remarques et corrections (-ed-). Pose des questions si tu ne comprends pas.

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
#if 0 
/* -ed- Moche et difficile a maintenir... */
 
/*                             **
**                              **
**   Auteur   :   Oyo               **
**   Fichier   :   Ex 23 FuTab    **
**                             **
**  Fusion 2 tableaux              **
**  ~> 20 x 2                       **
**  ~~> 1 tab 40 val tri ASC    **
**                              */
#else 
/*
**
** Auteur  : Oyo
** Fichier : Ex 23 FuTab
**
** Fusion 2 tableaux
** ~> 20 x 2
** ~~> 1 tab 40 val tri ASC
*/
#endif
 
#include <stdio.h>
#include <stdlib.h>
 
#define N 2
#define O 2
#define Z 4
/* -ed-
 Ces identificateurs sont peu parlants. 
 O peut etre confondu avec 0.
 On a du mal a feire le lien avec le nom des tableaux.
 Le code ne doit pas etre esoterique. Il doit se lire comme un livre.
*/
 
/* -ed- ajoute void (pas de parametre) */
int main (void)
{
   float tab[N], ztab[O], ytab[Z];
   int j, i, temp;
 
   printf("\n~~~~ Saisie Tableau 1 ~~~~\n\n");
   for (i = 0; i < N; i++)
   {
      /* -ed-
      printf("Essai %d: ", i + 1);
 
      pourquoi 'essai' ?
      */
      printf("Nombre %d: ", i + 1);
      fflush (stdout);
 
      /* -ed-
      scanf("%f", &tab[i]);
      mauvais choix de fonction de saisie.
 
      */
      {
         char s[16];
         fgets(s, sizeof s, stdin);
         tab[i] = strtod(s, NULL);
      }
   }
   printf("\n~~~~ Saisie Tableau 2 ~~~~\n\n");
   for (i = 0; i < O; i++)
   {
      printf("Nombre %d: ", i + 1);
      fflush (stdout);
 
      {
         char s[16];
         fgets(s, sizeof s, stdin);
         ztab[i] = strtod(s, NULL);
      }
   }
 
   /* tri */
   for (i = 0; i < N - 1; i++)
   {
      for (j = i + 1; j < N; j++)
      {
         if (tab[i] > tab[j])
         {
            temp = tab[j];
            tab[j] = tab[i];
            tab[i] = temp;
 
            /* -ed- Pourquoi faire ?
                     fflush (stdout);
            */
         }
      }
   }
 
   /* tri */
   for (i = 0; i < O - 1; i++)
   {
      for (j = i + 1; j < O; j++)
      {
         if (ztab[i] > ztab[j])
         {
            temp = ztab[j];
            ztab[j] = ztab[i];
            ztab[i] = temp;
         }
      }
   }
 
   printf("\n "
          "--------------------------------\n"
          "| Tri Tableau 1 | Tri Tableau 2  |\n"
          "|--------------------------------|\n"
          "|      OK       |        OK      |\n"
          " --------------------------------\n"
         );
 
   /* copie */
#if 0
 
   for ( i = 0 ; i < Z ; i++)
   {
      ytab[i] = tab[i];
      ytab[i] = ztab[i];
      /* -ed- bravo, tu viens d'ecraser ce que tu viens de copier...
              il faut faire 2 boucles indépendantes...
      */
   }
#else
   for ( i = 0 ; i < N ; i++)
   {
      ytab[i] = tab[i];
   }
 
   for ( i = 0 ; i < O ; i++)
   {
      ytab[i + N] = ztab[i];
   }
#endif
 
   printf(
      "|      Fusion Tableau 1 & 2      |\n"
      " --------------------------------\n"
      "|              OK                |\n"
      " --------------------------------\n"
      "|         Tri Tableau 3          |\n"
      " --------------------------------\n"
      "|              OK                |\n"
      " --------------------------------\n\n"
   );
 
   for (i = 0; i < Z; i++)
   {
      for (j = i + 1; j < Z; j++)
      {
         if (ytab[i] > ytab[j])
         {
            temp = ytab[j];
            /* -ed-
                        ytab[j] = ztab[i];
             
            Absurde! Mauvais copie/colle, je suppose...
            */
            ytab[j] = ytab[i];
 
            ytab[i] = temp;
            fflush (stdout);
         }
      }
      /* -ed-
      printf(" %.0f", ytab[i]);
 
      a quoi sert cet affichage ? Il manque un veritable affichage de ytab 
      independant. 
 
      (Ok, ca fonctionne, mais en principe, on ne melange pas les actions)
      */
   }
 
   /* -ed- affichage separe. */
   for (i = 0; i < Z; i++)
   {
      printf(" %.0f", ytab[i]);
   }
   printf("\n\n");
 
   /* -ed- passe plutot a Code::Blocks... Dev-C++, c'est fini.
      system("pause");
   */ 
   return 0;
}

Dommage que tu n'ai pas implementé la vrai fusion de tableaux tries...

[EDIT] Au fait, les deux premiers tris ne sont pas executés. (Ce qui n'a aucune importance ici). Ben oui, pourquoi N-1 et O-1 ?

24/01/2006, 21h51
Darkenshin

Salut Emmanuel Delahaye,

Dans un premier temps, merci pour la correction et les commentaires ;) apres pour les commentaire en haut du fichier c'est juste pour me rappeler de quoi il s'agit quand je prend les ex au tableau (généralement ça vire après) ;)

Pour les define enfaite j'ai un peu fait ça comme je pouvais vu l'heure..
Pour essai, il s'agit en gros d'une partie de l'énnoncé ;)
Pour scanf, je fais comme on nous apprend a l'école :(
Pour fflush (stdout); aucune idée :lol:
Pour les valeurs écrasaient, vu que j'ai un peu de mal a comprendre comment faire, il est normal que je me trompes ^^
Pour l'absurdité, certainement vu l'heure qu'il était hier
Pour l'affichage, il me semble que cela permetter de voir si le tri était bien effectuer.. :/
Pour la fin pas trop compris :/

Au final, il semble que j'ai mal compris l'algo de tri et mal copier celui-ci puisque dans mon cours il ya bien N-1 pour le tri :?

En même temps si je ne sais pas faire je ne risque pas de trouver comme ça la façon de bien implementé la vrai fusion de tableaux triés :)

(ps désolé pour les fautes quelques pb de clavier :/)

Sinon comment fonctionne le tri si celui que je fait ne fonctionne pas ?

Merci,
Cordialement ;)

Citation:

Envoyé par Darkenshin

SEn même temps si je ne sais pas faire je ne risque pas de trouver comme ça la façon de bien implementé la vrai fusion de tableaux triés :)

Sinon comment fonctionne le tri si celui que je fait ne fonctionne pas ?

Le principe de la fusion triée est de partir de 2 tableaux triés a et b et de les lire élément par élément et de les copier dans l'ordre en c.

Code:

1
2
3
4
5
6
 
- On commence par a[0] et b[0].
FAIRE
- On prend le plut petit de deux et on le met dans c[0]
- On incrémente l'indice du tableau dont on vient de placer un élément dans c, et l'indice de c.
TANT QUE  les tableaux a et b ne sont pas vides

- Précautions : la taille du tableau de destination doit être la somme de la taille des tableaux sources.

- Note : c'est plus amusant si les tableaux a et b ont des tailles différentes.

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
 
#include<stdio.h>
 
#define N(a) (sizeof (a)/sizeof *(a))
 
static void print(char const *s, int const a[], size_t n)
{
   size_t i;
   printf("%s: ", s);
   for (i = 0; i < n; i++)
   {
      printf("%d ", a[i]);
   }
   printf("\n");
}
 
int main(void)
{
 
   int a[] =
      {
         2, 5, 6, 8, 9, 11
      };
   int b[] =
      {
         3, 6, 7, 9, 12
      };
   int c[N(a) + N(b)];
   size_t ic = 0;
   {
      size_t ia = 0;
      size_t ib = 0;
 
      print("a", a + ia, N(a) - ia);
      print("b", b + ib, N(b) - ib);
      print("c", c, ic);
      printf ("\n");
 
      while (ia != N(a) || ib != N(b))
      {
#if 1
         /* elimination des doublons */
         if (a[ia] == b[ib])
         {
            if (ia < N(a))
            {
               c[ic] = a[ia];
               ia++;
            }
            if (ib < N(b))
            {
               ib++;
            }
         }
         else
#endif
            if (a[ia] < b[ib])
            {
               if (ia < N(a))
               {
                  c[ic] = a[ia];
                  ia++;
               }
            }
            else
            {
               if (ib < N(b))
               {
                  c[ic] = b[ib];
                  ib++;
               }
            }
         ic++;
         print("a", a + ia, N(a) - ia);
         print("b", b + ib, N(b) - ib);
         print("c", c, ic);
         printf ("\n");
      }
   }
 
 
   print("c", c, ic);
   return 0;
}

Avec élimination des doublons

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
 
a: 2 5 6 8 9 11
b: 3 6 7 9 12
c:
 
a: 5 6 8 9 11
b: 3 6 7 9 12
c: 2
 
a: 5 6 8 9 11
b: 6 7 9 12
c: 2 3
 
a: 6 8 9 11
b: 6 7 9 12
c: 2 3 5
 
a: 8 9 11
b: 7 9 12
c: 2 3 5 6
 
a: 8 9 11
b: 9 12
c: 2 3 5 6 7
 
a: 9 11
b: 9 12
c: 2 3 5 6 7 8
 
a: 11
b: 12
c: 2 3 5 6 7 8 9
 
a:
b: 12
c: 2 3 5 6 7 8 9 11
 
a:
b:
c: 2 3 5 6 7 8 9 11 12
 
c: 2 3 5 6 7 8 9 11 12

Sans éliminations des doublons (#if 0)

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
 
a: 2 5 6 8 9 11
b: 3 6 7 9 12
c:
 
a: 5 6 8 9 11
b: 3 6 7 9 12
c: 2
 
a: 5 6 8 9 11
b: 6 7 9 12
c: 2 3
 
a: 6 8 9 11
b: 6 7 9 12
c: 2 3 5
 
a: 6 8 9 11
b: 7 9 12
c: 2 3 5 6
 
a: 8 9 11
b: 7 9 12
c: 2 3 5 6 6
 
a: 8 9 11
b: 9 12
c: 2 3 5 6 6 7
 
a: 9 11
b: 9 12
c: 2 3 5 6 6 7 8
 
a: 9 11
b: 12
c: 2 3 5 6 6 7 8 9
 
a: 11
b: 12
c: 2 3 5 6 6 7 8 9 9
 
a:
b: 12
c: 2 3 5 6 6 7 8 9 9 11
 
a:
b:
c: 2 3 5 6 6 7 8 9 9 11 12
 
c: 2 3 5 6 6 7 8 9 9 11 12

Salut Emmanuel Delahaye,

Effectivement, maintenant que tu me le dis ^^ je comprend mieux, bien que dans la FAQ, il est marqué que lire éléments par éléments c'est plus lent et parfois complexe :)

Oui, c'est mieux de faire la somme des deux define, c'est ce que j'ai fait dans mon nouveau code puisque j'essai de faire quelque chose en passant par une autre solution ^^. Il faut noter aussi qu'on appris pour l'instant que scanf().. ;)

Euh pour la note, euh oui c'est sur mais comme c'est un exercice d'école, je ne fait qu'appliquer ce qu'on me demande ^^, il en va de même pour DevC++..

Voila le nouveau code:

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
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
 
#define TAB1 2 
#define TAB2 (TAB1+TAB1) 
 
typedef float tab_entiers[TAB2]; 
 
void fusionrec(tab_entiers t, tab_entiers tmp, int de1, int vers1, int de2, int vers2, int count, int posInB) { 
       int i; 
       for(i = 0 ; i < count ; i++) { 
               if(de2 > vers2 - 1) tmp[posInB++] = t[de1++]; 
               else if(de1 > vers1) tmp[posInB++] = t[de2++]; 
               else if(t[de1] < t[de2]) tmp[posInB++] = t[de1++]; 
               else tmp[posInB++] = t[de2++]; 
       } 
} 
void fusion(tab_entiers t) { 
       tab_entiers tmp; 
       int sortLength = 1, de1, de2, vers1, vers2, i; 
       while(sortLength < TAB2) { 
               de1 = 0; 
               while(de1 < TAB2) { 
                       de2 = de1 + sortLength; 
                       vers1 = de2 - 1; 
                       vers2 = de2 + sortLength - 1; 
                       if(vers1 >= TAB2 - 1) fusionrec(t, tmp, de1, TAB2-1, 0, 0, TAB2-de1, de1); 
                       else if (vers2 >= TAB2 - 1) fusionrec(t, tmp, de1, vers1, de2, TAB2, TAB2-de1, de1); 
                       else fusionrec(t, tmp, de1, vers1, de2, vers2 + 1, 2*sortLength, de1); 
                       de1 = vers2 + 1; 
               } 
               for(i = 0 ; i < TAB2 ; i++) t[i] = tmp[i]; 
               sortLength *= 2; 
       } 
} 
 
int main(void) 
{ 
	float tab1[TAB1], tab2[TAB1], tab3[TAB1], tab4[TAB1]; 
	int  i;  
 
	printf("\n~~~~ Saisie Tableau 1 ~~~~\n\n"); 
	for(i = 0; i < TAB1; i++) 
	{ 
		printf("Essai %d: ", i + 1); 
		scanf("%f", &tab1[i]); 
	} 
	memcpy(tab3,tab1,TAB1*sizeof(float)); 
 
	printf("\n~~~~ Saisie Tableau 2 ~~~~\n\n"); 
	for(i = 0; i < TAB1; i++) 
	{ 
		printf("Essai %d: ", i + 1); 
		scanf("%f", &tab2[i]); 
	} 
	memcpy(tab4,tab2,TAB1*sizeof(float)); 
	fusion(tab4); 
 
	printf("\nTri:\n"); 
	for (i = 0; i < TAB2; i++) 
	{ 
		printf(" %.0f", tab4[i]); 
	} 
	memcpy(tab4,tab3,TAB1*sizeof(float)); 
 
	printf("\n\n"); 
	system("PAUSE"); 
	return 0; 
}

Merci,
Cordialement.