Implémentation des machines Z en C

 

Vecteurs      Statique    Dynamique

Structures    Statique    Dynamique

Listes linéaires chaînées    Statique    Dynamique     

Listes bidirectionnelles     Statique    Dynamique       

Piles      Statique    Dynamique                   

Files d'attente    Statique    Dynamique

Arbres de recherche binaire    Statique    Dynamique

Arbres de recherche m-aire Statique    Dynamique

Fichiers       

 

 

 

Implémentation des vecteurs en C / Statique

 

 

  typedef % type d'un élément du tableau % Typeqq;

  typedef Typeqq Typevect[10];

 

      ELEMENT ( V, I )

 

  int Element (Typevect V , int I )

    {

      return ( V[I] );

    }

 

      AFF_ELEMENT ( V, I, Val )

 

  void Aff_element (Typevect  V,  int  I, int Val )

    {

      V[I] = Val;

    }

 

Exemple 

 

  int I;

  Typevect V ;

 

  main()

    {

      Aff_element(V, 0, 189);

      Aff_element(V, 1, 34);

      Aff_element(V, 2, 56);

      Aff_element(V, 3, 89);

      Aff_element(V, 4, 38);

      Aff_element(V, 5, 156);

 

      for (I= 0; I< 6; I++)

          printf("%d\n",Element( V, I) );

       

      Aff_element(V,3, 99);

      for (I= 0; I< 6; I++)

        printf("%d\n",Element( V, I) );

    }

 

Implémentation des vecteurs en C / Dynamique

 

  typedef % type d'un élément du tableau %    Typeqq    ;

  typedef Typeqq Typevect[10] ;

  typedef Typevect  *Typevect_dyn ;

 

    

     ALLOC_TAB ( T )

 

  void Alloc_tab( Typevect_dyn *T)

    {

      *T = (Typevect_dyn) malloc ( sizeof ( Typevect) );

    }

 

      LIBER_TAB ( T  )

 

  void Liber_tab( Typevect_dyn T)

    {

      free (T);

    }

 

      ELEMENT ( V, I )

 

  int Element (Typevect_dyn T , int I )

    {

      return ( *T[I] );

    }

 

      AFF_ELEMENT ( V, I, Val )

 

  void Aff_element ( Typevect_dyn T,  int  I, int Val )

    {

      *T[I] = Val;

     };

 

Exemple 

 

  #include <alloc.h>

 

  int I;

  Typevect_dyn V ;

 

  main()

    {

      Alloc_tab(&V);

      Aff_element(V, 0, 189);

      Aff_element(V, 1, 34);

      Aff_element(V, 2, 56);

      Aff_element(V, 3, 89);

      Aff_element(V, 4, 38);

      Aff_element(V, 5, 156);

 

      for (I= 0; I< 6; I++)

            printf("%d\n",Element( V, I) );

       

      Aff_element(V,3, 99);

      for (I= 0; I< 6; I++)

        printf("%d\n",Element( V, I) );

      Liber_tab(V);

    }

 

 

Implémentation des structures en C / Statique

 

  typedef %type du premier champs% Type1;

  typedef %type du deuxième champs% Type2;

  ...

  typedef %type du n-ième champs% Typen;

 

  struct Typestruct

    {

      Type1  Champ1;

      Type2  Champ2 ;

     }  ;

 

  struct Typestruct S;

 

      STRUCT (S, I )

 

  Si le type du champ I est un scalaire, STRUCT se traduit par une fonction comme suit :

 

  Typei Structi ( struct Typestruct S )

    {

      return(S.Champi) ;

    }

 

Il ya donc autant de fonctions STRUCT que de champs scalaires dans la structure.

 

Si le type du champ I est n'est pas scalaire, c'est à dire un vecteur à une dimension de scalaires, STRUCT se traduit par une procédure comme suit :

 

  void Struct2 ( struct Typestruct S , Type2 Result)

    {

      int K;

      for (K=0; K<5; K++)

        Result[K] = S.Champ2[K] ;

    }

S'il s'agit d'un tableau de chaînes l'affectation se fait par la fonction "strcpy".

 

     AFF_STRUCT (S, I, Exp)

 

  void Aff_struct1 ( struct Typestruct *S,  Type1 Val )

    {

      struct Typestruct P;

      P = *S;

      P.Champ1 = Val;

      *S = P;

    }

 

Il y a donc autant de fonctions Aff_struct que de champs scalaire dans la structure.

 

Exemple 

 

  Le Z-algorithme suivant :

 

  SOIENT

    S UNE STRUCTURE (ENTIER, VECTEUR(5) DE CHAINES);

    V1, V2 DES VECTEURS(5) DE CHAINES;

    I UN ENTIER ;

  DEBUT

    AFF_ELEMENT(V1[1],'1');

    AFF_ELEMENT(V1[2],'2');

    AFF_ELEMENT(V1[3],'3');

    AFF_ELEMENT(V1[4],'4');

    AFF_ELEMENT(V1[5],'5');

    AFF_STRUCT(S, 1, 5);

    AFF_STRUCT(S, 2,  V1);

    ECRIRE('champ1 = ', STRUCT(S, 1) );

    ECRIRE('champ2 =');

    V2 = STRUCT(S, 2);

    POUR I := 1, 5  ECRIRE( V2[I])  FPOUR

  FIN

 

