#include <stdlib.h>
#include <stdio.h>
#define N 50

struct liste_lineaire
    {
     int el;
     struct liste_lineaire *suiv;
    };
typedef  liste_lineaire * liste;

void InsererDebut(int v, liste *l)
{
 liste p;
 p=(liste)malloc(sizeof(liste_lineaire));
 p->el=v;
 p->suiv=*l;
 *l=p;
}

void InsererFin(int v, liste *l)
{
 liste p,q,pq;
 p=(liste)malloc(sizeof(liste_lineaire));
 p->el=v;
 p->suiv=NULL;
 q=*l;
 pq=NULL;
 while(q!=NULL)
 {
  pq=q;
  q=q->suiv;
 }
 if(pq==NULL)
 {
  *l=p;
 }
 else
 {
  pq->suiv=p;
 }
}
void SupprimerFin(int *v, liste *l)
{
 liste ppq,q,pq;
 q=*l;
 ppq=NULL;
 pq=NULL;
 while(q!=NULL)
 {
  ppq=pq;
  pq=q;
  q=q->suiv;
 }
 if(pq!=NULL)
 {
  if(ppq==NULL) {*l=NULL;}
  else {ppq->suiv=NULL;}
  *v=pq->el;
  free(pq);
 }
}

void SupprimerDebut(int *v, liste *l)
{
 liste p;
 p=*l;
 if (p!=NULL)
 {
  *v=p->el;
  *l=p->suiv;
  free(p);
 }
}
void tab2list(int tab[N],liste *l)
{
 int i;
 l=NULL;
 for (i=0;i<N;i++) InsererFin(tab[i],l);
}

void list2tab(liste *l, int *tab[N])
{
 liste p;
 int i=0;
 p=*l;
 while (i<N && p!=NULL)
 {
  SupprimerDebut(tab[i],l);
  i++;
 }
}

void RechSuppMin(int *x,liste *l)
{
 liste p,pp,min,pmin;
 p=*l;
 min=*l;
 pp=NULL; pmin=NULL;
 while(p!=NULL)
 {
  if(p->el<min->el)
  {
   min=p;
   pmin=pp;
  }
  pp=p;
  p=p->suiv;
 }
 *x=min->el;
 if(pmin==NULL)
 {
  *l=min->suiv;
 }
 else
 {
  pmin->suiv=min->suiv;
 }
 free(min);
}

void Tri(liste *l)
{
 liste nt;
 int x;
 nt=NULL;
 while(*l!=NULL)
 {
  RechSuppMin(&x,l);
  InsererFin(x,&nt);
 };
 *l=nt;
}
void Fusion(liste *l1,liste *l2,liste *l)
{
 liste p1,p2;
 int x;
 *l=NULL;
 while(*l1!=NULL && *l2!=NULL)
 {
  p1=*l1; p2=*l2;
  if(p1->el<p2->el)
  {SupprimerDebut(&x,l1);}
  else
  {SupprimerDebut(&x,l2);}
  InsererFin(x,l);
 }
 while(*l1!=NULL)
 {
  SupprimerDebut(&x,l1);
  InsererFin(x,l);
 }
 while(*l2!=NULL)
 {
  SupprimerDebut(&x,l2);
  InsererFin(x,l);
 }
}

void Inserer(int v,liste *l)
{
 liste p,pp,q;
 q=(liste)malloc(sizeof(liste_lineaire));
 q->el=v;
 p=*l;
 pp=NULL;
 while(p!=NULL && p->el<v)
 {
  pp=p;
  p=p->suiv;
 };
 q->suiv=p;
 if(pp==NULL)
 {*l=q;}
 else
 {pp->suiv=q;}
}

void Supprimer(int v,liste *l)
{
 liste p,pp,q;
 p=*l;
 pp=NULL;
 while(p!=NULL && p->el<v)
 {
  pp=p;
  p=p->suiv;
 };
 if(p!=NULL && p->el==v)
 {
  if(p==*l)
  {
   *l=p->suiv;
  }
  else
  {
   pp->suiv=p->suiv;
  }
   free(p);
 }
}

void  Afficher(liste l)
{
 if (l==NULL){printf("\n La liste est vide \n");}
 else
 {
  while(l!=NULL)
  {
   printf("%d ",l->el);
   l=l->suiv;
  }
 }
printf("\n");
}
int main(int argc, char* argv[])
{
     liste l1,l2,l3;
     int i,x;
     l1=NULL;
     l2=NULL;
     l3=NULL;
     randomize();
     printf("\n ================================");
     printf("\n Création\n");
     printf("================================\n");
     for(i=0;i<N;i++)
     {
      InsererDebut(random(1000),&l1);
     }
     for(i=0;i<N;i++)
     {
      InsererFin(random(1000),&l2);
     }

     printf("\n Première liste:");
     Afficher(l1);
     printf("\n Deuxième liste:");
     Afficher(l2);
     printf("\n ================================");
     printf("\n Tri des deux listes\n");
     printf("================================\n");

     Tri(&l1);
     Tri(&l2);

     printf("\Première liste triée:");
     Afficher(l1);
     printf("Deuxième liste triée:");
     Afficher(l2);

     printf("\n ================================");
     printf("\n Supprimer début et supprimer fin \n");
     printf("================================\n");

     SupprimerDebut(&x,&l1);
     SupprimerFin(&x,&l2);

     printf("Première liste:\n");
     Afficher(l1);
     printf("Deuxième liste:\n");
     Afficher(l2);

     printf("\n ================================");
     printf("\n Fusion \n");
     printf("================================\n");

     Fusion(&l1,&l2,&l3);

     printf("Troisième liste:\n");
     Afficher(l3);

     printf("\n ================================");
     printf("\n Insertion dans la liste triée \n");
     printf("================================\n");

     Inserer(50,&l3);

     printf("Liste: \n");
     Afficher(l3);

     printf("\n ================================");
     printf("\n Suppression de la liste triée \n");
     printf("================================\n");

     Supprimer(50,&l3);

     printf("\n Liste: \n");
     Afficher(l3);


    scanf("%d",&x);

        return 0;
}
//---------------------------------------------------------------------------