Chap. 09 — Structures de données, les séquences 1 : listes et tuples

Les séquences

Présentation

Les séquences forment un groupe de structures de données au sein desquelles les éléments sont ordonnés séquentiellement et sont accessibles via des indices.

On appelle ce groupe séquences car, d'un point de vue logique, les structures qui le composent sont « des suites » d'éléments. Par exemple, une chaîne de caractères est une séquence de caractères : le premier caractère de la chaîne "Bonjour" est le 'B', le deuxième le 'o', le troisième 'n', etc.

Toutes les séquences possèdent des caractéristiques, des opérateurs en commun. De même, certaines fonctions natives du langage Python agissent de la même façon sur toutes les séquences. Dans cette partie, nous allons donc essayer de faire émerger tout ce qui est commun à toutes les séquences.

Remarque. Dans toute cette section, les séquences seront repérées par le mot générique seq. Nous adapterons ce mot, par la suite, en fonction de la structure (chaîne de caractères, liste, tuple).

Modèle d'accès aux séquences

Les types séquentiels partagent tous le même modèle d'accès : ce sont des structures ordonnées au sein desquelles on accède aux éléments à partir d'indices.

Le schéma ci-dessous illustre le mode de stockage et d'accès aux éléments d'une séquence. $N$ est la longueur de la séquence ; les indices varient donc de 0 à $N-1$.

En Python,

• $N$ peut être obtenu à l'aide de la fonction len : N = len(seq);
• Les indices, dans une séquence, ont pour première valeur 0 et finissent à une valeur égale à la longueur de la séquence moins un : $N-1$.
• Les indices négatifs sont des raccourcis : $-1$ signifie en fait len(seq) - 1, $-2$ remplace est donc égal à len(seq) - 2, etc. Dans un premier temps je vous déconseille d'utiliser les indices négatifs.

Opérateurs des types séquentiels

Concaténation

• L'expression résultante est une nouvelle séquence, on ne modifie ni la séquence seq1, ni la séquence seq2.

• C'est la méthode la plus simple, d'un point de vue conceptuel, pour associer deux séquences mais ce n'est ni la plus rapide, ni la plus efficace.

  • Pour une chaîne de caractères, transformer toutes les sous-chaînes en listes à l'aide de la fonction list et utiliser la méthode join occupe moins de place en mémoire.
  • Pour deux listes, la méthode extend est préférable à la concaténation.

Répétition

• L'expression résultante est une nouvelle séquence, on ne modifie pas la séquence initiale.

Appartenance

• Les opérateurs in et not in sont booléens : ils retournent True si l'appartenance est confirmée, False sinon.

Découpage

Attention ! Cette partie est Hors-Programme, elle n'est ici présente qu'à titre documentaire. Vous pourrez utiliser ces notions dans vos programmes mais elles ne feront jamais parti des contrôles.

• Les opérateurs [], [:] permettent d'accéder à un ou plusieurs éléments d'une séquence. Ils ne modifient pas la séquence mais fournissent des « vues » de cette dernière.

• Exemples d'utilisation sur une séquence de 6 éléments :

  • Accès au quatrième élément : seq[3]
  • Accès au dernier élément : seq[5] ou seq[len(seq) - 1] ou seq[-1]. Les deux dernières expressions ne nécessitent pas de déterminer « à la main » la valeur du dernier indice.
  • Accès aux deuxième, troisième et quatrième éléments : seq[1:4]
  • Accès aux deux premiers éléments : seq[0:2] ou seq[:2]
  • Accès aux trois derniers éléments : seq[3:] ou seq[-3:]. La dernière expression est plus générale puisqu'il n'est pas nécessaire de connaître (ou déterminer) la longueur de la séquence.
  • Accès à tous les éléments de la séquence : eq[:]. Cette expression permet aussi de copier une séquence.

Fonctions intégrées du language Python qui agissent sur les séquences

Conversion de types

Les fonctions list, str et tuple permettent de convertir n'importe quel type séquentiel en un autre.

Fonctions opérant sur les types séquentiels

Parcours des séquences

La boucle Pour chaque (instruction for) parcourt les éléments d'une séquence et se termine quand tous les éléments sont épuisés. Sa syntax est :

for élément in séquence:
 suite_d_instructions_à_exécuter

Parcours en utilisant directement les éléments

xxxxxxxxxx
liste_de_noms = ['Patrick', 'Sylvie', 'Suzanne']
for nom in liste_de_noms:
    print(nom)

