Bonjour à tous,

Je souhaite faire un algorithme de tri de ma pile plus propre et pour ça, je vais faire le tri fusion.

Apparemment, pour cela il faut diviser la pile en deux sous piles, puis trier les deux sous piles, puis réunir les deux piles triées en une grosse pile triée.

J'en suis à la première étape, j'essaie de diviser ma pile en deux piles.

A la base, j'étais parti de ça :


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
 
 
pile division_en_deux(pile p, pile p1, pile p2)
{int a = milieu_pile(p)->suivant->valeur;
    element_pile *b;
    b = milieu_pile(p)->suivant;
 
    printf("\nListe 1\n");
    while(!(p->valeur == a))
    {
        p1 = ajouter_pile(p1, p->valeur);
        p = p->suivant;
    }
 
    printf("\nListe 2\n");
    while(!( b == NULL))
    {
        p2 = ajouter_pile(p2, p->valeur);
        p = p->suivant;
    }
}
Ce code ne marchait pas, mais en essayant, en changeant mon code, je suis tombé sur ça :

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
 
 
pile division_en_deux(pile p, pile p1, pile p2)
{
    int a = milieu_pile(p)->suivant->valeur;
 
    while(!(p->valeur == a))
    {
        pile1 = ajouter_pile(pile1, p->valeur);
        p = p->suivant;
        return p1;
    }
 
    while(!( p == NULL))
    {
        pile2 = ajouter_pile(pile2, p->valeur); // ajoute l'élément souhaité
        p = p->suivant; // passe à la pile suivante
    }
}
en changeant le :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
 
 
b = milieu_pile(p)->suivant;
 
while(!( b == NULL))
{
   ...
}
en :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
 
while(p!=NULL) {
    p2=ajouter_pile(p2,p->valeur);
    p=p->suivant;
}
Ducoup, c'est ma première question : Je ne comprends pas pourquoi on met p!=NULL, je ne suis pas censé repartir de b pour aller jusqu'à NULL ?

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Ensuite,

Pour la sous fonction qui divise ma pile en deux, je l'ai ensuite un peu modifié :

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
 
 
pile division_en_deux(pile p, pile p1, pile p2)
{
    int a = milieu_pile(p)->suivant->valeur;
    element_pile *pile1;
    element_pile *pile2;
    pile1 = p1;
    pile2 = p2;
 
    while(!(p->valeur == a))
    {
        pile1 = ajouter_pile(pile1, p->valeur);
        p = p->suivant;
        return p1;
    }
 
    while(!( p == NULL))
    {
        pile2 = ajouter_pile(pile2, p->valeur); // ajoute l'élément souhaité
        p = p->suivant; // passe à la pile suivante
    }
}
Dans cette partie du code :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
 
 
element_pile *pile1;
element_pile *pile2;
pile1 = p1;
pile2 = p2;
Je veux que ma " pile1 " et " pile2 " soient visible partout dans le code, c'est pour cela que je dois utiliser un pointeur. Mon code est faux d'ailleurs je pense.

" Pourquoi faire deux pointeurs de " pile1 " et " pile2 " ? " :

Voici mon main :

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
 
 
int main()
{
    pile p = nouvelle_pile();
    pile p1 = nouvelle_pile();
    pile p2 = nouvelle_pile();
 
    p = ajouter_pile(p, 16);
    p = ajouter_pile(p, 47);
    p = ajouter_pile(p, 63);
    p = ajouter_pile(p, 15);
    p = ajouter_pile(p, 94);
    p = ajouter_pile(p, 01);
 
    division_en_deux(p, p1, p2);
 
    afficher_pile(p1);
    afficher_pile(p2);
 
 
    return 0;
}
Je veux que dans cette partie du code :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
 
 
afficher_pile(p1);
afficher_pile(p2);
Je puisse faire : afficher_pile(pointeur_de_p1);


Et c'est ma deuxième question : Sachant que je ne vois pas comment faire des pointeur de " pile1 " et " pile2 ", comment dois je m'y prendre ?

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Pour information, voici mon code pile.c :

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
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
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pile.h"
 
pile nouvelle_pile(void)
{
    return NULL;
}
 
////////////////////////////////////////////////
 
