[PDF] Chapitre 5 informatique commune Listes et séquences

Cours dinformatique – PCSI

Cours d'informatique – PCSI Author: Alexandre Casamayou-Boucau Subject: IPT Keywords: IPT, lycée Louis Barthou (Pau) Created Date: 4/6/2020 11:53:56 PM

Cours d’Informatique pour Tous - SFR

classesdepremièreannéeMPSI(831),PCSI(833)etdedeuxièmeannéeMP*,MP,PC*,PC Le cours présenté ici est très détaillé, et tous les points ne sont pas nécessairement abordés en classe : il se veut

Cours d’informatique commune MPSI 4 - Free

Lycée Louis-Le-Grand, Paris Cours d’informatique commune MPSI 4 Alain TROESCH Version du: 4 juin 2015

Informatique - Dunod

lièresMPSI,PCSI,PTSI,TSI,BCPST,TPC,MP,PC,PSIetPT) Ilpourraégalementintéresser en rapport avec le chapitre de cours, illustrée d’un ou plusieurs exemples, et

CLASSES PRÉPARATOIRES SCIENTIFIQUES MPSI - PCSI

Cours TD TP Cours TD TP Cours TD TP Mathématiques 10 h 2 h - 7 h 3 h - 6 h 3 h - Physique 5 h 1 h 1 h 5 h 30 1 h 1 h 6 h 1 h 2 h Chimie 1 h - 1 h 1 h 0,5 h 1 h 3 h 0,5 h 2 h Elèves de MP : au choix Sciences industrielles ou option informatique 1 h 1 h - - - - - - -

Matrices - Gonnord

Dans tout ce chapitre, Kd´esigne un corps : Rou C Tous les espaces vectoriels en jeu sont de dimension finie 1 Pr´esentation de Mn,p(K) 1 1 Espace des matrices (n,p)

Chapitre 5 informatique commune Listes et séquences

Chapitre 5 informatique commune Listes et séquences Une structure de données est une façon de ranger et d’ordonner des objets Il en existe de plusieurs types, qui se distinguent par la façon d’accéder aux éléments de la structure de données et par la façon de modifier cette dernière (en ajoutant ou en ôtant des éléments)

Initiation à la simulation numérique Introduction aux bases

Initiation à la simulation numérique Introduction aux bases de données Cours d’informatique de PSI P E LEROY 11 juin 2019 Cetteœuvreestmiseàdispositionsouslicence

Informatique en CPGE (2018-2019) Le langage SQL

Informatique en CPGE (2018-2019) Le langage SQL S B Lycée des EK 14 mai 2019 S B Présentation en Latex avec Beamer cours avec Monsieur Python

[PDF] cours informatique mpsi python

[PDF] bo s si

[PDF] rapport isn terminale s

[PDF] eduscol ressources isn

[PDF] association d'utilité sociale définition

[PDF] bac s informatique et sciences du numérique

[PDF] définition utilité sociale loi ess

[PDF] utilité sociale des associations

[PDF] utilité sociale définition psychologie

[PDF] utilité sociale sociologie

[PDF] utilité sociale définition philosophique

[PDF] utilité sociale wikipédia

[PDF] le voyage du centurion résumé

[PDF] pathfinder metamagie

[PDF] wiki pathfinder

Chapitre 5informatique commune

Listes et séquencesUnestructure de donnéesest une façon de ranger et d"ordonner des objets. Il en existe de plusieurs types, qui se

distinguent par la façon d"accéder aux éléments de la structure de données et par la façon de modifier cette

dernière (en ajoutant ou en ôtant des éléments).

La principale structure de données enPythonest assurément la classelist. Il s"agit d"une structure hybride, qui

cherche à tirer avantage de deux structures de données fondamentales en informatique : lestableauxet leslistes

chaînées, qui n"existent pas en tant que telles enPython. Nous allons commencer par décrire les caractéristiques

principales de ces deux structures, avant d"observer en quoi la classelists"en s"inspire. 1.

S tructuresde données linéair es

Dans son acceptation la plus générale, unestructure de donnéesspécifie la façon de représenter en mémoire

machine les données d"un problème à résoudre en décrivant : la manière d" attribuerune certaine quan titéde mémoire à cette structure ; la f açond" accédera uxdonnées qu" ellecon tient.

