Modèle de classe - Pile - Fonction retirer

Version imprimable

2 pièce(s) jointe(s)

Bonjour à tous,

Comme le titre l'indique je travaille sur le template d'une classe de Pile, en logique FIFO (first in first out) et j'ai un problème dans ma fonction Retirer().

La fonction qui me permet d'empiler a bien été vérifié.

Voici ma fonction Retirer() :

Pièce jointe 194626

Lorsque que je l'a teste sur le main grâce à ce code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 File <int> F1(5); cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << "Valeurs : " << F1.Empiler(10) << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << "Valeurs : " << F1.Empiler(20) << endl; cout << "Valeurs : " << F1.Empiler(30) << endl; cout << "Valeurs : " << F1.Empiler(45) << endl; cout << "Valeurs : " << F1.Empiler(50) << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << F1.Retirer() << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << F1.Retirer() << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << F1.Retirer() << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << F1.Retirer() << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << F1.Retirer() << endl; cout << "Taille utilisee : " << F1.Tailleutilisee() << endl; cout << F1.Retirer() << endl << endl << endl;
Voici le résultat que j'obtiens :

Pièce jointe 194625

J'ai essayé de comprendre mon erreur qui semble être dans la façon de réécrire la pile après avoir enregistré la valeur que l'on veut sortir mais je n'ai pas trouvé.

Merci par avance.

07/12/2015, 20h24
Médinoc

Si c'est FIFO, ce n'est pas une Pile, mais une File.
Alors, est-ce une Pile (LIFO) ou une File (FIFO)?
07/12/2015, 21h15
Noxit

Une file !
07/12/2015, 22h31
dalfab

Bonjour,

la boucle effectue une étape de trop.
for ( i = 0 ; i < TailleUtilisee()-1 ; ++ i )

Lors de la première itération, on écrit dans l'indice[5] qui est hors table, ce qui écrase une donnée en mémoire...
07/12/2015, 22h39
JolyLoic

