Skip to content

Opérations sur listes simplement chaînées

Énoncé

On se propose de travailler sur des opérations de haut niveau sur les listes simplement chaînées réalisées précédemment dans le mini projet Listes simplement chaînées. Vous testerez vos fonctions au fur et à mesure de vos développements sur les entrées qui vous semblent les plus pertinentes. Mis à part le constructeur de la classe ListeSimplementChainee aucune des fonctions ci-dessous ne doit créer de nouvelles cellules.

Dans ce mini projet nous allons mettre en pratique les concepts d'itérateur, d'itérable et de fonction génératrice. Pour rappel :

  • un itérable est une instance à partir de laquelle on peut récupérer un itérateur et donc une instance sur laquelle on peut faire une boucle for ;
  • un itérateur est une instance à partir de laquelle on peut récupérer le prochain élément ;
  • un itérateur est un itérable ;
  • une fonction génératrice, aussi appelée générateur renvoie un itérateur (donc un itérable d'après le point ci-dessus).

Travail demandé :

  • Modifiez le constructeur __init__ de la classe ListeSimplementChainee pour construire une liste simplement chaînée à partir d'un itérable. Par exemple ListeSimplementChainee(range(1, 10)) doit construire une liste contenant tous les entiers entre 1 (inclus) et 9 (inclus).
  • Implémentez un générateur recupere_cellules(liste_chainee) qui renvoie un itérateur sur toutes les cellules de la liste donnée.
  • Implémentez une fonction remplace_valeurs(liste_chainee, transforme) qui remplace pour chaque cellule la valeur par la valeur renvoyée par l'appel de fonction transforme(valeur).
  • Étant donnée une fonction filtre(valeur) renvoyant un booléen, on souhaite récupérer un itérateur sur toutes les cellules de la liste simplement chaînée pour lesquelles filtre(valeur) renvoie True. Implémentez un générateur filtre_cellules(liste_chainee, filtre) renvoyant un tel itérateur. Votre générateur de filtrage devra lancer une exception si filtre(valeur) ne renvoie pas un booléen.
  • Utilisez filtre_cellules(liste_chainee, filtre) pour implémenter une fonction supprime_cellules(liste_chainee, filtre) qui élimine de liste_chainee toutes les cellules pour lesquelles filtre(valeur) renvoie False.

  • Implémentez une fonction concatene(liste_chainee_1, liste_chainee_2) rajoutant les cellules de liste_chainee_2 à la fin de liste_chainee_1. liste_chainee_2 doit devenir vide.

  • Implémentez une fonction decoupe(liste_chainee, fonction) qui crée et retourne deux listes simplement chaînées décrites ci-dessous (attention : l'ordre des cellules dans chacune des deux listes simplement chaînées est conservé) :

    • une liste chaînée contient les cellules pour lesquelles la fonction fonction renvoie True ;
    • la seconde liste chaînée contient les autres cellules.

Exercices