Différences entre versions de « Structures de données »
(Structures de données et implémentation python) |
|||
| Ligne 49 : | Ligne 49 : | ||
<!-- *************** Commercez les modifications *******************--> | <!-- *************** Commercez les modifications *******************--> | ||
| − | *............................................ | + | *...Structures de données |
| − | + | Les types prédéfinis que nous avons vus sont insuffisants pour traiter des données plus complexes. On peut citer deux exemples. On veut représenter un élève qui est caractérisé son nom, son prénom, sa date de naissance, sa moyenne générale, etc. On voudrait qu’une seule variable conserve et donc donne accès à toutes ces informations. En algorithmique, on définirait alors un type enregistrement Eleve regroupant ces informations. Le type Eleve est alors le produit cartésien d’une chaîne de caratère (le nom), d’une deuxième chaîne de caractère (le prénom), d’une date (la date de naissance), d’un nombre (la moyenne générale), etc. | |
| − | + | ||
| − | + | Dans un deuxième exemple, on voudrait pouvoir définir une classe avec tous les élèves qui apparatiennent à la classe. Dans ce cas, on veut représenter des informations de même type, les élèves, dont l’ordre n’a pas d’importance et pourrait être changé (les élèves pourraient être rangés de manière aléatoire, classés par ordre alphabétique de leur nom, classés en fonction de leur moyenne générale, etc.). En algorithmique, on utilise alors un tableau. Un tableau est un type de données qui permet de regrouper un nombre fini d’éléments ayant tous le même type. Les éléments sont repérés par leur position (appelée indice) dans le tableau (souvent l’entier 0 pour le premier élément). | |
| + | |||
| + | Ces deux types de données, enregistrement et tableau, n’existent pas vraiment en Python. Pour les tableaux, on s’appuiera sur le type List de Python. Pour les enregistrements, plusieurs solutions sont possibles : les tuples, les dictionnaires ou les classes. Nous préviligerons les classes dans un mode très dégradé. | ||
| + | |||
| + | 8.1. Tableau en Python (List) | ||
| + | Attention : Nous ne présentons ici qu’un tout petit sous-ensemble des possibilités du tpye List de Python. Le but est en effet de ne présenter que les éléments qui permettent de _simuler_ les tableaux algorithmiques . | ||
| + | |||
| + | Remarque : Pour des tableaux numériques de grande taille, on utilisera le type array de la bibliothèque Numpy qui offre une implémentation efficace. | ||
| + | |||
| + | Définition : Une liste est un agrégat d’éléments qui sont repérés par leur position (ou indice). | ||
| + | |||
| + | Python étant typé dynamiquement, aucun type n’est imposé sur les éléments de la liste qui peuvent donc être hétérogènes. | ||
| + | |||
| + | En algorithmique, quand on déclare un tableau, on précise sa capacité, le nombre maximal d’éléments qu’il pourra stocker, et on est souvent amené à gérer une taille effective, le nombre d’éléments réellement stockés dans le tableau. En Python, le programmeur n’a pas à se préoccuper de la capacité car l’espace de stockage des éléments sera agrandi quand de nouveaux éléments seront ajoutés. Il obtient la taille effective de la liste (le nombre d’éléments qu’elle contient) grâce à la fonction len(). | ||
| + | |||
| + | TODO : montrer plutôt les opérateurs du langage : + et += plutôt que append et extend | ||
| + | |||
| + | 8.1.1. En Python | ||
| + | >>> l = [] # liste vide | ||
| + | >>> type(l) | ||
| + | <class 'list'> | ||
| + | >>> l | ||
| + | [] | ||
| + | >>> l.append('b') # ajout d'un élément à la fin | ||
| + | >>> l | ||
| + | ['b'] | ||
| + | >>> 'a' in l # teste l'appartenance de 'a' à la liste | ||
| + | False | ||
| + | >>> l.extend(['c','d','d','e']) # ajout des éléments d'une autre | ||
| + | ... # liste à la fin (concaténation) | ||
| + | >>> l | ||
| + | ['b', 'c', 'd', 'd', 'e'] | ||
| + | >>> l.insert(0, 'a') # ajout d'un élément à une position donnée | ||
| + | >>> l | ||
| + | ['a', 'b', 'c', 'd', 'd', 'e'] | ||
| + | >>> 'a' in l # teste l'appartenance de 'a' à la liste | ||
| + | True | ||
| + | >>> len(l) # nombre d'éléments dans la liste | ||
| + | 6 | ||
| + | >>> l[2] # accès à un élément par sa position | ||
| + | 'c' | ||
| + | >>> l[2:4] # accès à une sous-liste | ||
| + | ['c', 'd'] | ||
| + | >>> del l[3] # suppression d'un élément (par sa position) | ||
| + | >>> l | ||
| + | ['a', 'b', 'c', 'd', 'e'] | ||
| + | >>> l[3] = 'D' # modification d'un élément | ||
| + | >>> l | ||
| + | ['a', 'b', 'c', 'D', 'e'] | ||
| + | >>> max(l) # maximum de la liste (ordre lexicographique) | ||
| + | 'e' | ||
| + | >>> min(l) # minimum de la liste (ordre lexicographique) | ||
| + | 'D' | ||
| + | >>> l.reverse() # inverse l'ordre des éléments dans la liste | ||
| + | >>> l | ||
| + | ['e', 'D', 'c', 'b', 'a'] | ||
| + | >>> l.sort() # trier la liste (ordre lexicographique) | ||
| + | >>> l | ||
| + | ['D', 'a', 'b', 'c', 'e'] | ||
| + | >>> [6, 7, 6, 7, 6].count(6) # compter le nombre d'occurence | ||
| + | ... # d'un élément | ||
| + | 3 | ||
| + | >>> list( (1,2,3) ) # contruire une liste (ici à partir d'un tuple) | ||
| + | [1, 2, 3]...... | ||
*...................................................................... | *...................................................................... | ||
....................................................................... | ....................................................................... | ||
Version du 3 juin 2022 à 06:56
 Votre Publicité sur le Réseau
