Machines abstraites

Vecteurs Listes linéaires chaînées
Listes linéaires chaînées bidirectionnelle Files d'attente   
Piles     Arbres de recherche binaire
Arbres de recherche m-aire Structures
Fichiers

 

Définition : Un vecteur de dimension N peut être vu comme une application de l’ensemble I= [1, Max1]X [1, Max2].....X[1, MaxN] vers un ensemble de valeurs. Un vecteur est donc un ensemble de couples (indice1, a), (indice2, b), ....., (indiceN, e) dont les premiers éléments sont appelés les indices et appartiennent à l’ensemble I. Une machine simple sur les vecteurs consiste à agir uniquement sur un élément, c’est à dire le consulter ou le modifier. De plus, les tableaux peuvent être statiques ou dynamiques.

Opérations :

ELEMENT ( T [i, j, ...] ) : Accès à l'élément T[i, j, ...] du vecteur T.

AFF_ELEMENT ( T [i, j, ...], Val ) : Affecter à l'élément T[i, j, ...] la valeur Val.

ALLOC_TAB (T) : Allocation d’un tableau.

LIBER_TAB(T) : Libération d’un tableau

Définition : Une liste linéaire chaînée est un ensemble de maillons alloués dynamiquement (c’est à dire pendant l’exécution d’un programme) chaînés entre eux. Un maillon contient en général deux champs : l’information et une adresse. C ‘est l’utilisateur qui crée la liste, qui la modifie en rajoutant ou supprimant des maillons, qui la parcourt en vu de faire un traitement donné. Une machine sur les listes linéaires chaînées consiste donc à offrir à l’utilisateur des opérations pour l’allocation dynamique de maillons, des opérations pour remplir un maillon ( information et chaînage) et des opérations pour consulter le contenu d’un maillon. La machine agit uniquement au niveau d’un maillon.

Opérations :

ALLOUER ( P ) : Créer un maillon et retourne son adresse dans P.

LIBERER ( P ) : Libèrer le noeud d'adresse P.

SUIVANT ( P ) : Accès au champ 'Adresse' du noeud référencé par P.

VALEUR ( P ) : Accès au champ 'Valeur' du noeud référencé par P.

AFF_ADR ( P, Q ) : Affecter au champ 'Adresse' du noeud référencé par P, l'adresse Q.

AFF_VAL( P, Val ) : Affecter au champ 'Valeur' du noeud référencé par P, la valeur Val.

Définition : Une liste bilatérale est une liste linéaire chaînée que l’on peut parcourir dans les deux sens. Une machine sur les listes bilatérales est définie de la même manière que celle définie sur les listes linéaires chaînées, sauf qu’un maillon au lieu de contenir une seule adresse, il en contient deux. En conséquence, on remplace la fonction AFF_ADR par AFF_ADRG et AFF_ADRD par exemple et rajouter la fonction PRECEDENT.

Opérations :

ALLOUER ( P ) : Créer un maillon et retourne son adresse dans P.

LIBERER ( P ) : Libèrer le noeud d'adresse P.

SUIVANT ( P ) : Accès au champ 'Adresse droit' du noeud référencé par P.

PRECEDENT ( P ) : Accès au champ 'Adresse gauche' du noeud référencé par P.

VALEUR ( P ) : Accès au champ 'Valeur' du noeud référencé par P.

AFF_VAL( P, Val ) : Affecter au champ 'Valeur' du noeud référencé par P, la valeur Val.

AFF_ADRD ( P, Q ) : Affecter au champ 'Adresse droite' du noeud référencé par P, l'adresse Q

AFF_ADRG ( P, Q ) : Affecter au champ 'Adresse gauche' du noeud référencé par P, l'adresse Q.

 

Définition : Une file d’attente obéit au principe ‘FIFO’ : First In First Out ( Premier rentré, premier servi). C’est une collection d’éléments telle que tout nouveau élément est inséré à la fin et tout retrait d’élément se fait au début. Une machine sur les files d’attente est donc dotée de ses deux opérations fondamentales auxquelles on rajoute quelques opérations de moindre importance permettant d’initialiser ou de tester l’état d’une file d’attente à tout moment ( File d’attente vide ou pleine ). La machine agit sur la collection entière.

Opérations :

CREERFILE ( F ) : Créer une file d'attente vide.

FILEVIDE ( F) : Tester si une file d'attente est vide.

ENFILER ( F, Val ) : Enfiler (rajouter en queue) la valeur Val dans la file d'attente F.

DEFILER ( F, Val ) : Défiler ( récupérer de la tête ) une valeur pour la mettre dans Val.

Définition : Une pile obéit au principe ‘LIFO’ : Last In First out ( Dernier rentré, Premier servi). C’est une collection d’éléments telle que tout nouveau élément est inséré au début et tout retrait d’élément se fait au début. Une machine sur les piles est donc dotée de ces deux opérations fondamentales auxquelles on rajoute quelques opérations permettant d’initialiser ou de tester l’état d’une pile à tout moment ( pile vide ou pleine). La machine agit sur la collection entière.

Opérations :

CREERPILE ( P ) : Créer une pile vide.

PILEVIDE ( P ) : Tester si une pile est vide.

EMPILER ( P, Val ) : Empiler (rajouter au sommet) la valeur Val dans la pile P.

DEPILER ( P, Val ) : Dépiler ( récupérer du sommet ) une valeur pour la mettre dans Val.

