T - 4.1 Listes

introduction

Exemple d'implémentation en Python du type LISTE

Les listes

Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers langages de programmation à introduire cette notion de liste (Lisp signifie "list processing").


On trouve différentes définitions du type abstrait liste.

Dans ce cours, nous définirons une liste comme une structure de donnée permettant de regrouper des données. C'est une structure linéaire qu'on ne peut parcourir qu'en partant du début. Elle est définie par son interface, c'est à dire l'ensemble des fonctions (méthodes), appelées des primitives qui vont permettre de creer et gérer la liste.

Il y a de nombreuses possibilités pour implémenter ce type abstrait, et vous n'avez pas besoin de connaître cette implémentation. Il vous suffit de connaître les spécifications des fonctions primitives, pour pouvoir les utiliser et éventuellement écrire d'autres fonctions.


Attention : ce que nous appelons listes dans ce chapitre n'est pas la même chose que les listes que vous connaissez en python. Il s'agit ici de types abstraits qui n'existent pas nécessairement de façon native dans tous les langages, mais peuvent être implémentés.


 Le type abstrait liste est différent du type list. Nous le noterons dans ce cours, pour bien le différencier, en majuscules : LISTE.

Pour résumé, une LISTE est composée de :

  • sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste (en tête de liste)
  • et sa queue (souvent noté cdr) qui correspond au reste de la liste.

Écriture d'une liste

La manière dont sont affichées les listes dépend de leur implémentation. Dans ce qui suit nous avons choisi un affichage qui ressemble à celui du type list de python :

  • Une liste vide s'écrit []
  • Exemple de liste : [1, 2, 3]


Comprendre le fonctionnement des primitives
:
lisez attentivement les spécifications de chaque primitive, car elles vous permettront de comprendre leur fonctionnement.
Exercice de code : Que font les primitives ?
Vous disposez des fonctions "primitives" suivantes :
  • Vide():
  • Liste(x, liste):
  • est_vide(liste):
  • tete(liste):
  • queue(liste) :
Pour connaître les spécifications, vous pouvez utiliser la fonction help(). Regardez les toutes et notez bien ces spécifications, vous allez les utiliser ensuite.

A vous d'utiliser les primitives
:
Exercice de code : essais à faire pour chacune des primitives
Vous devez compléter le code pour effectuer :
  • afficher pour list1 True ou False selon que lst1 est vide ou pas
  • créer une LISTE lst2 en ajoutant 2 en tête de lst1 et afficher lst2
  • puis afficher si lst2 est vide ou pas
  • ajouter 3 en tête de list2 et afficher list2
  • retirer 3 en tête de list2 et afficher list2

Dans quel ordre implémenter la liste ?
:
Exercice mêlé : créer la liste ['a', 'b', 'c']
mettre les lignes dans le bon ordre pour obtenir la liste demandée
(vous pouvez déplacer les lignes du code)
  • lst_exemple = Vide()
  • lst_exemple = Liste('a', lst_exemple)
  • lst_exemple = Liste('c', lst_exemple)
  • lst_exemple = Liste('b', lst_exemple)
  • print(lst_exemple)


Exemple : On peut imbriquer ces fonctions comme dans l'exemple suivant :


A vous maintenant !

Exercice de code : créer la liste ['a','b','c'] en utilisant l'imbrication

Autres fonctions

On peut maintenant construire toutes les fonctions qui nous viennent à l'esprit.
Voici quatre exercices à réaliser ci-dessous, pour implémenter de nouvelles fonctions.
Pour chacun de ces exercices, vous ne pouvez utiliser que les fonctions "primitives" définies précédemment, ou une fonction que vous avez vous-même implémentée dans un des exercices ci-dessous.
Vous ne devez donc pas utiliser les instructions usuelles en python pour le type list, notamment accéder un élément avec ma_liste[0] par exemple.

Pour la réalisation des différentes fonctions, vous n'avez pas le droit d'utiliser len, append et []
exercice 1 :
Exercice de code : Compléter cette fonction qui doit renvoyer la longueur de la liste, sans utiliser de fonction récursive.

exercice 2
Exercice de code : Compléter cette fonction qui doit renvoyer la longueur de la liste, en utilisant une fonction récursive.

exercice 3
Exercice de code : Compléter cette fonction qui enlève la tête de la liste

exercice 4
Exercice de code : Compléter cette fonction qui doit permettre de savoir si un élément x est dans la liste. Vous ne pouvez utiliser ni len, ni for, ni while, ni in


exercice 5
Dans cet exercice, vous ne pouvez utiliser ni len, ni for, ni while, ni in
Exercice de code : Compléter cette fonction qui doit retourner élément de rang n.
Votre fonction doit renvoyer la chaine de caractères "n hors limite" si n n'est le rang d'aucun élément de la liste