Trucsweb.com

Trucsweb 1997-2017 - 20 ans de partage.

C

Listes chaînées

RDFFav

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). allocations dynamiques mémoire c++ listes chaînées noeuds NULL pointeurs structures données ordre croissant
  • · Niveau : AVANCÉ
  • · Compatibilité : Tous compilateurs C++

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;
  }
}



Denis Marcoux
Dernière mise à jour :

Commentaires

       Visites : 4946 - Pages vues : 30831
X

Trucsweb.com Connexion

X

Trucsweb.com Mot de passe perdu

X

Trucsweb.com Conditions générales

Conditions

Responsabilité

La responsabilité des Trucsweb.com ne pourra être engagée en cas de faits indépendants de sa volonté. Les informations mises à disposition sur ce site le sont uniquement à titre purement informatif et ne sauraient constituer en aucun cas un conseil ou une recommandation de quelque nature que ce soit.

Aucun contrôle n'est exercé sur les références et ressources externes, l'utilisateur reconnaît que les Trucsweb.com n'assume aucune responsabilité relative à la mise à disposition de ces ressources, et ne peut être tenue responsable quant à leur contenu.

Droit applicable et juridiction compétente

Les règles en matière de droit, applicables aux contenus et aux transmissions de données sur et autour du site, sont déterminées par la loi canadienne. En cas de litige, n'ayant pu faire l'objet d'un accord à l'amiable, seuls les tribunaux canadien sont compétents.

X

Trucsweb.com Trucsweb

X

Trucsweb.com Glossaire

X

Trucsweb.com Trucsweb

X

Trucsweb.com Trucsweb

Conditions

Aucun message!

Merci.

X
Aucun message!
X

Trucsweb.com Créer un compte