\documentclass[a4paper]{article}
\usepackage{multicol,french}
  \topmargin -.54cm
  \headheight 0pt
  \headsep 0pt
  \textheight 25cm
  \advance\textheight by -\topskip
  \oddsidemargin  -.54cm
  \evensidemargin -.54cm
  \textwidth 17cm

\begin{document}

\begin{center}
\Huge Douzième TP
\bigskip
\end{center}

\begin{multicols}{2}[
\section*{Pointeurs}
]
\subsection*{Description}
Le contenu d'une variable est stocké à
un certain endroit de la mémoire.
On parle alors d'{\em adresse} de la variable
pour indiquer cet endroit.

Il existe un type de données, les {\em pointeurs},
qui permet de manipuler ces adresses.

$\bullet$
Lorsqu'un pointeur indique l'adresse où se trouve
la valeur d'une variable,
on dit que ce pointeur {\em pointe} sur la variable, et inversement,
que cette variable est {\em référencée} par le pointeur.
Récupérer la valeur qui est à l'endroit de la mémoire
indiqué par le pointeur s'appelle {\em déréférencer} le pointeur.

$\bullet$
Le type Pascal {\tt POINTER} permet de stocker tout pointeur.
On parle de {\em pointeur générique}.
Il est conseillé d'utiliser des pointeurs typés, qui précisent
le type d'objet vers lequel ils pointent.
Si une variable est de type {\tt TYPEVAR},
un pointeur vers cette variable est de type \verb|^TYPEVAR|.

$\bullet$
La valeur constante {\tt NIL} est un pointeur qui ne pointe sur rien.
Cette valeur est utile pour préciser qu'un pointeur ne doit pas
être déréférencé.

\subsection*{Syntaxe}
Un pointeur vers la variable \verb|I| est construit par
l'expression \verb|@I|.
On déréférence un pointeur \verb|P| en écrivant \verb|P^|.

Considérons en exemple le programme suivant, qui affiche \verb|2|~:
\bgroup\small
\begin{verbatim}
VAR P : ^INTEGER;
    I : INTEGER;
