Chapitre 3 Les listes chainées

1
Limite des tableaux

Taille connue et fixe des éléments

Insertion et suppression dynamiques non pratiques
Allocation d’un seul bloque en mémoire
D’où les listes :
Taille, inconnue au départ, elle varie au cours du temps
Insertion et suppression dynamiques pratiques
Les éléments sont habituellement éparpillés en mémoire
• Les listes chainées sont des structures composées de cellules.
• Chaque cellules contient deux champs (ou trois selon le types de la liste) le
premier contient la variable et le deuxième un pointeur vers la cellule qui
suit.
• De cette façon, on peut enregistrer les cellules dans n'importe quelle case
mémoire entier .Néanmoins, il faut garder l'adresse de la tête de la liste.
Ainsi, puisque chaque cellule a un lien vers son successeur (l'adresse de la
cellule qui suit), on peut trouver tout le reste de la liste.
• Avec les listes chainées, le compilateur n'est pas obligé de trouver des
cases successives vides dans la mémoire. Ces cases peuvent êtres
éparpillées dans toute la mémoire ce qui constitue un gain considérable.
• Une liste chaînée est un ensemble d’éléments contenus chacun dans
une cellule (ou nœud ou maillon).
• Chaque cellule contient, en plus de l’élément, l’adresse de l’élément
suivant appelée pointeur.
 Une liste chainée est une structure dynamique formée de nœuds reliés par
des liens.

19/04/2023 5
 - Représentation d’une liste chainée

L’élément de base d’une liste chaînée s’appelle le nœud. Il est constitué :

– d’un champ de données ;
– d’un pointeur vers un nœud.

19/04/2023 6
Nœud suivant
Le champ pointeur vers un nœud pointe vers le nœud suivant de la liste. S’il
n’y a pas de nœud suivant, le pointeur vaut NULL.

Notion de liste
Une liste simplement chaînée est un pointeur sur un nœud. Une liste vide est
une liste qui ne contient pas de nœud. Elle a donc la valeur NULL.

Définitions
La terminologie suivante est généralement employée :
– le premier nœud de la liste est appelé tête ;
– le dernier nœud de la liste est appelé queue.

7
19/04/2023 8
 Deux manières de définir une liste chainée

1- Liste chainée itérative

2- Liste chainée récursive

Vision itérative / vision récursive

Une liste chaînée est manipulée à l'aide d'un pointeur vers son premier élément.
Plus généralement, tout pointeur vers Nœud peut donc être vu de deux manière :
1- comme pointant vers un élément d'une liste,
•Nœud représente un élément, avec une valeur, et pointant vers l'élément
suivant,

 Une liste itérative : chaque élément permet d'accéder à l'élément suivant

19/04/2023 9
 Deux manières de définir une liste chainée

1- Liste chainée itérative

2- Liste chainée récursive

Vision itérative / vision récursive

Une liste chaînée est manipulée à l'aide d'un pointeur vers son premier élément.
Plus généralement, tout pointeur vers Nœud peut donc être vu de deux manière :
2- comme pointant vers une liste, via son premier élément.
•Nœud représente une liste, avec sa première valeur, et pointant vers la
liste des éléments suivants.

 Une liste récursive : chaque élément permet d'accéder à la liste d'éléments suivants

19/04/2023 10
 Liste chainée itérative
Principe: Définir la liste chainée itérative en prenant comme opérations de
base:

• L’accès à toutes les positions des nœuds

• L’insertion
• La suppression

19/04/2023 11
 Les opérations sur une liste chainée itérative

créer une liste : liste creer(void);

Tester si une liste est vide : int estvide(liste );

Insérer un élément à la tête d’une liste : liste inserer_tete(liste list, int val);

Insérer un élément à la queue d’une liste : liste inserer_fin(liste list, int val);

Supprimer un élément ayant la valeur val: liste supprimer(liste list, int val);

Déterminer la longueur d’une liste : int longueur(liste list);

Afficher les éléments d’une liste : void affichage(liste list);

19/04/2023 12
 - programmes en C des opérations d’une liste chainée itérative

int estvide(liste list)

{
if (list==NULL)
return (1);
else
return (0);
}

19/04/2023 13
 liste inserer_tete(liste list, int valeur)
{
liste list_i;
if ((list_i = (liste)malloc(sizeof(Noeud))) == NULL)
{ printf ("erreur allocation");
exit(1);
}
list_ivaleur = valeur;
list_isuivant = list;
return(list_i);
}

