Division d'une pile en deux piles

**Haddock0** · 03/02/2018, 19h06

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

**foetus** · 03/02/2018, 19h25

Ton code est pourri

milieu_pile(p)->suivant->valeur; ici il faut faire 2 tests NULL sinon tu plantes
(!(p->valeur == a)) est équivalent à (p->valeur != a)
return p1; Pourquoi un return sans tests, sans rien en pleine boucle ?

Le plus gros point c'est qu'est ce qu'est censé faire ton code ?

Parce que justement si tu utilises une liste chaînée (puisque ta pile LIFO c'est bien cela) au lieu d'un tableau, on ne doit jamais recopier les valeurs. Si on veut couper une liste chaînée à un endroit on sauvegarde le suivant et on y met NULL.

Édit : Même avec un tableau, on travaille avec des intervalles d'index pour éviter des copies partielles de tableau

**Haddock0** · 04/02/2018, 12h45

milieu_pile(p)->suivant->valeur; ici il faut faire 2 tests NULL sinon tu plantes
(!(p->valeur == a)) est équivalent à (p->valeur != a)
return p1; Pourquoi un return sans tests, sans rien en pleine boucle ?

Le plus gros point c'est qu'est ce qu'est censé faire ton code ?

Parce que justement si tu utilises une liste chaînée (puisque ta pile LIFO c'est bien cela) au lieu d'un tableau, on ne doit jamais recopier les valeurs. Si on veut couper une liste chaînée à un endroit on sauvegarde le suivant et on y met NULL.

Bonjour,

1) Pourquoi ça plante si je ne fais pas deux tests nuls ?
2) Sur un autre forum, un mec m'a dit qu'en faisant " != " j'assignais, je ne comparais pas, ducoup pour ne pas qu'il m'emm... par la suite, j'ai adopté cette écriture de mer...
3) Le return p1 est un test de ma part, je suis conscient que ça ne marche pas

Ce que je veux faire : Trier une pile en utilisant les fonctions " dépiler " et " empiler " et en utilisant un tri fusion en 3 étapes : division_en_deux ; tri_des_piles ; fusion_des_piles.

Voici le code de base :

Le 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
24
25
26
27
28
29
30
31
32
33
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pile.h"
#include "pile.c"
 
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);
 
    afficher_pile(p);
 
    printf("Sommet actuel : %d\n", sommet_pile(p));
    printf("Longueur pile : %d\n", longueur_pile(p));
 
    division_en_deux(p, p1, p2);
 
    afficher_pile(p1);
    afficher_pile(p2);
 
 
    return 0;
}

Le fichier 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
#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; // ici je met a et b, parce que si je les inclut dans la boucle, "milieu_pile()" ne va pas arrêter de mettre à jour le nouveau milieu de la pile. C'est pour ça que je le fixe en début de fonction.
 
    printf("\nListe 1\n");
    while(!(p->valeur == a))
    {
        p1 = ajouter_pile(p1, p->valeur);
        printf("[%d]\n", p1->valeur);
        p = p->suivant;
    }
 
    printf("\nListe 2\n");
    while(!( p == NULL))
    {
        p2 = ajouter_pile(p2, p->valeur);
        printf("[%d]\n", p2->valeur);
        p = p->suivant;
    }
}
 
////////////////////////////////////////////////
 
/*pile tri_des_piles(pile p)
{
 
}
 
////////////////////////////////////////////////
 
pile fusion_des_piles(pile p)
{
 
}*/

Et le fichier 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
47
48
 
 
#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

Voilà, j'espère que le code est un peu moins pourri

Le problème est dans ma fonction diviser_en_deux, ici j'affiche les éléments en me servant de la boucle while, et j'aimerais qu'au lieu de ça , il me les affiche en utilisant la sous fonction affichage :

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; // ici je met a et b, parce que si je les inclut dans la boucle, "milieu_pile()" ne va pas arrêter de mettre à jour le nouveau milieu de la pile. C'est pour ça que je le fixe en début de fonction.
 
    printf("\nListe 1\n");
    while(!(p->valeur == a))
    {
        p1 = ajouter_pile(p1, p->valeur);
        printf("[%d]\n", p1->valeur);
        p = p->suivant;
    }
 
    printf("\nListe 2\n");
    while(!( p == NULL))
    {
        p2 = ajouter_pile(p2, p->valeur);
        printf("[%d]\n", p2->valeur);
        p = p->suivant;
    }
}

**foetus** · 04/02/2018, 16h14

La difficulté que tu as c'est ta structure de données : une liste chaînée

... même si niveau place mémoire c'est x2 (à cause du pointeur)

Une liste chaînée est adaptée pour coder une pile LIFO, mais le problème de cette structure c'est :

accès à un "index" non direct
impossible de revenir en arrière, à moins de faire une liste doublement chaînée
on ne connaît pas le nombre de valeurs, même si avec une autre structure c'est pareil, et du moins en C.

Donc pour couper une liste chaînée SANS RECOPIE il faut faire 2 choses :

Stocker le nombre de valeurs. Comme cela tu sauras toujours où est ton milieu.
Dépiler plusieurs éléments en 1 fois

