Commit | Line | Data |
---|---|---|
3f0f8bfd JB |
1 | /********************************************************************/ |
2 | /* Implantation d'une liste triee d'entiers */ | |
3 | /********************************************************************/ | |
4 | #include <stdio.h> | |
5 | #include <stdlib.h> | |
ef5acd44 | 6 | #include <stdbool.h> |
3f0f8bfd JB |
7 | |
8 | typedef int element; | |
9 | ||
10 | typedef struct cellule { | |
11 | element valeur; | |
12 | struct cellule *suivant; | |
13 | } Cellule, *Liste; | |
14 | ||
c31b68a4 | 15 | Cellule *creer_maillon(element e, Cellule * suivant) |
0bf26b29 JB |
16 | { |
17 | Cellule *pnouveau = malloc(sizeof(Cellule)); | |
18 | pnouveau->valeur = e; | |
19 | pnouveau->suivant = suivant; | |
20 | return pnouveau; | |
21 | } | |
22 | ||
3f0f8bfd JB |
23 | Liste ajouter_iter(element e, Liste L) |
24 | { | |
25 | Cellule *pc, *p1 = L, *p2 = NULL; | |
0bf26b29 | 26 | pc = creer_maillon(e, NULL); |
3f0f8bfd JB |
27 | |
28 | if (!L) /* liste vide */ | |
29 | return pc; | |
30 | ||
31 | while (p1 && (e >= p1->valeur)) { | |
32 | p2 = p1; | |
33 | p1 = p1->suivant; | |
34 | } | |
35 | ||
36 | if (!p2) { /* insertion en tete */ | |
37 | pc->suivant = L; | |
38 | L = pc; | |
39 | } else { /* insertion entre p2 et p1 */ | |
40 | p2->suivant = pc; | |
41 | pc->suivant = p1; | |
42 | } | |
43 | ||
44 | return L; | |
45 | } | |
46 | ||
47 | int longueur_iter(Liste L) | |
48 | { | |
49 | int longueur = 0; | |
50 | ||
105fac43 | 51 | while (L != NULL) { |
3f0f8bfd JB |
52 | L = L->suivant; |
53 | longueur++; | |
54 | } | |
55 | return longueur; | |
56 | } | |
57 | ||
58 | int longueur_rec(Liste L) | |
59 | { | |
105fac43 JB |
60 | if (L != NULL) { |
61 | return 1 + longueur_rec(L->suivant); | |
62 | } else { | |
63 | return 0; | |
64 | } | |
3f0f8bfd JB |
65 | } |
66 | ||
67 | void visualiser_iter(Liste L) | |
68 | { | |
ca2c69d5 JB |
69 | int compteur = 0; |
70 | ||
71 | printf("--Debut--\n"); | |
72 | while (L != NULL) { | |
73 | printf("L[%d]->value=%d\n", compteur, L->valeur); | |
74 | L = L->suivant; | |
75 | compteur++; | |
76 | } | |
77 | printf("--Fin--\n"); | |
78 | } | |
79 | ||
80 | void _visualiser_rec(Liste L, int compteur) | |
81 | { | |
82 | if (L != NULL) { | |
0bf26b29 | 83 | /* FIXME: suboptimal printing to stdout, put this code path outside the recursion */ |
ef5acd44 JB |
84 | if (compteur == 0) |
85 | printf("--Debut--\n"); | |
ca2c69d5 JB |
86 | printf("L[%d]->value=%d\n", compteur, L->valeur); |
87 | compteur++; | |
88 | _visualiser_rec(L->suivant, compteur); | |
89 | if (compteur == (longueur_rec(L) - 1)) | |
90 | printf("--Fin--\n"); | |
91 | } | |
92 | ||
3f0f8bfd JB |
93 | } |
94 | ||
95 | void visualiser_rec(Liste L) | |
96 | { | |
ca2c69d5 JB |
97 | int compteur = 0; |
98 | ||
ca2c69d5 | 99 | _visualiser_rec(L, compteur); |
3f0f8bfd JB |
100 | } |
101 | ||
ef5acd44 | 102 | bool rechercher_iter(element e, Liste L) |
3f0f8bfd | 103 | { |
ef5acd44 JB |
104 | bool rt_val = false; |
105 | ||
85bdc677 JB |
106 | while (L != NULL) { |
107 | if (L->valeur == e) { | |
cdc1c7e2 | 108 | rt_val = true; |
85bdc677 JB |
109 | break; |
110 | } | |
111 | L = L->suivant; | |
ef5acd44 | 112 | } |
ef5acd44 | 113 | return rt_val; |
3f0f8bfd JB |
114 | } |
115 | ||
116 | Liste rechercher_rec(element e, Liste L) | |
117 | { | |
0bf26b29 | 118 | if (L->valeur != e && L->suivant != NULL) { |
f23fb1de JB |
119 | return L = rechercher_rec(e, L->suivant); |
120 | } | |
3f0f8bfd JB |
121 | } |
122 | ||
123 | Liste ajouter_rec(element e, Liste L) | |
124 | { | |
0bf26b29 JB |
125 | if (!L || !(L->valeur < e)) { |
126 | return creer_maillon(e, L); | |
127 | } | |
128 | ||
129 | L->suivant = ajouter_rec(e, L->suivant); | |
130 | ||
131 | return L; | |
3f0f8bfd JB |
132 | } |
133 | ||
134 | Liste supprimer_iter(element e, Liste L) | |
135 | { | |
0bf26b29 JB |
136 | Cellule *pavant = NULL; |
137 | Cellule *pdebut = L; | |
c31b68a4 | 138 | |
0bf26b29 JB |
139 | while (L != NULL) { |
140 | /* supprimer en fin de liste */ | |
141 | if (L->valeur == e && L->suivant == NULL) { | |
142 | free(L); | |
143 | pavant->suivant = NULL; | |
144 | return pdebut; | |
c31b68a4 | 145 | /* supprimer au début de la liste */ |
0bf26b29 JB |
146 | } else if (L->valeur == e && pavant == NULL) { |
147 | Cellule *pcourant = L; | |
148 | free(L); | |
149 | return pcourant->suivant; | |
c31b68a4 | 150 | /* supprimer au mileu de la liste */ |
0bf26b29 JB |
151 | } else if (L->valeur == e) { |
152 | Cellule *pcourant = L; | |
153 | free(L); | |
154 | L = pavant; | |
155 | L->suivant = pcourant->suivant->suivant; | |
156 | return pdebut; | |
157 | } | |
158 | pavant = L; | |
159 | L = L->suivant; | |
160 | } | |
3f0f8bfd JB |
161 | } |
162 | ||
163 | Liste supprimer_rec(element e, Liste L) | |
164 | { | |
c31b68a4 JB |
165 | if (L == NULL) { |
166 | return L; | |
167 | } | |
168 | if (L->valeur == e) { | |
169 | Cellule *p = L; | |
170 | L = L->suivant; | |
171 | free(p); | |
172 | } else { | |
173 | L->suivant = supprimer_rec(e, L->suivant); | |
174 | } | |
175 | return L; | |
3f0f8bfd JB |
176 | } |
177 | ||
178 | Liste inverser_iter(Liste L) | |
179 | { | |
180 | /* ... */ | |
181 | } | |
182 | ||
183 | Liste inverser_rec(Liste L) | |
184 | { | |
185 | /* ... */ | |
186 | } | |
187 | ||
5e90a798 JB |
188 | void liberer_iter(Liste L) |
189 | { | |
940a20a4 JB |
190 | while (!L) { |
191 | Cellule *pcourant = L; | |
192 | free(L); | |
193 | L = pcourant->suivant; | |
194 | } | |
5e90a798 JB |
195 | } |
196 | ||
0bf26b29 JB |
197 | void liberer_rec(Liste L) |
198 | { | |
199 | if (!L) { | |
200 | liberer_rec(L->suivant); | |
201 | free(L); | |
202 | } | |
203 | } | |
204 | ||
3f0f8bfd JB |
205 | /****************************************************************************/ |
206 | int main() | |
207 | { | |
208 | int x; | |
209 | Liste L = NULL; | |
105fac43 JB |
210 | L = ajouter_iter(2, L); |
211 | L = ajouter_iter(1, L); | |
212 | L = ajouter_iter(3, L); | |
85bdc677 JB |
213 | L = ajouter_iter(4, L); |
214 | printf("Saisir un entier a chercher dans la liste L\n"); | |
3f0f8bfd | 215 | scanf("%d", &x); |
ca2c69d5 | 216 | printf("L a pour longueur %d\n", longueur_rec(L)); |
3f0f8bfd | 217 | visualiser_iter(L); |
ca2c69d5 | 218 | visualiser_rec(L); |
85bdc677 JB |
219 | if (rechercher_iter(x, L)) |
220 | printf("L'element %d est present dans L\n", x); | |
221 | else | |
222 | printf("L'element %d n'est pas present dans L\n", x); | |
f23fb1de JB |
223 | if (rechercher_rec(x, L) != NULL) |
224 | printf("L'element %d est present dans L\n", x); | |
225 | else | |
226 | printf("L'element %d n'est pas present dans L\n", x); | |
0bf26b29 JB |
227 | L = ajouter_rec(6, L); |
228 | L = ajouter_rec(5, L); | |
229 | L = ajouter_rec(7, L); | |
230 | visualiser_iter(L); | |
c31b68a4 JB |
231 | /* L = supprimer_iter(1, L); |
232 | L = supprimer_iter(4, L); | |
233 | L = supprimer_iter(2, L); */ | |
234 | L = supprimer_rec(1, L); | |
235 | L = supprimer_rec(4, L); | |
236 | L = supprimer_rec(2, L); | |
0bf26b29 JB |
237 | visualiser_rec(L); |
238 | visualiser_iter(L); | |
c31b68a4 JB |
239 | liberer_rec(L); |
240 | //liberer_iter(L); | |
3f0f8bfd JB |
241 | /* ... */ |
242 | } | |
243 | ||
244 | /****************************************************************************/ | |
0146cff3 | 245 | /* vim:noet:ts=8:sw=8:textwidth=80 */ |