On donne $L=\{NSI;plaisir; jeux;livres; \pi; E0F1\}$

Expliciter ce que font chacune des commandes suivantes :

1. $ajouteEnFin(33,L)$ .
2. $dernier(L)$.
3. $debut(L)$ .
4. $supprDernier(L)$.
5. $taille(L)$.
6. $get(2,L)$.

Ecrire chaque élément de l'interface à l'aide des fonctions écrites dans la partie suivante.

CORRECTION :

• $listeVide=créerListeVide$
• $ajouteEnFin(x,L) $
• $dernier(L)$ : renvoie le dernier élément de $L$.
• $debut(L)$ : renvoie la liste $L$ auquel on a retiré le dernier élément.
• $supprDernier(L)$ : supprime le dernier élément de L.
• $taille(L)$ : renvoie le nombre d'éléments dans $L$.
• $get(i,L)$ : renvoie l'élément d'indice $i$ de $L$.

Ecrire les fonctions suivantes en Python à partir de la classe définie précédemment

1. $supprimer(L,i)$ : L'élément de clé i est supprimé de la liste.
2. $rechercheListe(L,k)$ : qui retourne l'index du premier objet de clé k.
3. $longueur(L)$ : qui renvoie le nombre d'élément dans la liste.
4. $insererEnDebut(L,x)$ : L'élément $x$ est inséré à la tête de la liste.

Préciser quelle est la structure de donnée à privilégier pour chacune de ces taches :

1. Représenter un répertoire téléphonique.
2. Stocker l'historique des actions effectuées dans un logiciel et disposer d'une commande Annuler.
3. Envoyer des fichiers au serveur impression.
4. On souhaite stocker un texte très long que l'on souhaite pouvoir modifier

Correction :

1. On choisit le dictionnaire. Les clés seraient par exemple : nom, prénom, téléphone
2. On se retrouve à avoir une structure de donnée du type LIFO on prend donc une pile.
3. On se retrouve à avoir une structure de donnée du type FIFO on prend donc une file.
4. liste en implantation simplement chainée

Dans chacun des cas suivants, déterminez quelle structure de données est la plus adaptée :

1. Gérer le flux des personnes arrivant à la caisse d'allocations familiales ;
2. Mise en place d'un mécanisme annuler/refaire pour un traitement de texte ;
3. Garder les nombres premiers parmi les nombres de 2 à 1000 en utilisant la méthode du crible d'Eraosthène.
4. Lors d'une partie échec, on veut enregistrer l'ensemble des coups joués et pouvoir les consulter.

La pile et la poo

Voila une définition de la classe pile en Python :

class Pile:
    def __init__(self,haut,reste=None):
        self.h=haut
        self.r=reste
    def estVide(self):
        if self.h==None:
            return True
        else:
            return False
    def empiler(self,valeur):
        self.r=Pile(self.h,self.r)
        self.h=valeur
    
    def depiler(self):
        if self.r==None:
            haut=self.h
            self.h=None
            return haut
        else:
            haut=self.h
            self.h=self.r.h
            self.r=self.r.r
            return haut
    def affiche(self):
        if self.r==None:
            print(self.h)
        else:
            Pile.affiche(self.r)
            print(self.h)

On considère la pile : P=("bob",(3,("nsi",(5,("vacances",vide)))))

1. Créer une pile vide est testée qu'elle est bien considérée comme vide.
2. Implémenter P sur votre machine en utilisant les méthodes (constructeurs et modificateurs) de la classe Pile.
3. Améliorer la méthode affiche pour quelle affiche la pile dans le bon sens.
4. Ecrire une fonction hauteur(P) qui renvoie la hauteur de la pile.
5. Ecrire une fonction depil2(P) qui enlève de la Pile P l'élément situé en deuxième position de la pile et renvoie cet élément.
6. Ecrire une fonction insere(P,elt) qui insère dans P l'élément elt à la position 2. On considère la position 1 correspond au haut de la pile.
7. Ecrire une fonction acces(P,pos) qui renvoie l'élément situé en position "pos".

L'objet file en Python

Voila une définition de l'objet file en Python ( implémenter avec une liste doublement chainées)

On commence par définir un élément d'une liste doublement chainées :

class Element:
    #chaque élément a pour attribut : le precedent , le suivant et la valeur de l'élément
    def __init__(self,x):
        self.val=x
        self.precedent=None
        self.suivant=None
    def __str__(self): #methode qui permet de lance un print sur un tel objet
        return str(self.val)+"-"+str(self.suivant)

on définit ensuite l'objet file :

class File:
    #ici une file est la donnée de deux attributs : la file complète de type Element et le dernier élément de la file de type Element 
    def __init__(self):
        self.tete=None
        self.queue=None
    def enfile(self,x):
        e=Element(x) #on transforme l'élément à ajouter en un objet Element de listes doublement Chainées
        if self.tete==None:
            self.tete=e #file vide la tete est remplacée par l'élément e
        else:
            e.precedent=self.queue #le précédent de l'élément pointe sur l'ancienne queue de la file
            self.queue.suivant=e #l'ancienne queue de la file pointe sur e avec suivant
        self.queue=e #on redéfinit self.queue par e.
        
    def file_vide(self):
        return self.tete is None #renvoie True si None et False sinon
    
    def defile(self):
        if not self.file_vide():
            e=self.tete #on stocke l'élément à defiler
            if e.suivant is None: #cas où il n'y a qu'un élément 
                self.tete=None
                self.queue=None
            else:
                self.tete=e.suivant
                self.tete.precedent=None
            return e.val
        
    def __str__(self):
        return str(self.tete)

On considère la file : F=(5,11115,("vacances","Bob",7,"nsi",12))

Revoir l'implémentation de la file vue au cours sd1 en cas de besoin

1. Identifier, dans l'exemple, la tête, la queue et le cœur de F.
2. Créer une file vide et tester qu'elle est bien considérée comme vide.
3. Implémenter F sur votre machine en utilisant les méthodes (constructeurs et modificateurs) de la classe File.
4. Ecrire une fonction longueur(F) qui renvoie la longueur de la file.
5. Ecrire une fonction affiche_coeur(F) qui affiche le coeur de la file.
6. Ecrire une fonction defil2(F) qui enlève de la file F l'élément situé en deuxième position de la file et renvoie cet élément.
7. Ecrire une fonction insere(F,elt) qui insère dans F l'élément elt à la position 2. On considère la position 1 correspond au haut de la file.
8. Ecrire une fonction acces(F,pos) qui renvoie l'élément situé en position "pos".

Une vidéo pour vous aider :