Par exemple avec une pile p1: 9 -> 7 -> 6 -> 4 -> 3 -> 2 -> NULL

pop(/*in_out*/ p1, /*out*/p2) == pop(/*in_out*/ p1, /*out*/p2, 1) - retour TRUE, p1: 7 -> 6 -> 4 -> 3 -> 2 -> NULL, p2: 9 -> NULL
pop(/*in_out*/ p1, /*out*/p2, 0) - retour TRUE, p1: 9 -> 7 -> 6 -> 4 -> 3 -> 2 -> NULL, p2: NULL
pop(/*in_out*/ p1, /*out*/p2, 3) - retour TRUE, p1: 4 -> 3 -> 2 -> NULL, p2: 9 -> 7 -> 6 -> NULL
pop(/*in_out*/ p1, /*out*/p2, 4) - retour TRUE, p1: 3 -> 2 -> NULL, p2: 9 -> 7 -> 6 -> 4 -> NULL
pop(/*in_out*/ p1, /*out*/p2, 6) - retour TRUE, p1: NULL, p2: 9 -> 7 -> 6 -> 4 -> 3 -> 2 -> NULL
pop(/*in_out*/ p1, /*out*/p2, 9) - retour FALSE

Et si tu observes bien

tu vois que l'algo de dépilement multiple est comme je l'ai dit : sauf cas particulier, tu affectes à p2 p1, tu parcoures ta liste chaînée avec un compteur, et lorsque tu es arrivé à l'élément X, tu affectes à p1 X->next et tu y mets NULL.

**Haddock0** · 04/02/2018, 22h28

Salut,

Et merci beaucoup pour ta réponse, je vais m'empresser d'essayer ce que tu dis, mais j'ai essayé ce code, et apparemment, il marche. Pourrais tu me dire ce que t'en penses, si c'est mal fait, si la méthode est correcte ? Pourrais je utiliser ce code par la suite pour ce que je compte faire ?

Ce sont les deux fonctions qui retournent p1 et p2 (Puis-je regrouper ces deux fonctions en une par exemple ?)

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
 
////////////////////////////////////////////////
 
pile division_en_deux_p1(pile p, pile p1, pile p2)
{
    int a = milieu_pile(p)->suivant->valeur; // ici je met a et b, parce que si je les inclut dans la boucle, "milieu_pile()" ne va pas arrêter de mettre à jour le nouveau milieu de la pile. C'est pour ça que je le fixe en début de fonction.
 
    //printf("\nListe 1\n");
    while(p->valeur != a)
    {
        p1 = ajouter_pile(p1, p->valeur);
        //printf("[%d]\n", p1->valeur);
        p = p->suivant;
    }
 
    return p1;
}
 
////////////////////////////////////////////////
 
pile division_en_deux_p2(pile p, pile p1, pile p2)
{
    //printf("\nListe 2\n");
    int a = milieu_pile(p)->suivant->valeur;
 
        while(p->valeur != a)
        {
            p = p->suivant;
        }
 
        while(p!= NULL)
        {
            p2 = ajouter_pile(p2, p->valeur);
            //printf("[%d]\n", p2->valeur);
            p = p->suivant;
        }
 
    return p2;
}
 
////////////////////////////////////////////////

Et voici le main correspondant :

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
 
 
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);
 
    afficher_pile(p);
 
    division_en_deux_p1(p, p1, p2);
    division_en_deux_p2(p, p1, p2);
 
    afficher_pile(division_en_deux_p1(p, p1, p2));
    afficher_pile(division_en_deux_p2(p, p1, p2));
 
    return 0;
}

Et voici ce qu'il m'affiche, ici je pense que c'est normal, on prends l'élément du haut de p, qui se retrouve à être l'élément tout en bas de p1, et même chose pour p2:
Nom : console.png
Affichages : 261
Taille : 4,2 Ko

Nom : console.png
Affichages : 261
Taille : 4,2 Ko

**foetus** · 04/02/2018, 23h25

Ouais

mais tu fais 2 parcours complets pour diviser ta pile + une RECOPIE PARTIELLE :

1 parcours pour compter le nombre d'éléments. Lorsque je te dis qu'il faut le mettre dans ta structure et le maintenir à jour
1/ 2 parcours pour renvoyer le milieu
1/ 2 parcours pour dépiler une pile et empiler l'autre. D'ailleurs je ne suis pas sûr que tu dépiles et c'est pour cela que tu dois avoir 3 piles alors que tu peux tout faire in-place (<- lien wiki)

Code :

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

milieu_pile(p)->suivant->valeur

2^ième fois : ce code peut planter

Si ta pile est vide, milieu_pile(p) retourne p donc NULL : NULL->suivant == BOUM
Si ta pile a 1 élément E, milieu_pile(p) retourne E, E->suivant == NULL == OK, NULL->valeur == BOUM

Un conseil : Tes affichages erreur ne servent à rien

Apprends à retourner un booléen (en C unsigned char ou char) et de tester à CHAQUE appel le retour avec des erreurs de type énuméré pour donner un sens à l'erreur en cas de problème.

Division d'une pile en deux piles

C

Discussions similaires

Partager

Partager