C8 Structures de données séquentielles ¶

"Smart data structures and dumb code works a lot better than the other way around."
Eric Raymond
(in The Cathedral and the Bazaar, 1999)

Cours¶

Support de cours chapitre 8

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés¶

Fiche de TD8

Travaux pratiques¶

Exercice 1 : Listes chainées en C¶

On reprend l'implémentation vue en cours pour les listes simplement chaînées en C :

        struct maillon_s
        {
            int valeur;
            struct maillon_s * suivant;
        };
        typedef struct maillon_s maillon;
        typedef maillon* liste;

On définit donc ici une liste comme un pointeur vers le maillon de tête, ainsi une liste vide correspond au pointeur NULL.

Ecrire les fonctions suivante :
1. cree_liste de signature liste cree_liste() qui renvoie la liste vide.
2. affiche de signature affiche(liste l) qui affiche les éléments de la liste l.
3. ajoute de signature void ajoute(liste *l, int val) qui ajoute en tête de liste la valeur val.
  Aide
  - On notera bien que cela modifie la liste passée en paramètre et que donc on utilise un pointeur vers cette liste.
  - Comme souvent, lorsqu'on programme en utilisant les listes chainées, le crayon et le papier sont ici des alliés de poids. On recommande vivement de schématiser rapidement les opérations effectuées par ajoute (voir cours).
4. supprime de signature supprime(list *l) qui supprime l'élément situé en tête de la liste.
5. detruit qui libère entièrement l'espace mémoire alloué aux maillons d'une liste.
Tester vos fonctions en créant puis en affichant la liste des 10 premiers entiers
Implémenter d'autres fonctions sur votre structure de données (taille, accès au n-ième élément, somme des éléments, \(\dots\)).
Vérifier l'absence de fuites mémoires.
Reprendre cette exercice en créant un type de liste doublement chaînées (vers le suivant et vers le précédent) appelé deque (pour double ended queue) dans lequel on conserve un accès vers la tête de la liste (afin de pouvoir ajouter ou retirer un élément "à gauche" comme dans une liste chainée "traditionnelle") mais aussi un accès vers le dernier élément de la liste afin de pouvoir ajouter ou retirer un élément "à droite" de la liste en temps constant.

Exercice 2 : Implémentation avec maillon fantôme¶

Une implémentation alternative des listes chainées consiste à utiliser un maillon de tête toujours vide, on parle alors de maillon fantôme ou maillon sentinelle (dummy head en anglais). Par rapport à l'implémentation vue en cours (et traité dans l'exercice précédent), on n'a plus besoin de traiter le cas particulier de la liste vide dans les fonctions (une liste n'est jamais NULL, elle possède au moins le maillon fantôme). Le passage d'un pointeur sur un pointeur de maillon (même si cela a été masqué avec le type list dans l'implémentation précédente) n'est plus utilisé, cette implémentation est donc parfois considérée comme plus facile.

On a représenté ci-dessous la liste contenant les valeurs 5, 7, 4 avec cette implémentation, la valeur du maillon fantôme n'étant pas utilisée, on l'a représenté avec @.

    graph LR
    classDef dashed stroke-dasharray:5 5,stroke:#333,fill:#eef,rx:5px,ry:5px;
    classDef null stroke:#FFFFFF, fill:#FFFFFF
    A["@"] --> B["5"] --> C["7"] --> D["4"] --> E["NULL"]
    class A dashed;
    class E null;

Pour mettre en oeuvre cette implémentation, on propose le type structuré suivant :

struct list_s
{
    int value;
    struct list_s * next;
};
typedef struct list_s list;

Note

Remarquez bien la différence avec l'implémentation précédente, une liste est maintenant un maillon et non plus un pointeur vers un maillon.

Ecrire la fonction de signature list make_list() qui renvoie une liste vide.
Ecrire la fonction de signature void add(list *l, int v) qui ajoute une valeur v en tête de liste (donc après le maillon fantome)
Ecrire la fonction de signature void view(list l) permettant d'afficher une liste puis tester votre implémentation.
Ecrire la fonction de signature int del(list *l) qui supprime le maillon suivant le maillon fantome et renvoie sa valeur.
On propose maintenant d'utiliser le maillon de tête afin d'y stocker la taille de la liste. Modifier en conséquence les fonctions précédentes et écrire la fonction de signature int size(list l) qui renvoie le nombre d'éléments de la liste.

