Équivalent des listes chainées

Bonjour,

Je travaille actuellement sur un générateur de trames (en vue de les transmettre à un serveur).
J'ai une ébauche du programme en C, qui utilise des listes chainées (des structures récursives), et j'aimerais savoir si ces listes chainées avaient un équivalent en python.

Pour information, une liste chainée en C est une structure qui contient (en plus des données) un pointeur vers une variable du même type.

Exemple :

Code:

---

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

typedef struct liste_chainee_trames_source {   /* L'entête de la trame: numéro lanceur, numéro trame, spare bits : 32 bits*/ char entete[4];   // Les données source : SOURCE_DATA_LENGTH bits char donnes_source[SOURCE_DATA_LENGTH/8];   // Le CRC correspondant : 16 bits char crc[2];   struct liste_chainee_trames_source *next_trame;   } liste_chainee_trames_source;

---

J'ai vaguement vu un document pdf qui parlait de chainage, mais ce n'était pas vraiment clair.

Merci d'avance
Cordialement,

Bonjour,

Oui, on peut facilement chainer des objets, et même fabriquer des arbres ou des structures plus complexes.

Voilà un exemple tout simple:

On définit l'objet sous forme de classe:

Code:

---

1 2 3 4 5

class Obj(object): def __init__(self, ind): self.ind = ind self.suiv = None

---

Ici, self.ind est un index pour reconnaitre les instances de classe entre eux (=pour vérifier que ça marche) et self.suiv est là pour pointer sur une autre instance de classe (= un autre objet).

On va donc instancier cette classe pour chainer 4 instances, de la façon suivante:

Code:

---

1 2 3 4 5 6 7 8 9 10

debut = Obj(1)   debut.suiv = Obj(2)   x = debut.suiv x.suiv = Obj(3)   x = x.suiv x.suiv = Obj(4)

---

Et maintenant on vérifie que ça marche: on va suivre les instances de la chaine jusqu'au bout, c'est à dire jusqu'à l'objet qui a un self.suiv==None:

Code:

---

1 2 3 4 5

z = debut while z!=None: print z.ind z = z.suiv

---

Ce qui affiche:

Code:

---

1 2 3 4

1 2 3 4

---

Dans la gestion mémoire, on peut "laisser tomber" les objets non utilisés: ils sont alors traités par le ramasse-miette quand c'est utile.

Au lieu de laisser les objets "en l'air", on peut aussi les faire supporter par une liste. On peut alors, par exemple, créer facilement des piles fifo ou lifo d'objets complexes en utilisant les primitives de gestion de liste.

Ok?

Tyrtamos

Hum, je ne suis pas sur d'avoir tout compris. Pourquoi avoir un paramètre après class ?

Avec quelque chose comme ça, ça peut marcher ?

Code:

---

1 2 3 4 5

class List: def __init__(self,entete="";donnees="",crc="",next=None): self.entete = entete self.donnees = donnees self.crc = crc

---

Imaginons que je sois dans une boucle. Je veux ajouter mes noeuds au fur et à mesure.

Code:

---

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

entete = a données = b crc = c nouvelle_trame = List(a,b,c)   if derniere_trame_source==None: trames_sources=nouvelle_trame derniere_trame_source=nouvelle_trame else: derniere_trame_source.next=nouvelle_trame derniere_trame_source=nouvelle_trame

---

Qu'en penses tu ?

Merci de ton aide, en tout cas, et bonne année !

Bonjour, et meilleurs voeux à toi aussi!

Voilà ta classe corrigée:

Code:

---

1 2 3 4 5 6 7

class List(object): def __init__(self, entete="", donnees="", crc=""): self.entete = entete self.donnees = donnees self.crc = crc self.next = None

---

j'ai fait plusieurs corrections:

- List(object) au lieu de List parce que c'est comme ça qu'il faut faire: les classes doivent hériter d'une autre classe, et c'est object par defaut. Ta solution pourrait encore marcher, mais elle n'est pas recommandée.

- il y avait un ';' au lieu d'une ',' dans la liste des paramètres.

- Il faut initialiser self.next=None comme je l'avais mis dans mon exemple. Tel que tu l'as fait, le paramètre next est bien initialisé à None pendant l'instanciation de la classe, mais il est perdu à la fin de l'exécution de la méthode __init__: tu ne pourrais donc pas le tester plus tard à None sans générer une erreur.

Pour la suite, c'est à moi de ne pas bien comprendre ce que tu veux faire. A mon avis, tu devrais essayer toi-même avec un python 2.6 et un petit texte sous idle. C'est facile à installer et tu gagneras du temps. Tu prends ce que je t'ai donné, et tu modifies progressivement jusqu'à obtenir ce que tu veux.

Et pour tes codes insérés dans tes messages ici, utilise les tags de code, sinon, les indentations ne sont pas conservées et, avec python, c'est rapidement incompréhensible.

Tyrtamos

On peut effectivement reproduire les listes chainées en Python comme l'explique tyrtamos, mais est-ce nécessaire pour ton problème ? Est-ce qu'une liste Python ne suffirait pas ? Est-ce que tu dois souvent insérer ou supprimer des éléments au milieu de la liste ? C'est la seule raison à laquelle je pense, si la liste est très longue, de reproduire une structure de liste chainée.

On a tendance, en passant d'un langage à un autre, à vouloir importer les techniques acquises dans le premier langage, mais ce n'est pas toujours ce qui convient le mieux dans le second. Surtout lorsque le premier est un langage bas niveau comme le C et le second haut niveau comme Python.