deutsch     english    français     Imprimer

 

3.9 LISTES

 

 

INTRODUCTION

 

Il faut souvent stocker des valeurs qui forment un tout mais dont le nombre n’est pas connu lors de la rédaction du programme. Ceci requière une structure de données capable de stocker plusieurs valeurs et suffisamment flexible pour tenir compte de l’ordre d’insertion des données. La structure Python répondant à ces critères est une séquence de conteneurs simples appelée liste. Cette section montre en détails comment travailler avec les listes.

Une liste comportant 5 éléments

Une liste est constituée d’éléments individuels simples arrangés les uns après les autres. Par contraste avec une collection d’éléments non ordonnée, les listes comportent un premier et un dernier élément. Tous les autres éléments, sauf le dernier, possèdent un successeur.

Les listes et les collections de données similaires sont d’une importance capitale en programmation. Les principales opérations possibles sur ces structures de données sont les suivantes :

Ajouter des éléments (à la fin, au début, quelque part au milieu)

Lire des éléments

Modifier des éléments

Supprimer des éléments
Itérer sur l’ensemble des éléments

Trier les éléments

Rechercher des éléments dans la collection de données

En Python, on peut stocker n’importe quel type de données dans les listes, pas seulement des nombres. Il est même possible que les éléments n’aient pas tous le même type de données. On pourrait par exemple stocker dans une même liste des nombres et des chaines de caractères.

CONCEPTS DE PROGRAMMATION: Conteneur, liste, prédécesseur, successeur, références

 

 

LISTE DE NOTES

 

On peut interpréter une liste comme une variable. Elle possède donc un nom (identifiant) et une valeur, à savoir ses éléments. On peut créer des listes à l’aide de crochets carrés. L’instruction li = [1, 2, 3] va par exemple créer une liste contenant les éléments 1, 2 et 3 dans l’ordre. Une liste peut également ne comporter aucun élément. Une liste vide est symbolisée par li = [].

Les carnets de notes où l’on insère les notes correspondant à une matière scolaire donnée sont un exemple typique de liste. Prenons l’exemple des notes de biologie. Au début du semestre, la liste de données est vide, ce qui pourrait s’exprimer en Python par bioGrades = []. Ajouter des notes au carnet correspond à l’opération d’ajout d’éléments à la liste. En Python, on utilise la méthode append() de sorte que pour une note de 5, on va faire bioGrades.append(5).

On peut visualiser la liste à n’importe quel moment avec une commande print en écrivant simplement print bioGrades. Si l’on veut calculer la moyenne des notes, il faut parcourir la liste pour additionner toutes les notes. On peut le faire de manière élégante avec une boucle for car

for grade in bioGrades:

parcourt la liste bioGrades dans l’ordre en copiant chaque élément vers la variable grade lors du parcours. Cette variable grade est ensuite accessible à l’intérieure du corps de la boucle.

bioGrades = []
bioGrades.append(5.5)
print bioGrades
bioGrades.append(5)
print bioGrades
bioGrades.append(5.5)
print bioGrades
bioGrades.append(6)
print bioGrades
count = 0
for note in bioGrades:
    count += note
print "Average: " + str(count / len(bioGrades))
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

La méthode append() permet d’ajouter de nouveaux éléments à la liste.

La fonction intégrée à Python len(list) retourne la longueur de la liste liste, à savoir le nombre de ses éléments. Notez l’astuce intéressante avec la variable sum, qui permet de calculer la somme des notes pour ensuite calculer la moyenne. Au lieu d’utiliser une boucle for pour calculer la somme de toutes les notes, on pourrait également utiliser la fonction sum(bioGrades) pour la calculer directement.

 

 

LISTES COMPORTANT UN NOMBRE FIXE D’ÉLÉMENTS

 

Souvent, la taille qu’aura une liste est connue d’avance lors du développement du programme et l’on sait également que tous les éléments de la liste auront le même de données. Dans de nombreux langages de programmation, une telle structure de données est appelée tableau (array en anglais) et on accède aux éléments par le biais de leur indice. En Python, il n’existe pas de tel type de données de longueur fixe et l’on utilise des listes à la place.

