\documentclass[10pt,a4paper,twoside]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amsfonts,amsmath,amsthm,amssymb,url,stmaryrd}
\usepackage{xspace}
\usepackage{fullpage}
\usepackage{color}
\usepackage{fancyhdr}

%\usepackage[correction]{ennonce}
\usepackage{ennonce}
\usepackage{fancyvrb}
\usepackage{color}
\usepackage{ifthen}
\usepackage{calc}

% Small verbatim + tabs
% \makeatletter
% \newenvironment{code}{\small\obeylines\@verbatimtab}{\endtrivlist}
% \makeatother

\fvset{numbersep=5pt}
\fvset{obeytabs=true}
\fvset{resetmargins=true}
\fvset{baselinestretch=0.7}
\fvset{frame=single}
\fvset{numbers=left}

\renewcommand{\FancyVerbFormatLine}[1]{\small{#1}}

\def\C{\textsf{C}\xspace}


\fancyhf{}
\renewcommand{\headrulewidth}{0mm}\renewcommand{\footrulewidth}{0mm}
\fancyhead[L]{\footnotesize DEUG MIAS 2\ieme~année}
\fancyhead[R]{\footnotesize Cours de programmation 2001--2002}
\fancyfoot[C]{\footnotesize M.\textsc{Quinson}}

\begin{document}
\pagestyle{fancy}
\begin{center}
  {\Large \ifennonce{Examen}\ifcorrection{Correction de l'examen de} TD n°2}

  \bigskip\parbox{120mm}{%
    La durée de l'examen est de 30 minutes, les notes de cours et de
    TD sont autorisées. La notation prendra en compte la présentation
    et la clarté des explications (programmes commentés, dessins
    explicatifs, \dots). L'examen sera noté sur 10 points. Les questions
    sont indépendantes.
  }\bigskip
\end{center}

L'objectif de cet examen est d'écrire la structure « arbre généalogique »
et certaines fonctions associées. On utilisera pour cela les définitions
suivantes :
\begin{Verbatim}
  typedef struct s_individu individu_t;

  struct s_individu {
    char *nom, *prenom;
    individu_t *pere, *mere;
    int nb_enfants;
    individu_t **enfants;
  };
\end{Verbatim}

Le champ \texttt{enfants} de cette structure est donc un tableau de
longueur \texttt{nb\_enfants} dont chaque case est un pointeur vers l'enfant
en question.

\begin{Question}
  \'Ecrivez la fonction créant un individu sans lien de parenté. Son
  prototype est le suivant :
  \texttt{individu\_t *cree\_individu(char *nom, char *prenom);}
  
  \noindent\hspace{1em}\emph{Indication:} il ne faut pas oublier le malloc.
\end{Question}
\begin{Reponse}
  \begin{Verbatim}
individu_t *cree_individu(char *prenom, char *nom) {
  individu_t *res;
  res=(individu_t*)malloc(sizeof(individu_t));

  res->nom = nom;
  res->prenom = prenom;
  res->pere = NULL;
  res->mere = NULL;
  res->nb_enfants=0;
  res->enfants=NULL;

  return res;
}    
  \end{Verbatim}
\end{Reponse}

\begin{Question}
  Ecrivez une fonction ajoutant un enfant à un couple d'individus
  existants. Son prototype est le suivant :\\
  \texttt{individu\_t *cree\_enfant(char *nom, char *prenom, individu\_t
  *pere,individu\_t *mere);}

\noindent\hspace{1em}\emph{Indication:} Il faut créer le nouvel enfant,
  puis modifier le pere et la mere pour indiquer dans ces structures
  l'existance de ce nouvel enfant. 

\noindent\hspace{1em}\emph{Indication:} La modification du père (et de la
  mère) demande entre autres un \texttt{realloc}.
\end{Question}
\begin{Reponse}
  \begin{Verbatim}
individu_t *cree_enfant(char *prenom, char *nom,
                        individu_t *pere, individu_t *mere) {

  individu_t *res;

  /* crée le fils */
  res=cree_individu(prenom,nom);
  /* indique dans le fils sa parenté */
  res->pere = pere;
  res->mere = mere;
  /* indique le nouveau fils dans le pere */
  pere->nb_enfants++;
  pere->enfants =(individu_t**) realloc(pere->enfants,
                                        pere->nb_enfants*sizeof(individu_t*));
  pere->enfants[ pere->nb_enfants-1 ] = res;
  /* idem pour la mère */
  mere->nb_enfants++;
  mere->enfants =(individu_t**) realloc(mere->enfants,
                                        mere->nb_enfants*sizeof(individu_t*));
  mere->enfants[ mere->nb_enfants-1 ] = res;
}
\end{Verbatim}
\end{Reponse}

\begin{Question}
  [QUESTION SUBSIDIAIRE] \'Ecrivez une fonction libérant la mémoire occupée
  par un individu, en tenant à jour les structures associées (enfants,
  parents, \emph{etc.}).
\end{Question}
\begin{Reponse}
  \begin{Verbatim}
void libere_individu(individu_t *ind) {
  int i;

  if (ind) {
    /* Met à jour le père si besoin */
    if (ind->pere) {
      /* Cherche ce fils dans la table des enfants */
      for (i=0 ; 
           i < ind->pere->nb_enfants && ind->pere->enfants[i] != ind ;
           i++); /* rien dans la boucle */
      if (ind->pere->enfants[i] != ind) {
        /* on a pas trouvé le fils : cela ne devrait jamais se produire */
        printf("libere_individu(): Erreur interne: "
               "l'individu n'est pas le fils de son père !\n");
        exit (1);
      }

      /* On décale les enfants restant */
      for (;/* pas d'initialisation, i a la bonne valeur */
           i < ind->pere->nb_enfants - 1 ; /* -1 car on utilise i+1 plus loin*/
           i++) {
        ind->pere->enfants[i] = ind->pere->enfants[i+1];
      }

      /* On réduit la taille du tableau à ce dont on a besoin */
      ind->pere->nb_enfants--;
      ind->pere->enfants = 
        (individu_t **)realloc(ind->pere->enfants,
                               ind->pere->nb_enfants * sizeof(individu_t*));
    }


    /* Idem pour la mère */
    if (ind->mere) {
      /* Cherche ce fils dans la table des enfants */
      for (i=0 ; 
           i < ind->mere->nb_enfants && ind->mere->enfants[i] != ind ;
           i++); /* rien dans la boucle */
      if (ind->mere->enfants[i] != ind) {
        /* on a pas trouvé le fils : cela ne devrait jamais se produire */
        printf("libere_individu(): Erreur interne: "
               "l'individu n'est pas le fils de sa mère !\n");
        exit (1);
      }

      /* On décale les enfants restant */
      for (;/* pas d'initialisation, i a la bonne valeur */
           i < ind->mere->nb_enfants - 1 ; /* -1 car on utilise i+1 plus loin*/
           i++) {
        ind->mere->enfants[i] = ind->mere->enfants[i+1];
      }

      /* On réduit la taille du tableau à ce dont on a besoin */
      ind->mere->nb_enfants--;
      ind->mere->enfants = 
        (individu_t **)realloc(ind->mere->enfants,
                               ind->mere->nb_enfants * sizeof(individu_t*));
    }
    if (ind->enfants) /* pas de free(NULL) !! */
      free(ind->enfants); 
    free(ind);
  }
}    
  \end{Verbatim}
\end{Reponse}

\begin{Question}
  Ecrivez une fonction créant la famille Dupont. Le pere s'appelle Jean, la
  mère Jacqueline, et ils ont trois enfants Paul, Henri et Charlotte.

\noindent\hspace{1em}\emph{Indication:} Servez vous des fonctions définies
  aux questions précédentes. 
\end{Question}
\begin{Reponse}
  \begin{Verbatim}
individu_t *dupont() {
  individu_t *pere,*mere,*paul,*henri,*charlotte;

  pere=cree_individu("Jean","Dupont");
  mere=cree_individu("Jacqueline","Dupont");
  paul=cree_enfant("Paul","Dupont",pere,mere);
  henri=cree_enfant("Henri","Dupont",pere,mere);
  charlotte=cree_enfant("Charlotte","Dupont",pere,mere);

  return pere;
}    
  \end{Verbatim}
\end{Reponse}

\begin{Question}
  Ecrivez les fonctions suivantes, chacune prenant deux individus
  \texttt{ind1} et \texttt{ind2} en parametres:
  \begin{itemize}
  \item est\_pere\_de : renvoi vrai ssi le \texttt{ind1} est le pere de
  \texttt{ind2}.
\item est\_frere\_de : renvoi vrai ssi \texttt{ind1} et \texttt{ind2} ont les
  mêmes parents.
  \end{itemize}
\end{Question}
\begin{Reponse}
  \begin{Verbatim}
int est_pere_de (individu_t*ind1, individu_t*ind2) {
  return (ind1 && ind2 && /* vérifie que les individus ne sont pas NULL */
          ind2->pere == ind1);
}

int est_frere_de (individu_t*ind1, individu_t*ind2) {
  return (ind1 && ind2 && /* vérifie que les individus ne sont pas NULL */
          /* on vérifie qu'on connait leurs parents */
          ind1->pere && ind1->mere && ind2->pere && ind2->mere &&
          /* on test qu'ils ont les mêmes parents */
          ind1->pere == ind2->pere && 
          ind1->mere == ind2->mere);
}    
  \end{Verbatim}
\end{Reponse}

\end{document}

