Commit | Line | Data |
---|---|---|
f5904379 JB |
1 | /************************************************************************** |
2 | Implantation d'un type File d'entiers sous forme chaînée | |
3 | ||
4 | La file est représentée par un doublet tête-queue de pointeurs | |
5 | vers une cellule. | |
6 | Le pointeur "tête" contient l'adresse de la tête de la file. | |
7 | Le pointeur "queue" contient l'adresse de la queue de la file. | |
8 | ||
9 | La file vide est représentée par le doublet NULL-NULL | |
10 | ||
11 | Chaque cellule pointe vers la cellule suivante de la file | |
12 | ou vers NULL si on est en queue de file. | |
13 | ||
14 | **************************************************************************/ | |
15 | #include <stdio.h> | |
16 | #include <stdlib.h> | |
17 | ||
18 | typedef int element; | |
19 | typedef struct cellule {element valeur; | |
20 | struct cellule *suivant; } Cellule; | |
21 | ||
22 | typedef struct file { Cellule *t, *q; } File; /* tête queue */ | |
23 | ||
24 | File file_vide(void) | |
25 | { | |
26 | File f={NULL,NULL}; | |
27 | return f; | |
28 | } | |
29 | ||
30 | int est_vide(File f) | |
31 | { | |
32 | return !f.t; | |
33 | } | |
34 | ||
35 | element tete(File f) | |
36 | /* ATTENTION: consulter la tête d'une File vide n'a pas de sens */ | |
37 | { | |
38 | if (est_vide(f)) {printf("Erreur - file vide\n"); exit(-1); } | |
39 | return f.t->valeur; /* la File n'est pas modifiée */ | |
40 | } | |
41 | ||
42 | File enfiler(element e,File f) | |
43 | { | |
44 | Cellule *pc=(Cellule *)malloc(sizeof(Cellule)); | |
45 | pc->valeur=e;pc->suivant=NULL; | |
46 | ||
47 | if (est_vide(f)) | |
48 | f.t=f.q=pc; /* la cellule créée est à la fois tête et queue */ | |
49 | else | |
50 | f.q=f.q->suivant=pc; /* la cellule créée est la nouvelle queue */ | |
51 | return f; | |
52 | } | |
53 | ||
54 | File defiler(File f) | |
55 | /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */ | |
56 | { | |
57 | Cellule *pc=f.t; | |
58 | if (est_vide(f)) | |
59 | { | |
60 | printf("Erreur - file vide\n"); | |
61 | exit(-1); | |
62 | } | |
63 | if (f.t==f.q) f=file_vide(); /* la File n'avait plus qu'une seule cellule */ | |
64 | else f.t=f.t->suivant; /* la queue ne change pas */ | |
65 | free(pc); | |
66 | return f; | |
67 | } | |
68 | ||
69 | element defiler2(File *f) /* ATTENTION: la File est modifiée */ | |
70 | /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */ | |
71 | { | |
72 | Cellule *pc=f->t; | |
73 | element e; | |
74 | if (est_vide(*f)) | |
75 | { | |
76 | printf("Erreur - file vide\n"); | |
77 | exit(-1); | |
78 | } | |
79 | e=f->t->valeur; | |
80 | if (f->t==f->q) *f=file_vide(); /* la File n'avait plus qu'une seule cellule */ | |
81 | else f->t=f->t->suivant; /* la queue ne change pas */ | |
82 | free(pc); | |
83 | return e; | |
84 | } | |
85 | ||
86 | ||
87 | /********************************************************************/ | |
88 | int main() | |
89 | { | |
90 | File p; | |
91 | int i; | |
92 | p=file_vide(); | |
93 | for (i=0; i<20; i++) p=enfiler(i,p); | |
94 | for (i=0; i<25; i++) printf("%d\n",defiler2(&p)); | |
95 | } | |
96 | /********************************************************************/ | |
97 |