Discussion :

[LupusCramus]

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 C :

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

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,

[tyrtamos]

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 :

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

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 :

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

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 :

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

1
2
3
4
5
 
z = debut
while z!=None:
    print z.ind
    z = z.suiv

Ce qui affiche:

Code :

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

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

[LupusCramus]

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 :

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

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 :

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

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 !

[tyrtamos]

Bonjour, et meilleurs voeux à toi aussi!

Voilà ta classe corrigée:

Code :

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

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

[dividee]

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.