se traduit en C comme suit :

 

 typedef int Type1  ;

 typedef char String[255];

 typedef String  Type2 [5]  ;

 

 struct Typestruct

   {

     Type1  Champ1;

     Type2  Champ2 ;

    }  ;

 

 struct Typestruct S;

 int I ;

 Type2 V1, V2 ;

 

 Type1 Struct1 ( struct Typestruct S )

     { return(S.Champ1) ;}

   

 

  void Struct2 ( struct Typestruct S , Type2 Result)

    {

      int K;

      for (K=0; K<5; K++)

      strcpy(Result[K], S.Champ2[K] );

    }

 

  void Aff_struct1 ( struct Typestruct *S,  Type1 Val )

    {

      struct Typestruct P;

      P = *S;

      P.Champ1 = Val;

      *S = P;

    }

 

 

void Aff_struct2 ( struct Typestruct *S,  Type2 Val )

    {

      int K;

      struct Typestruct P;

      P = *S;

      for (K=0; K<5; K++)

        strcpy(P.Champ2[K], Val[K]);

      *S = P;

    }

 

 main()

  {

    strcpy(V1[0], "1");

    strcpy(V1[1], "2");

    strcpy(V1[2], "3");

    strcpy(V1[3], "4");

    strcpy(V1[4], "5");

    Aff_struct1(&S, 5);

    Aff_struct2(&S, V1);

    printf("champ1 = %d \n", Struct1(S) );

    printf("champ2 = \n");

    Struct2(S, V2);

    for ( I= 0; I<5; I++) printf("%s \n",V2[I])  ;

  }

 

 

Implémentation des structures en C / Dynamique

 

  typedef type du premier champs Type1;

  typedef type du deuxième champs Type2;

  ...

  typedef type du n-ième champs Typen;

 

  struct Typestruct

   {

      Type1  Champ1;

      Type2  Champ2 ;

    }   ;

 

  struct Typestruct *S;

 

      ALLOC_STRUCT (S)

 

  void Alloc_struct( struct Typestruct *S)

    {

      S = (struct Typestruct *) malloc ( sizeof (struct Typestruct));

    }

 

      LIBER_STRUCT (S)

  void Liber_struct( struct Typestruct *S)

    {

      free (S);

    }

 

STRUCT (S, I )

 

Si le type du champ I est un scalaire, STRUCT se traduit par une fonction comme suit :

 

  Typei Structi ( struct Typestruct S )

    {

      return(S->Champi) ;

    }

 

Il y a donc autant de fonctions STRUCT que de champs scalaires dans la structure.

 

Si le type du champ I est n'est pas scalaire, c'est à dire un vecteur à une dimension de scalaires, STRUCT se traduit par une procédure comme suit :

 

  void Struct2 ( struct Typestruct *S , Type2 Result)

    {

      int K;

      for (K=0; K<5; K++)

        Result[K] = S->Champ2[K] ;

    }

 

S'il s'agit d'un tableau de chaînes l'affectation se fait par la fonction "strcpy".

 

AFF_STRUCT (S, I, Exp)

 

  void Aff_struct1 ( struct Typestruct *S,  Type1 Val )

    {

      struct Typestruct P;

      P = *S;

      P.Champ1 = Val;

      *S = P;

    }

Il y a donc autant de fonction Aff_struct que de champs scalaire dans la structure.

 

 

Exemple 

 

  Le Z-algorithme suivant :

 

  SOIENT

    S UNE STRUCTURE (ENTIER, VECTEUR(5) DE CHAINES) DYNAMIQUE;

    V1, V2 DES VECTEURS(5) DE CHAINES;

    I UN ENTIER ;

  DEBUT

    AFF_ELEMENT(V1[1],'1');

    AFF_ELEMENT(V1[2],'2');

    AFF_ELEMENT(V1[3],'3');

    AFF_ELEMENT(V1[4],'4');

    AFF_ELEMENT(V1[5],'5');

    ALLOC_STRUCT(S);

    AFF_STRUCT(S, 1, 5);

    AFF_STRUCT(S, 2,  V1);

    ECRIRE('champ1 = ', STRUCT(S, 1) );

    ECRIRE('champ2 =');

    V2 = STRUCT(S, 2);

    POUR I := 1, 5  ECRIRE( V2[I])  FPOUR;

    LIBER_STRUCT(S);

  FIN

se traduit en C comme suit :

 

  #include <alloc.h>

  typedef int Type1  ;

  typedef char String[255];

  typedef String  Type2 [5]  ;

 

  struct Typestruct

    {

      Type1  Champ1;

      Type2  Champ2 ;

     } ;

 

  struct Typestruct *S;

  int I ;

  Type2 V1, V2 ;

 

  void Alloc_struct( struct Typestruct *S)

    {

      S = (struct Typestruct *) malloc ( sizeof (struct Typestruct));

    }

 

  void Liber_struct( struct Typestruct *S)

    {

      free (S);

    }

 

  Type1 Struct1 ( struct Typestruct *S )

    {

      return(S->Champ1) ;

    }

 

  void Struct2 ( struct Typestruct *S , Type2 Result)

    {

      int K;

      for (K=0; K<5; K++)

        strcpy(Result[K], S->Champ2[K] );

    }

 

  void Aff_struct1 ( struct Typestruct *S,  Type1 Val )

    {

      struct Typestruct P;

      P = *S;

      P.Champ1 = Val;

      *S = P;

    }

 

  void Aff_struct2 ( struct Typestruct *S,  Type2 Val )

    {

      int K;

      struct Typestruct P;

      P = *S;

      for (K=0; K<5; K++)

        strcpy(P.Champ2[K], Val[K]);

      *S = P;

    }

 

  main()

     {   

      strcpy(V1[0], "1");

      strcpy(V1[1], "2");

      strcpy(V1[2], "3");

      strcpy(V1[3], "4");

      strcpy(V1[4], "5");

      Alloc_struct(S);

      Aff_struct1(S, 5);

      Aff_struct2(S, V1);

      printf("champ1 = %d \n", Struct1(S) );

      printf("champ2 = \n");

      Struct2(S, V2);

      for ( I= 0; I<5; I++) printf("%s \n",V2[I])  ;

      Liber_struct(S);

    }

 

