\chapter{Structures indexées\\et dynamiques}

\begin{exointro}{Lycée François Mauriac, Bordeaux}
\begin{questions}
\item En Python, on considère une pile \texttt{P}.
\begin{questions}
\item Quelle instruction permet d'empiler la valeur \og 7 \fg{} dans \texttt{P} ?
\item Quelle instruction permet de dépiler \texttt{P} ?
\item Quelle instruction permet d'afficher les deux éléments au sommet de la pile sans les défiler ?
\end{questions}

\item En Python, on considère une file \texttt{F}.
\begin{questions}
\item Quelle(s) instruction(s) permet(tent) d'enfiler successivement les valeurs \og 2 \fg, \og 7 \fg{} et \og 3 \fg{} dans \texttt{F} ?
\item Quelle instruction permet de défiler \texttt{F} ?
\item Quelle instruction permet d'afficher l'élément en tête de file sans le dépiler ?
\end{questions}
\end{questions}
\end{exointro}

\section{Structures indexées}
\enlargethispage*{\baselineskip}

\subsection{Notion de structure}

À l'heure du \textit{big data},  les quantités de données à traiter en informatique sont de plus en plus importantes. Le traitement de ces données (\textit{data} en anglais)  nécessite donc une organisation structurée et efficace. Plus les données seront structurées, plus leur traitement sera simple, et plus le risque d'erreur sera limité.

\begin{Exemple}
un agenda contenant des personnes identifiées par leurs noms, prénoms, date de naissance adresse et numéro de téléphone est une structure de données.
\end{Exemple}

\begin{defin}
Une \textit{structure de données} est une manière d'organiser des données afin de\linebreak pouvoir les traiter de façon simplifiée.
\end{defin}

\subsection{Structures indexées}

\subsubsection{Tableaux}
\index{Structures de données!Tableaux}

\vspace*{-3mm}
\begin{defin}
Un \textit{tableau} est une structure de données représentant une séquence finie\linebreak d'éléments auxquels on peut accéder par leur position dans la séquence, appelée \textit{indice}.
\end{defin}

L'indexation d'un tableau de $n$ éléments commence à 0 (premier élément) et se termine à $n-1$ (dernier élément).

\vspace*{-2mm}
\begin{Exemple}~\par
En Python, on peut définir un tableau de 5 entiers de la manière suivante :
\begin{center}
\ttfamily
tab = [ 7 , 12 , 45 , 0 , 12 ]
\end{center}
\end{Exemple}

Ceci est un tableau unidimensionnel. Il existe aussi des tableaux multidimensionnels \textbf{dont chaque élément est lui-même un tableau}.

\vspace*{-2mm}
\begin{Exemple} la matrice:
\[
\begin{pmatrix}
1 & 0 & 3\\
5 & -2 & 8
\end{pmatrix}
\]
peut-être représentée en Python par le tableau suivant:

\Par

{
\ttfamily
tab  = [

\hspace*{1.2cm} [ 1 , 0 , 3 ]

\hspace*{1.2cm}  [ 5 , -2 , 8 ]

\hspace*{.8cm} ]
}

\Par

Ici, \texttt{tab} est un tableau dans lequel chaque élément est un tableau de trois entiers.
\end{Exemple}

Un tableau se caractérise par:
\begin{itemize}
\item le type des éléments qu'il contient (entiers, caractères, tableaux,...);
\item le nombre d'éléments qu'il contient (sa \textit{taille}).
\end{itemize}
\enlargethispage*{5em}

\vspace*{-2mm}
\begin{Exemple}
dans cet exemple écrit en C, impossible de définir \texttt{tab[3]} car la taille du tableau a été fixée à 3 éléments uniquement.

\begin{listing}[language=C]{}{01-01.c}\end{listing}
\end{Exemple}


\newpage
\subsubsection{Les dictionnaires}
\index{Structures de données!Dictionnaires}

\begin{defin}
Un \textit{dictionnaire}, aussi appelé \textit{tableau associatif}, est une structure de données dans laquelle des \textit{clés} sont associées à des \textit{valeurs}.
\end{defin}

\begin{Remarque}
en mathématiques, l'équivalent du dictionnaire est une \textit{application}, qui associe à chaque valeur de la variable une autre valeur.
\end{Remarque}

