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