Implémentation des listes linéaires chaînées en C  /  Dynamique

 

 

  /* Maillon*/

  struct Maillon

    {

      int  Val ;

      struct Maillon *Suiv ;

     } ;

 

  /* Opérations */

  struct Maillon *Allouer ( )

    {

      return  (  (struct Maillon *) malloc( sizeof(struct Maillon))   );}

   

 

  void Aff_val(struct Maillon *P, int V)

   {  P->Val =V; }

 

  void Aff_adr( struct Maillon *P,  struct Maillon *Q)

   {    P->Suiv = Q; }

 

  struct Maillon *Suivant(  struct Maillon *P)

    { return( P->Suiv );  }

 

  int Valeur( struct Maillon *P)

    { return( P->Val) ; }

 

 

Implémentation des listes linéaires chaînées en C / Statique

 

Plusieurs listes dans un même tableau. Le tableau est un ensemble de triplets

(Element, Suivant, Occupe). Le champ "Occupe" est nécessaire pour les opérations Allouer et Libérer. Une phase d'initialisation est obligatoire avant l'utilisation de ce tableau. Donc le tableau est global.Une liste est définie par l'indice de son premier élément.

 

  #define Max 100

  #define True 1

  #define False 0

  #define Nil -1

 

  typedef int Bool;

  typedef int Typeqq;

 

  struct Typeliste

    {

     Typeqq Element ;

      int Suivant;

      Bool Occupe;

   } ;

 

  /* Initialisation */

  void Init()

    {

      int I;

      for (I=0; I<Max; I++)

        Liste[I].Occupe = False;

    }

 

  void Allouer ( int *I )

    {

      Bool Trouv;

      *I = 0;

      Trouv = False;

      while ( *I < Max && !Trouv )

        if ( Liste[*I].Occupe )

          *I++  ;

        else

          Trouv = True;

 

        if  ( !Trouv )  *I = -1;

    }

 

  void Liberer ( int I )

    {

      Liste[I].Occupe = False ;

    }

 

  Typeqq Valeur ( int I )

    {

      return( Liste[I].Element );

    }

 

  int Suivant ( int I )

    {

      return ( Liste[I].Suivant ) ;

    }

  void Aff_val ( int I, Typeqq Val)

    {

      Liste[I].Element = Val;

    }

 

  void Aff_adr ( int I, int J)

    {

      Liste[I].Suivant = J;

    }

Exemple 

 

  struct Typeliste Liste[ Max ];

  int E;

  main()

    {

      Init();

      Allouer (&E);

      if ( E != Nil )

        {

          Aff_val (E, 25);

          Aff_adr(E, Nil);

          printf("Ok");

        }

      else

        printf(" Pas d''espace ");

    }

 

Implémentation des listes bidirectionnelles en C / Dynamique

 

  /* structure du maillon */

 

  struct Maillon

    {

      int  Val ;

      struct Maillon *Suiv ;

      struct Maillon *Prec ;

     } ;

 

  /* Opérations */

  struct Maillon *Allouer ( )

   

      { return  (  (struct Maillon *) malloc( sizeof(struct Maillon))   );}

   

 

  void Aff_val(struct Maillon *P, int V)

    { P->Val =V; }

 

  void Aff_adrd( struct Maillon *P,  struct Maillon *Q)

    {  P->Suiv = Q; }

 

  void Aff_adrg( struct Maillon *P,  struct Maillon *Q)

    {  P->Prec = Q; }

  struct Maillon *Suivant(  struct Maillon *P)

    { return( P->Suiv );  }

 

  struct Maillon *Precedent(  struct Maillon *P)

    { return( P->Prec );  }

 

  int Valeur( struct Maillon *P)

     {return( P->Val) ; }

 

Implémentation des listes bidirectionnelles en C / Statique

 

Plusieurs listes dans un même tableau. Le tableau est un ensemble de quadruplé (Element, Suivant, Precedent, Occupe). Le champ "Occupe" est nécessaire pour les opérations Allouer et Libérer. Une phase d'initialisation est obligatoire avant l'utilisation de ce tableau.Donc le tableau est global. Une liste est définie par l'indice de son premier élément.

 

  #define Max 100

  #define True 1

  #define False 0

  #define Nil -1

 

  typedef int Bool;

  typedef int Typeqq;

 

  struct Typeliste

    {

      Typeqq Element ;

      int Suivant;

      int Precedent;

      Bool Occupe;

    };

 

  /* Initialisation */

  void Init()

    {

      int I;

      for (I=0; I<Max; I++)

        Listebi[I].Occupe = False;

    }

 

  void Allouer ( int *I )

    {

      Bool Trouv;

      *I = 0;

      Trouv = False;

      while ( *I < Max && !Trouv )

       if ( Listebi[*I].Occupe )

          *I++  ;

       else

          Trouv = True;

 

      if  ( !Trouv )  *I = -1;

    }

  void Liberer ( int I )

    {

      Listebi[I].Occupe = False ;

    }

 

  Typeqq Valeur ( int I )

    {

      return( Listebi[I].Element );

    }

 

  int Suivant ( int I )

    {

      return ( Listebi[I].Suivant ) ;

    }

 

  int Precedent ( int I )

    {

      return ( Listebi[I].Precedent ) ;

    }

 

  void Aff_val ( int I, Typeqq Val)

    {

 

      Listebi[I].Element = Val;

    }

 

  void Aff_adrd ( int I, int J)

    {

      Listebi[I].Suivant = J;

    }

 

  void Aff_adrg ( int I, int J)

    {

      Listebi[I].Precedent = J;

    }

 

 

