TP2 - Les piles et les files

Durée : 3h

Inès de Courchelle, Elisabeth Ranisavljevic, Romain Dujol

Objectifs :

  • Étudier des structures de données
  • Connaître les fonctionnalités d’une pile et d’une file
  • Appréhender des notions de gestion de données

Attention :

À chaque étape de programmation, vous devez vérifier si le programme :

  • Compile sans warning
  • Obtient les résultats attendus
  • Avant de coder, il faut écrire un algo avec un papier et un stylo !

Exercice 1 - Avoir plus d’une corde à son arc

Nous considèrons des flèches ayant 3 couleurs possibles “rouge”, “bleu” ou “jaune” et 3 personnages ! Chaque personnage sa pile de flèche.
Link possède la pile de flèches suivante :











Kilton possède la pile de flèches suivante :








Zelda possède la pile de flèches suivante :





À vous de jouer

Vérifier de manière régulière l’ensemble des fonctionnalités réalisées Ne pas oublier les commentaires

  1. Créer l’arborescence suivante :
Comme d’habitude n’oublié pas les entêtes de fichier
pile.h
#ifndef PILE_H
#define PILE_H
/* Le prototype/signature de toutes mes fonctions/procédures */
#endif
pile.c
#include "pile.h"
...
main.c
#include "pile.h"
...
  1. Écrire la structure d’une flèche et d’une pile : Ici, notre structure de pile va stocker des entiers
    Vous utiliserez l’énumeration suivante :
typedef enum fleche{
  ROUGE, VERTE, BLEUE
}fleche;

Vous pouvez laisser int dans la définition de la pile, car le programme assimilera ROUGE, VERTE, BLEUE par les entiers 0, 1 et 2.

Exemple :
Le code
printf("Je suis de couleur %d \n",ROUGE);
printf("Je suis de couleur %d \n",VERTE);
printf("Je suis de couleur %d \n",BLEUE);
OUTPUT - Dans le Terminal
0
1
2

  1. Initialiser les 3 piles de flèches de Link, Kilton et Zelda. Dans le programme principale il vous suffit d’instancier 3 Piles vides, une pour chaque personnage.

  2. Dans le fichier pile.h, ajouter les signatures suivantes :

    • creerElementPile
    /* Auteur : xxxxxx */
/* Date : xxxxxx */
/* Entrees :  une valeur*/
/* Sorties :  le nouvel elt créer */
/* Résumé :  créer un nouvel elt */
ElementP* creerElementPile (int valeur);
    • empiler
    /* Auteur : xxxxxx */
/* Date : xxxxxx */
/* Entrees :  pile et une fleche*/
/* Sorties :  la pile */
/* Résumé :  Ajouter une fleche à une pile */
void empiler(Pile* p, fleche fl)
    • depiler
    /* Auteur : xxxxxx */
/* Date : xxxxx */
/* Entrees :  une pile*/
/* Sorties : la fleche depilée */
/* Résumé :  enlever la flèche de la pile */
int depiler(Pile* p);
    • afficher
    /* Auteur : xxxxxxxx */
/* Date : xxxxxxx */
/* Entrees :  une pile*/
/* Sorties :  */
/* Résumé :  Afficher une pile */
void afficherP(Pile p);
    • compter
    /* Auteur : xxxxxxxx */
/* Date : xxxxxxx */
/* Entrees :  une pile et un accumulateur*/
/* Sorties : le nb de flèches*/
/* Résumé :  Compte le nombre de flèche dans une pile */
int compterP(Pile p, int acc);
    • inverser
    /* Auteur : xxxxxx */
/* Date : xxxxxx */
/* Entrees :  une pile p1 et une pile p2*/
/* Sorties : une pile p2 */
/* Résumé :  inverse la pile p1 dans p2 */
Pile inverserP(Pile p1, Pile p2);
    • doubler
    /* Auteur : xxxxxx */