Exercice 3 : Des listes d'entiers en OCaml¶

En OCaml, on considère le type somme suivant afin de représenter des listes d'entiers :

    type intlist =
    | Vide
    | TeteQueue of int * intlist;;

C'est à dire qu'une liste d'entier est soit vide, soit formé d'un couple (tete, queue) où tete est un entier et queue une liste d'entiers.

Ecrire une fonction ajoute : int -> intlist -> intlist qui ajoute un entier en tête d'une intlist.
Ecrire une fonction aleatoire : int -> int -> int -> intlist qui prend en argument trois entiers n, vmin et vmax et renvoie une intlist de n entiers compris entre vmin et vmax.
Ecrire une fonction affiche : intlist -> unit qui affiche les éléments d'une intlist
Ecrire une fonction longueur : intlist -> int qui renvoie le nombre d'élements d'une intlist
Ecrire une fonction enleve : intlist -> intlist qui supprime le premier élément d'une intlist, on traitera le cas de la liste vide avec un failwith
Ecrire une fonction partitionne : intlist -> (int -> bool) -> int list * intlist qui partitionne une intlist suivant le prédicat fourni en argument.

Exercice 4 : Une implémentation des listes de Python en C¶

Le but de l'exercice est d'écrire une implémentation en C des list de Python et des fonctions associés (append et pop), on utilisera pour cela le type structuré suivant :

    struct list
    {
        int current_size;
        int max_size;
        int *array;
    };
    typedef struct list list;

où le champ current_size contient la taille actuelle de la liste et le champ array est un tableau de longueur max_size (supérieur ou égal à current_size) contenant les éléments de la liste.

Ecrire la fonction de création d'une liste en donnant sa taille et une valeur d'initialisation. La signature de cette fonction est donnée ci-dessous :
```
    list create(int size, int value)
```
On initialisera la valeur de la taille maximale à la taille courante.
Ecrire une fonction d'affichage pour une liste, on pourra prévoir d'afficher en même temps la taille courante et la taille maximale du tableau. La signature de cette fonction est :
```
    void display(list v)
```
Un exemple d'affichage est donné ci-dessous :
```
Contenu = [10, 10, 10, 10, 10, 11 ]
Taille actuelle : 7
Taille maxi : 10
```
Ecrire une fonction append d'ajout d'un élément à une liste de signature :
```
    void append(list *v, int value)
```
On remarquera que comme en Python, notre fonction ne renvoie rien mais modifie la liste passé en argument (et que donc on doit passer un pointeur vers elle)
Aide

On devra distinguer deux cas :
- si current_size < max_size : on peut ajouter au tableau sans le redimensionner
- sinon, on doit doubler la taille du tableau et recopier les éléments présents dans l'ancien tableau
Ecrire une fonction pop qui supprime l'élément en fin de liste et le renvoie. La signature sera :

c int pop(list *v)

Là aussi, puisque la liste est modifiée (sa taille diminue), on doit passer un pointeur.
On pourra poursuivre cet exercice en implémentant d'autres fonctions du type list de Python.

Exercice 5 : Tableaux dynamiques en C¶

Le but est de l'exercice est d'implémenter un type Vector de tableaux redimensionnables en C. On utilise le type structuré suivant :

    struct vector {
        int current_size; // nombre d'éléments
        int max_size; // taille du tableau
        int* array; // tableau utilisé pour stocker les éléments
        int default_value; //valeur par defaut d'un élément du tableau
    };

