TP1 - Structures de données

A. Ridard

Dimension 0 : éléments "atomiques"

Nombres : entiers et flottants

Les valeurs numériques sont entières ou décimales (approximation avec les flottants), et on peut utiliser les opérateurs suivants :

• $+$ , $-$ , $*$ : addition , soustraction , multiplication
• / : division (le résultat est un flottant)
• ** : exponentiation
• // , % : quotient , reste de la division euclidienne

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

a = 2+5-3*4
print(a)
type(a)

a = 7/2
print(a)
type(a)

a = 2**4
print(a)

a = 7 // 2
b = 7 % 2
print(a)
print(b) 

Booléens

Les valeurs logiques sont True et False, et on peut utiliser les opérateurs suivants :

• and : conjonction
• or : disjonction
• not : négation
• in : test d'appartenance
• < , > , <= , >= , == , != : comparateurs

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

a = True and False
b = True or False
c = not (True or True)
d = 2 in [1,2,3]
print(a)
print(b)
print(c)
print(d)

a = 3 == 6/2
b = type(3) == type(6/2)
c = (1<2) != (1>=1)
print(a)
print(b)
print(c)

Dimension 1

Chaînes de caractères (non modifiables)

• Une chaîne de caractères est une structure ordonnée non modifiable de caractères
• Elle est définie par 'chaine' ou "chaine"
• Les caractères sont accessibles par leur indice (qui commence à 0) et [ ]

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

ch = 'Gymnase'
car = ch[1]
ss_ch = ch[1:4]
print(car)
print(ss_ch)

ch = 'Gymnase'
car = ch[-1]
print(car)
ch[-1] = 's'
print(ch)

Tuples (non modifiables)

• Un tuple est une structure ordonnée non modifiable de valeurs qui peuvent être de différents types
• Elle est définie par (val1, val2, ...)
• Les valeurs sont accessibles par leur indice (qui commence à 0) et [ ]

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

t = (2, 3.5, True, 'GyYv')
val = t[0]
ss_t = t[1:]
print(val)
print(ss_t)

t = (2, 3.5, True, 'GyYv')
val = t[1]
print(val)
t[1] = 7
print(t)

Listes (modifiables avec indice)

• Une liste est une structure ordonnée modifiable de valeurs qui peuvent être de différents types
• Elle est définie par [val1, val2, ...]
• Les valeurs sont accessibles par leur indice (qui commence à 0) et [ ]

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

l = [2, 3.5, True, 'GyYv']
val = l[0]
ss_l = l[:3]
print(val)
print(ss_l)

l = [2, 3.5, True, 'GyYv']
val = l[-2]
print(val)
l[-2] = False
print(l)

Au-delà de la simple modification de valeur, on peut aussi ajouter et supprimer des valeurs. Pour cela, on utilise des méthodes/fonctions prédéfinies.

l = [2, 3.5, True, 'GyYv']

l.append('ajout1')
print(l)

l.pop()
print(l)

l.insert(1,'ajout2')
print(l)

del(l[1])
print(l)

Dictionnaires (modifiables avec clé)

• Un dictionnaire est une structure non ordonnée modifiable de valeurs qui peuvent être de différents types
• Elle est définie par {cle1 : val1, cle2 : val2, ...}
• Les valeurs sont accessibles par leur clé et [ ]

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

d = {'nom' : 'Dupont', 'prenom' : 'Antoine', 'annee_naissance' : 1996, 'taille' : 1.74}
val = d['prenom']
print(val)

d = {'nom' : 'Dupond', 'prenom' : 'Antoine', 'annee_naissance' : 1996, 'taille' : 1.74}
val = d['nom']
print(val)
d['nom'] = 'Dupont'
print(d)

Au-delà de la simple modification de valeur, on peut aussi ajouter et supprimer des valeurs.

d = {'nom' : 'Dupont', 'prenom' : 'Antoine', 'annee_naissance' : 1996, 'taille' : 1.74}
d['poids'] = 85
print(d)
del(d['annee_naissance'])
print(d)

Affectation par valeur ou par référence

Lors d'une affectation sous Python, le nom de la variable est enregistré dans l'espace des noms et pointe vers l'adresse de l'objet qui lui est affecté.

/!\ Le comportement d'une variable dépend du caractère modifiable ou non de l'objet qui lui est affecté.

Exécuter les cellules suivantes et observer les sorties. En quoi est-ce surprenant ?

a = 2
print(a)
print(id(a))

b = a
print(b)
print(id(b))

a = 3
print(a)
print(id(a))
print(b)
print(id(b))

t1 = (2, 3.5, True, 'GyYv')
print(t1)
print(id(t1))

t2 = t1
print(t2)
print(id(t2))

t1 = (2, 3.5, False, 'GyYv')
print(t1)
print(id(t1))
print(t2)
print(id(t2))

l1 = [2, 3.5, True, 'GyYv']
print(l1)
print(id(l1))

l2 = l1
print(l2)
print(id(l2))

l1[2] = False
print(l1)
print(id(l1))
print(l2)
print(id(l2))

Pour éviter ce comportement piégeux, il est conseillé d'utiliser la fonction copy de la bibliothèque du même nom de manière à rendre les listes indépendantes.

from copy import copy

l1 = [2, 3.5, True, 'GyYv']
print(l1)
print(id(l1))

l2 = copy(l1)
print(l2)
print(id(l2))

l1[2] = False
print(l1)
print(id(l1))
print(l2)
print(id(l2))

Parcours d'une structure de données

On peut parcourir toutes les structures de données à l'aide d'une boucle for.

ch = 'Gymnase'
n = len(ch)

