Structure linéaire de données : Liste¶
En informatique on manipule essentiellement des données.
Une structure de données est une organisation logique des données permettant de simplifier ou d'accélérer leur traitement.
Du déjà vu :¶
Les types simples :¶
Pour des données simples comme des nombres, des chaînes de caractères ou des booléens, on peut les stocker dans des variables qui seront typées en fonction de la nature de la donnée : int, float, str, bool.
maPremiereVariable = 'Hello World!'
maPremiereVariable, type(maPremiereVariable)
maSecondeVariable = -5
maSecondeVariable, type(maSecondeVariable)
maTroisiemeVariable = 5.0
maTroisiemeVariable, type(maTroisiemeVariable)
maQuatriemeVariable = ( 0 == 1 )
maQuatriemeVariable, type(maQuatriemeVariable)
Les types construits :¶
Lorsque l’on a besoin de manipuler un grand nombre de données, qu’elles soient de même type ou pas, on utilise des structures de données comme les tuples, les listes, les tableaux ou les dictionnaires : tuple,list, dict.
monTuple=(3.14, "cours NSI", True, 5)
monTuple, monTuple[1], type(monTuple)
maListe=[3.14, "cours NSI", True, 5]
maListe, maListe[1], type(maListe)
monDictionnaire = {'zero':0, 'un':1, 'deux':2,'trois':3}
monDictionnaire, monDictionnaire['zero'], type(monDictionnaire)
monTableau = [[1,2,3,4],["toto","titi","tata"], [-3.14, 0.5, 1, 2.35, 6.48]]
monTableau, monTableau[1][0], type(monTableau)
Les chaînes de caractères, les tuples et les listes sont des séquences, c’est à dire des suites ordonnées d’éléments indexés par une suite d’entiers.
Avec :
- Chaînes de caractères et tuples sont non mutables (on ne peut les modifier)
- Les listes sont mutables
- Un tableau est une liste de liste
- Tuples et listes peuvent contenir des éléments de n’importe quel type, y compris d’autres tuples, listes ou encore des dictionnaires...
- Chacun de ces types dits construits possède un certain nombre de méthodes qui permettent d’agir sur l’objet (ajout, suppression, tris etc...)
- Dans un dictionnaire les éléments sont indexés par des clés et sont modifiables.
Type abstrait de donnée (TAD) :¶
Une structure de données est donc une manière de stocker, d'accéder à, et de manipuler des données.
L'interface de la structure de données décrit de quelle manière on peut la manipuler, comme append pour le type list.
L'implémentation de la structure de données, contient, quant à elle, le code de ces méthodes (comment fait Python). Il n'est pas nécessaire de connaitre l'implémentation pour manipuler la structure de données.
Un type abstrait décrit essentiellement une interface, indépendamment du langage de programmation.
Les listes (les vraies !) :¶
La structure de liste est assez facile à imaginer comme une suite d'éléments ordonnés par leurs indices.
$$a_0 , a_1 , a_2 , ... , a_n$$Dans cette partie on s'intéresse aux listes d'un point de vue "structure de données", celles que les informaticiens appellent vraiment des listes et non pas aux listes Python qui sont une implémentation spécifique à Python de la notion de liste.
Définition :¶
Une liste est une structure de données permettant de regrouper des données.
Elle est composée de 2 parties :
- sa tête notée "car" (pour : contents of address register), qui correspond au dernier élément ajouté à la liste.
- sa queue notée "cdr" (pour : contents of decrement register), 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 (souvent notée nil)
- tester si une liste est vide
- ajouter un élément en tête de liste
- supprimer la tête d’une liste et renvoyer cette tête
- compter le nombre d’éléments présents dans une liste
- un constructeur, historiquement appelé "cons", qui 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)))
Voici la représentation schématique d’une liste comportant, dans cet ordre, les trois éléments 1, 2 et 4.
La liste est constituée de trois cellules, représentées ici par des rectangles.
Chaque cellule possède une première partie, nommée "car" , qui contient l’entier correspondant, et d’une deuxième partie, nommée "cdr" , qui contient un lien vers la cellule suivante.
On a donc affaire à une chaîne de cellules, ce qui justifie la dénomination courante de liste chaînée.
Le champ "cdr" de la dernière cellule renvoie vers une liste vide, conventionnellement représentée par un hachurage.
On aura noté que le premier champ d’une cellule contient ici un entier (car on considère une liste d’entiers) alors que le deuxième est une liste, c’est-à-dire un lien vers une autre cellule.
Nous avons défini les contours de la structure de liste. Celle-ci est un concept ("une vue de l’esprit") de ce qu’est une liste.
On dit que c’est un un type abstrait de données, TAD.
Pour implémenter cette structure il faudra, quelque soit le langage utilisé, que l’implémentation permette de retrouver les fonctions qui ont été définies pour le type abstrait.
def vide():
return None
def cons(x,L):
return(x,L)
def ajouteEnTete(L,x):
return cons(x,L)
def supprEnTete(L):
return (L[0],L[1])
def estVide(L):
return L is None
def compte(L):
if estVide(L):
return 0
return 1 + compte(L[1])
A faire vous même n°1 :
Vérifier le bon fonctionnement de cette implémentation en exécutant ces instructions:
- nil = vide()
- afficher estVide(nil)
- L = cons(5, cons(4, cons(3, cons(2, cons(1, cons(0,nil))))))
- afficher estVide(L)
- afficher compte(L)
- L = ajouteEnTete(L,6)
- afficher compte(L)
- x, L=supprEnTete(L)
- afficher x
- afficher compte(L)
- x, L=supprEnTete(L)
- afficher x
- afficher compte(L)
Version 2 :¶
Cette fois-ci on utilise deux classes :
La classe Cellule qui crée un objet (instance) cellule avec les attributs "car" et "cdr"
class Cellule:
def __init__(self, tete, queue):
self.car = tete
self.cdr = queue
La classe Liste dont les instances (objets) seront de type Cellule, avec quelques méthodes :
class Liste:
def __init__(self, c):
self.cellule = c
def estVide(self):
return self.cellule is None
def car(self):
assert not(self.cellule is None), "Liste vide"
return self.cellule.car
def cdr(self):
assert not(self.cellule is None), "Liste vide"
return self.cellule.cdr
La fonction "cons" qui permet de construire la liste :
def cons(tete, queue):
return Liste(Cellule(tete, queue))
Ainsi pour créer une la liste L = [5, 4, 3, 2, 1, 0], il suffit d’exécuter les instructions :
nil=Liste(None)
L = cons(5, cons(4, cons(3, cons(2, cons(1, cons(0,nil))))))
A faire vous même n°2 :
Tester les instructions suivantes :
print(L.estVide())
print(L.car())
print(L.cdr().car())
print(L.cdr().cdr().car())
et écrire l’instruction qui permet d’afficher le dernier élément de la liste.
A faire vous même n°3 :
Ajouter les fonctions suivantes :
def longueurListe(L):
n = 0
while not(L.estVide()):
n += 1
L = L.cdr()
return n
def listeElements(L):
t = []
while not(L.estVide()):
t.append(L.car())
L = L.cdr()
return t
Que font-elles ?
...
A faire vous même n°4 :
Que produit l’instruction :
L = cons(6,L)
? ...
A faire vous même n°5 :
Écrire une fonction ajouteEnTete qui prend en paramètre une liste et un nombre et qui renvoie une liste dans laquelle le nombre a été ajouté en entête.
A faire vous même n°6 :
Que produisent les instructions :
x = L.car()
L = cons(L.cdr().car(),L.cdr().cdr())
? ...
A faire vous même n°5 :
Écrire une fonction supprEnTete qui prend en paramètre une liste et qui retourne son entête et la liste amputée de l’entête.
Références aux programmes :¶
Structures de données
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Listes, piles, files : structures linéaires. Dictionnaires, index et clé. |
Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire. |
On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files. |
Ce document, basé sur le travail de Stephan VAN ZUIJLEN, est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.
Pour toute question, suggestion ou commentaire : eric.madec@ecmorlaix.fr