Exemple 

 

  struct Typeliste Listebi[ Max ];

  int E;

  main()

    {

      Init();

      Allouer (&E);

      if ( E != Nil )

        {

          Aff_val (E, 25);

          Aff_adrg(E, Nil);

          Aff_adrd(E, Nil);

        }

      else

        printf(" Pas d''espace ");

    }

 

Implémentation des arbres de recherche binaire en C / Dynamique

 

  struct Noeud

    {

      int  Element ;

      struct Noeud *Fg ;

      struct Noeud *Fd ;

    } ;

 

  struct Noeud *Creernoeud ( int Val)

    {

      struct Noeud *P;

      P =   (struct Noeud *) malloc( sizeof(struct Noeud))   ;

      P->Element = Val ;

      P->Fg = NULL;

      P->Fd = NULL;

      return (P) ;

    }

 

  struct Noeud *Fg ( struct Noeud *P)

    {      return ( P->Fg );  }

 

  struct Noeud *Fd ( struct Noeud *P)

            { return ( P->Fd ) ; }

 

  int Info ( struct Noeud *P)

            { return ( P->Element ); }

 

  void Affinfo(struct Noeud *P, int V)

    {  P->Element =V; }

 

  void Aff_fg(struct Noeud *P, struct Noeud *Q)

     { P->Fg = Q; }

 

  void Aff_fd(struct Noeud *P, struct Noeud *Q)

     { P->Fd = Q; }

 

Implémentation des arbres de recherche binaire en C /  Statique

 

Plusieurs arbres de recherche binaire dans un même tableau. Le tableau est un ensemble de 5-uplets(Info, Fg, Fd, Pere, Occupe). Le champ "Occupe" est nécessaire pour les opérations Creernoeud et Liberernoeud. Une phase d'initialisation est obligatoire avant l'utilisation de ce tableau.

Donc le tableau est global. Un arbre de recherche binaire est défini par l'indice de son premier élément.

 

  #define Max 100

  #define True 1

  #define False 0

  #define Nil -1

 

  typedef int Bool;

  typedef int Typeqq;

 

  struct Typearb

    {

      Typeqq Info ;

      int Fg;

      int Fd;

      Bool Occupe;

    };

 

  /* Initialisation */

  void Init()

    {

      int I;

      for (I=0; I<Max; I++)

        Arb[I].Occupe = False;

    }

 

  void Creernoeud ( int *I )

    {

      Bool Trouv;

      *I = 0;

      Trouv = False;

      while ( *I < Max && !Trouv )

        if ( Arb[*I].Occupe )

          *I++  ;

        else

          Trouv = True;

      if  ( !Trouv )  *I = -1;

    }

 

  void Liberernoeud ( int I )

    {

      Arb[I].Occupe = False ;

    }   

  Typeqq Info ( int I )

    {

      return( Arb[I].Info );

    }

 

  int Fd ( int I )

    {

      return ( Arb[I].Fd ) ;

    }

 

  int Fg ( int I )

    {

      return ( Arb[I].Fg ) ;

    }

 

  void Aff_info ( int I, Typeqq Val)

    {

      Arb[I].Info = Val;

    }

 

 

  void Aff_fd ( int I, int J)

    {

      Arb[I].Fd = J;

    }

 

  void Aff_fg ( int I, int J)

    {

      Arb[I].Fg = J;

    }

 

Exemple            

 

  struct Typearb Arb[ Max ];

  int E;

  main()

    {

      Init();

      Creernoeud (&E);

      if ( E != Nil )

        {

          Aff_info (E, 25);

          Aff_fg(E, Nil);

          Aff_fd(E, Nil);

        }

      else

        printf(" Pas d''espace ");

    }

 

Implémentation des arbres de recherche m-aire en C / Dynamique

 

  #include <Alloc.H>

  #include <Stdio.H>

 

  #define Ordre 5

  #define True  1

  #define False 0

 

  typedef int Bool;

  typedef int Typeqq;

 

  struct Noeud

    {

      Typeqq  Info[Ordre-1] ;

      struct Noeud *Fils[Ordre] ;

      short Degre;

     } ;

 

  void Creernoeud ( struct Noeud *P)

    {

      int I;

      P =   (struct Noeud *) malloc( sizeof(struct Noeud))   ;

      for (I=1; I<Ordre ; I++)

        P->Fils[I] = NULL;

    }

  struct Noeud *Fils ( struct Noeud *P, short I)

    {      return ( P->Fils[I] );  }

 

  Typeqq Infor ( struct Noeud *P, short I)

    {      return ( P->Info[I] ); }

 

  void Aff_infor(struct Noeud *P, short I, Typeqq  V)

     {    P->Info[I] =V; }

 

  void Aff_fils(struct Noeud *P, short I, struct Noeud *Q)

     {    P->Fils[I] = Q; }

 

  short Degre ( struct Noeud *P)

    {

      return ( P->Degre );

    }

 

  void Aff_degre ( struct Noeud *P, short I)

    {

      P->Degre = I ;

    }

Exemple 

 

  struct Noeud *A;

  int I;

 

  main()

    {

      Creernoeud (A);

      for (I=0; I < 5; I++ )

        {

          Aff_infor(A, I, 3*I);

        };

      for (I=0; I < 5; I++ )

        printf("%d  ", Infor(A, I) );

    }

 

Implémentation des arbres de recherche m-aire en C /  Statique

 