for i in range(n) :
    print(i)

ch = 'Gymnase'
n = len(ch)

for i in range(n) :
    print(ch[i])

ch = 'Gymnase'

for car in ch :
    print(car)

t = (2, 3.5, True, 'GyYv')

for val in t :
    print(val)

l = [2, 3.5, True, 'GyYv']

for val in l :
    print(val)

d = {'nom' : 'Dupont', 'prenom' : 'Antoine', 'annee_naissance' : 1996, 'taille' : 1.74}

for val in d.values() :
    print(val)

d = {'nom' : 'Dupont', 'prenom' : 'Antoine', 'annee_naissance' : 1996, 'taille' : 1.74}

for cle in d.keys() :
    print(cle)

d = {'nom' : 'Dupont', 'prenom' : 'Antoine', 'annee_naissance' : 1996, 'taille' : 1.74}

for (cle, val) in d.items() :
    print(cle, '<-->', val)

Exercices

Exercice 1

Ecrire une fonction somme(lst) qui renvoie la somme des entiers de la liste lst.

# réponse

Exercice 2

Ecrire une fonction produit(lst) qui renvoie le produit des entiers de la liste lst.

Si la liste contient 0, la fonction devra renvoyer 0 sans terminer le calcul.

# réponse

Exercice 3

Ecrire une fonction echange(lst, i, j) qui échange dans la liste lst les éléments aux indices i et j.

# réponse

Exercice 4

Ecrire une fonction miroir(lst) qui renvoie "l'image miroir" de la liste lst définie de la manière suivante :

• le 1er élément est le dernier de lst
• le 2eme élément est l'avant dernier de lst
• ...

On pourra se servir de la fonction echange de l'exercice 3.

# réponse

Exercice 5

Ecrire une fonction hamming(lst1, lst2) qui renvoie le nombre d'indices auxquels les deux listes (supposées de la même longueur) diffèrent.

# réponse

Exercice 6

Pour mélanger les éléments d'une liste, il existe un algorithme très simple qui s'appelle le mélange de Knuth : on parcourt la liste de la gauche vers la droite et, pour chaque élément à l'indice i, on l'échange avec un élément situé à un indice tiré aléatoirement entre 0 et i (inclus).

Ecrire une fonction melange(lst) qui réalise cet algorithme.

On pourra se servir de la fonction echange de l'exercice 3.

# réponse

Exercice 7

Ecrire une fonction occurences(lst) qui renvoie un dictionnaire contenant pour chaque entier présent dans la liste lst son nombre d'occurences.

Par exemple, occurences([5, 1, 5, 1, 1]) doit renvoyer le dictionnaire {5:2, 1:3}.

# réponse

Exercice 8

Ecrire une fonction lettre_plus_frequente(ch) qui renvoie la lettre la plus fréquente dans la chaine de caractères ch.

On pourra se servir de la fonction occurences de l'exercice 7.

# réponse

Dimension 2

Listes de listes

Une liste permet de stocker plusieurs valeurs accessibles par leur indice. Si chaque valeur est elle-même une liste, on obtient une liste de listes que l'on peut voir comme la liste des lignes d'un tableau à deux dimensions.

On peut alors accéder aux valeurs (pour les lire ou les modifier) par leur indice et deux [ ] successifs.

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

eleve1 = [4, 4.5, 5.5]
eleve2 = [5, 5.5, 6]

l = [eleve1, eleve2]
print(l)

eleve1 = [4, 4.5, 5.5]
eleve2 = [5, 5.5, 6]

l = [eleve1, eleve2]
val = l[1][0]
print(val)

l[0][2] = 6
print(l)

Pour stocker ce type de données, on préfère les tableaux numpy qui sont "plus proches" des tableaux usuels.

Tableaux numpy

Cette structure de données nécessite la bibliothèque numpy que l'on importera avec l'alias np.

import numpy as np

En fait, la fonction np.array transforme une liste de listes en un tableau numpy.
Contrairement à une liste de listes, l'affichage d'un tableau numpy est conforme à nos habitudes.

On peut accéder aux valeurs (pour les lire ou les modifier) par leur double indice (ligne puis colonne) et [ ].

Deviner les sorties suivantes, puis vérifier en exécutant les cellules.

eleve1 = [4, 4.5, 5.5]
eleve2 = [5, 5.5, 6]
l = [eleve1, eleve2]

tab = np.array(l)
print(tab)

eleve1 = [4, 4.5, 5.5]
eleve2 = [5, 5.5, 6]
l = [eleve1, eleve2]

tab = np.array(l)
val = tab[1,0]
print(val)

tab[0,2] = 6
print(tab)

Pourquoi les entiers sont-ils devenus des flottants ?

Exercices

Exercice 1

Ecrire une fonction max_minLigne(llst) qui renvoie le maximum des minimums de chaque ligne du "tableau" llst.

On pourra écrire une fonction intermédiaire minLigne(lst) qui renvoie le minimum de la liste lst.

# réponse

Exercice 2

Ecrire un programme qui construit un tableau numpy t de taille 11 x 11, tel que t[i, j] = i j.

# réponse

Exercice 3

Ecrire une fonction dessine(llst) qui dessine le "tableau" de booléens llst à l'aide de Turtle, en représentant chaque occurence de False par un carré noir.

Par exemple, dessine([ [False, True, False], [True, False, True] ]) donnera :

# réponse

Pour terminer, on rappelle qu'une image (matricielle) en noir et blanc est représentée par un "tableau" de 0 et de 1.

from pylab import *

image = [[0, 1, 0], [1, 0, 1]]
imshow(image, cmap=cm.gray)
show()