Liste simplement chaînée (A): ouverte avec pointeur first

Télécharger le projet
Commenter

Description

Bonjour,

Est-il nécessaire de disposer de plusieurs "librairies", pour traiter les listes de type "ouvert" et celles de type "fermé" ?
Et si l'une d'entre elles suffisait ?

Voici une "comparaison" entre des 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.

Remarques:
a) Les termes first (premier) et last (dernier) sont utilisés ici pour représenter la position dans la liste, et non le moment d'introduction comme dans FIFO ou LIFO.
b) J'aurais également pu ajouter les opérations ExtractFirst et ExtractLast. Faites-le comme exercice!
 

Liste chaînée ouverte (avec pointeur first)

Elément (Elem) 
//// Elem.h

struct Elem {
  Elem *next=0; // Chaînage simple

  // Autre contenu ...

  // simple exemple pour tests:
  char chr;
  Elem(char c) {chr=c;} // constructeur pour les tests
};
Nous utilisons ce même code dans les trois types de liste.

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

  void InsertFirst(Elem *e) { // e ne doit pas être déjà inséré dans une liste
    e->next=first;  first=e;
  }
  void InsertLast(Elem *e) { // e ne doit pas être déjà inséré dans une liste
    Elem *last=first;
    if (last==0) first=e; else {
      while (last->next) last=last->next; // cherche dernier Elem
      last->next=e;
    }
    e->next=0;
  }
  unsigned int Length() { // Nombre d'éléments
    unsigned int len=0;
    Elem *e=first;
    if (e) do {++len; e=e->next;} while (e);
    return len;
  }
  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; return e;}
    } while (e);
    return 0;
  }
  void AllElems(void (*Do)(uint idx,Elem *)) {
    uint idx=0;
    Elem *e=first;
    if (e) do {Do(idx,e); ++idx; 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);
    first=p;
  }
};

Après avoir présenté trois "variantes" de listes simplement chainées, une Comparaison de listes chainées va suivre.
 
 
Bonne lecture ...
 

Tester avec Visual Studio Express

Pour concevoir et tester les codes C++ que je propose, j’utilise Visual Studio Express qui est gratuit.

Pour tester et/ou adapter les codes énoncés, il suffit de lancer VS-Express, de créer un Projet vide (sous Visual C++) avec un Nom adéquat, puis d’ajouter à Fichiers sources le ou les fichiers existants *.cpp proposés.
Les autres fichiers peuvent simplement être "glissés" dans la fenêtre principale de VS-Express.
On a pas besoin ajouter explicitement les fichiers *.h dans Fichiers d'en-tête.
 

Liens

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)