Diviser une pile en deux

**Haddock0** · 01/03/2018, 22h48

Salut à tous,

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

Dans mon sous-programme " fusion ", quand je mets le sommet_pile(p1) > sommet_pile(p2), ça plante, il me met dès la première itération (la boucle affichée précédemment) qu'il n'y a pas de sommet à p1. Je pense qu'il ne voit pas le sommet de la pile p1 EN COURS (Pourquoi ? Je ne sais pas). Qu'est ce que j'entends par EN COURS ? Voici un schéma qui le résume :https://www.cjoint.com/doc/18_02/HBCvxgqgOxs_image.png

Ce qu'il faudrait, c'est passer d'une pile p1 à une autre pile p1 et pareil pour p2, et ça, je ne vois pas comment faire.

La fonction " tri fusion " qui marche bien normalement :

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
pile tri_fusion(pile p)
{
    printf("\nSOUS PROGRAMME TRI_FUSION\n");
    pile p1 = nouvelle_pile();
    pile p2 = nouvelle_pile();
 
    if(est_elle_vide(p) || un_seul_element(p))
    {
        return p;
    }
 
    diviser(p, &p1, &p2);
 
    p1 = tri_fusion(p1);
 
    p2 = tri_fusion(p2);
 
    printf("------------------------------------------------------AFFICHAGE--------------------------------------------------------\n");
 
    printf("p1 :");
    afficher_pile(p1);
    printf("\n");
 
    printf("p2 :");
    afficher_pile(p2);
    printf("\n");
 
    printf("p :");
    afficher_pile(p);
    printf("\n");
 
    printf("-----------------------------------------------------FIN-AFFICHAGE-----------------------------------------------------\n");
 
    return fusion(p1, p2);
}

La fonction " fusion " avec laquelle je me bagarre :

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
pile fusion(pile p1, pile p2)
{
    printf("\nSOUS PROGRAMME FUSION\n");
    pile resultat = nouvelle_pile();
    int echange = vrai;
 
    printf("------------------------------------------------------AFFICHAGE--------------------------------------------------------\n");
 
    printf("p1 :");
    afficher_pile(p1);
    printf("\n");
 
    printf("p2 :");
    afficher_pile(p2);
    printf("\n");
 
    printf("-----------------------------------------------------FIN-AFFICHAGE-----------------------------------------------------\n");
 
 
    while(!(est_elle_vide(p1)) || !(est_elle_vide(p2)) && (echange == vrai))
    {
        echange = faux;
 
        if(sommet_pile(p1) > sommet_pile(p2))
        {
            echange = vrai;
 
            resultat = ajouter_pile(resultat, sommet_pile(p1));
            p1 = enlever_element(p1);
            //p2 = enlever_element(p2);
 
        }
 
 
        else
        {
            echange = vrai;
 
            resultat = ajouter_pile(resultat, sommet_pile(p2));
            //resultat = ajouter_pile(resultat, sommet_pile(p1));
 
            //p1 = enlever_element(p1);
            p2 = enlever_element(p2);
 
        }
    }
 
    printf("------------------------------------------------------AFFICHAGE--------------------------------------------------------\n");
 
    printf("resultat :");
    afficher_pile(resultat);
    printf("\n");
 
    printf("-----------------------------------------------------FIN-AFFICHAGE-----------------------------------------------------\n");
 
        return resultat;
 
    // et s'il reste ensuite des éléments dans une pile, terminer le travail
    // puis on note qu'on a mis les éléments dans l'ordre inverse de celui
    // voulu donc il reste encore quelque chose à faire pour les remettre
    // dans l'ordre.
}

Et pour information, les fonctions " echanger_element " et "diviser " qui interviennent mais qui sont justes :

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
////////////////////////////////////////////////
 
void echanger_element(pile *p1, pile *p2)
{
  pile temporaire = *p1;
  *p1 = *p2;
  *p2 = temporaire;
}
 
////////////////////////////////////////////////
 
void diviser(pile p, pile *p1, pile *p2)
{
    while(p)                                    
    {
        *p1 = ajouter_pile(*p1, sommet_pile(p));
        p = enlever_element(p);                 
        echanger_element(p1, p2);               
    }
}
 
////////////////////////////////////////////////

**foetus** · 02/03/2018, 05h29

