Wiki NSI

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

Nous allons aborder deux structures de données abstraites : la pile et la file.

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 :

·La structure pile dispose d'un opérateur pour créer une pile P vide. On notera dans ce cours P=vide().

·estVide(P)=Vraie si P est vide
·estVide(P)=Faux si P n'est pas vide

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

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

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.

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