Variations autour des piles et des listes
Juste une petite remarque en passant, ça me "choque" toujours de voir une liste (ou pile, queue, etc.) connue par son premier noeud (et par conséquence d'avoir une classe node en guise de pile).
De mon point de vue, une liste contient des éléments (et à la limite que ce soit des noeuds chaînés par un pointeur, un tableau ou que sais-je, c'est un détail d'implémentation qui devrait rester interne) et fournie des APIs pour manipuler la liste. Mais une liste n'est pas et ne peut pas se résumer à un noeud.
Variations autour des piles et des listes
Citation:
Envoyé par
TropMDR
Pour une pile je suis d'accord, ça devrait être sagement encapsulé. En revanche, pour une liste, il peut y avoir un intérêt à vraiment voir ça comme "une liste chaînée" : le partage et la persistance.
Comme ça, quand tu as la liste [2;3;4], rien ne t'empêche de rajouter 1 en tête, et d'avoir *à la fois* la liste [1;2;3;4] et la liste [2;3;4]. Ce qui risque d'être nettement plus pénible si c'est encapsulé.
Absolument pas, du moins dans le contexte où nous sommes ici, qui est une programmation procédurale pure (et, à bien y réfléchir, cela ne poserait pas de problème particulier si nous étions dans un contexte OO :D)...
Si, d'une manière générale, tu souhaite garder un pointeur sur un élément particulier de la liste, il n'y a strictement rien qui t'empêche de maintenir un tel pointeur, sachant qu'il sera alors connu (et utilisé) sous la forme d'un noeud et non sous la forme d'une liste.
Au contraire, si tel est effectivement ton souhait, le fait de séparer clairement la structure liste de la structure noeud t'évitera bien des déboires:
Imagine si tu n'encapsule pas ton noeud dans une structure particulière, et que tu veut, effectivement garder un pointeur sur le deuxième élément:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int main
{
Node * liste=NULL;
push(&liste,4);
push(&liste,3);
push(&liste,2);
/*nous avons nos trois premiers éléments, et tout va bien */
Node *l2=liste /* on garde cette première version de la liste grace à l2*/
push(&liste,1);
/* à priori, tout va bien, tant que nous continuerons à invoquer push
* en passant &liste, mais...
*/
push(&l2,-10); // CRACK: on perd tous les éléments qui précèdent 2
// et on a une fuite mémoire
return 0;
} |
Par contre, si tu sépare correctement les deux concepts que sont liste et noeud, sous une forme proche de
Code:
1
2
3
4
5
6
7
8
9
10
11
| struct Noeud
{
int val;
Noeud * next;
};
struct Liste
{
Noeud * first;
/* j'apprécie particulièrement d'avoir */
Noeud * last;
}; |
le prototype de tes fonctions push et pull devient
Code:
1
2
3
4
5
| void push(Liste & l, int val);
void pull(Liste & l, int val);
/* voir, si tu veux travailler avec des pointeurs */
void push(List * l, int val);
void pull(List * l, int val); |
Et, du coup, tu va travailler 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
| int main()
{
Liste liste;
/* il serait pas mal d'avoir un système d'initialisation complet, mais
* on peut se contenter de
*/
liste.first = NULL;
/* et au besoin */
liste.last = NULL;
/* créons notre liste de départ */
push(liste, 4);
push(liste, 3);
push(liste, 2);
/* et gardons un pointeur sur l'élément "2" */
Node * n = liste.first;
/* rajoutons des éléments avant "2" */
push(liste, 1);
push(liste, 0);
/* la ligne suivante sera refusée à la compilation, car n n'est pas
* une liste
*/
push(n, -10);
} |
Tu n'a au final que des avantages pour un cout, finalement, des plus réduits (on a quoi :question: deux pointeurs présents en mémoire en plus, ou à peine plus ;))
