appartient(x,L)

/* appartient(x,L)

 *
 * Profil:
 * =======
 *   typelt x liste -> booleee
 *
 * Exemples:
 * =========
 *   appartient(x, () ) = faux
 *   appartient(a, (a b)) = vrai
 *   appartient(a, (b a)) = vrai
 *   appartient(a, (b c)) = faux
 *
 *   appartient(a, (a b)) = (a = a) = vrai
 *                        = (a = prem( (a b) )
 *   appartient(a, (b a)) = (a = prem( (b a) ) ou appartient(a, reste( (b a) )
 *                        = (a = b) ou appartient(a, (a))
 *                        = faux  ou appartient(a, (a))
 *                        = appartient(a, (a))
 *                        = vrai
 *
 * Axiomes:
 * ========
 *   appartient(a, () ) = faux
 *   appartient(a, cons(x, L) ) = (a = x) ou appartient(a, L)
 *
 * Algorithme récursif:
 * ====================
 * fonction appartient(x: typelt, L: liste): booleen
 * debut
 *  | si est_vide(L)
 *  |  | alors retourner faux
 *  |  | sinon retourner (x = prem(L)) ou appartient(x, reste(L))
 *  | finsi
 * fin
 *
 * Algorithme itératif:
 * ====================
 * fonction appartient(x: typelt, L: liste): booleen
 * debut
 *  | ret: booleen
 *  | ret:= faux
 *  | tant que non est_vide(L) faire
 *  |  | si (x = prem(L))
 *  |  |  | alors ret:= vrai
 *  |  | finsi
 *  |  | L = reste(L)                  // passage au suivant
 *  | fin tant que
 *  | retourner ret
 * fin
 *
 */

#include "liste.h"

BOOLEEN appartientR(int x, liste L)
{
  if (est_vide(L))
  {
    return FAUX;
  }
  else
  {
    return (x == prem(L) || appartientR(x, reste(L)));
  }
}

BOOLEEN appartientI(int x, liste L)
{
  BOOLEEN ret = FAUX;
  while (! est_vide(L))
  {
    if (x == prem(L))
    {
      ret = VRAI;
    }
    L = reste(L);
  }
  return ret;
}

void test_appartenance(int x, liste L)
{
  BOOLEEN retR = appartientR(x, L);
  BOOLEEN retI = appartientI(x, L);
  if (retR)
  {
    printf("algo recursif: %d appartient a la liste", x);
    affichage(L);
  }
  else
  {
    printf("algo recursif: %d n'appartient pas a la liste", x);
    affichage(L);
  }
  if (retI)
  {
    printf("algo iteratif: %d appartient a la liste", x);
    affichage(L);
  }
  else
  {
    printf("algo iteratif: %d n'appartient pas a la liste", x);
    affichage(L);
  }
}

int main()
{
  /* test de longueurR et longueurI */
  liste L1 = l_vide();
  L1 = cons(1, L1);
  L1 = cons(5, L1);
  L1 = cons(2, L1);
  L1 = cons(3, L1);
  L1 = cons(1, L1);
  test_appartenance(1,L1);
  test_appartenance(2,L1);
  test_appartenance(3,L1);
  test_appartenance(4,L1);
  test_appartenance(5,L1);

}