LISTE DOUBLEMENT CHAINÉE D'ENTIERS

// liste_chainee_dble.c
/* Programme d'apprentissage des pointeurs en langage C */
/* Liste doublement chainee d'entiers avec tri croissant des valeurs */
/* De maniere a ajouter des valeurs en debut, fin et milieu de liste */

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERR -1
#define QUIT 6 // valeur pour quitter le programme

// declaration maillon pour liste chainee double
typedef struct _maillon_dble_{
  int valeur;
  struct _maillon_dble_* suivant;
  struct _maillon_dble_* precedent;
}MaillonD;

/* Retourne un pointeur sur le maillon nouvellement cree */
MaillonD* creer_maillon_dble(int valeur){
  MaillonD* maillon = NULL;

  maillon = (MaillonD*) malloc(sizeof(MaillonD));
  maillon->valeur = valeur;
  maillon->suivant = NULL;
  maillon->precedent = NULL;
  return(maillon);
}

/* Parcours la liste depuis le 1er maillon
   et retourne le denier maillon de la liste */
MaillonD* dernier_maillon_dble(MaillonD* entete){

  while(entete->suivant != NULL)
    entete = entete->suivant;
  return(entete);
}

/* Retourne OK si le maillon a ete trouve, ERR sinon */
int recherche_maillon_dble(MaillonD* entete, int valeur){

  while((entete->valeur != valeur) && (entete->suivant!= NULL))
    entete = entete->suivant;
  if(entete->valeur == valeur)
    return(OK);
  else
    return(ERR);
}
/* Ajoute un maillon nouvellement cree en debut de liste, si la valeur du
   maillon entete est superieure a la valeur du nouveau maillon.
   Retourne un pointeur sur le maillon en tete de liste */
MaillonD* ajoute_maillon_dble_entete(MaillonD* entete, MaillonD* nouveau){

  if(entete != NULL){
    nouveau->suivant = entete;
    entete->precedent = nouveau;
    entete = nouveau;
    return(entete);
  }else
    return(NULL);
}

/* Ajoute un maillon nouvellement cree en fin de liste, si la valeur du
   maillon enqueue est inferieure ou egale a la valeur du nouveau maillon.
   Retourne un pointeur sur le maillon en queue de liste */
MaillonD* ajoute_maillon_dble_enqueue(MaillonD* enqueue, MaillonD* nouveau){

  if(enqueue != NULL){
    enqueue->suivant = nouveau;
    nouveau->precedent = enqueue;
    return(nouveau);
  }else
    return(NULL);
}

/* Ajoute le maillon nouvellement cree entre le maillon de valeur immediatement
   inferieure ou egale et le maillon de valeur immediatement superieure */
int ajoute_maillon_dble_milieu(MaillonD* entete, MaillonD* nouveau){
  MaillonD* suivant;
  
  suivant = entete->suivant;
  if((entete != NULL) && (suivant != NULL)){
    while((entete->valeur <= nouveau->valeur) &&
	  (suivant->valeur < nouveau->valeur)){
      entete = entete->suivant;
      suivant = entete->suivant;
    }
    if(suivant->valeur > nouveau->valeur){
      nouveau->suivant = suivant;
      suivant->precedent = nouveau;
      entete->suivant = nouveau;
      nouveau->precedent = entete;
      return(OK);
    }
  }
  return(ERR);
}
/* Retourne un pointeur sur le maillon en tete de liste, NULL si la liste
   est vide ou si l'unique maillon de la liste est supprime */
MaillonD* supprime_maillon_dble(MaillonD* precedent, int valeur){
  MaillonD* encours;
  MaillonD* suivant;
  MaillonD* liste;

  if(precedent != NULL){
    if(precedent->valeur == valeur){
      // le maillon a supprimer est le maillon en tete de liste
      if(precedent->suivant != NULL){
	encours = precedent->suivant;
	encours->precedent = NULL;
	liste = encours;
	free(precedent);
	return(liste);
      }else{
	free(precedent);
	return(NULL);
      }
    }else{
      liste = precedent;
      encours = precedent->suivant;
      suivant = encours->suivant;
      while(encours->valeur != valeur){
	precedent = encours;
	encours = suivant;
	suivant = suivant->suivant;
      }
      if(encours->valeur == valeur){
        if(encours->suivant == NULL)
	  // le maillon a supprimer est le dernier de la liste
          precedent->suivant = NULL;
        else{
	  // le maillon a supprimer est au milieu de la liste
          precedent->suivant = suivant;
          suivant->precedent = precedent;
        }
        free(encours);
        return(liste);
      }
    }
  }
  return(NULL);
}
/* Affiche les valeurs de la liste par ordre croissant */
int affiche_liste_croissant(MaillonD* affiche){

  while(affiche != NULL){
    printf("%d, ", affiche->valeur);
    affiche = affiche->suivant;
  }
  puts("");
  return(OK);
}

