Fix a GCC flag in Makefiles

[Algorithmic_C.git] / TP5 / exo4 / liste_chainee.c

diff --git a/TP5/exo4/liste_chainee.c b/TP5/exo4/liste_chainee.c
index b21ad04a501b051e71c3ab463672fd364e3f9d0d..add8b224f8d3bab04fc1d614ba66680c3ce53a9d 100644 (file)
--- a/TP5/exo4/liste_chainee.c
+++ b/TP5/exo4/liste_chainee.c
@@ -12,13 +12,19 @@ typedef struct cellule {
        struct cellule *suivant;
 } Cellule, *Liste;
 
+Cellule *creer_maillon(element e, Cellule * suivant)
+{
+       Cellule *pnouveau = malloc(sizeof(Cellule));
+       pnouveau->valeur = e;
+       pnouveau->suivant = suivant;
+       return pnouveau;
+}
+
 Liste ajouter_iter(element e, Liste L)
 {
        Cellule *pc, *p1 = L, *p2 = NULL;
 
-       pc = (Cellule *) malloc(sizeof(Cellule));
-       pc->valeur = e;
-       pc->suivant = NULL;
+       pc = creer_maillon(e, NULL);
 
        if (!L)                 /* liste vide */
                return pc;
@@ -75,6 +81,7 @@ void visualiser_iter(Liste L)
 void _visualiser_rec(Liste L, int compteur)
 {
        if (L != NULL) {
+               /* FIXME: suboptimal printing to stdout, put this code path outside the recursion */
                if (compteur == 0)
                        printf("--Debut--\n");
                printf("L[%d]->value=%d\n", compteur, L->valeur);
@@ -97,26 +104,60 @@ bool rechercher_iter(element e, Liste L)
 {
        bool rt_val = false;
 
-       while (L != NULL && L->valeur != e) {
+       while (L != NULL) {
+               if (L->valeur == e) {
+                       rt_val = true;
+                       break;
+               }
                L = L->suivant;
        }
-       if (L->valeur == e) 
-               rt_val = true;
        return rt_val;
 }
 
 Liste rechercher_rec(element e, Liste L)
 {
+       if (L->valeur != e && L->suivant != NULL) {
+               return L = rechercher_rec(e, L->suivant);
+       }
 }
 
 Liste ajouter_rec(element e, Liste L)
 {
-       /* ... */
+       if (!L || !(L->valeur < e)) {
+               return creer_maillon(e, L);
+       }
+
+       L->suivant = ajouter_rec(e, L->suivant);
+
+       return L;
 }
 
 Liste supprimer_iter(element e, Liste L)
 {
-       /* ... */
+       Cellule *pavant = NULL;
+       Cellule *pdebut = L;
+       while (L != NULL) {
+               /* supprimer en fin de liste */
+               if (L->valeur == e && L->suivant == NULL) {
+                       free(L);
+                       pavant->suivant = NULL;
+                       return pdebut;
+                       /* supprimer au début de la liste */
+               } else if (L->valeur == e && pavant == NULL) {
+                       Cellule *pcourant = L;
+                       free(L);
+                       return pcourant->suivant;
+                       /* supprimer au mileu de la liste */
+               } else if (L->valeur == e) {
+                       Cellule *pcourant = L;
+                       free(L);
+                       L = pavant;
+                       L->suivant = pcourant->suivant->suivant;
+                       return pdebut;
+               }
+               pavant = L;
+               L = L->suivant;
+       }
 }
 
 Liste supprimer_rec(element e, Liste L)
@@ -134,6 +175,19 @@ Liste inverser_rec(Liste L)
        /* ... */
 }
 
+void liberer_iter(Liste L)
+{
+
+}
+
+void liberer_rec(Liste L)
+{
+       if (!L) {
+               liberer_rec(L->suivant);
+               free(L);
+       }
+}
+
 /****************************************************************************/
 int main()
 {
@@ -142,14 +196,30 @@ int main()
        L = ajouter_iter(2, L);
        L = ajouter_iter(1, L);
        L = ajouter_iter(3, L);
-       printf("Saisir un entier a ajouter a la liste L\n");
+       L = ajouter_iter(4, L);
+       printf("Saisir un entier a chercher dans la liste L\n");
        scanf("%d", &x);
-       L = ajouter_iter(x, L);
        printf("L a pour longueur %d\n", longueur_rec(L));
        visualiser_iter(L);
        visualiser_rec(L);
-       if (rechercher_iter(3, L))
-               printf("Element 3 est present dans L\n");
+       if (rechercher_iter(x, L))
+               printf("L'element %d est present dans L\n", x);
+       else
+               printf("L'element %d n'est pas present dans L\n", x);
+       if (rechercher_rec(x, L) != NULL)
+               printf("L'element %d est present dans L\n", x);
+       else
+               printf("L'element %d n'est pas present dans L\n", x);
+       L = ajouter_rec(6, L);
+       L = ajouter_rec(5, L);
+       L = ajouter_rec(7, L);
+       visualiser_iter(L);
+       L = supprimer_iter(1, L);
+       L = supprimer_iter(4, L);
+       L = supprimer_iter(2, L);
+       visualiser_rec(L);
+       visualiser_iter(L);
+       liberer_rec(L);
        /* ... */
 }