% Document Type: LaTeX
% Master File: TP4.tex
% FILE. . . . . /users/formel2/dicosmo/ACADEMIC/CORSI-DIDATTICA/Algo199798/TP4.tex
% EDIT BY . . . Roberto Di Cosmo
% ON MACHINE. . Verveine.Ens.Fr
% STARTED ON. . Thu Nov 20 15:19:43 1997
\documentclass{article}
\usepackage{a4}
\usepackage{francais}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}{Exercice}[section]
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}
% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip
\bigskip

\centerline {TP num\'ero 3}
\centerline {semaine du 26 octobre 1998}
\bigskip
\bigskip
\bigskip
\centerline{\bf Struct(ures) de donn\'ees. Listes. Arbres.}

\section{Structures de donn\'ees}

En C il est possible pour l'utilisateur de d\'efinir des structures de donn\'ees
en utilisant la construction \verb|struct| qui corresponde aux declarations de
types enregistrement en CamlLight ou Pascal.\\

Par exemple, 
%
\begin{verbatim}
struct date {
            int annee;
            int mois;
            int jour;
};
\end{verbatim}
%
d\'efinit un   type   enregistrement \verb|date| avec  des   champs  \verb|annee|,
\verb|mois| et \verb|jour| de type \verb|int|.\\

Ensuite, on peut d\'eclarer des variables de ce nouveau type :
%
\begin{verbatim}
struct date d;
\end{verbatim}
%
et la d\'eclaration alloue directement la m\'emoire n\'ecessaire pour la structure.\\
On peut acceder aux champs par l'op\'erateur de s\'el\'ection \verb|.| comme en CamlLight :
%
\begin{verbatim}
d.annee=1997;
d.mois=11;
d.jour=24;
printf("La date est %02d/%02d/%d\n",d.jour,d.mois,d.annee);
\end{verbatim}
%
Enfin, on peut utiliser la construction \verb|typedef| pour assigner un nouveau
nom \`a tout type d\'ej\`a existant, avec la m\^eme syntaxe que pour une d\'eclaration \verb|extern|
ou \verb|static|, i.e.\\
\mbox{}\hfill \verb|typedef| $typepreexistant$ \verb|NOUVEAU(X)NOM(S)|\hfill\mbox{}\\
Par exemple :
%
\begin{verbatim}
typedef struct date DATE, *DATEPTR;
\end{verbatim}
%
permet ensuite de d\'eclarer
%
\begin{verbatim}
DATE d;      /* struct date d   */
DATEPTR pd;  /* struct date *pd */
\end{verbatim}
%
On peut aussi tout faire en un seul coup, comme dans l'exemple du type list plus avant.\\
%
Notons enfin que quand on manipule des structures on le fait  le plus souvent en
passant aux fonctions des pointeurs sur des structures et non pas les structures
elles m\^emes (on n'a pas  envie de recopier des  structures \`a chaque coup !), donc
on   trouve    souvent  la   notation   syntaxique  \verb|pd->annee|    qui  est
\emph{exactement \'equivalente \`a} \verb|(*pd).annee|.

\section{Manipulation de listes}

Nous souhaitons  nous constituer  ici   une librairie de  fonctions utiles  pour
travailler  sur  des listes, et  l\`a  nous sommes d\'ej\`a  confront\'es  \`a un choix de
conception important : 

\begin{itemize}
  \item doit-on pr\'evoir de faire toutes les manipulations de fa\c{c}on
        \emph{destructive} en \emph{modifiant la structure en place} (on fera alors bien
        attention \`a pr\'evoir une fonction pour cloner une structure)?
  \item ou veut-on, au contraire, ne rien modifier en place, pour travailler
        comme en CamlLight (on devra alors faire attention \`a lib\'erer tout le temps la m\'emoire
        qui devient inutilis\'ee)?
\end{itemize}

Ici, nous allons  d'abord explorer  la deuxi\`eme  solution, en programmant  notre
biblioth\`eque  selon un approche  algebrique  aux types de  donn\'ees developp\'ee au
debut des ann\'ees 80, qui sugg\`ere de decomposer les  fonctions qui manipulent une
structure de donn\'ees en differentes classes : ``constructeurs'', ``destructeurs''
et ``testeurs'' (des noms qui expliquent d\'ej\`a tout).

\begin{exercise}[Le type de donn\'ee intlist]
Pour la structure de donn\'ees \verb|intlist| d\'efinie  comme suit

\begin{verbatim}
typedef struct intlist {
        int data;
        struct intlist *suivant;
} intlist;
\end{verbatim}

d\'efinissez les fonctions suivantes :\\
Coonstructeurs :
\begin{itemize}
  \item \verb|intlist *nil()| construit une ``intliste vide''
  \item \verb|intlist *cons(int data, intlist *l)| construit la intliste {\tt cons(data,l)}
        (la concatenation de la donn\'ee data en t\^ete de la intliste l)
\end{itemize}
Testeurs :
\begin{itemize}
  \item \verb|int isnil(intlist *l)| renvoie 1 si la intliste est vide et 0 sinon
\end{itemize}
Destructeurs :
\begin{itemize}
  \item \verb|int hd(intlist *l)| renvoie le premier \'el\'ement de la intliste {\tt l}
  \item \verb|intlist *tl(intlist *l)| renvoie le reste de la intliste {\tt a}
\end{itemize}
\end{exercise}

\begin{exercise}[Append et reverse]\mbox{}\\
\'Ecrivez une fonction \verb|void printintlist(intlist *l)| qui imprime les \'el\'ements d'une intliste.
Ensuite, \'ecrire une fonction 
%
\verb|intlist *append(intlist *l1, intlist *l2)| qui concatene deux listes, et une fonction
\verb|intlist *rev(intlist *l)|
qui renverse une intliste.\\

R\'emarquez que  si vous   vous   imposez d'\'ecrire  ces  fonctions  en   utilisant
\emph{uniquement} les fonctions definies ci-dessus, vous \^etes  oblig\'es de ne pas
faire de la modification en place. Mais rien ne vous emp\^eche d'essayer d'\'ecrire
une version avec modification en place, en accedant directement \`a la structure.\\

Testez   vos fonctions et  reflechissez  aux avantages et  d\'esavantages des deux
approches (en place vs. r\'ecopie).
\end{exercise}

\section{Manipulation d'arbres}

\begin{exercise}[Le type de donn\'ee intarbre]
Pour la structure de donn\'ees \verb|intarbre| d\'efinie  comme suit

\begin{verbatim}
typedef struct intarbre {
                int data;
                struct intarbre *fg;
                struct intarbre *fd;
} intarbre, *iaptr;
\end{verbatim}

d\'efinissez les fonctions suivantes :\\
Constructeurs :
\begin{itemize}
  \item \verb|iaptr empty()| construit un ``intarbre vide''
  \item \verb|iaptr node(int data, iaptr g, iaptr d)| construit l'intarbre {\tt node(data,g,d)}
\end{itemize}
Testeurs :
\begin{itemize}
  \item \verb|int isempty(iaptr a)| renvoie 1 si l'intarbre est vide et 0 sinon
\end{itemize}
Destructeurs :
\begin{itemize}
  \item \verb|int data(iaptr a)| renvoie la donn\'ee dans la racine de {\tt a}
  \item \verb|iaptr filsg(iaptr a)| renvoie le sousarbre gauche de {\tt a}
  \item \verb|iaptr filsd(iaptr a)| renvoie le sousarbre droit de {\tt a}
\end{itemize}
\end{exercise}

\begin{exercise}[Parcours d'arbres]
\'Ecrivez une fonction \verb|intlist *infixintarbre(iaptr a)| qui renvoie la liste des noeuds d'un intarbre
dans l'ordre de la visite infixe.\\
\'Ecrivez ensuite une fonction \verb|void printintarbre(iaptr a)| qui imprime les \'el\'ements d'un intarbre
d'entiers dans cet ordre (utilisez \verb|printintlist|).\\
\end{exercise}

\begin{exercise}[Miroir d'un arbre]
\'Ecrivez une fonction \verb|iaptr miroir(iaptr a)| qui construit l'arbre miroir de {\tt a},
en utilisant \emph{uniquement} les fonctions definies ci-dessus.\\
Testez votre fonction.
\end{exercise}

\begin{exercise}[Modification en place]
\'Ecrivez  maintenant,  en accedant   directement  \`a la   structure, une  fonction
\verb|void echange(iaptr a, iaptr b)| qui \'echange les arbres point\'es par {\tt a}
et {\tt b}.\\ Re\'ecrivez  la fonction \verb|miroir|  \`a l'aide de cette  fonction.
Commentez sur la diff\'erence des deux approches.
\end{exercise}

{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}
\end{document}