Définition : Un arbre de recherche binaire permet de représenter un ensemble de données muni d’une relation d’ordre. Toutes les données se trouvant dans le sous arbre gauche de tout noeud avec l’information x sont inférieures à x, toutes les données se trouvant dans le sous arbre droit de tout noeud avec l’information x sont supérieures à x. Comme c’est une structure de données dynamique (composé d’un ensemble de noeuds formant un graphe dans lequel tout noeud a au plus un prédécesseur et au plus deux successeurs ) une machine consiste à fournir des opérations pour faire l’allocation dynamique, des opérations pour remplir un noeud et des opérations pour consulter un noeud. Intuitivement, un noeud est composé de 3 champs : l’information et deux champs adresses fournissant les fils gauche et droit. . La machine agit uniquement au niveau du noeud.

Opérations :

CREERNOEUD ( Val ) : Créer un noeud avec l'information Val et retourne l'adresse du noeud.

Les autres champs sont à NIL.

LIBERERNOEUD ( P ) : Libèrer le noeud d'adresse P.

FG ( P ) : Accès au champ Fils gauche du noeud référencé par P.

FD ( P ) : Accès au champ Fils droit du noeud référencé par P.

PERE ( P ) : Accès au champ Père du noeud référencé par P.

INFO ( P ) : Accès au champ Info du noeud référencé par P.

AFF_FG ( P, Q ) : Affecter au champ Fils gauche du noeud référencé par p, l'adresse Q

AFF_FD ( P, Q ) : Affecter au champ Fils droit du noeud référencé par p, l'adresse Q

AFF_PERE ( P, Q ) : Affecter au champ Père du noeud référencé par p, l'adresse Q

AFF_INFO( P, Val ) : Affecter au champ Info du noeud référencé par p, la valeur Val

Définition : Un arbre de recherche m-aire permet de représenter un ensemble de données muni d’une relation d’ordre. C’est une généralisation de l’arbre de recherche binaire. Au lieu d’avoir une information et deux champs adresse, on a p adresses et (p-1) informations auquel cas l’arbre de recherche m-aire est dit d’ordre p. Intuitivement, un noeud a la forme suivante : (a1, v1, a2, v2, ......, vp-1, ap). Toutes les données se trouvant dans le sous arbre de racine a1 sont inférieures à v1, toutes les données se trouvant dans le sous arbre de racine a2 sont supérieures à v1 et inférieures à v2, etc. Une machine consiste à fournir des opérations pour faire l’allocation dynamique, des opérations pour remplir un noeud et des opérations pour consulter un noeud. La machine agit uniquement au niveau du noeud.

Opérations :

CREERNOEUD ( Val ) : Créer un noeud avec l'information Val et retourne l'adresse du noeud.

Les autres champs sont à NIL.

LIBERERNOEUD ( P ) : Libèrer le noeud d'adresse P.

FILS ( P, I ) : Accès au champ I-ième fils du noeud référencé par P.

PERE ( P ) : Accès au champ Père du noeud référencé par P.

INFOR ( P, I ) : Accès au I-ième champ Info du noeud référencé par P.

AFF_FILS ( P, I, Q ) : Affecter au champ I-ième fils du noeud référencé par P, l'adresse Q.

AFF_PERE ( P, Q ) : Affecter au champ Père du noeud référencé par P, l'adresse Q.

AFF_INFOR( P, I, Val ) : Affecter au I-ième champ Information du noeud référencé par P, la valeur Val.

DEGRE(P) : Nombre d’informations rangées dans le noeud référencé par P.

AFF_DEGRE(P, n) : Affecter au champ Degre du noeud référencé par P la valeur n.

Définition : une structure est un ensemble d’éléments hétérogènes. Un élément d’une structure peut être un scalaire ou un vecteur à une dimension de scalaires. Une machine simple sur les structures consiste à récupérer le i-ème champs ou d’affecter une valeur dans son i-ème champ.

Les structures peuvent être statiques ou dynamiques. Dans ce dernier cas, deux opérations sont ajoutées à la machine abstraite, permettant leur allocation et libération.

Opérations

STRUCT(S, i) : accès au i-ème champs.

AFF_STRUCT(S, i, Val) : affecter la valeur val au i-ème champ.

ALLOC_STRUCT(S) : Allocation d’une structure

LIBER_STRUCT(S) : Libération d’une structure

 

Définition : un fichier est ensemble de structures, généralement rangées sur le disque. Les structures peuvent être des articles(niveau utilisateur) ou des blocs(niveau concepteur). Le fichier renferme une structure particulière (entête) nécessaire pour la conception de structures de fichiers. Une machine abstraite sur les fichiers consiste à fournir des opérations permettant de faire l’accès séquentiel et l’accès direct.

Opérations

OUVRIR (Flogique, Fphysique, Mode) : ouvrir le fichier logique et l’associer au fichier physique

en précisant si le fichier est nouveau ('N') ou ancien ('A').

FERMER(Flogique) : fermer le fichier.

LIRESEQ (Flogique, V) : Lecture dans la variable V l'article se trouvant à la position courante.

ECRIRESEQ (Flogique, V) : Ecriture de l'article V à la position courante.

LIREDIR (Flogique, V, n) : lecture du n-ième article du fichier.

ECRIREDIR (Flogique, V, n) : écriture de l'article V à la n-ième position.

RAJOUTER (Flogique, V) : rajoute un article en fin du fichier

FINFICH (Flogique) : prédicat égal à vrai si la fin du fichier est rencontrée, faux sinon.

ALLOC_BLOC(Flogique) : position d'un bloc ( ou article ) dans laquelle on pourra écrire.

ENTETE (F, i) : récupérer la i-ème caractéristique du fichier.

AFF_ENTETE(F, i, v) : affecter v comme i-ème caractéristique du fichier.