Parcours en utilisant les indices

​x
""" Avec une boucle for """
​
liste_de_noms = ['Patrick', 'Sylvie', 'Suzanne']
for i in range(len(liste_de_noms)):
    print(liste_de_noms[i])

xxxxxxxxxx
""" Avec une boucle while """
​
liste_de_noms = ['Patrick', 'Sylvie', 'Suzanne']
i = 0
while i < len(liste_de_noms):
    print(liste_de_noms[i])
    i += 1

Remarque. Le parcours par élément est plus performant en Python que le parcours par indice.

Parcours en utilisant les indices et les éléments

On prend très vite l'habitude d'utiliser le parcours par élément, lorsqu'on souhaite extraire les éléments d'une séquence. Il est cependant parfois utile de récupérer en même temps l'indice de l'élément. La fonction intégrée enumerate permet de réaliser ces deux opérations en une seule instruction :

xxxxxxxxxx
""" Avec une boucle enumerate """
​
liste_de_noms = ['Patrick', 'Sylvie', 'Suzanne']
for i, element in enumerate(liste_de_noms):
    print("{} en position {} dans la liste".format(element, i + 1))

Les listes

Présentation

Les listes sont des objets conteneurs pouvant contenir un nombre arbitraire et modifiable d'objets Python différents.

Premières manipulations

Comment créer et affecter une liste à une variable ?

L'opération est identique à celle de l'affection d'un littéral entier à une variable : création de la liste et affectation de l'objet nouvellement créé à une variable.

xxxxxxxxxx
>>> une_liste = [1123, 'abc', 4.56, ['liste', 'interne']]
>>> une_liste_vide = []
>>> une_autre_liste = list('chaine')
>>> print(une_liste)
[1123, 'abc', 4.56, ['liste', 'interne']]
>>> print(une_liste_vide)
[]
>>> print(une_autre_liste)
['c', 'h', 'a', 'i', 'n', 'e']

Comment accéder aux données stockées dans une liste ?

Le découpage fonctionne comme pour toutes les séquences, on utilise l'opérateur de découpage [] avec le ou les indices.

xxxxxxxxxx
>>> une_liste[0]
1123
>>> une_liste[1:3]
['abc', 4.56]
>>> une_liste[3][1]
'interne'
>>> une_liste[:3]
[1123, 'abc', 4.56]

Remarque. On rappelle que les tranches ne sont pas au programme : les instructions une_liste[1:3] et une_liste[:3] sont donc présentes à titre documentaire.

Comment modifier une liste ?

On modifie un ou plusieurs éléments d'une liste en spécifiant une « tranche » à gauche de l'opérateur d'affectation= et la ou les nouveaux objets à droite de cet opérateur.

xxxxxxxxxx
>>> une_liste
[1123, 'abc', 4.56, ['liste', 'interne']]
>>> une_liste[2] = 'remplace float'
>>> une_liste
[1123, 'abc', 'remplace float', ['liste', 'interne']]
>>> une_liste[0:2] = ['remplace int', 'remplace string']
>>> une_liste
['remplace int', 'remplace string', 'remplace float', ['liste', 'interne']]

Remarque. On rappelle que les tranches ne sont pas au programme : l'instruction une_liste[0:2] = ['remplace int', 'remplace string'] est donc présente à titre documentaire.

Attention ! Les listes étant des structures modifiables, il est souvent préférable d'utiliser l'une des nombreuses méthodes décrites à la section 2.3.

Action des opérateurs des types séquentiels sur les listes

Tous les opérateurs des types séquentiels présentés dans la première section de ce chapitre s'appliquent aux listes.

xxxxxxxxxx
>>> une_liste = [1123, 'abc', 4.56, ['liste', 'interne']]
>>> 1123 in une_liste
True
>>> 2 in une_liste
False
>>> a = [10, 11, 12]
>>> b = [13, 14]
>>> a + b
[10, 11, 12, 13, 14]
>>> a 
[10, 11, 12]
>>> a += b
>>> a
[10, 11, 12, 13, 14]

Attention ! a + b n'est pas équivalent à a += b comme on peut le voir dans l'exemple précédent. La première instruction crée une nouvelle liste alors que la seconde modifie la liste référencée par la variable à gauche de l'opérateur d'affectation. En fait, a += b est équivalent à a.extend(b).

Action des fonctions intégrées du language Python sur les listes

Toutes les fonctions des types séquentiels présentées dans la première section de ce chapitre s'appliquent aux listes.