Plusieurs arbres de recherche m-aire dans un même tableau.Le tableau est un ensemble de quadruplé  (Info, Fils, Degre, Occupe).Info est un tableau de (Ordre-1) valeurs.  Fils est un tableau de (Ordre) indices.  Le champ degre contient le nombre courant de valeur dans le noeud. Le champ "Occupe" est nécessaire pour les opérations Creernoeud et Liberernoeud. Une phase d'initialisation est obligatoire avant l'utilisation de ce tableau. Donc le tableau est global.  Un arbre de recherche m-aire est défini par l'indice de son premier élément.

 

  #define Max 100

  #define Ordre 8

  #define True 1

  #define False 0

  #define Nil -1

 

  typedef int Bool;

  typedef int Typeqq;

 

  struct Typearm

    {

      int Fils[Ordre];

      int Info[Ordre-1];

      short Degre;

      Bool Occupe;

    };

 

  /* Initialisation */

  void Init()

    {

      int I;

      for (I=0; I<Max; I++)

        Arm[I].Occupe = False;

    }

 

  void Creernoeud ( int *P )

    {

      Bool Trouv;

      *P = 0;

      Trouv = False;

      while ( *P < Max && !Trouv )

        if ( Arm[*P].Occupe )

           *P++  ;

        else

           Trouv = True;

 

      if  ( !Trouv )  *P = -1;

    }

 

  void Liberernoeud ( int P )

    {

      Arm[P].Occupe = False ;

    }

 

  Typeqq Infor ( int P, int I )

    {

      return( Arm[P].Info[I-1] );

    }

 

  int Fils ( int P, int I )

    {

      return ( Arm[P].Fils[I-1] ) ;

    }

 

  void Aff_infor ( int P, int I, Typeqq Val)

    {

      Arm[P].Info[I-1] = Val;

    }

 

  void Aff_fils ( int P, int I, int J)

    {

      Arm[P].Fils[I-1] = J;

    }

 

  short Degre ( int P )

    {

      return ( Arm[P].Degre );

    }

  void Aff_degre ( int P, short I )

    {

      Arm[P].Degre = I ;

    }

 

Exemple

 

  struct Typearm Arm[ Max ];

  int E;

  main()

    {

      Init();

      Creernoeud (&E);

      if ( E != Nil )

        {

          Aff_infor (E, 1, 25);

          Aff_fils(E, 2, Nil);

        }

      else

        printf(" Pas d''espace ");

    }

 

Implémentation des piles en C /  Dynamique

 

  #include <Alloc.H>

  #include <Stdio.h>

 

  typedef int Bool;

  typedef int Typeqq;

 

  struct Maillon

    {

      int  Valeur ;

      struct Maillon *Suivant ;

     } ;

  void Creerpile( struct Maillon ** P )

    {

      struct Maillon *Pil;

      Pil = *P;

      Pil = NULL;

      *P = Pil;

    }

 

  Bool Pilevide ( struct Maillon *P )

    {

      struct Maillon *Pil;

      Pil = P;

      return ( Pil == NULL ) ;

    }

 

  void Empiler ( struct Maillon **P, Typeqq Val )

    {

      struct Maillon *Q;

      Q = (struct Maillon *) malloc ( sizeof(struct Maillon));

      Q->Valeur = Val;

      Q->Suivant = *P;

      *P = Q;

    }

 

  void Depiler ( struct Maillon **P, Typeqq *V )

    {

      struct Maillon *Sauv, *Pil;

      Pil = *P;

      if ( ! Pilevide ( Pil ) )

        {

          *V = Pil->Valeur;

          Sauv = Pil;

          Pil = Pil->Suivant;

          *P = Pil;

        }

      else

        printf(" Pile vide ");

  }

Implémentation des piles en C /  Statique

 

 

  #define True  1

  #define False 0

  typedef int Bool;

 

  struct Pile

    {

      int Som ;

      struct Noeud *Tab[50];

     };

 

  void Creerpile( struct Pile *P)

    {

      struct Pile Q ;

      Q =*P;

      Q.Som = 0 ;

      *P = Q;

    }

 

  Bool Pilepleine(struct Pile P)

     { return ( P.Som == 49 ); }

 

  Bool Pilevide(struct Pile P)

     { return ( P.Som == 0 ); }

  void Empiler ( struct Pile *P, struct Noeud *Val)

    {

      struct Pile Q;

      Q = *P;

      if (  !Pilepleine(*P)  )

        {

           Q.Som++;

           Q.Tab[Q.Som] = Val ;

           *P = Q;

        }

      else

         fprintf( "Pile satur\n"); exit(0) ;

    }

 

  void Depiler ( struct Pile *P, struct Noeud **Val)

    {

      struct Pile Q;

      Q = *P;

      if (  !Pilevide(*P)  )

        {

          *Val = Q.Tab[Q.Som]  ;

          Q.Som--;

          *P = Q ;

        }

      else

         fprintf( "Pile vide\n"); exit(0) ;

    }

 

Exemple

 

  struct Maillon *Pile;

  Typeqq V ;

 

  main()

    {

      Creerpile(&Pile);

      Empiler ( &Pile, 25);

      Empiler ( &Pile, 35);

      Empiler ( &Pile, 45);

      Depiler ( &Pile, &V );

      printf( " %d ", V);

    }

 