Déjà, il faut nous montrer ta structure Pile (et aussi toutes les fonctions qui s'y rapportent)

: est-ce avec un tableau ou avec une liste chaînée

Et sur un autre fil de discussion récent sur le même thème, j'avais écrit qu'il ne faut jamais dépiler et empiler : il faut travailler "sur place" soit en inversant les valeurs (pour un tableau), soit en modifiant les liens (pour une liste chaînée)

**Wankyx** · 02/03/2018, 11h09

Moi je ferais comme ceci, la piles du compte sa taille entièrement jusqu'a que tu arriver en bas de la piles, tu divise la taille par deux .

tu fait une fonction qui prendre 2 paramètre, le premier étant la piles en elle même, le second étant la moitie des première valeurs de la piles et le troisième le reste des valeurs de la piles, et le fait de diviser la taille par deux c'est pour faire ce que j'ai dit au dessus .

Après "couper une piles en deux" détruit un peu le principe d'une piles .

**foetus** · 03/03/2018, 06h10

Envoyé par Wankyx

Moi je ferais comme ceci, la piles du compte sa taille entièrement jusqu'a que tu arriver en bas de la piles, tu divise la taille par deux .

tu fait une fonction qui prendre 2 paramètre, le premier étant la piles en elle même, le second étant la moitie des première valeurs de la piles et le troisième le reste des valeurs de la piles, et le fait de diviser la taille par deux c'est pour faire ce que j'ai dit au dessus .

Cela il le sait parce que je lui ai déjà dit dans ce fil de discussion

Envoyé par Wankyx

Après "couper une piles en deux" détruit un peu le principe d'une piles .

Pas forcément. Si ta pile est implémentée avec une liste chaînée, tu n'as qu'à casser un lien pour diviser ta pile ... et pas qu'au milieu (mais je lui ai déjà dit dans l'autre fil de discussion)

Mais si la division est "aussi spéciale" (prendre 1 sur 2), c'est pour, à ce que je soupçonne, éviter de stocker le nombre d'éléments : c'est comme une division dichotomique entrelacée

Ensuite, avec un tri fusion, lorsque tu divises ta collection en 2, c'est pendant la descente : donc l'ordre n'est pas important puisque c'est le double principe :

Diviser pour régner (<- lien Wiki)
On ne sait pas trier plus d'1 ou 2 valeurs

Envoyé par Wankyx

Après "couper une piles en deux" détruit un peu le principe d'une piles .

Non le pire c'est : TRIER UNE PILE AVEC UN TRI FUSION, C'EST DE LA M$RD$ EN BOÎTE

mais qui a eu cette idée folle (<- et ce n'est pas ce sacré Charlemagne

)

Le problème est le suivant

Ta pile : 1 -> 15 -> 63 -> 47 -> 16 -> 94
Tri fusion : étape 1 - la division 01 - P1: 94 -> 47 -> 15, P2: 16 -> 63 ->1
Tri fusion : étape 2 - la division 02 - P1: 94 -> 15, P2: 47
Tri fusion : étape 3 - la division 03 - P1: 94, P2: 15
Tri fusion : étape 5 - la remontée 03 - P: 15 -> 94
Tri fusion : étape 6 - la remontée 02 - Là ton algo est flingué

Parce que comme c'est une pile, tu vas comparer les 2 hauts de piles (donc il faut une pile avec les valeurs les plus grandes en bas et les plus petites en haut), mais tu vas empiler les valeurs de la plus petite à la plus grande.
Donc si tu n'inverses pas ta pile ou tes comparaisons à chaque fois, la première fois cela fonctionne. Ensuite, poubelle parce que tu vas te retrouver avec les plus grandes valeurs en haut.

Un exemple en "quick & dirty", avec une liste chaînée et et des algos "in place" (<- lien wiki)

Édit 1: Pendant mon tri fusion (fonction stack_sort_fusion1), j'empile par le bas (et non pas le haut) - Donc c'est le comportement d'une file (queue - FIFO en anglais)
Édit 1: Et si on veut trier par ordre croissant ou décroissant, il y a juste l'inversion de la pile a activé ou a désactivé dans la fonction stack_sort_fusion.
Édit 2: Je pourrais alléger mon code en ne gérant que le haut de la pile (et non pas le bas qui ne sert que pour ce fichu tri fusion)

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
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
#include <stdio.h>
#include <stdlib.h>
 
