Aller au contenu

TP - Utiliser une interface de Liste☘

Dans le dossier [NSI], créez le dossier [A02-Listes].

Téléchargez le module TAD_Listes.py qui contient une implémentation de liste et placez ce module dans le dossier [A02-Listes].
L'interface est celle donnée dans le cours :

Méthode/Opérations Description
L = Liste() Initialisation d'une liste vide
est_vide(L) Renvoie True si la liste L est vide, False sinon.
inserer_en_tete(elt, L) « Ajoute » un nouvel élément en tête de la liste,
c'est-à-dire renvoie le couple (elt, L)
tete(L) Renvoie la valeur de l'élément en tête (le premier élément du couple)
queue(L) Renvoie la liste située en queue (le second élément du couple)

Attention

Cette interface n'est pas orientée objet, elle s'utilise de la même manière que dans les exemples du cours et dans le TD.

Préambule☘

Ce TP a pour but de vous faire définir des fonctions (opérations) récursives et usuelles sur la structure de données « Liste ».

Téléchargez le fichier « à trous » TPA02.11.py (clic droit -> [Enregistrer sous]) et enregistrez-le dans ce dossier.

Important

  1. Dans chaque fonction à programmer, remplacez le mot-clef pass par les instructions nécessaires.
  2. Pour gagner du temps, on ne lèvera pas les erreurs sur les types de données entrées par l'utilisateur. On considèrera que si la spécification indique un type int, alors ce sera bien un type int qui sera saisi.

Remplir rapidement☘

Complétez la définition (récursive ou non, c'est vous qui choisissez) de la fonction tab_to_liste() qui prend en paramètre un tableau (type list en Python) et qui renvoie une liste de ses éléments dans le même ordre.

1
2
3
4
5
def tab_to_liste(tab):
    """
    tab - list
    Sortie: Liste - Liste constituée des mêmes éléments que tab, dans le même ordre
    """

Plan de test

>>> L1 = tab_to_liste([5, 2, 1, 4, 3])

>>> L1
(5, (2, (1, (4, (3, ())))))

>>> from random import randint

>>> L2 = tab_to_liste([randint(1, 20) for _ in range(10)])

>>> L2
(7, (19, (5, (6, (5, (17, (17, (3, (16, (9, ()))))))))))

Nombre d'éléments☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction taille() qui prend en paramètre une liste et qui renvoie le nombre d'éléments de cette liste.

1
2
3
4
5
def taille(lst):
    """
    lst - Liste
    Sortie: int - Nombre d'éléments de lst
    """

Plan de test

>>> taille(L1)
5

>>> taille(L2)
10

Somme des éléments☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction somme() qui prend en paramètre une liste d'entiers et qui renvoie la somme des éléments de cette liste.

1
2
3
4
5
def somme(lst):
    """
    lst - Liste d'entiers
    Sortie: int - Somme des éléments de lst
    """

Plan de test

>>> somme(L1)
15

>>> somme(L2)
104

Plus grand élément☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction maximum() qui prend en paramètre une liste non vide d'entiers et qui renvoie le plus grand des éléments de cette liste.

Il faudra lever une erreur si la liste est vide.

1
2
3
4
5
def maximum(lst):
    """
    lst - Liste non vide d'entiers
    Sortie: int - Plus grand des éléments de lst
    """

Plan de test

>>> maximum(L1)
5

>>> maximum(L2)
19

>>> maximum(Liste())
AssertionError: La liste est vide

Appartenance☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction appartient() qui prend en paramètre une liste d'éléments et un élément de même type et qui renvoie True si cet élément fait partie de la liste.

1
2
3
4
5
6
def appartient(val, lst):
    """
    val - Un élément de même type que les éléments de lst
    lst - Liste d'éléments
    Sortie: bool - True si val appartient à lst, False sinon
    """

Plan de test

>>> appartient(4, L1)
True

>>> appartient(15, L2)
False

N-ième élément☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction element_indice() qui prend en paramètre un entier k et une liste d'éléments et qui renvoie l'élément d'indice k (s'il existe - on numérote à partir de 0) de la liste.

Il faudra lever une erreur si l'indice est trop élevé.

1
2
3
4
5
6
def element_indice(k, lst):
    """
    k - entier strictement positif tel que 0 <= k < taille(lst)
    lst - Liste d'éléments
    Sortie: elt - Élément de lst ayant pour indice k
    """

Plan de test

>>> element_indice(3, L1)
4

>>> element_indice(8, L2)
16

>>> element_indice(5, L1)
AssertionError: Indice trop élevé

Supprimer un élément☘

Complétez la définition récursive (ici, vous n'avez pas le choix !) de la fonction supprimer_elt_indice() qui prend en paramètre un entier k et une liste d'éléments et qui supprime l'élément d'indice k (s'il existe - on numérote à partir de 0) de la liste.

Il faudra lever une erreur si l'indice est trop élevé.

1
2
3
4
5
6
def supprimer_elt_indice(k, lst):
    """
    k - entier strictement positif tel que 0 <= k < taille(lst)
    lst - Liste d'éléments
    Sortie: Liste - La liste lst dans laquelle l'élément d'indice k est supprimé
    """

Plan de test

>>> L1 = supprimer_elt_indice(3, L1)

>>> L1
(5, (2, (1, (3, ()))))

>>> L2 = supprimer_elt_indice(6, L2)

>>> L2
(7, (19, (5, (6, (5, (17, (3, (16, (9, ())))))))))

>>> L1 = supprimer_elt_indice(5, L1)
AssertionError: Indice trop élevé