Chapitre IV - Les Listes simplement chaînées
1. Définition d’une liste chaînée
Une liste chaînée est un ensemble ordonné de données homogènes. Ces éléments ne sont
pas nécessairement contigus en mémoire à la différence des tableaux.
C’est un ensemble de cellules qui sont chaînées entre elles. La liste est déterminée par
l’adresse de la première cellule.
Une cellule est composée de deux parties, une partie contenant la donnée utile et une
deuxième partie contenant un pointeur pointant vers la cellule suivante. Une cellule est
donc définie par une structure de deux champs ; un premier champ pouvant être de
n’importe quel type et qui représente l’information et un deuxième champ qui est un
pointeur contenant l’adresse de la cellule suivante.
Le pointeur de la dernière cellule d’une liste chaînée contient la valeur NULL.
ASD2 – TI1-7 – Les listes
1/6
ListecelluleNULLCELLULEinformationsuivant
2. Spécification d’une liste chaînée : fichier liste.h
/ Fichier liste.h /
typedef int element;
typedef struct cellule {
element information ;
struct cellule * suivant ;
} cellule ;
typedef cellule *liste;
void creer_liste(liste); /cree une liste vide*/
int vide_liste(liste); /teste si une liste donnee est vide ou non/
element tete_liste(liste); /*retourne l'element tete d'une liste donnee non
vide*/
element queue_liste(liste); /*retourne l'element queue d'une liste donnee
non vide*/
cellulerecherche_cellule_liste(liste, element); /retourne un pointeur sur
une cellule d'une liste donnee contenant un element donn鬠sinon retourne
NULL*/
int longueur_liste(liste); /retourne la longueur de la liste/
void afficher_liste(liste); /affiche les elements d'une liste donnee/
void inserer_tete_liste(liste , element); / inserer un element donne en
tete d'une liste donnee */
void inserer_queue_liste(liste , element); / inserer un element donne en
queue d'une liste donnee */
void inserer_apres_liste(cellule , element); / inserer un element donne
apres une cellule donnee d'une liste */
void supprimer_tete_liste(liste); / supprime la tete d'une liste non vide
*/
Advertisement
void supprimer_queue_liste(liste); / supprime la queue d'une liste non
vide */
3. Implémentation d’une liste chaînée : fichier liste.c
Insertion en tête de liste
ASD2 – TI1-7 – Les listes
2/6
Insertion en fin de liste
Suppression du premier élément
/ fichier liste.c /
#include "liste.h"
#include <stdio.h>
#include <stdlib.h>
void creer_liste(liste*l){
*l=NULL ;
}
int vide_liste(liste l){
return l == NULL ;
ASD2 – TI1-7 – Les listes
3/6
LP(a)(b)Élément à insérerLPÉlément à insérerder(a)(b)LÉlément à supprimer
}
element tete_liste(liste l){
return l->information;
}
element queue_liste(liste l){
cellule * p;
p = l;
while(p->suivant != NULL)
p = p->suivant;
return p->information;
}
cellule*recherche_cellule_liste(liste l , element e){
cellule * p;
if(vide_liste(l))
return NULL;
p = l;
while(p != NULL){
if(p->information == e)
return p;
}
Advertisement
return NULL;
}
int longueur_liste(liste l){
cellule * p;
int longueur;
if(vide_liste(l))
return 0;
longueur = 1;
p = l;
while(p->suivant != NULL){
longueur++;
p = p->suivant;
}
return longueur;
}
void afficher_liste(liste l){
cellule * p = l;
while(p != NULL){
printf("%d\n" , p->information);
p = p->suivant;
}
}
void inserer_tete_liste(liste*l , element e){
cellule * n;
n = (cellule*)malloc(sizeof(cellule));
n->information = e;
ASD2 – TI1-7 – Les listes
4/6
n->suivant = *l;
*l = n;
}
void inserer_queue_liste(liste*l , element e){
cellule * n;
cellule * p;
n = (cellule*)malloc(sizeof(cellule));
n->information = e;
n->suivant = NULL;
if(vide_liste(*l))
*l = n;
else{
p = *l;
while(p->suivant != NULL)
Advertisement
p = p->suivant;
p->suivant = n;
}
}
void inserer_apres_liste(cellule*p , element e){
cellule * n;
n = (cellule*)malloc(sizeof(cellule));
n->information = e;
n->suivant = p->suivant;
p->suivant = n;
}
void supprimer_tete_liste(liste*l){
cellule p = l;
*l = p->suivant;
free(p);
}
void supprimer_queue_liste(liste*l){
cellule p1 , p2;
p1 = *l;
if(p1->suivant == NULL){
*l = NULL;
free(p1);
}
else{
while((p1->suivant)->suivant != NULL)
p1 = p1->suivant;
p2 = p1->suivant;
p1->suivant = NULL;
free(p2);
}
}
4. Exercice : Utilisation du module liste.h
Ecrire un programme principal qui utilise et teste efficacement le module liste.h
ASD2 – TI1-7 – Les listes
5/6
/ fichier main.c /
#include <stdio.h>
#include <stdlib.h>
#include "liste.h"
void main( ){
liste l1, l2;
creer_liste(&l1);
Advertisement
creer_liste(&l2);
inserer_tete_liste(&l1 , 10);
inserer_tete_liste(&l1 , 10);
inserer_queue_liste(&l1 , 1);
inserer_tete_liste(&l1 , 11);
inserer_queue_liste(&l1 , 0);
printf("Longueur de la liste l1 = %d\n" , longueur_liste(l1));
afficher_liste(l1);
supprimer_queue_liste(&l1);
supprimer_queue_liste(&l1);
supprimer_tete_liste(&l1);
printf("Longueur de la liste l1 = %d\n" , longueur_liste(l1));
afficher_liste(l1);
inserer_apres_liste(recherche_cellule_liste(l1 , 10) , 9);
printf("Longueur de la liste l1 = %d\n" , longueur_liste(l1));
afficher_liste(l1);
inserer_tete_liste(&l2 , -1);
inserer_queue_liste(&l2 , -2);
printf("Longueur de la liste l2 = %d\n" , longueur_liste(l2));
afficher_liste(l2);
}
Résultat de l’exécution
Longueur de la liste l1 = 5
11
10
10
1
0
Longueur de la liste l1 = 2
10
10
Longueur de la liste l1 = 3
10
9
10
Longueur de la liste l2 = 2
-1
-2
ASD2 – TI1-7 – Les listes
6/6