Le programme suivant définit un polygone comme une liste de 4 sommets qui sont eux-mêmes définis comme des coordonnées représentées par des listes à deux éléments). Pour pouvoir accéder immédiatement aux éléments à l’aide des indices, on commence par définir le polygone comme une liste d’éléments tous nuls polygon = [0, 0, 0, 0], ce qui peut aussi s’écrire de manière raccourcie par polygon = [0] * 4. Ensuite, on remplace les éléments nuls de la liste par les coordonnées des sommets stockés dans les listes à deux éléments. On affiche le polygone à l’aide d’une boucle for qui parcourt la liste polygon.

 


from gpanel import *

pA = [0, -3]
pB = [5, -3]
pC = [0, 7]
pD = [-5, 7]

makeGPanel(-10, 10, -10, 10)
line(-10, 0, 10, 0)
line(0, -10, 0, 10)

polygon = [0] * 4  # list with 4 elements, initialized with 0
polygon[0] = pA
polygon[1] = pB
polygon[2] = pC
polygon[3] = pD

for i in range(4):
    k = i + 1
    if k == 4:
        k = 0
    line(polygon[i], polygon[k])
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Si l’on connait d’avance la taille de la liste au moment du développement du programme, il est préférable, pour des raisons pratiques et de performance, de créer une liste comprenant directement le bon nombre d’éléments qui seront tous initialisés, généralement avec des zéros. On peut ensuite sans problème se référer à chacun des éléments par son indice.

Rappelez-vous que l’indice du premier élément est 0 et celui du dernier élément est len(liste) – 1.

 

 

INSÉRER ET SUPPRIMER DES ÉLÉMENTS

 

Le programme suivant montre comment fonctionne un traitement de texte. Les caractères saisis sont insérés dans une liste. Il est clair que la longueur de cette liste n’est pas connue d’avance lors de la rédaction du programme, ce qui fait de la liste une structure de données idéale pour la situation. De plus, on dispose d’un curseur de texte que l’on peut placer n’importe où dans le texte à l’aide de la souris.

Lorsque l’on saisit alors un caractère au clavier, celui-ci est inséré à droite du curseur et la liste est de ce fait allongée. Lorsque l’on utilise la touche « retour arrière », le caractère à gauche du curseur de texte est alors supprimé et la liste est réduite d’un élément..

Pour présenter le texte joliment, on écrit les caractères en texte coloré sur un fond pastel dans GPanel. Pour ce faire, on parcourt la liste sur la base de l’indice i.
 
from gpanel import *

BS = 8
SPACE = 32
DEL = 127

def showInfo(key):
    text = "List length = " + str(len(letterList))
    if key != "":
        text += ". Last key code = " + str(ord(key))
    setStatusText(text)  
        
def updateGraphics():
    clear()
    for i in range(len(letterList)):
        text(i, 2, letterList[i], Font("Courier", Font.PLAIN, 24), 
              "blue", "light gray")
    line(cursorPos - 0.2, 1.7, cursorPos - 0.2, 2.7) 

def onMousePressed(x, y):
    setCursor(x)
    updateGraphics()

def setCursor(x):
    global cursorPos
    pos = int(x + 0.7)
    if pos <= len(letterList):    
       cursorPos = pos

makeGPanel(-1, 30, 0, 12, mousePressed = onMousePressed)

letterList = []
cursorPos = 0
addStatusBar(30)
setStatusText("Enter Text. Backspace to delete. Mouse to set cursor.")
lineWidth(3)

while True:
    delay(10)
    key = getKey()
    if key == "":
        continue
    keyCode = ord(key)
    if keyCode == BS:  # backspace
        if cursorPos > 0:
            cursorPos -= 1
            letterList.pop(cursorPos)
    elif keyCode >= SPACE and keyCode != DEL:      
        letterList.insert(cursorPos, key)
        cursorPos += 1
    updateGraphics()
    showInfo(key)
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

On a déjà vu que les éléments d’une liste sont accessibles par un indice qui commence à 0. Pour cela, on utilise les crochets carrés, à savoir. letterList[i]. L’indice doit toujours être compris entre 0 et la longueur de la liste –1. Lorsqu’on utilise une structure for in range(), la valeur d’arrêt de la boucle correspond à la longueur de la liste.
Accéder à un élément qui ne se trouve pas dans la liste constitue une erreur comptant parmi les plus fréquentes en programmation. Si l’on ne fait pas très attention lors de l’utilisation des indices, on peut obtenir des programmes qui tantôt fonctionnent et tantôt se plantent.

