\documentclass[10pt,french]{article}
 
% Packages
\usepackage{fullpage}
\usepackage{multicol}
\usepackage{babel}
\usepackage[latin1]{inputenc}
 
\setlength{\textheight}{24.5cm}
 
\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.

Les types 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  :
{\small
$$ \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.


Les questions suivantes visent \`a calculer, sur notre représentation,
la transpos\'ee de la matrice. C'est \`a dire que l'on va échanger les
lignes et les colonnes.

\Exo Écrire une fonction qui retourne le num\'ero de la plus petite
colonne qui contient un élément non nul. Elle retourne {\tt -1} si la
matrice est nulle. Vérifiez la sur notre exemple.


\Exo On suppose que l'on dispose d'une procédure {\tt
extrait\_transpose\_colonne(liste\_M \&m,int i,liste\_M \&a,liste\_M
\&b)} qui extrait de {\tt m} la colonne numéro {\tt i}, en plaçant le
résultat transpos\'e dans {\tt a}. {\tt b} est un pointeur vers le
dernier élément de {\tt a}. Utilisez cette procédure et la fonction
précédente pour écrire une procédure r\'ecursive qui effectue la
transposée d'une matrice.


\Exo Écrivez \`a présent la procédure {\tt
extrait\_transpose\_colonne(liste\_M \&m,int i,liste\_M \&a,liste\_M
\&b)}. Faites attention \`a placer les élément de {\tt a} dans le bon
ordre, et d'\'echanger leur coordonn\'ees.

\Exo Vérifier sur notre exemple.

\end{document}