19/04/2023 14
 liste inserer_queue(liste list, int valeur)
{
liste list_i, list_move;
if((list_i = (liste )malloc(sizeof(Noeud))) == NULL)
{ printf(" erreur allocation "); exit(1); }
//creation noeud
list_i valeur = valeur;
list_i suivant= NULL;

if(list == NULL)
return(list_i);
// insertion queue
else
list_move= list;
// parcours Liste
while (list_move suivant!=NULL)
list_move=list_move suivant;

list_move suivant = list_i;

19/04/2023
return(list); 15
}
liste supprimer(liste list, int valeur)
{
liste list_move, before_list_move, vlist_tampon;
before_list_move = NULL;
list_move=list;
while ((list_move !=NULL) && (list_move valeur !=valeur))
{
before_list_move=list_move;
list_move=list_move suivant;
}
if(list_move == NULL) // élément non trouvé
return(list);
else
{ if(before_list_move == NULL) // si le 1er élément est l’élément cherché
{ vlist_tampon = list_move suivant;
free(list_move);
return(vlist_tampon); }
else { // si l’élément cherché est au milieu ou à la fin de la liste
before_list_movesuivant = list_move suivant;
free(list_move);
return(list); } } }
19/04/2023 16
 int longueur(liste list)
{
liste p_maillon = list;
int lon = 0;

while (p_maillon != NULL)

{
lon++;
p_maillon = p_maillon suivant;
}
return (lon);
}

19/04/2023 17
void affichage(liste list)
{
liste p_maillon = list;

if(p_maillon ==NULL)
printf("liste vide\n") ;
else
{
while (p_maillon !=NULL)
{
printf("%d ", p_maillon valeur);
p_maillon=p_maillon suivant ;
}
}
}

19/04/2023 18
Application

On considère la structure Employe définie par :

- une matricule : un entier
- Nom : chaîne de caractères
- Prénom : chaîne de caractères
- Ancienneté : un entier

Ecrire un programme qui permet de :

1. Saisir une liste chaînée de N employés
2. Ajouter un employé à la fin de la liste
3. Supprimer l'employé le plus ancien
4. Afficher la liste ainsi obtenue
typedef struct
{
int mat;
char nom[20];
char prenom[20];
int ancien;
}Employe;

typedef struct BD_Emp

{
Employe emp;
struct BD_Emp* suiv;
}BD_Emp;

typedef BD_Emp* llist;

int main()
{
int i;
llist ma_liste1 = NULL;
Employe employee;
for(i=1;i<=5;i++)
{
employee=saisir();
ma_liste1 = ajouterEnFin(ma_liste1, employee);
}
printf(" La liste initialement remplie");
affich(ma_liste1);

employee=saisir();
ma_liste1 = ajouterEnFin(ma_liste1, employee);
printf(" \n La liste apres rajout ");
affich(ma_liste1);
printf(" \n La liste apres suppression de l\'employe le plus ancien \n
");
ma_liste1=Supp-ancien(ma_liste1);
affich(ma_liste1);

return 0;
}
Employe saisir()
{
Employe empl;
printf("Saisir matricule employe \n");
scanf("%d",&empl.mat);
printf("Saisir nom employe \n");
scanf("%s",empl.nom);
printf("Saisir prenom employe \n");
scanf("%s",empl.prenom);
printf("Saisir anciennete employe\n");
scanf("%d",&empl.ancien);
return empl;
}
llist ajouterEnFin(llist liste, Employe e)
{
/* On crée un nouvel élément */
BD_Emp* nouvelEmploye, temp=liste;

nouvelEmploye=(BD_Emp*)malloc(sizeof(BD_Emp));

/* On assigne la valeur au nouvel élément */

nouvelEmploye->emp = e;
nouvelEmploye->suiv = NULL;
if(liste == NULL)
return nouvelEmploye;
else
{
while(temp->suiv != NULL)
temp = temp->suiv;

temp->suiv = nouvelEmploye;
return liste;
}
}
void affich(llist liste)
{
BD_Emp *temp=liste;
while(temp != NULL)
{
printf("{ %d %s %s %d }-> \n",temp->emp.mat,temp->emp.nom,temp->emp.prenom,temp-
>emp.ancien);
temp = temp->suiv;
}

}
llist Supp-ancien( llist liste)
{
llist temp = liste;
llist pmax, prec,precmax;
int max= temp->emp.ancien;
precmax=NULL;
prec= temp;
pmax=temp;
temp=temp->suiv;

while (temp->suiv ) {
if(temp->emp.ancien > max)
{max = temp->emp.ancien;precmax=prec; pmax=temp;}
prec=temp;
temp = temp->suiv;
}
if (precmax == NULL) {liste= pmax->suiv ; free(pmax); return liste ; }
if (temp->suiv == NULL && temp->emp.ancien > max)
{max = temp->emp.ancien;precmax=prec;pmax=temp;}

precmax->suiv=pmax->suiv;

return liste ;
}