Pour déterminer la touche pressée, on utilise getKey(). Cette fonction retourne immédiatement après l’appel et livre soit le dernier caractère saisi au clavier, soit la valeur 65535 (la plus grande valeur entière non signée représentable sur 16 bits) si aucune touche du clavier n’a été pressée.

 

 

DÉJÀ UN PROGRAMME PROFESSIONNEL 

 

Vous êtes déjà capables de visualiser un graphe avec les connaissances acquises jusqu’à présent [plus... Représenter des graphes par ordinateur constitue tout un sujet de recherche de la science informatique]

Il faut pouvoir créer des petits disques noirs dans la fenêtre graphique à l’aide de clics droits de la souris. Ceux-ci seront considérés comme les sommets d’un graphe qui seront interconnectés par des lignes, appelées arêtes. On aimerait pouvoir déplacer un nœud en cliquant dessus avec le bouton gauche et en glissant la souris tout en s’assurant que les arêtes connectées à ce graphe soient mises à jour en temps réel. Un clic droit sur un des nœuds du graphe le supprime ainsi que toutes les arêtes correspondantes.

Il est sage, lorsque l’on fait face à une tâche complexe, de s’intéresser en premier lieu à une sous-tâche plus simple mais qui ne remplit pas tous les critères de la spécification du programme. On pourrait par exemple commencer par développer un programme permettant de créer les sommets du graphe à l’aide de clics gauches de la souris en veillant à les connecter à tous les autres nœuds déjà présents, sans qu’il soit pour autant possible de les déplacer.

Il paraît assez évident qu’il faut représenter le graphe par une liste dans laquelle on stocke les coordonnées des sommets, toujours sous forme de listes.
 

Les nœuds sont donc des points P(x,y) possédant deux coordonnées que l’on peut représenter à l’aide d’une liste pt [x, y]. Le graphe est donc une liste dont les éléments sont des listes de longueur fixée à 2. On va dessiner les arêtes pour connecter les nœuds à l’aide de deux boucles imbriquées, mais il faut s’assurer que chaque paire de nœuds n’est reliée que par une seule arête.

from gpanel import *

def drawGraph():
    clear()
    for pt in graph:
        move(pt) 
        fillCircle(2)
    
    for i in range(len(graph)):
        for k in range(i, len(graph)):
            line(graph[i], graph[k])

def onMousePressed(x, y):
    pt = [x, y]
    graph.append(pt)
    drawGraph()

graph = []
makeGPanel(0, 100, 0, 100, mousePressed = onMousePressed)
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

Une fois cette fonctionnalité de base implémentée, on peut passer à la fonctionnalité de déplacement par glissé-déposer des nœuds à l’aide du bouton droit de la souris. Lors du glissé-déposé, il est très important de connaitre le nœud qui est en train d’être déplacé. On peut l’identifier par son indice iNode dans la liste du graphe. Si aucun nœud n’est en train d’être déplacé, on a iNode = -1. La fonction near(x, y) utilise le théorème de Pythagore pour calculer la distance entre le point P(x, y) du clic de la souris et les sommets du graphe. On utilise cette fonction pour déterminer sur lequel des sommets on est en train de cliquer.

 

En effet, la souris ne cliquera en général pas exactement sur le milieu des sommets. La fonction near(x,y) retourne donc l’indice du sommet tel que la distance entre son centre et le clic est inférieur à 10. On remarquera au passage qu’on utilise une instruction return en plein milieu de la fonction et non nécessairement à la fin [plus... Le fait d'interrompre prématurément une fonction avec un return peut conduire
à des programmes non structurés, ce qui amène beaucoup de programmeurs à éviter cette pratique
]

Tout le reste du code n’est que petit plaisir de développement que vous auriez aisément pu écrire de manière autonome avec vos connaissances actuelles.

from gpanel import *

def drawGraph():
    clear()
    for i in range(len(graph)):
        move(graph[i]) 
        if i == iNode:
            setColor("red")
        else:
            setColor("green")              
        fillCircle(2)
  
    setColor("blue")
    for i in range(len(graph)):
        for k in range(i, len(graph)):
            line(graph[i], graph[k])

