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> | |
67b44095 | 17 | |
f5904379 | 18 | typedef int element; |
67b44095 JB |
19 | typedef struct cellule { |
20 | element valeur; | |
21 | struct cellule *suivant; | |
22 | } Cellule; | |
23 | ||
24 | typedef struct file { | |
25 | Cellule *t, *q; | |
26 | } File; /* tête queue */ | |
f5904379 JB |
27 | |
28 | File file_vide(void) | |
67b44095 JB |
29 | { |
30 | File f = { NULL, NULL }; | |
31 | return f; | |
f5904379 JB |
32 | } |
33 | ||
34 | int est_vide(File f) | |
35 | { | |
67b44095 | 36 | return !f.t; |
f5904379 JB |
37 | } |
38 | ||
39 | element tete(File f) | |
40 | /* ATTENTION: consulter la tête d'une File vide n'a pas de sens */ | |
41 | { | |
67b44095 JB |
42 | if (est_vide(f)) { |
43 | printf("Erreur - file vide\n"); | |
44 | exit(-1); | |
45 | } | |
46 | return f.t->valeur; /* la File n'est pas modifiée */ | |
f5904379 JB |
47 | } |
48 | ||
67b44095 | 49 | File enfiler(element e, File f) |
f5904379 | 50 | { |
67b44095 JB |
51 | Cellule *pc = (Cellule *) malloc(sizeof(Cellule)); |
52 | pc->valeur = e; | |
53 | pc->suivant = NULL; | |
54 | ||
55 | if (est_vide(f)) | |
56 | f.t = f.q = pc; /* la cellule créée est à la fois tête et queue */ | |
57 | else | |
58 | f.q = f.q->suivant = pc; /* la cellule créée est la nouvelle queue */ | |
59 | return f; | |
f5904379 JB |
60 | } |
61 | ||
62 | File defiler(File f) | |
63 | /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */ | |
64 | { | |
67b44095 JB |
65 | Cellule *pc = f.t; |
66 | if (est_vide(f)) { | |
67 | printf("Erreur - file vide\n"); | |
68 | exit(-1); | |
69 | } | |
70 | if (f.t == f.q) | |
71 | f = file_vide(); /* la File n'avait plus qu'une seule cellule */ | |
72 | else | |
73 | f.t = f.t->suivant; /* la queue ne change pas */ | |
74 | free(pc); | |
75 | return f; | |
f5904379 | 76 | } |
67b44095 JB |
77 | |
78 | element defiler2(File * f) | |
f5904379 | 79 | { |
67b44095 JB |
80 | /* ATTENTION: la File est modifiée */ |
81 | /* ATTENTION: supprimer la tête d'une File vide n'a pas de sens */ | |
82 | Cellule *pc = f->t; | |
83 | element e; | |
84 | if (est_vide(*f)) { | |
85 | printf("Erreur - file vide\n"); | |
86 | exit(-1); | |
87 | } | |
88 | e = f->t->valeur; | |
89 | if (f->t == f->q) | |
90 | *f = file_vide(); /* la File n'avait plus qu'une seule cellule */ | |
91 | else | |
92 | f->t = f->t->suivant; /* la queue ne change pas */ | |
93 | free(pc); | |
94 | return e; | |
f5904379 JB |
95 | } |
96 | ||
f5904379 JB |
97 | /********************************************************************/ |
98 | int main() | |
99 | { | |
67b44095 JB |
100 | File p; |
101 | int i; | |
102 | p = file_vide(); | |
103 | for (i = 0; i < 20; i++) | |
104 | p = enfiler(i, p); | |
105 | for (i = 0; i < 25; i++) | |
106 | printf("%d\n", defiler2(&p)); | |
f5904379 | 107 | } |
f5904379 | 108 | |
67b44095 | 109 | /********************************************************************/ |