On propose la fonction, écrite en pseudo code, $mystere(L,i)$ où $L$ est une liste et $i$ une clé de cette liste :

1. mystere(L,i)
2. x=tete[L]
3. si cle[x]==i 
4.      tete[L]=succ[x]
5. sinon 
6.      tant que cle[x]!=i et pointeVers[succ[x]]!=NIL
7.          y=x 
8.          x=succ[x]
9.      fin tant que
10.     pointeVers[succ[y]]=pointeVers[succ[x]]

1. Effectuer une trace d'exécution de $mystere(L,cle[\alpha])$, où $L$ est la liste simplement chaînée contenant les valeurs $\{\alpha;\gamma;x;\beta;a;3;z;\phi;\omega\}$, liste simplement chaînée représentée ici, en reproduisant et en complétant le tableau suivant :

   Numéro de ligne	$x$	$succ[x]$	$i$	$L$	$y$	$pointeVers[succ[y]]$	$pointeVers[succ[x]]$	$Tete[L]$	Test
   ...	...	...	...	...	...	...	...	...	...
   ...	...	...	...	...	...	...	...	...	...

Code de déblocage de la correction :

2. De même, effectuer une trace d'exécution de $mystere(L,cle[a])$ où $L$ est la liste simplement chaînée contenant les valeurs $\{\alpha;\gamma;x;\beta;a;3;z;\phi;\omega\}$, liste simplement chaînée représentée ici.

3. Proposer un nom pertinent pour la fonction $mystere$ en comprennant le rôle de cette fonction.

Code de déblocage de la correction :

On propose la fonction $mystere(L,k)$ où $L$ est une liste et $k$ une clé de cette liste suivante écrit en pseudo code :

1. mystere(L,k) 
2. x=tete[L]
3. tant que cle[x]!=k et pointeVers[succ[x]]!=NIL
4.    x=succ[x]
5. fin tant que
6. retourner x
                            

1. appliquer $mystere(L,cle[\alpha])$, où $L$ est la liste simplement chaînée contenant les valeurs $\{\alpha;\gamma;x;\beta;a;3;z;\phi;\omega\}$, liste simplement chaînée représentée ici..

   Code de déblocage de la correction :

2. appliquer $mystere(L,cle[a])$, où $L$ est la liste simplement chaînée contenant les valeurs $\{\alpha;\gamma;x;\beta;a;3;z;\phi;\omega\}$, liste simplement chaînée représentée ici..

3. Proposer un nom pour la fonction $mystere$.

4. Que pensez-vous de la seconde condition de la boucle tant que pointeVers[succ[x]]!=NIL.

Code de déblocage de la correction :

Écrire en pseudo code les fonctions suivantes :

1. $longueur(L)$ : qui renvoie le nombre d'élément dans la liste.

2. $insererEnDebut(L,x)$ : L'élément $x$ (de la forme ($clé[x]$,$pointeVers[succ[x]]$)) est inséré à la tête de la liste. (Seule la donnée de l'élément $x$ est insérée, le pointeur dépend de la liste $L$).

