#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, 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);
       }
}

/*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;
}

struct maillon
Le type structure défini ici, struct maillon, comporte deux champs :

Ce type de structure est destiné à construire ce qu'on appelle une liste chaînée ; ici, le type struct maillon est destiné à chaîner des "int". A chaque "int" est associé, dans le struct maillon qui le contient, l'adresse de l' "int" suivant dans la liste.
Pour pouvoir accéder à l'ensemble des valeurs contenues dans la liste, il est nécessaire de connaître l'adresse du premier "struct maillon". On peut alors, de proche en proche, retrouver tous les éléments de la liste en utilisant les adresses successives.

typedef struct maillon * VersMaillon;
Dans notre programme, beaucoup de variables sont des adresses vers des variables de type "struct maillon", c'est-à-dire des "struct maillon *". Pour alléger l'écriture, on utilise l'instruction typedef pour de renommer le type "struct Maillon *" en le type "VersMaillon".

VersMaillon debut, p;
On déclare deux variables de type VersMaillon ; cette déclaration est équivalente à :

struct maillon * debut, * p ;

(VersMaillon ) malloc(sizeof(struct maillon));
On alloue ici l'espace mémoire pour un objet de type struct maillon ; l'adresse de cet objet est mise dans la variable nouveau. Une allocation d'un struct maillon est faite pendant l'exécution du programme pour chaque donnée à insérer.

(q!=NULL) && (donnee > q->valeur))
Nous utilisons ici le fait que, lorsqu'une expression du type

expr1 && expr2
est évaluée, si expr1 est fausse, alors expr2 n'est pas calculée.
Ainsi, si q vaut NULL, on n'essaiera pas de lire en mémoire q->valeur qui intervient dans :
donnee > q->valeur.
Tenter d'accéder à q->valeur alors que vaut NULL conduirait à une erreur.