typedef unsigned char TYPE_RETURN;
typedef unsigned int  STACKED_TYPE;
 
 
typedef enum e_return_value {
    RETURN_ERROR = 0,
    RETURN_OK,
    RETURN_STACK_IS_EMPTY
} RETURN_VALUE;
 
 
typedef struct s_stack_element {
    STACKED_TYPE value;
 
    struct s_stack_element* next;
} Stack_Element;
 
 
typedef struct s_one_stack {
    Stack_Element* bottom;
    Stack_Element* top;
} One_Stack;
 
 
#define CLEAN_ALL \
    printf("\n***** Empty *****\n"); \
     \
    stack_empty(&one_stack); \
     \
    printf("\n***** Destroy *****\n"); \
     \
    stack_destroy(&another_stack);
 
 
#define TEST_RETURN(ret, msg, value) \
    if (ret == RETURN_OK) { \
        printf("%s %d - OK\n", msg, value); \
    } else if (ret == RETURN_ERROR) { \
        printf("%s - ERROR\n", msg); \
         \
        CLEAN_ALL \
         \
        return 1; \
    } else  if (ret == RETURN_STACK_IS_EMPTY) { \
        printf("%s - stack is empty\n", msg); \
    }
 
 
#define stack_init(one_stack) \
    one_stack.bottom = NULL; \
    one_stack.top    = NULL;
 
 
// Private macros
#define STACK_HAS_AT_LEAST_2_ELEMENTS(one_stack) ((one_stack.top != one_stack.bottom) && (one_stack.bottom != NULL))
 
//#define STACK_HAS_ONLY_ONE_ELEMENT(one_stack) ((one_stack.top == one_stack.bottom) && (one_stack.bottom != NULL))
 
#define STACK_IS_EMPTY(one_stack) (one_stack.top == NULL)
//#define STACK_IS_EMPTY(one_stack) ((one_stack.top == NULL) && (one_stack.bottom == NULL))
 
