%cf c:\nant\binome.pas
\magnification\magstep1
\ifx\TD\exo\input TDexo \else \let\findoc=\relax \fi
\def\para#1){\bigbreak{\bf#1)} }
\para1)
Dans un programme contenant les déclarations :
{\verbatim
type pftd=^ftd;
     ftd=record
           nom,prenom:string[30];
           notes:array[1..5] of integer;
           my:integer;
           binome,suivant:pftd
         end;
var l:pftd;
}
on veut s'allouer dans le tas la place pour quatre fiches de T.D.,
mettre à jour les champs {\tt nom}, {\tt binome} et {\tt suivant} de
chacune de ces quatre fiches et mettre dans {\tt l} un pointeur sur
la première pour obtenir :
%\let\special=\relax
\def\p#1,{\quad\special{em:point #1}\quad}
\def\n#1,{\quad\hbox to 0pt{\hss\tt nil\hss}\quad}
\def\ftd#1#2#3 #4 {{\offinterlineskip\tabskip=0pt
\edef\nom{#2}
$\vcenter{
\halign{&##\vrule height0pt depth5pt\cr
\special{em:point #1}&\hbox to 50pt{\hss\tt'\nom'\hss}&#3,&#4,\cr
\noalign{\hrule}}}$}}

{\tt l}
{\offinterlineskip\tabskip=0pt
\vtop{\halign{&#\vrule height0pt depth5pt\cr
&\p10,\cr
\noalign{\hrule}}}}
\hskip1cm \ftd1{ANDRE}\p11 \p12 \par\kern1cm
          \ftd2{BRUNO}\n21 \p22
\hskip5cm \ftd4{DENIS}\n41 \n42 \par\kern1cm
\hskip5cm \ftd3{CELINE}\p31 \p32 \par
\special{em:line 10,1}
\special{em:line 12,2}
\special{em:line 22,3}
\special{em:line 32,4}
\special{em:line 11,3}
\special{em:line 31,1}
André et Céline forment un binôme alors que Bruno et Denis sont
individualistes.
On peut réaliser cela par les instructions suivantes :
{\verbatim
new(l);
new(l^.suivant);
new(l^.suivant^.suivant);
l^.nom:='ANDRE';
l^.binome:=l^.suivant^.suivant;
l^.suivant^.binome:=nil;
}
Compléter ces instructions. (Il manque un {\tt new} et six
affectations)

\para2)
On peut aussi procéder en utilisant des variables de type pointeur,
ce qui rend le programme plus lisible :
{\verbatim
var andre,bruno,celine,denis:pftd;
begin
  new(andre);
  new(bruno);
  new(celine);
  new(denis);
  l:=andre;
  andre^.nom:='ANDRE';
  andre^.binome:=celine;
  andre^.suivant:=bruno;
}
Compléter ces instructions. (Il manque neuf affectations)

\para3)
On utilise la procédure récursive suivante pour afficher la liste des
noms.
{\verbatim
procedure affnom(a:pftd);
begin
  if a<>nil then
  begin
    writeln(a^.nom);
    affnom(a^.suivant)
  end
end;
}
Qu'apparaît-il sur l'écran quand on appelle la procédure par
{\tt affnom(l)} ?
Ecrire une version non récursive de {\tt affnom}.
Que se passe-t-il si on intervertit les deux instructions
{\tt writeln(a\^{}.nom)} et
{\tt affnom(a\^{}.suivant)} ?
Peut-on alors écrire facilement une version non récursive de cette
procédure ?

\para4) Compléter la fonction
\par\noindent\tt
function nbfiches(a:pftd):integer;
\par\noindent\rm
qui donne le nombre de fiches dans la liste {\tt a}.
Par exemple {\tt nbfiches(l)=4} tandis que
{\tt nbfiches(l\^{}.suivant)=3}.
Donner une version récursive et une version non récursive de cette
fonction.

\para5) Compléter la fonction
\par\noindent\tt
function nbbinomes(a:pftd):integer;
\par\noindent\rm
qui donne le nombre de binômes dans la liste {\tt a}.
Par exemple {\tt nbbinomes(l)=1}.
On pourra compter les étudiants qui sont dans un binôme, puis
diviser ce nombre par deux.

\para6) Compléter la procédure
\par\noindent\tt
procedure affbinomes(a:pftd);
\par\noindent\rm
qui affiche les binômes existants.
Par exemple {\tt affbinomes(l)} doit afficher un des deux couples
{\tt ANDRE+CELINE} ou
{\tt CELINE+ANDRE} mais pas les deux.

\para7) Compléter la fonction
\par\noindent\tt
function copie(a:pftd):pftd;
\par\noindent\rm
qui fait une copie de la liste de fiches de TD {\tt a}.
Cette copie doit être constituée de nouvelles fiches de TD (obtenues
par {\tt new}).
Dans la copie tous les champs {\tt binome} seront mis à {\tt nil},
c'est à dire que les binômes seront séparés.
Il est plus simple d'écrire cette fonction récursivement.

