linear-struct-fr.tex

\documentclass[12pt]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[frenchb]{babel}
\usepackage{listings}
\usepackage{tabu}
\usepackage{booktabs}

\beamertemplatenavigationsymbolsempty
\AtBeginSection[]
{
    \begin{frame}
    \frametitle{Table des matières}
    \tableofcontents[currentsection]
    \end{frame}
}
\newcommand{\gray}{\textcolor{gray}}
\newcommand{\bigoh}[1]{\mathcal{O}\left(#1\right)}
\newcommand{\constant}{\bigoh{1}}
\newcommand{\linear}{\bigoh{n}}

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
  basicstyle=\tiny,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  commentstyle=\color{mygreen},    % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
  keywordstyle=\color{blue},       % keyword style
  language=C++,                 % the language of the code
  morekeywords={*,...},            % if you want to add more keywords to the set
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{mymauve},     % string literal style
  tabsize=2                      % sets default tabsize to 2 spaces
}

\title{Structures de données linéaires}
\subtitle{Tableaux, vecteurs, listes chaînées}
\author{Training beOI}
\institute{\includegraphics[height=12em]{../share/beoi-logo}}

\begin{document}

\frame{\titlepage}

\section{Tableaux et variantes}

\begin{frame}[fragile]
\frametitle{Tableau}
\begin{lstlisting}
#define MAX_N 10000
int tab[MAX_N];

int main() {
    tab[1234] = 100;
    tab[1234]; // 100
    tab[5678]; // 0
}
\end{lstlisting}
\begin{itemize}
\item Taille fixée à la compilation
\item Accès à un élément arbitraire: $\constant$
\item Astuce : en-dehors d'une fonction, initialisé à zéro
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Bitset}
C++ : \texttt{bitset} \\
Java : \texttt{BitSet}
\begin{lstlisting}
bitset<MAX_N> tab; // bool tab[MAX_N];
tab[1234] = true;

bitset<4> b1(string("1100")),
          b2(string("0101"));
b1 | b2; // 1101
b1 & b2; // 0100
b1 >> 1; // 0110
\end{lstlisting}
\begin{itemize}
\item Comme un tableau de booléens
\item 8x plus compact
\item Opérations bit-à-bit 64x plus rapides
\item Voir manuel pour la liste des opérations
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Tableau dynamique: fonctionnement}
{\setlength{\parskip}{.9em}
Si plus de place, multiplier par 2

\def\arraystretch{1.3}

\begin{tabu} to .175\textwidth {|X[c]|X[c]|}
\hline
1 & \\
\hline
\end{tabu}
\hfill Capacité = 2

\begin{tabu} to .175\textwidth {|X[c]|X[c]|}
\hline
1 & 2 \\
\hline
\end{tabu}

\begin{tabu} to .35\textwidth {|X[c]|X[c]|X[c]|X[c]|}
\hline
1 & 2 & 3 & \\
\hline
\end{tabu}
\hfill Capacité = 4

\begin{tabu} to .35\textwidth {|X[c]|X[c]|X[c]|X[c]|}
\hline
1 & 2 & 3 & 4 \\
\hline
\end{tabu}

\begin{tabu} to .7\textwidth {|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|X[c]|}
\hline
1 & 2 & 3 & 4 & 5 & & & \\
\hline
\end{tabu}
\hfill Capacité = 8} %\setlength
\end{frame}

\begin{frame}[fragile]
\frametitle{Tableau dynamique : en pratique}
C++ : \texttt{vector} \\
Java : \texttt{ArrayList<E>}

\begin{lstlisting}
vector<int> vec(8, -1); // initialize to -1
vec[5] += vec[2];       // -2
vec.push_back(5);
vec.push_back(19);
vec.pop_back();
vec.back();             // 5
\end{lstlisting}
\begin{itemize}
\item Taille augmente et diminue
\item Accès à un élément arbitraire: $\constant$
\item Ajout/suppression d'un élément \textbf{à la fin}: $\constant$
\item Ajout/suppression autre part: $\linear$
\end{itemize}
\end{frame}

\section{Listes chaînées}

\begin{frame}[fragile]
\frametitle{Liste chaînée: concept}
Des nœuds reliés par des liens (pointeurs)
\begin{figure}
\centering
\includegraphics[width=.8\textwidth]{img/singly-linked}
\end{figure}
\begin{itemize}
\item Chaque nœud sait où est le prochain
\item Les nœuds ne sont plus côte à côte
\end{itemize}
\begin{lstlisting}
struct Node {
    int value;
    Node *next; // link (pointer)
};
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Liste chaînée: parcours}
Commencer au premier nœud et suivre les liens
\begin{figure}
\centering
\includegraphics[width=.6\textwidth]{img/singly-linked}
\end{figure}
Dans le dernier nœud le lien vaut NULL:
\begin{lstlisting}
Node *cur = start;   // always keep the first node!
while (cur != NULL) {
    cur->value;      // access value
    cur = cur->next; // switch pointer to next
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Liste chaînée: ajout}
Seulement deux liens à changer
\begin{figure}
\centering
\includegraphics[width=.9\textwidth]{img/insert-node}
\end{figure}
\begin{lstlisting}
void insertAfter(Node *node, Node *new_node) {
    new_node->next = node->next;
    node->next = new_node;
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Liste chaînée : suppression}
Changer le lien et supprimer
\begin{figure}
\centering
\includegraphics[width=.6\textwidth]{img/remove-node}
\end{figure}
\begin{lstlisting}
void removeAfter(Node *node) {
    Node *toRemove = node->next;
    node->next = node->next->next; // bypass
    delete toRemove;
}
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Liste chaînée : limitations}
\begin{figure}
\centering
\includegraphics[width=.8\textwidth]{img/singly-linked}
\end{figure}
Avec une liste (simplement) chaînée :
\begin{itemize}
\item Ajout/suppression au début: $\constant$
\item Ajout/suppression à une position \textbf{donnée}: $\constant$
\end{itemize}
Si on retient la fin aussi :
\begin{itemize}
\item Ajout à la fin: $\constant$
\item Suppression à la fin: pas possible, $\linear$
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Liste doublement chaînée}
Des liens dans les deux sens!
\begin{figure}
\centering
\includegraphics[width=.8\textwidth]{img/doubly-linked}
\end{figure}
\begin{itemize}
\item Parcours dans les deux sens
\item Suppression à la fin en $\constant$
\item Un peu plus lourd
\end{itemize}
\begin{lstlisting}
struct Node {
    int value;
    Node *prev, *next; // two pointers
};
\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Listes chaînée: en pratique}
C++ : \texttt{list} \\
Java : \texttt{LinkedList<E>}
\begin{lstlisting}
list<int> l;
list<int>::iterator it;

