Aller au contenu
La liste chaînée en programmation objetChapitre 11/12

La classe Maillon

AttentionCe chapitre utilise la programmation orientée objet (classes, __init__, self, méthodes). Si besoin, passe d'abord par le cours POO.

Au chapitre 3, un maillon était un dictionnaire {"valeur": ..., "suivant": ...}. En POO, c'est un objet avec deux attributs :

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

suivant=None est une valeur par défaut : si on ne précise pas le suivant, il vaut None. On peut construire une chaîne d'un coup, de la fin vers le début :

tete = Maillon(12, Maillon(8, Maillon(17)))
print(tete.valeur)                 # 12
print(tete.suivant.valeur)         # 8
print(tete.suivant.suivant.valeur) # 17
print(tete.suivant.suivant.suivant) # None
Chapitre 3 (dictionnaire)POO (objet Maillon)
{"valeur": 8, "suivant": m}Maillon(8, m)
m["valeur"]m.valeur
m = m["suivant"]m = m.suivant
Programme complet du cours structures de données (12 chapitres, gratuit)
  1. 1. Ranger des données dans la mémoire : La RAM est un gros tableau de cases numérotées de 0 à N - 1 : 8 milliards pour 8 Go. Impossible de tout relire pour trouver une donnée, d'où les structures de données : un ordre connu à l'avance et des règles pour y accéder. Interface et implémentation.
  2. 2. Le tableau : des cases côte à côte : Des cases contiguës numérotées : accès direct par l'indice en une seule étape, mais insérer ou supprimer au début oblige à tout décaler.
  3. 3. La liste chaînée : des maillons reliés : Des maillons éparpillés dans la mémoire, chacun connaît l'adresse du suivant : insérer ou supprimer revient à raccrocher une flèche, mais lire le 100e oblige à passer par les 99 premiers.
  4. 4. La pile : dernier arrivé, premier sorti : La pile d'assiettes : on pose en haut, on prend en haut. Empiler, dépiler, sommet, LIFO, et une pile en Python avec append et pop.
  5. 5. La file : premier arrivé, premier servi : La file d'attente : on arrive à la fin, on sort par le début. Enfiler, défiler, FIFO, la différence avec la pile, et une file en Python.
  6. 6. Devine la structure : Le retour d'Insta, Ctrl+Z, la file d'impression, la playlist « à suivre », le distributeur de Pez, la pile d'appels : reconnaître la structure cachée derrière des situations réelles.
  7. 7. Les arbres : ranger en hiérarchie : Arborescence de fichiers, arbre généalogique, tournoi : une racine, des nœuds, des feuilles. Vocabulaire, hauteur, taille et arbre binaire.
  8. 8. Parcourir un arbre : Visiter tous les nœuds d'un arbre, chacun une fois : le parcours en largeur (avec une file), et les parcours en profondeur préfixe, infixe et suffixe.
  9. 9. L'arbre binaire de recherche : Plus petit à gauche, plus grand à droite : chercher une valeur en éliminant la moitié de l'arbre à chaque comparaison, insérer, et pourquoi l'arbre doit rester équilibré.
  10. 10. Pile et file en programmation objet : Écrire les classes Pile et File, puis une file fabriquée avec deux piles : même interface, autre implémentation.
  11. 11. La liste chaînée en programmation objet : Les classes Maillon et ListeChainee : ajouter en tête, parcourir, compter, lire le k-ième, ajouter en queue, supprimer. Puis une pile implémentée par une liste chaînée.
  12. 12. Les arbres en programmation objet : La classe Noeud, la récursivité pour la taille et la hauteur, les parcours préfixe, infixe, suffixe et en largeur, puis l'insertion et la recherche dans un ABR.