Cours gratuits » Cours informatique » Cours programmation » Cours langage C » Exercices C

Exercice langage C : Gestion d'une liste chaînée

Écriture d'un programme intéractif de gestion d'une liste chaînée.

Ce programme affichera le menu suivant :

1 - AJOUTS d'éléments dans une liste chaînée.
2 - AFFICHAGE de la liste chaînée.
3 - TRI de la liste chaînée.
4 - SUPPRESSION d'éléments dans la liste.
5 - VIDER la liste.
6 - ARRÊT du programme.

et effectuera le traitement correspondant au choix effectué.

Fichier exo19.h


#define taille(t) sizeof(t) / sizeof(t[0])
typedef enum bool {False, True} Boolean;

Fichier exo19_gestion_liste.h


void ajouts     ( void );
void liste      ( void );
void tri        ( void );
void suppression( void );
void vider      ( void );
void arret      ( void );

Fichier exo19.c


#include 
#include 
#include 
#include "exo19.h"
#include "exo19_gestion_liste.h"

struct menu
{
  char  *texte;
  void (*action)( void );
};

§MEVBCBfint main()
{
  /* Définition du menu. */
  struct menu menu[] =
  {
    {"  1 - AJOUTS d'éléments dans une liste chaînée.\n",
                                                 ajouts},
    {"  2 - AFFICHAGE de la liste chaînée.\n",
                                                  liste},
    {"  3 - TRI de la liste chaînée.\n",
                                                    tri},
    {"  4 - SUPPRESSION d'éléments dans la liste.\n",
                                            suppression},
    {"  5 - VIDER la liste.\n",
                                                  vider},
    {"  6 - ARRÊT du programme.\n",
                                                  arret}
  };

  int SelectionMenu( struct menu menu[], int NbChoix );

  /* Boucle infinie sur les choix effectués. */
  for (;;)
    menu[SelectionMenu( menu, taille(menu) )].action();
}

 /* Fonction renvoyant le choix effectué. */

§MEVBCBfint SelectionMenu( struct menu menu[], int NbChoix )
{
  int   choix, m;
  char  entree[10];
  char *endp;

  do
  {
    printf( "\n\nListe des choix :\n" );
    for( m=0; m NbChoix )
      printf( "\nERREUR - choix invalide.\n" );
  } while( *endp != '\0' ||
           choix < 1 || choix > NbChoix );
  printf("\n");

  return --choix;
}

Fichier exo19_gestion_liste.c


#include 
#include 
#include 
#include "exo19.h"
#include "exo19_gestion_liste.h"

#define LISTE_VIDE "La liste est vide.\n"

static const char * const prompt_ajout       =
     "Élément à ajouter[CtrlD pour terminer] --> ";
static const char * const prompt_suppression =
     "Élément à supprimer[CtrlD pour terminer] --> ";
static const char *prompt;

typedef struct cellule
{
  char           *capitale;
  struct cellule *ptr_precedent;
  struct cellule *ptr_suivant;
} CEL;

static CEL  *debut   = NULL;
static CEL  *curseur = NULL;

static Boolean  liste_vide( void );
static void     ajout_cellule( char *chaine );
static void     suppression_cellule( void );
static Boolean  recherche_cellule( char *chaine );
static char    *lire_chaine( void );
static void     affichage_liste( CEL *p );

§MEVBCBfstatic Boolean liste_vide( void )
{
  return debut == NULL ? True : False;
}

§MEVBCBfstatic void ajout_cellule( char *chaine )
{
  CEL *p;

  /*
   * Allocation, valorisation,
   * insertion du nouvel élément.
   */

  p = malloc( sizeof(CEL) );
  p->capitale = chaine;

  if ( liste_vide() )
    p->ptr_suivant = p->ptr_precedent = NULL;
  else
  {
    if ( curseur != debut )
      curseur->ptr_precedent->ptr_suivant = p;
    p->ptr_precedent = curseur->ptr_precedent;
    curseur->ptr_precedent = p;
    p->ptr_suivant = curseur;
  }
  curseur = p;
  if( curseur->ptr_precedent == NULL )
    debut = curseur;

  return;
}

 §MEVBCBfstatic void suppression_cellule( void )
{
  if( curseur == debut )
  {
    /*
     * L'élément à supprimer est le 1er de la liste.
     */

    debut = curseur->ptr_suivant;
    if( ! liste_vide() )
      debut->ptr_precedent = NULL;
  }
  else
  {
    /*
     * L'élément à supprimer n'est pas le 1er de la liste.
     */

    curseur->ptr_precedent->ptr_suivant =
                          curseur->ptr_suivant;
    if( curseur->ptr_suivant != NULL )
      /*
       * L'élément à supprimer n'est
       * pas le dernier de la liste.
       */
      curseur->ptr_suivant->ptr_precedent =
                          curseur->ptr_precedent;
  }

   {
    CEL *p = curseur;

    free( p->capitale ); free( p );
    if ( curseur->ptr_suivant != NULL )
      curseur = curseur->ptr_suivant;
    else
      curseur = debut;
  }

  return;
}

