\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 Exercice \arabic{numeroquestion} :}\ }

\def\Corr{\addtocounter{numerocorrection}{1}
     {\bf Correction \arabic{numerocorrection} :}\ }

% Titre
\title{TD7 - Listes cha\^{\i}n\'ees (Suite)} \date{Ann\'ee 2002} \author{}
\pagestyle{plain}

\begin{document}

\maketitle


\section{Tri par fusion}

{\bf Le tri par fusion} 

Pour trier une liste cha\^{\i}n\'ee d'au moins deux \'el\'ements, on
proc\`ede {\it r\'ecursivement} comme suit~: on la coupe en deux, on
trie chacune des parties (qui sont plus petites) et on les
``fusionne'' comme on l'explique plus bas, d'o\`u le nom de cette
m\'ethode. Lorsque les morceaux de la liste coup\'ee en deux ne sont
pas plus petit que la liste de d\'epart, (le cas de base de la
r\'ecursion) c'est que la liste a au plus un \'el\'ement, et elle
peut \^etre consid\'er\'ees comme d\'ej\`a tri\'ees.

\Exo
Faire le sch\'ema correspondant \`a l'op\'eration suivante~: soit {\bf
a} une liste contenant {\it n} \'el\'ements. On cr\'ee une liste {\bf
b} qui contient les $\frac{n}{2}$ derniers \'el\'ements de {\ a} en
les d\'etachant de {\bf a}. {\bf a} ne contient donc plus que ses
$\frac{n}{2}$ premiers \'el\'ements.


\Exo Écrire une fonction qui partage une liste en deux.  Combien de
cellules sont visit\'ees pendant cette op\'eration ?  En fait on n'est
pas oblig\'e de preserver l'ordre des cartes lors du partage. Donner
une seconde solution qui ne visite qu'une fois chacune des cellules.


{\bf Fusion}

La fusion de deux listes tri\'ees {\bf a} et {\bf b}, pour obtenir une
autre liste tri\'ee, s'effectue de la fa\c{c}on suivante: on s'arrange
pour que la valeur de t\^ete de {\bf a} soit inf\'erieure \`a celle de
{\bf b} (quitte \`a permuter les deux). Dans ce cas on \'ecarte le
premier \'element de {\bf a}, et on fusionne ce qui reste de {\bf a}
avec {\bf b}. Finalement on rajoute l'\'el\'ement \'ecart\'e au
r\'esultat.

Il est \`a noter que toutes ces op\'erations se font par manipulations
de pointeurs : \`a aucun moment on ne cr\'ee de nouvel \'el\'ement.


\Exo Écrire une proc\'edure \`a deux arguments {\bf a} et{\bf b}, qui  fusionne
 les deux listes dans $a$.


\Exo Écrire un programme qui effectue par cette m\'ethode, de fa\c{c}on r\'ecursive, le tri de {\bf n} 
entiers donn\'es par l'utilisateur.


\section{Listes doublement chaînées}

Les listes doublement cha\^{\i}n\'ees sont des extensions des listes
chaînées. Les cellules contiennent \`a la fois un pointeur vers la
cellule qui la suit (ici {\tt suiv}), et \'egalement un pointeur vers
la cellule qui la prec\`ede. Lorsque l'une des deux n'existe pas, on
le signale en lui donnant la valeur {\tt NULL}.

\Exo On consid\`ere une machine constituée d'une tête de lecture et
 d'un ruban ou elle peut écrire.  La tête peut se d\'eplacer vers la
gauche ou vers la droite. On représente le ruban \`a l'aide d'une
liste doublement chaînée, et la tête de lecture par un pointeur vers
une position sur le ruban.

A chaque fois que la tête change de position, elle augmente de un la
valeur de la case sur laquelle elle pointait, avant de la quitter.

Lorsque la tête avance au delà de l'extrémité droite du ruban, elle le
rallonge d'une case, et elle y \'ecrit 0.
\begin{itemize}
\item définissez la machine
\item écrivez les procédures {\tt recule} et {\tt avance}
\end{itemize}

\section{Exercices complémentaires}

\Exo Après avoir tri\'e une liste, on va la mélanger. Dans le monde réel 
pour mélanger, (c'est l'exemple d'un paquet de cartes), on le coupe
d'abord en deux tas \`a priori non équilibres, puis on intercale les
éléments l'un après l'autre. Proposer les proc\'edures qui permettent
de faire ces opérations.

\Exo \underline{Listes  cha\^{\i}n\'ee CIRCULAIRES}

Rien dans la d\'efinitions des différents types de liste vus jusqu'\`a
pr\'esent n'oblige \`a ce que la fin d'une liste soit d\'etermin\'ee
par le pointeur NULL. On consid\`ere ici des listes (dites
circulaires) que l'on peut obtenir \`a partir des listes connues
(dites planes), pour lesquelles le successeur du ``dernier'' est le
``premier''. ( Pour les listes doublement chainees, on dira que le
prédécesseur du ``premier'' élément est le ``dernier'')

\begin{itemize}
\item Donner un exemple de liste non circulaire et non plane. 
A quoi cela ressemble t'il si on se pose la même question avec des
listes doublement chaînées ?

\item Chercher le minimum d'une liste circulaire.

\item On veut écrire une fonction qui teste si une liste est plane,
pour cela il faut la parcourir et détecter si on est d\'ej\`a passe
par une cellule. Le seul probl\`eme est qu'il faut r\'epondre oui ou
non, et donc trouver une condition d'arr\^et \`a ce parcourt pour le
cas o\`u la liste est non plane. Pour nous aider, on suppose que les
cellules comportent un champs supplémentaire {\tt tag}. Ce {\tt
booléen}, initialement a faux permet de garder une trace d'un
passage. Écrivez la fonction {\tt test\_plane}. Attention \`a remettre
la liste dans l'état o\`u vous l'avez trouv\'e !

\item Écrire une fonction qui teste si une liste chaînée est
circulaire.

\item Comment faire si on n'avait pas sous la main ce {\tt tag} ?
\end{itemize}



\pagebreak

\section{Correction}
\Corr


\Corr La premi\`ere solution attendue consiste \`a
 compter les éléments : n, puis de recompter en s'arretant juste avant
 la moitie : n/2-1, pour pouvoir couper.  {\small
\begin{verbatim}
// coupe la liste l en deux partie de meme longueur +- 1
void coupe(liste l,liste &a,liste &b){
   int n=0;
   // calcul de la longueur
   a=l;
   for (liste i=l;l!=NULL;l=l->suiv){n++;}
   
   // on repere la moitie
   l=a;
   for (int i=1; i < n/2;i++ ) { l=l->suiv;}
   
   // on detache la branche
   b=l->suiv;
   l->suiv=NULL;
}
\end{verbatim}}

Une autre solution consiste \`a distribuer les \'el\'ements,
alternativement dans une liste puis une autres. Ça vaut le coup de
regarder pour cette solution le jeu des passages par référence.

{\small
\begin{verbatim}
// Une autre facon de couper, en distribuant dans des paquets
// initialement vides
void coupe2(liste l,liste &a,liste &b){
   a=NULL;
   b=NULL;
   distribue(l,a,b);
}

// le haut de la liste part dans un paquet, puis le suivant dans
// l'autre paquet, jusqu'a ce que la liste soit vide.
void distribue(liste l,liste &a,liste &b){
   if (l==NULL) return;
   insert(a,l->val);
   distribue(l->suiv,b,a);
}

// ajout d'un element a une liste
void insert(liste &l,int i){
   liste aux=new element;
   aux->val =i;
   aux->suiv = l;
   l=aux;
}
\end{verbatim}
}

\Corr
{\small
\begin{verbatim}
// la fusion de deux listes Triees
// resultat dans a
void fusionneTriee(liste &a,liste &b){
   liste aux,aux2;
   if (a==NULL) {a=b; return;}
   if (b==NULL) {return;}
   
   if (a->val > b->val) { // echange de a et de b
      aux=a;
      a=b;
      b=aux;
   } // on peut continuer

   fusionneTriee(a->suiv,b); // Remarquer qu'en une etape on fait 2 operations
   // a) on fusionne les sous listes
   // b) on rattache a la cellule de tete de a
}
\end{verbatim}
}
\Corr
{\small
\begin{verbatim}
// le trie par fusion
void trie(liste &l){
   liste a,b;
   coupe2(l,a,b);
   // si on a pas reduit en coupant on s'arrete
   if (a==NULL) {l=b;return;}
   if (b==NULL) {l=a;return;}
   trie(a);
   trie(b);
   fusionneTriee(a,b);
   l=a;
}
\end{verbatim}
}
\Corr
{\small
\begin{verbatim}
#include <iostream>

typedef struct element{
   int val;
   element * suiv;
   element * pred;
};

typedef element* tete;


void affiche_g(tete t){
   if (t==NULL) { cout << endl; return;}
   cout << t->val << " ";
   affiche_g(t->pred);
}

void affiche_d(tete t){
   if (t==NULL) { cout << endl; return;}
   cout << t->val<< " ";
   affiche_d(t->suiv);
}


void affiche(tete t){
   cout << " partie gauche" << endl;
   affiche_g(t);
   cout << "partie droite" << endl;
   affiche_d(t);
}

void avance(tete &t){
   if(t==NULL){
      t=new element;
      t->suiv=NULL;
      t->pred=NULL;
      t->val = 0;
      return;
   }
   (t->val)++;
   if (t->suiv == NULL){
      t->suiv=new element;
      t->suiv->pred=t;
      t=t->suiv;
      t->suiv=NULL;
      t->val=0;
   }
   else t=t->suiv;
}

void recule(tete &t){
   if (t == NULL) return;
   if (t->pred==NULL) return;
   (t->val)++;
   t=t->pred;
}



void main(){
    tete t=NULL;
    avance(t);
    avance(t);
    avance(t);
    recule(t);
    recule(t);
    avance(t);
    recule(t);
    avance(t);
    recule(t);

    affiche(t);
}
\end{verbatim}
}
\Corr
{\small
\begin{verbatim}
#include <iostream>
#include <cstdlib>
#include <time.h>

typedef struct element{
   int val;
   element * suiv;
};

typedef element* liste;


// ajout d'un element a une liste
void insert(liste &l,int i){
   liste aux=new element;
   aux->val =i;
   aux->suiv = l;
   l=aux;
}

// creation automatique d'une liste de 10 elements
void liste_10(liste &l){
   l=NULL;
   for (int i=0;i<10;i++) {insert(l,i);}
}

// affichage d'une liste
void affiche(liste l){
   if (l==NULL) {cout << endl; return;}
   cout << " " << l->val;
   affiche(l->suiv);
}
// taille de la liste
int taille(liste l){
   if (l==NULL) return 0;
   return 1+taille(l->suiv);
}


// coupe en position x, resultat dans a et b
void coupe(liste l,int x,liste &a,liste &b){
   
   // on repere la position x-1
   a=l;
   for (int i=1; i < x ;i++ ) { l=l->suiv;}
   
   // on detache la branche
   if (l== NULL) { b=NULL;}
   else {
      b=l->suiv;
      l->suiv=NULL;
   }
}

// on intercale, resultat dans a
void shuffle(liste &a,liste b){
   if (a==NULL) {a=b;return;}
   if (b==NULL) {return;}
   shuffle(a->suiv,b->suiv);
   b->suiv=a->suiv;
   a->suiv=b;
}
// cette seconde version est jolie non ?
// c'est pas facile en tout ca
void shuffle2(liste &a,liste b){
    if (a==NULL) {a=b;return;}
    shuffle2(b,a->suiv);
    a->suiv=b;
}

// on coupe au hazard, et on intercale
void melange_1(liste &l){
   liste a,b;
   int x=taille(l);
   x=(rand() % x);
   coupe (l,x,a,b);
   cout << " premiere liste "; affiche(a); cout << endl;
   cout << " seconde liste "; affiche(b); cout << endl;
   shuffle(a,b);
   l=a;
}

void main(){
   liste l;
   srand(time(NULL));
   
   liste_10(l);
   affiche(l);
   melange_1(l);
   affiche(l);
}
\end{verbatim}
}

\Corr 

\begin{itemize}
 \item il suffit que le dernier pointe sur un élément du milieu. Pour
 les doublement chaînée, c'est pire, puisque le prédécesseur est alors
 une informations incomplète, on peut dire que ça donne des structures
 plus générales que les arbres.

\item
je garde un doit sur le début, et je parcours jusqu'à ce que je
retombe dessus.

{\small
\begin{verbatim}
int min(liste l){
   liste aux;
   int m;
   if (l==NULL) { cout << ``erreur''; return -1;}
   m=l->val;
   aux=l->suiv;
   while(aux!=l){
     if (aux->val < m) m= aux->val;  
     aux=aux->suiv;
   }
}
\end{verbatim}
}
\item il ne faut pas oublier de detagger, ça doit se faire avant les return, 
ce qui m'impose de stocker le résultat.

{\small
\begin{verbatim}

bool est_plane(liste l){
   bool res;
   if (l==NULL) return true;
   
   if (l->tag) { 
     l->tag=false;
     return false;
   }
   l->tag =true;
   res=est_plane(l->suiv);
   l->tag=false;
   return res;
}
\end{verbatim}
}

\item Une liste est circulaire, si lorsque je rencontre un état marque
 c'était mon point de départ. Il faut donc reprendre la fonction
 précédente, et au lieu de retourner un booléen, retourner le pointeur
 sur lequel on cycle. Remarquer que NULL est circulaire.

{\small
\begin{verbatim}
bool est_circulaire(liste l){
 return (l==get_cycle(l));
}

liste get_cycle(liste l){
   liste res;
   if (l==NULL) return l;
   
   if (l->tag) { 
     l->tag=false;
     return l;
   }
   l->tag =true;
   res=get_cycle(l->suiv);
   l->tag=false;
   return res;
}
\end{verbatim}
}
\item On pourrait utiliser une liste de pointeurs, qui contiendrait les positions déjà visitées.
  
\end{itemize}
\end{document}

