http://www-sop.inria.fr/oasis/personnel/Carine.Courbis/c/

IUT GTR Sophia Antipolis

Dec 2000

Autre Exemple d'allocation dynamique : exempleAllocDyn.c

1. Changez la structure de données de votre répertoire téléphonique (repTel.c)

Au lieu d'utiliser un tableau de Personne comme structure de données, utilisez une liste chaînée de Personne. Le type Personne doit être changé pour indiquer qu’il possède un nouveau champ suiv permettant de pointer sur la Personne suivante de la liste. De plus, les champs nom et prenom devront être changés en char * (pour optimiser l’utilisation de la mémoire ; en effet si on réserve de la place pour un tableau de 30 caractères et si le nom n’en contient que 8, 22 octets sont " perdus "). Votre variable contenant le répertoire sera donc un pointeur vers cette liste chaînée. Une correction du tp3 se trouve en annexe.

2. Modifiez les fonctions pour utiliser cette nouvelle structure de données

2.1] Insérez vos nouvelles Personne en tête de la liste chaînée, puis testez.

2.2] Insérez vos nouvelles Personne en queue de la liste chaînée, puis testez.

2.3] Insérez vos nouvelles Personne par ordre alphabétique dans la liste chaînée. La fonction permettant de rechercher une Personne dans le répertoire devra être optimisée (si le prochain nom de Personne est plus " grand " que celui recherché, on est sûr que la personne recherchée n’est pas dans le répertoire ; cela ne sert à rien de parcourir la liste jusqu’à la fin).

3. Faites une bibliothèque de votre répertoire téléphonique

• Un fichier d'entête (ou interface) repTel.h contenant tous les éléments publics du module (définitions de constantes, de types, de variables, de macro-définitions et les prototypes des fonctions ou procédures).
• Un fichier de réalisation repTel.c contenant la partie " cachée " i.e. le corps des opérations publiques et les objets privés au module (constantes, types, opérations, variables). Ce fichier ne doit pas contenir la fonction main.
• Un fichier testRepTel.c contenant la fonction main permettant de tester votre bibliothèque.

Aidez-vous de l'exemple de la bibliothèque du morpion fournie en annexe (morpion.h morpion.c testMorpion.c).

Faites aussi le Makefile indiquant les dépendances entre vos fichiers facilitant la compilation de votre bibliothèque (pour compiler, tapez dans le shell make suivi du nom de votre entrée compilant testRep.Tel.c).

1. Utilisez #ifdefine, lint et gdc

