Programmation Proc Edurale - C: La Structure de Donn Ees FILE

Définitions
Les opérations de base

Les types de représentations
Programmation Procédurale - C
La structure de données FILE
Dr. Marwa Thabet
ESPRIT MONASTIR
Cycle préparatoire MP/PC 1, Semestre 2, 2024
1/26
Dr. Thabet Prog. Proc.
Définitions
Objectif du chapitre
Être capable de définir, manipuler et réutiliser la structure de

données FILE.
Distinguer les différentes représentations contiguës et chaı̂nées.
2/26
Définitions
Plan du chapitre
1 Définitions
2 Les opérations de base
3 Les types de représentations

La représentation contiguë
La représentation chaı̂née
3/26
Définitions
Plan du chapitre
1 Définitions

4/26
Définitions
C’est quoi la SD FILE?
Une structure de données linéaire.

On ne peut ajouter qu’en queue,
consulter qu’en tête,
et supprimer qu’en tête.
Comme pour une file d’attente ... !
Les files sont aussi appelées structures
FIFO pour First In First Out: c-à-d
premier-entré-premier-sorti.
5/26
Définitions
C’est quoi la SD FILE?

Pour l’implémentation de la file, on maintient deux pointeur:
le pointeur doit être maintenu en tête de la file, c’est-à-dire le
premier élément inséré dans la file.
le pointeur doit être maintenu en queue de la file, c’est-à-dire
le dernier élément inséré dans la file.
Applications: les algorithmes de recherche non informés (exemple:
BFS).
6/26
Définitions
Plan du chapitre
1 Définitions

7/26
Définitions
Opération Description
créer() créé une file vide.
est vide() vérifie si une file est vide ou non.
premier() retourne l’élément qui se trouve en tête de la file.
dernier() retourne l’élément qui se trouve en queue de la file.
enfiler() insère un élément donné en queue de la file.
defiler() supprime l’élément qui se trouve en tête de la file.
8/26
Définitions
Plan du chapitre
1 Définitions

9/26
Définitions
Deux principaux types de files sont les files contiguës et chaı̂nées:

Contiguë:
Mise en œuvre à l’aide d’un tableau.
Taille fixe.
chaı̂née:
Mise en œuvre à l’aide d’une liste chaı̂née.
Taille dynamique.
10/26
Définitions
1 #define N 100
2 struct file{
3 int cle[N];
4 int tete;
5 int queue;
6 };
7 static struct file f;
11/26
Définitions
Créer une FILE
1 void creer_file(){
2 f.tete=-1;
3 f.queue=-1
4 }
12/26
Définitions
Consulter si une FILE est vide ou non
1 unsigned file_vide(){
2 return (f.tete==-1 &&f.queue==-1 );
3 }
13/26
Définitions
Retourner l’élément en tête de la FILE
1 int premier(){
2 assert(file_vide()==0);
3 return f.cle[f.tete];
4 }
14/26
Définitions
Retourner l’élément en queue de la FILE
1 int dernier(){
3 return f.cle[f.queue];
4 }
15/26
Définitions
Ajouter un élément à la FILE
1 void enfiler(int info){

2 assert(!file_pleine());
3 if (file_vide())
4 f.tete++;
5 f.queue++;
6 if (f.queue==N)
7 f.queue=0;
8 f.cle[f.queue]=info;
9 }
16/26
Définitions
Consulter si une FILE est pleine ou non
1 void file_pleine(){
2 return((f.tete==0&&f.queue==N-1)||
3 f.tete==f.queue+1);
4 }
17/26
Définitions
Supprimer un élément de la FILE
1 void defiler(){
3 if (f.tete==f.queue)
4 {f.tete=-1;
,→ f.queue=-1;}
5 else if(f.tete==N-1)
6 f.tete=0;
7 else f.tete++;
8 }
18/26
Définitions
1 struct element{
2 int cle;
3 struct element* suivant;
4 };
5 struct file{
6 struct element* tete;
7 struct element* queue;
8 }
9 static struct file* f;
19/26
Définitions
Créer une FILE
1 void creer_file(){
2 f->tete = NULL;
3 f->queue = NULL;
4 }
20/26
Définitions
Consulter si une FILE est vide ou non
1 unsigned file_vide(){
2 return ( f->tete == NULL && f->queue == NULL);
3 }
21/26
Définitions
Retourner l’élément en tête de la FILE
1 int premier (){

3 return f->tete->cle;
4 }
22/26
Définitions
Retourner l’élément en queue de la FILE
1 int dernier (){

3 return f->queue->cle;
4 }
23/26
Définitions
Ajouter un élément à la FILE

1 void enfiler(int info){
2 struct element* p;
3 p=(struct element*) malloc(sizeof
4 (struct element*));
5 p->cle=info;
6 p->suivant=NULL;
7 if(file_vide())
8 f->tete=p;
9 f->queue->suivant=p;
10 f->queue=p;
11 }
24/26
Définitions
Supprimer un élément de la FILE

1 void defiler(){
2 assert(!file_vide());
3 struct element* p;
4 p=f->tete;
5 if(p==f->queue)
6 f->queue=NULL;
7 f->tete = p->suivant;
8 free(p);
9 }
25/26
Définitions
Merci de votre attention
26/26

Programmation Proc Edurale - C: La Structure de Donn Ees FILE

Transféré par

Droits d'auteur :

Formats disponibles

Programmation Proc Edurale - C: La Structure de Donn Ees FILE

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Programmation Proc Edurale - C: La Structure de Donn Ees FILE

Transféré par

Droits d'auteur :

Formats disponibles

Définitions

Les opérations de base

Dr. Marwa Thabet

Cycle préparatoire MP/PC 1, Semestre 2, 2024

Être capable de définir, manipuler et réutiliser la structure de

2 Les opérations de base

3 Les types de représentations

2 Les opérations de base

3 Les types de représentations

C’est quoi la SD FILE?

Une structure de données linéaire.

C’est quoi la SD FILE?

2 Les opérations de base

3 Les types de représentations

Les opérations de base

2 Les opérations de base

3 Les types de représentations

Les types de représentations

Deux principaux types de files sont les files contiguës et chaı̂nées:

Créer une FILE

Consulter si une FILE est vide ou non

Retourner l’élément en tête de la FILE

Retourner l’élément en queue de la FILE

Ajouter un élément à la FILE

1 void enfiler(int info){

Consulter si une FILE est pleine ou non

Supprimer un élément de la FILE

Créer une FILE

Consulter si une FILE est vide ou non

Retourner l’élément en tête de la FILE

1 int premier (){

Retourner l’élément en queue de la FILE

1 int dernier (){

Ajouter un élément à la FILE

Supprimer un élément de la FILE

Merci de votre attention

Vous aimerez peut-être aussi