/* Affiche les valeurs de la liste par orde decroissant */
int affiche_liste_decroissant(MaillonD* affiche){
  while(affiche != NULL){
    printf("%d, ", affiche->valeur);
    affiche = affiche->precedent;
  }
  puts("");
  return(OK);
}

/* Retourne le choix de l'utilisateur */
int menu(void){
  int choix = 0;

  puts("");
  puts("1. Ajouter un maillon");
  puts("2. Supprimer un maillon");
  puts("3. Rechercher un maillon");
  puts("4. Afficher la liste dans l\'ordre croissant");
  puts("5. Afficher la liste dans l\'ordre decroissant");
  puts("6. Quitter");
  printf("Entrez un choix : ");
  scanf("%d", &choix);
  return(choix);
}

/* Retourne la valeur dans le cas d'un(e) ajout/suppr./recherche d'un maillon */
int navigation(int choix){
  int valeur = 0;

  switch(choix){
  case 1: // l'utilisateur ajoute un maillon a la liste
    printf("Entrez la valeur a ajouter : ");
    scanf("%d", &valeur);
    break;
  case 2: // l'utilisateur supprime un maillon de la liste
    printf("Entrez la valeur a supprimer : ");
    scanf("%d", &valeur);
    break;
  case 3: // l'utilisateur recherche un maillon dans la liste
    printf("Entrer la valeur a rechercher : ");
    scanf("%d", &valeur);
    break;
  }
  return(valeur);
}

int main(void){
  MaillonD* entete = NULL; // pointe sur le 1er maillon (declare a NULL)
  MaillonD* enqueue; // pointe sur le dernier maillon
  MaillonD* nouveau; // designe le maillon nouvellement cree
  int valeur, choix, etat;

  valeur = choix = etat = 0; // init
  choix = menu();
  while(choix != QUIT){ // tant que l'utilisateur ne quitte pas
    if((choix > 1) && (entete == NULL)){
      puts("La liste est vide.");
    }else{
      valeur = navigation(choix);
      switch(choix){
	case 1: // Ajout d'un maillon
	  nouveau = creer_maillon_dble(valeur);
	  if(entete != NULL){
	    if(nouveau->valeur < entete->valeur)
	      // Ajout d'un maillon en tete de liste
	      entete = ajoute_maillon_dble_entete(entete, nouveau);
	    else{
	      enqueue = dernier_maillon_dble(entete);
	      if(nouveau->valeur >= enqueue->valeur)
		// Ajout d'un maillon en queue de liste
		enqueue = ajoute_maillon_dble_enqueue(enqueue, nouveau);
	      else if((nouveau->valeur >= entete->valeur) &&
		      (nouveau->valeur < enqueue->valeur))
		// Ajout d'un maillon en milieu de liste
		ajoute_maillon_dble_milieu(entete, nouveau);
	    }				 
	  }else // entete == NULL --> 1er maillon ajoute a la liste
	     entete = nouveau;
	  break;
      case 2: // Suppression d'un maillon
	if(entete != NULL){
	  if(recherche_maillon_dble(entete, valeur) == OK){
	    entete = supprime_maillon_dble(entete, valeur);
            if(entete == NULL)
	      free(entete);
	  }else
	    puts("La valeur n\'existe pas dans la liste.");
	}else
	  puts("La liste est vide.");
	break;
      case 3: // Recherche d'un maillon
	etat = recherche_maillon_dble(entete, valeur);
	if(etat == ERR)
	  puts("la valeur recherchee n\'existe pas dans la liste.");
	else
	  printf("la valeur a ete trouve : %d\n", valeur);
	break;
      case 4: // Affichage de la liste dans l'ordre croissant
	affiche_liste_croissant(entete);
	break;
      case 5: // Affichage de la liste dans l'ordre decroissant
	affiche_liste_decroissant(enqueue);
	break;
      }
    }
    choix = menu(); // re-init
  }
return(EXIT_SUCCESS);
}