cherche éclaircissement sur les Listes Chainées !

Bonjour,
étudiant en deuxième année d'informatique à la fac (Tours), nous avons un cours qui s'intitule Algorithmique avancée. Dans celui ci, nous sommes actuellement en train de voir les listes Chainées (qui ne sont pas de bases dans Python si je ne m'abuse, il n'y a que des tableaux dynamiques, mais encore une fois, peut être que je me trompe !)

J'ai un problème dans la syntaxe que l'on utilise pour définir une liste chainée, je m'explique.
Nous partons d'une liste, ou tableau dynamique présent de base sur python , par exemple : p=[1,2,3,4], et au travers d'une méthode nous récupérons une liste chainée, à savoir une liste dont chaque valeur est liée à la suivante grâce à l'adresse mémoire (je ré-précise ceci simplement pour être sur que l'on parle bien de la même chose !)

Seulement j'ai du mal à comprendre dans le code concretement comment cela fonctionne et comme on arrive à "chainer" une valeur à l'adresse mémoire de la valeur suivante, voici le code que j'ai :

Ma classe Liste :

Code:

---

1 2 3 4 5 6 7

class Liste(): def __init__(self, head, tail=None): '''         Create a new linked list         ''' self.valeur = head self.suivant=tail

---

Ma méthode prenant en paramètre un tableau dynamique et donnant en sortie une liste chainée :

Code:

---

1 2 3 4 5 6 7 8 9 10

import Liste   def init(L): res=Liste(L[0]) p=res for i in range (1, len(L)): tmp=Liste(L[i]) p.suivant=tmp p=p.suivant return res

---

De ce que j'ai comprit pour l'instant, l'instruction "res=Liste(L[0])" fixe res à l'adresse de départ, afin de ne pas perdre le contenu de la liste.
"p=res" sert à initialiser p qui sera celui qui se déplace (très très mal dit désolé ...)
La boucle for sert à avancer dans notre tableau dynamique de départ, mais je ne comprend pas les instructions à l'intérieur de cette boucle. Est ce que quelqu'un pourrait m'éclaircir ce point ci ?

Merci d'avance ! J'espère ne pas avoir oublier d'information !

Je ne sais pas pourquoi on te présente ça comme ça, mais ton enseignant semble souhaiter dégouter les étudiant de l'algo… Parce que voilà les confusions…

Les listes chainées ne sont pas un type mais une algo. Il n'est donc pas question de les avoir "de base dans Python", juste de savoir si c'est la manière dont tu souhaite organiser tes données.

De ce que tu présente, tu a une classe (Liste, pas de parenthèse à la déclaration) qui n'a qu'une méthode, son constructeur (oui, initialiseur). À coté, tu a une fonction (et non pas une méthode), init(L). En passant, super le nomage des variables. Cette méthode te retourne un objet de type Liste, pas une "liste chainée". Si je te demande le type de retour, c'est bien un objet de type Liste.

Ton objet de type Liste contient deux attributs. Valeur est du type de la valeur d'un élément du tableau L et suivant est de type Liste.

La méthode init est imbitable. Elle parcourt en effet une liste, et pour chaque élément, elle crée un objet de type Liste et le stock en temporaire afin de créer l'objet suivant car celui-ci doit être attribué à l'attribut suivant…

Bon, d'une part, en "vrai" Python, on écrirait ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Liste: def __init__(self, head, tail=None): self.valeur = head self.suivant=tail   def init(L): res=Liste(L[0]) p=res for element in L[1:]: tmp=Liste(element) p.suivant=tmp p=p.suivant return res

---

Mais en fait, init devrait se parcourir à l'envers, ça simplifie tout :

Code:

---

1 2 3 4 5 6 7

def init(L): item = None for element in reversed(L): item = Liste(element, item) # Attention, j'avais écris Liste(L, item), comme quoi, le nommage…   return item

---

On crée un élément et on garde une référence sur celui-ci. À l'itération suivante, on crée un nouvel élément en passant l'ancien en paramètre en tant que "suivant" et on passe la référence à ce dernier. Ainsi de suite jusqu'au premier objet que l'on retourne.
Ainsi, tu aura

Code:

---

1 2 3 4 5 6 7 8

>>> first_knight = init(["Arthur", "Lancelot", "Robin"]) >>> print(first_knight.valeur) Arthur >>> print(first_knight.suivant.valeur) Lancelot >>> print(first_knight.suivant.suivant.valeur) Robin

---

Donc tu ne manipule pas d'adresses mais des références à des objets (sous le capot c'est des adresses, mais on s'en fiche). Chaque objet sait quel est le suivant et tu dois parcourir la grappe élément après élément contrairement aux listes où tu accès à un élément par indice en plus de l'itération… Sauf que là, tu ne peux pas non plus utiliser un itérateur (for).
Les listes chainées sont une algo d'implémentation de collection quand le langage a des types limités. En Python, elles ne servent quasiment à rien.