Bool est_elle_vide(pile p)
{
    if(p == NULL)
        return vrai;
    return faux;
}
 
////////////////////////////////////////////////
 
pile ajouter_pile(pile p, int x)
{
   element_pile *element;  // on déclare un pointeur parce qu'on veut que cette variable soit valable partout dans le code, pas seulement dans la sous-fonction.
 
   element = malloc(sizeof(*element));
   if(element == NULL)
   {
       fprintf(stderr, "Problème allocation dynamique.\n");
       exit(EXIT_FAILURE);
   }
 
   element -> valeur = x;
   element -> suivant = p; // c'est ici que la structure "pile" est créée (pas sûr, à demander)
 
   return element;
}
 
////////////////////////////////////////////////
 
pile supprimer_pile(pile p)
{
    element_pile *element; // on déclare element, c'est la partie de la pile que l'on va garder.
 
    if(est_elle_vide(p))
        return nouvelle_pile();
 
    element = p -> suivant; // on prend l'élément juste après élément, pour pouvoir isoler l'élément tout en haut de la pile, c'est à dire p.
    free(p);  // on enlève l'élément tout en haut de la pile, c'est à dire p.
 
    return supprimer_pile(element); // On appelle la fonction tant de fois qu'il le faut pour pouvoir supprimer tous les éléments de la pile. C'est la récursivité.
}
 
////////////////////////////////////////////////
 
//pile supprimer_pile_2(pile p)  // C'est la même fonction que supprimer_pile, mais écrite différement
//{
//    while(!est_elle_vide(p))
//      {
//          p = enlever_element(p);
//      }
//
//      return nouvelle_pile();
//}
 
////////////////////////////////////////////////
 
void afficher_pile(pile p)
{
    printf("\nVoici les valeurs de la liste :\n");
 
    if(est_elle_vide(p))
    {
        printf("Rien a afficher, la pile est vide\n");
        return;
    }
 
    while(!(est_elle_vide(p))) // Tant que la pile n'est pas vide, on "creuse", et on affiche chaque élément de la pile.
    {
        printf("[%d]\n", p -> valeur); // Afficher la valeur de l'élément de la pile.
        p = p -> suivant; //Pour pouvoir "creuser", on prend l'élément suivant pour pouvoir afficher l'élément suivant.
    }
}
 
////////////////////////////////////////////////
 
pile enlever_element(pile p)
{
    element_pile *element; // on déclare element, c'est la partie de la pile que l'on va garder.
 
    if(est_elle_vide(p))
        return nouvelle_pile();
 
    element = p -> suivant; // on prend l'élément juste après élément, pour pouvoir isoler l'élément tout en haut de la pile, c'est à dire p.
    free(p); // on enlève l'élément tout en haut de la pile, c'est à dire p.
    return element;
}
 
////////////////////////////////////////////////
 
int sommet_pile(pile p)
{
     if(est_elle_vide(p))
    {
        printf("Aucun sommet de pile, la pile est vide");
    }
 
    return p -> valeur;     // Par défaut, la pile pointe vers l'élément le plus en haut, le premier.
}
 
////////////////////////////////////////////////
 
pile milieu_pile(pile p)
{
    int i = 0;
     if(est_elle_vide(p))
    {
        printf("Aucun milieu de pile, la pile est vide");
    }
 
    for(i = 0; i < longueur_pile(p)/2; i++)
    {
         p = p->suivant;
    }
 
    return p;
}
 
////////////////////////////////////////////////
 
int bas_pile(pile p)
{
     if(est_elle_vide(p))
    {
        printf("Aucun bas de pile, la pile est vide");
    }
 
    while(p->suivant != NULL)
        {
            p = p->suivant;
        }
    return p -> valeur;
}
 
////////////////////////////////////////////////
 
int longueur_pile(pile p)
{
    int i = 0;
 
    if(est_elle_vide(p))
    {
        printf("Pas de longueur, la pile est vide");
        return;
    }
 
    while(!est_elle_vide(p))
    {
        i++;
        p = p -> suivant;
    }
 
    return i;
}
 
/* Une recherche dichotomique consiste à regarder d’abord l’élément au milieu, mais avec une pile,
    on est obligé de passer par tous les éléments au dessus pour regarder celui du milieu,
    donc autant les regarder aussi, et alors la recherche n’est plus dichotomique, donc pas de recherche dichotomique pour une pile */
 
