Implémentation des machines Z en C
Listes linéaires chaînées Statique Dynamique
Listes bidirectionnelles Statique Dynamique
Files d'attente Statique Dynamique
Arbres de recherche binaire Statique Dynamique
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 d饕ut */
K = K / sizeof (Typebloc);
K ++;
return(K);
}
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 d饕ut */
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();
}