l.push_back(3);  // 3
it = l.begin();  // ^ points to 3
l.push_back(4);  // 3 4
l.push_front(1); // 1 3 4
l.insert(it, 2); // 1 2 3 4 (inserts before 3)
l.pop_front();   // 2 3 4
l.pop_back();    // 2 3
\end{lstlisting}
\begin{itemize}
\item Les \texttt{list<>} sont doublement chaînées
\item Retenir les positions avec des \texttt{iterator}
\item Tout en $\constant$
\end{itemize}
\end{frame}

\section{File et pile}

\begin{frame}
\frametitle{File : concept}
\begin{itemize}
\item Faire la file dans un magasin
\item On ajoute à la fin, on enlève au début
\item Premier arrivé premier servi (First In First Out)
\end{itemize}
\begin{figure}
\centering
\includegraphics[width=.6\textwidth]{img/queue}
\end{figure}
\end{frame}

\begin{frame}[fragile]
\frametitle{File : en pratique}
C++ : \texttt{queue} \\
Java : \texttt{Queue<E>}
\begin{itemize}
\item Ajouter à la fin, enlever au début $\Rightarrow$ liste chaînée
\item Tout en $\constant$
\end{itemize}
\begin{lstlisting}
queue<int> q;
q.push(1);
q.push(2);
q.front(); // 1
q.pop();
q.front(); // 2
\end{lstlisting}
\end{frame}

\begin{frame}
\frametitle{Pile : concept}
\begin{itemize}
\item Pile de crêpes
\item On ajoute au-dessus, on enlève au-dessus
\item Dernière cuite première mangée (Last In First Out)
\end{itemize}
\begin{figure}
\centering
\includegraphics[width=.5\textwidth]{img/stack}
\end{figure}
\end{frame}

\begin{frame}[fragile]
\frametitle{Pile : en pratique}
C++ : \texttt{stack} \\
Java : \texttt{Stack<E>}
\begin{itemize}
\item Ajouter et enlever à la fin $\Rightarrow$ liste chaînée \emph{ou vecteur}
\item Tout en $\constant$
\end{itemize}
\begin{lstlisting}
stack<int> q;
q.push(1);
q.push(2);
q.top(); // 2
q.pop();
q.top(); // 1
\end{lstlisting}
\end{frame}

\section{Choisir la bonne structure}

\begin{frame}
\frametitle{Choix: structures spéciales}
Structures pour besoins spéciaux:
\begin{itemize}
\item Ajoute d'un côté et on enlève de l'autre $\Rightarrow$ \textbf{file}
\item Enlève et ajoute d'un même côté $\Rightarrow$ \textbf{pile}
\item Booléens, opérations spéciales (et, ou, shift, ...) $\Rightarrow$ \textbf{bitset}
\end{itemize}

~

Sinon, voir slide suivante!
\end{frame}

\begin{frame}
\frametitle{Choix: tableaux, vecteurs, listes chaînées}
``Ajout'' = ajout ou suppression
\begin{center}
\begin{tabu}{l|cccc}
\toprule
Structure & Indexation & Ajout fin & Ajout milieu \\
\midrule
Tableau & $\constant$ & $\linear$ & $\linear$ \\
Vecteur & $\constant$ & $\constant$ & $\linear$ \\
Liste chaînée & $\linear$ & $\constant$ & $\constant$ \\
\bottomrule
\end{tabu}
\end{center}
\begin{itemize}
\item Ajout au milieu nécessaire (rare) $\Rightarrow$ \textbf{liste chaînée}
\item Taille maximale inconnue $\Rightarrow$ \textbf{vecteur}
\item Tous les autres cas $\Rightarrow$ \textbf{tableau} (plus rapide)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Source des figures}
\begin{itemize}
\item \url{https://commons.wikimedia.org/wiki/File:Singly-linked-list.svg}
\item \url{https://commons.wikimedia.org/wiki/File:CPT-LinkedLists-addingnode.svg}
\item \url{https://en.wikipedia.org/wiki/File:CPT-LinkedLists-deletingnode.svg}
\item \url{https://en.wikipedia.org/wiki/File:Doubly-linked-list.svg}
\item \url{https://en.wikipedia.org/wiki/File:Data_Queue.svg}
\item \url{https://en.wikipedia.org/wiki/File:Data_stack.svg}
\end{itemize}
\end{frame}

\end{document}