Implémentation des files d'attente en C / Dynamique

 

  #define True  1

  #define False 0

  typedef int Bool;

  Typedef int typelment;

 

  struct Filedattente

    {

      struct Maillon *Tete, *Queue;

     };

  struct Maillon

    {

      typelement Val ;

      struct Maillon *Suiv ;

     } ;

 

  void Creerfile( struct Filedattente *F)

    {

      struct Filedattente Q ;

      Q =*F;

      Q.Tete = NULL ;

      *F = Q;

    }

 

  Bool Filevide(struct Filedattente F)

     {return ( F.Tete == NULL ); }

 

  void Enfiler ( struct Filedattente *F, typelement Val)

    {

      struct Filedattente Q;

      struct Maillon *P;

      P = Allouer();

      Affval(P, Val);

      Affadr(P, NULL);

      Q = *F;

      if (  !Filevide(*F)  )

        Affadr( Q.Queue, P);

      else Q.Tete = P;

      Q.Queue = P;

      *F = Q;

    }

 

  void Defiler ( struct Filedattente *F, typelement *Val)

    {

      struct Filedattente Q;

      Q = *F;

      if (  !Filevide(*F)  )

        {

          *Val = Valeur(Q.Tete)  ;

          Q.Tete = Suivant(Q.Tete);

          *F = Q ;

        }

      else

         fprintf("File Vide\n"); exit(0) ;

    }

 

Implémentation des files d'attente en C / Statique

 

  #define Max 100

  typedef int Bool;

  typedef int Typeqq;

 

  struct Typefile

    {

      Typeqq Elements[Max];

      int Tete, Queue;

    };

 

  void Creerfile ( struct Typefile *F )

    {

      struct Typefile Fil;

      Fil = *F;

      Fil.Tete = Max - 1;

      Fil.Queue = Max - 1;

      *F = Fil;

    }

 

  Bool Filevide ( struct Typefile F )

    {

      return ( F.Tete == F.Queue );

    }

 

  Bool Filepleine ( struct Typefile F )

    {

      return ( F.Tete == F.Queue % (Max-1) + 1 );

    }

 

  void Enfiler ( struct Typefile *F, Typeqq Val )

    {

      struct Typefile Fil;

      Fil = *F;

      if ( ! Filepleine(Fil) )

        {

          if (Fil.Queue == Max-1 )

            Fil.Queue = 0;

          else

            Fil.Queue =  Fil.Queue + 1 ;

          Fil.Elements[Fil.Queue] = Val;

          *F = Fil;

        }

      else

        printf(" File pleine");

    }

  void Defiler ( struct Typefile *F, Typeqq *Val )

    {

      struct Typefile Fil;

      Fil = *F;

      if ( ! Filevide(Fil) )

        {

          if ( Fil.Tete == Max - 1)

            Fil.Tete = 0;

          else

            Fil.Tete = Fil.Tete + 1;

 

          *Val = Fil.Elements[Fil.Tete];

          *F = Fil ;

        }

      else

        printf(" File vide");

    }

 

Exemple 

 

  struct Typefile F;

  Typeqq V;

  main()

    {

      Creerfile (&F);

      Enfiler(&F, 5);

      Enfiler(&F, 18);

      Enfiler(&F, 22);

      Defiler(&F, &V);

      printf("%d\n", V);

    }

 

 

 

Implémentation des fichiers en C 

 

  /* Types des champs formant le bloc du fichier */

  typedef type du premier champ du bloc du fichier  Type1  ;

  typedef type du deuxième champ du bloc du fichier  Type2  ;

  ...

  typedef type du n-ième champ du bloc du fichier  Typen  ;

 

  /* Types des champs formant l'entête du fichier */

  typedef type du premier champ des caractéristiques du fichier Typecaract1 ;

  typedef du deuxième champ des caractéristiques du fichier Typecaract2 ;

  ...

  typedef du n-ième champ des caractéristiques du fichier Typecaractn ;

 

  /* Types de travail */

  typedef int Boolean;

  typedef char String[255];

 

  /* Type du bloc de données du fichier */

  typedef struct

    {

     Type1 Champ1 ;

     Type2 Champ2;

     ...

     Typen Champn;

     }  Typestruct1;

 

  /* Type du bloc des caractéristiques du fichier */

  typedef struct

    {

     Typecaract1 Caract1;

     Typecaract2 Caract2 ;

     ...

     Typecaractm Caractm ;

     }Typestruct2 ;

 

  /* Type du bloc du fichier */

  typedef union

   {

     Typestruct1 Buf_Donnees;

     Typestruct2 Buf_Caract;

   }Typebloc;

 

 

  FILE *F;                  /* Le fichier */

  Typebloc Bloc_Caract;     /* Le bloc des caractéristiques du fichier */

 

  /* Machine abstaite sur les fichiers */

 

  void Ouvrir ( FILE **Fl , String Fp , String Mode )

    {

      if ( strcmp(Mode,"A") == 0)

         {

           *Fl = fopen(Fp, "r+b");

           fread(&Bloc_Caract, sizeof(Typebloc), 1, *Fl);

         }

      else

         {

          *Fl = fopen(Fp, "w+b");

          fwrite(&Bloc_Caract, sizeof(Typebloc), 1, *Fl)  ;

         }

    }

 

  void Fermer ( FILE **Fl )

    {

      fseek(*Fl, 0, 0);

      fwrite(&Bloc_Caract, sizeof( Typebloc), 1, *Fl)  ;

      fclose( *Fl) ;

    }

 

ENTETE ( Fl, i )

 

  Typecaract Entetei(  FILE *Fl)

    {

      return(Bloc_Caract.Buf_Caract.Caracti) ;

    }

 

  /* Il y a donc autant de fonctions ENTETEi que de types scalaires définis dans la partie 'ENTETE'. */

 

