Tableaux et listes : les algorithmes de base

Un tableau est une structure qui range plusieurs valeurs sous un seul nom, chacune repérée par sa position, appelée indice ; en Python, on utilise pour cela une liste. Ce chapitre montre comment construire un tableau, accéder à ses éléments, le parcourir, et écrire les algorithmes qui reviennent dans tous les sujets : somme, moyenne, maximum, comptage, recherche, insertion, suppression et copie.

Pourquoi des tableaux ?

Pour calculer la moyenne de trois notes, trois variables suffisent. Pour trente notes, il en faudrait trente, et autant de lignes de calcul. Et si le nombre de notes change, il faut réécrire le programme. Un tableau regroupe toutes les notes dans une seule variable ; une boucle les traite toutes, quel que soit leur nombre.

Le tableau notes a 5 éléments, d'indices 0 à 4. L'élément d'indice 2, noté notes[2], vaut 17. Un tableau de n éléments a des indices de 0 à n - 1 : le dernier indice n'est pas n.

Construire un tableau

En pseudo-code, on déclare le tableau avec sa taille et le type de ses éléments. Le programme parle de tableaux « de type homogène » : toutes les cases ont le même type.

Variables
    notes : tableau[0..4] de réels
Début
    notes[0] ← 14
    notes[1] ← 9
    ...

En Python, un tableau à une dimension est une liste. Elle n'a pas de taille fixe et peut grandir : on peut la créer de plusieurs façons.

notes = [14, 9, 17, 11, 9]   # en donnant ses valeurs
zeros = [0] * 5              # 5 cases à 0 : [0, 0, 0, 0, 0]
releves = []                 # vide, puis on ajoute
releves.append(21.5)
releves.append(19.0)
print(notes, zeros, releves, len(notes))

[14, 9, 17, 11, 9] [0, 0, 0, 0, 0] [21.5, 19.0] 5

len(t) donne le nombre d'éléments. t.append(x) ajoute x à la fin : c'est la façon normale de remplir une liste dans une boucle, par exemple à partir de saisies.

n = int(input("Combien de notes ? "))
notes = []
for i in range(n):
    notes.append(float(input(f"Note {i + 1} ? ")))

Accéder à un élément

On lit ou on modifie un élément par son indice, entre crochets.

notes = [14, 9, 17, 11, 9]
print(notes[0], notes[4])   # premier et dernier
notes[1] = 10               # modification
print(notes)
print(notes[-1])            # Python : le dernier élément

14 9
[14, 10, 17, 11, 9]
9

