Structures de données

Autres Fiches Conceptuelles

Posez une Question

(+)

Votre Publicité sur le Réseau

Traduction

Structures de données (Français) / Concept en Anglais (Anglais) / Concept en Arabe (Arabe)

(+)

Traductions

Définition

Domaine, Discipline, Thématique

(+)

Pensée computationnelle / Algorithmique et programmation / Structures de donnés et implémentation Python /

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é.

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

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]......

• ......................................................................

....................................................................... .......................................................................

(+)

Enregistrement (struct) Définition algorithmique Définition algorithmique : Un enregistrement est un type correspondant à un agrégat d’élément de types éventuellement différent auxquels ont accède grâce à un nom. Exemple :. On peut définir un note comme étant une valeur (nombre), un coefficient (nombre) et une matière (chaîne de caratères). Les noms « valeur », « coefficient » et « matière » sont alors les champs de l’information et permettent d’accèder à l’une des données d’une note. En Python Le type enregistrement n’utilise pas. On peut utiliser les tuples, les dictionnaire (dict) ou les classes. Les tupes Définition : Un tuple est une valeur composée de plusieurs valeurs. note de valeur 15, coefficient 1.5 en programmation >>> n1 = (15, 1.5, "programmation") >>> n1 (15, 1.5, 'programmation') >>> _, c, _ = n1 # récupérer le coefficient >>> print(c) 1.5 >>> v, _, m = n1 # récupérer la valeur v et la matière m >>> n1 = (v, 2.5, m) # pour changer le coefficient en 2.5 >>> n1 (15, 2.5, 'programmation'). ...................................................................... ....................................................................... .......................................................................

Structures de données - Historique (+)

Définition graphique

Carte structure des données

• 

  Choix SD

• 

  Voir CmapCloud

• 

  Les structures de données en IA.

{{{AutresMedias}}}

Concepts ou notions associés

(+)

Les variables simples / Les variables complexes / Les types des variables / Implémentation Python / Objets mutables / Objets immutables /

Structures de données - Glossaire / (+)

Exemples, applications, utilisations

Définition Dans le tableau, tous les éléments ont la même taille mémoire. Nombre d’élément : n, taille d’un élément t : T[0] T[1] T[2] . . . T[n-1] On suppose que le tableau commence à l’adresse d T[0] occupe les cases d à d + t − 1 ; T[1] occupe les cases d + t à d + 2t − 1 ; T[i] occupe les cases d + it à d + (i + 1)t − 1 ; Le tableau entier occupe les cases d à d + nt − 1. Note : indirection (pointeur) possible si taille variable (par exemple classe virtuelle). ............................................................................... ................................................................................ ................................................................................ ................................................................................ (+)

Erreurs ou confusions éventuelles

Erreur: Croire que

• Le type caractère n'existe pas en python
• Le type tableau d'un seul type n'existe pas eb python

Confusion possible ou glissement de sens

• Confusion entre Objet mutable - Objet immutable
• Confusion entre Type - Constructeur de type

Erreur fréquente:

• Passage par valeur et passage par adresse

(+)

Questions possibles

• Est ce qu'on enseigne les structures de données avant ou après les structures de contrôles ?
• Comment faire avec le typage dynamique de Python ?
• Est ce qu'on sait dire Merci ?

(+)

Liaisons enseignements et programmes

Idées ou Réflexions liées à son enseignement

• https://cmapcloud.ihmc.us/cmaps/myCmaps.html

• Structures de données

• ..................

• .................

(+)

Aides et astuces

• ..................

• .................

• ..................

• .................

Education: Autres liens, sites ou portails

• Prof.tn Plateforme d'apprentissage en ligne (Interdisciplinarité : Connexion anonyme).
• https://didactique.info/formation/course/view.php?id=412 (Connexion anonyme)
• .

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 24, novembre, 2024

• ..................
• ..................
• ..................
• ..................

Donnez votre avis sur les fiches conceptuelles