Outils pour utilisateurs
les_fiches_revisions:structure_des_donnees:interface_implementation
Différences
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 | ||
|
les_fiches_revisions:structure_des_donnees:interface_implementation [2023/02/05 23:18] tb |
les_fiches_revisions:structure_des_donnees:interface_implementation [2023/02/06 09:42] (Version actuelle) tb |
||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| - | ====== Structures de données, interfaces et implémentation ======**thomas brosseau** | + | ====== Structures de données, interfaces et implémentation ====== |
| Ligne 9: | Ligne 8: | ||
| == Définition : Interfaces == | == Définition : Interfaces == | ||
| - | Les interfaces décrivent les fonctionnalités d'un objet ou d'une classe sans décrire comment elles sont implémentées. Cela permet aux développeurs de créer des objets qui respectent une certaine interface sans avoir à connaître les détails de l' | + | Les **interfaces** décrivent les **fonctionnalités d'un objet** ou d'une classe sans décrire comment elles sont implémentées. Cela **permet aux développeurs de créer des objets qui respectent une certaine interface sans avoir à connaître les détails de l' |
| {{: | {{: | ||
| Ligne 16: | Ligne 15: | ||
| == Définition : Implémentations == | == Définition : Implémentations == | ||
| - | L' | + | **L' |
| - | |||
| - | |||
| - | |||
| - | | ||
| - | {{https:// | ||
| Ligne 36: | Ligne 30: | ||
| ==Interface de la pile== | ==Interface de la pile== | ||
| - | L' | + | |
| - | ·vide() | + | |
| - | ·estVide(P) | + | |
| - | ·empiler(a, | + | |
| - | ·depiler(P) | + | |
| | | ||
| ==Interface de la file== | ==Interface de la file== | ||
| Ligne 47: | Ligne 37: | ||
| 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 46: | ||
| {{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 54: | ||
| {{: | {{: | ||
| - | 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 60: | ||
| ===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=== | ||
| Ligne 143: | Ligne 82: | ||
| qui indexe l’élément de tête et un attribut queue(F) qui indexe l' | qui indexe l’élément de tête et un attribut queue(F) qui indexe l' | ||
| élément sera inséré. T[queue(F)] est vide au sens de la file. | élément sera inséré. T[queue(F)] est vide au sens de la file. | ||
| - | La file est constituée des éléments T[tête(F)..queue(F)−1]. | + | |
| Avec cette implémentation T[n+1] doit pointer vers T[1] au sens de la file. | Avec cette implémentation T[n+1] doit pointer vers T[1] au sens de la file. | ||
les_fiches_revisions/structure_des_donnees/interface_implementation.1675635512.txt.gz · Dernière modification: 2023/02/05 23:18 de tb
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial 4.0 International
