Liste simplement chaînée (B): ouverte avec first et last

Télécharger le projet
Commenter

Description

Bonjour,

Deuxième type de liste ouverte, "gérée" par les deux pointeurs "first" et "last" de la "comparaison" entre des listes simplement chaînées:
‥ Listes simplement chaînées (A): liste chaînée ouverte (avec pointeur first).
‥ Listes simplement chaînées (B): liste chaînée ouverte (avec pointeurs first et last).
‥ Listes simplement chaînées (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.
‥ Parcourir tous les éléments: AllItems.
‥ Inverser l'ordre de la chaîne: Invert.
‥ Enlever un élément: Extract.

Liste chaînée ouverte (avec pointeurs first et last)

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

Entête de liste chaînée ouverte (avec first et last) 
////  OpenList2.h
//
//     ┌─────────────────────────────────────┐
//     │ Entête de liste chaînée ouverte     │
//     │ first                          last │
//     └─────────────────────────────────────┘
//         │                             │
//         ▼                             ▼
//     ┌───────┐   ┌───────┐         ┌───────┐   
//     │ ElemA │   │ ElemB │         │ ElemZ │   
//     │  next │──►│  next │──►...──►│  next │──►║   
//     └───────┘   └───────┘         └───────┘
//
struct  OpenList2 { // Liste chaînée ouverte avec pointeurs first et last
  Elem *first=0,*last; // vide si first == 0

  void InsertFirst(Elem *e) { // e ne doit pas être déjà inséré dans une liste
    if (first) e->next=first; else last=e;
    first=e;
  }
  void InsertLast(Elem *e) { // e ne doit pas être déjà inséré dans une liste
    if (first) last->next=e; else first=e;
    last=e;
  }
  unsigned int Length() { // Nombre d'éléments
    unsigned int n=0;
    Elem *e=first;
    if (e) do {++n; e=e->next;} while (e);
    return n;
  }
  Elem *Find(bool (*Ident)(Elem *)) { // Ident: fonction d'identification
    Elem *e=first;
    while ((e)&&(!Ident(e))) e=e->next;
    return e;
  }
  Elem *Extract(bool (*Ident)(Elem *)) { // Ident: fonction d'identification
    if (first==0) return 0;
    Elem *p,*e=first; 
    if (Ident(e)) {first=e->next; e->next=0; return e;} // extract first
    do {
      p=e; e=e->next;
      if (Ident(e)) {
        p->next=e->next; e->next=0;
        if (e==last) last=p;
        return e;
      }
    } while (e);
    return 0;
  }
  void AllElems(void (*Do)(uint n,Elem*)) {
    uint n=0;
    Elem *e=first;
    if (e) do {Do(n,e); ++n; e=e->next;} while (e);
  }
  void Invert() { // Inversion de la liste chaînée
    Elem *e=first,*ee,*p=0;
    if (e) do {ee=e; e=e->next; ee->next=p; p=ee;} while (e);
    last=first; first=p;
  }
};

En anticipant sur la comparaison, on constate que l'avantage principal est l'amélioration de la routine InsertLast; par contre, il faut maintenir à jour deux pointeurs.
 
 
Bonne lecture ...
 

Liens

CodeS-SourceS: Liste simplement chaînée (A): ouverte avec pointeur first
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)