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 [2022/11/16 11:08] tb [Structures de données, interfaces et implémentation] |
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 ====== |
| - | Nous allons | + | == Définition : Structure de données == |
| + | Les **structures de données** sont des moyens de **stocker et de manipuler les données de manière efficace**. Il existe de nombreux types de structures de données, chacun ayant ses propres avantages et inconvénients. Par exemple, les **tableaux** sont **très rapides** pour accéder | ||
| - | == Définition : Structure de données abstraites== | + | == Définition : Interfaces |
| - | Un type abstrait | + | Les **interfaces** décrivent les **fonctionnalités d'un objet** |
| - | On qualifie d' | + | |
| + | {{: | ||
| - | \\ | ||
| - | Nous allons aborder deux structures de données abstraites : la pile et la file. | ||
| - | =====Un premier exemple | + | == Définition |
| - | ===Pile=== | + | **L' |
| - | Une pile est : | ||
| - | |||
| - | · soit vide ;\\ | ||
| - | · soit une cellule à deux champs, un champ contenant un élément, et un champ contenant une autre pile.\\ | ||
| - | On dit que cette structure de donnée est de type LIFO : Last In First Out | ||
| - | |||
| - | On pourra représenter une pile de la manière suivante :\\ \\ | ||
| - | {{https:// | ||
| - | |||
| - | \\ | ||
| - | ===Propriété 1 === | ||
| - | |||
| - | ==Créer une Pile vide== | ||
| - | |||
| - | ·La structure pile dispose d'un opérateur pour créer une pile P vide. On notera dans ce cours P=vide(). | ||
| - | |||
| - | ===Propriété 2=== | ||
| - | |||
| - | ==La Fonction estVide()== | ||
| - | |||
| - | ·estVide(P)=Vraie si P est vide | ||
| - | ·estVide(P)=Faux si P n'est pas vide | ||
| - | | ||
| - | ===Propriété 3=== | ||
| - | |||
| - | ==Empiler un élément en haut de pile== | ||
| - | ·Soit P une pile, la pile obtenue en empilant un élément a en haut de P est la pile (a,P). | ||
| - | On notera cet opérateur empiler(a, | ||
| - | {{https:// | ||
| - | |||
| - | ===Propriété 4=== | ||
| - | |||
| - | ==Dépiler un élément== | ||
| - | ·Soit P1, P2 deux piles et a le haut de la pile P1, | ||
| - | la pile obtenue en dépilant l' | ||
| - | On notera cet opérateur dépiler(P1), | ||
| - | |||
| - | | ||
| - | {{https:// | ||
| Ligne 70: | 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 81: | 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 91: | Ligne 46: | ||
| {{https:// | {{https:// | ||
| - | ===Propriété 1 === | ||
| - | ==Créer une File vide== | + | ===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' | ||
| - | ·La file est vide si sa queue est vide. On notera dans ce cours F=vide(). | + | ==EXEMPLES d' |
| - | ===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' | ||
| - | |||
| - | | ||
| - | | ||
| - | | ||
| - | | ||
| =====Implémentation===== | =====Implémentation===== | ||
| Ligne 131: | 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 160: | 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.1668593332.txt.gz · Dernière modification: 2022/11/16 11:08 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