3. $inserer(L,a,e)$ : L'élément $e$ est inséré après l'élément de clé $a$ présent dans la liste $L$. (Seule la donnée de l'élément $e$ est insérée, son pointeur est adapté à la liste $L$).

Créer la classe ListeSimpleCh qui possède comme attribut un objet de type list et sa tête à partir des listes en Python. On donne Le constructeur __init__(self,l,tete) avec deux attributs une liste $l$ et une $tete$ :

class ListeSimpleCh:
    """définition de l’objet liste"""
    
    def __init__(self,l,tete):
        self.l = l
        self.t=tete
    

Créer une instanciation de la classe ListeSimpleCh avec la liste [1,'bos',4,"BG",0]. Afficher la tete de liste.

Vous devez ajouter à cette classe :

• La méthode estVide(self) qui teste si une liste est vide.

• L'accesseur tete(self) qui renvoie la tête de la liste.

• L'accesseur succ(self,x) qui renvoie le successeur de $x$ en vérifiant que ce successeur existe( faire des assert).

Le but de cet exercice est de créer une classe Element dont chaque instance correspond à un élément d'une liste simplement chaînée.

1. Créer cette classe avec son constructeur de sorte qu'un objet de cette classe possède deux attributs :

   • cle qui correspond à la valeur de cet élément,

   • pointeur qui correspond au successeur de de cet élément.

   None sera la valeur donnée à un de ces attributs si celui-ci est vide.

2. Rajouter une méthode estVide qui renvoie un booleen True si cet élément de liste chaînée est vide et False sinon.

3. Rajouter la méthode __str__ suivante afin de tester la classe créée et pour mieux visualiser chaque instance :

       def __str__(self):
           """permet de visualiser un élément. """
           if not self.estVide():
               if self.pointeur == None:
                   ch = "(" + str(self.cle) + "|NIL)."
                   return ch
               else:
                   ch = "(" + str(self.cle) + "|-->" + str(self.pointeur) + ")...>"
                   return ch
                       

Voici le début d'une classe ListeSpChainee implémentant la structure linéaire de liste simplement chaînée :

class ListeSpChainee:
    """définition de l’objet liste simplement chaînée comme juxtapositionn d'élément de la classe Element"""

    def __init__(self, debut=None):
        """création d'une liste vide"""
        self.tete = Element(debut)
                    

1. Créer une méthode lstVide qui renvoie True si la liste simplement chaînée est vide, False sinon.

   Comme chaque élément d'un objet de la classe ListeSpChainee est une instance de la classe Element, il suffit d'utiliser une méthode créée sur cette classe à l'exercice précédent.

2. Créer une méthode ajouterEltEnFin qui prend en argument une valeur, qui crée un objet de type Element ayant comme cle cette valeur et qui rajoute cet élément en fin de la liste sur laquelle s'applique cette méthode.

   • Penser à traiter le cas où la liste est initialement vide,

   • Penser à gérer le pointeur du dernier élément de la liste initiale.

3. Rajouter la méthode __str__ suivante afin de tester la classe créée et pour mieux visualiser chaque instance :

       def __str__(self):
           ch = ""
           if not self.lstVide():
               lecteur = self.tete  # position de l'élément regardé (on commence toujours par la tête pour une liste simplement chaînée)
               while lecteur.pointeur != None:
                   ch += "(" + str(lecteur.cle) + "|-->" + str(lecteur.pointeur.cle) + ")...>"
                   lecteur = lecteur.pointeur   # on passe à l'élément suivant.
               ch += "(" + str(lecteur.cle) + "|NIL)."
           return ch
                       

1. Rajouter à la classe précédente ListeSpChainee une méthode get_tete qui renvoie l'élément en tête de l'objet si celui n'est pas vide.

2. Rajouter à cette classe ListeSpChainee une méthode succ qui prend en argument une valeur elt, qui cherche dans la liste chaînée l'élément contenant cette valeur et renvoie le successeur de cette valeur dans le cas où un tel élément a été trouvé.
   Penser à afficher des messages d'erreurs dans les cas où l'élément n'a pas été trouvé.

Un enseignant de NSI stocke les résultats de ses élèves à l'aide d'un dictionnaire :

• les clés sont les noms des élèves,

• les valeurs sont des dictionnaires dont les clés sont les noms des épreuves et les valeurs sont des listes contenant la note obtenue suivie du coefficient de l'épreuve.

Voici le dictionnaire de 3 de ses élèves :

resultats = {'Alice': {'DS1' : [15.5, 3], 
                       'DM1' : [14.5, 1], 
                       'DS2' : [17, 4], 
                       'PROJET1' : [18, 5], 
                       'DS3' : [16, 4]}, 
                'Bob':{'DS1' : [6 , 3], 
                       'DM1' : [14.5, 1], 
                       'DS2' : [8.8, 4], 
                       'PROJET1' : [10, 5], 
                       'IE1' : [7, 2], 
                       'DS3' : [8, 4], 
                       'DS4' :[10, 4]},
              'Chaïn':{'DS1' : [13.5, 3], 
                       'DM1' : [16, 1], 
                       'DS2' : [14.5, 4], 
                       'PROJET1' : [16, 5], 
                       'IE1' : [16, 2], 
                       'DS4' : [19, 4]}}
                    

Le problème est que le professeur n'arrive pas à créer une fonction moyenne prenant en paramètre le dictionnaire resultat ainsi qu'un nom sous forme de chaîne de caractères et qui renvoie la moyenne des notes de l'élève ayant ce nom nom dans le cas où son nom apparaît dans le dictionnaire resultat.

Proposer une telle fonction moyenne afin d'aider cet enseignant. Il en sera surement reconnaissant !