Les indices négatifs sont une facilité de Python (t[-1] est le dernier élément, t[-2] l'avant-dernier) ; ils n'existent pas en pseudo-code ni dans la plupart des langages. En algorithmique, écris t[n - 1].

Parcourir un tableau

Parcourir, c'est visiter chaque élément une fois, dans l'ordre. Deux écritures existent en Python.

Par indice, quand tu as besoin de la position (pour la renvoyer, pour comparer un élément à son voisin, pour modifier la case) :

Pour i de 0 à longueur(t) - 1 Faire
    Afficher(i, " : ", t[i])
FinPour

t = [14, 9, 17]
for i in range(len(t)):
    print(i, ":", t[i])

Par valeur, quand seule la valeur compte (somme, comptage) :

t = [14, 9, 17]
for note in t:
    print(note)

La seconde est plus lisible et ne peut pas déborder du tableau. Quand tu as besoin des deux, enumerate donne l'indice et la valeur à chaque tour : for i, note in enumerate(t):.

Somme et moyenne

C'est le motif de l'accumulateur (chapitre 4) appliqué à un tableau.

Fonction Moyenne(t : tableau de réels) : réel
// Précondition : t n'est pas vide
    somme ← 0
    Pour i de 0 à longueur(t) - 1 Faire
        somme ← somme + t[i]
    FinPour
    Retourner somme / longueur(t)
FinFonction

def moyenne(t):
    """Moyenne d'une liste non vide de nombres."""
    somme = 0
    for valeur in t:
        somme = somme + valeur
    return somme / len(t)


print(moyenne([14, 9, 17, 11, 9]))

12.0

Maximum et minimum

Pour trouver le plus grand élément, on garde « le plus grand vu jusqu'ici » et on le compare à chaque élément suivant.

Fonction Maximum(t : tableau de réels) : réel
// Précondition : t n'est pas vide
    maxi ← t[0]
    Pour i de 1 à longueur(t) - 1 Faire
        Si t[i] > maxi Alors
            maxi ← t[i]
        FinSi
    FinPour
    Retourner maxi
FinFonction

def maximum(t):
    maxi = t[0]
    for i in range(1, len(t)):
        if t[i] > maxi:
            maxi = t[i]
    return maxi


print(maximum([14, 9, 17, 11, 9]), maximum([-3, -8, -1]))

17 -1

Pour le minimum, on inverse la comparaison (<). Souvent, on veut la position du maximum plutôt que sa valeur, par exemple pour afficher le nom de l'étudiant qui a la meilleure note. On garde alors l'indice :

def indice_du_max(t):
    i_max = 0
    for i in range(1, len(t)):
        if t[i] > t[i_max]:
            i_max = i
    return i_max


noms = ["Inès", "Hugo", "Léa", "Malik"]
notes = [14, 9, 17, 11]
i = indice_du_max(notes)
print(noms[i], "a la meilleure note :", notes[i])

Léa a la meilleure note : 17

En cas d'égalité, > garde le premier maximum rencontré ; avec >=, on garderait le dernier.

Compter

Le compteur s'incrémente quand un élément vérifie une condition.

notes = [14, 9, 17, 11, 9]
nb_sous_la_moyenne = 0
for note in notes:
    if note < 10:
        nb_sous_la_moyenne = nb_sous_la_moyenne + 1
print(nb_sous_la_moyenne)

2

Beaucoup d'énoncés sont des comptages déguisés : « combien de tickets sont ouverts », « y a-t-il au moins un serveur hors ligne » (compter, puis tester nb > 0), « tous les postes sont-ils à jour » (compter ceux qui ne le sont pas, puis tester nb = 0).

Rechercher un élément

La recherche séquentielle parcourt le tableau jusqu'à trouver la valeur cherchée. Elle fonctionne sur n'importe quel tableau, trié ou non. On renvoie l'indice de la première occurrence, ou −1 par convention si la valeur est absente.

En pseudo-code, une boucle TantQue exprime clairement les deux raisons de s'arrêter : on a trouvé, ou on est au bout.

Fonction Rechercher(t : tableau d'entiers, x : entier) : entier
    i ← 0
    trouve ← FAUX
    TantQue i < longueur(t) ET NON trouve Faire
        Si t[i] = x Alors
            trouve ← VRAI
        Sinon
            i ← i + 1
        FinSi
    FinTantQue
    Si trouve Alors
        Retourner i
    Sinon
        Retourner -1
    FinSi
FinFonction

En Python, un return dans la boucle donne une version plus courte :

def rechercher(t, x):
    for i in range(len(t)):
        if t[i] == x:
            return i
    return -1


ports = [22, 80, 443, 3306]
print(rechercher(ports, 443), rechercher(ports, 21))

2 -1

Dans le pire cas (valeur absente ou en dernière position), la recherche séquentielle examine tous les éléments. Sur un tableau trié, la recherche dichotomique fait beaucoup mieux (chapitre 10).

Ajouter, insérer, supprimer

En pseudo-code, un tableau a une taille fixe. Insérer une valeur au milieu oblige à décaler les éléments suivants d'une case vers la droite, en partant de la fin pour ne rien écraser. C'est un exercice classique, qui montre pourquoi l'insertion « coûte » plus cher qu'un ajout en fin de tableau.

// t contient n éléments utiles, dans un tableau d'au moins n + 1 cases.
// Insère x à l'indice p (0 ≤ p ≤ n).
Pour i de n à p + 1 pas -1 Faire
    t[i] ← t[i - 1]
FinPour
t[p] ← x
n ← n + 1

Python fait ce travail pour toi avec ses méthodes de liste :

Ces méthodes décalent les éléments en interne : insert et pop(0) sont plus lentes que append et pop() sur une très longue liste.

Copier un tableau

C'est le piège le plus surprenant de Python. L'affectation b = a ne copie pas la liste : elle donne un second nom à la même liste. Toute modification par b est visible par a.

a = [3, 8, 5]
b = a          # b désigne la même liste que a
b[0] = 99
print(a)

a = [3, 8, 5]
c = a.copy()   # c est une nouvelle liste, avec les mêmes valeurs
c[0] = 99
print(a, c)

[99, 8, 5]
[3, 8, 5] [99, 8, 5]

Une variable Python ne contient pas la liste elle-même, mais une référence vers elle (une sorte d'adresse). b = a copie la référence. Pour copier les valeurs, utilise a.copy(), list(a) ou a[:]. C'est le même mécanisme qui permet à une fonction de modifier une liste reçue en paramètre (chapitre 6). Le programme demande de savoir « copier un tableau » : en pseudo-code, on l'écrit avec une boucle qui recopie chaque case.

Pour i de 0 à longueur(a) - 1 Faire
    copie[i] ← a[i]
FinPour

Les nombres et les chaînes, eux, ne posent pas ce problème : on ne peut pas les modifier sur place, donc partager une référence est sans danger.

Les fonctions toutes faites de Python

Python fournit la plupart de ces algorithmes en une instruction. En situation professionnelle, on s'en sert ; à l'examen, on te demande souvent l'algorithme : connais les deux.

Python propose aussi les listes en compréhension, une écriture compacte pour construire une liste à partir d'une autre : [n * 2 for n in t] double chaque élément, [n for n in t if n >= 10] filtre. Elles sont courantes en Python professionnel ; la boucle avec append fait exactement la même chose et reste la forme à maîtriser.

Exercices

t = [5, 12, 7, 3, 12]
k = 0
for i in range(1, len(t)):
    if t[i] > t[k]:
        k = i
print(k, t[k])

def nb_au_dessus_moyenne(t):
    somme = 0
    for v in t:
        somme = somme + v
    moy = somme / len(t)
    nb = 0
    for v in t:
        if v > moy:
            nb = nb + 1
    return nb


print(nb_au_dessus_moyenne([14, 9, 17, 11, 9]))

n ← longueur(t)
Pour i de 0 à n DIV 2 - 1 Faire
    temp ← t[i]
    t[i] ← t[n - 1 - i]
    t[n - 1 - i] ← temp
FinPour

t = [4, 7, 1, 9, 3]
n = len(t)
for i in range(n // 2):
    t[i], t[n - 1 - i] = t[n - 1 - i], t[i]
print(t)

def sans_doublons(t):
    resultat = []
    for v in t:
        if v not in resultat:
            resultat.append(v)
    return resultat


print(sans_doublons([12, 5, 7, 5, 12, 3]))

def est_trie(t):
    for i in range(1, len(t)):
        if t[i] < t[i - 1]:
            return False
    return True


assert est_trie([2, 5, 5, 9]) == True    # cas normal, avec égalité
assert est_trie([2, 9, 5]) == False      # cas normal non trié
assert est_trie([9, 2]) == False         # défaut au tout début
assert est_trie([]) == True              # cas limite : vide
assert est_trie([7]) == True             # cas limite : un élément
print("OK")

def ajouter_bonus(notes):
    for i in range(len(notes)):
        notes[i] = notes[i] + 1


classe = [12, 8, 15]
sauvegarde = classe
ajouter_bonus(classe)
print(classe, sauvegarde)

t = [1, 2, 3, 4]
n = len(t)
dernier = t[n - 1]
for i in range(n - 1, 0, -1):
    t[i] = t[i - 1]
t[0] = dernier
print(t)