%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   TC Info X PC 4
%     Listes (Java)
%   version du 24 octobre 98
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\titre}[1]{\begin{center}{\huge \bf #1}\end{center}}

\documentclass{article}

\usepackage{graphics}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Pour compatibilite
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\Lafig}[5]{
\begin{figure}[hbt]
\includegraphics{#1}
\caption{#5}

\end{figure}
}

\pagestyle{headings}
\markright{PC 4 listes et pointeurs}
\begin{document}
\LARGE



\titre{
PC 4\\
Listes cha\^{\i}n\'ees
}

\vspace{10mm}

 \begin{itemize}
\item Listes
\item Classes et objets
\item Listes cha{\^\i}n\'ees
\item Piles
\item Files

\end{itemize}
\pagebreak







\titre{ Listes }


But~: repr\'esenter des suites $(a,b,c,\ldots)$ d'\'el\'ements
d'un ensemble de fa\c{c}on \`a pouvoir facilement ins\'erer
un nouvel \'el\'ement (ou en supprimer un).
\begin{figure}[hbt]
\scalebox{0.7}{\includegraphics{liste}}
\caption{Liste chain\'ee $(a,b,c)$}
\end{figure}

\pagebreak

\titre{Exemples d'application}
1. Le {\it hachage ouvert} associe \`a chaque cl\'e $h(x)$
une liste.
\Lafig{hachage}{102mm}{128mm}{600}{Hachage ouvert}

2. L'espace m\'emoire sur disque est attribu\'e par blocs de taille
fixe et chaque fichier est repr\'esent\'e par une liste de blocs.
\pagebreak

\titre{ Classes et objets}


Cahque objet en Java est une {\em instance} d'une classe. Par exemple,
un objet de la classe
\begin{verbatim}
class Point {
  public double x,y;
}
\end{verbatim}
peut \^etre cr\'e\'e par 
\begin{verbatim}
Point origine = new Point();
\end{verbatim}
et ses coordonn\'ees initialis\'ees par
\begin{verbatim}
origine.x = 0.0;
origine.y = 0.0;
\end{verbatim}
Le nom de l'objet est une {\em r\'ef\'erence} de cet objet.
\begin{center}
\begin{picture}(200,80)(10,20)
\put(0,40){\framebox(25,25){}}
\put(70,40){\framebox(60,25){0.0 0.0}}
\put(100,40){\line(0,1){25}} % ligne de separation
\put(12.5,52.5){\vector(1,0){57.5}} %la fleche
\put(-10,20){origine}
\put(80,20){x}
\put(110,20){y}
\end{picture}
\end{center}
Si un nom ne r\'ef\'erence aucun objet, sa valeur est \verb+null+.
\pagebreak
\titre{Constructeurs}
On  cr\'ee des objets en utilisant des {\em constructeurs}. La
d\'eclaration
\begin{verbatim}
Point p;
\end{verbatim}
ne cr\'ee pas d'objet, seulement une r\'ef\'erence. On utilise
un constructeur pour cr\'eer l'objet. Par exemple, si la classe
Point contient le constructeur
\begin{verbatim}
Point(double a, double b) {
  x= a;
  y= b;
}
\end{verbatim}
l'instruction
\begin{verbatim}
p=new Point(5.2,3);
\end{verbatim}
cr\'ee un point de coordonn\'ees $(5.2,3)$.
\pagebreak

\begin{center}
{\huge \bf Listes cha{\^\i}n{\'e}es}
\end{center}

\begin{verbatim}
class Liste {
  int contenu;
  Liste suivant;

  Liste (int x, Liste a) {
    contenu = x;
    suivant = a;
  }
}
\end{verbatim}
Les instructions
\begin{verbatim}
 p=new Liste(5,null);
 p.suivant= new Liste(7,null);
\end{verbatim}
cr\'eent la liste $(5,7)$.
\pagebreak


\titre{ Insertion en t\^ete de liste}

\begin{verbatim}
static Liste ajouter (int x, Liste p) {
 return new Liste(x,p);
}
\end{verbatim}
L'instruction \verb+ q = ajouter(x,p); + ins\`ere x
en t\^ete de la liste p.
\Lafig{inserer2}{133mm}{33mm}{700}{}

\pagebreak


\titre{Recherche d'un {\'e}l{\'e}ment}

\begin{verbatim}
static boolean recherche(int x, Liste p) {
  if (p == null)
    return false;
  else if (p.contenu == x)
    return true;
  else
    return recherche (x, p.suivant);
}
\end{verbatim}
ou it\'erativement:
 \begin{verbatim}
static boolean rechercheIter (int x, Liste p) {
  while (p != null) {
    if (p.contenu == x)
      return true;
    p = p.suivant;
  }
  return false;
}
\end{verbatim}



\pagebreak

\titre{ Suppression d'un {\'e}l{\'e}ment}

\begin{verbatim}
static Liste supprimer(int x, Liste a) {

  if (a != null) 
    if (a.contenu == x) 
      return a.suivant;
    else 
      a.suivant= supprimer (x, a.suivant);
  return a;
}
\end{verbatim}
\pagebreak




\begin{center}
{\huge \bf Variantes}
\end{center}

1. Liste avec cellule vide en t\^ete: {\'e}vite de traiter de fa\c{c}on
sp{\'e}ciale l'insertion et la suppression en t\^ete.
\begin{figure}[hbt]
%\scalebox{0.7}{\includegraphics{listetete}}
\end{figure}

2. Liste doublement cha{\^\i}n{\'e}e.
\begin{figure}[hbt]
\scalebox{0.7}{\includegraphics{listed}}
\end{figure}

Possibilit{\'e} de cha{\^\i}nage circulaire.

\pagebreak


\begin{center}
{\huge \bf Piles}
\end{center}
Liste avec acc\`es restreint utilis{\'e}e dans de tr\`es nombreux algorithmes.
On ins\`ere et supprime toujours du m\^eme c\^ot{\'e} (lifo). La t\^ete
s'appelle traditionnellement le {\em sommet} de pile.
Op{\'e}rations de base:
\begin{itemize}
\item {\tt Empiler(x,S)}: ajoute $x$ en sommet de pile.
\item {\tt Depiler(S)}: supprime le sommet de pile.
\end{itemize}
\Lafig{pile}{77mm}{100mm}{600}{}
Impl{\'e}mentation usuelle en tableau.
\pagebreak



\begin{center}
{\huge \bf Files}
\end{center}
Cette fois on ins\`ere d'un c\^ot{\'e} (la {\em queue}) et on supprime
toujours de l'autre (la {\em t\^ete}): strat{\'e}gie {\it fifo}.

Impl{\'e}mentation possible: Dans un tableau avec gestion circulaire des
indices.
\begin{figure}[hbt]
\scalebox{0.7}{\includegraphics{file}}
\end{figure}


\noindent File vide:

{\tt queue = tete mod N}

\noindent File pleine:
 
{\tt tete = queue + 1 mod N}
 
 

\end{document}