AFF_ENTETE ( Fl, i, Exp )

 

  void Aff_entetei ( FILE *Fl, Typecaracti Val)

    {

      Bloc_Caract.Buf_Caract.Caracti = Val ;

    }

 

   /* Il y a donc autant de fonctions AFF_ENTETEi que de types scalaires définis dans la partie 'ENTETE'. */

 

  void Ecrireseq ( FILE **Fl,  Typebloc Buf )

    {

      fwrite(&Buf, sizeof( Typebloc), 1, *Fl)  ;

    }

 

  void Ecriredir ( FILE **Fl,  Typebloc Buf, int N )

    {

      fseek(*Fl, 0, (long) (N-1)* sizeof(  Typebloc) /*SEEK_SET*/);

      fwrite(&Buf, sizeof( Typebloc), 1, *Fl)  ;

    }

 

  void Lireseq ( FILE **Fl,  Typebloc *Buf )

    {

      fread(&*Buf, sizeof( Typebloc), 1, *Fl);

    }

 

  void Liredir ( FILE **Fl, Typebloc *Buf, int N )

    {

      fseek(*Fl, 0, (long) (N-1)* sizeof(  Typebloc) /*SEEK_SET*/ );

      fread(&*Buf, sizeof( Typebloc), 1, *Fl);

    }

 

  Boolean Finfich ( FILE **Fl)

    {

      if ( feof(*Fl) == 0 )

        return(0)   ;

      else

        return(1)    ;

    }

 

  int  Alloc_bloc ( FILE *Fl )

    {

      int K;

      fseek(Fl, 0, 2); /* Fin du fichier */

      K = ftell(Fl);   /* position _ partir du dut */

      K = K / sizeof (Typebloc);

      K ++;

      return(K); 

   }

 

 