Dans certains cas, la quantité de mémoire allouée à la structure de donnée est fixée au moment de la création

de celle-ci et ne peut plus être modifiée ensuite; on parle alors de structure de donnéesstatique. Dans d"autres

cas l"attribution de la mémoire nécessaire est effectuée pendant le déroulement de l"algorithme et peut donc

varier au cours de celui-ci; il s"agit alors de structure de donnéesdynamique. Enfin, lorsque le contenu d"une

structure de donnée est modifiable, on parle de structure de donnéemutable. Les structures de données classiques appartiennent le plus souvent aux familles suivantes :

lesstructures linéaires: il s"agit essentiellement des structures représentables par des suites finies ordon-

nées; on y trouve les tableaux et les listes chaînées, qui vont nous intéresser par la suite;

les matricesoutableaux multidimensionnels; les structures arborescentes(en particulier les arbres binaires); les structures relationnelles(bases de données ou graphes pour les relations binaires). Nous nous intéresserons avant tout aux deux premières de ces familles. 1.1

T ableaux

Lestableauxforment une suite de variables de même type associées à des emplacements consécutifs de la

mémoire.ad Figure1 - Une représentation d"un tableau en mémoire.

Puisque tous les emplacements sont de même type, ils occupent tous le même nombredde cases mémoire;

connaissant l"adresseade la première case du tableau, on accèdeen coût constantà l"adresse de la case d"indice

ken calculanta+kd. En revanche, ce type de structure est statique : une fois un tableau créé, la taille de ce

dernier ne peut plus être modifiée faute de pouvoir garantir qu"il y a encore un espace mémoire disponible au

delà de la dernière case. En résumé : un tablea uest une structure de donnée sta tique; les élémen tsd utablea uson taccessibles en lecture et en écriture en tem psconstan t.

Remarque

. Le moduleNumpypropose une implémentation des tableaux que nous utiliserons au second semestre : la classearray.

Jean-Pierre Becirspahic

5.2informatique commune

1.2

List eschaînées Leslistes chaînéesassocient à chaque donnée (de même type) un pointeur indiquant la localisation dans la

mémoire de la donnée suivante (à l"exception de la dernière, qui pointe vers une valeur particulière indiquant

la fin de la liste).anil Figure2 - Une représentation d"une liste en mémoire.

Dans une liste chaînée, il est impossible de connaître à l"avance l"adresse d"une case en particulier, à l"exception

de la première. Pour accéder à lanecase il faut donc parcourir lesn1précédentes : le coût de l"accès à une

case est proportionnelle à la distance qui la sépare de la tête de la liste. En contrepartie, ce type de structure

est dynamique : une fois la liste crée, il est toujours possible de modifier un pointeur pour insérer une case

supplémentaire. En résumé : une liste chaînée est une structure de donnée dynamique ; le neélément d"une liste chaînée est accessible en temps proportionnel àn. 1.3

La classe listenPython

Contrairement à ce que pourrait laisser croire son nom, la classelistn"est pas une liste chaînée au sens qu"on

vient de lui donner, mais une structure de donnée plus complexe qui cherche à concilier les avantages des

tableaux et des listes chaînées, à savoir :

être une structure de donnée dynamique dans laquelle les éléments sont accessibles à coût constant.

Dans la description de cette classe qui va suivre, on pourra distinguer les opérations qui relèvent de la structure

