L'objectif de cette activité est de découvrir comment implémenter les différentes structures de données en Python, avec ou sans les objets, à travers 3 TP :
- TP1 : Implémentation d'un arbre binaire par tuple de tuple (sans utiliser les objets)
- TP2 : Implémentation d'un arbre binaire en Programmation Orientée Objet (POO)
- TP3 : Implémentation des structures de données linéaires en POO
TP1 : Implémentation d'un arbre binaire par tuple de tuple
|
Voici les différents éléments vus durant ce TP1 :
- définition récursive des arbres binaires
- implémentation d'un nœud avec un tuple (racine,fils gauche,fils droit)
- l’arbre vide est représenté par None
- codage d'un arbre binaire avec des tuples de tuples
- par exemple :
arbre=(2,(1,(0,None,None),None),(5,(4,(3,None,None),None),(12,(9,(8,(6,None,(7,None,None)),None),(10,None,(11,None,None))),(13,None,(14,None,(18,(17,(15,None,(16,None,None)),None),(19,None,None)))))))
- affichage du nombre de nœuds, du nombre de feuilles, de la liste de feuilles et de la hauteur de l'arbre binaire
- tracé graphique de l'arbre binaire en utilisant la bibliothèque matplotlib
- implémentation d'un arbre binaire de recherche (ABR) avec des tuples de tuples
- recherche récursive d'une valeur dans l'ABR
- recherche du minimum (on va à fond à gauche) et du maximum (on va à fond à droite) dans l'ABR
- modification de l'ABR : ajout et suppression d'une valeur
- génération d'un ABR aléatoire à partir d'une liste aléatoire
- implémentation des différents types de parcours d'un arbre
- le parcours en largeur (parcours niveau par niveau)
- distinction entre les 3 parcours en profondeur :
- le parcours préfixe : R,G,D
- le parcours infixe : G,R,D (donne une liste triée des nœuds de l’ABR)
- le parcours suffixe : G,D,R
- utilisation d'un ABR pour trier une liste aléatoire : on range la liste dans un ABR puis on donne son parcours infixe
- création d'une liste par compréhension. Exemple : [2*k for k in range(8)] donne [0, 2, 4, 6, 8, 10, 12, 14]
- codage d'un texte en binaire en utilisant les codes ASCII des caractères
- décodage d'un message binaire pour retrouver les codes ASCII
- notion de code-préfixe (aucun mot du code préfixe ne peut se prolonger pour donner un autre mot du code)
- codage de Huffman pour la compression de données : il génère pour chaque caractère un code-préfixe à taille variable
- utilisation d'un file de priorité (file auto-triée lors de l'ajout d'un élément) avec le module heapq de Python
- estimation du taux de compression obtenu avec le codage de Huffman par rapport au codage ASCII
TP2 : Implémentation d'un arbre binaire en Programmation Orientée Objet (POO)
|
Voici les différents éléments travaillés durant ce TP2 :
Création d'une classe Arbre possédants les méthodes suivantes :
- __init__(self, val)
- ajout_gauche(self, val)
- ajout_droit(self, val)
- taille(self)
- hauteur(self)
- vide(self) renvoyant True si l'arbre est vide
Création de 3 fonctions externes à la classe Arbre prenant en paramètre un objet "arbre" de classe Arbre et affichant chacune un parcours en profondeur sur une ligne dans la console :
- parcours_prefixe(arbre)
- parcours_infixe(arbre)
- parcours_suffixe(arbre)
Enrichissement de la classe Arbre en créant 3 nouvelles méthodes qui affichent chacune un parcours en profondeur de l'arbre lui-même sur une ligne dans la console :
- parcours_prefixe(self)
- parcours_infixe(self)
- parcours_suffixe(self)
TP3 : Implémentation des structures de données linéaires en POO
|
Voici les différents éléments vus durant ce TP3 :
- rappel des bases de la POO : classes, attributs et méthodes
- rappel sur les structures de données (linéaire ou non linéaire, homogène ou non, statique ou dynamique)
- création, test et solution de la classe Perso
- création d'un classe Tableau avec les méthodes insert et supprime (programme de base à compléter puis solution finale donnée)
- création d'un classe Pile (programme de base à compléter puis solution finale donnée)
- création d'un classe File (programme de base à compléter puis solution finale donnée)
- création d'un classe Maillon pour implémenter une liste chaînée (programme de base à compléter puis solution finale donnée)
Vous savez maintenant implémenter en Python toutes sortes de structures de données, avec ou sans la programmation orientée objets.
Réalisé par Jean-Christophe MICHEL
© Janvier 2025