Tu ne veux vraiment pas nous faciliter la tâche :
- Tu nous caches la définition de ta classe, et le rôle de tes différentes variables...
- Tu nous empêches de faire des copier/coller de code en mettant un screenshot plutôt que le code lui même (balise [code] pour qu'il soit bien mis en forme, bouton #)

Sinon, en plus de la réponse de dalfab (il m'a grillé), je dirais :
- J'ai des gros doutes sur la gestion de la mémoire dans ta classe, mais on n'en voit pas assez pour être plus précis. C'est peut-être bon si tu as une limite arbitraire sur le nombre d'éléments possibles dans ta queue.
- En terme de performances, ta queue est catastrophique, puisqu'on retire un élément en O(N). Participer ainsi au réchauffement climatique en plein COP21, c'est de la provocation ;)
- C'est quoi ce vide() == 1 ? Vide retourne quoi ? Un booléen j'espère...
07/12/2015, 22h43
Noxit

Bonjour, par rapport à cette réponse, ayant utilisé la fonction empiler pour ajouter 5 valeurs, la variable Tailleutilisee est donc égale à 5, or ma condition de boucle est i strictement inférieure à Tailleutilisee donc 4 boucles dans mon cas. Normalement, c'est bien le nombre de boucle nécessaire à remplacer les données du tableau.

De plus ayant essayé avec Tailleutilisee()-1, rien n'a changé, lorsque j'utilise ma fonction retirer une première fois il me retourne bien la valeur du premier objet empiler mais lorsque je l'utilise une deuxième fois, il me retourne une valeur aléatoire, ensuite pour les troisième et quatrième fois il retire bien les valeurs du deuxième et troisième objet.

[QUOTE=JolyLoic;8465407]Tu ne veux vraiment pas nous faciliter la tâche :
- Tu nous caches la définition de ta classe, et le rôle de tes différentes variables...
- Tu nous empêches de faire des copier/coller de code en mettant un screenshot plutôt que le code lui même (balise [code] pour qu'il soit bien mis en forme, bouton #)

Désolé je suis inscrit que depuis peu sur le site et ayant mis le code une première fois tout était collé sans les espaces donc j'ai opté pour des screenshots.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 template <class T> class File { public: File(int); //Constructeur définit à la suite du .h ~File(); int Tailleutilisee(); T Empiler(T); T Retirer(); bool pleine(); bool vide(); private: int taille; //Nombres d'éléments maximal de la Pile T* adresse; //Zone mémoire de la Pile T* ptrSommet; };
Voici la définition de ma fonction File

07/12/2015, 22h48
Noxit

- En terme de performances, ta queue est catastrophique, puisqu'on retire un élément en O(N). Participer ainsi au réchauffement climatique en plein COP21, c'est de la provocation ;)

Je n'ai pas du tout compris ce point sinon ^^

En tout cas, merci pour vos réponses dans tous les cas.

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
template <class T> File<T>::File(int n)
{
    taille = n;
    adresse = new T[taille];
    ptrSommet = NULL;
}
 
template <class T> File<T>::~File()
{
    delete [] adresse;
}
 
template <class T>int File<T>::Tailleutilisee()
{
    if (ptrSommet==NULL)
        return 0;
    else
        return (ptrSommet-adresse);
}
 
 
 
template <class T>T File<T>::Empiler(T Element)
{
    bool a;
    a = pleine();
    if (a==1)
        cout << "La pile est deja pleine" << endl;
    else
    {
        if(ptrSommet==NULL)
        {
            adresse[0]=Element;
            ptrSommet = adresse+1;
            //cout << "Adresse [0] " << adresse[0] << endl;
 
        }
        else
        {
            ptrSommet++;
            *ptrSommet = Element;
            //cout << "Valeur ptrSommet :  " << *ptrSommet << endl;
        }
    return Element;
    }
}
 
template <class T>T File<T>::Retirer()
{
    if (vide()==1)
        cout << "La pile est deja vide" << endl;
    else
    {
        T b;
        if(Tailleutilisee()==1)
        {
            b = adresse[0];
            ptrSommet = NULL;
        }
        else
        {
            b = adresse[0];
            int i;
            for (i=0;i<(Tailleutilisee()-1);i++)
            {
                //cout << adresse[i+1] << endl;
                adresse[i] = adresse[i+1];
                //cout << adresse[i] << endl;
            }
            ptrSommet--;
        }
        return b;
    }
}
 
template <class T>bool File<T>:: pleine()
{
    if (Tailleutilisee()==taille)
        return true;
    else
        return false;
}
 
template <class T>bool File<T>:: vide()
{
    if (Tailleutilisee()==0)
        return true;
    else
        return false;
}

Et voici le reste des fonctions utilisées.

08/12/2015, 00h10
dalfab

Citation:

La fonction qui me permet d'empiler a bien été vérifié.

Revérifie quand même ce qui se passe à la seconde insertion ;)

Salut,

Déjà, de manière générale, qu'il s'agisse d'une pile ou d'une file, le principe reste le même : l'idée est d'optimiser l'ajout, la suppression et l'accès au dernier (respectivement au premier) élément rajouté et ce, sans avoir à indiquer le nombre d'éléments que l'on envisage de placer dans la pile (respectivement dans la file).

Dés lors, ce n'est vraiment pas un bonne idée que de commencer à utiliser en interne un T* initialisé à l'aide d'un new[XXX], car cela nous fait partir sur l'utilisation d'un tableau et que c'est justement pour pallier les faiblesses des tableaux lors de l'ajout et de la suppression que les concepts de pile et de file sont apparus.

