Examen i133 structures de données en langage c 2019 2020 str

Télécharger PDF

Implémentation Statique d'une Pile pour la Vérification de Palindromes

Un palindrome est une chaîne de caractères qui se lit de la même manière de gauche à droite et de droite à gauche. Exemple : Le prénom AZIZA est palindrome, mais le prénom IBRAHIM n'est pas palindrome.

En utilisant une pile avec une implémentation statique, écrire un programme qui permet de vérifier si une chaîne de caractère (un mot) est palindrome.

La structure de donnée permettant de gérer une telle pile est donnée par :

#define MAX 10
typedef struct {
    char T[MAX];
    int sommet;
} TPile;

NB : Une implémentation de l'ensemble des fonctions de manipulation d'une pile est obligatoire.

Problème : Développement du Jeu Snake avec une Liste Chaînée

Dans le cadre du développement du célèbre jeu de serpent (snake), l'équipe de développement a décidé d'implémenter le snake en utilisant une liste chaînée. Chaque élément de cette liste correspond à un maillon du snake et contient les coordonnées x et y de ce maillon.

Le snake évolue dans une grille de 10x10 cases.

La structure de données qui permet de représenter le snake est donnée par :

typedef struct maillon {
    int x;
    int y;
    struct maillon *suivant;
} Snake;

Le snake se déplace d'une seule case à chaque étape vers une direction qui peut être Nord, Sud, Est ou Ouest. L'équipe de développement a choisi d'implémenter le mouvement du snake en faisant un ajout en tête et une suppression en queue. Les coordonnées de la nouvelle tête du snake sont calculées en fonction de la direction voulue.

Fonctions à Implémenter pour le Jeu Snake

Fonction taille

Écrire une fonction taille qui permet de calculer la taille du serpent (nombre de maillons).

int taille(Snake *S)

Fonction detruire

Écrire une fonction detruire qui permet de détruire le serpent (la liste entière).

void detruire(Snake **S)

Fonction mordre

Le serpent est mort lorsqu'il repasse sur un élément de son corps. Écrire une fonction mordre qui permet de retourner 1 si les coordonnées (x,y) de la tête du serpent sont égales aux coordonnées d'un maillon du serpent, et 0 sinon.

int mordre(Snake *S)

Fonction mouvement et Fonctions Auxiliaires

Le but est d'écrire la fonction mouvement qui permet de faire avancer le serpent sur la grille. Pour ce faire, il faut implémenter ces deux fonctions auxiliaires :

Fonction auxiliaire inserer_tete

Écrire une fonction inserer_tete qui permet d'insérer en tête du serpent un maillon de coordonnées (x,y). Cette fonction a comme argument les coordonnées x, y et S, le représentant du serpent.

Snake *inserer_tete(Snake *S, int x, int y)

Fonction auxiliaire supprimer_queue

Écrire une fonction supprimer_queue qui permet de supprimer la queue du serpent.

Snake *supprimer_queue(Snake *S)

Implémentation de la Fonction mouvement

Écrire une fonction mouvement qui permet de faire avancer d'une seule case sur la grille le serpent, dans les cas : direction=='N', direction=='S', direction=='E' ou direction=='O'.

Il faut prendre en compte le fait que le snake peut sortir d'une des extrémités de la grille et apparaître à l'extrémité opposée. Exemple de gestion de sortie de grille vers le Nord :

if (direction == 'N') {
    x = S->x;
    y = S->y - 1;
    if (y < 0) y = 9;
}

NB : La fonction mouvement fait appel aux fonctions inserer_tete, supprimer_queue et mordre. Si mordre(S)==1, on affiche "Perdu", la taille du serpent et on détruit le serpent.

Snake *mouvement(Snake *S, char direction)

Fonction gain

Lorsque le serpent passe sur une proie, sa taille est augmentée d'un élément. Écrire une fonction gain qui permet d'agrandir la taille du serpent lorsque les coordonnées de la tête après un mouvement sont égales aux coordonnées (x1,y1) de la proie.

Cet agrandissement est généralement réalisé en omettant la suppression du maillon de queue du serpent pour le tour de mouvement concerné.

Questions Fréquemment Posées (FAQ)

Qu'est-ce qu'un palindrome ?

Un palindrome est une séquence de caractères qui se lit de la même manière de gauche à droite et de droite à gauche. Des exemples courants incluent des mots comme "AZIZA" ou des phrases sans ponctuation ni espaces, comme "Élu par cette crapule".

Pourquoi les listes chaînées sont-elles adaptées pour le jeu Snake ?

Les listes chaînées sont idéales pour le jeu Snake car elles permettent une gestion dynamique de la taille du serpent. L'ajout d'une nouvelle tête et la suppression de la queue sont des opérations très efficaces dans une liste chaînée, ne nécessitant pas de coûteux déplacements de données en mémoire comme ce serait le cas avec un tableau de taille fixe.

Comment le jeu gère-t-il les déplacements du serpent hors de la grille ?

Le jeu implémente un mécanisme de "wrap-around". Cela signifie que si le serpent sort d'un bord de la grille (par exemple, il va trop à gauche), il réapparaît automatiquement du côté opposé (dans ce cas, à droite de la grille), créant ainsi un monde sans fin.