Bonjour,
merci beaucoup de ta réponse. Ce n'est pas que moi qui ai du mal avec "init", ça me rassure un peu. Je vais me tourner vers la deuxième solution que tu as donné, qui me semble plus évidente et plus simple à comprendre !
Je ne pense pas que le prof souhaite nous dégouter de l'algo, néanmoins selon lui, Python est plus abordable pour traiter la question des listes chainées (il faisait ce cours avec Java les deux années précédentes, et je crois, je dis bien je crois, que Java rend l'exercice plus difficile).


Merci beaucoup pour tes explications, j'y vois plus clair maintenant !

Citation:

---

Envoyé par chalael

Je ne pense pas que le prof souhaite nous dégouter de l'algo, néanmoins selon lui, Python est plus abordable pour traiter la question des listes chainées (il faisait ce cours avec Java les deux années précédentes, et je crois, je dis bien je crois, que Java rend l'exercice plus difficile).

---

Java ??? Oh carrément… Mais ce n'est pas exactement la faute d'un langage mais du fait que l'algo…*ne se travaille pas avec un langage. Un cours d'algo, c'est sur le papier. Oui je sais, ça peut paraitre aberrant mais ton cas démontre que la difficulté lorsqu'on le travaille avec un langage, c'est que l'étudiant essaye de comprendre l'algo et le langage… Et surtout, cela peut entrainer des tortures du langage pour faire rentrer des notions qui n'ont rien à y faire.
Pour les listes chainées, le langage le plus adapté est le C. L'élément, c'est une struct. Transposé en Python, on se retrouve avec des objets castrés à la Java qui ne servent qu'à regrouper deux données. Donc il faut en plus que tu comprenne la notion d'objet qui est ici pervertie.

Avant de finir, je commencerai par dire que

Citation:

---

Envoyé par chalael

merci beaucoup de ta réponse. Ce n'est pas que moi qui ai du mal avec "init", ça me rassure un peu. Je vais me tourner vers la deuxième solution que tu as donné, qui me semble plus évidente et plus simple à comprendre !

---

Je n'ai pas de problème avec init, j'ai des problèmes avec le nommage général dans cet extrait. Si je devais reprendre une version propre, ce serait :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

class LinkableElement: def __init__(self, value, next=None): self.value = value self.next = next   def link_elements(some_list): item = None for element in reversed(some_list): item = LinkableElement(element, item) # Attention, faute dans ma version précédente…   return item

---

Et donc pour conclure, en Python, il n'est pas nécessaire de créer des objets pour lier des valeurs. Python n'a pas de structs mais on peut gérer ça avec des listes (le code suivant est suffisant, pas besoin de créer une classe dont ce type ne sert à rien)

Code:

---

1 2 3 4 5 6 7

def link_elements(some_list): item = None for element in reversed(some_list): item = list((element, item))   return item

---

Le retour de link_elements est une liste l tel que l[0] est une valeur et l[1] est l'élément liste de 2 éléments suivant. Donc on aurai

Code:

---

1 2 3 4 5 6 7 8

>>> first_knight = init(["Arthur", "Lancelot", "Robin"]) >>> print(first_knight[0]) Arthur >>> print(first_knight[1][0]) Lancelot >>> print(first_knight[1][1][0]) Robin

---

et on est d'accord que l'accès aux données est peu pratique et la structure rigide (en fait non pour ce qui nous intéresse mais c'est une spécificité de Python) alors on peut aussi utiliser des dictionnaires

Code:

---

1 2 3 4 5 6 7

def link_elements(some_list): item = None for element in reversed(some_list): item = dict(value=element, next=item)   return item

---

la fonction retourne un dict et là tu aura

Code:

---

1 2 3 4 5 6 7 8

>>> first_knight = init(["Arthur", "Lancelot", "Robin"]) >>> print(first_knight['value']) Arthur >>> print(first_knight['next']['value']) Lancelot >>> print(first_knight['next']['next']['value']) Robin

---

Donc voilà, quand je dis qu'il essaye de vous en dégouter, ce n'est pas une volonté de sa part mais qu'en utilisant un langage, il ajoute la difficulté de la spécificité de chaque langage.

Citation:

---

nous sommes actuellement en train de voir les listes Chainées

---

Ce n'est pas un objectif ça !

1. Quel est l'objectif ou le but à atteindre pour l'étudiant de faire cet exercice ?
2. Avez-vous eu un cours lié ou en rapport à cet exercice ?
3. Quels sont les pré-requis que vous avez afin de résoudre l'exercice ?
4. Avez-vous travaillé sur les tableaux en C ?
5. Quel est l'avantage des listes chaînées par rapport aux tableaux ?

Si tu sais répondre à tout ça, alors je veux bien croire à un intérêt sur l'exercice donné.

Je vois ce que tu veux dire Martopioche, et je suis d'accord, pour moi l'algo doit se faire sur papier, du moins le plus gros du travail. Personnellement je n'ai jamais fait de Python, et pour l'instant, à par recopier des fonctions dans mon éditeur, et chercher comment fonctionne la syntaxe, je n'ai rien fait d'utile me permettant de comprendre comment fonctionne le concept de "liste chainée". Ce qui me bloque le plus pour l'instant c'est le langage et l'adaptation de ce que l'on a vu en cours dans le langage.

Fred :
1)Le but serait de manipuler des structures de données dynamiques. De ce que j'ai comprit par exemple, lorsque l'on doit ajouter des données dans une structure mais que l'on ne sait pas combien de donnée l'on va devoir rentrer
2)Nous sommes en train de faire le cours qui s'appelle : "Structures séquentielles simples : listes chaînées"
3)Les pré-requis sont la classe Liste ainsi que la fonction "init" que j'ai mit dans mon premier message sur ce post
4)Non, notre professeur nous en a rapidement parler, je n'ai jamais fait de C mais de ce que j'ai pu comprendre, en C on manipule directement les adresses (?)
5)L'avantage des listes chainées serait de ne pas prendre un bloc mémoire (par exemple pour un tableau je "bloque" 10 espaces mémoires), mais de rajouter des données à différents endroits en liant chaque données à la suivante

