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

\begin{exointro}{\null}
\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{Exemples de définitions et de manipulations de listes}:

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

\Par

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



\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}

\vspace*{-1mm}
\nathanlive{video}{Retrouvez une explication des piles et des files en vidéo avec Nathan Live.}
\label{video:ch1}

\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}.

\enlargethispage*{5em}

\vspace*{-2mm}
\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}

\subsubsection{Les piles en Python}

On peut implémenter une pile à l'aide d'une liste.
\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). À noter que \texttt{p.pop(n)} supprime l'élément d'indice \texttt{n}.\index{Python!pop() [pile]}
\end{itemize}

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

\subsection{Les files}

\subsubsection{Définition}

\begin{defin}
Une \textit{file} est une liste remplie sur le principe du \og premier arrivé, premier sorti \fg, abrégé en \textit{FIFO}, de l'anglais \og First In, First Out \fg.

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}

\Par\enlargethispage*{4em}

\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.
\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. 

\index{Python!deque}
C'est la raison pour laquelle on pourra utiliser la fonction \texttt{deque} du module \texttt{collections}. La syntaxe de cette fonction est :
\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{} défile l'élément défilé, ce qui n'est pas le cas dans un programme. 
\end{itemize}

\begin{Exemple}

\nathanlive{progmargin}{}
\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}

\textit{Voir exercices 1 à 12.}

\newpage
\section{Packing et unpacking explicite en Python}
\index{Packing}
\index{Unpacking}


\subsection{Introduction}

Nous avons vu en classe de 1\iere{} que la syntaxe suivante :

\Par

\texttt{a , b = 3 , -2}

\Par

permet de définir un tuple. C'est ce que l'on appelle l'\textit{unpacking} implicite.

De même, quand on écrit :

\Par


\texttt{L = [15 , 48]}

\Par

on définit une liste; c'est ce que l'on appelle le \textit{packing implicite}.

\Par

Dans certaines situations, des fonctions qui admettent par exemple deux\linebreak paramètres doivent être appelées à partir d'une liste. 

Dans d'autres cas, il est utile de créer une fonction dont le nombre de paramètres peut être variable. 

Fort heureusement, il existe des solutions simples pour cela.

\subsection{L'unpacking explicite}

Considérons l'exemple basique d'une fonction permettant de calculer la longueur entre deux points $A(x_A;y_A)$ et $B(x_B;y_B)$ dans un repère.

\begin{listing}{}{01-07.py}\end{listing}

\Par

Cette syntaxe est assez pratique car elle est lisible et donc compréhensible assez facilement:

\begin{itemize}
\item on commence par définir deux points $A$ et $B$ à l'aide de leurs coordonnées, donc à l'aide de deux tuples;
\item ensuite, on fait appel à la fonction \texttt{longueur}, qui admet quatre paramètres. Mais comme \texttt{A} et \texttt{B} ne sont que deux variables, on transforme chacune d'elles en deux paramètres à l'aide de l'opérateur \textit{splat} (\og \texttt{*} \fg). 

C'est l'\textit{unpacking} (en français, le \og déballage \fg) explicite.
\end{itemize}

\newpage

L'unpacking explicite peut s'appliquer aux tuples comme aux listes.  Il peut aussi être utilisé sur les dictionnaires, mais avec une syntaxe légèrement différente :

\begin{listing}{}{01-08.py}\end{listing}

\Par

On transforme ici les valeurs successives en paramètres. 

À noter toutefois que les clés du dictionnaire doivent avoir le même nom que les paramètres de la fonction.

Ainsi,

\begin{center}
\texttt{points = \{ 'a' : -2 , 'b' : 5 , 'c' : 7 , 'd' : 3 \}}
\end{center}

ne fonctionne pas.

\subsection{Le packing explicite}

Nous pouvons nous en douter, le \textit{packing} (en français, l'\og emballage \fg)  explicite est l'inverse de l'unpacking explicite.

Il est très utile dès lors que l'on écrit une fonction dont le nombre d'arguments est inconnu.

Par exemple, pour afficher un polynôme en fonction de ses coefficients, du terme de degré 0 vers le terme de plus haut degré, on pourra utiliser le programme\linebreak suivant :

\nathanlive{progmargin}{} % 01-09.py
\begin{listing}{}{01-09-1.txt}\end{listing}
\Par

\begin{center}
\textit{(suite du programme page ci-contre)}
\end{center}

\newpage

\begin{listing}{}{01-09-2.txt}\end{listing}

\Par

Ce programme affiche ici:

\Par
\begin{center}
{\ttfamily-1-2x\verb+^+2}
\end{center}

\Par

Si nous souhaitons manipuler non pas une liste mais un dictionnaire dans la\linebreak fonction, nous devrons alors utiliser le double \textit{splat}.

\nathanlive{progmargin}{}
\begin{listing}{}{01-10.py}\end{listing}

\Par

Ce programme affiche :

\Par

{\ttfamily
Le coefficient du terme de degré 0 est : -9\\
Le coefficient du terme de degré 1 est : 2\\
Le coefficient du terme de degré 2 est : 5
}

\begin{Remarque}
il est commun de voir \texttt{*args} et \texttt{**kwargs} dans de nombreux\linebreak programmes. Ce n'est pas une obligation (comme nous venons de le voir) mais plutôt une habitude.
\end{Remarque}

\textit{Voir exercices 13 à 17.}

\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 :

\Par

\texttt{\pychevrons P.append(7)}

\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 :

\Par

\texttt{\pychevrons P.pop()}

\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:

\Par

\texttt{\pychevrons P[-2] , P[-1]}

\begin{Remarque}
en ligne de commande, inutile de mettre \og \texttt{print} \fg.
\end{Remarque}
\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
\pychevrons F = deque()

\pychevrons for i in [2,7,3]:

\pychevrons ... 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}