xxxxxxxxxx
>>> liste = [1, 2, 4, 8, 16, 32]
>>> len(liste)
6                       # nombre d'élements dans la liste
>>> max(liste)
32                      # plus grand élément de la liste
>>> min(liste)
1                       # plus petit élément de la liste
>>> sum(liste)
63                      # somme des éléments de la lsite

Quelques méthodes spécifiques aux listes

Présentation

Les listes, en Python, possèdent des méthodes. Une méthode, concept de la programmation objet, peut être considérée comme une fonction (ou une procédure) s'appliquant à un objet spécifique. Les méthodes décrites dans cette section se comportent donc exactement comme des fonctions intégrées qui n'opéreraient que sur des listes.

Comment accéder à la liste de ces méthodes ?

xxxxxxxxxx
>>> liste = [1, 2, 3, 4]
>>> dir(liste)
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

Liste des méthodes

xxxxxxxxxx
>>> music_media = [45]
>>> music_media.insert(0, 'CD')
>>> music_media
['CD', 45]
>>> music_media.append('33 tours')
>>> music_media.insert(2, 'bande 8 pistes')
>>> music_media
['CD', 45, 'bande 8 pistes', '33 tours']
>>> 'cassette' in music_media
False
>>> 'CD' in music_media
True
>>> music_media.index(45)
1
>>> music_media.index('bande 8 pistes')
2

Les méthodes des objets modifiables qui modifient l'objet n'ont pas de valeur de retour.

Attention !!! Une erreur courante consiste à écrire : music_media = music_media.sort(). L'instruction music_media référence alors l'objet None, car la méthode sort ne retourne rien !!!

La façon correcte d'utiliser ces méthodes consiste à les appeler sur les objets, sans réaliser d'affectation.

Une méthode particulière et très efficace de création de listes : compréhension de liste

Le langage Python met à disposition une méthode efficace, concise et claire pour créer des listes que nous aborderons à travers des exemples.

xxxxxxxxxx
>>> l1 = [i for i in range(5)]  # liste des 5 premiers entiers
>>> l1
[0, 1, 2, 3, 4]
>>> l2 = [i**2 for i in range(5)]  # liste des carrés des 5 premiers entiers
>>> l2
[0, 1, 4, 9, 16]
>>> l3 = [i**2 for i in range(5) if i % 2 == 0]  
>>> l3  # liste des carrés des 5 premiers entiers si ces entiers sont pairs
[0, 4, 16]
>>> l4 = [ (i, elt**2) for (i, elt) in enumerate(range(5))]  
>>> l4  # liste des des carrés des 5 premiers entiers accompagnés de leur position
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16)]
>>> l5 = [ (i, elt**2) for (i, elt) in enumerate(range(5)) if i % 2 == 0]
>>> l5  # liste des des carrés des 5 premiers entiers accompagnés de leur position
        # si l'entier est pair
[(0, 0), (2, 4), (4, 16)]

Les tuples

Présentation

Les tuples (ou n-uplets en français) sont des objets conteneurs pouvant contenir un nombre arbitraire et non modifiable d'objets Python différents.

De nombreux points communs existent donc entre les tuples et les listes. La grande différence est le caractère modifiable ou pas.

Premières manipulations

Comment créer et affecter un tuple à une variable ?

La création et l'affectation de tuples sont pratiquement identiques à celles des listes, à l'exception des tuples ne contenant qu'un seul élément.

Attention. Pour Python ce qui fait la spécificité d'un tuple, ce ne sont pas les parenthèses mais la virgule.

xxxxxxxxxx
>>> un_tuple = (123, 'abc', 4.56, ('tuple', 'interne'), ['liste', 'interne'])
>>> un_tuple
(123, 'abc', 4.56, ('tuple', 'interne'), ['liste', 'interne'])
>>> autre_tuple = (123,)
>>> autre_tuple
(123,)
>>> autre_tuple[0] = 123   # les tuples ne sont pas modifiables
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>> pas_tuple = (123)
>>> pas_tuple
123

Comment accéder aux éléments d'un tuple ?

xxxxxxxxxx
>>> un_tuple[1:4]
('abc', 4.56, ('tuple', 'interne'))
>>> un_tuple[3][1]
'interne'
>>> un_tuple[4][0]
'liste'

Remarque. On rappelle que les tranches ne sont pas au programme : l'instruction un_tuple[1:4] est donc présente à titre documentaire.

