TP5: move corrections in their own directory

[Algorithmic_C.git] / TP5 / exo_c4 / liste_correction.c

/********************************************************************/
/*   Implantation d'une liste triee d'entiers                       */
/********************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef int element;

typedef struct cellule {
 element valeur;
 struct cellule *suivant; 
} Cellule, *Liste;



Liste ajouter_iter(element e, Liste L)
{
 Cellule *pc, *p1=L, *p2=NULL;

 pc = (Cellule *)malloc(sizeof(Cellule)); 
 pc->valeur=e;pc->suivant=NULL;
 
 if (!L) /* liste vide */ return pc;
 while (p1 && (e >= p1->valeur))
 {
  p2 = p1; 
  p1 = p1->suivant; 
 }

 if (!p2) /* insertion en tete */ {pc->suivant = L; L=pc; }
 else {/* insertion entre p2 et p1 */
       p2->suivant = pc; 
       pc->suivant = p1; 
      }

 return L;
}


int longueur_iter(Liste L)
{
 int res = 0;
 while(L) 
 {
  res = res + 1;
  L=L->suivant;
 }
 return res;
}


int longueur_rec(Liste L)
{
 if(!L) return 0;
 return 1+longueur_rec(L->suivant);
}


void visualiser_iter(Liste L)
{
 while (L) 
 {
  printf("%d ",L->valeur); 
  L = L->suivant;
 }
 printf("\n");
}


void visualiser_aux(Liste L)
{
 if(L) 
 {
  printf("%d ",L->valeur);
  visualiser_aux(L->suivant);
 }
}


void visualiser_rec(Liste L)
{
 visualiser_aux(L);
 printf("\n");
}


int rechercher_iter(element e, Liste L)
{
 while(L) 
 {
  if(e == L->valeur) return 1;
  L = L->suivant;
 }
 return 0;
}


int rechercher_rec(element e, Liste L)
{
 if(L == NULL) return 0;
 if(e==L->valeur) return 1;
 return rechercher_rec(e,L->suivant);
}


Liste rechercher_rec2(element e, Liste L)
{
 if(!L || e==L->valeur) return L;
 else return rechercher_rec2(e,L->suivant);
}


Liste ajouter_rec(element e, Liste L)
{ 
 if(!L)	
 {
  L=(Cellule *)malloc(sizeof(Cellule)); /* liste vide */
  L->valeur=e;L->suivant=NULL;
 }
 else if(e < L->valeur) /* ajouter DEVANT la tete */
      {
       Cellule *p=(Cellule *)malloc(sizeof(Cellule));
       p->valeur=e; p->suivant=L;
       L=p; /* nouvelle tete de liste */
      }
      else L->suivant=ajouter_rec(e,L->suivant); /* ajouter DERRIERE la tete */
 return L;
}


Liste supprimer_iter(element e, Liste L)
{
 Liste prec = NULL;
 while(L) 
 {
  if(e == L->valeur) {   
   prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */
   free(L); /* liberation memoire pour L */
   return prec;
  }
  prec = L;
  L = L->suivant;
 }
 return L;
}


Liste supprimer_rec(element e, Liste L)
{
 if(!L) ; /* element absent - on ne fait rien */
 else if(L->valeur==e) 
      {
       Cellule *p=L; 
       L=L->suivant;
       free(p);
      }		
      else L->suivant=supprimer_rec(e,L->suivant);
 return L;
}


Liste inverser_iter(Liste L)
{
 Liste cell=NULL; /* une cellule temporaire */
 Liste inv=NULL; /* la liste inversee */
 
 while(L!=NULL)
 {
  cell=L; /* on prend la premiere cellule de la liste */
  L=L->suivant; /* le debut de la liste devient l'element suivant */
  cell->suivant=inv; /* on libere l'element de la liste  et on le place en debut de la liste a renvoyer*/
  inv=cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */
 }
 return inv;
}



Liste inserer_fin(element e, Liste L)
{
 Cellule *pc, *p1=L, *p2=NULL;
 pc = (Cellule *)malloc(sizeof(Cellule)); 
 pc->valeur=e;pc->suivant=NULL;
 if (!L) return pc;
 while (p1)
 {
  p2 = p1; 
  p1 = p1->suivant;
 }
 p2->suivant = pc; 
 pc->suivant = p1; 
 return L;
}


Liste inverser_rec(Liste L)
{
 if(L != NULL) {
  return inserer_fin(L->valeur, inverser_rec(L->suivant));
 }
 else return L;
}


/****************************************************************************/ 

int main()
{
 Liste L=NULL;
 printf("liste vide\n");
 visualiser_iter(L);
 visualiser_rec(L);

 printf("longueur=%d\n",longueur_iter(L));
 printf("longueur=%d\n",longueur_rec(L));

 printf("ajout de 3\n");
 L=ajouter_iter(3,L);
 printf("ajout de 6\n");
 L=ajouter_iter(6,L);
 printf("ajout de 1\n");
 L=ajouter_iter(1,L);
 printf("ajout de 10\n");
 L=ajouter_iter(10,L);
 printf("ajout de 6\n");
 L=ajouter_iter(6,L);
 visualiser_iter(L);
 visualiser_rec(L);

 printf("longueur=%d\n",longueur_iter(L));
 printf("longueur=%d\n",longueur_rec(L));

 printf("recherche de %d = %d\n",3,rechercher_iter(3,L));
 printf("recherche de %d = %d\n",3,rechercher_rec(3,L));
 printf("recherche de %d = %d\n",4,rechercher_iter(4,L));
 printf("recherche de %d = %d\n",4,rechercher_rec(4,L));

 printf("ajout (rec) de 4\n");
 L=ajouter_rec(4,L);
 visualiser_iter(L);
 printf("ajout (rec) de 8\n");
 L=ajouter_rec(8,L);
 visualiser_iter(L);

 printf("suppression (iter) de 4\n");
 supprimer_iter(4,L);
 visualiser_iter(L);
 printf("suppression (rec) de 6\n");
 supprimer_rec(6,L);
 visualiser_iter(L);

 printf("liste inversee (iter)\n");
 Liste inv = inverser_iter(L);
 visualiser_iter(inv);

 printf("Liste inversee (rec)\n");
 Liste inv2 = inverser_rec(inv);
 visualiser_iter(inv2);

 /* 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, ... */
}


/****************************************************************************/ 

/* trace d'execution :
liste vide


longueur=0
longueur=0
ajout de 3
ajout de 6
ajout de 1
ajout de 10
ajout de 6
1 3 6 6 10 
1 3 6 6 10 
longueur=5
longueur=5
recherche de 3 = 1
recherche de 3 = 1
recherche de 4 = 0
recherche de 4 = 0
ajout (rec) de 4
1 3 4 6 6 10 
ajout (rec) de 8
1 3 4 6 6 8 10 
suppression (iter) de 4
1 3 6 6 8 10 
suppression (rec) de 6
1 3 6 8 10 
liste inversee (iter)
10 8 6 3 1 
Liste inversee (rec)
1 3 6 8 10 
*/