Listes circulaires (Ring Buffer)

Note : lami20j est l'auteur d'origine de l'astuce.

Listes circulaires

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées
Les listes doublement chaînées

I. INTRODUCTION

Cette article a pour but la compréhension des listes circulaires.
L'implémentation en fonction des besoins et des performances vous appartient.

II. Définition

La liste circulaire est une sorte de liste simplement ou doublement chaînée, qui comporte une caractéristique supplémentaire pour le déplacement dans la liste, "elle n'a pas de fin".
Pour rendre la liste sans fin, le pointeur suivant du dernier élément pointera sur le 1er élément de la liste au lieu de la valeur NULL, que nous avons vu dans le cas des listes simplement et doublement chaînées.
Dans les listes circulaires, nous n'arriverons jamais à une position depuis laquelle nous ne pourrons plus nous déplacer.
En arrivant au dernier élément, le déplacement recommencera au premier élément. En bref, il s'agit d'une rotation.

III. La construction du prototype d'un élément de la liste

Pour définir un élément de la liste, le type struct sera utilisé.
L'élément de la liste contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur "suivant" permettra l'accès vers le prochain élément.

typedef struct ElementListe {
    char *donnee;
    struct ElementListe *suivant;
}Element;

Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.


Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition:

typedef struct ListeRepere {
    Element *debut;
    Element *fin;
    int taille;
}Liste;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.

Quelle que soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelle que soit l'opération effectuée sur la liste.

IV. Opérations sur les listes circulaires

A. Initialisation

Prototype de la fonction :

void initialisation (Liste *liste);

Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (Liste *liste){
    liste->debut = NULL;
    liste->fin = NULL;
    taille = 0;
}

B. Insertion d'un élément dans la liste

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
  • Cas particulier : dans une liste avec un seul élément, le 1er est en même temps le dernier.
  • mettre à jour la taille de la liste

1. Insertion dans une liste vide

Prototype de la fonction :

int ins_liste_circ_vide(Liste * liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

étapes :

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointera vers lui-même (c'est l'étape qui rend la liste circulaire)
• les pointeurs debut et fin pointeront vers le nouvel élément
• la taille est mise à jour

La fonction

/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
          == NULL)
      return -1;
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
       return -1;
    strcpy (nouveau_element->donnee, donnee);

    nouveau_element->suivant = nouveau_element;
    liste->debut = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

2. Insertion dans une liste non vide

Prototype de la fonction :

