\documentclass[10pt,french]{article}
 
% Packages
\usepackage{fullpage}
\usepackage{multicol}
\usepackage{babel}
\usepackage[latin1]{inputenc}
 
\setlength{\textheight}{24.1cm}
 
\newcounter{numeroquestion}
\newcounter{numerocorrection}
 
\def\Exo{\addtocounter{numeroquestion}{1}
     {\mbox{}\\\bf Question \arabic{numeroquestion} :}\ }
 
\def\Corr{\addtocounter{numerocorrection}{1}
     {\bf Correction \arabic{numerocorrection} :}\ }
 
% Titre
\title{Partiel IF122 - Dur\'ee : 50mn}
\date{}
\author{}
\pagestyle{plain}
 
\begin{document}
\maketitle
 
 
{\bf Les documents sont interdits. Vous n'avez pas le droit de sortir
 de la salle avant la fin de l'épreuve. Votre nom doit figurer en
 commentaire tout au début de votre programme, sous la forme : // NOM
 Prénom. Une fois le temps ecoul\'e, vous quitterez la salle sans
 éteindre votre machine le temps que l'un des surveillants vienne
 récupérer votre résultat. Bonne chance.}\\


Une matrice se représente habituellement \`a l'aide d'un tableau. Ceci
a deux inconvénients. Le premier est que la taille du tableau doit
être fixée \`a priori, et le second, que chacune des cases ai une
valeur. Or bien souvent les grandes matrices ont beaucoup de cases
vides (de valeur z\'ero). Nous allons les représenter \`a l'aide d'une
liste chaînée, avec pour convention de ne pas faire apparaître les
zéro.\\

Cette liste doit correspondre \`a la lecture des éléments de la
matrice de gauche \`a droite en partant du coin supérieur gauche, puis
on continue en revenant \`a la ligne. Les cellules contiennent \`a la
fois la valeur de la case {\tt val}, mais aussi ses deux coordonnées
{\tt x,y} respectivement pour la colonne et la ligne.

Le type vous sont donn\'es :
{\small
\begin{verbatim}
#include <iostream>
typedef struct cellule{
  int val;
  int x;
  int y;
  cellule * suiv;
};
typedef cellule* liste_M;
\end{verbatim}}

\Exo Pour tester vos fonctions, vous aurez besoin d'un exemple. 
Écrivez une fonction {\tt exemple} qui retourne une liste
correspondant \`a la matrice  :

$$ \left(\begin{array}{ll} 5 & -7\\ 0 & 4 \end{array}\right)$$


\Exo On veut afficher cette liste. Pour la matrice de l'exemple
préc\'edent, le résultat doit \^etre :\\ $(1,1,5)\;\;(2,1,-7)\\(2,2,4)
$\\

C'est \`a dire que l'on affiche, par lignes, les cellules.\\ Écrivez
une procédure qui affiche une {\tt liste\_M}. Essayez la sur notre
exemple.


\Exo Si on cherche \`a additionner deux matrices, un cas tr\`es simple
est celui o\`u l'on ajoute une matrice qui est r\'eduite \`a une seule
cellule. On suppose que l'on a \`a notre disposition une proc\'edure
{\tt ajoute\_reduite(liste\_M m,cellule \&c)}, qui peut lors de
l'ajout modifier les champs de {\tt c}.

Écrivez une procédure r\'ecursive simple {\tt additionne\_M} qui
utiliserait {\tt ajoute\_reduite } pour additionner deux listes
repr\'esentant des matrices.


\Exo Il faut maintenant \'ecrire {\tt ajoute\_reduite(liste\_M
m,cellule \&c)}.  Il faut faire attention \`a la chose suivante : si $m$
contient une cellule de mêmes coordonn\'ees que {\tt c} et de valeur
opposée, alors le résultat de la somme est $0$, or par convention une
telle cellule ne doit pas apparaître dans la représentation de la
matrice.

\Exo Testez votre procédure {\tt ajoute\_reduite} en ajoutant 
la cellule $(2,1,7)$ \`a notre exemple. Testez l'addition de matrice
en additionnant notre exemple avec lui même.




 \end{document}
