Commit | Line | Data |
---|---|---|
f5904379 JB |
1 | /********************************************************************/ |
2 | /* Implantation d'une liste triee d'entiers */ | |
3 | /********************************************************************/ | |
4 | #include <stdio.h> | |
5 | #include <stdlib.h> | |
6 | ||
7 | typedef int element; | |
8 | ||
9 | typedef struct cellule { | |
c31b68a4 JB |
10 | element valeur; |
11 | struct cellule *suivant; | |
f5904379 JB |
12 | } Cellule, *Liste; |
13 | ||
f5904379 JB |
14 | Liste ajouter_iter(element e, Liste L) |
15 | { | |
c31b68a4 JB |
16 | Cellule *pc, *p1 = L, *p2 = NULL; |
17 | ||
18 | pc = (Cellule *) malloc(sizeof(Cellule)); | |
19 | pc->valeur = e; | |
20 | pc->suivant = NULL; | |
21 | ||
22 | if (!L) /* liste vide */ | |
23 | return pc; | |
24 | while (p1 && (e >= p1->valeur)) { | |
25 | p2 = p1; | |
26 | p1 = p1->suivant; | |
27 | } | |
28 | ||
29 | if (!p2) { /* insertion en tete */ | |
30 | pc->suivant = L; | |
31 | L = pc; | |
32 | } else { /* insertion entre p2 et p1 */ | |
33 | p2->suivant = pc; | |
34 | pc->suivant = p1; | |
35 | } | |
36 | ||
37 | return L; | |
f5904379 JB |
38 | } |
39 | ||
f5904379 JB |
40 | int longueur_iter(Liste L) |
41 | { | |
c31b68a4 JB |
42 | int res = 0; |
43 | while (L) { | |
44 | res = res + 1; | |
45 | L = L->suivant; | |
46 | } | |
47 | return res; | |
f5904379 JB |
48 | } |
49 | ||
f5904379 JB |
50 | int longueur_rec(Liste L) |
51 | { | |
c31b68a4 JB |
52 | if (!L) |
53 | return 0; | |
54 | return 1 + longueur_rec(L->suivant); | |
f5904379 JB |
55 | } |
56 | ||
f5904379 JB |
57 | void visualiser_iter(Liste L) |
58 | { | |
c31b68a4 JB |
59 | while (L) { |
60 | printf("%d ", L->valeur); | |
61 | L = L->suivant; | |
62 | } | |
63 | printf("\n"); | |
f5904379 JB |
64 | } |
65 | ||
f5904379 JB |
66 | void visualiser_aux(Liste L) |
67 | { | |
c31b68a4 JB |
68 | if (L) { |
69 | printf("%d ", L->valeur); | |
70 | visualiser_aux(L->suivant); | |
71 | } | |
f5904379 JB |
72 | } |
73 | ||
f5904379 JB |
74 | void visualiser_rec(Liste L) |
75 | { | |
c31b68a4 JB |
76 | visualiser_aux(L); |
77 | printf("\n"); | |
f5904379 JB |
78 | } |
79 | ||
f5904379 JB |
80 | int rechercher_iter(element e, Liste L) |
81 | { | |
c31b68a4 JB |
82 | while (L) { |
83 | if (e == L->valeur) | |
84 | return 1; | |
85 | L = L->suivant; | |
86 | } | |
87 | return 0; | |
f5904379 JB |
88 | } |
89 | ||
f5904379 JB |
90 | int rechercher_rec(element e, Liste L) |
91 | { | |
c31b68a4 JB |
92 | if (L == NULL) |
93 | return 0; | |
94 | if (e == L->valeur) | |
95 | return 1; | |
96 | return rechercher_rec(e, L->suivant); | |
f5904379 JB |
97 | } |
98 | ||
f5904379 JB |
99 | Liste rechercher_rec2(element e, Liste L) |
100 | { | |
c31b68a4 JB |
101 | if (!L || e == L->valeur) |
102 | return L; | |
103 | else | |
104 | return rechercher_rec2(e, L->suivant); | |
f5904379 JB |
105 | } |
106 | ||
f5904379 | 107 | Liste ajouter_rec(element e, Liste L) |
c31b68a4 JB |
108 | { |
109 | if (!L) { | |
110 | L = (Cellule *) malloc(sizeof(Cellule)); /* liste vide */ | |
111 | L->valeur = e; | |
112 | L->suivant = NULL; | |
113 | } else if (e < L->valeur) { /* ajouter DEVANT la tete */ | |
114 | Cellule *p = (Cellule *) malloc(sizeof(Cellule)); | |
115 | p->valeur = e; | |
116 | p->suivant = L; | |
117 | L = p; /* nouvelle tete de liste */ | |
118 | } else | |
119 | L->suivant = ajouter_rec(e, L->suivant); /* ajouter DERRIERE la tete */ | |
120 | return L; | |
f5904379 JB |
121 | } |
122 | ||
f5904379 JB |
123 | Liste supprimer_iter(element e, Liste L) |
124 | { | |
c31b68a4 JB |
125 | Liste prec = NULL; |
126 | while (L) { | |
127 | if (e == L->valeur) { | |
128 | prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */ | |
129 | free(L); /* liberation memoire pour L */ | |
130 | return prec; | |
131 | } | |
132 | prec = L; | |
133 | L = L->suivant; | |
134 | } | |
135 | return L; | |
f5904379 JB |
136 | } |
137 | ||
f5904379 JB |
138 | Liste supprimer_rec(element e, Liste L) |
139 | { | |
c31b68a4 JB |
140 | if (!L) ; /* element absent - on ne fait rien */ |
141 | else if (L->valeur == e) { | |
142 | Cellule *p = L; | |
143 | L = L->suivant; | |
144 | free(p); | |
145 | } else | |
146 | L->suivant = supprimer_rec(e, L->suivant); | |
147 | return L; | |
f5904379 JB |
148 | } |
149 | ||
f5904379 JB |
150 | Liste inverser_iter(Liste L) |
151 | { | |
c31b68a4 JB |
152 | Liste cell = NULL; /* une cellule temporaire */ |
153 | Liste inv = NULL; /* la liste inversee */ | |
154 | ||
155 | while (L != NULL) { | |
156 | cell = L; /* on prend la premiere cellule de la liste */ | |
157 | L = L->suivant; /* le debut de la liste devient l'element suivant */ | |
c43303a3 | 158 | cell->suivant = inv; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer */ |
c31b68a4 JB |
159 | inv = cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */ |
160 | } | |
161 | return inv; | |
f5904379 JB |
162 | } |
163 | ||
f5904379 JB |
164 | Liste inserer_fin(element e, Liste L) |
165 | { | |
c31b68a4 JB |
166 | Cellule *pc, *p1 = L, *p2 = NULL; |
167 | pc = (Cellule *) malloc(sizeof(Cellule)); | |
168 | pc->valeur = e; | |
169 | pc->suivant = NULL; | |
c43303a3 | 170 | |
c31b68a4 JB |
171 | if (!L) |
172 | return pc; | |
173 | while (p1) { | |
174 | p2 = p1; | |
175 | p1 = p1->suivant; | |
176 | } | |
177 | p2->suivant = pc; | |
178 | pc->suivant = p1; | |
179 | return L; | |
f5904379 JB |
180 | } |
181 | ||
f5904379 JB |
182 | Liste inverser_rec(Liste L) |
183 | { | |
c31b68a4 JB |
184 | if (L != NULL) { |
185 | return inserer_fin(L->valeur, inverser_rec(L->suivant)); | |
186 | } else | |
187 | return L; | |
f5904379 JB |
188 | } |
189 | ||
c31b68a4 | 190 | /****************************************************************************/ |
f5904379 JB |
191 | |
192 | int main() | |
9132827c | 193 | { |
c31b68a4 JB |
194 | Liste L = NULL; |
195 | printf("liste vide\n"); | |
196 | visualiser_iter(L); | |
197 | visualiser_rec(L); | |
198 | ||
199 | printf("longueur=%d\n", longueur_iter(L)); | |
200 | printf("longueur=%d\n", longueur_rec(L)); | |
201 | ||
202 | printf("ajout de 3\n"); | |
203 | L = ajouter_iter(3, L); | |
204 | printf("ajout de 6\n"); | |
205 | L = ajouter_iter(6, L); | |
206 | printf("ajout de 1\n"); | |
207 | L = ajouter_iter(1, L); | |
208 | printf("ajout de 10\n"); | |
209 | L = ajouter_iter(10, L); | |
210 | printf("ajout de 6\n"); | |
211 | L = ajouter_iter(6, L); | |
212 | visualiser_iter(L); | |
213 | visualiser_rec(L); | |
214 | ||
215 | printf("longueur=%d\n", longueur_iter(L)); | |
216 | printf("longueur=%d\n", longueur_rec(L)); | |
217 | ||
218 | printf("recherche de %d = %d\n", 3, rechercher_iter(3, L)); | |
219 | printf("recherche de %d = %d\n", 3, rechercher_rec(3, L)); | |
220 | printf("recherche de %d = %d\n", 4, rechercher_iter(4, L)); | |
221 | printf("recherche de %d = %d\n", 4, rechercher_rec(4, L)); | |
222 | ||
223 | printf("ajout (rec) de 4\n"); | |
224 | L = ajouter_rec(4, L); | |
225 | visualiser_iter(L); | |
226 | printf("ajout (rec) de 8\n"); | |
227 | L = ajouter_rec(8, L); | |
228 | visualiser_iter(L); | |
229 | ||
230 | printf("suppression (iter) de 4\n"); | |
231 | supprimer_iter(4, L); | |
232 | visualiser_iter(L); | |
233 | printf("suppression (rec) de 6\n"); | |
234 | supprimer_rec(6, L); | |
235 | visualiser_iter(L); | |
236 | ||
237 | printf("liste inversee (iter)\n"); | |
238 | Liste inv = inverser_iter(L); | |
239 | visualiser_iter(inv); | |
240 | ||
241 | printf("Liste inversee (rec)\n"); | |
242 | Liste inv2 = inverser_rec(inv); | |
243 | visualiser_iter(inv2); | |
244 | ||
245 | /* il faut aussi tester chaque fonction (visualiser, supprimer, rechercher, inverser, ...) sur tous les cas : liste vide, liste avec un seul element, operation sur le premier element, operation sur le dernier element, ... */ | |
f5904379 JB |
246 | } |
247 | ||
c31b68a4 | 248 | /****************************************************************************/ |
f5904379 JB |
249 | |
250 | /* trace d'execution : | |
251 | liste vide | |
252 | ||
f5904379 JB |
253 | longueur=0 |
254 | longueur=0 | |
255 | ajout de 3 | |
256 | ajout de 6 | |
257 | ajout de 1 | |
258 | ajout de 10 | |
259 | ajout de 6 | |
260 | 1 3 6 6 10 | |
261 | 1 3 6 6 10 | |
262 | longueur=5 | |
263 | longueur=5 | |
264 | recherche de 3 = 1 | |
265 | recherche de 3 = 1 | |
266 | recherche de 4 = 0 | |
267 | recherche de 4 = 0 | |
268 | ajout (rec) de 4 | |
269 | 1 3 4 6 6 10 | |
270 | ajout (rec) de 8 | |
271 | 1 3 4 6 6 8 10 | |
272 | suppression (iter) de 4 | |
273 | 1 3 6 6 8 10 | |
274 | suppression (rec) de 6 | |
275 | 1 3 6 8 10 | |
276 | liste inversee (iter) | |
277 | 10 8 6 3 1 | |
278 | Liste inversee (rec) | |
279 | 1 3 6 8 10 | |
280 | */ |