\begin{Exemple}
\begin{listing}{En Python}{01-02.py}
\end{listing}
\index{Python!format}

\Par

Ce programme affiche:
\Par
{\ttfamily
La capitale de la France est Paris.\\
La capitale de l'Angleterre est Londres.\\
La capitale de l'Allemagne est Berlin.
}
\end{Exemple}

\vspace*{-2mm}
\section{Structures dynamiques}

\subsection{Listes}
\index{Structures de données!Listes}

\begin{defin}
Une \textit{liste} est une structure de données regroupant des éléments ordonnés qu'il est possible de manipuler individuellement (accès, ajout, suppression et modification).
\end{defin}

\enlargethispage*{5em}

\textit{Un exemple de définition et de manipulation de listes}:

\begin{listing}{En Python}{01-04.py}
\end{listing}

\newpage

\begin{Remarques}
\begin{itemize}
\item La taille d'un tableau est statique, contrairement à celle d'une liste.
\item Le langage Python permet de confondre les deux notions car la notion de tableau n'est pas à proprement parler implémentée dans ce langage. Ainsi, quand on programme en Python, on parlera de tableaux ou de listes indifféremment.
\end{itemize}
\end{Remarques}


\subsection{Les piles}

\NathanLiveVideo[\PictoVideo\ Retrouvez une explication des piles et des files en vidéo.]{piles et files}{https://media.prepamath.fr/ILTNSIch01crs01}

\qrset{height=1.1cm,version=5}\rput(-1,0.3){
\psframebox{\qrcode{https://media.prepamath.fr/ILTNSIch01crs01}}}
\vspace*{-10pt}

\subsubsection{Définition}
\index{Structures de données!Piles}

\vspace*{-3mm}
\begin{defin}
Une \textit{pile} est une liste remplie sur le principe du \og dernier arrivé, premier sorti \fg, abrégé en \textit{LIFO}, de l'anglais \og Last In, First Out \fg.
\end{defin}
\begin{figure}
\begin{center}
\includegraphics{004_01-crs-pile}
\figcaption{Illustration d'une pile}
\end{center}
\end{figure}

\Par

Quand on ajoute un élément à une pile, on dit que l'on \textit{empile}; quand on retire un élément d'une liste, on dit que l'on \textit{dépile}.

\begin{Exemples}
\begin{itemize}
\item Dans un navigateur web, une pile sert à mémoriser les dernières pages visitées : la première à apparaître est la dernière à avoir été visitée (accessible en cliquant sur l'icône \og Page précédente \fg{} par exemple).

\item Dans un traitement de texte, la combinaison de touches \og [Ctrl] + [Z] \fg{} annule la dernière action : cela repose sur le fait que les actions sont empilées.
\end{itemize}
\end{Exemples}

\newpage

\subsubsection{Les piles en Python}

Dans les langages de programmation, il existe souvent de multiples moyens de représenter une même structure de données. Ainsi, en Python, on peut par exemple implémenter une pile à l’aide d’une liste dont le début représente le bas de la pile et la fin le sommet de celle-ci.
\begin{itemize}
\item \texttt{p.append(v)} ajoute \texttt{v} au sommet de la pile (à la fin de la liste);
\item \texttt{p[-1]} est l'élément au sommet de la pile (c'est le dernier élément de la liste);
\item \texttt{p.pop()} retire l'élément au sommet de la pile (le dernier élément de la liste). index{Python!pop() [pile]}
\end{itemize}

\begin{Exemple}
\begin{listing}{}{01-05.py}\end{listing}
\end{Exemple}

\enlargethispage*{5em}
\subsection{Les files}

\subsubsection{Définition}

\begin{defin}
Une \textit{file} est une suite ordonnée d’éléments remplie sur le principe du « premier arrivé, premier sorti », abrégé en \textit{FIFO}, de l’anglais « First In, First Out ».

Quand on ajoute un élément à une file, on dit que l’on \textit{enfile}; quand on retire un élément d’une file, on dit que l’on \textit{défile}.
\end{defin}
\begin{figure}
\begin{center}
\includegraphics{005_01-crs-file}
\figcaption{Illustration d'une file}
\end{center}
\end{figure}


\begin{Exemple}
lorsque l’on imprime plusieurs documents, les requêtes d’impression
sont traitées selon une file. C’est le même principe qu’une caisse au supermarché.
\end{Exemple}

\subsubsection{Les files en Python}

Les listes sont mal adaptées pour représenter en Python des files car l'ajout d'élément se fait toujours en fin de liste, et non en début. 


C’est la raison pour laquelle on pourra utiliser la structure de donnée \texttt{deque} (\textit{double ended queue}) du module \texttt{collections}, que l’on pourra construire ainsi :
\begin{center}
\texttt{file = deque([ liste de nombres séparés par des virgules ])}\\
ou: \texttt{file = deque((liste de nombres séparés par des virgules))}
\end{center}
Ainsi,
\begin{center}
\ttfamily
file = deque( (3,2,1) )
\end{center}
représente la file dont le premier élément (la tête de file) est \og 1 \fg{} et dont le dernier élément enfilé est \og 3 \fg.

On utilisera alors:
\begin{itemize}
\item \texttt{file.appendleft(élément)} pour enfiler un élément;
\item \texttt{file.pop()} pour défiler la tête de file. À noter toutefois qu'en mode console, écrire \og \texttt{f.pop()} \fg{} affiche l'élément défilé, ce qui n'est pas le cas dans un programme. 
\end{itemize}

\begin{Exemple}
\begin{listing}{}{01-06.py}
\end{listing}
\index{Python!appendleft}
\index{Python!pop() [file]}
\end{Exemple}

\enlargethispage*{5em}

\begin{aretenir}
\begin{center}
\begin{tabular}{|>{\centering\arraybackslash}M{25mm}|Z{m{75mm}}|}
\hline
Tableaux & Séquence finie et de taille fixe d'éléments auxquels on peut accéder par leur indice.\\
\hline
Dictionnaires & Association dynamique de paires clé/valeur.\\
\hline
Liste & Groupe d'éléments ordonnés que l'on peut manipuler individuellement.\\
\hline
Pile & Liste remplie sur le principe \og dernier arrivé, premier sorti \fg (LIFO).\\
\hline
File & Liste remplie sur le principe \og premier arrivé, premier sorti \fg{} (FIFO).\\
\hline
\end{tabular}
\end{center}
\end{aretenir}


\newpage


\begin{solintro}
\begin{questions}
\item En Python une pile est représentée par une liste.
\begin{questions}
\item Empiler une valeur revient à ajouter cette valeur à la fin de la liste.

L'instruction qui permet d'empiler la valeur \og 7 \fg{} dans \texttt{P}  est alors :
\begin{center}
\texttt{P.append(7)}
\end{center}

\item Dépiler \texttt{P} revient à enlever la dernière valeur de la liste.

Ainsi, l'instruction qui permet de dépiler \texttt{P} est :
\begin{center}
\texttt{P.pop()}
\end{center}

\item Les deux éléments au sommet de la pile sont les deux derniers éléments de la liste. 

Ainsi, l'instruction qui permet d'afficher d'abord le 2\ieme{} puis le 1\ier{} est:
\begin{center}
\texttt{P[-2] , P[-1]}
\end{center}
\end{questions}

\item En Python, une file \texttt{F} est aussi représentée par une liste.
\begin{questions}
\item Pour enfiler une valeur dans \texttt{F}, on peut utiliser \texttt{deque} du module \texttt{collections}.

Dans ce cas, on pourra utiliser les instructions suivantes:

\Par

{\ttfamily
F = deque()

for i in [2,7,3]:

\qquad F.appendleft(i)

}

\Par

À ce stade, \texttt{F = deque([3, 7, 2])}.

\item Défiler \texttt{F} signifie enlever l'élément \og le plus ancien \fg{} de la file, à savoir ici \og 2 \fg.

Il s'agit du dernier élément de l'objet \texttt{F} (on ne peut pas réellement dire ici que \texttt{F} est une liste car quand on affiche \texttt{F}, ce n'est pas exactement une liste que l'on voit).

Ainsi, pour défiler, on utilise l'instruction :

\Par

\texttt{\pychevrons F.pop()}

\item Comme pour la pile, l'instruction qui permet de connaître ou de retrouver l'élément en tête de la file \texttt{F} est :

\Par

\texttt{\pychevrons F[-1]}
\end{questions}
\end{questions}
\end{solintro}
