Liste linéaire chaînée
Manipulation d’une liste linéaire chaînée
Affichage le contenu d’une liste linéaire chaînée
Pour parcourir un tableau on utilise les indices
for ( i = 0 ; i < nbElem ; i++) …..
Pour parcourir un fichier, comme on n’a pas d’indices, on utilise la boucle while : while (!feof(…)) ….
Pour parcourir une liste linéaire chaînée
- on utilise la boucle :
while (liste != NULL) …..
ou plus court : while (liste) …..
- on avance dans la liste pour chaque tour de boucle : liste = liste->suivant ; /* liste pointe comme son « suivant » */
Exemple 1 : Écrire une fonction permettant d’afficher le contenu d’une liste linéaire chaînée des entiers.
Solution
void afficher( Pointeur liste)
{
while (liste) /* Tantque la liste soit non vide */
{ printf(« %5d\n », liste -> valeur );
liste = liste -> suivant ; /* avancer dans la liste */
}
}
Exercice :
Simuler la fonction avec la liste suivante :
liste ———-> ║ 10 ║ ——->║ 15 ║ ——> ║ 32 ║
Exemple 2 :
Écrire une fonction « récursive » permettant d’afficher le
contenu d’une liste linéaire chaînée des entiers.
Solution :
void afficher( Pointeur liste)
{
if (liste)
{ printf(« %5d\n », liste -> valeur );
afficher(liste -> suivant) ;
}
}
Exercice :
Simuler la fonction avec la liste suivante :
liste ———-> ║ 60 ║ ——->║ 15 ║ ——> ║ 49 ║
Recherche d’un élément dans une liste linéaire chaînée
2.1) Raisons d’une recherche :
On cherche un élément de la liste :
- pour une consultation (cas très fréquent)
- pour une suppresion (exemple : cas d’abandon dans un
système d’inscription)
- pour une modification (exemple : changements de notes dans
un système de gestion des notes)
etc ….
Pour les besoins de consultation, il suffit d’avoir un pointeur qui :
. pointe vers rien si on ne trouve pas OU
. pointe vers l’élément trouvé
Si on cherche « LEVAC LUC » et si on dispose d’un pointeur « cestLui » :
cestLui
|
v
╔════════════╗═══╗ ╔════════════╗═══╗ ╔════════════╗═══╗
liste -> ║ BEDARD MARC║ ║ ║ LEVAC LUC ║ ║ ║ VIAU LISE ║ ║
║ 1.75 mètre ║ –║–>║ 1.55 mètre ║ –║–>║ 1.67 mètre ║ X ║
║ 65.2 kgs ║ ║ ║ 57.8 kgs ║ ║ ║ 52.4 kgs ║ ║
╚════════════╝═══╝ ╚════════════╝═══╝ ╚══════════╝═══╝
on est capable de faire : afficher(cestLui->pers) ; où pers est le premier champ du type Element. Si on a besoin de corriger la taille de « LEVAC LUC » : 175 mètre
au lieu de 1.55 mètre, il suffit de faire :
cestLui->pers.taille = 1.75 ;
Cependant, si on a besoin de supprimer « LEVAC LUC » de la liste,
le pointeur cestLui n’est pas suffisant.
Supposons qu’on dispose d’un autre pointeur du nom « avant » qui
pointe vers le prédécesseur de l’élément trouvé :
avant cestLui
| |
v v
╔════════════╗═══╗ ╔════════════╗═══╗ ╔════════════╗═══╗
liste -> ║ BEDARD MARC║ ║ ║ LEVAC LUC ║ ║ ║ VIAU LISE ║ ║
║ 1.75 mètre ║ –║–>║ 1.55 mètre ║ –║–>║ 1.67 mètre ║ X ║
║ 65.2 kgs ║ ║ ║ 57.8 kgs ║ ║ ║ 52.4 kgs ║ ║
╚════════════╝═══╝ ╚════════════╝═══╝ ╚════════════╝═══╝
Pour supprimer « LEVAC LUC », il suffit de faire comme suit :
avant->suivant = cestLui->suivant ;
avant cestLui
| |
v v
╔════════════╗═══╗ ╔════════════╗═══╗ ╔════════════╗═══╗
liste -> ║ BEDARD MARC║ ║ ║ LEVAC LUC ║ ║ ║ VIAU LISE ║ ║
║ 1.75 mètre ║ | ║ ║ 1.55 mètre ║ ────────>║ 1.67 mètre ║ X ║
║ 65.2 kgs ║ | ║ ║ 57.8 kgs ║ ║ ┌───>║ 52.4 kgs ║ ║
╚════════════╝═|═╝ ╚════════════╝═══╝ | ╚════════════╝═══╝
| |
└────────────────────────┘
Résumés : Ainsi, pour les besoins de la gestion d’une liste (y compris la suppression), on aimerait avoir une fonction qui retourne
2 pointeurs :
- cestLui qui pointe sur l’élément trouvé ou vaut NULL dans le cas contraire
- avant qui pointe sur le prédécesseur de l’élément trouvé
ou qui vaut NULL si on trouve au début de la liste.
2.2) Recherche dans une liste triée des personnes :
Je présente ici un cas où la clé est une chaîne de caractères.
C’est plus simple si la clé est un entier :
void chercher ( char * aChercher, Pointeur liste,
Pointeur *av, Pointeur * cl)
{ int longueur = strlen(aChercher), compare , trouve ;
Pointeur avant, cestLui ; /* comme *av et *cl */
/* Initialisation : */
avant = NULL ;
cestLui = liste ;
trouve = 0 ; /* Faux, on ne trouve pas encore */
while (cestLui && !trouve)
{
compare = strnicmp (cestLui->pers.nomPre, aChercher,
longueur);
trouve = compare == 0 ; /* on trouve */
if (!trouve )
if ( compare < 0) /* on a la chance et on continue à chercher */
{ avant = cestLui ;
cestLui = cestLui->suivant;
}
else cestLui = NULL ; /* on ne trouve plus */
}
*av = avant ;
*cl = cestLui ;
}
Notes :
- La fonction : strnicmp(chaine1, chaine2, k) permet de comparer k premiers caractères de ces deux chaînes sans tenir compte des majuscules ou des minuscules. Le résultat (variable compare dans la fonction) est un entier :
zéro : elles sont pareilles dans les k premiers caractères
< 0 : chaine1 < chaine2 dans les k premiers caractères
> 0 : chaine1 > chaine2 dans les k premiers caractères
- Pour chaque tour de la boucle de recherche :
Si compare vaut zéro, on trouve. C’est réglé. Si compare < 0, on ne trouve pas encore mais, on a quand même la chance car le nom de la personne rendue (exemple « BEDARD MARC ») est plus petit que le nom recherché (ici « LEVAC LUC »). Dans ce cas, avant prend la position de cestLui et on avance cestLui. Si on cherche « LAVOIE JACQUES » et qu’on trouve plutôt « LEVAC LUC », dans ce cas on a compare > 0 et on n’aura jamais la chance de trouver « LAVOIE JACQUES » car la liste est triée. On affecte NULL à cestLui pour signaler qu’on ne rencontre pas « LAVOIE JACQUES ».
- Notez que :
- a) la recherche de « BEDARD MARC » donne NULL au pointeur avant. Dans ce cas, cestLui qui est non NULL alors que avant vaut NULL signale qu’on trouve au début de la liste. Cette information est précieuse pour la suppression.
- b) la recherche de « LAVOIE JACQUES » est échouée. c est Lui vaut NULL pour signaler qu’on ne le trouve pas. Cependant avant pointe sur « BEDARD MARC » (le prédécesseur immédiat
si « LAVOIE JACQUES » est dans la liste). Cette information est précieuse pour l’ajout de « LAVOIE JACQUES » dans la liste.
2.3) Recherche dans une liste non triée :
Je présente ici un cas où la clé est un entier.
╔═════╗════╗ ╔═════╗════╗ ╔═════╗════╗
liste ———-> ║ 60 ║ ——->║ 15 ║ ——> ║ 49 ║ X ║
╚═════╝════╝ ╚═════╝════╝ ╚═════╝════╝
void chercher(int aChercher, Pointeur liste, Pointeur * av,
Pointeur * cl)
{
Pointeur avant = NULL, cestLui = liste ;
/* Si on ne trouve pas, on avance dans la liste */
while (cestLui && cestLui->valeur != aChercher)
{ avant = cestLui ;
cestLui = cestLui->suivant ;
}
*av = avant ;
*cl = cestLui ;
}
Exercice 1 : Simuler l’algorithme avec la recherche de 15 et de 20 de la liste des entiers représentés par le schéma ci-dessus.
Exercice 2 :
Réécrire la fonction de recherche dans le cas où la clé est
un nom et un prénom et, qu’il il y a possibilité de noms doubles :
- si la liste est triée selon le nom et prénom
- si la liste n’est pas du tout triée.
Télécharger le document complet
