Liste chainee circulaire

Fermé
mohammed - 14 mai 2017 à 17:22
Dalfab Messages postés 706 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 2 novembre 2023 - 14 mai 2017 à 20:09
Bonjour,
je cherche les algorithmed d'ajout et suppression et parcours de la liste chainee circulaire(n'est pas doublement chainee);svp aidez moi!!!

1 réponse

Dalfab Messages postés 706 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 2 novembre 2023 101
14 mai 2017 à 20:09
Bonjour,
Les circulaires simplement chaînées sont les plus simples en C. Il suffit mémoriser le dernier élément pour gérer la liste car le premier est le suivant du dernier.
struct Noeud {
   int  x;
   struct Noeud *pSuivant;
};
struct Liste {
   struct Noeud  *pDernier;
};
struct Noeud* dernier( struct Liste lst ) {
   return lst.pDernier;
}
struct Noeud* premier( struct Liste lst ) {
   return lst.pDernier ? lst.pDernier->pSuivant : NULL;
}
bool estVide( struct Liste lst ) {
   return lst.pDernier == NULL;
}

Pour insérer un item
si la liste est vide:
   pItem->pSuivant = pItem;  // seul donc suit lui-même
   lst.pDernier = pItem;     // devient le dernier et aussi le premier
si la liste n'est pas vide, en appelant pPrecedent un élément de la liste
   pItem->pSuivant = pPrecedent->pSuivant;
   pPrecedent->pSuivant = pItem;
   if (lst.pDernier==pPrecedent) lst.pDernier = pItem; // devient dernier

Pour parcourir ... ... Le suivant s'appelle pSuivant et le dernier pDernier.

Pour supprimer, il faut trouver l'élément tel que pItem->pSuivant == pElementASupprimer et remplacer son suivant et peut-être mettre à jour lst.pDernier.
0