Exemple  

 

  Le Z-algorithme suivant :

 

  SOIENT

    F UN FICHIER DE ( ENTIER , VECTEUR ( 5 ) DE ENTIERS )

    BUFFER Bloc

    ENTETE ( ENTIER , ENTIER ) ;

     { fichier de blocs contenant le nombre d'articles et un tableau d'articles}

     { entete : nombre d'articles, nombre de blocs}

    Creer , Ajouter, Imprimer DES ACTIONS ;

  DEBUT

    APPEL Creer ;

    APPEL Imprimer ;

    APPEL Ajouter ;

    APPEL Imprimer;

   FIN

 

  /******    Chargement de 5 blocs _ raison de 60% ****/

  ACTION Creer ;

  SOIENT

    I , K DES ENTIERS ;

  DEBUT

    OUVRIR ( F , 'f.pas' , 'N' ) ;

    POUR I:=1, 5 :

       POUR K:=1, 3 :

          AFF_ELEMENT ( STRUCT ( Bloc , 2 ) [ K ] , ALEAENTIER )

       FPOUR

       AFF_STRUCT ( Bloc , 1 , K ) ;

       ECRIRESEQ ( F , Bloc ) ;

    FINPOUR ;

    AFF_ENTETE ( F , 1 , 5 ) ;

    AFF_ENTETE ( F , 2 , 3*5 ) ;

    FERMER ( F ) ;

  FIN

 

 /*  Réouvre le fichier, rajoute un bloc en fin de fichier puis le ferme */

 

  ACTION Ajouter

    DEBUT

      OUVRIR(F, 'f.c' , 'A' ) ;

      POUR  K := 1, 4

        AFF_ELEMENT ( STRUCT ( Bloc , 2 ) [ K ], ALEAENTIER );

            FPOUR:

      AFF_STRUCT ( Bloc, 1 , 4 ) ;

 

      ECRIREDIR(F, Bloc, ALLOC_BLOC(F) );

      FERMER(F);

    FIN

 

  /*****       Impression des articles du fichier ****/

  ACTION Imprimer ;

  SOIENT

    I , K DES ENTIERS ;

  DEBUT

    I := 0 ;

    OUVRIR ( F , 'f.pas' , 'A' ) ;

    ECRIRE('Caractéristiques du fichier');

    ECRIRE('- Nombre de blocs : ', Entete(F, 1) );

    ECRIRE('- Nombre d''articles : ', Entete(F, 2) );

    LIRESEQ ( F , Bloc ) ;

    TQ NON FINFICH ( F )

       I := I + 1 ;

       ECRIRE ( 'B  L  O  C    ' , I ) ;

       LIRESEQ ( F , Bloc ) ;

       POUR K := 1 , STRUCT ( Bloc , 1 )

ECRIRE ( ELEMENT ( STRUCT ( Bloc , 2 ) [ K ] ) )

       FPOUR

       LIRESEQ ( F , B1 ) ;

    FTQ;

    FERMER(F);

  FIN

 

se traduit en C Comme suit :

  #include "stdio.h"

  #include "string.h"

  #include "stdlib.h"

 

  typedef int Type1  ;

  typedef int  Type2 [5]  ;

 

  typedef char String[255];

 

  typedef int Typecaract1 ;

  typedef int Typecaract2 ;

 

  typedef int Boolean;

 

  typedef struct

    {

     Type1 Champ1 ;

     Type2 Champ2;

     }  Typestruct1;

 

  typedef struct

    {

     Typecaract1 Caract1;

     Typecaract2 Caract2 ;

     }Typestruct2 ;

 

  typedef union

   {

     Typestruct1 Buf_Donnees;

     Typestruct2 Buf_Caract;

   } Typebloc;

 

  /*fichier de blocs contenant le nombre d'articles et un tableau d'articles */

  FILE *F;

 

  Typebloc

     Bloc ,          /* pour les lectures/écritures */

     Bloc_Caract ;   /* pour la sauvegarde des caractéristiques */

 

  /* Machine abstraite sur les vecteurs */

  int Element ( Type2 V, int I )

    {

      return( V[I] );

    }

 

  void Aff_element ( Type2 V, int I, int Val)

    {

      V[I] = Val;

    }

  /* Machine abstraite sur les structures */

  Type1 Struct1 ( Typestruct1 S )

    {

      return(S.Champ1) ;

    }

 

  void Struct2 ( Typestruct1 S , Type2 Result)

    {

      int K;

      for (K=0; K<5; K++)

        Result[K] = S.Champ2[K] ;

    }

 

 

  void Aff_struct1 ( Typestruct1 *S,  Type1 Val )

    {

      Typestruct1 P;

      P = *S;

      P.Champ1 = Val;

      *S = P;

    }

 

  void Aff_struct2 ( Typestruct1 *S,  Type2 Val )

    {

      int K;

      Typestruct1 P;

      P = *S;

      for (K=0; K<5; K++)

        P.Champ2[K] = Val[K] ;

      *S = P;

    }

 

  /* Machine abstraite sur les fichiers */

  void Ouvrir ( FILE **Fl , String Fp , String Mode )

    {

      if ( strcmp(Mode,"A") == 0)

        {

          *Fl = fopen(Fp, "r+b");

          fread(&Bloc_Caract, sizeof(Typebloc), 1, *Fl);

        }

      else

        {

          *Fl = fopen(Fp, "w+b");

          fwrite(&Bloc_Caract, sizeof(Typebloc), 1, *Fl)  ;

        }

    }

 

  void Fermer ( FILE **Fl )

    {

      fseek(*Fl, 0, 0);

      fwrite(&Bloc_Caract, sizeof( Typebloc), 1, *Fl)  ;

      fclose( *Fl) ;

    }

 

  Typecaract1 Entete1(  FILE *Fl)

    {

      return(Bloc_Caract.Buf_Caract.Caract1) ;

    }

  Typecaract2 Entete2(  FILE *Fl )

    {

      return (Bloc_Caract.Buf_Caract.Caract2);

    }

 

  void Aff_entete1 ( FILE *Fl, Typecaract1 Val)

    {

      Bloc_Caract.Buf_Caract.Caract1 = Val ;

    }

  void Aff_entete2 ( FILE *Fl, Typecaract2 Val)

    {

      Bloc_Caract.Buf_Caract.Caract2 = Val ;

    }

  void Ecrireseq ( FILE **Fl,  Typebloc Buf )

    {

      fwrite(&Buf, sizeof( Typebloc), 1, *Fl)  ;

    }

  void Ecriredir ( FILE **Fl,  Typebloc Buf, int N )

    {

      fseek(*Fl, (long) (N-1)* sizeof(  Typebloc), 0 /*SEEK_SET*/);

      fwrite(&Buf, sizeof( Typebloc), 1, *Fl)  ;

    }

  void Lireseq ( FILE **Fl,  Typebloc *Buf )

    {

      fread(&*Buf, sizeof( Typebloc), 1, *Fl);

    }

  void Liredir ( FILE **Fl, Typebloc *Buf, int N )

    {

      fseek(*Fl, (long) (N-1)* sizeof(  Typebloc), 0 /*SEEK_SET*/ );

      fread(&*Buf, sizeof( Typebloc), 1, *Fl);

    }

  Boolean Finfich ( FILE **Fl)

    {

      if ( feof(*Fl) == 0 )

        return(0)   ;

      else

        return(1)    ;

    }

  int Aleaentier ()

    {

      return( random(10000) );

    }

 

  int  Alloc_bloc ( FILE *Fl )

    {

      int K;

      fseek(Fl, 0, 2);

      K = ftell(Fl); /* position _ partir du dut */

      K = K / sizeof (Typebloc);

      K ++;

      return(K);

    }

 

  /******    Chargement de 5 blocs à raison de 60% ****/

  void Creer  ()

    {

      int I , K  ;

      Type2 V;

      Ouvrir ( &F , "f.c" , "N" ) ;

      for ( I = 1; I<=5; I++)

        {

          for ( K = 0; K<3; K++)

            Aff_element ( V , K  , Aleaentier() );

          Aff_struct2( &Bloc.Buf_Donnees, V);

          Aff_struct1 ( &Bloc.Buf_Donnees , 3 ) ;

          Ecrireseq ( &F , Bloc ) ;

        } ;

      Aff_entete1(F, 5);  /* Nombre de blocs   */

      Aff_entete2(F, 3*5); /* Nombre d'articles */

      Fermer ( &F ) ;

    }

 

  void Ajouter()

    {

      int K;

      Type2 V;

      Ouvrir ( &F , "f.c" , "A" ) ;

      for ( K = 0; K<4; K++)

        Aff_element ( V , K  , Aleaentier() );

      Aff_struct2( &Bloc.Buf_Donnees, V);

Aff_struct1 ( &Bloc.Buf_Donnees , 4 ) ;

      Ecriredir(&F, Bloc, Alloc_bloc(F) );

      Fermer(&F);

    }

  /*****    Impression des articles du fichier ****/

  void Imprimer ()

    {

      int I=0;

      int  K;

      Type2 V;

      Ouvrir ( &F , "f.c" , "A" ) ;

      printf("Caractéristiques du fichier : \n");

      printf("-Nombre de bloc    : %d \n", Entete1(F) );

      printf("-Nombre d'articles : %d \n", Entete2(F) );

      Ouvrir ( &F , "f.c" , "A" ) ;

      Lireseq ( &F , &Bloc ) ;

      while ( ! Finfich ( &F )  )

        {

          I++;

          printf("\n Bloc %d: \n ", I);

          Struct2(Bloc.Buf_Donnees, V);

          for ( K=0; K < Struct1 ( Bloc.Buf_Donnees ); K++)

             printf("Element : %d \n", Element ( V , K  ) );

          Lireseq ( &F , &Bloc ) ;

        }

      Fermer(&F);

    }

 

  main ()

    {

      randomize();    Creer() ;      Imprimer() ;

      Ajouter();      Imprimer();

    }