int rechercher_pile(pile p)
{
    int valeur_recherche = 0;
    printf("\nQuelle valeur voulez - vous chercher ?\n");
    scanf("%d", &valeur_recherche);
 
    if(est_elle_vide(p))
    {
        printf("Rien a rechercher, la pile est vide\n");
        return;
    }
 
     do
     {
         if (p -> valeur == valeur_recherche)
        {
            printf("Chiffre present dans la pile\n");
            return p -> valeur;
        }
        p = p -> suivant;
     } while(!est_elle_vide(p));
 
     printf("Chiffre PAS PAS PAS present dans la pile\n");
 
}
 
////////////////////////////////////////////////
 
pile tri_croissant_pile(pile p)
{
    int echange = vrai;  // on met une variable echange à " vrai "
 
    while(echange == vrai) // tant que echange passe par vrai
    {
        while(p->suivant != NULL) // et tant que l'élément suivant n'est pas "NULL"
        {
            echange = faux; // on met echange à faux
            if (p->valeur > p->suivant->valeur) // si la valeur de la pile sur laquelle on est est supérieure à la valeur de la pile d'après
            {
               echanger(p); // on échange les deux valeurs
               echange = vrai;  // et on met echange à vrai
            }
            p = p->suivant; // ensuite, on passe à l'élément suivant
            if (p->suivant == NULL || (echange = vrai)) //si le pointeur vers la pile sur laquelle on est pointe vers "NULL" OU si echange est vrai
            {
                tri_croissant_pile(p); //alors on refait le code
            }
        }
        return p; // on retourne la pile ainsi triée
    }
}
 
////////////////////////////////////////////////
 
pile echanger(pile p)
{
    int i,temporaire;
 
    if (p->valeur > p->suivant->valeur)
    {
        temporaire = p->valeur;
        p->valeur = p->suivant->valeur;
        p->suivant->valeur = temporaire;
        //printf("P->VALEUR : %d\n",p->valeur);
        //printf("P->SUIVANT->VALEUR : %d\n",p->suivant->valeur);
    }
}
 
////////////////////////////////////////////////
 
pile division_en_deux(pile p, pile p1, pile p2)
{
    int a = milieu_pile(p)->suivant->valeur;
    element_pile *pile1;
    element_pile *pile2;
    pile1 = p1;
    pile2 = p2;
 
    while(!(p->valeur == a))
    {
        pile1 = ajouter_pile(pile1, p->valeur);
        p = p->suivant;
 
    }
 
    while(!( p == NULL))
    {
        pile2 = ajouter_pile(pile2, p->valeur); // ajoute l'élément souhaité
        p = p->suivant; // passe à la pile suivante
    }
}
 
////////////////////////////////////////////////
 
/*pile tri_des_piles(pile p)
{
 
}
 
////////////////////////////////////////////////
 
pile fusion_des_piles(pile p)
{
 
}*/
Et voici mon pile.h :

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
#ifndef PILE_H_INCLUDED
#define PILE_H_INCLUDED
 
// Booléen
 
typedef enum
{
    faux, // 0
    vrai  // 1
} Bool;
 
////////////////////////////////////////////////
 
// Définition d'une pile
 
typedef struct element_pile
{
    int valeur;
    struct element_pile *suivant;
} element_pile, *pile;
 
////////////////////////////////////////////////
 
// Prototype des fonctions
 
pile nouvelle_pile(void);
Bool est_elle_vide(pile p);
pile ajouter_pile(pile p, int x);
pile supprimer_pile(pile p);
void afficher_pile(pile p);
pile enlever_element(pile p);
int sommet_pile(pile p);
pile milieu_pile(pile p);
int bas_pile(pile p);
int longueur_pile(pile p);
int rechercher_pile(pile p);
int recherche_dichotomique_pile(pile p);
pile tri_croissant_pile(pile p);
int test_tri_croissant_pile(pile p);
pile echanger(pile p);
pile operation(pile p);
pile division_en_deux(pile p, pile p1, pile p2);
pile tri_des_piles(pile p);
pile fusion_des_piles(pile p);
 
#endif // PILE_H_INCLUDED