Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révision Les deux révisions suivantes | ||
les_fiches_revisions:structure_des_donnees:interface_implementation [2023/02/05 23:18] tb |
les_fiches_revisions:structure_des_donnees:interface_implementation [2023/02/05 23:23] tb |
||
---|---|---|---|
Ligne 18: | Ligne 18: | ||
L' | L' | ||
- | |||
- | |||
- | |||
- | | ||
- | {{https:// | ||
Ligne 47: | Ligne 42: | ||
Une file est: | Une file est: | ||
- | ·soit vide | + | |
- | ·soit une cellule à trois temps, un champ queue et un champ contenant une file. | + | |
| | ||
Une structure de File fonctionne sur le principe premier entré − premier sorti (comme les files d’attentes à un guichet) FIFO : First In First Out. | Une structure de File fonctionne sur le principe premier entré − premier sorti (comme les files d’attentes à un guichet) FIFO : First In First Out. | ||
Ligne 57: | Ligne 51: | ||
{{https:// | {{https:// | ||
- | ===Propriété 1 === | ||
- | ==Créer une File vide== | ||
- | |||
- | ·La file est vide si sa queue est vide. On notera dans ce cours F=vide(). | ||
- | |||
- | ===Propriété 2=== | ||
- | |||
- | ==Enfiler un élément dans la file()== | ||
- | |||
- | ·la nouvelle file obtenue à l' | ||
- | ·de tête celle de F | ||
- | ·de queue a | ||
- | ·et de troisième champ enfiler(troisième champ de F, queue de F). | ||
- | | ||
- | Cet opérateur est récursif | ||
- | | ||
- | ===Propriété 3=== | ||
- | |||
- | ==Défiler un élément de la file== | ||
- | ·la nouvelle file obtenue par défilement de F est la file: | ||
- | ·de tête , la tête du troisième champ de F ; | ||
- | ·de queue celle de F ; | ||
- | ·et de troisième champ défiler(du troisième champ de F) . | ||
- | Cet opérateur est récursif. | ||
- | Cet opérateur transforme F et renvoie la tête de F. | ||
- | |||
- | ===Interface de la file=== | ||
- | |||
- | L' | ||
- | |||
- | | ||
- | | ||
- | | ||
- | | ||
===Interface d' un arbre=== | ===Interface d' un arbre=== | ||
Un arbre est une structure de données hiérachique qui est constitué d'un noeud racine tout en haut et de plusieurs sous-arbres.Chaque noeud de l' | Un arbre est une structure de données hiérachique qui est constitué d'un noeud racine tout en haut et de plusieurs sous-arbres.Chaque noeud de l' | ||
Ligne 99: | Ligne 59: | ||
{{: | {{: | ||
- | il existe de nombreux types d' | + | |
- | * Arbres binaires : chaque nœud d'un arbre binaire a au plus deux enfants. | + | |
- | * Arbres Tries : un arbre Trie (aussi appelé "arbre de préfixe" | + | |
- | de manière organisée de manière à faciliter la recherche de mots spécifiques. | + | |
- | * Arbre de décision : un arbre de décision est utilisé pour représenter les possibilités d'une | + | |
- | décision basée sur un certain nombre de critères. Chaque nœud de l' | + | |
- | décision, et les sous-arbres représentent les différentes options pour chaque critère. | + | |
- | * Arbre de répartition : un arbre de répartition peut être utilisé pour organiser les objets dans | + | |
- | un espace de jeu de manière à faciliter la recherche d' | + | |
- | | + | |
=====Implémentation===== | =====Implémentation===== | ||
Ligne 114: | Ligne 65: | ||
===Définition=== | ===Définition=== | ||
- | ==Implémentation== | ||
- | |||
- | Implémenter une structure de données à travers une structure existante c'est écrire les éléments de l' | ||
- | |||
- | ==Tableau== | ||
- | |||
- | Un tableau est une structure de données avec une taille fixe où chacune des cases est indexée. On peut accéder à une case connaissant son index. | ||
===Implémentation des piles avec des tableaux=== | ===Implémentation des piles avec des tableaux=== |