C

Listes chaînées

Listes chaînées - Exemple de liste simplement chaînée

Voici un exemple d’une liste simplement chaînée réalisée en C++. C’est une structure de donnée fondamentale. La même chose peut se faire en C, bien sûr, avec les modifications qui s’imposent.

En C++, il convient d’utiliser une classe, ici nommée Noeud (chaque élément d’une liste est nommée "noeud").

Cette classe contient un pointeur vers un autre noeud, ici nommé "suivant".

Dans cet exemple, nous ne faisons que conserver un nombre indéterminé de chiffres donnés par l’entrée standard (cin). À chaque nouvel entrée, une allocation dynamique de la mémoire crée un nouveau noeud où entreposer le dernier chiffre fourni. Ensuite, la liste existente (qui pourrait être vide) est examinée en suivant la liste à partir de son premier élément, pour trouver l’endroit où il faut l’insérer. La liste est maintenue en ordre croissant des valeurs fournies.

Dans un exemple plus utile, chaque noeud pourrait être une "Personne", décrivant son nom, son adresse, son statut. Et la liste relierait chaque personne faisant partie d’un groupe donné de personnes.

Pourquoi utiliser une liste chaînée? Losrque nous avons un petit nombre de données à traiter, et que nous connaissons la quantité exacte de ces données, il convient souvent d’utiliser des tableaux. Mais lorsque nous ne pouvons prédire le maximum de données que nous aurons à conserver en mémoire vive, il convient alors mieux d’allouer dynamiquement de la mémoire au fur et à mesure que nous recevons de nouvelles données. Il faut alors utiliser un moyen de retenir toutes les adresses de ces allocations. Plutôt que de définir une multitude de variables, une méthode consiste à inclure dans chaque noeud, un ou plusieurs pointeurs vers d’autres noeuds, de sorte de permettre de tous les retrouver au besoin.

Limitations de l’exemple: Attention, car cet exemple ne vérifie pas si l’allocation dynamique a réussi. Un pointeur NULL est retourné si l’allocation n’a pas réussi (manque de mémoire). Cette amélioration est laissée au lecteur.

// ListeChaînée.cpp
//
// Par Denis Marcoux
// à titre d’exemple d’une liste chaînée créée en ordre
// alphabétique.
//
// Tout est dans la fonction main() (pour laisser du travail à faire aux
// étudiants) sauf pour TrouverSaPlaceDansChaine() qui effectue
// une recherche dans une liste chaînée et 
// AfficheLaListe() qui ne fait qu’afficher chaque noeud de la 
// liste.


#include 
// Définition des classes
class Noeud {
public:
  int nombre;
  Noeud * suivant;
};
//

Noeud * TrouverSaPlaceDansChaine(Noeud *, Noeud *&, int);
void AfficheLaListe(Noeud *);

void main () {
  Noeud * Premier = NULL; 
  Noeud * NouveauNoeud = NULL, * NoeudActuel = NULL, * NoeudPrecedent = NULL;
  int n;

  while (cin >> n) {
  // Un nouveau noeud doit être préparé
    NouveauNoeud = new Noeud;
    NouveauNoeud->nombre = n;
    NouveauNoeud->suivant = NULL;
    NoeudPrecedent = NULL;
  // À quel endroit doit-il être inséré?
    NoeudActuel = TrouverSaPlaceDansChaine(Premier, NoeudPrecedent, n);

    if (NoeudPrecedent == NULL) { 
      // On est au Premier noeud
      // puisque NoeudPrecedent est NULL
      NouveauNoeud->suivant = Premier; // qui sera NULL la première fois
      Premier = NouveauNoeud;          // mais pas par la suite

    } else {
      
      // Si NoeudActuel est NULL, on est à la fin 
      // et alors NoeudPrecedent pointe sur le dernier
      if (NoeudActuel== NULL)
        NoeudPrecedent->suivant = NouveauNoeud;
      else {
        // Insérer avant NoeudActuel
        // et il y a un noeud précédent si on est ici
        NoeudPrecedent->suivant = NouveauNoeud;
        NouveauNoeud->suivant = NoeudActuel;
        
      } // if (NoeudActuel== NULL)
    } // if (NoeudPrecedent == NULL)
  } // while
  
  AfficheLaListe(Premier);
} // Fin

// Fonction TrouverSaPlaceDansChaine()
// Cette fonction suis la chaîne à partir de la valeur passée en pNoeud
// Conserver en NoeudPrecedent le pointeur précédent l’actuel
// qui pourrait être NULL au départ
// et retourne l’adresse du Noeud suivant l’endroit
// où doit être inséré le nouveau Noeud
// Si NULL est retourné, c’est qu’il faut insérer le noeud
// à la fin.
Noeud * TrouverSaPlaceDansChaine(Noeud * pNoeud, Noeud *& NoeudPrecedent, int valeur) {
  if (!(pNoeud == NULL) && valeur >= pNoeud->nombre)
  {
    NoeudPrecedent = pNoeud;
    TrouverSaPlaceDansChaine(pNoeud->suivant, NoeudPrecedent, valeur);
  }
  else
    return pNoeud;
  
}

// Fonction AfficheLaListe()
// Parcours la liste en affichant le contenu
// de chaque noeud
void AfficheLaListe(Noeud * pNoeud) {
  cout << endl << endl << "Voici la liste:" << endl;
  while (pNoeud) {
    cout << pNoeud ->nombre << endl;
    pNoeud = pNoeud->suivant;
  }
}