5c219e755d0fb31aa693f4d2092f72354d69a32a
1 /********************************************************************/
2 /* Implantation d'une liste triee d'entiers */
3 /********************************************************************/
9 typedef struct cellule
{
11 struct cellule
*suivant
;
14 Liste
ajouter_iter(element e
, Liste L
)
16 Cellule
*pc
, *p1
= L
, *p2
= NULL
;
18 pc
= (Cellule
*) malloc(sizeof(Cellule
));
22 if (!L
) /* liste vide */
24 while (p1
&& (e
>= p1
->valeur
)) {
29 if (!p2
) { /* insertion en tete */
32 } else { /* insertion entre p2 et p1 */
40 int longueur_iter(Liste L
)
50 int longueur_rec(Liste L
)
54 return 1 + longueur_rec(L
->suivant
);
57 void visualiser_iter(Liste L
)
60 printf("%d ", L
->valeur
);
66 void visualiser_aux(Liste L
)
69 printf("%d ", L
->valeur
);
70 visualiser_aux(L
->suivant
);
74 void visualiser_rec(Liste L
)
80 int rechercher_iter(element e
, Liste L
)
90 int rechercher_rec(element e
, Liste L
)
96 return rechercher_rec(e
, L
->suivant
);
99 Liste
rechercher_rec2(element e
, Liste L
)
101 if (!L
|| e
== L
->valeur
)
104 return rechercher_rec2(e
, L
->suivant
);
107 Liste
ajouter_rec(element e
, Liste L
)
110 L
= (Cellule
*) malloc(sizeof(Cellule
)); /* liste vide */
113 } else if (e
< L
->valeur
) { /* ajouter DEVANT la tete */
114 Cellule
*p
= (Cellule
*) malloc(sizeof(Cellule
));
117 L
= p
; /* nouvelle tete de liste */
119 L
->suivant
= ajouter_rec(e
, L
->suivant
); /* ajouter DERRIERE la tete */
123 Liste
supprimer_iter(element e
, Liste 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 */
138 Liste
supprimer_rec(element e
, Liste L
)
140 if (!L
) ; /* element absent - on ne fait rien */
141 else if (L
->valeur
== e
) {
146 L
->suivant
= supprimer_rec(e
, L
->suivant
);
150 Liste
inverser_iter(Liste L
)
152 Liste cell
= NULL
; /* une cellule temporaire */
153 Liste inv
= NULL
; /* la liste inversee */
156 cell
= L
; /* on prend la premiere cellule de la liste */
157 L
= L
->suivant
; /* le debut de la liste devient l'element suivant */
158 cell
->suivant
= inv
; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer */
159 inv
= cell
; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */
164 Liste
inserer_fin(element e
, Liste L
)
166 Cellule
*pc
, *p1
= L
, *p2
= NULL
;
167 pc
= (Cellule
*) malloc(sizeof(Cellule
));
181 Liste
inverser_rec(Liste L
)
184 return inserer_fin(L
->valeur
, inverser_rec(L
->suivant
));
189 /****************************************************************************/
194 printf("liste vide\n");
198 printf("longueur=%d\n", longueur_iter(L
));
199 printf("longueur=%d\n", longueur_rec(L
));
201 printf("ajout de 3\n");
202 L
= ajouter_iter(3, L
);
203 printf("ajout de 6\n");
204 L
= ajouter_iter(6, L
);
205 printf("ajout de 1\n");
206 L
= ajouter_iter(1, L
);
207 printf("ajout de 10\n");
208 L
= ajouter_iter(10, L
);
209 printf("ajout de 6\n");
210 L
= ajouter_iter(6, L
);
214 printf("longueur=%d\n", longueur_iter(L
));
215 printf("longueur=%d\n", longueur_rec(L
));
217 printf("recherche de %d = %d\n", 3, rechercher_iter(3, L
));
218 printf("recherche de %d = %d\n", 3, rechercher_rec(3, L
));
219 printf("recherche de %d = %d\n", 4, rechercher_iter(4, L
));
220 printf("recherche de %d = %d\n", 4, rechercher_rec(4, L
));
222 printf("ajout (rec) de 4\n");
223 L
= ajouter_rec(4, L
);
225 printf("ajout (rec) de 8\n");
226 L
= ajouter_rec(8, L
);
229 printf("suppression (iter) de 4\n");
230 supprimer_iter(4, L
);
232 printf("suppression (rec) de 6\n");
236 printf("liste inversee (iter)\n");
237 Liste inv
= inverser_iter(L
);
238 visualiser_iter(inv
);
240 printf("Liste inversee (rec)\n");
241 Liste inv2
= inverser_rec(inv
);
242 visualiser_iter(inv2
);
244 /* 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, ... */
247 /****************************************************************************/
249 /* trace d'execution :
271 suppression (iter) de 4
273 suppression (rec) de 6
275 liste inversee (iter)