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
|
#include "ajoute.h"
#include <stddef.h>
using namespace std;
// mss == mySortedStack
//toute pile, à la base, commence par un mss d'une valeur quelconque et pointant vers 'rien'
mySortedStack::mySortedStack() // constructeur sans paramètre
{
info = 1.1;
next = NULL;
}
// on crée d'abord une pile (un mss) et ensuite on rajoute l'élément passé en paramètre
//en rajoutant l'élément, un mss est créé et est lié au mss primitif
mySortedStack::mySortedStack(double elem) // constructeur avec 1 paramètre réel
{
info = 1.1;
next = NULL;
this->push(elem);
}
mySortedStack::mySortedStack(const mySortedStack &mssAcopier) // constructeur de copie
{
mySortedStack* ptrPivot = mssAcopier.next; //parcours du mss à copier en parcourant tous les pointeurs,...
//...sous-pointeur, sous-sous-pointeur, etc.
while (ptrPivot != NULL)
{
this->push(ptrPivot->info); //copie, rajout de l'info dans la pile vide
ptrPivot = ptrPivot->next; // passe au pointeur suivant (sous-pointeur)
}
}
const mySortedStack& mySortedStack::operator=(const mySortedStack &mssAcopier)
{
if (this != &mssAcopier)
{
this->empty(); // vide d'abord la pile
mySortedStack* ptrPivot = mssAcopier.next;
// puis, comme dans la fonction précédente, copie d'éléments un à un pendant le parcours
while (ptrPivot != NULL)
{
this->push(ptrPivot->info);
ptrPivot = ptrPivot->next;
}
}
return *this;
}
mySortedStack::mySortedStack(double tableau[]) //info(1.1),next(NULL)
// création du mss primitif (création de la pile (vide) en fait)
{
int taille = tableau[0]; // la taille est connue
for (int ind=1; ind<=taille; ind++) // rajout de tous les éléments dans mon stack...
{
this->push(tableau[ind]); //...tous sauf le premier
}
}
mySortedStack::mySortedStack(mySortedStack* ptrPile): info(1.1),next(NULL)
{
mySortedStack* ptrPivot= ptrPile->next;
while (ptrPivot != NULL)
{
this->push(ptrPivot->info);
ptrPivot = ptrPivot->next;
}
}
mySortedStack::~mySortedStack()
{
this->empty();
}
void mySortedStack::chaine (mySortedStack* aAjouter)
// rajoute un sous-mss dans ma pile (qui est une chaîne de mss liés entre eux) en la liant ...
// ...à l'élément qu'il doit précéder, celui-ci (une mss) étant connu d'avance
{
aAjouter->next = next; //le mss à ajouter pointera vers l'élément (mss) qui succédait ...
//...à l'élément après lequel on doit placer notre mss (à ajouter)
next = aAjouter; // on retient le mss à ajouter dans la pile en passant son addresse à ...
//...l'élément qui doit le précéder
aAjouter = NULL; // ne sert à rien
}
void mySortedStack::push (double element)
{
bool rajout(false); // change d'état s'il y a bien eu rajout
mySortedStack* ptrPivot = next; // permet de parcourir plusieurs pointeurs
// création de la sous-pile à rajouter
mySortedStack* sousPile = new mySortedStack;
sousPile->info = element; // enregistrement du nombre réel
if (this->size() == 0) // isEmpty
{
this->chaine(sousPile); //si pile vide, on lie directement le sous-mss au mss primitif
rajout = true;
}
else if (this->size() == 1) // au moins un élément...
{
if (sousPile->info > next->info) //si le (info du) sous-mss à ajouté est > au premier sous-mss,...
{
this->chaine(sousPile); //...dans ce cas il devient le premier sous-mss de la pile
rajout = true;
}
else
{
next->chaine(sousPile); // rajout après le premier élément
rajout = true;
}
}
else // pour plus de 2 éléments dans une pile, parcours des mss (2 à 2) par des pointeurs
{
while (!rajout && ptrPivot != NULL && ptrPivot->next != NULL)
// si pas de rajout, et si les deux pointeurs suivants ne pointent vers un NULL
{
if (sousPile->info > ptrPivot->next->info && sousPile->info <= ptrPivot->info)
{
ptrPivot->chaine(sousPile); // ajout du mss entre les 2 mss si son info est aussi compris...
rajout = true; // ...entre les 2 infos
}
else {ptrPivot = ptrPivot->next;} // on passe au(x) pointeur(s) suivant(s)
}
}
if (!rajout) // toujours pas de rajout (surtout si plus de 2 éléments dans la pile) dans ce cas ...
{
if (next->info <= sousPile->info){this->chaine(sousPile);} // rajout au début de la pile
else {ptrPivot->chaine(sousPile);} // ou rajout à la fin de la pile
}
}
void mySortedStack::supprime () // supprime l'élément (mss) le suivant
{
mySortedStack* aSupprimer = next; // garde l'adresse du mss à supprimer
if (aSupprimer == NULL){return;} // si jamais
next = aSupprimer->next; // oublie du mss de notre chaine de mss (de la pile)
delete aSupprimer; // suppression
}
mySortedStack mySortedStack::pop ()
{
if (!(this->isEmpty ()))
{
mySortedStack* ptrPivot = this; // recherche de l'avant-dernier mss
for (int ind=1; ind<this->size(); ind++)
{
ptrPivot = ptrPivot->next; // on arrive à l'avant-dernier mss
}
ptrPivot->supprime(); // on supprime le mss qui le succède
}
return *this;
}
double mySortedStack::top ()
{
if (!(this->isEmpty())) // si la pile n'est pas vide
{
mySortedStack* ptrPivot = next; // permet de parcourir la pile
for (int ind=1; ind<this->size(); ind++) // grâce à la taille de ma pile,...
{
ptrPivot = ptrPivot->next; //...je peux accéder au tout dernier sous-mss
}
return ptrPivot->info; //...je retourne l'info du dernier sous-mss
}
else {return 999.23;} // pile vide: renvoie une valeur quelconque (toujours celle-là)
}
bool mySortedStack::isEmpty ()const
{
return next==NULL; // pile vide i.e le premier pointeur (mss primitif) ne pointe vers rien
}
int mySortedStack::size ()
{
int nbrElem=0;
mySortedStack* ptrPivot = next; // sert au parcours de pile
while (ptrPivot != NULL)
{
nbrElem++;
ptrPivot = ptrPivot->next;
}
return nbrElem; // taille de ma pile
}
void mySortedStack::empty ()
{
while (!(this->isEmpty()))
{
this->pop(); // vide toute la pile avec des pop (s) successifs
}
}
|
