/* Classe n entiers donnes par l'utilisateur                  */
/* Exemple de programme avec liste chainee double et triee    */
/* L'algorithme de tri est ici primaire...                    */

#include <stdio.h>

main()
{
   int i,idum,n;
   
   typedef struct classer
   {
      int valeur;
      struct classer *apres;
      struct classer *avant;
   } liste ;
   
   liste * pdebut;                          /* pointeur vers debut de liste */
   liste * pnouveau;                        /* pointeur vers nouvel element */
   liste * pfin;                            /* pointeur vers fin de liste   */
   liste * pdum;                            /* pointeur de controle         */

   printf("Combien d'entiers voulez-vous saisir ?\n");
   scanf("%d",&n);

/**************** Allocation memoire pour premier element *******************/
   pdebut = (liste *) malloc(sizeof(liste));
   pnouveau = pfin = pdebut;
   (*pdebut).apres = NULL;     /* On peut aussi ecrire pdebut->apres = NULL */
   pdebut->avant = pdebut->apres=NULL ;
   pdebut->valeur = 0;

/* Saisie des donnees */
for(idum=1;idum<=n;idum++)  
 { 
   printf("Rentrer un entier\n");
   scanf("%d",&i);
   (*pnouveau).valeur = i;    
   pnouveau->apres=pnouveau;      
   printf("Vous avez rentre %d\n",pnouveau->apres->valeur);

   /* insertion nouvel element */
   if (pnouveau->valeur < pdebut->valeur)
      {
         pdebut->avant   = pnouveau;
	 pnouveau->apres = pdebut;
	 pnouveau->avant = NULL;
	 pdebut          = pnouveau ;
      } 
   else if (pnouveau->valeur > pfin->valeur)  
      {
         pfin->apres     = pnouveau;
	 pnouveau->avant = pfin;
	 pnouveau->apres = NULL;
	 pfin            = pnouveau ;
      }    
   else 
      {
         for(pdum=pdebut; pdum->apres->valeur < pnouveau->valeur;pdum=pdum->apres)
	    ;
	    pnouveau->apres    = pdum->apres;
	    pnouveau->avant    = pdum ;
	    pdum->apres        = pnouveau ;
	    pdum->apres->avant = pnouveau ;
      }
      
   /****** Allocation memoire pour nouvel element  ******/
   pnouveau = (liste *) malloc(sizeof(liste));
   

 }     /*fin de boucle for sur idum*/
 
   printf("\nListe Classee\n"); 
   i=1;
   for (pdum=pdebut;pdum!=NULL;pdum=pdum->apres,i++)
      {
          printf("  Element %d : %d\n",i,pdum->valeur); 
      }
 
}