§MEVBCBfstatic Boolean recherche_cellule( char *chaine )
{
  CEL *p;

  for( p=debut; p; p=p->ptr_suivant )
    if ( ! strcmp( p->capitale, chaine ) )
      break;

  if( p != NULL )
  {
    curseur = p;
    return True;
  }

  return False;
}

 §MEVBCBfstatic char *lire_chaine( void )
{
  char buffer[BUFSIZ];

  /*
   * Lecture de l'élément à ajouter.
   */

  fputs( prompt, stdout );
  gets( buffer );

  /*
   * Si Control-D, annuler le bit indicateur
   * de fin de fichier, pour les prochaines saisies.
   */

  if( feof( stdin ) )
  {
    clearerr( stdin );
    return NULL;
  }

  return strdup( buffer );
}

 /*
 * Fonction rattachée au choix 1.
 * (AJOUTS d'éléments dans la liste chaînée).
 */

§MEVBCBfvoid ajouts( void )
{
  char *chaine;

  /*
   * Boucle de lecture des chaînes.
   */

  prompt = prompt_ajout;

  while( (chaine = lire_chaine()) != NULL )
    ajout_cellule( chaine );

  return;
}

 /*
 * Fonction rattachée au choix 3.
 * (TRI de la liste chaînée).
 */

§MEVBCBfvoid tri( void )
{
  Boolean  tri_terminee;
  CEL     *ptr;

  /*
   * La liste doit exister.
   */

  if ( liste_vide() )
    fprintf( stderr, LISTE_VIDE );
  else
  {
    /*
     * Boucle de tri.
     */

     do
    {
      tri_terminee = True;
      for( ptr=debut; ptr->ptr_suivant;
           ptr = ptr->ptr_suivant )
        if( strcmp( ptr->capitale,
                    ptr->ptr_suivant->capitale ) > 0 )
        {
          /*
           * On effectue une interversion.
           */

          curseur = ptr;
          ajout_cellule(
            strdup( curseur->ptr_suivant->capitale ) );
          curseur = ptr->ptr_suivant;
          suppression_cellule();
          tri_terminee = False;
          if ( ptr->ptr_suivant == NULL )
            break;
        }
    } while( ! tri_terminee );
  }

  return;
}

 /*
 * Fonction rattachée au choix 4.
 * (SUPPRESSION d'éléments dans la liste).
 */
§MEVBCBfvoid suppression( void )
{
  char *chaine;

  /*
   * Boucle de lecture des chaînes.
   */
  prompt = prompt_suppression;

  while( ! liste_vide() && (chaine = lire_chaine()) != NULL )
  {
    if( ! recherche_cellule( chaine ) )
    {
      fprintf( stderr, "L'élément \"%s\" est"
                       " inexistant!\n\n", chaine );
      continue;
    }
    suppression_cellule();
    printf( "L'élément \"%s\" a été supprimé"
            " de la liste.\n\n", chaine );
  }

  /*
   * La liste est-elle vide ?
   */
  if ( liste_vide() ) fprintf( stderr, LISTE_VIDE );

  return;
}

 /*
 * Fonction rattachée au choix 5.
 * (VIDER la liste ).
 */
§MEVBCBfvoid vider( void )
{
  if ( liste_vide() )
    fprintf( stderr, LISTE_VIDE );
  else
  {
    curseur = debut;
    while ( ! liste_vide() )
      suppression_cellule();
  }

  return;
}
/*
 * Fonction rattachée au choix 6.
 * (ARRET du programme).
 */
§MEVBCBfvoid arret( void )
{
  /*
   * Si la liste n'est pas vide, on libère
   * la mémoire qu'elle occupe.
   */
  if( ! liste_vide() ) vider();

  printf( "\n\nFin EXO19.\n" );

  exit( 0 );
}