\documentclass[10pt]{article}

% Packages
\usepackage{french}
\usepackage{fullpage}
\usepackage{multicol}
\usepackage{epsfig}
\setlength{\textheight}{24.1cm}

% Titre
\title{Partiel IF122 - Dur\'ee : 50mn}
\date{}
\author{}
\pagestyle{empty}



\begin{document}
\maketitle


{\bf Les documents sont interdits. Vous n'avez pas le droit de sortir de la salle avant la fin de l'epreuve. Votre nom doit figurer en commentaire tout au debut de votre programme, sous la forme : // NOM Prenom. Une fois le temps ecoul\'e, lancer l'impression de votre programme, et attendez sans quitter votre place que l'un des surveillants vienne le copier sur disquette. Bonne chance.}\\


Dans une liste on peut souhaiter eviter les begaiements, c'est le
sujet de cet examen. Partant d'une liste {\bf l} d'elements, on
cherche \`a obtenir une liste {\bf l1} de {\bf double\_elem} de la
facon suivante : si {\bf l} commence par 4 occurrences successives de
{\bf 1}, alors {\bf l1} commence par un double element dont le premier
champs indique la valeur, ici {\bf 1}, et sont second champs indique
sa multiplicit\'e, ici {\bf 4}, et ainsi de suite.

\begin{center}\epsffile{compacte_exemple_2.eps}\end{center}


Il vous est demande d'ecrire une fonction {\bf compacte} qui prenne en
argument une liste et retourne la liste double correspondante au
compactage d\'ecrit dans l'exemple.


Pour vous concentrer sur le travail demand\'e, il vous est fourni le
code suivant qui saisit et affiche les listes  : \\

\begin{multicols}{2}{|}
\begin{verbatim}
#include <iostream.h>

typedef struct elem{
  int val;
  elem * suivant;
};

typedef elem* liste;

typedef struct double_elem{
  int val;
  int multiplicite;
  elem * suivant;
};

typedef double_elem* liste_double;



liste saisie(int n){
  elem* e;
  
  if (n==0) return( NULL);

  e=new elem;
  cout << ``valeur :'' ;
  cin >> e->val;
  e->suc=saisie(n-1);
  return e;

}

void affiche(liste l){
  if (l==NULL) {cout << endl;}
  else {
      cout << l->val;
      affiche(l->suivant);
  }
}

void affiche_double(liste_double l){
  if (l==NULL) {cout << endl;}
  else {
      cout << ``(`` << l->val<< ``,'' 
           << l->multiplicite << ``) '';
      affiche(l->suivant);
  }
}

int main(){
  liste l;
  int n;
  cout << `` longueur de la liste'';
  cin >> n;
  l = saisie (n);
  cout << ``liste saisie '';
  affiche(c);
}
\end{verbatim}
\end{multicols}



\end{document}
