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 lensemble 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 à lensemble I. Une
machine simple sur les vecteurs consiste à agir uniquement sur un élément, cest
à 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 dun tableau. LIBER_TAB(T) : Libération dun tableau Définition : Une liste linéaire chaînée est un
ensemble de maillons alloués dynamiquement (cest à dire pendant lexécution
dun programme) chaînés entre eux. Un maillon contient en général deux
champs : linformation et une adresse. C est lutilisateur 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 à lutilisateur des opérations pour lallocation dynamique de
maillons, des opérations pour remplir un maillon ( information et chaînage) et des
opérations pour consulter le contenu dun maillon. La machine agit uniquement au
niveau dun 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 lon 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 quun 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 dattente obéit au principe
FIFO : First In First Out ( Premier rentré, premier servi). Cest
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
dattente est donc dotée de ses deux opérations fondamentales auxquelles on rajoute
quelques opérations de moindre importance permettant dinitialiser ou de tester
létat dune file dattente à tout moment ( File dattente 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). Cest
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 dinitialiser ou de tester létat dune 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 dune relation dordre. Toutes les
données se trouvant dans le sous arbre gauche de tout noeud avec linformation x
sont inférieures à x, toutes les données se trouvant dans le sous arbre droit de tout
noeud avec linformation x sont supérieures à x. Comme cest une structure de
données dynamique (composé dun 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 lallocation dynamique, des opérations pour
remplir un noeud et des opérations pour consulter un noeud. Intuitivement, un noeud est
composé de 3 champs : linformation 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 dune relation dordre. Cest une
généralisation de larbre de recherche binaire. Au lieu davoir une
information et deux champs adresse, on a p adresses et (p-1) informations auquel cas
larbre de recherche m-aire est dit dordre 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 lallocation 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 dinformations 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.
Vecteurs
Listes
linéaires chaînées
Listes
bidirectionnelles
Files d'attente
Piles
Arbres
de recherche binaire
Arbres
de recherche m-aire
Structures
Définition : une structure est un
ensemble déléments hétérogènes. Un élément dune 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 daffecter 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érationsSTRUCT(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 dune structure LIBER_STRUCT(S) : Libération dune 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 laccès séquentiel et laccès direct.
Opérations
OUVRIR (Flogique, Fphysique, Mode) : ouvrir le fichier logique et lassocier 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. |