\documentstyle[12pt,psfig,twoside]{article}
%
%
% Depth for table of contents
%
\setcounter{secnumdepth}{4}
%\setcounter{tocdepth}{4}
%
% definitions
%
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{-0.10in}
\setlength{\topmargin}{-0.10in}
\setlength{\headsep}{1.5cm}
\setlength{\textwidth}{15.cm}
\setlength{\textheight}{21.cm}
\parindent=7mm
\title{TP Pascal $n^{o}$ 8 : Les listes lin\'eaires chain\'ees}
\date{}
\begin{document}
\maketitle
\section{Rappels}
Variables de type pointeur, repr\'esentation d'une cellule, gestion
dynamique de la m\'emoire et d\'efinition d'une liste chain\'ee.
On donne~:
\begin{verbatim}
        type
            ptr=^cellule;
            cellule=record
                    info : integer;
                    suivant : ptr;
            end;
\end{verbatim}

\section{Cr\'eation d'une liste}
A partir de l'entr\'ee au clavier d'une suite S d'entiers naturels
$n_1$, $n_2$, \dots, $n_p$, (arr\^et lors de l'entr\'ee d'un nombre
strictement n\'egatif), la proc\'edure EntreeListe (voir ci-dessous)
cr\'ee la liste L o\`u les \'el\'ements de S sont rang\'es dans 
l'ordre~: $n_1$, $n_2$, \dots, $n_p$. Expliquer.
\begin{verbatim}
       procedure EntreeListe (var liste : ptr);
       var 
          p, dernier : ptr;
          n : integer;
       begin
          readln(n);
          if n < 0 then liste := nil
          else begin
               new(liste); liste^.info := n; liste^.suivant:=nil;
               dernier := liste; readln(n);
               while n>=0 do begin 
                     new(p); p^.info:=n; p^.suivant:=nil; 
                     dernier^.suivant := p;
                     dernier := p; readln(n);
               end;
          end;
       end;
\end{verbatim}

\section{Parcours d'une liste}
Afficher les \'el\'ements de la liste L.

\section{Exemples d'algorithmes sur les listes}
\begin{itemize}
\item calcul de la longueur d'une liste,
\item calcul du nombre d'occurences d'un \'el\'ement dans une liste,
\item acc\`es au $k^{ieme}$ \'el\'ement d'une liste,
\item acc\`es \`a la premi\`ere occurence de {\tt val} dans une liste.
\end{itemize} 

\section{Algorithmes de mise \`a jour dans une liste}
\begin{itemize}
\item insertion d'un \'el\'ement en t\^ete de liste,
\item insertion d'un \'el\'ement en fin de liste,
\item insertion d'un \'el\'ement en $k^{ieme}$ position,
\item suppression du premier \'el\'ement,
\item suppression du $k^{ieme}$ \'el\'ement.
\end{itemize}

\section{Autres exemples d'algorithmes}
\begin{itemize}
\item concat\'enation de deux listes,
\item cr\'eation de la liste miroir.
\end{itemize} 
 
\end{document}


