Les listes

liste.c

#include `<stdio.h>`

#include `<stdlib.h>`
#include `<stdbool.h>`

typedef struct Liste *liste; /* liste est de type "adresse vers une struct Liste" */

typedef int TYPELT; /* TYPELT est un type generique, ici un entier */

struct Liste
{
    TYPELT a;
    liste suivant;
};

liste liste_vide()
{
    /* une liste vide, c'est une liste qui n'a pas d'adressse */
    return NULL; /* NULL veut dire "pas d'adresse dans la memoire" */
    /* (il n'y a pas d'adresse en memoire qui contient la liste) */
}

bool est_vide(liste L)
{
    if (L == NULL)
    {
    return true;
    }
    else
    {
    return false;
    }
    /* on peut simplifier la fonction par "return L == NULL" */
}

liste cons(TYPELT x, liste L)
{
    /* 3 etapes: creation d'une structure Liste
               remplissage du premier champ: TYPELT a
               remplissage du deuxieme champ: liste suivant

   */

    /* 1ere etape: creation d'une structure Liste */
    /* on demande à l'ordinateur, une adresse memoire contenant une structure Liste */
    liste nouvelle_liste;

    nouvelle_liste = (liste) malloc(sizeof(struct Liste));
    /* on verifie toujours que l'allocation memoire s'est bien effectuee */
    if (nouvelle_liste == NULL)
    {
    printf("Erreur d'allocation memoire dans la fonction cons\n");
    exit(EXIT_FAILURE);
    }

    /* deuxieme etape, on remplit le premier champ */
    (*nouvelle_liste).a = x;

    /* troisieme etape: on remplit le deuxieme champ */
    (*nouvelle_liste).suivant = L;

    return nouvelle_liste;
}

TYPELT premier(liste L)
{
   if (est_vide(L))
   {
      printf("Erreur dans la fonction premier: liste vide!\n");
      exit(EXIT_FAILURE);
   }
   return (*L).a;
}

liste reste(liste L)
{
    if (est_vide(L))
    {
    return liste_vide();
    }
    else
    {
    return (*L).suivant;
    }
}

int longueurR(liste L)
{
   if (est_vide(L))
   {
     return 0;
   }
   else
   {
     return 1 + longueurR(reste(L)); 
   }
}

int longueurI(liste L)
{
    int c;
    c = 0;
    while (! est_vide(L))
    {
    c = c + 1;
    L = reste(L);
    }
    return c;
}

void affiche(liste L)
{
    printf("( ");
    while (! est_vide(L))
    {
    printf("%d ", premier(L));
    L = reste(L);
    }
    printf(")\n");
}

TYPELT neme_elementR(int n, liste L)
{
    if (est_vide(L))
    {
    printf("Erreur dans neme_elementR: liste vide\n");
    exit(EXIT_FAILURE);
    } 
    if (n == 0)
    {
    printf("Erreur dans neme_elementR: n == 0\n");
    exit(EXIT_FAILURE);
    } 
    if (n == 1)
    {
    return premier(L);
    }
    else
    {
    return neme_elementR(n-1, reste(L));
    } 
}

TYPELT neme_elementI(int n, liste L)
{
    while( (n > 1) && (! est_vide(L)))
    {
    n = n-1;
    L = reste(L);
    }
    if ((n == 0) || (est_vide(L)))
    {
    printf("Erreur dans neme_elementI\n");
    exit(EXIT_FAILURE);
    }
    return premier(L);
}

liste supprimer_element(TYPELT a, liste L)
{
    if (est_vide(L))
    {
    return L;
    }
    else
    {
    if (a == premier(L))
    {
      return supprimer_element(a, reste(L));
    }
    else
    {
      return cons(premier(L), supprimer_element(a, reste(L)));
    }
    }
}

int main()
{
   liste L;
   L = cons(8, cons(5, cons(0, cons(11, liste_vide()))));
   affiche(L);
   printf("longueur de la liste (recursif): %d\n", longueurR(L));
   printf("longueur de la liste (iteratif): %d\n", longueurI(L));

   printf("Recursif: Le 3eme element de L vaut: %d\n", neme_elementR(3, L));
   printf("Iteratif: Le 3eme element de L vaut: %d\n", neme_elementI(3, L));
   printf("Recursif: Le 1er element de L vaut: %d\n", neme_elementR(1, L));
   printf("Iteratif: Le 1er element de L vaut: %d\n", neme_elementI(1, L));
/*
   printf("Recursif: Le 11eme element de L vaut: %d\n", neme_elementR(11, L));
   printf("Iteratif: Le 11eme element de L vaut: %d\n", neme_elementI(11, L));

*/
   L = cons(8, cons(5, cons(0, cons(11, liste_vide()))));
   L = cons(8, cons(3, cons(8, cons(5, cons(5, L)))));
   affiche(L);

   affiche(supprimer_element(1, L));
   affiche(supprimer_element(5, L));
   affiche(supprimer_element(5, supprimer_element(8, L)));

   return EXIT_SUCCESS;
}

Devoir maison

Exercices vus en cours

La Pile vue comme un tableau

pile.c

#include `<stdio.h>`

typedef int TYPELT;                                                                                                                       

struct Pile                                                                                                                               
{                                                                                                                                         
    TYPELT[1000] Tab;                                                                                                                       
    int h;                                                                                                                                  
}                                                                                                                                         

/* pile_vide()
   est_vide()
   empiler
   sommet
   depiler

 */

int main()
{
    pile p;
    p = pile_vide();
    p = empiler(1, p);
    p = empiler(5, p);
    printf("sommet de p = %d\n", sommet(p));
    affiche(p);
    p = depiler(p);
    printf("sommet de p = %d\n", sommet(p));
    affiche(p);
    return EXIT_SUCCESS;
}