Action des opérateurs des types séquentiels sur les tuples

Tous les opérateurs des types séquentiels présentés dans la première section de ce chapitre s'appliquent aux tuples.

xxxxxxxxxx
>>> un_tuple = (1111, 29873, 12)
>>> un_tuple
(1111, 29873, 12)
>>> 1111 in un_tuple
True
>>> un_autre_tuple = (1,)
>>> un_tuple + un_autre_tuple
(1111, 29873, 12, 1)
>>> un_tuple  # Aucun des tuples n'est modifié
(1111, 29873, 12)
>>> un_autre_tuple
(1,)

Action des fonctions intégrées du language Python sur les tuples

Toutes les fonctions des types séquentiels présentées dans la première section de ce chapitre s'appliquent aux tuples.

xxxxxxxxxx
>>> un_tuple = (1, 2, 4, 8, 16, 32)
>>> un_tuple
(1, 2, 4, 8, 16, 32)
>>> len(un_tuple)
6
>>> max(un_tuple)
32
>>> min(un_tuple)
1
>>> sum(un_tuple)
63

Exercices

Exercice 1. Introduction à l'utilisation des listes

xxxxxxxxxx
valeurs = []
valeurs.append(1)
​
for i in range(6):
    valeurs.append(0)
​
for i in range(1, 7):
    valeurs[i] = valeurs[i - 1] + 2
​
for i in range(7):
    print("Valeur {0} : {1}".format(i, valeurs[i]))
​
for valeur in valeurs:
    print("Valeur : {0}".format(valeur))
​
for i, valeur in enumerate(valeurs):
    print("Valeur {0} : {1}".format(i, valeur))

1. Décrire l'action de chacune des instructions.
2. Comparer les trois dernières structures de boucles.

Exercice 2

Écrire une fonction qui reçoit comme argument une liste de nombres à virgule et recherche lequel est le plus grand et lequel est le plus petit.

x
from typing import List, Tuple
​
def exo2(liste: List[float]) -> Tuple[float]:
    """
    Détermine l'élément le plus grand de la liste de floats passée
    en argument.
    """
    return max(liste), min(liste)

Exercice 3

Écrire une fonction qui reçoit comme argument une liste et détermine le nombre d'éléments dans la liste. Ne pas utiliser la fonction len du langage.

xxxxxxxxxx
from typing import List
​
def longueur_liste(liste: List) -> int:
    """Détermine la longueur de la liste reçue en argument. """
    longueur = 0
    
    for element in liste:
        longueur += 1
    
    return longueur

Exercice 4

Écrire une fonction qui simule le tirage du Loto. Pour rappel, il s'agit de tirer aléatoirement 6 entiers compris entre 1 et 49.

Remarque. Un numéro ne peut apparaître qu'une seule fois. Il est donc nécessaire de stocker le résultat de chaque tirage dans une liste et de vérifier s'il est présent ou pas.

xxxxxxxxxx
def loto() -> List[int]:
    """
    Simule le tirage du Loto. retourne une liste de 6 entiers compris
    entre 1 et 49.
    """
    numeros = []
    nbre_valeurs = 6
    val_min = 1
    val_max = 49
​
    nbre_elements = 0
    while nbre_elements <= nbre_valeurs:
        numero = random.randint(val_min, val_max)
        if numero not in numeros:
            numeros.append(numero)
            nbre_elements += 1
​
    return numeros

Exercice 5

Écrire une fonction qui reçoit une liste de notes comprises entre 0 et 20 comme argument et retourne la moyenne de ces notes et le pourcentage de ces notes comprises dans les intervalles : $[0; \overline{n} - 3]$, $[\overline{n} - 3; \overline{n} + 3]$ et $[\overline{n} + 3; 20]$ où $\overline{n}$ est la valeur moyenne des notes.

La signature de la fonction est :

xxxxxxxxxx
def statistiques(notes: List[float]) -> Tuple[float]:
    """
    Détermine les statistiques des notes reçues en argument : moyenne
    et notes comprises dans les intervalles [0, moy - 3], [moy - 3, moy + 3],
    [moy + 3, 20]
    """

Cette fonction doit utiliser les deux fonctions de signature :

xxxxxxxxxx
def moyenne(liste_notes: List[float]) -> float:
    """
    Détermine la moyenne des notes reçues en argument dans la
    liste passée en argument.
    """

et