#define STACK_IS_NOT_EMPTY(one_stack) ((one_stack.top != NULL) && (one_stack.bottom != NULL))
 
 
TYPE_RETURN stack_create_init(One_Stack** one_stack) {
    TYPE_RETURN ret;
 
    if (one_stack != NULL) {
        One_Stack* new_stack = (One_Stack*) malloc( sizeof(One_Stack) );
 
        if (new_stack != NULL) {
            stack_init( (*new_stack) )
            (*one_stack) = new_stack;
 
            ret = RETURN_OK;
        } else {
            (*one_stack) = NULL;
 
            ret = RETURN_ERROR;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
// XXX : synchronize function stack_destroy and function stack_empty
TYPE_RETURN stack_destroy(One_Stack** one_stack) {
    TYPE_RETURN ret;
 
    if (one_stack != NULL) {
        if ((*one_stack) != NULL) {
            Stack_Element* element = (*one_stack)->top;
            Stack_Element* next;
 
 
            while (element != NULL) {
                if (element != (*one_stack)->bottom) {
                    printf("Destroy : %u\n", element->value);
                } else {
                    printf("Destroy : %u <- bottom\n", element->value);
                }
 
                next = element->next;
 
                free(element);
 
                element = next;
            }
 
            free( (*one_stack) );
            (*one_stack) = NULL;
 
            ret = RETURN_OK;
        } else {
            ret = RETURN_ERROR;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
TYPE_RETURN stack_divide_every_other_value(One_Stack* one_stack, One_Stack* another_stack) {
    TYPE_RETURN ret;
 
    if ((one_stack != NULL) && (another_stack != NULL)) {
        if (one_stack->top != NULL) {
            Stack_Element* element    = one_stack->top;
            Stack_Element* next       = element->next;
            Stack_Element* new_bottom = element;
            Stack_Element* new_top    = element;
 
            another_stack->bottom = next;
            another_stack->top    = next;
 
            if (next != NULL) {
                next = next->next; // Start at the third element
 
                while (next != NULL) {
                    element = next;
 
                    next = element->next;
 
                    element->next = new_top;
                    new_top = element;
 
                    if (next != NULL) {
                        element = next;
 
                        next = element->next;
 
                        element->next = another_stack->top;
                        another_stack->top = element;
                    }
                }
 
//              XXX : Here because another_stack->bottom can be NULL
//              XXX : At last in order to not break links
                another_stack->bottom->next = NULL;
            }
 
//          XXX : At last in order to not break links
            new_bottom->next  = NULL;
 
            one_stack->bottom = new_bottom;
            one_stack->top    = new_top;
 
            ret = RETURN_OK;
        } else {
            another_stack->bottom = NULL;
            another_stack->top    = NULL;
 
            ret = RETURN_STACK_IS_EMPTY;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
// XXX : synchronize function stack_destroy and function stack_empty
void stack_empty(One_Stack* one_stack) {
    if (one_stack != NULL) {
        Stack_Element* element = one_stack->top;
        Stack_Element* next;
 
        while (element != NULL) {
            if (element != one_stack->bottom) {
                printf("Empty : %u\n", element->value);
            } else {
                printf("Empty : %u <- bottom\n", element->value);
            }
 
            next = element->next;
 
            free(element);
 
            element = next;
        }
    }
}
 
 
TYPE_RETURN stack_pop(One_Stack* one_stack, STACKED_TYPE* value) {
    TYPE_RETURN ret;
 
    if ((one_stack != NULL) && (value != NULL)) {
        if (one_stack->top != NULL) {
            Stack_Element* element = one_stack->top;
            Stack_Element* next;
 
            (*value) = element->value;
 
            next = element->next;
 
            free(element);
 
            one_stack->top = next;
 
            if (one_stack->top == NULL) { one_stack->bottom = NULL; }
 
            ret = RETURN_OK;
        } else {
           ret = RETURN_STACK_IS_EMPTY;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
void stack_print(One_Stack* one_stack) {
    if (one_stack != NULL) {
        Stack_Element* element = one_stack->top;
 
        if (element != NULL) {
            while (element != NULL) {
                if (element != one_stack->bottom) {
                    printf("Value : %u\n", element->value);
                } else {
                    printf("Value : %u <- bottom\n", element->value);
                }
 
                element = element->next;
            }
        } else {
            printf("Stack is empty - %s", ((element == one_stack->bottom)? "OK": "top != bottom"));
        }
    }
}
 
 
TYPE_RETURN stack_push(One_Stack* one_stack, STACKED_TYPE value) {
    TYPE_RETURN ret;
 
    if (one_stack != NULL) {
        Stack_Element* new_element = (Stack_Element*) malloc( sizeof(Stack_Element) );
 
        if (new_element != NULL) {
            if ( STACK_IS_NOT_EMPTY( (*one_stack) ) ) {
                new_element->value = value;
                new_element->next  = one_stack->top;
                one_stack->top     = new_element;
            } else {
                new_element->value = value;
                new_element->next  = NULL;
                one_stack->bottom  = new_element;
                one_stack->top     = new_element;
            }
 
            ret = RETURN_OK;
        } else {
            ret = RETURN_ERROR;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
// XXX : The top most element should be the lowest value
// XXX : Because the lowest value is popped to be "pushed"
// XXX : To avoid to reverse the stack at the end, the value is pushed at the bottom
TYPE_RETURN stack_sort_fusion1(One_Stack* one_stack) {
    TYPE_RETURN ret;
 
    if ( STACK_IS_NOT_EMPTY( (*one_stack) ) ) {
        if ( STACK_HAS_AT_LEAST_2_ELEMENTS( (*one_stack) ) ) {
            One_Stack another_stack;
 
//          printf("\n***************\n");
//          printf("***** Stack *****\n"); stack_print(one_stack);
 
            stack_init(another_stack);
 
            ret = stack_divide_every_other_value(one_stack, &another_stack);
 
            if ((ret == RETURN_OK) && STACK_HAS_AT_LEAST_2_ELEMENTS( (*one_stack) )) { ret = stack_sort_fusion1(one_stack); }
            if ((ret == RETURN_OK) && STACK_HAS_AT_LEAST_2_ELEMENTS(another_stack))  { ret = stack_sort_fusion1(&another_stack); }
 
//          Fusion
            if (ret == RETURN_OK) {
                if ( STACK_IS_EMPTY( (*one_stack) ) ) { ret = RETURN_ERROR; }
            }
 
            if (ret == RETURN_OK) {
                if ( STACK_IS_EMPTY(another_stack) ) { ret = RETURN_ERROR; }
            }
 
            if (ret == RETURN_OK) {
                Stack_Element* current_top1;
                Stack_Element* current_top2;
                Stack_Element* new_bottom;
                Stack_Element* new_top;
 
//              printf("\n***** Stack 1 *****\n"); stack_print(one_stack);
//              printf("\n***** Stack 2 *****\n"); stack_print(&another_stack);
//              printf("\n*****  *****\n");
 
                current_top1 = one_stack->top;
                current_top2 = another_stack.top;
 
//              First : the lowest top is pushed
                if (current_top1->value > current_top2->value) {
                    new_bottom = current_top2;
                    new_top    = current_top2;
 
                    current_top2 = current_top2->next;
                } else {
                    new_bottom = current_top1;
                    new_top    = current_top1;
 
                    current_top1 = current_top1->next;
                }
 
//              Second : the lowest value is pushed
                while ((current_top1 != NULL) && (current_top2 != NULL)) {
//                  printf("\n*****  *****\n");
 
                    if (current_top1->value > current_top2->value) {
//                      printf("Pop 2 : %d\n", current_top2->value);
 
                        new_bottom->next = current_top2;
                        new_bottom       = current_top2;
                        current_top2     = current_top2->next;
                    } else {
//                      printf("Pop 1 : %d\n", current_top1->value);
 
                        new_bottom->next = current_top1;
                        new_bottom       = current_top1;
                        current_top1     = current_top1->next;
                    }
                }
 
//              Third : One stack is not empty : push the rest of the stack
                if ((current_top1 == NULL) && (current_top2 != NULL)) {
                    new_bottom->next = current_top2;
 
                    one_stack->bottom = another_stack.bottom;
                    one_stack->top    = new_top;
 
                    ret = RETURN_OK;
                } else if ((current_top1 != NULL) && (current_top2 == NULL)) {
                    new_bottom->next = current_top1;
 
                    one_stack->bottom = one_stack->bottom;
                    one_stack->top    = new_top;
 
                    ret = RETURN_OK;
                } else {
                    ret = RETURN_ERROR;
                }
            }
        } else {
//          Stack is sorted
            ret = RETURN_OK;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
TYPE_RETURN stack_sort_fusion(One_Stack* one_stack) {
    TYPE_RETURN ret;
 
    if (one_stack != NULL) {
        if ( STACK_IS_NOT_EMPTY( (*one_stack) ) ) {
            ret = stack_sort_fusion1(one_stack);
 
            if ((ret == RETURN_OK) && ( STACK_HAS_AT_LEAST_2_ELEMENTS( (*one_stack) ) )) {
//              Reverse the stack
                Stack_Element* current;
                Stack_Element* next;
                Stack_Element* new_bottom;
                Stack_Element* new_top;
 
                new_bottom = one_stack->top;
                new_top    = new_bottom;
 
                current = new_top->next;
 
                while (current != NULL) {
                    next          = current->next;
                    current->next = new_top;
                    new_top       = current;
 
                    current       = next;
                }
 
                new_bottom->next  = NULL;
 
                one_stack->bottom = new_bottom;
                one_stack->top    = new_top;
            }
        } else {
//          Nothing to do
            ret = RETURN_OK;
        }
    } else {
        ret = RETURN_ERROR;
    }
 
    return ret;
}
 
 
int main(int argc, char** argv)
{
    One_Stack one_stack;
    One_Stack* another_stack = NULL;
    STACKED_TYPE value;
    TYPE_RETURN ret;
 
    stack_init(one_stack);
    ret = stack_create_init(&another_stack); TEST_RETURN(ret, "main : create init", 66)
 
    printf("***** Init *****\n");
 
    ret = stack_push(&one_stack, 94); TEST_RETURN(ret, "main : push", 94)
    ret = stack_push(&one_stack, 16); TEST_RETURN(ret, "main : push", 16)
    ret = stack_push(&one_stack, 47); TEST_RETURN(ret, "main : push", 47)
    ret = stack_push(&one_stack, 63); TEST_RETURN(ret, "main : push", 63)
    ret = stack_push(&one_stack, 15); TEST_RETURN(ret, "main : push", 15)
    ret = stack_push(&one_stack,  1); TEST_RETURN(ret, "main : push",  1)
//  ret = stack_push(&one_stack, 58); TEST_RETURN(ret, "main : push", 58)
//  ret = stack_push(&one_stack, 33); TEST_RETURN(ret, "main : push", 33)
 
    stack_print(&one_stack);
 
//  printf("\n***** 3 pops *****\n");
//
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//
//  stack_print(&one_stack);
 
    printf("\n***** sort fusion *****\n");
 
    ret = stack_sort_fusion(&one_stack); TEST_RETURN(ret, "main : sort fusion", 67)
 
    stack_print(&one_stack);
 
//  printf("\n***** divide every other value *****\n");
//
//  ret = stack_divide_every_other_value(&one_stack, another_stack); TEST_RETURN(ret, "main : divide every other value", 67)
//
//  stack_print(&one_stack);
//
//  printf("\n*****  *****\n");
//
//  stack_print(another_stack);
 
//  printf("\n***** 4 pops *****\n");
//
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//
//  stack_print(&one_stack);
//
//  printf("\n***** 2 pops *****\n");
//
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//  ret = stack_pop(one_stack, &value); TEST_RETURN(ret, "main : pop", value)
//
//  stack_print(&one_stack);
 
    CLEAN_ALL
 
    return 0;
}

**Haddock0** · 04/03/2018, 00h19

Avec les programmes suivants :

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pile.h"
#include "pile.c"
#include <assert.h>
 
int main()
{
    pile p = nouvelle_pile();
    pile p1 = nouvelle_pile();
    pile p2 = nouvelle_pile();
 
    p = ajouter_pile(p, 94);
    p = ajouter_pile(p, 16);
    p = ajouter_pile(p, 47);
    p = ajouter_pile(p, 63);
    p = ajouter_pile(p, 15);
    p = ajouter_pile(p, 01);
 
    printf("p :");
    afficher_pile(p);
    printf("\n");
 
    printf("Tri fusion :\n");
    tri_fusion(p);
    printf("\n");
 
	return 0;
}

Sous programmes :

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
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pile.h"
#include <assert.h>
 
pile nouvelle_pile(void)
{
    return NULL;
}
 
////////////////////////////////////////////////
 
Bool est_elle_vide(pile p)
{
    if(p == NULL)
        return vrai;
    return faux;
}
 
////////////////////////////////////////////////
 
Bool un_seul_element(pile p)
{
    if(p->suivant == 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 pile :\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;
}
 
////////////////////////////////////////////////
 
void echanger_element(pile *p1, pile *p2)
{
  pile temporaire = *p1;
  *p1 = *p2;
  *p2 = temporaire;
}
 
////////////////////////////////////////////////
 
void diviser(pile p, pile *p1, pile *p2)
{
    while(p)                                    // Tant que p n'est pas vide
    {
        *p1 = ajouter_pile(*p1, sommet_pile(p));// Ajouter le sommet de p à p1
        p = enlever_element(p);                 // Enlever le sommet de p
        echanger_element(p1, p2);               // S'assurer que l'on va ajouter au vieux p2 /!\ DEMANDER : JE COMPRENDS PAS
    }
}
////////////////////////////////////////////////
 
pile tri_fusion(pile p)
{
    printf("\nSOUS PROGRAMME TRI_FUSION\n");
    pile p1 = nouvelle_pile();
    pile p2 = nouvelle_pile();
 
    if(est_elle_vide(p) || un_seul_element(p))
    {
        return p;
    }
 
    diviser(p, &p1, &p2);
 
    p1 = tri_fusion(p1);
 
    p2 = tri_fusion(p2);
 
    printf("------------------------------------------------------AFFICHAGE--------------------------------------------------------\n");
 
    printf("p1 :");
    afficher_pile(p1);
    printf("\n");
 
    printf("p2 :");
    afficher_pile(p2);
    printf("\n");
 
    printf("p :");
    afficher_pile(p);
    printf("\n");
 
    printf("-----------------------------------------------------FIN-AFFICHAGE-----------------------------------------------------\n");
 
    return fusion(p1, p2);
}
 
////////////////////////////////////////////////
 
pile fusion(pile p1, pile p2)
{
    printf("\nSOUS PROGRAMME FUSION\n");
    pile resultat = nouvelle_pile();
    int echange = vrai;
 
    printf("------------------------------------------------------AFFICHAGE--------------------------------------------------------\n");
 
    printf("p1 :");
    afficher_pile(p1);
    printf("\n");
 
    printf("p2 :");
    afficher_pile(p2);
    printf("\n");
 
    printf("-----------------------------------------------------FIN-AFFICHAGE-----------------------------------------------------\n");
 
 
    while(!(est_elle_vide(p1)) || !(est_elle_vide(p2)) && (echange == vrai))
    {
        echange = faux;
 
        if(sommet_pile(p1) > sommet_pile(p2))
        {
            echange = vrai;
 
            resultat = ajouter_pile(resultat, sommet_pile(p1));
            p1 = enlever_element(p1);
            //p2 = enlever_element(p2);
 
        }
 
 
        else
        {
            echange = vrai;
 
            resultat = ajouter_pile(resultat, sommet_pile(p2));
            //resultat = ajouter_pile(resultat, sommet_pile(p1));
 
            //p1 = enlever_element(p1);
            p2 = enlever_element(p2);
 
        }
    }
 
    printf("------------------------------------------------------AFFICHAGE--------------------------------------------------------\n");
 
    printf("resultat :");
    afficher_pile(resultat);
    printf("\n");
 
    printf("-----------------------------------------------------FIN-AFFICHAGE-----------------------------------------------------\n");
 
        return resultat;
 
    // et s'il reste ensuite des éléments dans une pile, terminer le travail
    // puis on note qu'on a mis les éléments dans l'ordre inverse de celui
    // voulu donc il reste encore quelque chose à faire pour les remettre
    // dans l'ordre.
}
 
 
 
////////////////////////////////////////////////

Définition d'une pile :

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
#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;
 
 
#endif // PILE_H_INCLUDED

**foetus** · 04/03/2018, 02h46

Avec ton typedef, tu caches le pointeur.
Fuite mémoire dans le main + 2 variables inutiles (<- si tu actives tous les alertes du compilateur tu dois le voir passer *)
Fuite mémoire dans la fonction tri_fusion. Et en récursive, c'est le pompon
Oubli des déclarations anticipées ("forward declaration" en anglais) et/ ou tu ne sais pas faire une entête C (ne pas inclure un fichier .c )
Déjà dit : ta division fonctionne, mais elle fait 1,5 parcours de ta liste chaînée. Et en plus tu alourdis ton code avec 2 fonctions.
Déjà dit : ton système de log ne sert à rien tant que le programme plante/ quitte en fuitant/ ne s'interrompt pas en cas d'erreur.
Ton code est lourd parce qu'il ne respecte pas les "standards" : une pile doit avoir la fonction pop (que tu remplaces par ajouter_pile + enlever_element) et push (tu remplaces par ajouter_pile)
Ta fonction sommet_pile est fausse et plante avec une pile vide (***)
À vérifier : ta fonction milieu_pile est fausse et plante avec une pile vide. Et pour la même raison que la fonction sommet_pile (***)
Ta fonction bas_pile est fausse et plante avec une pile vide. Et pour la même raison que la fonction sommet_pile (***)
Ta fonction longueur_pile est fausse (<- si tu actives tous les alertes du compilateur tu dois le voir passer **) (***)
Pourquoi tu n'utilises pas ta fonction est_elle_vide dans la fonction diviser ? On voit le code corrigé et le code à produire
Dans la fonction fusion ton booléen ne sert à rien. Tu l'affectes à vrai dans le cas si et sinon
Je ne suis pas fan de la fonction enlever_element qui fait une destruction récursive

Et je ne parle pas des conventions de codage (surtout pour une petite bibliothèque), du "passage double pointeur" VS "passage simple retour + retour" (***) et de tous les appels fonctions inutiles.

Code :

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

echanger_element(p1, p2);               // S'assurer que l'on va ajouter au vieux p2 /!\ DEMANDER : JE COMPRENDS PAS

C'est un truc classique

Tu as 2 pointeurs P1 (qui pointe vers A) et P2 (qui pointe vers B)
Tu ne travailles qu'avec P1.
Mais comme tu échanges les pointeurs à chaque fois, alors P1 pointe alternativement vers A et vers B (1 fois sur 2).

Dans ton cas

, tu vas alternativement empiler sur la première pile et sur la deuxième pile (1 fois sur 2).
Mais, à la fin, tu ne sais plus qui de P1 et de P2, pointe vers la première pile et vers la deuxième pile.

* ->

main.c:11:10: warning: unused variable ‘p2’ [-Wunused-variable]
pile p2 = nouvelle_pile();
^
main.c:10:10: warning: unused variable ‘p1’ [-Wunused-variable]
pile p1 = nouvelle_pile();

** ->

warning: ‘return’ with no value, in function returning non-void

*** -> Tu n'arrives pas à gérer correctement la pile vide

parce que tu ne peux avoir qu'1 seul type de retour, que tu utilises déjà pour retourner une pile résultat et qui t'empêche donc te passer un message "pile vide" (qui n'est pas forcément une erreur)

Diviser une pile en deux

C

Vue hybride

Discussions similaires

Partager

Partager