Discussion :

[bounadalvidal]

Bonjours tous,

Je suis toujours en train de vagabonder sur des exercices de pile, je voulais juste pour m'entrainer créer une fonction qui efface le premier élément ajouté à une pile (donc le dernier en vrai dans la liste) :

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
 
#include <stdio.h>
#include <stdlib.h>
 
//-------------------------------------------
///définir la structure
//-------------------------------------------
   typedef struct pile
        {
                int valeur;
                struct pile *prec;
        } pile ;
 
//-------------------------------------------
/// intitialiser la pile à NULL
//-------------------------------------------
 pile *MaPile = NULL;
 
//------------------------------------------
///fonction d'ajout dans la liste chaînée
//-------------------------------------------
pile * add(pile ** p,int val) {
        pile * n=malloc(sizeof(pile));
        n->prec= *p;
        *p=n;
        n->valeur= val;
        return *p;}

Jusque là, c'est des préliminaires nécessaire pour la compréhension du problème, le voilà le code de la fonction qui m'intéresse (et qui ne marche pas !) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void efface_first(pile **p){
 
        pile * n=*p;
        pile * m=(*p)->prec;
        pile * k;
        while (m)
        {
            add(k,n->valeur);
        }
 
        *p = k;
}

[diogene]

Il ne faut pas procéder de cette façon pour enlever le sommet de la pile :

1- Détacher le sommet de la pile de la liste (si elle n'est pas vide) en déclarant que le nouveau sommet de la pile est le prec de l'ancien sommet.
2- Détruire par free() l'élément qu'on a détaché.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Départ :                      prec            prec        prec
         Pile >----> Element1 >----> Element2 >---->.....>----> NULL

Etape 1 :                     prec
                     Element1 >----
                                   \           prec        prec
         Pile >--------------------> Element2 >---->.....>----> NULL

Etape 2 :
                               prec        prec
         Pile >----> Element2 >---->.....>----> NULL

[bounadalvidal]

Il ne faut pas procéder de cette façon pour enlever le sommet de la pile :

1- Détacher le sommet de la pile de la liste (si elle n'est pas vide) en déclarant que le nouveau sommet de la pile est le prec de l'ancien sommet.
2- Détruire par free() l'élément qu'on a détaché.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Départ :                      prec            prec        prec
         Pile >----> Element1 >----> Element2 >---->.....>----> NULL

Etape 1 :                     prec
                     Element1 >----
                                   \           prec        prec
         Pile >--------------------> Element2 >---->.....>----> NULL

Etape 2 :
                               prec        prec
         Pile >----> Element2 >---->.....>----> NULL

J'apprécie mais ce que je veux c'est effacer le dernier élément dans votre représentation : celui juste avant NULL !! Par schématisation c'est facile, mais en algo ?

[diogene]

Si tu parles de 'pile', tu impliques un mode d'utilisation de tes données : On n'accède qu'au dernier élément placé dans la pile, soit pour le consulter, soit pour l'enlever, soit pour faire les deux ensembles. Il y a peu d'intérêt à pouvoir détruire l'élément le plus ancien dans la pile.

Si tu veux accéder à l'élément en queue de pile, cela va t'obliger à parcourir la liste pour trouver l'avant dernier si il existe. p pointe sur l'avant dernier lorsque p->prec->prec == NULL ce qui impose p non NULL et p->prec non NULL
Il y a donc trois cas à considérer pour établir l'algorithme
- p est NULL au départ : la pile est vide et il n'y a rien à faire
- au départ, p est non NULL mais p->prec est NULL : la pile ne contient qu'un élément. Il faut détruire l'élément p de la pile et mettre le pointeur de pile à NULL.
- sinon, la pile contient au moins deux éléments et il faut rechercher p tel que p->prec->prec == NULL en parcourant les éléments successifs de la liste, détruire l'élément pointé par p->prec et mettre p->prec à NULL.

[sloshy]

Bonsoir,
Juste pour information complémentaire

Une pile est une structure de données de type LIFO (Last In First Out - en français dernier entré premier sorti)
L'analogie la plus simple est une pile d’assiette, une fois les assiette lavées, tu les ranges en les empilant (push) les unes sur les autres, l'assiette la plus haute de ta pile est la dernière que tu as rangé. C'est aussi la première que tu va utiliser (pop) lorsque tu voudra manger, il ne te viendrait pas a l'esprit d'en prendre une autre.
Pour plus d'info: Les piles en C

[bounadalvidal]

Si tu parles de 'pile', tu impliques un mode d'utilisation de tes données : On n'accède qu'au dernier élément placé dans la pile, soit pour le consulter, soit pour l'enlever, soit pour faire les deux ensembles. Il y a peu d'intérêt à pouvoir détruire l'élément le plus ancien dans la pile.

Si tu veux accéder à l'élément en queue de pile, cela va t'obliger à parcourir la liste pour trouver l'avant dernier si il existe. p pointe sur l'avant dernier lorsque p->prec->prec == NULL ce qui impose p non NULL et p->prec non NULL
Il y a donc trois cas à considérer pour établir l'algorithme
- p est NULL au départ : la pile est vide et il n'y a rien à faire
- au départ, p est non NULL mais p->prec est NULL : la pile ne contient qu'un élément. Il faut détruire l'élément p de la pile et mettre le pointeur de pile à NULL.
- sinon, la pile contient au moins deux éléments et il faut rechercher p tel que p->prec->prec == NULL en parcourant les éléments successifs de la liste, détruire l'élément pointé par p->prec et mettre p->prec à NULL.

Ok, j'essaye de mettre en code (je ne m'intéresse pas au cas où p est NULL ou p->prec est NULL, je ne traiterai que le cas d'une liste "bien remplie") :

Code :

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

1
2
3
4
5
6
7
8
 
void efface_first(pile **p)
{
        while(*p)
            {
                if(((*p)->prec)->prec==NULL) p->prec=NULL;
            }
}

Je compile et ça ne marche pas !

[bounadalvidal]

Je comprends que cet exercice auquel je m'adonne ne relève pas de l'esprit des piles, qui se veulent une structure de données favorisant "le dernier arrivé", mais c'est plus pour savoir résoudre des problèmes qu'autre chose...