- Transformer la file d’attente FIFO en file de priorité basée sur le spicyIndex
- Former des matchs plus équilibrés entre joueurs de niveaux proches
- Cours sur les listes chaînées et files
- Documentation sur les files de priorité
- Référence Partie 3 : file FIFO
Fichiers à compléter :
headers/
└── priority-queue.h # Prototypes des fonctions de file de priorité
src/
├── priority-queue.c # Implémentation des fonctions de file de priorité
└── main.c # Optionnel : menu interactif pour tester la file de priorité1 Contexte
Dans la Partie 3, vous avez implémenté une file d’attente classique (FIFO) où les joueurs sont servis dans l’ordre d’arrivée. Cette méthode peut créer des matchs déséquilibrés (ex : un débutant affronte un expert).
Dans cette partie, vous allez :
- Créer une file de priorité où les joueurs sont triés par spicyIndex (force)
- Insérer chaque joueur à la bonne position pour garantir des matchs équilibrés
- Réutiliser les structures de la file FIFO, mais avec de nouvelles opérations
2 Principe de la file de priorité
- Les joueurs sont insérés à leur place selon leur spicyIndex (ordre décroissant)
- Le joueur en tête a toujours le spicyIndex le plus élevé
Exemple :
File actuelle : [1200] → [1000] → [800]
Insertion de 1100 :
Résultat : [1200] → [1100] → [1000] → [800]| FIFO (Partie 3) | File de priorité (Partie 4) |
|---|---|
| Ordre d’arrivée | Ordre de compétence |
| Insertion en queue | Insertion triée |
| Matchs rapides | Matchs équilibrés |
| Peut être déséquilibré | Niveaux proches |
3 Comparaison visuelle FIFO vs Priorité
Scénario : 6 joueurs arrivent dans cet ordre
| Ordre d’arrivée | Pseudo | spicyIndex |
|---|---|---|
| 1 | Alice | 1000 |
| 2 | Bob | 1500 |
| 3 | Charlie | 800 |
| 4 | Diana | 1200 |
| 5 | Eve | 900 |
| 6 | Frank | 1400 |
File FIFO :
[Alice:1000] → [Bob:1500] → [Charlie:800] → [Diana:1200] → [Eve:900] → [Frank:1400]Écart pour 4 premiers : 1500 - 800 = 700 points ⚠️
File de Priorité :
[Bob:1500] → [Frank:1400] → [Diana:1200] → [Alice:1000] → [Eve:900] → [Charlie:800]Écart pour 4 premiers : 1500 - 1000 = 500 points : ✅
4 Structures de données
Vous réutilisez :
typedef struct s_cell {
Player* value;
struct s_cell* next;
} t_cell;
typedef struct s_queue {
t_cell* head;
t_cell* tail;
} t_queue;Nouveau type défini dans: headers/priority-queue.h
typedef t_queue t_priority_queue;Un simple alias pour clarifier le code.
5 Fonctions à implémenter
5.1 Création d’une file de priorité
t_priority_queue * createPriorityQueue();Description :
Alloue et initialise une file de priorité vide (utilise createQueue()). Retourne NULL en cas d’échec.
5.2 Insertion avec priorité
void insertWithPriority(t_priority_queue * queue, Player * player);Description :
Cette fonction créé une nouvelle cellule dont le champ value pointe vers player l’ajoute dans la file queue de manière triée selon le spicyIndex des joueurs déjà présents puis met à jour le champ inQueue du joueur à 1. Si plusieurs joueurs ont le même spicyIndex, le nouvel entrant est placé après les joueurs existants avec le même spicyIndex.
Cette fonction doit pouvoir gérer tous les cas :
- File vide
- Insertion en tête (nouveau joueur a le plus grand spicyIndex)
- Insertion au milieu
- Insertion en fin (nouveau joueur a le plus petit
spicyIndex)
5.3 Retrait du joueur prioritaire
Player* removeHighestPriority(t_priority_queue* queue);Description :
Retire et retourne le joueur en tête (spicyIndex max) de la file de priorité queue. Utilise dequeue(). Retourne NULL si file vide.
5.4 Affichage de la file de priorité
void displayPriorityQueue(t_priority_queue* queue);Description :
Affiche tous les joueurs dans l’ordre décroissant de spicyIndex, avec un en-tête et le total.
Format suggéré :
====== File de Priorité ======
1. [ForkMaster | Lvl: 15 | Spicy: 1500] (max)
2. [KnifeLord | Lvl: 12 | Spicy: 1200]
3. [SteelBlade | Lvl: 10 | Spicy: 1000]
4. [RustyFork | Lvl: 5 | Spicy: 800]
Total: 4 joueurs (ordre décroissant)
==============================5.5 Destruction de la file de priorité
void destroyPriorityQueue(t_priority_queue* queue);Description :
Libère toutes les cellules de la file de priorité queue sans libérer les joueurs. Utilise destroyQueue().