Structures de données

• Les tableaux : les éléments sont stockés dans des cases, chaque case possédant un indice pour s’y référer.
  
  
• Les listes : chaque élément possède deux caractéristiques : sa valeur et l’adresse de l’élément qui le suit.
  
  
• Les piles : les éléments sont empilés les uns aux dessus des autres. Ainsi le premier élément auquel on peut accéder est celui situé sur le dessus de la pile (Analogie avec la pile d’assiettes).
  
  
• Les files : les éléments sont empilés les uns derrière les autres. Ainsi le premier élément auquel on peut accéder est celui entré en premier dans la file (analogie avec la file d’attente).
  
  
• Les arbres : organisation des éléments selon une structure hiérarchique.
  
  
• Les dictionnaires : équivalent du tableau associatif. Chaque case contenant un élément est associée à une clé pour pouvoir y accéder.

Les piles et les files sont toutes les deux des structures de données permettant de stocker plusieurs éléments.

Dans une pile, dont l’organisation et la manipulation peuvent être comparées à celles d’une pile d’assiettes, les éléments sont empilés les uns aux dessus des autres. Ainsi le premier élément auquel on peut accéder est celui situé sur le dessus de la pile. On parle alors de LIFO – Last In First Out / Dernier entré Premier sorti.

Dans une file, dont l’organisation et la manipulation peuvent être comparées à celles d’une file d’attente, les éléments sont enfilés les uns derrière les autres. Ainsi le premier élément auquel on peut accéder est celui entré en premier dans la file. On parle alors de FIFO – First In First Out / Premier entré Premier sorti.

Un dictionnaire est une structure de données permettant de stocker plusieurs éléments.

On parle aussi de tableau associatif.

Le principe est d’associer à chaque case contenant un élément, une clé pour pouvoir y accéder.

Chaque élément d’un dictionnaire est défini selon le format « clé / valeur ».

Un dictionnaire de notes contiendra pour chaque note :

• Les clés « Note », « Coefficient » et « Matière »
• Associées aux valeurs « 12 », « 2 » et « Informatique »

Création du dictionnaire en Python

monDictionnaireDeNotes = {"Note": "12", "Coefficient ": "2", "Matière ": " Informatique "}

Pile 

Une pile est une structure de données linéaire, de type LIFO (last in, first out).

Dans une pile, les données sont empilées les unes sur les autres. Lorsque l’on souhaite récupérer les données de la pile, ce sont les dernières données empilées qui sont les premières accessibles.

Les structures de type pile comportent les deux méthodes suivantes :

• empiler : cette méthode sert à ajouter un élément au sommet de la pile ;
• dépiler : cette méthode permet de récupérer l’éliment au sommet de la pile, en le retirant de la pile.

File 

Une file est une structure de données linéaire, de type FIFO (first in, first out).

Dans une file, les données sont placées les unes à la suite des autres : chaque donnée entrant dans la file vient se placer après la précédente. Lorsque l’on souhaite récupérer les données de la file, ce sont les premières données enfilées qui sont les premières accessibles.

Les structures de type file comportent les deux méthodes suivantes :

• enfiler : cette méthode sert à ajouter un élément en dernière position de la file ;
• défiler : cette méthode permet de récupérer le premier élément de la file, en le retirant de la file.

Un arbre est une structure de données non linéaire.

Dans un arbre, les données sont organisées de manière à former une arborescence. L’arbre débute avec une racine, dont partent des branches, qu’on appelle des arêtes. Au bout de chaque arête, on trouve un nœud, qui peut à son tour être le point de départ de nouvelles arêtes. Un nœud, dont aucune arête ne part, s’appelle une feuille. Les nœuds de l’arbre sont organisés en niveaux, et contiennent des données (nombre, texte, liste, dictionnaire, etc.). La taille d’un arbre représente le nombre de nœuds qu’il contient.

Un arbre binaire est un type d’arbre particulier d’arbre : chacun de ses nœuds peut avoir, au maximum, 2 arêtes (il peut dont avoir 0, 1 ou 2 arêtes).

La profondeur d’un nœuds N est le nombre de nœuds à parcourir pour aller du nœud N jusqu’à la racine de l’arbre (racine comprise). La hauteur de l’arbre représente la profondeur maximale atteinte par un nœud de l’arbre.

Les arbres sont des graphes particuliers, qui ne contiennent pas de boucle.

Un graphe est une structure de données non linéaire.

Dans un graphe, les données sont organisées de manière à former un réseau. Les éléments de ce réseau, qui contiennent les données, sont appelés des sommets (ou parfois des nœuds). Les sommets sont interconnectés par des arêtes. Un graphe peut comporter des boucles, qu’on appelle des cycles.

Un algorithme peut parcourir le graphe, en passant d’un sommet à un autre, du moment que ces sommets sont reliés par une arête. Deux sommets reliés par une arête sont nommés sommets voisins. 

Graphes orientés

Un graphe peut être orienté : dans ce cas les arêtes ne peuvent être empruntées que dans un sens, indiqué par une tête de flèche.

Graphes pondérés

Un graphe peut être pondéré : dans ce cas les arêtes ont un poids, qui représente leur importance.