Structures de données

Cette approche des listes, vue l'an dernier en première, est bien sur à réviser avant de commencer !

Une liste est une structure permettant de regrouper des données et d'y accéder de façon séquentielle.
Les éléments de la liste sont ordonnés et leur place, leur rang (index) est très important .
Une liste peut évoluer : On peut lui ajourter ou retirer des données

Ci dessous des liens vers des vidéos permettant d'asseoir les connaissances :

* D'abord l'essentiel à connaitre sur les listes
* Comprendre les 2 méthodes pour parcourir une liste
* Utiliser les listes en compréhension

Une liste L est composée de 2 parties : sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste, et sa queue (souvent noté cdr) qui correspond au reste de la liste. 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"). Voici les opérations qui peuvent être effectuées sur une liste :

• créer une liste vide                                                          (L=vide() on a créé une liste L vide)
• tester si une liste est vide                                                   (estVide(L) renvoie vrai si la liste L est vide)
• ajouter un élément en tête de liste                                     (ajouteEnTete (x,L) avec L une liste et x l'élément à ajouter)
• supprimer la tête x d'une liste L et renvoyer cette tête x         (supprEnTete(L))
• Compter le nombre d'éléments présents dans une liste         (compte(L) renvoie le nombre d'éléments présents dans la liste L)
• rechercher un élément dans une liste                              (recherche(e,L) renvoie l'index de l'élement recherché)
• lire un élément dans une liste                                            (lire(i,L) renvoie l'objet se trouvant à l'index i)

La fonction cons permet d'obtenir une nouvelle liste à partir d'une liste et d'un élément (L1 = cons(x,L)). Il est possible "d'enchaîner" les cons et d'obtenir ce genre de structure : cons(x, cons(y, cons(z,L)))

Exemples :

Voici une série d'instructions (les instructions ci-dessous s'enchaînent):

• L=vide() => on a créé une liste vide
• estVide(L) => renvoie vrai
• ajoutEnTete(3,L) => La liste L contient maintenant l'élément 3
• estVide(L) => renvoie faux
• ajoutEnTete(5,L) => la tête de la liste L correspond à 5, la queue contient l'élément 3
• ajoutEnTete(8,L) => la tête de la liste L correspond à 8, la queue contient les éléments 3 et 5
• t = supprEnTete(L) => la variable t vaut 8, la tête de L correspond à 5 et la queue contient l'élément 3
• L1 = vide()
• L2 = cons(8, cons(5, cons(3, L1))) => La tête de L2 correspond à 8 et la queue contient les éléments 3 et 5

Exercice 1

Voici une série d'instructions qui s'enchaînent, expliquez ce qui se passe à chacune des étapes :

• L = vide()
• ajoutEnTete(10,L)
• ajoutEnTete(9,L)
• ajoutEnTete(7,L)
• L1 = vide()
• L2 = cons(5, cons(4, cons(3, cons (2, cons(1, cons(0,L1))))))
• lire (3,L2)
• rechercher (5,L2)

En python

Vous avez ici une page qui parle des listes
Attention , en python, le type "liste" se présente sous forme d'un tableau dynamique ou sous forme d'une liste chainée.
Pour concevoir une liste L =[0...n], on utilise par exemple un tableau de (n+1) éléments :
Si (L[0]== 0), la liste est vide et on augmente L[0] d'une unité à chaque fois qu'on insère un élément dans cette liste.
Si (L[0]== n+1), la liste est pleine et on diminue L[0] d'une unité à chaque fois qu'on enlève un élément dans cette liste.
Pour implémenter une liste en python, on peut utiliser un code comme celui-ci :

Exercice 2