\para8) Ecrire maintenant la fonction {\tt copie} itérativement et
en lui faisant mettre à jour les champs {\tt binome} de manière à
conserver le même appariement en binômes que dans la liste originale.
Il faut noter que les champs {\tt binome} de la copie
doivent pointer dans la copie et non dans l'original.
On pourra écrire une fonction qui parcourra la liste originale trois
fois.
Lors du premier parcours, on insèrera une nouvelle fiche de TD
derrière chacune des fiches de liste originale.
Lors du deuxième parcours, on mettra à jour les champs {\tt binome}
des nouvelles fiches.
Enfin
lors du troisième et dernier parcours, on séparera les deux listes.
De cette manière la fonction {\tt copie} aura un temps de calcul
proportionnel à la longueur de la liste à copier.
\corrige
\para1)
{\verbatim
new(l);
new(l^.suivant);
new(l^.suivant^.suivant);
l^.nom:='ANDRE';
l^.binome:=l^.suivant^.suivant;
l^.suivant^.binome:=nil;
l^.suivant^.nom:='BRUNO';
new(l^.suivant^.suivant^.suivant);
l^.suivant^.suivant^.nom:='CELINE';
l^.suivant^.suivant^.binome:=l;
l^.suivant^.suivant^.suivant^.nom:='DENIS';
l^.suivant^.suivant^.suivant^.binome:=nil;
l^.suivant^.suivant^.suivant^.suivant:=nil;
}
\para2)
{\verbatim
var andre,bruno,celine,denis:pftd;
begin
  new(andre);
  new(bruno);
  new(celine);
  new(denis);
  l:=andre;
  andre^.nom:='ANDRE';
  andre^.binome:=celine;
  andre^.suivant:=bruno;
  bruno^.nom:='BRUNO';
  bruno^.binome:=nil;
  bruno^.suivant:=celine;
  celine^.nom:='CELINE';
  celine^.binome:=andre;
  celine^.suivant:=denis;
  denis^.nom:='DENIS';
  denis^.binome:=nil;
  denis^.suivant:=nil;
}
\para3)
{\verbatim
procedure affnom(a:pftd);
begin
  if a<>nil then
  begin
    writeln(a^.nom);
    affnom(a^.suivant)
  end
end;
}
{\tt affnom(l)} fait apparaître sur l'écran :
{\verbatim
ANDRE
BRUNO
CELINE
DENIS
}
Voici une version non récursive de {\tt affnom}.
{\verbatim
procedure affnom(a:pftd);
begin
  while a<>nil do
  begin
    writeln(a^.nom);
    a:=a^.suivant
  end
end;
}
Si on intervertit les deux instructions
{\tt writeln(a\^{}.nom)} et
{\tt affnom(a\^{}.suivant)} alors
{\tt affnom(l)} fait apparaître sur l'écran :
{\verbatim
DENIS
CELINE
BRUNO
ANDRE
}
Il est beaucoup plus difficile d'écrire
une version non récursive de cette
procédure.

\para4)
{\verbatim
function nbfiches(a:pftd):integer;
begin
  if a=nil then nbfiches:=0
           else nbfiches:=1+nbfiches(a^.suivant)
end;
}
{\verbatim
function nbfiches(a:pftd):integer;
var n:integer;
begin
  n:=0;
  while a<>nil do
  begin
    n:=n+1;
    a:=a^.suivant
  end;
  nbfiches:=n
end;
}
\para5)
{\verbatim
function nbbinomes(a:pftd):integer;
var n:integer;
begin
  n:=0;
  while a<>nil do
  begin
    if a^.binome<>nil then n:=n+1;
    a:=a^.suivant
  end;
  nbbinomes:=n div 2
end;
}
\para6)
{\verbatim
procedure affbinomes(a:pftd);
begin
  while a<>nil do
  begin
    if a^.binome<>nil then
    if a^.binome^.nom>a^.nom then
    writeln(a^.nom,'+',a^.binome^.nom);
    a:=a^.suivant
  end
end;
}
La version précédente affiche tous les binômes une fois,
les deux noms étant affichés dans l'ordre alphabétique,
sauf dans le cas où les deux membres du binôme ont le même nom
auquel cas le binôme est affiché deux fois.
La procédure suivante remédie à ce défaut.
Elle modifie temporairement la liste chaînée.
{\verbatim
procedure affbinomes(a:pftd);
begin
  while a<>nil do
  with a^ do
  begin
    if binome<>nil then
    if binome^.binome=nil then binome^.binome:=a else
    begin
      writeln(nom,'+',binome^.nom);
      binome:=nil
    end;
    a:=a^.suivant
  end
end;
}
\para7)
{\verbatim
function copie(a:pftd):pftd;
var b:pftd;
begin
  if a=nil then copie:=nil else
  begin
    new(b);
    b^:=a^;
    b^.binome:=nil;
    b^.suivant:=copie(a^.suivant);
    copie:=b
  end
end;
}
\para8)
{\verbatim
function copie2(a:pftd):pftd;
var x,y:pftd;
begin
  if a=nil then copie2:=nil else
  begin
    x:=a;
    repeat
      new(y);
      y^:=x^;
      x^.suivant:=y;
      x:=y^.suivant
    until x=nil;
    x:=a;
    repeat
      y:=x^.suivant;
      if y^.binome<>nil then
      y^.binome:=y^.binome^.suivant;
      x:=y^.suivant
    until x=nil;
    copie2:=a^.suivant;
    x:=a;
    repeat
      y:=x^.suivant;
      x^.suivant:=y^.suivant;
      x:=x^.suivant;
      if x<>nil then y^.suivant:=x^.suivant
    until x=nil
  end
end;
}
\findoc