def onMousePressed(x, y):
    global iNode   
    if isLeftMouseButton():
        iNode = near(x, y)
    if isRightMouseButton():
        index = near(x, y)
        if index != -1:
            graph.pop(index)
            iNode = -1
        else:
            pt = [x, y]
            graph.append(pt)
    drawGraph()

def onMouseDragged(x, y):
    if isLeftMouseButton():
        if iNode == -1:
            return        
        graph[iNode] = [x, y]
        drawGraph()

def onMouseReleased(x, y):
    global iNode
    if isLeftMouseButton():
        iNode = -1
        drawGraph()

def near(x, y):
    for i in range(len(graph)):
        p = graph[i]
        d = (p[0] - x) * (p[0] - x) + (p[1] - y) * (p[1] - y)
        if  d < 10:
            return i
    return -1

graph = []
iNode = -1
makeGPanel(0, 100, 0, 100, 
              mousePressed = onMousePressed, 
              mouseDragged = onMouseDragged,
              mouseReleased = onMouseReleased)
addStatusBar(20) 
setStatusText("Right mouse button to set nodes, left button to drag")             
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Le programme est complètement dirigé par les événements. Le bloc principal ne fait que définir deux variables globales et initialiser la fenêtre de graphiques. Pour chaque action déclenchée par les événements, l’entier de la fenêtre est effacé et redessiné avec les données du graphe mises à jour.
Voici un résumé des opérations les plus importantes sur les listes :


li = [1, 2, 3, 4]

li = [1, "a", [7 , 5]]

li[i]

li[start:end]

li[start:end:step]

li[start:]

li[:end]

li.append(element)

li.insert(i, element)

li.extend(li2)

li.index(element)

li.pop(i)

pop()

li1 + li2

li1 += li2

li * 4

[0] * 4

len(li)

del li[i]

del li[start:end]

del li[:]

li.reverse() 

li.sort() 

x in li

x not in li

Définit une liste avec les nombres 1, 2, 3, 4

Définit une liste avec différents types de données

Accède à l’élément d’indice i

Sous-liste d’éléments entre start et end non compris

Liste d’éléments entre start et end non compris, par sauts step

Sous-liste des éléments à partir de start

Sous-liste des éléments depuis le début jusqu’à end non compris

Ajoute un élément en fin de liste

Insère un élément à la position i, repoussant les autres droite

Appond tous les éléments de la liste li2 à la fin de li

Trouve la première occurrence de element et retourne son indice

Retourne et supprime l’élément d’indice i

Retourne et supprime le dernier élément

Retourne la concaténation de li1 et li2 dans une nouvelle liste

Remplace li1 par la concaténation de li1 et li2

Nouvelle liste constituée des éléments de li répétés 4 fois

Crée une nouvelle liste de longueur 4 (tous les éléments nuls)

Retourne le nombre d’éléments de la liste

Supprimer l’élément d’indice i

Supprime tous éléments à partir de start jusqu’à end non compris

Supprimer l’élément d’indice i

Renverse l’ordre de la liste (le dernier devient le premier)

Trie la liste (comparaison avec des méthodes standards)

Retourne True si x se trouve dans la liste

Retourne True si x ne se trouve pas dans la liste


La notation [ :] avec les crochets carrés et le double-point effectue une opération appelée slicing qui coupe une « tranche » dans la liste. start et end sont des indices de la liste qui fonctionnent exactement comme les paramètres de la fonction range().

 

 

EXERCICES

 

1.


Écrire un programme permettant de saisir un nombre quelconque de notes avec inputFloat(prompt, False). Si l’on clique sur Annuler, la moyenne sera calculée et affichée dans la console. Le deuxième paramètre prend la valeur False pour éviter que le programme ne se termine si l’on clique sur Annuler. Au lieu de cela, la fonction retournera la valeur None que l’on peut tester dans une structure if.


2.

Étendre le programme d’édition de texte vu précédemment avec un slicing de sorte qu’un clic droit supprime le début de la phrase jusqu’au premier espace inclus.



3.

