#include <stdio.h>
#include <stdlib.h>

struct maillon
{
  int valeur;
  struct maillon * suivant;
};
typedef struct maillon * VersMaillon;

VersMaillon inserer(int, VersMaillon);

void main()
{
  VersMaillon debut, p;
  int donnee, nb_donnee=0;
  
  debut=NULL;
  printf("Donnez vos données positives, tapez -1 pour terminer : \n"); 
  
  /*On saisit les données*/
  scanf("%d",&donnee);
  while (donnee!=-1)
    {
      nb_donnee++;
      debut=inserer(donnee,debut);
      scanf("%d",&donnee);
    }
  
  /*On affiche les donnéee triées et on libère la mémoire allouée*/
  while (debut!=NULL)
    {
      printf("%d ",debut->valeur);
      p=debut;
      debut=debut->suivant;
      free(p);
    }
  printf("\n");
}

/*Fonction qui insère une donnée selon l'ordre croissant*/
VersMaillon inserer(int donnee, VersMaillon deb)
{
  VersMaillon nouveau, p, q;
  
  nouveau=(VersMaillon)malloc(sizeof(struct maillon));
  nouveau->valeur=donnee;
  if (deb==NULL)
    {
      nouveau->suivant=NULL;
      deb=nouveau;
    }
  else if (donnee<= deb->valeur)
    {
      nouveau->suivant=deb;
      deb=nouveau;
    }
  else
    {
      p=deb;
      q=deb->suivant;
      while((q!=NULL) && (donnee>q->valeur))
	{
	  p=q;
	  q=q->suivant;
	}
      p->suivant=nouveau;
      nouveau->suivant=q;
    }
  return deb;
}