I11: Chapitre 3 Structures de données Instruction for Nicolas Méloni Licence 1: 1er semestre (2018/2019) ============================================================= 1. Données simples/composites ============================================================= Les types int, float et bool sont appelés des types simples Leurs valeurs, appelées constantes littérales, sont simples. Il existe également des données composées de plusieurs valeurs : les données composites. Nous verrons principalement 3 structures : - les chaı̂nes - les tuples - les listes ============================================================= 2. Les chaı̂nes de caractères ============================================================= Le type str, chaı̂ne de caractères en Python est permet à pour valeur une séquence de caractères unicode. C’est une suite d’éléments ordonnées, indicées par des entiers. L’opérateur [i] avec i un entier (positif ou négatif) permet d'accéder aux différents caractères de la chaı̂ne. s = " Bonjour a tous ! " print ( s [0] , s [3] , s [7] , s [8]) >>> B j s = " Bonjour a tous ! " print ( s [ -1] , s [ -2] , s [ -4] , s [ -5]) >>> ! s o t #Les caractères d'une chaı̂ne à l’endroit à l’envers. s = " Rayon X " i = 0 while i < len ( s ) : print ( s [ i ] ) i = i +1 i = -1 while - len ( ch ) <= i : print ( s [ i ]) i = i - 1 2.2 Extraction de sous-chaı̂ne : ------------------------------------------------------------ Syntaxe : [i:j] représente les caractères entre les indices i et j (exclus) >>> s = " Python 3 " >>> s [1:5] " ytho " >>> s [:3] " Pyt " >>> s [5:] "n 3" >>> s [ -4: -1] " on " >>> s [: -3] " Pytho " >>> s [ -4:] " on 3 " 2.2 Ensemble d’indices ------------------------------------------------------------ syntaxe : [i:j:k] représente les caractères entre les indices i et j (exclus) avec un pas de k : i, i + k, i + 2k, i + 3k, . . . >>> s = " Programmer " >>> s [1:6:2] " rga " >>> s [:7:3] " Pgm " >>> s [::4] " Pre " >>> s [ -8: -2:1] " ogramm " >>> s [7:2: -1] " mmarg " >>> s [10:2: -2] " rmag " 2.4 Opérations sur les chaı̂nes de caractères ------------------------------------------------------------ Les opérateurs : + : concaténation * : répétition len : fonction retournant la longueur d’une chaı̂ne >>> s1 , s2 = " Bonjour " , " a tous " >>> s1 [1:4]+ s2 [::2] ’ onjatu ’ >>> s1 [ -4: -1]*2 ’ joujou ’ >>> len ( s1 [2:]+ s2 [:2]) 6 2.5 Manipulation des chaı̂nes de caractères ------------------------------------------------------------ 1. Écrire un script qui affiche le nombre d’occurences de la lettre e (majuscule ou minuscule) dans une chaı̂ne de caractères saisie au clavier. 2. Écrire un script qui crée une copie d’une chaı̂ne de caractère ch en remplacant tous les i par des 1 et les a par des 4. 3. Écrire un script qui concatène une série de chaı̂nes de caractères en les séparant par des espaces ; la saisie s’arrête quand la chaı̂ne saisie est vide. # occurences de la lettre e (majuscule ou minuscule). nb = 0 i = 0 s = input () while i < len ( s ) : if ch [ i ] == ’e ’ or ch [ i ]== ’E ’: nb = nb + 1 i = i +1 print ( nb ) #remplacer tous les i par des 1 et les a par des 4. s = input () copie = "" i = 0 while i < len ( s ): if ch [ i ] == 'i': copie = copie + "1" elif s[ i ] == 'a': copie = copie + "4" else : copie = copie + s [ i ] # concaténation de chaı̂nes saisie au clavier mots = '' continuer = True while continuer : s = input () mots = mots + ' ' + s continuer = ( s == '.' ) print( mots ) ============================================================= 3. Les tuples ============================================================= Le type tuple Un tuple en Python (type tuple), est une séquence d’éléments hétérogènes non modifiable. Syntaxe : (element 1,element 2,...,element n) les on on les les 12/44 éléments ne sont pas forcément du même type (hétérogènes) peut définir un tuple vide par (,) peut définir un tuple à un seul élément par (element,) éléments sont indicés de 0 à n − 1 éléménts d’un tuple ne peuvent pas être modifié Les tuples Exemples >>> t =(1 , ’ deux ’ ,3.0 ,4 , ’ cinq ’) >>> t [0] 1 >>> t [2] 3 >>> t [1:4] ( ’ deux ’ ,3.0 ,4) >>> t [0] = 0 Traceback ( most recent call last ): File " < stdin > " , line 1 , in < module > TypeError : ’ tuple ’ object does not support item assignment 13/44 Initialisation des tuples La fonction range La fonction range retourne une séquence d’entiers pouvant servir à l’initialisation de listes ou tuple, ou au parcours d’objet composites indexés par des entiers. range(f) correspond à la suite 0, 1, . . . , f − 1 range(d, f) correspond à suite d, d + 1, . . . , f − 1 range(d, f, p) correspond à la suite d, d + p, d + 2p, d + 3p, . . . jusqu’à f − 1 exclu. Exemples >>> t = (0 , 1 , >>> t = (2 , 3 , >>> t = (1 , 3 , 14/44 tuple ( range (4)) 2 , 3) tuple ( range (2 ,5)) 4) tuple ( range (1 ,11 ,2)) 5 , 7 , 9) Opérations sur les tuples Les opérateurs + : concaténation * : répétition len : fonction retournant la longueur d’une chaı̂ne Exemples >>> t1 , t2 = (1 ,2 ,3 ,4) , ( -1 , -2 , -3 , -4) >>> t1 [:3]+ t2 [2:] (1 , 2 , 3 , -3 , -4) >>> t1 [ -4: -1]*2 (1 , 2 , 3 , 1 , 2 , 3) >>> len ( t1 + t2 [::2]) 6 15/44 ============================================================= 4. Les listes ============================================================= Le type list Une liste en Python (type list), est une séquence d’éléments hétérogènes. Syntaxe : [element 1,element 2,...,element n] les éléments ne sont pas forcément du même type (hétérogènes) on peut définir une liste vide par [] les éléments sont indicés de 0 à n − 1 chaque élément d’une liste peut être modifié >>> l =[1 , ’ deux ’ ,3.0 ,4 , ’ cinq ’] >>> l [0] 1 >>> l [2] 3 >>> l [1:4] [ ’ deux ’ ,3.0 ,4] 16/44 >>> l1 = [ ’a ’ , ’b ’] >>> l2 = [ ’1 ’ , ’2 ’] >>> l = [ l1 , l2 ] [[ ’a ’ , ’b ’] ,[ ’1 ’ , ’2 ’ ]] >>> l [0][0] ’a ’ >>> l [0][1] = 0 >>> l [[ ’a ’ ,0] ,[ ’1 ’ , ’2 ’ ]] Initialisation des listes La fonction range La fonction range retourne une séquence d’entiers pouvant servir à l’initialisation de listes ou tuple, ou au parcours d’objet composites indexés par des entiers. range(f) correspond à la suite 0, 1, . . . , f − 1 range(d, f) correspond à suite d, d + 1, . . . , f − 1 range(d, f, p) correspond à la suite d, d + p, d + 2p, d + 3p, . . . jusqu’à f − 1 exclu. Exemples >>> l = list ( range (4)) [0 , 1 , 2 , 3] >>> l = list ( range ( -4 , -1)) ( -4 , -3 , -2) >>> l = list ( range ( -4 ,12 ,3)) [ -4 , -1 , 2 , 5 , 8 , 11] 17/44 Opérations sur les listes Les opérateurs + : concaténation * : répétition len : fonction retournant la longueur d’une chaı̂ne Exemples >>> l1 , l2 = [1 ,2 ,3 ,4] , [ -1 , -2 , -3 , -4] >>> l1 [:3]+ l2 [2:] [1 , 2 , 3 , -3 , -4] >>> l1 [ -4: -1]*2 [1 , 2 , 3 , 1 , 2 , 3] >>> len ( l1 + l2 [::2]) 6 18/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = L[1]+int(L[0][1]) = (2,-1)+L[3] = L[2][1:4] = L[-2][1::2] = L[0][:2]*L[-1][-1] = 19/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = "12345" L[1]+int(L[0][1]) = (2,-1)+L[3] = L[2][1:4] = L[-2][1::2] = L[0][:2]*L[-1][-1] = 19/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = "12345" L[1]+int(L[0][1]) = 5.14 (2,-1)+L[3] = L[2][1:4] = L[-2][1::2] = L[0][:2]*L[-1][-1] = 19/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = "12345" L[1]+int(L[0][1]) = 5.14 (2,-1)+L[3] = (2,-1,-1,2) L[2][1:4] = L[-2][1::2] = L[0][:2]*L[-1][-1] = 19/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = "12345" L[1]+int(L[0][1]) = 5.14 (2,-1)+L[3] = (2,-1,-1,2) L[2][1:4] = ["tu","il","nous"] L[-2][1::2] = L[0][:2]*L[-1][-1] = 19/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = "12345" L[1]+int(L[0][1]) = 5.14 (2,-1)+L[3] = (2,-1,-1,2) L[2][1:4] = ["tu","il","nous"] L[-2][1::2] = ["tu,"nous","ils"] L[0][:2]*L[-1][-1] = 19/44 Exemples nb = " 12345 " L =[ nb , 3.14 , [ " je " ," tu " ," il " ," nous " ," vous " ," ils " ] , ( -1 ,2)] L[0] = "12345" L[1]+int(L[0][1]) = 5.14 (2,-1)+L[3] = (2,-1,-1,2) L[2][1:4] = ["tu","il","nous"] L[-2][1::2] = ["tu,"nous","ils"] L[0][:2]*L[-1][-1] = "1212" 19/44 Modification et affectation des listes Les listes font parties des types modifiables. Une liste peut être modifiée par élément ou par tranche d’éléments. >>> l = [1 ,2 ,3 ,4] >>> l [0] = 0 >>> l [0 ,2 ,3 ,4] >>> l [1] = [1 ,2] >>> l [0 , [1 , 2] , 3 , 4] 20/44 >>> l [1:3]=[10] >>> l [0 ,10 ,4] >>> l [0:2]=[1 ,2 ,3] >>> l [1 , 2 , 3 , 4] Modification et affectation des listes L’opérateur spécial += permet d’ajouter un/des élément(s) en fin de liste. Syntaxe : liste += [element 1,...,element N] >>> l = [1 ,2 ,3 ,4] >>> l += [5] >>> l [1 ,2 ,3 ,4 ,5] 21/44 >>> l += [6 ,7] >>> l [1 ,2 ,3 ,4 ,5 ,6 ,7] Modification et affectation des listes Contrairement aux types précédents, les listes ne sont pas des éléments mais représentent des zones mémoires. S’il existe plusieurs références à une même zone mémoire, alors modifier une partie de la zone mémoire à partir d’une référence modifie également les autres références ! Ça n’est pas le cas pour tous les autres types. >>> a = 2 >>> b = a >>> a = 3 >>> print (a , b ) 3 2 22/44 >>> l1 = [1 ,2] >>> l2 = l1 >>> l1 [0] = 0 >>> print ( l1 , l2 ) [0 ,2] [0 ,2] >>> l1 = [1 ,2] >>> l2 = [1 ,2] >>> l1 [0] = 0 >>> print ( l1 , l2 ) [0 ,2] [1 ,2] Modification et affectation des listes Attention notamment aux listes de listes ! >>> l1 = [1 ,2] >>> l2 = [1 ,2] >>> l3 = [ l1 , l2 ] >>> print ( l3 ) [[1 ,2] ,[1 ,2]] >>> l3 [0][0] = 0 >>> print ( l3 ) [[0 ,2] ,[1 ,2]] 23/44 >>> l1 = [1 ,2] >>> l2 = l1 >>> l3 = [ l1 , l2 ] >>> print ( l3 ) [[1 ,2] ,[1 ,2]] >>> l3 [0][0] = 0 >>> print ( l3 ) [[0 ,2] ,[0 ,2]] Modification et affectation des listes Liste de tuples et tuple de listes >>> >>> >>> >>> 24/44 l1 = [1 ,2] l2 = [3 ,4] t = ( l1 , l2 ) t [0][0] = 1 >>> >>> >>> >>> t1 = (1 ,2) t2 = (3 ,4) l = [ t1 , t2 ] l [0][0] = 1 Modification et affectation des listes Liste de tuples et tuple de listes >>> >>> >>> >>> l1 = [1 ,2] l2 = [3 ,4] t = ( l1 , l2 ) t [0][0] = 1 t = ([0,2],[3,4]) 24/44 >>> >>> >>> >>> t1 = (1 ,2) t2 = (3 ,4) l = [ t1 , t2 ] l [0][0] = 1 Modification et affectation des listes Liste de tuples et tuple de listes >>> >>> >>> >>> l1 = [1 ,2] l2 = [3 ,4] t = ( l1 , l2 ) t [0][0] = 1 t = ([0,2],[3,4]) 24/44 >>> >>> >>> >>> t1 = (1 ,2) t2 = (3 ,4) l = [ t1 , t2 ] l [0][0] = 1 TypeError: ’tuple’ object does not support item assignment Copie de liste Pour copier une liste il faut donc la copier élément par élément : 25/44 # version 1 # version 2 l = [1 ,2 ,3 ,4 ,5 ,6] l_copie = [] i = 0 while i < len ( l ): l_copie += [ l [ i ]] i = i +1 l = [1 ,2 ,3 ,4 ,5 ,6] l_copie = [0]* len ( l ) i = 0 while i < len ( l ): l_copie [ i ] = l [ i ] i = i +1 Copie de liste Attention à nouveau aux listes de listes ! # Copie de surface d ’ une liste l = [[1 ,2] ,[3 ,4]] l_copie = [] i = 0 while i < len ( l ): l_copie += [ l [ i ]] i = i +1 l [0][0]=0 print (l , l_copie ) >>> [[0 ,2] ,[3 ,4]] [[0 ,2] ,[3 ,4]] 26/44 Copie de liste Attention à nouveau aux listes de listes ! # Copie p r o f o n d e d ’ une liste l = [[1 ,2] ,[3 ,4]] l_copie = [] i = 0 while i < len ( l ): l_temp = [] j =0 while j < len ( l [ i ]): l_temp += [ l [ i ][ j ]] j = j +1 l_copie += [ l_temp ] i = i +1 l [0][0]=0 print (l , l_copie ) >>> [[0 ,2] ,[3 ,4]] [[1 ,2] ,[3 ,4]] 27/44 Manipulations des listes Manipulations classiques 1. Saisir les éléments d’une liste au clavier, la saisie se termine quand la chaı̂ne vide est saisie (elle ne doit pas être prise en compte). 2. Calculer la moyenne des éléments d’une liste l float de flottants prédéfinie. 3. Stocker dans une liste les indices où apparait le caractère saut de ligne d’une chaine de caractère ch prédéfinie. 28/44 Manipulations des listes Saisir les éléments d’une liste au clavier, la saisie se termine quand la chaı̂ne vide est saisie. l = [] saisie = input () while saisir != " " : l += [ saisie ] saisie = input () 29/44 Manipulations des listes Calculer la moyenne des éléments d’une liste l float de flottants prédéfinie. moyenne = 0 i = 0 while i < len ( l_float ): moyenne = moyenne + l_float [ i ] i = i +1 moyenne = moyenne / len ( l_float ) 30/44 Manipulations des listes Stocker dans une liste les indices où apparait le caractère saut de ligne d’une chaine de caractère ch prédéfinie. l_indice = [] i = 0 while i < len ( ch ): if ch [ i ] == ’\ n ’: l_indice += [ i ] 31/44 Manipulations de plusieurs listes Manipulations de deux listes 1. Stocker dans une liste les indices des cases contenant des éléments identiques de deux listes l1 et l2 de même longueur. 2. Afficher toutes les combinaisons possibles de paires d’élements appartenant à deux listes l1 et l2. 32/44 Manipulations de plusieurs listes Stocker dans une liste les indices des cases contenant des éléments identiques de deux listes l1 et l2 prédéfinies de même longueur. l_indice = [] i = 0 while i < len ( l1 ): if l1 [ i ] == l2 [ i ]: l_indice += [ i ] i = i +1 33/44 Manipulations de plusieurs listes Afficher toutes les combinaisons possibles de paires d’élements appartenant à deux listes l1 et l2 prédéfinies. i = 0 while i < len ( l1 ): j = 0 while j < len ( l2 ): print ( l1 [ i ] , l2 [ i ]) j = j +1 i = i +1 34/44 L’instruction for Syntaxe : for in est un nom de variable est un itérable Lors de l’exécution de la boucle, la variable prendra tour à tour toutes les valeurs des éléments composant la structure . Dans ce cours, on considérera qu’un itérable est simplement une donnée de type list, str, tuple ou le résultat de la fonction range. 35/44 ============================================================= 5. Linstruction for ============================================================= Parcours de chaı̂ne de caractères chaine = " Bonjour " for car in chaine : print ( car ) >>> B o n j o u r 36/44 L’instruction for Parcours de chaı̂ne de caractères t = ( " toto " , 1 , 2.4) for el in t : print ( el ) >>> toto 1 2.4 37/44 L’instruction for Parcours de chaı̂ne de caractères l = [(1 ,2) , ’ rien ’ , 3.14] for case in l : print ( case ) >>> (1 , 2) rien 3.14 38/44 L’instruction for Parcours d’un intervalle d’entiers 39/44 for i in range (5): print ( i ) for nombre in range ( -7 ,8 ,3): print ( nombre ) >>> 0 1 2 3 4 >>> -7 -4 -1 2 5 Comparaison for / while L’instruction for ne permet que de parcourir des ensembles finis dont la taille est connue avant l’exécution de la boucle. L’instruction while permet de créer une répétition d’instructions selon une condition quelconque. for somme = 0 n = int ( input ( " entrer un nombre : " )) for i in range ( n ): somme = somme + i print ( somme ) >>> entrer un nombre : 100 4950 40/44 Comparaison for / while L’instruction for ne permet que de parcourir des ensembles finis dont la taille est connue avant l’exécution de la boucle. L’instruction while permet de créer une répétition d’instructions selon une condition quelconque. while somme = 0 while somme < 100: n = int ( input ( " entrer un nombre : " )) somme = somme + n print ( somme ) >>> entrer un nombre : 50 entrer un nombre : 25 entrer un nombre : 65 140 41/44 Parcours de liste avancé L’instruction for peut être utilisée avec plusieurs variables lorsque la structure à parcourir s’y prête. # parcours classique l =[(0.1 ,0) , (1 ,2) , (3.14 ,6.12)] for t in l : x = t [0] y = t [1] print (x , y ) >>> 0.1 0 1 2 3.14 6.12 42/44 # p a r c o u r s avance l =[(0.1 ,0) , (1 ,2) , (3.14 ,6.12)] for x , y in l : print (x , y ) >>> 0.1 0 1 2 3.14 6.12 Parcours de liste avancé On considère une liste prédéfinies l points contenant des tuples de 2 flottants représentant des points du plan. Écrire un script qui demande à l’utilisateur de saisir trois flottant x p,y p et r et affiche tous les points de la liste se trouvant à l’intérieur du cercle de centre (x p,y p) et de rayon r. 43/44 Parcours de liste avancé # la liste l _ p o i n t s est p r e d e f i n i e s x_p = float ( input ()) y_p = float ( input ()) r = float ( input ()) for x , y in l_points : X = x_p - x Y = y_p - y dist = ( X **2+ Y **2)**(0.5) if dist <= r : print (x , y )