|
Traduction
Traductions
Définition
Domaine, Discipline, Thématique
Justification
Définition écrite
- ...Structures de données
Les types prédéfinis que nous avons vus sont insuffisants pour traiter des données plus complexes. On peut citer deux exemples. On veut représenter un élève qui est caractérisé son nom, son prénom, sa date de naissance, sa moyenne générale, etc. On voudrait qu’une seule variable conserve et donc donne accès à toutes ces informations. En algorithmique, on définirait alors un type enregistrement Eleve regroupant ces informations. Le type Eleve est alors le produit cartésien d’une chaîne de caratère (le nom), d’une deuxième chaîne de caractère (le prénom), d’une date (la date de naissance), d’un nombre (la moyenne générale), etc.
Dans un deuxième exemple, on voudrait pouvoir définir une classe avec tous les élèves qui apparatiennent à la classe. Dans ce cas, on veut représenter des informations de même type, les élèves, dont l’ordre n’a pas d’importance et pourrait être changé (les élèves pourraient être rangés de manière aléatoire, classés par ordre alphabétique de leur nom, classés en fonction de leur moyenne générale, etc.). En algorithmique, on utilise alors un tableau. Un tableau est un type de données qui permet de regrouper un nombre fini d’éléments ayant tous le même type. Les éléments sont repérés par leur position (appelée indice) dans le tableau (souvent l’entier 0 pour le premier élément).
Ces deux types de données, enregistrement et tableau, n’existent pas vraiment en Python. Pour les tableaux, on s’appuiera sur le type List de Python. Pour les enregistrements, plusieurs solutions sont possibles : les tuples, les dictionnaires ou les classes. Nous préviligerons les classes dans un mode très dégradé.
8.1. Tableau en Python (List) Attention : Nous ne présentons ici qu’un tout petit sous-ensemble des possibilités du tpye List de Python. Le but est en effet de ne présenter que les éléments qui permettent de _simuler_ les tableaux algorithmiques .
Remarque : Pour des tableaux numériques de grande taille, on utilisera le type array de la bibliothèque Numpy qui offre une implémentation efficace.
Définition : Une liste est un agrégat d’éléments qui sont repérés par leur position (ou indice).
Python étant typé dynamiquement, aucun type n’est imposé sur les éléments de la liste qui peuvent donc être hétérogènes.
En algorithmique, quand on déclare un tableau, on précise sa capacité, le nombre maximal d’éléments qu’il pourra stocker, et on est souvent amené à gérer une taille effective, le nombre d’éléments réellement stockés dans le tableau. En Python, le programmeur n’a pas à se préoccuper de la capacité car l’espace de stockage des éléments sera agrandi quand de nouveaux éléments seront ajoutés. Il obtient la taille effective de la liste (le nombre d’éléments qu’elle contient) grâce à la fonction len().
TODO : montrer plutôt les opérateurs du langage : + et += plutôt que append et extend
8.1.1. En Python >>> l = [] # liste vide >>> type(l) <class 'list'> >>> l [] >>> l.append('b') # ajout d'un élément à la fin >>> l ['b'] >>> 'a' in l # teste l'appartenance de 'a' à la liste False >>> l.extend(['c','d','d','e']) # ajout des éléments d'une autre ... # liste à la fin (concaténation) >>> l ['b', 'c', 'd', 'd', 'e'] >>> l.insert(0, 'a') # ajout d'un élément à une position donnée >>> l ['a', 'b', 'c', 'd', 'd', 'e'] >>> 'a' in l # teste l'appartenance de 'a' à la liste True >>> len(l) # nombre d'éléments dans la liste 6 >>> l[2] # accès à un élément par sa position 'c' >>> l[2:4] # accès à une sous-liste ['c', 'd'] >>> del l[3] # suppression d'un élément (par sa position) >>> l ['a', 'b', 'c', 'd', 'e'] >>> l[3] = 'D' # modification d'un élément >>> l ['a', 'b', 'c', 'D', 'e'] >>> max(l) # maximum de la liste (ordre lexicographique) 'e' >>> min(l) # minimum de la liste (ordre lexicographique) 'D' >>> l.reverse() # inverse l'ordre des éléments dans la liste >>> l ['e', 'D', 'c', 'b', 'a'] >>> l.sort() # trier la liste (ordre lexicographique) >>> l ['D', 'a', 'b', 'c', 'e'] >>> [6, 7, 6, 7, 6].count(6) # compter le nombre d'occurence ... # d'un élément 3 >>> list( (1,2,3) ) # contruire une liste (ici à partir d'un tuple) [1, 2, 3]......
- ......................................................................
.......................................................................
.......................................................................
....................................................................... ....................................................................... .......................................................................
....................................................................... ....................................................................... |
Structures de données - Historique (+)
Définition graphique
Titre de Votre Image 1
Titre de Votre Image 2
Titre de Votre Image 3
{{{AutresMedias}}}
Concepts ou notions associés
Structures de données - Glossaire / (+)
Exemples, applications, utilisations
................................................................................ ................................................................................ ................................................................................
................................................................................ ................................................................................ ................................................................................ |
Erreurs ou confusions éventuelles
Erreur: Croire que
- .........................................
- .........................................
Confusion possible ou glissement de sens
- Confusion entre ....... - ........
- Confusion entre ....... - ........
Erreur fréquente:
- ....................
Questions possibles
Liaisons enseignements et programmes
Idées ou Réflexions liées à son enseignement
Aides et astuces
- ..................
- .................
- ..................
- .................
Education: Autres liens, sites ou portails
- ..................
- ..................
- ..................
Bibliographie
Pour citer cette page: (de données)
ABROUGUI, M & al, 2022. Structures de données. In Didaquest [en ligne]. <http:www.didaquest.org/wiki/Structures_de_donn%C3%A9es>, consulté le 21, novembre, 2024
- ..................
- ..................
- ..................
- ..................
