Wiki NSI

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 à un é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.

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).

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.

L'interface d'une structure de données abstraite est l'ensemble des opérateurs nécessaires à la manipulation de cette structure.

L'interface de la structure pile est l'ensemble des opérateurs vu précédemment :

·vide()
·estVide(P)
·empiler(a,P)
·depiler(P)

=La file=

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.

On pourra représenter une file de la manière suivante :

·La file est vide si sa queue est vide. On notera dans ce cours F=vide().

·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

·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.

L'interface de la structure de file est composée de :

 1.vide()
 2.estVide(F)
 3.enfiler(a,F)
 4.defiler(F)

 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

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.

• 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'arbre représente un critère de

  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'objets proches.

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.

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.

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é.  
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
et de la valeur de sommet(P).

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.
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.
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.