Ecrire les fonctions suivantes :
1. Une fonction create de signature vector create(int size, int value) qui renvoie un objet de type vector dont les size éléments du tableau sont initialisés à value et dont le champ max_size vaut aussi size et le champ default_value à value.
2. Ecrire une fonction display de signature void display(vector v) qui affiche les éléments d'un objet de type vector. Cette affichage pourra aussi indiquer les tailles actuelles (current_size) et maximales (max_size).
3. Ecrire une fonction get_element de signature int get_element(vector v, int index) qui renvoie l'élément du tableau situé à l'indice index dans le tableau. On vérifiera à l'aide d'un assert que index \(\leq\) current_size.
4. Ecrire une fonction set_element de signature void set_element(vector v, int index, int value) qui affecte à l'élément situé à l'indice index dans le tableau la valeur value.
5. Ecrire une fonction resize de signature void resize(vector *v, int new_size) qui redimensionne le v. Dans le cas où la nouvelle taille est supérieure à l'ancienne, les nouveaux éléments seront initialisés à default_value.
6. Ecrire une fonction destroy permettant de libérer l'espace mémoire occupée par l'objet vector donné en argument.
En revoyant si besoin le cours sur la compilation séparée écrire les fichiers vector.h et vector.c permettant de compiler séparément les fonctions ci-dessus afin de les utiliser dans un autre programme.

Exercice 6 : Implémentations de piles¶

En C (mutable), implémenter la structure de données pile au choix à l'aide d'une liste chaînée ou d'un tableau (voir cours). On écrira les fichiers pile.h et pile.c de façon à disposer de cette structure de donnée pour la suite.
En Ocaml (non mutable) : implémenter la structure de données pile à l'aide du type list de OCaml, on rappelle que ce type étant non mutable, empiler doit renvoyer une nouvelle pile et depiler doit renvoyer un couple (le sommet de la pile et la nouvelle pile)

Exercice 7 : Implémentations de files en C¶

Réaliser en C l'implémentation d'une file à l'aide d'une liste chaînée en utilisant deux pointeurs l'un vers le premier maillon de la liste et le second vers le dernier maillon

Aide

On fera bien attention aux cas particuliers des files contenant moins de deux éléments dans lesquels les deux pointeurs sont identiques
Réaliser en C l'implémentation d'une file de taille maximale connue \(n\) à l'aide d'un tableau circulaire de taille \(n\) (voir cours)

Exercice 8 : File de priorité¶

Une file de priorité est une structure de données dans laquelle chaque élément est enfilé avec une priorité, lorsqu'on veut défiler un élément c'est celui ayant la plus faible priorité qui est extrait. Une implémentation efficace de cette structure de données sera vu plus loin dans le cours, on propose ici de réaliser une implémentation utilisant une liste chainée d'entiers (représentant les priorités) que l'on garde triée ainsi le prochain élément à défiler se trouve toujours en tête de la liste. L'insertion doit maintenir la liste triée.

Par exemple, après insertion des valeurs 12, 7, 13, 8 , 10, la liste sera :

    graph LR
    classDef null stroke:#FFFFFF, fill:#FFFFFF
    A["7"] --> B["8"] --> C["10"] --> D["12"] --> E["13"] --> F["NULL"]
    class F null

Si on défile un élément c'est celui figurant en tête de liste (donc 7 dans l'exemple) qui sera extrait.

On utilisera le type structuré déjà rencontré en cours :

    struct maillon_s
    {
        int prio;
        struct maillon_s *suivant;
    };
    typedef struct maillon_s maillon;
    typedef maillon *fprio;

Quelle sera la complexité des opérations enfiler et défiler ?
Ecrire la fonction de signature enfiler(list* l, int p) qui enfile l'élément de priorité p dans la liste l.
Aide

On rappelle que cette se fait en supposant la liste triée et qu'elle doit la maintenir triée. Comme toujours lorsqu'on utilise une liste chainée, on recommande vivement de schématiser avant de passer à la programmation. Pour l'opération enfiler on pourra distinguer les deux cas suivants :
- l'insertion s'effectue en tête de liste, cela se produit dans les deux cas suivants : la liste est vide ou alors la priorité du maillon de tête est supéreure à celle de l'élément à inséser,
- l'insertion s'effectue après le maillon de tête.
Ecrire la fonction permettant de défiler un élément et tester votre implémentation.
Ecrire la fonction de signature void detruit(fprio *f) qui supprime une file de priorité en libérant l'espace mémoire allouée lors de sa construction.
On donne ci-dessous un fichier simulant l'arrivée et la prise en charge de patients dans un hopital, chaque patient a une priorité de traitement unique permettant de l'identifier. L'arrivée du patient de priorité x est indiqué dans le fichier par la ligne + x. La prise en charge d'un patient est indiqué par une ligne -. Par exemple les lignes :
```
+ 42
+ 12
-
+ 7
```
Signifient que les patients 42, 12 et 7 sont arrivés dans cet ordre, une seule prise en charge à eu lieu : celle du patient de priorité 12 (il était au moment de la prise en charge le plus prioritaire). On précise que ce fichier contient un total de 1000 opérations (arrivées et prise en charge). Patients En utilisant la file de priorité implémentée aux questions précédentes, déterminer au terme des 1000 opérations indiquées dans le fichier la liste des patients qui a été prise en charge. Vérifier votre réponse en entrant la liste des priorités des patients (dans leur ordre de prise en charge et séparé par des virgules) dans le cadre suivant :