Développer un programme faisant apparaître un ballon de football (football.gif) à la position de chaque clic de la souris. Tous les ballons sont constamment en mouvement de gauche à droite sur l’écran. Au besoin, replongez-vous dans le chapitre sur les animations qui présente un exemple similaire. On peut optimiser le programme en chargeant une fois pour toutes l’image avec img = getImage("sprites/football.gif") et passer la variable img à la fonction image().


 
 

 

 

 

MATÉRIEL SUPPLÉMENTAIRE:


 

TYPES DE DONNÉES MUTABLES ET IMMUTABLES

 

En Python, toutes les données sont stockées sous forme d’objets, quel que soit leur type, y compris les types numériques (nombres entiers, flottants, entiers longs et nombres complexes). Comme vous le savez, on peut accéder à un objet par son nom (identifiant). On dit également que le nom se réfère à l’objet ou qu’il est lié à l’objet (bound en anglais). De ce fait, une telle variable est également appelée une variable référence.

Un même objet peut être référencé par plus d’un nom. Un nom supplémentaire est appelé un alias. L’exemple suivant montre ce concept en action.

Un triangle est défini par la liste de ses sommets a, b, c. On peut créer un alias avec l’instruction a_alias = a, de telle sorte que a et a_alias référencent exactement la même liste de coordonnées. Ainsi, si l’on modifie la liste de coordonnées du sommet dont le nom est a, les changements seront également appliqués à la liste de coordonnées référencée par a_alias puisque c’est exactement la même..

 


from gpanel import *

makeGPanel(-10, 10, -10, 10)

a = [0, 0]  
a_alias = a
b = [0, 5]
c = [5, 0]

fillTriangle(a, b, c)
a[0] = 1
setColor("green")
fillTriangle(a_alias, b, c)
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

Du fait que les nombres sont également des objets, on s’attendrait au même comportement si on utilisait des nombres pour représenter les coordonnées des sommets. L’exemple suivant montre cependant qu’il n’en est rien. Si l’on change xA, la valeur de xA_alias ne change pas.

 


from gpanel import *

makeGPanel(-10, 10, -10, 10)

xA = 0
yA = 0
xA_alias = xA
yA_alias = yA
xB = 0
yB = 5
xC = 5
yC = 0

fillTriangle(xA, yA, xB, yB, xC, yC)
xA = 1
setColor("green")
fillTriangle(xA_alias, yA_alias, xB, yB, xC, yC)
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

Comment expliquer ce phénomène ? La raison est que les nombres sont des objets immutables et que l’instruction xA + 1 génère un nouveau nombre. xA_alias vaut donc toujours 0.

La différence entre des types de données immutables et mutables peut également être observée lorsque l’on passe des paramètres aux fonctions. Lorsqu’un objet immutable est passé, il ne peut pas être modifié de l’intérieur de la fonction. Par contre, lorsqu’on passe un objet mutable comme une liste, celui-ci peut être modifié de l’intérieur de la fonction, ce qui constitue un effet secondaire, ou effet de bord. Lorsque l’on cherche à programmer avec un bon style, on évite le plus possible les effets de bords car ils peuvent causer des comportements non souhaités dont les causes sont souvent très difficiles à identifier.

Dans l’exemple suivant, la fonction translate() modifie les listes de coordonnées passées en paramètre pour effectuer une translation.

 


from gpanel import *

def translate(pA, pB, pC):
  pA[0] = pA[0] + 5
  pA[1] = pA[1] + 2
  pB[0] = pB[0] + 5
  pB[1] = pB[1] + 2
  pC[0] = pC[0] + 5
  pC[1] = pC[1] + 2

makeGPanel(-10, 10, -10, 10)

a = [0, 0]  
b = [0, 5]
c = [5, 0]
fillTriangle(a, b, c)
translate(a, b, c)
setColor("green")
fillTriangle(a, b, c)
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

En Python, tous les types de données sont stockés sous forme d’objets dont certains sont considérés comme immutables. Les types immutables en Python sont les suivants: Les types numériques, les chaînes de caractères ainsi que byte et tuple.
Tous les autres types de données sont mutables. Lorsqu’on assigne une nouvelle valeur à une variable immutable, un nouvel objet est créé en mémoire et à son tour référencé par cette variable.

Si des objets mutables sont passés en paramètre à une fonction, la fonction peut les modifier tandis que les objets immutables sont immunisés contre de tels modifications depuis l’intérieur de la fonction.