BEGIN
  I := 2;  { P est un pointeur vers l'endroit de }
  P := @I; { la mémoire où est la valeur de I.   }
  WriteLn('Contenu de I = ',P^);
END.
\end{verbatim}
\egroup

$\bullet$
Quand on met le {\tt \verb+^+} \`a gauche, ce qui est \`a droite
doit \^etre un type, et le tout est un pointeur sur le type indiqu\'e.

$\bullet$
Quand on met le {\tt \verb+^+} \`a droite, ce qui est \`a gauche
doit \^etre un pointeur typ\'e, et le tout est une valeur typ\'ee
qui est le contenu de ce qui est stock\'e \`a l'adresse
indiqu\'ee par le pointeur.
C'est un {\em d\'er\'ef\'erencement}.

$\bullet$
Quand on met un {\tt @} \`a gauche, ce qui est \`a droite doit
\^etre une variable, et le tout est le pointeur de la variable.
C'est un {\em r\'ef\'erencement}.

\section*{R\'eservation et Lib\'eration}

On a parfois besoin de manipuler des objets
de mani\`ere seulement temporaire~: on aimerait
utiliser de la place m\'emoire \`a un moment donn\'e,
puis pouvoir utiliser cette m\^eme place \`a d'autres fins.
C'est l'une des applications des pointeurs.


Lorsqu'on d\'eclare une variable, cette d\'eclaration est faite
une fois pour toutes~: la place utilis\'ee pour stocker la variable
est perdue jusqu'\`a ce que le programme s'ach\`eve.
Mais lorsqu'on manipule des pointeurs, on peut {\em lib\'erer}
la place occup\'ee par ce qui est point\'e.

$\bullet$ La proc\'edure {\tt New} r\'eserve (on dit aussi,
{\em alloue}) de la m\'emoire pour le pointeur donn\'e en argument.
Il faut que le pointeur soit typ\'e.

$\bullet$ La proc\'edure {\tt Dispose} lib\`ere (on dit aussi,
{\em d\'esalloue}) la m\'emoire point\'ee par le pointeur donn\'e
en argument.

\section*{Exemple}

\bgroup\small
\begin{verbatim}
VAR P:^INTEGER;
BEGIN
  New(P);      { On reserve }
  P^ := 12;    { On donne une valeur }
  WriteLn(P^); { On affiche le contenu } 
  Dispose(P);  { On libere }
  WriteLn(P^); { C'est interdit ! }
END.
\end{verbatim}
\egroup
\end{multicols}

\newpage

\begin{center}
\begin{picture}(471,60)(0,0)
\special{psfile=liste.eps vscale=100 hscale=100}
\end{picture}
\end{center}

\begin{multicols}{2}[
\section*{Liste chaînée}
]
\subsection*{Définition}
On appelle {\em liste chaînée } une liste
de longueur quelconque formée d'objets de même type. 
Par exemple, pour d\'efinir le type liste chaînée
d'entiers, on écrit en Pascal~:
\begin{verbatim}
TYPE Liste   = ^Contenu;
     Contenu = RECORD
                Valeur  : INTEGER;
                Suivant : Liste;
               END;
\end{verbatim}
Lorsque la liste vaut {\tt NIL}, elle est vide,
c'est une liste de zéro éléments.

Sinon, la valeur qui est dans {\tt Valeur} est le premier élément
de la liste, tandis que {\tt Suivant} pointe sur le reste de la liste.
Bien évidemment, le reste de la liste
est aussi une liste, avec un élément de moins.

\subsection*{Exercices}
$\bullet$ 
\'Ecrire une fonction {\tt Longueur} qui retourne
un entier valant le nombre d'\'el\'ements de la liste cha\^{\i}n\'ee
donn\'ee en argument.
Comprendre pourquoi il est naturel d'utiliser une
fonction récursive.

$\bullet$ 
\'Ecrire une proc\'edure {\tt EcritListe} qui affiche successivement
les \'el\'ements qui composent la liste donn\'ee en argument.

$\bullet$
\'Ecrire une fonction {\tt Ajoute} prenant une liste
et un entier en arguments, qui ajoute au début de la liste
l'entier qui a été donné en argument, et qui donne comme résultat
la nouvelle liste.

Vérifier le le programme principal ci-dessous
affiche bien \verb|4| puis \verb|12 3 27 5| :
\bgroup\small
\begin{verbatim}
VAR l : Liste;
BEGIN
  l := NIL;
  l := Ajoute(l,5);
  l := Ajoute(l,27);
  l := Ajoute(l,3);
  l := Ajoute(l,12);
  WriteLn (Longueur(l));
  EcritListe (l);
END.
\end{verbatim}
\egroup
\bigskip

$\bullet$
$\bullet$
\'Ecrire une procédure {\tt AjouteFin} prenant une liste
et un entier en arguments, qui ajoute à la fin de la liste
l'entier qui a été donné en argument.

Comprendre pourquoi la procédure {\tt AjouteFin}
peut modifier la liste, même si elle est passée
comme argument par valeur.

$\bullet$
Utiliser cette procédure pour faire une fonction
{\tt LitListe} qui lit successivement les éléments
de la liste, que l'utilisateur tape au clavier.
On pourra utiliser la convention suivante :
si l'utilisateur a tapé le nombre \verb|-1|,
cela signifie qu'il est arrivé à la fin de la liste.

$\bullet$
$\bullet$
Écrire une procédure {\tt Concate} qui prenne 2 listes en argument
et qui ajoute à la fin de la première la seconde.

$\bullet$
$\bullet$
Écrire une procédure {\tt Insere} prenant une liste
et deux entiers \verb|N| et \verb|p| en arguments
et qui insère en \verb|p|-ième position l'élément \verb|N|.
Cette procédure rajoute \verb|N| à la fin de la liste si
celle-ci a moins de \verb|p| éléments.

Lorsqu'on insère l'entier \verb|6| en deuxième position
dans la liste \verb|(12, 3, 27, 5)|, elle devient
\verb|(12, 6, 3, 27, 5)|.

$\bullet$
$\bullet$
Écrire une procédure {\tt Détruit} prenant une liste
et un entier \verb|p| en arguments
et qui supprime le  \verb|p|-ième élément de la liste,
ne faisant rien si la liste a moins de \verb|p| éléments.
Lorsqu'on supprime le deuxième élément
de la liste \verb|(12, 3, 27, 5)|, elle devient
\verb|(12, 27, 5)|.

$\bullet$
$\bullet$
Écrire une procédure {\tt InsereTri} prenant une liste
et un entier en arguments, qui ins\`ere l'entier dans la liste
en supposant que la liste est déjà triée par ordre croissant.

$\bullet$
$\bullet$
$\bullet$
En déduire une procédure {\tt Tri}
qui trie la liste donnée en argument.
C'est le {\em tri par insertion}.

\end{multicols}

\end{document}
