Bonjour,

J'aimerais avoir vos avis sur ce code que j'ai écrit sur une classe de liste chaînée. Je tiens à préciser que les prototypes étaient déjà définies.

J'ai tout regroupé ici : http://wall.deblan.fr/x47/c/1/

Merci !

Peut etre que la question est stupide, mais pourquoi ne pas utiliser std::forward_list [1] ?

Aussi, il me semble que ta liste servent a stocker des entiers. Pourquoi ne pas utiliser les template pour pouvoir stocker n'importe quoi?

Les fonctions de la liste ne sont pas documentee. Ce qui rends l'utilisation et la comprehension de la classe difficile.

De ce que j'en comprends, cette liste est inutile. Je peux avoir l'element du debut, et l'element de la fin. Mais je ne peux pas traverser la liste. En tout cas, pas en O(n). Du fait, cette interface semble utile uniquement pour implementer une file ou un pile.

Best,

Erik

[1] http://www.cplusplus.com/om/reference/stl/forward_list/

Salut

Tout d'abord merci de ta réponse.

Je n'utilise pas forward_list car je ne connaissais pas cette fonction et le but de l'exercice était d'implémenter une liste chaînée.

La notion de template n'a pas encore été abordée.

Alors en effet, j'avoue que ce n'est pas commenté mais tu peux parcourir la liste dans ine boucle for et appeler la fonction consult_position qui te donne la valeur de la case choisie, mais en effet ce n'est pas disponible en O(n).

Je prends note de remarques et reproposerais une solution d'ici quelques semaines je pense (quand j'aurais vu les templates et les exceptions).

Merci !

vivecod, l'interet principal d'une liste chaine est de pouvoir avancer dans la liste en O(1) et de pouvoir ajouter ou retirer un element a n'importe quel position en O(1) pourvu que l'on ait un iterateur (pointeur sur le maillon) sur cette position.

NB: Les exceptions ne servent pas a grand chose ici. globalement les exceptions ont un cout en terme de temps d'execution. Je ne pense pas que les utiliser dans une telle structure de donnee soit une bonne idee.

Peut être parce que j'ai mal compris ce que tu as écris godrik, mais le parcours d'une liste chainée c'est pas O(n) plutôt ?

Ce que je voulais dire c'est que passer d'un element au suivant c'est O(1). Dans le code de OP, les element ne sont accessible que par leur index. Du fait, si tu viens de lire l'element 4 et que tu veux maintenant lire l'element 5, il faut relire les 4 premiers elements. Ce qui fait que parcourir la liste dans l'implementation de OP coute O(n^2)

Ah oui effectivement, assez couteux d'utiliser la fonction consult_position pour parcourir la liste. Mais visiblement c'est un exercice et tu es obligé d'utiliser ces prototypes donc pas trop le choix.

Tu peux rajouter de quoi parcourir la liste en O(N) en faisant un petit itérateur par exemple.

Ce qui peut être amusant c'est de faire des fonctions qui reverse, qui sort et qui shuffle ta liste.

En effet,les prototypes étaient imposée.

Je vais faire tout ça et re-proposer une version (peut-être une qui sera avec des prototypes différents)