Listes simplement chaînées (C): fermée avec pointeur last

Télécharger le projet
Commenter

Description

Bonjour,

En traitant les sections formées de polygones, j'ai rapidement remarqué qu'une liste simplement chaînée fermée leur est bien adaptée.
(Voir lien ci-dessous: CodeS-SourceS: Section_B: Polygone en cycle de segments)

Voici la troisième partie de la comparaison entre listes simplement chaînées ouvertes ou fermées:
‥ Liste simplement chaînée (A): liste chaînée ouverte (avec pointeur first).
‥ Liste simplement chaînée (B): liste chaînée ouverte (avec pointeurs first et last).
‥ Liste simplement chaînée (C): liste chaînée fermée (avec pointeur last).

Cette comparaison se limite à quelques opérations courantes:
‥ Ajouter un élément au début: InsertFirst.
‥ Ajouter un élément à la fin: InsertLast.
‥ Déterminer le nombre d'éléments: Length.
‥ Trouver un élément: Find.
‥ Enlever un élément: Extract.
‥ Parcourir tous les éléments: AllElems.
‥ Inverser l'ordre de la chaîne: Invert.
 

Liste chaînée fermée (avec pointeur last)

Elément (Elem)
L'objet Elem reste identique. (voir Zip: Elem.h).

Entête de liste chaînée fermée (avec last) 
//  ClosedList.h
//
//     ┌─────────────────────────────────────┐
//     │ Entête de liste chaînée fermée      │
//     │                                last │
//     └─────────────────────────────────────┘
//                                       │
//                                       ▼
//     ┌───────┐   ┌───────┐         ┌───────┐
//     │ ElemA │   │ ElemB │         │ ElemZ │
//  ┌─►│  next │──►│  next │──►...──►│  next │──┐
//  │  └───────┘   └───────┘         └───────┘  │
//  └───────────────────────────────────────────┘
//
struct ClosedList { // Entête de liste chaînée fermée
  Elem *last=0; // liste vide: last==0

  void InsertFirst(Elem *e) {
    if (e->next) return; // e déjà inséré !
    if (last) {e->next=last->next; last->next=e;}
    else {e->next=e; last=e;}
  }
  void InsertLast(Elem *e) {
    if (e->next) return; // e déjà inséré !
    if (last) {e->next=last->next; last->next=e;} else e->next=e;
    last=e;
  }
  unsigned int Length() { // Nombre d'éléments
    unsigned int n=0;
    Elem *e=last;
    if (e) do {e=e->next; ++n;} while (e!=last);
    return n;
  }
  Elem *Find(bool (*Ident)(Elem *)) { // Ident: fonction d'identification
    Elem *e=last;
    if (e) do {e=e->next;
      if (Ident(e)) return e;
    } while (e!=last);
    return 0;
  }
  Elem *Extract(bool (*Ident)(Elem*)) { // Ident: fonction d'identification
    Elem *e=last,*p;
    if (e) do {p=e; e=e->next;
      if (Ident(e)) {
        p->next=e->next; // supprime e de la liste fermée
        if (e==last) last=p; // si nécessaire, met à jour le pointeur last
        return e;
      }
    } while (e!=last);
    return 0;
  }
  void AllElems(void (*Do)(unsigned int,Elem*)) {
    unsigned int n=0;
    Elem *e=last;
    if (e) do {e=e->next; Do(n,e); ++n;} while (e!=last);
  }
  void Invert() { // Inversion de la chaîne
    if (last==0) return;
    Elem *p=last,*e=p->next,*ee;
    if (p!=e->next)
      do {ee=e->next; e->next=p; p=e; e=ee;} while (p!=last);
    last=e;
  }
};

Ce type de liste permet de savoir si un élément e est déjà inséré dans une liste: e->next != 0, et donc d'éviter de l'insérer plusieurs fois.
 
 
Bonne lecture ...
 

Liens

CodeS-SourceS: Liste simplement chaînée (A): ouverte avec pointeur first
CodeS-SourceS: Liste simplement chaînée (B): ouverte avec pointeurs first et last
CodeS-SourceS: Section_B: Polygone en cycle de segments
WikipédiA: Liste chaînée
CCM: Liste simplement chaînée
Les listes chaînées
OpenClassrooms: Listes chaînées
Programmation et Algorithmique
 
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)