/*tri baquets*/
#include <stdio.h>
#include <stdlib.h>

typedef struct maillon
{
  int entier;
  struct maillon *suivant;
} Maillon;

typedef Maillon *VersMaillon;

VersMaillon L = NULL;
int k;     /* contiendra le nombre maximum de chiffres des données à trier*/

struct
{
  VersMaillon deb, fin;
} baquet[10];

FILE *lecture,*ecriture;

void entrerDonnees(void);
void trier(void);
void afficher(void);
void initialiserBaquets(void);
void ranger(void);
void reconstruire(void);

int main(void)
{
  entrerDonnees();
  trier();
  afficher();
  return 0;
}

void entrerDonnees()
{
  int n;
  VersMaillon p;
  
  lecture = fopen("donnees.dat","r");
  if (lecture == NULL)
    {
      printf("fichier introuvable\n");
      exit(1);
    }
  fscanf(lecture, "%d", &k);
  while (fscanf(lecture,"%d",&n)!=EOF)
    {
      p=(VersMaillon)malloc(sizeof(Maillon));
      p->entier=n;
      p->suivant=L;
      L=p;
    }
  fclose(lecture);
}

void trier()
{
  int i;
  
  for (i = 1;i <= k; i++)
    {
      initialiserBaquets();
      ranger();
      reconstruire();
    }
}

void initialiserBaquets()
{
  int j;
  
  for (j = 0; j < 10; j++) baquet[j].deb=baquet[j].fin = NULL;
}

void ranger()
{
  int n, num;
  VersMaillon m;
  static int puiss = 1;  /*au ieme appel de ranger, c doit valoir
		       10 puissane (i - 1) */
  
  while (L != NULL)
    {
      m = L;
      L = L->suivant;
      m -> suivant = NULL;
      n = m->entier;
      num = ( n% (10 * puiss))/puiss;
      if (baquet[num].deb == NULL)
	{
	  baquet[num].deb = m;
	  baquet[num].fin = m;
	}
      else
	{
	  baquet[num].fin->suivant = m;
	  baquet[num].fin = m;
	}
    }
  puiss *= 10;
}

void reconstruire()
{
  int dernier, j = 0;
  
  while (j < 10 && baquet[j].deb == NULL) j++;
  if (j == 10) return;  /*la liste était vide*/
  L = baquet[j].deb;
  dernier =  j;
  while (++j < 10)
    if (baquet[j].deb != NULL)
      {
	baquet[dernier].fin -> suivant = baquet[j].deb;
	dernier = j;
      }
}

void afficher(void)
{
  ecriture = fopen("resultats.dat","w");
  printf("Vous trouverez le resultat dans le fichier "
				"resultats.dat\n");
  while (L!=NULL)
    {
      fprintf(ecriture,"%d ", L->entier);
      L=L->suivant;
    }
  fclose(ecriture);
}