4.1] Mettez des traces dans votre programme (par exemple avant le retour d'une valeur ou au début des fonctions) encadrées par #ifdefine.

MAP est un identificateur. S'il n'est pas défini (pour le définir il faut soit écrire #define MAP dans le programme ou ajouter l'option -DMAP à la commande de compilation), le printf n'apparaîtra pas dans le code.

4.3] Tester le debugger gdb (mettre l'option –g à la compilation). Faire man gdb pour plus d'info.

  
Makefile
  testMorpion: testMorpion.o morpion.o
     cc -g testMorpion.o morpion.o -o testMorpion
   testMorpion.o: testMorpion.c morpion.h
     cc -g -c testMorpion.c
   morpion.o: morpion.c morpion.h
     cc -g -c morpion.c
  
morpion.h
/*
    Bibliotheque contenant les fonctions permettant de realiser le jeu du morpion. 
*/
#ifndef morpion_1 /*permet d'eviter les doubles definitions */

    typedef enum {FALSE, TRUE} Boolean;
     
    /* si on avait des variables globales a exporter (A EVITER) on ecrirait
      #ifndef morpion
      extern MonType maVariable;
      #endif
    */

    /* Initialise la grille du morpion a vide */
    extern void initialiseGrille(void);
  
    /* Affiche la grille du morpion 
       _ indique case vide, O pion joueur 1 et X pion jour 2
     */
    extern void afficheGrille(void);
   
    /*
      Saisie les coordonnees du nouveau pion a mettre sur la grille
      Si les coordonnees sont en dehors de la grille ou si la case possede
      deja un pion, la saisie est refusee, un message d'erreur est affiche, 
      et le joueur doit rejouer
     */
    extern void metUnPionSurLaGrille(void);
  
    /* Teste si l'un des joueurs a gagne; (ligne, colonne ou diagonale remplit
       de pions semblables). Dans ce cas affiche un message pour indiquer le 
       joueur qui a gagne
       S'il n'y a pas de gagnant, teste que la grille n'est pas pleine. Si elle 
       est pleine, affiche un message indiquant qu'aucun des joueurs a gagne
       Retourne TRUE si la grille est pleine ou si un joueur a gagne
                FALSE sinon
    */
    extern Boolean testeFinJeu(void);
  
#endif
  
morpion.c
/*
      Bibliotheque contenant les fonctions permettant de realiser
      le jeu du morpion. 
*/
#include 
    /* a definir #define morpion si on avait des variables globales a exporter
       pour eviter la double declaration de variable
    */
#include "morpion.h"
  
    #define NB_LIG 3
    #define NB_COL 3

    typedef enum {VIDE, ROND, CROIX} ValeurGrille;
    static ValeurGrille grille[NB_LIG][NB_COL]; /* grille du morpion valeurs possibles VIDE, ROND ou CROIX */
    /* indique quel sera le prochain joueur a mettre un pion dans la grille ie soit
    ROND soit CROIX 
    */
    static int prochainJoueur = ROND; 

    /*
     * Initialise la grille du morpion a vide
     */
    extern void initialiseGrille() {
      int i, j;
      for (i=0; i 0) && (ligne < NB_LIG) && (col > 0) && (col <= NB_COL)) {
          ligne--; /* enleve 1 pour etre compatible avec le tableau ayant des
                     indices de 0 a NB_LIG-1 */
          col--;
          if (grille[ligne][col] != VIDE) 
             printf("Cette case a deja ete remplie. Veuillez recommencer: \n");
          else {
             saisieCorrecte = TRUE;
             grille[ligne][col] = prochainJoueur;
             if (prochainJoueur == ROND)
                prochainJoueur = CROIX;
             else
                prochainJoueur = ROND;
          }
        } else
          printf("Indice de ligne ou de colonne incorrect. Veuillez recommencer:\n");
      } while (!saisieCorrecte);  
    }

    /* Teste si l'un des joueurs a gagne (ligne, colonne ou diagonale remplit
       de pions semblables). Dans ce cas affiche un message pour indiquer le 
       joueur qui a gagne.
       S'il n'y a pas de gagnant, teste que la grille n'est pas pleine. Si elle 
       est pleine, affiche un message indiquant qu'aucun des joueurs a gagne
       Retourne TRUE si la grille est pleine ou si un joueur a gagn;, FALSE sinon
    */
    extern Boolean testeFinJeu() {
      int i,j;
      int joueurGagnant; /* pour connaitre quel est le gagnant ie CROIX ou ROND */
      Boolean estFini = FALSE;

      /* Teste s'il y a un gagnant */
      /* L'algorithme utilise est le plus facile mais n'est pas le plus efficace 
         car on n'utilise pas la position du dernier pion ajoute sur la grille. 
         Cette information permettrait de reduire le temps de la recherche.
         De plus, cet algo suppose que la taille de la matrice est de 3 par 3
      */
      /* si la case 1,1 est VIDE, cela signifie que les diagonales, la ligne 1 et la 
         colonne 1 ne sont pas gagnantes
      */
      if (grille[1][1] != VIDE) {
        if (/* colonne 1 */ ((grille[0][1] == grille[1][1]) &&
                             (grille[1][1] == grille[2][1])) ||
            /* ligne 1 */ ((grille[1][0] == grille[1][1]) &&
                         (grille[1][1] == grille[1][2])) ||
            /* diagonale */ ((grille[0][0] == grille[1][1]) &&
                            (grille[1][1] == grille[2][2])) ||
            /* autre diag */ ((grille[0][2] == grille[1][1]) &&
                             (grille[1][1] == grille[2][0]))) { 
          joueurGagnant = grille[1][1]; /* ie ROND ou CROIX */
          estFini = TRUE;
        }
      }

      /* si la case 0,0 est vide, cela signifie que la ligne 0 et le colonne 0 ne sont pas gagnantes */
      if ((!estFini) && (grille[0][0] != VIDE)) {
        if ( /* ligne 0 */ ((grille[0][0] == grille[0][1]) &&
                            (grille[0][1] == grille[0][2])) ||
             /* colonne 0*/ ((grille[0][0] == grille[1][0]) &&
                            (grille[1][0] == grille[2][0]))) {
          joueurGagnant = grille[0][0];
          estFini = TRUE;
        }
      }

    /* si la case 2,2 est vide, cela signifie que la ligne 2 et la colonne 2 ne sont gagnantes */
      if ((!estFini) && (grille[2][2] != VIDE)) {
        if ( /* ligne 2 */ ((grille[2][0] == grille[2][1]) &&
                            (grille[2][1] == grille[2][2])) ||
             /* colonne 2 */ ((grille[0][2] == grille[1][2]) && 
                             (grille[1][2] == grille[2][2]))) {
          joueurGagnant = grille[2][2];
          estFini = TRUE;
        }
      }

      if (estFini) {
        printf("Felicitations au joueur ayant les ");
        if (joueurGagnant == ROND)
          printf("ronds ");
        else
          printf("croix ");
        printf("qui a gagne.\n");
        return TRUE;
      }

      /* teste si la grille n'est pas pleine */
      for (i=0; i < NB_LIG; i++) {
        for (j=0; j < NB_COL; j++) {
          if (grille[i][j] == VIDE) /* Au moins une case est vide donc le jeu n'est pas fini */
             return FALSE;
        }
      }
      return TRUE;
    }

testMorpion.c
  #include "morpion.h"
  /*
      Programme de  morpion. Le jeu s'arrete qd l'un des joueurs a gagne
      (ie 3 pions semblables sur une ligne, colonne ou diagonale) ou qd
      la grille est pleine.
      Algo:
      Initialise la grille a vide puis tant que la grille n'est pas pleine ou
      qu'il n'y a pas un gagnant, saisie les pions des joueurs et affiche la
      grille
     */
    void main() {
      initialiseGrille();
      do {
        metUnPionSurLaGrille();
        afficheGrille();
      }while(!testeFinJeu());
    }