L'idée est donc de faire en sorte que chaque élément de la pile soit mis en relation avec l'élément qui a été rajouté juste avant (si tant est qu'il existe) et, pour la file, que chaque élément soit mis en relation avec celui qui a été rajouté juste après. et de garder une référence sur le dernier (respectivement le premier) élément ajouté (et non encore retiré) de manière à pouvoir parcourir la pile ou la file, en sachant que l'on n'en a absolument rien à faire du nombre d'éléments que la pile (respectivement que la file) contient : tout ce qui nous intéresse étant de savoir si elle est vide ou non.

Dés lors, l'idéal est de modéliser la notion d'élément sous une forme sans doute proche de
Code:

1 2 3 4 5 6 7 8 template <typename T> struct Element{ T value; Element * next; /* voire std::unique_ptr<Element> next; */ };
et de maintenir les élément sous une forme proche de
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 template <typename T> class Pile{ public: Pile():head_{nullptr}{ } bool empty() const{ return head_!=nullptr; } void push(T value){ Element<T> * toadd = new Element<T>; toadd->value = value; toadd->next = head_; head_ = toadd; } T top() const{ assert(head!= nullptr); return head_->value; } void pop(){ if(head_){ auto * temp =head_->next; delete head_; head= temp; } } void clear(){ while(head_){ auto * temp =head_->next; delete head_; head= temp; } } private: Element<T> head_; };
Pour la file, nous aurons intérêt à garder également une référence sur le dernier élément ajouté (de manière à garantir l'ajout en O(1) ) sous une forme proche de
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 template <typename T> class file{ File():head_{nullptr},tail_{nullptr}{ } bool empty() const{ return head_==nullptr; } T front() const{ assert(head_!= nullptr); return head_->value; } void push(T toadd){ Element<T> * temp = new Element<T>; temp->value = toadd; if(tail_) tail_->next = temp; tail_=temp; if(!head_) head_=temp; } void pop(){ if(head_){ auto * temp = head_->next; delete head_; head_=next; } if(!head_) tail_=nullptr; } private: Element<T> * head_; Element<T> * tail_; };
Et tout ira pour le mieux... Facile, non :question:

NOTA: je suis resté très proche du concept tel qu'il serait défini en C... En C++, nous pourrions sans doute profiter de la classe std::unique_ptr pour faire le lien et nous aurions surement défini un constructeur adéquat pour la structure Element, mais bon... cela serait quand meme revenu à peu près au même ;)

08/12/2015, 10h29
Médinoc

Franchement, je doute fort de la pertinence de unique_ptr<> pour les liens d'une liste chaînée, car les chaînons ne se possèdent pas entre eux: Chacun peut être ajouté ou supprimé à loisir indépendamment des autres, et c'est la liste qui a la propriété de tous.
08/12/2015, 11h23
koala01

Citation:

Envoyé par Médinoc

Franchement, je doute fort de la pertinence de unique_ptr<> pour les liens d'une liste chaînée, car les chaînons ne se possèdent pas entre eux: Chacun peut être ajouté ou supprimé à loisir indépendamment des autres, et c'est la liste qui a la propriété de tous.

Ouaip, tu n'as pas tord sur ce coup là...

D'ailleurs, si l'on y regarde d'un peu plus près au niveau de ce qui se fait dans la SL, on remarque en effet que les pointeurs intelligents ne sont absolument pas utilisés pour les différentes collections... Ce n'est surement pas sans raison ;)
09/12/2015, 02h52
Luc Hermitte

Mes classes chainon ont toujours un constructeur. Le "on peut faire des trucs qui ressemblent en C" ne justifient pour moi l'approche d'initialisation multi-passes (d'abord un attribut, puis un deuxième, puis ...).
Une autre raison que j'ai de critiquer les setters, c'est le risque d'oubli de positionner tout ce qui doit l'être (c'est d'ailleurs l'angle d'attaque le plus efficace à l'encontre des setters : les collègues ont toujours des expériences où cette initialisation qui ne garantie pas les invariants vient déstabiliser le code). Alors faire la même chose en attaquant directement les variables ... ben, justement, c'est la même chose et donc pas mieux.

unique_ptr, tant que l'on ne gère qu'une ressource, il n'est pas indispensable. Et ne pas l'utiliser pour des collections ne me gêne pas plus que ça. Même si au final on va dupliquer son code. En l'utilisant, la move-construction devient immédiate.

Après, pile et file sont des contrats (FILO/LIFO et FIFO), des candidats idéals pour des Types Abstraits de Données. Pas des promesses d'implémentation. D'ailleurs std::queue et std::stack ne sont pas des conteneurs, mais des adaptateurs de conteneurs. Certes une file sur un vecteur sera un chouilla moins efficace, mais c'est possible d'en avoir. Sur des files de taille modeste (qui auraient pu, voire dû, être des buffers circulaires auto-redimensionnés en somme), je ne serai pas surpris que l'on ait de meilleures performances avec une structure sous-jacente contigüe comme le vecteur tant que l'on n'a pas de synchro à faire.

Bref je ne suis pas d'accord pour dire que ces concepts sont apparus pour combler des manques des tableaux. Il s'agit juste de besoins précis en termes de services à rendre, et on en arrive à proposer des abstractions plus riches que l'abstraction tableau -- des années après, on aurait dit "design pattern" AMA.
À noter que l'implémentation de pile la plus utilisée encapsule un tableau. Et que la file standard la plus efficace en C++ est au dessus d'un semi-tableau (dequeue: liste de tableaux). Une implémentation par tableau n'est pas si aberrante dans une première approximation, on connait juste beaucoup mieux pour la file, et ce n'est pas nécessairement la liste.

Citation:
Envoyé par Noxit
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 template <class T>T File<T>::Empiler(T Element) { bool a; a = pleine(); if (a==1) cout << "La pile est deja pleine" << endl; else { if(ptrSommet==NULL) { adresse[0]=Element; ptrSommet = adresse+1; //cout << "Adresse [0] " << adresse[0] << endl; } else { ptrSommet++; *ptrSommet = Element; //cout << "Valeur ptrSommet : " << *ptrSommet << endl; } return Element; } }
Ta fonction d'empilement a été vérifié mais pas assez bien (ce dont je me doutais à la vue de ton erreur). C'est ce qu'on appelle une erreur aux limites. Ta fonction d'insertion ne se comporte pas de la même façon quand tu insères un objet dans une file vide ou dans une file qui contient quelque chose. Il faut donc vérifier ce qui se passe quand le comportement change, c'est à dire quand tu insères un objet dans une file pleine juste après l'insertion dans une file vide (autrement dit, quand tu insère le deuxième élément). Et là, tu as un problème.

Quand ta file est vide, tu places ton élément a l'emplacement 0 de ta file et tu places le pointeur de fin de file sur l’élément suivant de la ta file.
Quand ta file n'est pas vide, tu déplace le pointeur de fin de file sur l’élément suivant de la ta file et tu positionne l’élément a cet emplacement.

Ton pointeur a donc deux positions possibles :
- Juste après l'insertion du premier élément de la pile, il pointe après l'élément inséré.
- Dans tout les autres cas, il pointe sur l'élément inséré.
Tes index utilisés sont donc : 0, 2, 3, 4, 5, etc. Le 1 est sauté.

La correction est très facile, je te laisse la trouver.

Je serai curieux de savoir comment tu as testé cette fonction.

Bonne correction.

09/12/2015, 15h44
Noxit

[QUOTE=koala01;8465482]

Bonjour, avant tout merci pour le temps et l'aide que vous m'avez fourni.

Etant un exercice de programmation de TD, je ne peux modifier la structure de l'Element que je vais empiler.
09/12/2015, 15h53
Noxit

[QUOTE=fenkys;8467206]

Je vous remercie, l'erreur était bien là.

Il s'agit seulement du +1.

Dans la logique que j'avais adopté, j'ai confondu deux choses, ptrSommet = NULL et ptrSommet-adresse = 0, qui sont deux cas bien différents mais que j'avais soumis équivalent dans ma façon de raisonner.

La "vérification" n'en était pas vraiment une, car je vérifier la valeur que j'ajoutais à la File grâce à un return *adresse qui me retournait bien la valeur que j'avais ajouté mais comme l'erreur se situait dans le placement du pointeur ptrSommet, j'avais effectué une fausse vérification.

Merci beaucoup pour vos contributions.