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
| #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
}
vector<double> mySortedStack::rajouZero (vector<double>& oneTab, int nbrZero)
{
vector<double> newTab(nbrZero, 0);
for (unsigned int ind=0; ind<oneTab.size(); ind++)
{
newTab.push_back(oneTab[ind]);
}
return newTab;
}
vector<double> mySortedStack::addition (vector<double>& tab1, vector<double>& tab2)
{
vector<double> newTab;
for (unsigned int ind=0; ind<tab1.size(); ind++)
{
newTab.push_back(tab1[ind]+tab2[ind]);
}
return newTab;
}
void mySortedStack::empty ()
{
while (!(this->isEmpty()))
{
this->pop(); // vide toute la pile avec des pop (s) successifs
}
}
mySortedStack mySortedStack::add (mySortedStack const& unePile)
{
vector<double> tab1, tab2;
mySortedStack* ptrPivot= next;
while (ptrPivot != NULL)
{
tab1.push_back(ptrPivot->info);
ptrPivot = ptrPivot->next;
}
ptrPivot = unePile.next;
while (ptrPivot != NULL)
{
tab2.push_back(ptrPivot->info);
ptrPivot = ptrPivot->next;
}
if (tab1.size() < tab2.size()){tab1=rajouZero(tab1,tab2.size()-tab1.size());}
else if (tab2.size() < tab1.size()){tab2=rajouZero(tab2,tab1.size()-tab2.size());}
tab1 = addition (tab1,tab2);
this->empty();
for (unsigned int ind=0; ind<tab1.size(); ind++)
{
this->push(tab1[ind]);
}
return *this;
}
void mySortedStack::fusion (mySortedStack const& unePile)
{
mySortedStack* ptrPivot = unePile.next; // servira à parcourir la pile reçue en paramètre
while (ptrPivot != NULL)
{
this->push(ptrPivot->info); // rajout dans ma pile principale de chaque élément de ...
ptrPivot = ptrPivot->next; //... la pile donnée en paramètre
}
}
void mySortedStack::swap (mySortedStack& unePile, int debut, int fin)
{
vector<double> tab1, tab2;
mySortedStack* ptrPivot= next;
while (ptrPivot != NULL)
{
tab1.push_back(ptrPivot->info);
ptrPivot = ptrPivot->next;
}
ptrPivot = unePile.next;
while (ptrPivot != NULL)
{
tab2.push_back(ptrPivot->info);
ptrPivot = ptrPivot->next;
}
tab1 = retient (tab2, debut, fin);
tab2 = retient (tab1, debut, fin);
ptrPivot= next;
while (ptrPivot != NULL)
{
if (!(interne(tab2,ptrPivot->info))){tab1.push_back(ptrPivot->info);}
ptrPivot = ptrPivot->next;
}
ptrPivot = unePile.next;
while (ptrPivot != NULL)
{
if (!(interne(tab1,ptrPivot->info))){tab2.push_back(ptrPivot->info);}
ptrPivot = ptrPivot->next;
}
this->empty();
unePile.empty();
for (unsigned int ind=0; ind<tab1.size(); ind++)
{
this->push(tab1[ind]);
}
for (unsigned int ind=0; ind<tab2.size(); ind++)
{
unePile.push(tab2[ind]);
}
}
bool mySortedStack::interne (vector<double>& oneTab, double nbr) // verifie si un élément est dans un tableau
{
bool verifie = false;
for (unsigned int ind=0; ind<oneTab.size(); ind++)
{
if (nbr == oneTab[ind]){verifie = true;}
}
return verifie;
}
vector<double> mySortedStack::retient (vector<double>& oneTab, int deb, int fin)
{
vector<double> newTab;
for (int ind=deb; ind<=fin; ind++)
{
newTab.push_back(oneTab[ind]);
}
return newTab;
}
bool mySortedStack::estEgal (mySortedStack const& maPile) const // vérifie si deux piles équivalent
{
bool vaut = true;
/*
mySortedStack* ptrPivot1= maPile.next;
mySortedStack* ptrPivot2= this->next;
while (ptrPivot1 != NULL && ptrPivot2 != NULL)
{
if (ptrPivot1->info != ptrPivot2->info){vaut = false ;}
ptrPivot1 = ptrPivot1->next;
ptrPivot2 = ptrPivot2->next;
}
*/
return vaut;
}
bool operator==(mySortedStack const& pile1, mySortedStack const& pile2) // surcharge ==
{
return pile1.estEgal(pile2);
} |
