851e35428f6d63f1ad12b2805500501bbb79effd
1 /********************************************************************/
2 /* Implantation d'une liste triee d'entiers */
3 /********************************************************************/
10 typedef struct cellule
{
12 struct cellule
*suivant
;
15 Cellule
*creer_maillon(element e
, Cellule
* suivant
)
17 Cellule
*pnouveau
= malloc(sizeof(Cellule
));
19 pnouveau
->suivant
= suivant
;
23 Liste
ajouter_iter(element e
, Liste L
)
25 Cellule
*pc
, *p1
= L
, *p2
= NULL
;
26 pc
= creer_maillon(e
, NULL
);
28 if (!L
) /* liste vide */
31 while (p1
&& (e
>= p1
->valeur
)) {
36 if (!p2
) { /* insertion en tete */
39 } else { /* insertion entre p2 et p1 */
47 int longueur_iter(Liste L
)
58 int longueur_rec(Liste L
)
61 return 1 + longueur_rec(L
->suivant
);
67 void visualiser_iter(Liste L
)
71 printf("--Debut--\n");
73 printf("L[%d]->value=%d\n", compteur
, L
->valeur
);
80 void _visualiser_rec(Liste L
, int compteur
)
83 /* FIXME: suboptimal printing to stdout, put this code path outside the recursion */
85 printf("--Debut--\n");
86 printf("L[%d]->value=%d\n", compteur
, L
->valeur
);
88 _visualiser_rec(L
->suivant
, compteur
);
89 if (compteur
== (longueur_rec(L
) - 1))
95 void visualiser_rec(Liste L
)
99 _visualiser_rec(L
, compteur
);
102 bool rechercher_iter(element e
, Liste L
)
107 if (L
->valeur
== e
) {
116 Liste
rechercher_rec(element e
, Liste L
)
118 if (L
->valeur
!= e
&& L
->suivant
!= NULL
) {
119 return L
= rechercher_rec(e
, L
->suivant
);
123 Liste
ajouter_rec(element e
, Liste L
)
125 if (!L
|| !(L
->valeur
< e
)) {
126 return creer_maillon(e
, L
);
129 L
->suivant
= ajouter_rec(e
, L
->suivant
);
134 Liste
supprimer_iter(element e
, Liste L
)
136 Cellule
*pavant
= NULL
;
140 /* supprimer en fin de liste */
141 if (L
->valeur
== e
&& L
->suivant
== NULL
) {
143 pavant
->suivant
= NULL
;
145 /* supprimer au début de la liste */
146 } else if (L
->valeur
== e
&& pavant
== NULL
) {
147 Cellule
*pcourant
= L
;
149 return pcourant
->suivant
;
150 /* supprimer au mileu de la liste */
151 } else if (L
->valeur
== e
) {
152 Cellule
*pcourant
= L
;
155 L
->suivant
= pcourant
->suivant
->suivant
;
163 Liste
supprimer_rec(element e
, Liste L
)
168 if (L
->valeur
== e
) {
173 L
->suivant
= supprimer_rec(e
, L
->suivant
);
178 Liste
inverser_iter(Liste L
)
183 Liste
inverser_rec(Liste L
)
188 void liberer_iter(Liste L
)
191 Cellule
*pcourant
= L
;
193 L
= pcourant
->suivant
;
197 void liberer_rec(Liste L
)
200 liberer_rec(L
->suivant
);
205 /****************************************************************************/
210 L
= ajouter_iter(2, L
);
211 L
= ajouter_iter(1, L
);
212 L
= ajouter_iter(3, L
);
213 L
= ajouter_iter(4, L
);
214 printf("Saisir un entier a chercher dans la liste L\n");
216 printf("L a pour longueur %d\n", longueur_rec(L
));
219 if (rechercher_iter(x
, L
))
220 printf("L'element %d est present dans L\n", x
);
222 printf("L'element %d n'est pas present dans L\n", x
);
223 if (rechercher_rec(x
, L
) != NULL
)
224 printf("L'element %d est present dans L\n", x
);
226 printf("L'element %d n'est pas present dans L\n", x
);
227 L
= ajouter_rec(6, L
);
228 L
= ajouter_rec(5, L
);
229 L
= ajouter_rec(7, L
);
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
);
244 /****************************************************************************/
245 /* vim:noet:ts=8:sw=8:textwidth=80 */