TP5 exo4: Implement recursive search function inside a linked list

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

diff --git a/TP5/exo4/liste_chainee.c b/TP5/exo4/liste_chainee.c
index c46f1491b2e97acc97b327ae933a3684cf0ef51e..c04ccc2db85d58c293b05959fa27df0fe9ce8a20 100644 (file)
--- a/TP5/exo4/liste_chainee.c
+++ b/TP5/exo4/liste_chainee.c
@@ -3,6 +3,7 @@
 /********************************************************************/
 #include <stdio.h>
 #include <stdlib.h>
+#include <stdbool.h>
 
 typedef int element;
 
@@ -42,11 +43,7 @@ int longueur_iter(Liste L)
 {
        int longueur = 0;
 
-       if (!L)
-               return longueur;
-
-       while ( L->suivant != NULL)
-       {
+       while (L != NULL) {
                L = L->suivant;
                longueur++;
        }
@@ -55,27 +52,67 @@ int longueur_iter(Liste L)
 
 int longueur_rec(Liste L)
 {
-       /* ... */
+       if (L != NULL) {
+               return 1 + longueur_rec(L->suivant);
+       } else {
+               return 0;
+       }
 }
 
 void visualiser_iter(Liste L)
 {
-       /* ... */
+       int compteur = 0;
+
+       printf("--Debut--\n");
+       while (L != NULL) {
+               printf("L[%d]->value=%d\n", compteur, L->valeur);
+               L = L->suivant;
+               compteur++;
+       }
+       printf("--Fin--\n");
+}
+
+void _visualiser_rec(Liste L, int compteur)
+{
+       if (L != NULL) {
+               if (compteur == 0)
+                       printf("--Debut--\n");
+               printf("L[%d]->value=%d\n", compteur, L->valeur);
+               compteur++;
+               _visualiser_rec(L->suivant, compteur);
+               if (compteur == (longueur_rec(L) - 1))
+                       printf("--Fin--\n");
+       }
+
 }
 
 void visualiser_rec(Liste L)
 {
-       /* ... */
+       int compteur = 0;
+
+       _visualiser_rec(L, compteur);
 }
 
-int rechercher_iter(element e, Liste L)
+bool rechercher_iter(element e, Liste L)
 {
-       /* ... */
+       bool rt_val = false;
+
+       while (L != NULL) {
+               if (L->valeur == e) {
+                       rt_val = true;
+                       break;
+               }
+               L = L->suivant;
+       }
+       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)
@@ -108,10 +145,23 @@ int main()
 {
        int x;
        Liste L = NULL;
+       L = ajouter_iter(2, L);
+       L = ajouter_iter(1, L);
+       L = ajouter_iter(3, L);
+       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("longueur=%d\n", longueur_iter(L));
+       printf("L a pour longueur %d\n", longueur_rec(L));
        visualiser_iter(L);
+       visualiser_rec(L);
+       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);
        /* ... */
 }