Exercice 9 : Implémentation d'une file avec deux piles¶

On considère la file suivante : file On peut aussi la schématiser sous la forme de deux piles : file Pour comprendre ce fonctionnement, on part d'une file vide et on montre par quelques exemples l'état de la file et des deux piles qui la représente :

Opération	Etat de la file	Pile d'entrée	Pile de sortie
Enfiler `a`	`>a>`	`\|a>`	`\|>`
Enfiler `b`	`>b,a>`	`\|a,b>`	`\|>`
Enfiler `c`	`>c,b,a>`	`\|a,b,c>`	`\|>`
Défiler (`a`)	`>c,b>`	`\|>`	`\|c,b>`
Défiler (`b`)	`>c>`	`\|>`	`\|c>`
Enfiler `d`	`>d,c>`	`\|d>`	`\|c>`

Aide

Observer attentivement ce qui se passe à l'étape : la pile de sortie étant vide, la totalité de la pile d'entrée est dépilé dans la pile de sortie.

Compléter le tableau ci-dessous avec les étapes suivantes :
1. Défiler
2. Enfiler e
3. Défiler
Mettre par écrit le principe de l'implémentation d'une file avec deux piles (une pile d'entrée et une pile de sortie), on indiquera précisément :
- l'effet d'enfiler un élément sur chacune des deux piles
- l'effet de défiler sur chacune des deux piles (en distinguant les deux cas)
Ecrire en OCaml une implémentation d'une file sous la forme de deux piles (structure non mutable).
Tester votre implémentation (reprendre éventuellement les opérations à en faisant afficher l'état de la file et des deux piles à chaque étape).

Pour aller plus loin

Rechercher la complexité des opérations de cette implémentation.

Exercice 10 : Expression bien parenthésée¶

On considère dans cet exercice un parenthésage avec les couples \((\;), [\;]\) et \(\{\;\}\). On dit qu'une expression est bien parenthésée lorsque chaque symbole ouvrant est associé à un unique symbole fermant et si l'expression contenue à l'intérieur est elle-même bien parenthésée. Par exemple, on a souligné dans l'expression suivante le problème de parenthésage : \((3+2)\textcolor{red}{\underline{]}}-(4+1)\)

Les expressions suivantes sont-elles bien parenthésées ? Sinon, indiquer l'emplacement dans la chaîne de caractères où l'erreur est détectée.
1. \(3+\left.\left[5-4\div(3+2)\right]\right]+10\)
2. \(\left\{(3+2)\times 5\right.\)
3. \(5)-4\times2(\)
4. \(\left\{(3+2)\times(5-3)\right\}\)
Ecrire une fonction bien_parenthesee qui prend en argument une expression (sous la forme d'une chaine de caractères) et qui renvoie \(-1\) lorsque l'expression est bien parenthésée et sinon un entier indiquant l'emplacement dans l'expression où l'erreur de parenthésage est détectée.

Aide

On pourra, parcourir l'expression et utiliser une pile qui stocke les indices de chaque parenthèses ouvrante. On dépile, lorsqu'on rencontre une parenthèse fermante.
Tester votre fonction sur les expressions de la question 1.
Utiliser cette fonction afin de produire un affichage de l'erreur avec un caractère ^ en dessous de l'erreur. Par exemple : \((2+3)\underset{\textcolor{red}{\wedge}}{)}-5\)

Exercice 11 : Evaluation d'une expression en notation polonaise inverse¶

La notation polonaise inverse (npi) est une méthode d'écriture des expressions mathématiques qui n'utilise pas de parenthèses et qui de plus se calcule sans règles de priorité. Prenons un exemple, l'expression \((3+7)\times5\), s'écrit en notation polonaise inversée : \(3\ 7\ + 5 \times\). c'est-à-dire qu'on donne d'abord les deux opérandes puis l'opération. Pour d'autres exemples on pourra consulter : la page wikipedia dédiée

Le but de l'exercice est d'écrire une fonction évaluant une expression en npi passée en paramètre à l'aide d'une pile :

Parcourir l'expression de gauche à droite
Si on rencontre un nombre l'empiler
Si on rencontre une opération effectuer cette opération entre les deux valeurs situés au dessus de la pile et empiler le résultat

On représente ci-dessous l'état de la pile pour l'évaluation de \(3\ 7\ + 5\ \times\) :

3

7

3

10

5

10

50

Mettre en oeuvre cette méthode et la tester.

Exercice 12 : Mot mystère¶

Vous pouvez télécharger ci-dessous un fichier contenant \(10\,000\) caractères. Le but de l'exercice est de trouver une stratégie efficace afin de découvrir le mot caché qui s'y trouve. Pour cela, à chaque fois que deux lettres identiques se suivent, on doit les supprimer. Cela peut entrainer l'apparition de nouveau caractères identiques qui se suivent et donc offrir de nouvelles possibilités de suppression. Par exemple, avec la chaine de départ "ASSAMPOZZOPPI" on peut supprimer les deux S au début ce qui donne "AAMPOZZOPPI", puis "MPOZZOPPI", puis, "MPOOPPI" et enfin "MPI".

Mot mystère

Vous pouvez tester votre réponse (en lettres majuscules) dans le formulaire suivant :

Aide

Il faut choisir une structure de données adaptée !

Exercice 13 : Problème de Joseph¶

Le but de l'exercice est d'écrire un programme permettant de résoudre le problème de Joseph en simulant le déroulement des éliminations successives.

On représente un cercle de \(n\) soldats par la suite de valeurs 1,2,..,n et on décide que le soldat situé en premier dans la liste est celui qui tient l'épée. Ainsi en utilisant cette façon de représenter le problème, dans un cercle de 5 soldats le procédé décrit donne :

1, 2, 3, 4, 5 : position initiale
3, 4, 5, 1 (1 a éliminé 2 et transmis l'épée à 3)
5, 1, 3
3, 5
3

Proposer une structure de données adaptée à la résolution de ce problème (on veut que les opérations à effectuer sur cette structure de donnée soient en \(O(1)\)).
En donner une implémentation en C et l'utiliser afin de résoudre ce problème.
Quel est le soldat survivant dans un cercle d'un million de soldats ? Vous pouvez tester votre réponse ci-dessous (où alors avec la réponse mathématique au problème).

Exercice 14 : Un étrange clavier¶

Un ordinateur est doté d'un étrange clavier sur lequel ne figure que les lettres (majuscules ou minuscules) et le 0. Lorsqu'on tape une lettre elle apparaît sur la ligne du terminal à l'écran, mais cette ligne est limité à 10 caractères et donc continuer à taper des lettres alors qu'il y a en déjà 10 affichées est sans effet. Enfin, le 0 permet d'effacer la première lettre à gauche.

Par exemple, supposons qu'on tape dans l'ordre la suite de caractères suivantes : ZUP0M0P0I alors on obtient successivement à l'écran Z, ZU, ZUP, UP, UPM, PM, PMP, MP et enfin MPI.

Prenons un autre exemple : si on tape la suite de caractères ABCDEFGHIJKLMNOPQRSTUVWXYZ alors seuls les 10 premiers apparaitront à l'écran et on obtiendra ABCDEFGHIJ

Quel sera donc le mot affiché à l'écran si on tape la suite de caractères donnée dans le fichier ci-dessous : Touches tapées

Aide

On fera bien évidemment attention à utiliser une structure de donnée adaptée pour résoudre ce problème.

Tester votre réponse :

Humour d'informaticien¶

linked