int ins_liste_circ(Liste * liste, Element *courant, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

L'insertion s'effectuera à la fin de la liste.


étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointe vers l'adresse du premier élément (garder la liste circulaire)
• le pointeur debut ne change pas
• le pointeur fin pointe vers le nouvel élément
• la taille est incrémentée d'une unité

La fonction

/* insertion dans une liste non vide */
int ins_liste_circ(Liste * liste, Element *courant, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
            == NULL)
        return -1;
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
        return -1;
    strcpy (nouveau_element->donnee, donnee);

    if(courant != liste->fin)
        return -1;

    nouveau_element->suivant = courant->suivant;
    courant->suivant = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

C. Suppression d'un élément dans la liste

Voici l'algorithme de suppression d'un élément de la liste :

• utilisation d'un pointeur temporaire pour sauvegarder l'adresse d'éléments à supprimer
• l'élément à supprimer se trouve après l'élément courant

Faire pointer le pointeur suivant de l'élément courant vers l'adresse du pointeur suivant de l'élément à supprimer

• libérer la mémoire occupée par l'élément supprimé
• mettre à jour la taille de la liste

Pour supprimer un élément dans la liste il y a plusieurs situations :

• 1. Suppression dans la liste
• 2. Suppression du dernier élément de la liste

1. Suppression au début de la liste

Prototype de la fonction:

int supp_list_circ(Liste *liste);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


étapes:

• le pointeur supp_elem contiendra l'adresse du 1er élément
• le pointeur debut pointera vers le 2ème élément
• le pointeur suivant du dernier élément pointera vers le 1er élément (qui était le 2ème avant la suppression)
• la taille de la liste sera décrémentée d'un élément

La fonction

/* suppression au début de la liste */
int supp_liste_circ(Liste * liste){
    if (liste->taille < 2)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    liste->fin->suivant = liste->debut;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

2. Suppression dans une liste avec un seul élément

Prototype de la fonction:

int supp_list_circ_unique(Liste *liste);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


étapes:

• le pointeur supp_elem contiendra l'adresse d'élément (la liste contient un seul élément)
• le pointeur debut pointera vers NULL
• le pointeur fin pointera vers NULL
• la taille de la liste sera décrémentée d'un élément

La fonction

/* suppression dans une liste avec un seul élément*/
int supp_liste_circ_unique(Liste *liste){
    if (liste->taille != 1)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = NULL;
    liste->fin = NULL;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

D. Affichage de la liste

Pour afficher la liste entière, il faut se positionner au début de la liste (le pointeur debut le permettra).
Ensuite, en utilisant le pointeur suivant de chaque élément, la liste est parcourue du 1er vers le dernier élément.
En comparaison avec les listes simplement et doublement chaînées, où la condition d'arrêt est donnée par le pointeur suivant du dernier élément, qui vaut NULL, pour la liste circulaire, il n'y a pas de point d'arrêt, à moins que vous n'en choisissiez un.

Voici deux variantes d'affichage :

• affichage de la liste (du 1er vers le dernier élément)
• affichage de la liste sans condition d'arrêt (à l'infini)

1. Affichage de la liste (du 1er vers le dernier élément)

Nous utiliserons la taille de la liste pour la condition d'arrêt.

La fonction

/* affichage de la liste */
void affiche (Liste * liste){
    Element *courant;
    courant = liste->debut;
    int i;
    for(i=0;i<liste->taille;++i){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

2. Affichage de la liste sans condition d'arrêt (à l'infini)

La fonction

/* parcourir la liste à l'infini*/
void affiche_infini (Liste * liste){
    Element *courant;
    courant = liste->debut;
    while (1){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

E. Destruction de la liste

Pour détruire la liste entière, j'ai utilisé la suppression au début de la liste tant que la taille est plus grande que 1, ensuite la suppression dans une liste avec un seul élément.

La fonction

/* detruire la liste */
void detruire (Liste * liste){
    while (liste->taille > 0){
        if(liste->taille > 1)
        supp_liste_circ (liste);
    else
        supp_liste_circ_unique(liste);
    }
}

V. Exemple complet

liste_circ.h

/* ---------- liste_circ.h ----------- */
typedef struct ElementListeCirc {
    char *donnee;
    struct ElementListeCirc *suivant;
} Element;

typedef struct ListeRepereCirc {
    Element *debut;
    Element *fin;
    int taille;
} Liste;

/* initialisation de la liste */
void initialisation (Liste * liste);

/* INSERTION */
/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee);
int ins_liste_circ(Liste * liste, Element *courant, char *donnee);

/* SUPPRESSION */
int supp_liste_circ (Liste * liste);
int supp_liste_circ_unique (Liste * liste);

int menu (Liste *liste);
void affiche (Liste * liste);
void affiche_infini (Liste * liste);
void detruire (Liste * liste);
/* -------- FIN liste_circ.h --------- */

liste_circ_function.h

/******************************\

    * liste_circ_function.h *
\******************************/
void initialisation (Liste * liste){
    liste->debut = NULL;
    liste->fin = NULL;
    liste->taille = 0;
}

/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
          == NULL)
      return -1;
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
       return -1;
    strcpy (nouveau_element->donnee, donnee);

    nouveau_element->suivant = nouveau_element;
    liste->debut = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

/* insertion dans une liste non-vide */
int ins_liste_circ(Liste * liste, Element *courant, char *donnee){
    Element *nouveau_element;
    if ((nouveau_element = (Element *) malloc (sizeof (Element)))
            == NULL)
        return -1;
    if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
            == NULL)
        return -1;
    strcpy (nouveau_element->donnee, donnee);

    if(courant != liste->fin)
        return -1;

    nouveau_element->suivant = courant->suivant;
    courant->suivant = nouveau_element;
    liste->fin = nouveau_element;
    liste->taille++;
    return 0;
}

/* suppression au début de la liste */
int supp_liste_circ(Liste * liste){
    if (liste->taille < 2)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = liste->debut->suivant;
    liste->fin->suivant = liste->debut;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

/* suppression dans une liste avec un seul élément*/
int supp_liste_circ_unique(Liste *liste){
    if (liste->taille != 1)
        return -1;
    Element *supp_element;

    supp_element = liste->debut;
    liste->debut = NULL;
    liste->fin = NULL;

    free (supp_element->donnee);
    free (supp_element);
    liste->taille--;
    return 0;
}

/* affichage de la liste */
void affiche (Liste * liste){
    Element *courant;
    courant = liste->debut;
    int i;
    for(i=0;i<liste->taille;++i){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

/* parcourir la liste à l'infini*/
void affiche_infini (Liste * liste){
    Element *courant;
    courant = liste->debut;
    while (1){
        printf ("%p - %s\n", courant, courant->donnee);
        courant = courant->suivant;
    }
}

/* detruire la liste */
void detruire (Liste * liste){
    while (liste->taille > 0){
        if(liste->taille > 1)
        supp_liste_circ (liste);
    else
        supp_liste_circ_unique(liste);
    }
}

int menu (Liste *liste){
    int choix;     printf("********** MENU **********\n");
    if (liste->taille == 0){
        printf ("1. Ajout du 1er element\n");
        printf ("2. Quitter\n");
    }else {
        printf ("1. Ajout d'un élément\n");
        printf ("2. Suppression au début (la liste doit avoir au moins 2 éléments)\n");
    printf ("3. Suppression dans une liste avec un seul élément\n");
        printf ("4. Affiche liste circulaire\n");
        printf ("5. Affiche liste circulaire [Ctrl-C] pour quitter le programme\n");
        printf ("6. Détruire la liste\n");
        printf ("7. Quitter\n");
    }
    printf ("\n\nFaites votre choix : ");
    scanf ("%d", &choix);
    getchar();
    if(liste->taille == 0 && choix == 2)
        choix = 7;
    return choix;
}
/* -------- FIN liste_circ_function --------- */

liste_circ.c

/**********************\

    * liste_circ.c *
\**********************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "liste_circ.h"
#include "liste_circ_function.h"

int main (void)
{
    char choix;
    char *nom;
    Liste *liste;
    Element *courant;


    if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL)
    return -1;
    if ((nom = (char *) malloc (50)) == NULL)
        return -1;
    courant = NULL;
    choix = 'o';

    initialisation (liste);

    while (choix != 7){
        choix = menu (liste);
        switch (choix){
            case 1:
                printf ("Entrez un element : ");
                scanf ("%s", nom);
                getchar ();
                if(liste->taille == 0)
                    ins_liste_circ_vide (liste,nom);
                else
                    ins_liste_circ (liste,liste->fin,nom);
                printf ("%d elements:deb=%s, fin=%s\n",
                                        liste->taille,
                                        liste->debut->donnee,
                                        liste->fin->donnee);
                affiche (liste);
                break;
            case 2:
                if(liste->taille < 2)
                    break;
                supp_liste_circ (liste);
                if (liste->taille != 0)
                    printf ("%d elements:deb=%s, fin=%s\n",
                                            liste->taille,
                                            liste->debut->donnee,
                                            liste->fin->donnee);
                affiche(liste);
                break;
            case 3:
                if(liste->taille != 1)
                    break;
                supp_liste_circ_unique(liste);
                printf("La liste est vide\n");
                break;
            case 4:
                affiche(liste);
                break;
            case 5:
                affiche_infini(liste);
                break;
            case 6:
                detruire (liste);
                printf ("la liste a ete detruite : %d elements\n", liste->taille);
                break;
        }
    }
    return 0;
}

VI. Voir aussi

• les listes simplement chaînées
• les listes doublement chaînées
• les piles
• les files