Structures de données¶
Liste¶
Une liste est une séquence, c’est-à-dire un conteneur d’objets rangés dans un ordre précis. Il est possible de créer une liste d’objets de tout type. Pour définir une liste d’objets, il suffit de les séparer par une virgule et d’encadrer par des crochets.
Voici par exemple une liste contenant des nombres entiers, placée dans une variable (c.a.d. un nom qui permet de retrouver cette liste).
>>> L1 = [1,5,0,2,9]
>>> type(L1)
<class 'list'>
Les éléments de la liste peuvent être de types différents :
>>> L2 = [1,2.5,[1,2],"mot"]
Les listes peuvent ainsi être utilisées pour construire des structures de données beaucoup plus complexe, par exemple une matrice de trois colonnes et deux lignes peut être représentée par la liste suivante :
>>> M = [[1,0,2],[0,-3,1]]
Le premier élément de cette liste est une liste, qui définit la première ligne de la matrice. Le second élément définit la seconde ligne de la matrice.
L’opérateur + permet de concaténer deux listes :
>>> L1 + L2
[1, 5, 0, 2, 9, 1, 2.5, [1, 2], 'mot']
L’opérateur * permet de concaténer une liste avec elle-même :
>>> L1*3
[1, 5, 0, 2, 9, 1, 5, 0, 2, 9, 1, 5, 0, 2, 9]
La fonction len permet d’obtenir la longueur d’une liste (sous la forme d’un nombre entier) :
>>> len(L1)
5
L’accès à un élément quelconque d’une liste se fait au moyen d’un indice. Par convention, la valeur de l’indice du premier élément est 0, celle du dernier élément est donc la longueur de la liste moins 1.
>>> L1[0] # élément d'indice 0
1
>>> L1[4]
9
Si l’indice est trop grand, une erreur est déclenchée :
>>> L1[5]
Traceback (most recent call last):
File "<pyshell#282>", line 1, in <module>
L1[5]
IndexError: list index out of range
Cependant, un indice négatif ne déclenche par une erreur mais permet d’accéder à un élément en comptant à partir du dernier :
>>> L1[-3]
0
Les listes ont la particularité d’être des objets mutables, ce qui signifie qu’un élément d’une liste peut être changé sans que la liste elle-même soit recréée :
>>> L1[4] = 10
>>> L1
[1, 5, 0, 2, 10]
La variable nommée L1 fait toujours référence à la même liste, c’est-à-dire au même objet stocké en mémoire, mais l’élément d’indice 4 de cette liste a été changé. Le caractère mutable d’une liste est très important puisqu’il évite de recréer la liste à chaque changement, ce qui serait très inefficace lorsque la liste est très grande.
Voici une conséquence de cette propriété qu’il est important de connaître :
>>> a = L1
>>> L1[0] = -5
>>> a
[-5, 5, 0, 2, 10]
La variable a contient une référence à la même liste que celle référencée par la variable L1. Ainsi, si on modifie cette liste via L1, le résultat est visible via a.
Si on veut créer une nouvelle liste qui soit une copie d’une autre liste, on procède comme ceci :
>>> b = list(L1)
>>> L1[0] = 0
>>> b
[-5, 5, 0, 2, 10]
Dans ce cas, les variables b et L1 font référence à deux listes différentes.
Il est possible d’ajouter un élément à une liste :
>>> L1.append(7)
>>> L1
[0, 5, 0, 2, 10, 7]
ou bien d’enlever le dernier élément tout en le récupérant :
>>> L1.pop()
7
Ces deux dernières fonctions font de la liste un moyen de réaliser une pile. On remarque au passage la syntaxe particulière d’une fonction attachée à un objet, qui permet de modifier les propriétés d’un objet mutable.
Pour accéder à une partie d’une liste, on utilise une tranche. Voici comment créer une tranche :
>>> tranche = slice(0,4,1) # premier indice = 0, dernier indice = 4-1, incrément de l'indice = 1
et voici comment l’utiliser pour extraire de la liste précédente les éléments d’indice 0 à 3 :
>>> L1[tranche]
[0, 5, 0, 2]
Il existe une syntaxe simplifiée qui permet de définir directement la tranche entre les crochets :
>>> L1[0:3:1]
[0, 5, 0]
La dernière valeur, qui indique l’incrément de l’indice, est facultative car sa valeur par défaut est 1 :
>>> L1[0:3]
[0, 5, 0]
Lorsqu’on omet la première valeur, elle vaut 0 :
>>> L1[:3] # 3 premiers éléments de la liste
[0, 5, 0]
Lorsqu’on omet la deuxième valeur, elle vaut la longueur de la liste :
>>> L1[2:] # tous les éléments à partir de celui d'indice 2
[0, 2, 10, 7]
Voici comment obtenir la liste des éléments d’indices pairs :
>>> L1[::2]
[0, 0, 10]
Si on veut créer une liste dont tous les éléments ont (initialement) la même valeur, on utilise l’opérateur * déjà mentionné plus haut :
>>> L = [0]*10 # liste de 10 entiers nuls
Il est fréquent qu’on ait besoin d’une liste contenant des nombres entiers en progression arithmétique. L’objet range permet de l’obtenir. Pour construire un objet de ce type, on écrit :
range(start,stop,step)
Le paramètre start indique la première valeur, stop indique la valeur qu’il ne faut pas dépasser et step est l’incrément (la raison de la suite). L’incrément peut être omis et dans ce cas la valeur 1 est utilisée. L’argument start peut être omis, auquel cas la valeur 0 est utilisée. Voici deux exemples :
>>> list(range(1,10,1))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(-1,-10,-1))
[-1, -2, -3, -4, -5, -6, -7, -8, -9]
Comme indiqué, la valeur de stop n’est pas atteinte. Voici une des raisons de ce choix a priori étrange :
>>> list(range(1,10,1))+list(range(10,20,1))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
La valeur stop de la première liste est égale à la valeur start de la seconde.
N-uplets¶
Les n-uplets (tuples en anglais) sont, tout comme les listes, des séquences. Contrairement aux listes, ils ne sont pas mutables. Voici comment créer un n-uplet :
>>> x = (1,3,0)
>>> type(x)
<class 'tuple'>
On peut accéder à un élément par son indice :
>>> x[0]
1
mais il est impossible de modifier un élément :
>>> x[0] = 2
Traceback (most recent call last):
File "<pyshell#308>", line 1, in <module>
x[0] = 2
TypeError: 'tuple' object does not support item assignment
Pour définir un n-uplet, les parenthèses sont parfois facultatives :
>>> y = 1,2
mais elles sont bien sûr indispensables dans l’exemple suivant (liste de deux n-uplets) :
>>> L = [(0,1),(0,2)]
Les n-uplets permettent de regrouper des objets différents. Il permettent aussi de faire des affectations multiples :
>>> a,b = 2,3
et d’échanger facilement le contenu de deux variables :
>>> a,b = b,a
>>> a
3
>>> b
2
Dans ce cas, un n-uplet est créé à partir des nombres entiers référencés par les variables a et b, puis ce n-uplet est utilisé pour définir les variables a et b.
Si on est amené à modifier un n-uplet, alors il est préférable de le remplacer par une liste, mais on peut toujours le faire en le convertissant en liste :
>>> x=(1,3,0)
>>> L=list(x)
>>> L[0]=-1
>>> x=tuple(L)
>>> x
(-1, 3, 0)
Dictionnaires¶
Le dictionnaire est une structure de données qui contient des paires clé-valeur. La clé est un entier, un flottant ou une chaîne de caractères. La valeur est un objet de type quelconque.
Voici comment créer un dictionnaire pour stocker des constantes physiques. Les clés sont des chaînes de caractères, les valeurs sont des flottants.
>>> constantes={'e':1.6e-19,'h':6.62e-34}
>>> type(constantes)
<class 'dict'>
Pour accéder à une valeur par sa clé, on utilise la notation crochets (comme pour les listes) :
>>> D=constantes['e']
1.6e-19
Les dictionnaires sont des objets mutables. On peut non seulement modifier une valeur mais aussi ajouter une paire clé-valeur :
>>> constantes['c'] = 3.00e8
>>> constantes
{'e': 1.6e-19, 'h': 6.62e-34, 'c': 300000000.0}
Il faut remarquer qu’un dictionnaire n’est pas une séquence, c’est-à-dire que l’ordre des éléments (qui est l’ordre de leur introduction dans le dictionnaire) n’a pas de signification.