Langage Z (Structures de données)

 

Structures

Tableaux

Listes linéaires chaînées

Listes linéaires chaînées bilatérales

Files d'attente

Piles

Arbres de recherche binaire

Arbres de recherche m-aire

Fichiers

 

 

Structures      

 

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;

 

Tableaux

 

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 ;

Listes linéaires chaînées

 

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;

 

Files d'attente

 

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;

Piles

 

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;

 

Arbres de recherche binaire

 

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;

 

Arbres de recherche m-aire

  

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;

 

Fichiers

 

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