Discussion :

[chalael]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[martopioche]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[chalael]

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 !

[martopioche]

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

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[fred1599]

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é.

[chalael]

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