Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_fiches_revisions:structure_des_donnees:interface_implementation [2022/05/13 11:10]
gh
+++ les_fiches_revisions:structure_des_donnees:interface_implementation [2023/02/06 09:42] (Version actuelle)
tb
@@ Ligne 3: / Ligne 3: @@
-Nous allons à travers des exemples voir ce qu'est l'interface d'une structure de données.
+== 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 à u**n élément spécifique**, mais ils peuvent être **lents pour insérer ou supprimer des éléments**. Les listes liées, d'autre part, sont plus **lentes pour accéder à un élément spécifique**, mais elles sont plus **rapides pour insérer ou supprimer des éléments**.
-== Définition : Structure de données abstraites==
+== Définition : Interfaces ==
-Un type abstrait ou une structure de données abstraite est une spécification mathématique d'un ensemble de données et de l'ensemble des opérateurs associés.\\
+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'implémentation**. Par exemple, une interface pour un téléphone mobile pourrait **décrire les fonctions telles que passer un appel, envoyer un message texte et accéder à internet**, **mais ne décrirait pas comment ces fonctions sont implémentées** (par exemple, en utilisant une carte SIM ou une connexion Wi-Fi).
-On qualifie d'abstrait ce type de données car il correspond à un cahier des charges qu’une structure de données doit ensuite implémenter.
+{{:les_fiches_revisions:structure_des_donnees:photo_nsi.jpg?400|}}
-\\
-Nous allons aborder deux structures de données abstraites : la pile et la file.
-=====Un premier exemple : la pile=====
+== Définition : Implémentations ==
-===Pile===
+**L'implémentation** est le processus de **création d'un objet ou d'une classe** qui respecte une certaine interface. Cela peut impliquer la création de variables de données pour stocker les données de l'objet et la définition de fonctions pour manipuler ces données. Par exemple, **pour implémenter une interface de téléphone mobile, un développeur pourrait créer une classe qui contient des variables pour stocker le numéro de téléphone**, **le nom du contact, et d'autres informations liées aux contacts, et définir des fonctions pour ajouter, supprimer, et afficher les contacts**.
-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://monlyceenumerique.fr/nsi_terminale/sd/img/pile.jpg?400| }}
-\\
-===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,P).
-{{https://monlyceenumerique.fr/nsi_terminale/sd/img/prop3.jpg?100|}}
-===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'élément a de pile P1 est la pile P2.
-  On notera cet opérateur dépiler(P1), elle transforme la pile initiale et renvoie l'élément dépiler.
-{{https://monlyceenumerique.fr/nsi_terminale/sd/img/prop4.jpg?100|}}
@@ Ligne 70: / Ligne 30: @@
 ==Interface de la pile==
-L'interface de la structure pile est l'ensemble des opérateurs vu précédemment :
-  ·vide()
-  ·estVide(P)
-  ·empiler(a,P)
-  ·depiler(P)
 ==Interface de la file==
@@ Ligne 81: / Ligne 37: @@
 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.
@@ Ligne 91: / Ligne 46: @@
 {{https://monlyceenumerique.fr/nsi_terminale/sd/img/file.jpg?400}}
-===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'arbre peut avoir un ou plusieur enfants mais un seul parent(sauf le noeud racine qui n'a pas de parents
-  ·La file est vide si sa queue est vide. On notera dans ce cours F=vide().
+==EXEMPLES d'arbre==
-===Propriété 2===
+{{:les_fiches_revisions:structure_des_donnees:arbre.png?400|}}
-==Enfiler un élément dans la file()==
-  ·la nouvelle file obtenue à l'enfilement de a sur F est la file :
-       ·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 de la structure de file est composée de :
-.vide()
-.estVide(F)
-.enfiler(a,F)
-.defiler(F)
 =====Implémentation=====
@@ Ligne 131: / Ligne 60: @@
 ===Définition===
-==Implémentation==
-Implémenter une structure de données à travers une structure existante c'est écrire les éléments de l'interface à l'aide des outils proposées par la structure de données existante.
-==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===
@@ Ligne 143: / Ligne 65: @@
   Soit P une pile. On dispose d'un tableau nommé T avec n emplacements.
   Il est possible d’implémenter la pile P d’au plus n éléments avec le tableau T.
-  Le tableau possède un attribut sommet(P) qui indexe l’élément le plus récemment inséré.
+  Le tableau possède un attribut sommet(P) qui indexe l’élément le plus récemment inséré.
   La pile est constituée des éléments T[1..sommet(P)], tous ceux compris entre T[1],
   l’élément situé à la base de la pile, et T[sommet(P)], l’élément situé au sommet.
-La donnée de la pile se constitue donc de la donnée de T
+  La donnée de la pile se constitue donc de la donnée de T
-et de la valeur de sommet(P).
+  et de la valeur de sommet(P).
+===Implémentation des files avec des tableaux===
+  On dispose d'un tableau nommé T avec n emplacements.
+  Il est possible d’implémenter une file F
+  d’au plus n éléments avec le tableau T.
+  Le tableau possède un attribut tete(F)
+  qui indexe l’élément de tête et un attribut queue(F) qui indexe l'emplacement où un nouvel
+  élément sera inséré. T[queue(F)] est vide au sens de la file.
+  Avec cette implémentation T[n+1] doit pointer vers T[1] au sens de la file.
+  Une façons de visualiser cette implémentation est un tableau circulaire où le début
+  du tableau et la fin du tableau seraient reliés.
+  Les éléments de la file se trouvent aux emplacements tete(F),
+  tete(F)+1, . . . , queue(F)−1, après quoi l’on « boucle » : l’emplacement 1 suit immédiatement
+  l’emplacement n dans un ordre circulaire.
+  Dans cette implémentation la queue est vide.

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page