\documentclass[a4,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage[a4paper]{geometry}
\geometry{top=2cm, bottom=2cm, left=2cm, right=2cm}
\usepackage[french]{algorithm2e}
\usepackage{url}

\title{TD2~: Implémentation des listes}
\date{Vendredi 4 mars 2011}

\begin{document}
\maketitle

Ce TD vise à mettre en place une bibliothèque minimale pour la
manipulation des listes chaînées, qui servira au TD suivant. Les
questions portent essentiellement sur l'implémentation de diverses
opérations. Pour chacune de ces opérations, il vous est demandé~:
\begin{itemize}
\item de proposer un exemple d'utilisation de l'opération pour tester
  votre implémentation,
\item dans le cas où votre opération crée ou modifie une liste, de
  représenter l'état de la mémoire avant et après appel à votre
  fonction,
\item de justifier que votre implémentation termine et produit un
  résultat correct,
\item d'évaluer la complexité de votre algorithme.
\end{itemize}
Remarque~: vous pouvez choisir le style (récursif ou itératif) qui
vous convient le mieux. Il est néanmoins fortement conseillé de faire
chaque question dans les deux styles (quand cela s'y prête).

\section*{Représentation mémoire des listes}
\begin{enumerate}
\item Proposer un type C pour représenter les listes d'entiers.
\item \'Ecrire un constructeur de liste vide, et un constructeur
  \verb|cons| qui ajoute un élément en tête de liste et de prototype
\begin{verbatim}
list cons(int h, list t);
\end{verbatim}
\item \'Ecrire une fonction \verb|free_list| permettant de libérer
  la mémoire allouée à une liste.
\item \'Ecrire une fonction de copie de liste, de prototype
\begin{verbatim}
list copy_list(list l);
\end{verbatim}
\item Implémenter une fonction produisant la liste des $n$ premiers
  entiers naturels dans l'ordre décroissant, de prototype
\begin{verbatim}
list list_integers(int n);
\end{verbatim}
Si on l'appelle avec 5 pour argument la fonction doit produire la
liste $4 :: 3 :: 2 :: 1 :: 0 :: \emptyset$.
\begin{itemize}
\item (Optionnel) Comment produire la même liste en ordre croissant~?
\end{itemize}
\item (Optionnel) De la même façon que l'on peut utiliser des
  pointeurs sur des données (comme des entiers ou des caractères), on
  peut également manipuler en C des {\bf pointeurs sur fonction}.
  Lorsque l'on définit une fonction, son nom peut être utilisé pour
  désigner l'adresse en mémoire du code de la fonction~: le nom de la
  fonction est un pointeur sur la mémoire qui contient le code. Cette
  possibilité a un intérêt majeur, celui de permettre le passage d'une
  fonction en paramètre d'une autre. Réciproquement, si \verb|pf| est
  un pointeur sur fonction alors on peut appeler la fonction pointée
  par \verb|pf| en utilisant l'opérateur d'indirection~:
  \verb|(*pf)(...)|. Sachant cela, proposer une fonction
  \verb|list_init| qui initialise une liste en appelant une fonction
  sur les entiers données en paramètres. Par exemple, l'appel à
  \verb|list_init(3,pf)| doit retourner la liste $f(2) :: f(1) :: f(0)
  :: \emptyset$ où $f$ est la fonction pointée par \verb|pf|. Le
  prototype attendu est~:
\begin{verbatim}
list list_init(int n, int (*pf)(int x));
\end{verbatim}
\end{enumerate}

\section*{Observateurs}
Implémenter successivement~:
\begin{enumerate}
\item la fonction \verb|length| qui calcule la longueur d'une liste,
\item la fonction \verb|member| qui teste la présence d'un
  élément dans une liste, puis la fonction \verb|multiplicity| qui
  calcule le nombre d'occurrences d'un élément dans une liste. Proposer
  une autre version de \verb|member| en utilisant \verb|multiplicity|,
\item la fonction \verb|print_list| qui affiche une liste à
  l'écran,
\item la fonction \verb|equals| qui teste l'égalité de deux listes,
\item la fonction \verb|get| qui retourne le $i^e$ élément d'une
  liste.
\end{enumerate}

\section*{Modification des listes}
\begin{enumerate}
\item On s'intéresse à l'opération qui permet de supprimer le premier
  élément d'une liste. \`A quoi doit-on prendre garde~? Quelle est la
  conséquence sur le prototype et sur l'usage de cette fonction~?
\item Implémenter l'opération \verb|chop| qui supprime le premier
  élément d'une liste.
\item Utiliser la réponse précédente pour la fonction \verb|remove|
  qui retire le $i^e$ élément d'une liste.
\item \'Ecrire la fonction \verb|insert| qui permet d'insérer un
  élément à la $i^e$ position d'une liste, ainsi qu'une variante qui
  insère un élément à la fin de la liste.
\item Comment doit-on s'y prendre pour insérer un élément au milieu
  d'un tableau~? Discuter l'efficacité de l'opération ``insertion d'un
  élément'' dans le cas d'un tableau et d'une liste.
\end{enumerate}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
