program list_s_c; (* liste simplement chaînée *)

uses crt;

type TDonnee=integer;

type PCellule = ^Cellule;
     Cellule = record
                 nb:TDonnee;
                 next:Pcellule;
               end;

function init_liste:PCellule;
(* initialise une liste *)
begin
  init_liste:=nil;
end;

function est_vide(l:Pcellule):boolean;
(* retourne true si la liste est vide *)
begin
  est_vide:= (l=nil);
end;

function suivant(l:Pcellule):Pcellule;
(* retourne l'adresse de la cellule suivante *)
begin
  suivant:=l^.next;
end;

function contenu(l:Pcellule):TDonnee;
(* retourne le contenu d'une cellule pointée par l *)
begin
  contenu:=l^.nb;
end;

(* bon... ça devient, sérieux, va falloir commenter un peu plus!! *)

function insere(l:Pcellule;n:TDonnee):PCellule;
(* permet d'insérer une cellule contenant une donnée n devant la cellule sur
laquelle pointe l ; Est retourné le pointeur de la nouvelle liste *)
var temp:PCellule;
begin
  new(temp);   (* on crée une nouvelle variable dynamique *)
  temp^.nb:=n; (* on lui affecte son contenu *)
  temp^.next:=l; (* on la fait pointer sur la 1ère cellule qui devient la 2ème *)
  insere:=temp;  (* cette cellule devient ainsi la 1ère (c'est son pointeur que
                  l'on retourne comme tête de liste) *)
end;

function supprime(l:Pcellule):Pcellule;
(* permet de supprimer la cellule pointée par l ; Est retourné le pointeur de
la nouvelle liste *)
var temp:Pcellule;
begin
  temp:=l^.next;  (* on garde D'ABORD trace de la cellule suivante (elle va
                   perdue à la destruction de l^ !) *)
  dispose(l);     (* on détruit la variable pointée par l *)
  supprime:=temp; (* la cellule suivant l (et préalablement stockée dans temp)
                  devient la nouvelle tête de liste *)
end;

(* c'est maintenant que l'on saute à pied joints dans le récursif !!
accrochez vous à vos synapses, les neuronnes vont chauffer ! *)

function supprime_elem(l:PCellule;elem:TDonnee):PCellule;
(* fonction qui parcours la liste ; si elle trouve une cellule contenant la
donnée elem, elle la supprime ; elle retourne un pointeur pointant sur la
première cellule de la nouvelle liste *)
begin
if est_vide(l)       (* liste vide? *)
  then supprime_elem:=l    (* on change rien ! *)
  else if contenu(l)=elem  (* SINON *) (* si la première cellule est la bonne *)
     (* (remarque : /\ attention au test valable seulement pour type scalaire) *)
        then supprime_elem:=supprime(l) (* alors on supprime la cellule *)
         else begin               (* sinon *)
              l^.next:=supprime_elem(suivant(l),elem); (* on recommence mais en
                                           partant de la cellule suivante ...
                           notez que c'est là qu'intervient la récursivité !
                           on fait pointer la cellule courante sur la cellule
                           qui fera partie de la liste traitée (dont le
                           pointeur est retourné par supprim_elem !) ; en
                           gros, on recolle les bouts! *)
              supprime_elem:=l;    (* et on retourne la liste traitée *)
              end;
end;

function insere_sort(l:PCellule;elem:TDonnee):PCellule;
(* insère une cellule contenant elem à la bonne place et retourne le pointeur
pointant sur le début de la nouvelle liste *)
begin
  if est_vide(l)    (* si la liste est vide (on si on est auu bout de la liste) *)
    then insere_sort:=insere(l,elem)  (* on crée une liste contenant l'élément *)
    else if elem<=contenu(l)  (* sinon si l'élément est plus petit que le
                                        contenu de la cellule courante *)
    (* REM : RELATION D'ORDRE A DEFINIR SELON LE TYPE DE TDonnee !!! *)
           then insere_sort:=insere(l,elem) (* on insère une cellule contenant
                                             l'élément et on retourne son
                                             pointeur *)
           else begin                       (* SINON *)
                l^.next:=insere_sort(suivant(l),elem); (* même remarque que
                                                pour la fonction précédente !
                                        C'est là qu'intervient la récursivité
                                On fait pointer la cellule courante sur la
                                cellule qui fera partie de la liste traitée *)
                insere_sort:=l; (* on retourne la liste traîtée *)
                end;
end;

procedure affiche(l:Pcellule);
(* procédure affichant le contenu de toutes les cellules depuis celle pointée
par l jusqu'à la fin de la liste *)
begin
if not(est_vide(l))         (* si la liste n'est pas vide (équivalent à savoir
                                si on a atteint la fin qui est NIL selon la
                                convention adoptée *)
then begin
     writeln(contenu(l));   (* on affiche le contenu de la cellule courante *)
     affiche(suivant(l));(* on ré-appelle la procédure pour la cellule suivante *)
     end;
end;

(* ce qui suit est un démonstration de l'utilisation
des procédures précédentes *)

var l:pcellule;

BEGIN
clrscr;
l:=init_liste;  (* très important car sinon le dernier élément
                ne pointe pas sur NIL ! *)
l:=insere(l,5);
l:=insere(l,4);
l:=insere(l,3);
affiche(l);
l:=supprime_elem(l,4);
writeln;
affiche(l);
l:=insere_sort(l,9);
writeln;
affiche(l);
END.