de tableau (accès direct aux éléments) de ceux qui relèvent de la structure de liste chaînée (ajout/suppression

d"éléments). 2. C onstruction,modifica tionet acc èsà une list e 2.1

Définition et acc èsaux éléments

Une liste est une structure de données linéaire, les objets étant enclos par des crochets et séparés par des

virgules. Par exemple,a = [0, 1,"abc", 4.5,"de", 6]

est une liste qui comporte 6 éléments. Comme on peut le constater, une liste peut contenir une collection

hétérogène d"objets (des entiers, des flottants, des chaînes de caractères...).

Notons déjà qu"une liste étant elle-même un objetpython, il est tout à fait possible qu"une liste contienne des

listes parmi ses éléments :b = [[], [1], [1,2], [1, 2, 3]]

On accède à chaque élément individuel de la liste par l"intermédiaire de son index. Attention, le premier

élément de la liste possède l"index 0 (tout comme les chaînes de caractères). Pour connaître l"index du dernier

élément, on peut calculer la longueur d"une liste à l"aide de la fonctionlen; l"index du dernier élément d"une

liste nomméelest donclen(l)1.In[1 ]:a[2] Out [1 ]:"abc" In [2 b[3][1] Out [2 2 In [3 ]:len(b) Out [3 4

Listes et séquences5.3Lorsque l"index est négatif, le décompte est pris en partant de la fin; ainsi le dernier élément porte l"index1,

l"avant-dernier l"index2, etc1.In[4 ]:a [2] Out [4 ]:"de"

En d"autres termes, sikest un entier non nul, l"élément d"indicekcoïncide avec l"élément d"indice`k, où`

désigne la longueur de la liste. 2.2

Slicing

À l"instar des chaînes de caractères,pythonpermet d"effectuer des coupes (leslicing) : silest une liste, alors

l[i:j]crée unenouvelle listeconstituée des éléments dont les index sont compris entreietj1 :In[5 ]:a[1:5]

Out [5 [1, "abc", 4.5,"de"] In [6 a [1:1] Out [6 [1, "abc", 4.5,"de"]

Lorsque l"indexiest absent, il est pris par défaut égal à0; lorsquejest absent, il est pris par défaut égal à la

longueur de la liste.In[7 ]:a[:4] Out [7 [0, 1, "abc", 4.5] In [8 a [3:] Out [8 [4.5, "de", 6]

On peut observer sur les exemples ci-dessus quel[:n]permet d"obtenir lesnpremiers éléments de la liste et

l[n:]lesnderniers.

Sélection partielle

Si nécessaire, la syntaxel[debut:fin]possède un troisième paramètre (égal par défaut à 1) indiquant le pas de

la sélection. La commandel[debut:fin:pas]donne tous les éléments de la liste dont les index sont compris

entredebut(au sens large) etfin(au sens strict) et espacés d"un pas égal àpas. Par exemple :In[9 ]:l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

In [10 l[2:9:3] Out [10 [2, 5, 8] In [11 l[3::2] Out [11 [3, 5, 7, 9] In [12 l[::2] Out [12 [0, 2, 4, 6, 8]

Il est même possible de choisir un pas négatif, auquel cas la liste est parcourue à rebours. En particulier,

l[::1]retourne une nouvelle liste dont l"ordre des éléments est inversé2:In[13 ]:l [::1] Out [13 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 2.3Cr éationd"une list epar compr éhension

Les listes sont de typelistet à l"instar des autres types déjà rencontrés, il existe une fonctionlistqui convertit

lorsque c"est possible un objet d"un certain type vers le typelist. C"est le cas en particulier des énumérations

produites par la fonctionrange3. Par exemple :1. Les conventions d"indexation sont identiques à celles des chaînes de caractères (cf. chapitre 2).

2. On observera que pour un pas négatif les valeurs par défaut de début et de fin sont inversées.

3

. Rappelons querange(i, j, p)énumère les entiers compris entrei(au sens large) etj(au sens strict) espacés d"un pas égal àp, les

paramètresietpétant par défaut pris égaux respectivement à 0 et 1.

Jean-Pierre Becirspahic

5.4informatique communeIn[14 ]:list(range(11))

Out [14 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] In [15 ]:list(range(13, 2,3)) Out [15 [13, 10, 7, 4] La conversion est aussi possible entre une chaîne de caractères et une liste : In [16 ]:list("LouisLeGrand") Out [16

[ "L","o","u","i","s","","L","e","","G","r","a","n","d"]Cependant, la conversion de type est toujours un peu dangereuse, faute de connaître précisément la manière

dont la conversion s"opère. Aussi, il est souvent préférable de définir une liste par filtrage du contenu d"une énu-

mération selon un principe analogue à une définition mathématique. Par exemple, à la définition mathématiquenx2~0;10x2650ocorrespond la définitionpar compréhensionsuivante :In[17 ]:[x forxinrange (11)ifx*x <= 50]

Out [17

[0, 1, 2, 3, 4, 5, 6, 7] Ceci nous donne un moyen simple de calculer le produit cartésien de deux listes :

In [18 a, b = [1, 3, 5], [2, 4, 6] Inquotesdbs_dbs4.pdfusesText_8