Citation:

---

Fred :
1)Le but serait de manipuler des structures de données dynamiques. De ce que j'ai comprit par exemple, lorsque l'on doit ajouter des données dans une structure mais que l'on ne sait pas combien de donnée l'on va devoir rentrer
2)Nous sommes en train de faire le cours qui s'appelle : "Structures séquentielles simples : listes chaînées"
3)Les pré-requis sont la classe Liste ainsi que la fonction "init" que j'ai mit dans mon premier message sur ce post
4)Non, notre professeur nous en a rapidement parler, je n'ai jamais fait de C mais de ce que j'ai pu comprendre, en C on manipule directement les adresses (?)
5)L'avantage des listes chainées serait de ne pas prendre un bloc mémoire (par exemple pour un tableau je "bloque" 10 espaces mémoires), mais de rajouter des données à différents endroits en liant chaque données à la suivante

---

Très bien, alors cet exercice n'est pas inutile, l'enseignant vous a bien fait comprendre l'intérêt d'une telle structure de données qu'est la pile.

Par contre, est-ce que votre professeur vous avait donné des contraintes concernant cet exercice ?

Aucune, ci ce n'est que notre fonction doit prendre une "liste native Python" (c'est ce qui est dans l'énoncé), et en sortie on doit obtenir une Liste chainée

Et donc voilà exactement ce que je reproche à la démarche. Chaque langage a une gestion de ses types de données, structures de contrôle, fonctions… Si l'étudiant passe son temps à comprendre l'instruction, c'est autant de temps de perdu sur la compréhension de l'algo.
J'espère que vous avez au moins des questions sur l'insertion d'éléments sinon, c'est gâché.

Alors pour donner plus d'informations, les différents exercices ont pour but de recréer une barrière d'abstraction pour les listes chainées, donc on doit faire : une fonction "init" (qui était l'objet de ma question), une fonction print qui doit afficher entre parenthèse et séparer par une virgule les éléments de notre liste chainée, équivalent de la fonction "append" pour insérer un élément à la fin d'une liste chainée, une fonction get(L, index) qui retourne l’élément d’indice indexde la liste s’il existe et None sinon, et pour finir une fonction set(L, index, value) qui modifie la valeur de l’élément d’indice index dans la liste L

Citation:

---

Envoyé par chalael

Alors pour donner plus d'informations, les différents exercices ont pour but de recréer une barrière d'abstraction pour les listes chainées, donc on doit faire : une fonction "init" (qui était l'objet de ma question), une fonction print qui doit afficher entre parenthèse et séparer par une virgule les éléments de notre liste chainée, équivalent de la fonction "append" pour insérer un élément à la fin d'une liste chainée, une fonction get(L, index) qui retourne l’élément d’indice indexde la liste s’il existe et None sinon, et pour finir une fonction set(L, index, value) qui modifie la valeur de l’élément d’indice index dans la liste L

---

Attends…*Plus haut, tu parlait de "méthode" init… Est-ce que tu ne dois pas créer un objet qui encapsule les données sous forme le liste chainée en exposant ces méthodes et alors la méthode init est la méthode spéciale __init__(self) de Python qui permet d'instancier un objet…

Moi j'dis ça… Mais on reviens au fait que vous apprenez ET Python ET l'algo…

Pardonne moi je n'ai pas tout comprit de ce que tu as dit ... Nous avons d'un côté la classe Liste avec une fonction "__init__" et de l'autre nous avons une fonction "init", mais ne comprenant pas la première (créer le "type" liste chainée ?) je ne peux pas te donner plus d'information