MODULE: INFORMATIQUE 4 /
STRUCTURE DE DONNÉES
(SMA 4/ SMI 4)
Pr. Yassine SADQI
Université Sultan Moulay Slimane (USMS)
Faculté Polydisciplinaire de Béni Mellal (FPBM)
Département de Mathématiques et Informatique
[email protected] Chapitre2 1
Rappel: Liste simplement chaînée
Définition: Une liste simplement chaînée est une structure de
données à l’intérieure de laquelle les objets sont ordonnés de
façon linéaire. À la différence d’un tableau, où l’ordre linéaire
est déterminé par les indices du tableau, l’ordre dans une
liste chaînée est déterminé par l'adresse de maillon suivant
ou une marque de fin s'il n'y a pas de suivant.
Exemple:
12.5 17.3 3.3 NULL
Cellule 2 Cellule 3
Cellule 1
Cellule ou bien maillon Queue de la liste
Tête de la liste
Chapitre2 2
Rappel: Liste simplement chaînée
Propriétés de base:
Une liste chaînée est constituée de 0 (liste vide) ou n
cellules (maillons).
Une liste chaînée est accessible uniquement par sa
tête de liste c’est-à-dire sa première cellule.
Sans la tête impossible de savoir où commence la
chaine et sans la queue impossible de savoir où elle
s'arrête.
Implémentation en langage C:
On réalise une liste chaînée en se basant sur la
notion de structure en C.
Chapitre2 3
Rappel: Exemple
Nous allons prendre un exemple simple d’une liste
contenant: (1) une donnée de type réel , et (2) un pointeur
« suivant ». La définition de cette structure en C est la
suivante:
typedef struct Cellule{
float donnee;
struct Cellule* suivant;
}TypeCellule;
Pointeur sur la cellule suivante
TypeCellule synonyme du nouveau type « struct Cellule »
Chapitre2 4
Rappel: Exemple
Puisque la liste est vide, le premier maillon prend la
valeur « NULL ». Pour cela, on déclare et initialise à
« NULL » un pointeur « L » vers le nouveau type crée
« TypeCellule »:
TypeCellule* L=NULL;
L NULL
Par la suite, il est possible de faire d’autres opérations,
telles que l’ajout, la suppression, la modification des
cellules.
Chapitre2 5
Chapitre 2: Les structures de
données linéaires (Partie 2)
Chapitre2 6
IV Principales opérations sur une liste chainée
Les listes chaînées autorisent les opérations de base
suivantes:
l’ajout ou l’insertion d’une cellule (1) en tête/ (2) en queue/
(3) en i-ème position
la suppression d’une cellule (1) en tête/ (2) en queue/ (3)
en i-ème position;
la recherche d’une donnée;
L’affichage des éléments de la liste.
Une liste chaînée, c’est un peu comme un fichier disque : des
maillons peuvent être ajoutés, modifiés ou supprimés, mais il
est indispensable d’ajuster les pointeurs de liaison (de
chaînage) lorsqu’on exécute ce type d’opération.
Chapitre2 7
IV Principales opérations sur une liste chainée
L NULL
L 12.5 NULL 1. Opération d’ajout d’une cellule
contenant la donnée 12.5
Cellule 1
L 12.5 3.3 NULL 2. Opération d’ajout d’une cellule
contenant la donnée 3.3
Cellule 1 Cellule 2
L 12.5 NULL 3. Opération de suppression de la cellule 2
Cellule 1
A bien noter: Sans l’adresse du premier maillon, on ne peut jamais
accéder à une liste chainée
Chapitre2 8
IV.1 Opération d’insertion
Soit « L » une liste chaînée
NULL
Cellule « A » Cellule « B » Cellule « C »
Oùl’insérer?
Début
Nouvelle_cellule
i-ème position
Fin
Si on désire insérer une nouvelle cellule, on a trois
possibilités: (1) en tête/ (2) en queue, ou bien (3) en i-ème
position.
Chapitre2 9
IV.1 Opération d’insertion
Point important: Dans tous les trois cas d’insertion, Il faut
toujours se rappeler de L. Puisque « L » stocke l’adresse
du premier maillon (pointeur vers la 1er cellule de la
chaine).
L
NULL
Cellule « A » Cellule « B » Cellule « C »
Oùl’insérer?
Début
Nouvelle_cellule
i-ème position
Fin
Chapitre2 10
IV.1.1 Insertion en tête
L’opération d’insertion en tête peut être réaliser en suivant les quatre
étapes suivantes:
o Etape1: Créer et allouer la mémoire pour la nouvelle cellule
« Nouvelle_Cellule »;
o Etape 2: Remplir le contenu du champ de données de
« Nouvelle_Cellule »; ;
o Etape 3 : Le pointeur « suivant » de la nouvelle cellule doit pointer
vers l’ancienne tête de liste. Dans notre exemple, l’adresse de
l’ancienne tête de liste est stocké dans « L ».
o Etape 4: Affecter au pointeur de tête de la liste « L » l’adresse de
« Nouvelle_Cellule »; .
L
chaînage
Nouvelle_Cellule Cellule « B »
Cellule « A » Cellule « C »
NULL
Chapitre2 11
II.4.1 Opération d’insertion
L
NULL
Cellule « A » Cellule « B » Cellule « C »
Avant l’insertion en tête
TypeCellule* Nouvelle_Cellule ; // Etape1: Déclarer un pointeur Nouvelle_Cellule vers TypeCellule
Nouvelle_Cellule = malloc(sizeof(TypeCellule)); // Etape1: Allouer la mémoire
Nouvelle_Cellule->donnee=12.5; // Etape2: Remplir la partie donnée de la cellule
Nouvelle_Cellule->suivant=L; // Etape 3: Chaînage
L=Nouvelle_Cellule; // Etape 4: Affecter à “L” l’adresse de “Nouvelle_Cellule”
Chaînage
L
Nouvelle_Cellule Cellule « A » Cellule « B » Cellule « C »
NULL
Après l’insertion en tête 12
II.4.1 Opération d’insertion
L
NULL
Cellule « A » Cellule « B » Cellule « C »
Nouvelle_cellule
Après l’opération d’insertion en queue
Chaînage
L
Cellule « A » Cellule « B » Cellule « C » Nouvelle_Cellule
NULL
Question: Comment peut-on insérer en queue la cellule
« Nouvelle_Cellule »? 13
II.4.1 Opération d’insertion
L
NULL
Cellule « A » Cellule « B » Cellule « C »
Nouvelle_cellule
Après l’opération d’insertion en queue
Chaînage
L
Cellule « A » Cellule « B » Cellule « C » Nouvelle_Cellule
NULL
Réponse: Le problème d’insertion en queue d’une liste chainée se
résume à un problème de parcours de la liste, afin de définir la
queue de la liste. 14
II.4.1 Opération d’insertion
Question: Comment peut-on parcourir une liste
chaînée?
L’approche standard consiste à utiliser un pointeur
temporaire, qui ne sera utilisé que pour cette tâche
de parcours. Il est initialisé au début de la liste, et
modifié par une boucle (voire une fonction
récursive).
L
NULL
Cellule « A » Cellule « B » Cellule « C »
P 15
II.4.1 Opération d’insertion
Exemple d’algorithme de parcours:
1. Déclarer un pointeur « p » de même type que la liste;
2. Faire pointer « p » sur la première cellule (tête de la
liste). L’adresse de la tête est stocké dans « L » ;
L
NULL
Cellule « A » Cellule « B » Cellule « C »
16
II.4.1 Opération d’insertion
Exemple d’algorithme de parcours:
1. Déclarer un pointeur « p » de même type que la liste;
2. Faire pointer « p » sur la première cellule (tête de la
liste);
3. Utiliser « p» pour se déplacer vers la cellule suivante;
L
NULL
Cellule « A » Cellule « B » Cellule « C »
P 17
II.4.1 Opération d’insertion
Exemple d’algorithme de parcours:
1. Déclarer un pointeur « p » de même type que la liste;
2. Faire pointer « p » sur la première cellule (tête de la
liste);
3. Utiliser « p » pour se déplacer vers la cellule suivante;
4. Le parcours s’arrête lorsque p vaut le suivant de la
dernière cellule (dans cette exemple c’est la cellule « C »).
L
NULL
Cellule « A » Cellule « B » Cellule « C »
P 18
II.4.1 Opération d’insertion
Méthode 1 de parcours
TypeCellule *p;
/* recherche de la dernière cellule */
for (p = L ; p->suivant!=NULL ; p=p->suivant)
{}
// à la fin de l’exécution de cette boucle p va stocker l’adresse de la
//cellule « C »
Méthode 2 de parcours
TypeCellule *p;
p = L; /* on pointe sur la première cellule */
while (p != NULL) /* tant qu’il y a une cellule */
{
*/
p = p->suivant; /* on passe à la cellule suivante */
}
19
TP1
Chapitre2 20