/* Date : xxxxxxxxx */
/* Entrees :  une pile p1 et une pile p2 */
/* Sorties : une pile p2 */
/* Résumé :  doubler la pile p1 dans la pile p2  */
Pile doublerP(Pile p1,Pile p2);
    • vider
    Pile viderP (Pile p);

  3. Implèmenter le scénario suivant dans un main :

    1. Empiler les différentes flèches pour chacun des personnages (empiler)
    2. Afficher les différentes piles de chacun des personnages (afficherP)
    3. Link donne ses 2 premières flèches à Kilton (depiler+empiler)
    4. Kilton perd ensuite ses 3 premières flèches (depiler)
    5. Kilton et Link compare leur pile de flèches (compterP)
    6. Link trouve 2 flèches (bleue,verte) dans la nature (empiler)
    7. Kilton prend les 4 premières flèches de Link (empiler + depiler)
    8. Link offre ses 2 premières flèches à Zelda (empiler + depiler)
    9. Zelda fait du rangement et décide d’inverser l’ordre sa pile (inverserP)
    10. Link a gagné au Loto. Sa pile de flèche est dupliquée. (doublerP)
    11. “Un problème est survenu !” La carte mémoire a planté ! Toutes les piles sont de nouveau vide (viderP)

Exercice 2 : Acheter sa Potion

Nous considèrons la file d’attente chez un apothicaire. Chaque personne dans la file désire acheter une potion.

A vous de jouer

Vérifier de manière régulière l’ensemble des fonctionnalités réalisées.

Ne pas oublier les commentaires

  1. Créer l’arborescence suivante :
    Comme d’habitude n’oublié pas les entêtes de fichier
    file.h
#ifndef FILE_H
#define FILE_H
/* Le prototype/signature de toutes mes fonctions/procédures */
#endif
file.c
#include "file.h"
...
main.c
#include "file.h"
...

  1. Écrire la structure Personne : Attention contrairement au cours la file ne stock pas d’entier mais des chaînes de caractères (char*)

  2. Initialiser la file de personnes suivantes :

    Ici, Harry est la première personne à pouvoir acheter sa potion

  3. Réaliser les procèdures/fonctions suivantes :

/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une chaine de caracteres*/
/* Sorties :  une personne*/
/* Résumé :  Creer une personne avec un nom */
Personne* creerElementFile(char* valeur);
/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une File et une chaine de caracteres*/
/* Sorties :  la file modifiée*/
/* Résumé :  enfiler un élement personne dans la file */
File enfiler(File f, char* valeur) ;
/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une File*/
/* Sorties :  */
/* Résumé :  Afficher une File */
void afficherF (File f);
/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une File*/
/* Sorties :  une chaine de caracteres*/
/* Résumé : défile la premiere personne de la file */
char* defilerF (File* f);
/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une File et un entier*/
/* Sorties :  un entier*/
/* Résumé : compte le nombre de personne dans la file*/
int compterF (File f, int acc);
/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une File*/
/* Sorties :  une File*/
/* Résumé : inverse le sens de la file*/
File* inverserF(File* f1);
/* Auteur : xxxxx */
/* Date : xxxxxx */
/* Entrees :  une File*/
/* Sorties :  une File*/
/* Résumé : vide le contenu de la file*/
File viderF (File* f);

  1. Implémenter le scénario suivant dans un main :

    1. La première personne de la file passe, il parle fort.
    <nom du personnage> :  "J'AI ACHETÉ MA POTION !"
    1. La seconde personne de la file passe, il parle lentement.
    <nom du personnage> :  "J'ai "
<nom du personnage> :  "acheté"
<nom du personnage> :  "ma"
<nom du personnage> :  "..."
<nom du personnage> :  "potion"
    1. La seconde personne a oublié une potion, elle refait la queue
    2. La troisième personne passe, et parle normalement
    <nom du personnage> : "j'ai acheté ma potion"
    1. La quatrième personne passe, et parle normalement
    <nom du personnage> : "j'ai acheté ma potion"
    1. Harry a oublié une potion. Il retourne faire la queue.
    2. En raison d’une anomalie, la file d’attente change de sens
    3. La première personne passe, et parle rapidement
    <nom du personnage> : "jaiachetémapotion"
    1. Compter le nombre de personne dans la file d’attente
    2. La nuit tombe, l’apothicaire ferme. Vider la file d’attente.

Exercice 3 : Beaucoup de correction

Nous considérons un professeur enseignant plusieurs matières. Pour chaque matière, il y aune pile de copie à corriger. Chaque copie possède un nom, un prénom et une note.

  1. Modéliser le problème
  2. Implémenter les structures nécéssaires
  3. Implémenter les fonctions et les méthodes étudiées en cours pour modéliser ce problème.
  4. Écrire l’algorithme permettant de compter les notes en dessous de 10.