eff60c44928e498d2b25b1caab743810c8c10fd8
1 /********************************************************************/
2 /* Implantation d'une liste triee d'entiers */
3 /********************************************************************/
9 typedef struct cellule
{
11 struct cellule
*suivant
;
16 Liste
ajouter_iter(element e
, Liste L
)
18 Cellule
*pc
, *p1
=L
, *p2
=NULL
;
20 pc
= (Cellule
*)malloc(sizeof(Cellule
));
21 pc
->valeur
=e
;pc
->suivant
=NULL
;
23 if (!L
) /* liste vide */ return pc
;
24 while (p1
&& (e
>= p1
->valeur
))
30 if (!p2
) /* insertion en tete */ {pc
->suivant
= L
; L
=pc
; }
31 else {/* insertion entre p2 et p1 */
40 int longueur_iter(Liste L
)
52 int longueur_rec(Liste L
)
55 return 1+longueur_rec(L
->suivant
);
59 void visualiser_iter(Liste L
)
63 printf("%d ",L
->valeur
);
70 void visualiser_aux(Liste L
)
74 printf("%d ",L
->valeur
);
75 visualiser_aux(L
->suivant
);
80 void visualiser_rec(Liste L
)
87 int rechercher_iter(element e
, Liste L
)
91 if(e
== L
->valeur
) return 1;
98 int rechercher_rec(element e
, Liste L
)
100 if(L
== NULL
) return 0;
101 if(e
==L
->valeur
) return 1;
102 return rechercher_rec(e
,L
->suivant
);
106 Liste
rechercher_rec2(element e
, Liste L
)
108 if(!L
|| e
==L
->valeur
) return L
;
109 else return rechercher_rec2(e
,L
->suivant
);
113 Liste
ajouter_rec(element e
, Liste L
)
117 L
=(Cellule
*)malloc(sizeof(Cellule
)); /* liste vide */
118 L
->valeur
=e
;L
->suivant
=NULL
;
120 else if(e
< L
->valeur
) /* ajouter DEVANT la tete */
122 Cellule
*p
=(Cellule
*)malloc(sizeof(Cellule
));
123 p
->valeur
=e
; p
->suivant
=L
;
124 L
=p
; /* nouvelle tete de liste */
126 else L
->suivant
=ajouter_rec(e
,L
->suivant
); /* ajouter DERRIERE la tete */
131 Liste
supprimer_iter(element e
, Liste L
)
137 prec
->suivant
= L
->suivant
; /* le suivant de prec devient le suivant de L */
138 free(L
); /* liberation memoire pour L */
148 Liste
supprimer_rec(element e
, Liste L
)
150 if(!L
) ; /* element absent - on ne fait rien */
151 else if(L
->valeur
==e
)
157 else L
->suivant
=supprimer_rec(e
,L
->suivant
);
162 Liste
inverser_iter(Liste L
)
164 Liste cell
=NULL
; /* une cellule temporaire */
165 Liste inv
=NULL
; /* la liste inversee */
169 cell
=L
; /* on prend la premiere cellule de la liste */
170 L
=L
->suivant
; /* le debut de la liste devient l'element suivant */
171 cell
->suivant
=inv
; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer*/
172 inv
=cell
; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */
179 Liste
inserer_fin(element e
, Liste L
)
181 Cellule
*pc
, *p1
=L
, *p2
=NULL
;
182 pc
= (Cellule
*)malloc(sizeof(Cellule
));
183 pc
->valeur
=e
;pc
->suivant
=NULL
;
196 Liste
inverser_rec(Liste L
)
199 return inserer_fin(L
->valeur
, inverser_rec(L
->suivant
));
205 /****************************************************************************/
210 printf("liste vide\n");
214 printf("longueur=%d\n",longueur_iter(L
));
215 printf("longueur=%d\n",longueur_rec(L
));
217 printf("ajout de 3\n");
219 printf("ajout de 6\n");
221 printf("ajout de 1\n");
223 printf("ajout de 10\n");
224 L
=ajouter_iter(10,L
);
225 printf("ajout de 6\n");
230 printf("longueur=%d\n",longueur_iter(L
));
231 printf("longueur=%d\n",longueur_rec(L
));
233 printf("recherche de %d = %d\n",3,rechercher_iter(3,L
));
234 printf("recherche de %d = %d\n",3,rechercher_rec(3,L
));
235 printf("recherche de %d = %d\n",4,rechercher_iter(4,L
));
236 printf("recherche de %d = %d\n",4,rechercher_rec(4,L
));
238 printf("ajout (rec) de 4\n");
241 printf("ajout (rec) de 8\n");
245 printf("suppression (iter) de 4\n");
248 printf("suppression (rec) de 6\n");
252 printf("liste inversee (iter)\n");
253 Liste inv
= inverser_iter(L
);
254 visualiser_iter(inv
);
256 printf("Liste inversee (rec)\n");
257 Liste inv2
= inverser_rec(inv
);
258 visualiser_iter(inv2
);
260 /* 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, ... */
264 /****************************************************************************/
266 /* trace d'execution :
289 suppression (iter) de 4
291 suppression (rec) de 6
293 liste inversee (iter)