Wiki NSI

Outils pour utilisateurs

Outils du site

Piste: • k_plus_proches
les_fiches_revisions:structure_des_donnees:interface_implementation

Différences

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

Lien vers cette vue comparative

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/01/08 18:42]
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 ======
  
  
  
-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== ==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== ==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://monlyceenumerique.fr/nsi_terminale/sd/img/file.jpg?400}} {{https://monlyceenumerique.fr/nsi_terminale/sd/img/file.jpg?400}}
  
-===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'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 : 
- 
-   1.vide() 
-   2.estVide(F) 
-   3.enfiler(a,F) 
-   4.defiler(F) 
 ===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'arbre peut avoir un ou plusieur enfants mais un seul parent(sauf le noeud racine qui n'a pas de parents    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
Ligne 133: Ligne 54:
 {{:les_fiches_revisions:structure_des_donnees:arbre.png?400|}} {{:les_fiches_revisions:structure_des_donnees:arbre.png?400|}}
  
-il existe de nombreux types d'arbres,chacun ayant ses propres caractéristiques et utilisations: +
-  * 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") est utilisé pour stocker des mots  +
-    de manière organisée de manière à faciliter la recherche de mots spécifiques. +
-  * Arbres de recherche binaire : un arbre de recherche binaire est un type d'arbre binaire dans  +
-    lequel les nœuds sont triés de manière telle que l'élément du nœud est plus grand que tous les  +
-    éléments de son sous-arbre gauche et plus petit que tous les éléments de son sous-arbre droit. +
-    Les arbres sont souvent utilisés pour stocker des données de manière organisée et permettre des  +
-    opérations de recherche et de tri rapides.+
  
 =====Implémentation===== =====Implémentation=====
Ligne 147: 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'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=== ===Implémentation des piles avec des tableaux===
Ligne 176: Ligne 82:
   qui indexe l’élément de tête et un attribut queue(F) qui indexe l'emplacement où un nouvel   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.   é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.1673199747.txt.gz · Dernière modification: 2023/01/08 18:42 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
CC Attribution-Noncommercial 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki