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
));
182 Liste
inverser_rec(Liste L
)
185 return inserer_fin(L
->valeur
, inverser_rec(L
->suivant
));
190 /****************************************************************************/
195 printf("liste vide\n");
199 printf("longueur=%d\n", longueur_iter(L
));
200 printf("longueur=%d\n", longueur_rec(L
));
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
);
215 printf("longueur=%d\n", longueur_iter(L
));
216 printf("longueur=%d\n", longueur_rec(L
));
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
));
223 printf("ajout (rec) de 4\n");
224 L
= ajouter_rec(4, L
);
226 printf("ajout (rec) de 8\n");
227 L
= ajouter_rec(8, L
);
230 printf("suppression (iter) de 4\n");
231 supprimer_iter(4, L
);
233 printf("suppression (rec) de 6\n");
237 printf("liste inversee (iter)\n");
238 Liste inv
= inverser_iter(L
);
239 visualiser_iter(inv
);
241 printf("Liste inversee (rec)\n");
242 Liste inv2
= inverser_rec(inv
);
243 visualiser_iter(inv2
);
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, ... */
248 /****************************************************************************/
250 /* trace d'execution :
272 suppression (iter) de 4
274 suppression (rec) de 6
276 liste inversee (iter)