Structures de données

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

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

Les piles (LIFO)

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.

Les files (FIFO)

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.

Les dictionnaires en Python

Un dictionnaire est une structure de données permettant de stocker plusieurs éléments. On parle aussi de tableau associatif.

Principe de fonctionnement

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

Exemple concret

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). Cette structure suit le principe que le dernier élément ajouté est le premier à être retiré.

Fonctionnement d'une pile

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.

Méthodes principales

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'élément 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). Cette structure suit le principe que le premier élément ajouté est le premier à être retiré.

Fonctionnement d'une file

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.

Méthodes principales

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.

Les arbres en informatique

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

Organisation des données dans un arbre

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.

Arbre binaire

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

Profondeur et hauteur

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.

Relation avec les graphes

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

Définition d'un graphe

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.

Éléments constitutifs d'un graphe

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.

Parcours d'un graphe

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.