Langage Z (Structures de données)
Une structure est un ensemble d'éléments hétérogènes.
Une structure peut être simple, c'est à dire composée uniquement de scalaires.
Une structure peut être complexe, c'est à dire composée de scalaires et/ou de vecteurs à une dimension de scalaires.
Une structure peut être statique ou dynamique.
Définition des structures
[SOIT/SOIENT] <Li> Sep
[STRUCTURE] ( Type1, type2, ... ) [DYNAMIQUE]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Typei est soit un type scalaire soit un tableau à une dimension de scalaires.
Exemples
S1 : (ENTIER, CHAINE) ;
S2 UNE STRUCTURE ( CHAINE, ENTIER, BOOLEEN) ;
S3 UN ( ENTIER, VECTEUR(5) DE CHAINE) DYNAMIQUE;
Un tableau est un ensemble d'éléments homogènes.
Un tableau ( ou vecteur) peut être simple, c'est à dire composé uniquement de scalaires.
Un tableau peut être complexe, c'est à dire composé de structures simples.
Un tableau peut être statique ou dynamique.
Définition des tableaux
[SOIT/SOIENT] <Li> sep
VECTEUR(Dim1, Dim2, ... )
DE Typec DE Typec DE .... DE Types [DYNAMIQUE]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans {:, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
V1 UN TABLEAU (5) DYNAMIQUE;
V2, V3 DES VECTEURS (3, 8) DE CHAINES ;
Une liste linéaire chaînée est un ensemble de maillons alloués dynamiquement.
Un élément possède deux champs : Valeur et Adresse.
Le champ 'Valeur' peut être quelconque.
Définition des listes
[SOIT/SOIENT] <Li> Sep LISTE [ DE Typec DE Typec DE .... ] [ DE Types ]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans {:, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
L1 UNE LISTE DE (CHAINE, ENTIER);
L2 UNE LISTE DE PILE DE CHAINE ;
L3 UNE LISTE DE CHAINES;
Listes linéaires chaînées bilatérales
Une liste linéaire chaînée bilatérale est un ensemble de maillons alloués dynamiquement qui peut être parcourue dans les deux sens.
Un élément possède trois champs : Valeur, adresse gauche, adresse droite.
Le champ 'Valeur' peut être quelconque.
Définition des listes bilatérales
[SOIT/SOIENT] <Li> Sep LISTEBI [DE Typec DE Typec DE .... ][ DE Types]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
Lb1 UNE LISTEBI DE (CHAINE, ENTIER);
Lb2 UNE LISTEBI DE PILE DE CHAINE ;
Lb3 UNE LISTEBI DE CHAINES;
Une file d'attente est une collection d'éléments dans laquelle tout nouvel élément est inséré à la fin et tout retrait se fait du début. C’est le principe FIFO : First In First Out
Un élément peut être quelconque
Définition des files d'attente
[SOIT/SOIENT] <Li> Sep FILE [DE Typec DE Typec DE .... ] [DE Types]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
F1 UNE FILE DE (CHAINE, ENTIER);
F2 UNE FILE DE PILE DE CHAINE ;
F3 UNE FILE DE CHAINES;
Une pile est une collection d'éléments dans laquelle tout nouveau élément est inséré à la fin et tout retrait se fait également de la fin. C'est le principe LIFO : Last In First Out.
Un élément peut être quelconque.
Définition des piles
[SOIT/SOIENT] <Li> Sep PILE [DE Typec DE Typec DE .... ][ DE Types]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
P1 UNE PILE DE (CHAINE, ENTIER);
P2 UNE PILE DE PILE DE CHAINE ;
P3 UNE PILE DE CHAINES;
Un arbre de recherche binaire est une structure de données généralement dynamique non linéaire.
Un nœud d'un arbre de recherche binaire contient une information et deux fils.
Structure d'un nœud : (a1, V1, a2)
Toutes les données rangées dans le sous arbre a1 sont strictement inférieures à V1.
Toutes les données rangées dans le sous arbre a2 sont strictement supérieures à V1.
Un élément (nœud) peut être quelconque.
Définition des arbres de recherche binaire
[SOIT/SOIENT] <Li> Sep ARB [DE Typec DE Typec DE .... ] [DE Types]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
A1 UN ARB DE (CHAINE, ENTIER);
A2 UN ARB DE PILE DE CHAINE ;
A3 UN ARB DE CHAINES;
Un arbre de recherche m-aire est une structure de données généralement dynamique non linéaire.
C'est une généralisation de l'arbre de recherche binaire.
Un nœud d'un arbre de recherche m-aire d'ordre p contient (p-1) informations et p fils.
Structure d'un nœud : (a1, V1, a2, V2, ......,Vp-1, ap)
Toutes les données rangées dans le sous arbre a1 sont strictement inférieures à V1.
Toutes les données rangées dans le sous arbre ap sont strictement supérieures à Vp-1.
Toutes les données rangées dans le sous arbre ai ( 1 < i < p ) sont strictement inférieures à Vi et strictement supérieures à Vi+1.
Un élément (nœud) peut être quelconque.
Définition des arbres de recherche m-aire
[SOIT/SOIENT] <Li> Sep ARM (degre) [ DE Typec DE Typec DE ....] [ DE Types]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Typec dans { vecteur, pile, liste, file, pile, arb, listebi, arm }
Types est un scalaire ou une structure simple.
Exemples
M1 UN ARM(4) DE (CHAINE, ENTIER);
M2 UN ARM(2) DE PILE DE CHAINE ;
M3 UN ARM(3) DE CHAINES;
Un fichier est un ensemble d'enregistrements ( ou structures ) rangés généralement sur un disque.
Les enregistrements peuvent être des articles pour un utilisateur.
Les enregistrements peuvent être des blocs pour un concepteur.
Le fichier renferme une partie indispensable ( En-tête )pour la conception de structures de fichiers.
Définition des fichiers
[SOIT/SOIENT] <Li> sep FICHIER DE type
BUFFER <Li>
[ENTETE ( Type1, Type2, .... ) ]
<Li> : Liste d'identificateurs séparés par des virgules.
Sep dans { :, Un, Une, Des }
Une définition de fichier comporte 3 parties :
La première partie (FICHIER) précise la nature des éléments du fichier.
Un élément (article ou bloc) du fichier peut être
- un scalaire
- un vecteur à une dimension de scalaires
- une structure complexe ( pouvant contenir des scalaires et/ou des vecteurs à une dimension de scalaires)
La deuxième partie (BUFFER) définit les variables Tampon utilisées dans les opérations de lecture/écriture.
La troisième partie (ENTETE) définit les caractéristiques du fichier en précisant le type de chacune d'entre elles. Cette partie est facultative et est surtout utilisée pour la création de structures de fichiers. Elle sert à mémoriser toutes les informations utiles pour l'exploitation du fichier.
Exemples
F1 UN FICHIER DE CHAINES BUFFER V1, V2;
F2 UN FICHIER DE VECTEUR(5) DE ENTIER BUFFER V ;
F3 UN FICHIER DE (ENTIER, VECTEUR(3) DE CAR) BUFFER V ENTETE(ENTIER,ENTIER) ;
F4 UN FICHIER DE CAR BUFFER V ENTETE (ENTIER, CHAINE, BOOLEEN) ;