xxxxxxxxxx
def nombre_dans_intervalle(liste: List[float], valeur_min: float,
                           valeur_max: float) -> float:
    """
    Détermine le nombre de valeurs de liste comprises dans l'intervalle
    [val_min, val_max].
    """

xxxxxxxxxx
from typing import List
​
def moyenne(liste_notes: List[float]) -> float:
    """
    Détermine la moyenne des notes reçues en argument dans la
    liste passée en argument.
    """
    return sum(liste_notes) / len(liste_notes)
​
​
def nombre_dans_intervalle(liste: List[float], valeur_min: float,
                           valeur_max: float) -> float:
    """
    Détermine le nombre de valeurs de liste comprises dans l'intervalle
    [val_min, val_max].
    """
    nbre = 0
    
    for valeur in liste:
        if valeur >= valeur_min and valeur <= valeur_max:
            nbre += 1
    
    return nbre
​
​
def statistiques(notes: List[float]) -> Tuple[float]:
    """
    Détermine les statistiques des notes reçues en argument : moyenne
    et notes comprises dans les intervalles [0, moy - 3], [moy - 3, moy + 3],
    [moy + 3, 20]
    """
    note_moyenne = moyenne(notes)
    intervalle_inf = nombre_dans_intervalle(notes, 0, note_moyenne - 3)
    intervalle_mid = nombre_dans_intervalle(notes, note_moyenne - 3, note_moyenne + 3)
    intervalle_sup = nombre_dans_intervalle(notes, note_moyenne + 3, 20)
    
    return (note_moyenne, intervalle_inf, intervalle_mid, intervalle_sup)

Exercice 6

Écrire une fonction qui, partir de deux points de l'espace à trois dimensions, calcule la distance euclidienne entre ces deux points. Remarque. Les coordonnées d'un point sont stockées dans un tuple.

La signature de la fonction est :

xxxxxxxxxx
def distance(pt1: Tuple[float], pt2: Tuple[float]) -> float:
    """
    Détermine la distance entre les points pt1 et pt2.
    ERREUR si les dimensions des tuples ne correspondent pas.
    """

xxxxxxxxxx
from typing import Tuple
import math as m
​
​
def distance(pt1: Tuple[float], pt2: Tuple[float]) -> float:
    """
    Détermine la distance entre les points pt1 et pt2.
    ERREUR si les dimensions des tuples ne correspondent pas.
    """
    if len(pt1) != len(pt2):
        raise Exception("Les dimensions des tuples ne correspondent pas.")
    
    distance_carre = 0
    for i in range(len(pt1)):
        distance_carre += (pt1[i] - pt2[i])**2
    
    return m.sqrt(distance_carre)

Exercice 7

Reprendre l'exercice précédent et considérer que les points appartiennent à un espace de dimension $N$ ($N$ étant potentiellement grand).

xxxxxxxxxx
from typing import Tuple
import math as m
​
​
def distance(pt1: Tuple[float], pt2: Tuple[float]) -> float:
    """
    Détermine la distance entre les points pt1 et pt2.
    ERREUR si les dimensions des tuples ne correspondent pas.
    """
    if len(pt1) != len(pt2):
        raise Exception("Les dimensions des tuples ne correspondent pas.")
    
    distance_carre = 0
    for i in range(len(pt1)):
        distance_carre += (pt1[i] - pt2[i])**2
    
    return m.sqrt(distance_carre)

Exercice 8

Écrire une fonction qui retourne une la table de multiplication de tous les nombres entiers compris entre 0 et n.

La spécification de la fonction est :

xxxxxxxxxx
def table_multiplication(n: int) -> List[List[int]]:
    """
    Détermine la table de multiplication de tous les entiers compris entre
    1 et n.
    
    >>> table_multiplication(4)
    [[1, 2, 3, 4], [2, 4, 6, 8], [3, 6, 9, 12], [4, 8, 12, 16]]
    """

xxxxxxxxxx
from typing import List
​
def table_multiplication(n: int) -> List[List[int]]:
    """
    Détermine la table de multiplication de tous les entiers compris entre
    1 et n.
    
    >>> table_multiplication(4)
    [[1, 2, 3, 4], [2, 4, 6, 8], [3, 6, 9, 12], [4, 8, 12, 16]]
    """
    table = []
    
    for i in range(1, n + 1):
        ligne = []
        for j in range(1, n + 1):
            ligne.append(i * j)
        table.append(ligne)
        
    return table
​
if __name__ == "__main__":
    import doctest
    doctest.testmod()