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)

l.pop(1)
print(l)

l.insert(0,3.5)
print(l)

l.remove(3.5)
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)

Parcours d'une structure de données

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

Sur les indices ou les clés

# chaîne de caractères

ch = 'Gymnase'
n = len(ch)

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

# tuple

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

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

# liste

l = [2, 3.5, True, 'GyYv']
n = len(l)

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

# dictionnaire

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

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

Sur les éléments (à privilégier si possible)

# chaîne de caractères

ch = 'Gymnase'

for car in ch :
    print(car)

# tuple

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

for val in t :
    print(val)

# liste

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

for val in l :
    print(val)

# dictionnaire

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

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

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
b = a
b = 3

print(a)

t1 = (2, 3.5, True, 'GyYv')
t2 = t1
t2 = (2, 3.5, False, 'GyYv')

print(t1)

l1 = [2, 3.5, True, 'GyYv']
l2 = l1
l2[2] = False

print(l1)

print(id(l1))
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']
l2 = copy(l1)
l2[2] = False

print(l1)

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

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 directement renvoyer 0.

# 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

Considérons la base de données NoSQL (orientée documents) suivante :

data_nosql = [
{'id_proprio' : 1, 'nom' : 'Müller', 'prenom' : 'Ruedi', 'immat' : 'ZH123456', 'marque' : 'Peugeot', 'tel' : '0799871234'},
{'id_proprio' : 2, 'nom' : 'Caroselli', 'prenom' : 'Maria', 'immat' : 'TI987321', 'marque' : 'Peugeot', 'tel' : '0799875678'},
{'id_proprio' : 3, 'nom' : 'Martin', 'prenom' : 'Pierre', 'immat' : ['GE456789','GE321674'], 'marque' : ['Mercedes','Renault'], 'tel' : '0799874321'},
{'id_proprio' : 4, 'nom' : 'Schneider', 'prenom' : 'Sophie', 'immat' : 'VD789123', 'marque' : 'Ferrari', 'tel' : '0799878765'}
]

# print(data_nosql)
data_nosql

Il s'agit en fait d'une liste de dictionnaires (appelés documents dans ce cadre) ayant un contenu similaire. Plus précisément, chaque dictionnaire permet de stocker les mêmes informations (représentées au niveau des clés), mais pour des entités différentes.

Ces bases de données NoSQL sont flexibles et bien adaptées à une quantité de données gigantesque (big data). Mais lorsque les données sont souvent mises à jour, il est préférable d'utiliser des bases de données relationnelles pour garantir l'intégrité des données. Ces dernières feront l'objet du cours 3 de l'OC Info, mais pour se faire déjà une petite idée, considérerons la table "universelle" suivante :

data_univ = [
['ZH123456', 'Peugeot', 1, 'Müller', 'Ruedi', '0799871234'],
['TI987321', 'Peugeot', 2, 'Caroselli', 'Maria', '0799875678'],
['GE456789', 'Mercedes', 3, 'Martin', 'Pierre', '0799874321'],
['GE321674', 'Renault', 3, 'Martin', 'Pierre', '0799874321'],
['VD789123', 'Ferrari', 4, 'Schneider', 'Sophie', '0799878765']
]

data_univ

Il s'agit là d'une liste de listes (appelés enregistrements dans ce cadre) ayant un contenu similaire. Plus précisément, chaque liste permet de stocker les mêmes informations (représentées au niveau des colonnes), mais pour des entités différentes.

Cette organisation des données est simple et "atomique", mais l'intégrité des données n'est pas évidente à maintenir (pourquoi ?). C'est pour cette raison que nous allons séparer les données dans des tables différentes avec un système de "clés de jointures" permettant de reconstituer toute l'information.

proprio = [
[1, 'Müller', 'Ruedi', '0799871234'],
[2, 'Caroselli', 'Maria', '0799875678'],
[3, 'Martin', 'Pierre', '0799874321'],
[4, 'Schneider', 'Sophie', '0799878765']
]

proprio

voiture = [
['GE321674', 'Renault', 3],
['GE456789', 'Mercedes', 3],
['TI987321', 'Peugeot', 2],
['VD789123', 'Ferrari', 4],
['ZH123456', 'Peugeot', 1]
]

voiture

A l'aide de data_nosql, définir une fonction recherche_nom_nosql(immat) qui renvoie le nom du propriétaire de la voiture dont l'immatriculation est fournie en paramètre.

# définition

# test 

A l'aide de data_univ, définir une fonction recherche_nom_univ(immat) qui renvoie le nom du propriétaire de la voiture dont l'immatriculation est fournie en paramètre.

# définition

# test 

A l'aide de proprio et voiture, définir une fonction recherche_nom(immat) qui renvoie le nom du propriétaire de la voiture dont l'immatriculation est fournie en paramètre.

# définition

# test 

Dans le cours 3, nous verrons le langage SQL qui permet de consulter beaucoup plus facilement ces bases de données relationnelles !