INF1301 : Structures de données et Programmation,

Systèmes d'exploitation
EC1 : Structures de données et programmation

Dr Coulibaly Kadidiatou DJIBO

October 19, 2022

Plan du cours

1 Cours introductif

2 Les listes

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 2 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 3 / 54
Qu'est ce qu'une structure de données ?

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 4 / 54
Qu'est ce qu'une structure de données ?

Dénition
Les données informatiques désignent les informations qui sont stockées
ou traitées par des ordinateurs. Ces informations sont optimisées pour
le traitement et le déplacement, des faits et des chires stockés sur des
ordinateurs.
Les structures de données encore appelées Data Structure sont une
manière spécique d'organiser les données dans un format spécialisé sur
organisées,
un ordinateur an que les informations puissent être
traitées, stockées et récupérées rapidement et ecacement .
Ainsi, elles constituent un moyen de traiter l'information, en rendant les
données faciles à utiliser.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 5 / 54
Qu'est ce qu'une structure de données ?

En programmation informatique, une structure de données peut être

sélectionnée ou conçue pour stocker des données de manière à pouvoir les
manipuler à l'aide de plusieurs algorithmes. Chaque structure de données
contient des informations sur la valeur des données, les relations entre elles
et les fonctions applicables.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 6 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 7 / 54
Caractéristiques des structures de données

Les structures de données sont souvent classées en fonction de leurs

caractéristiques. Les principales sont :
Linéaires ou non linéaires :
cette caractéristique indique si les éléments de données sont organisés
chronologiquement, comme dans un tableau, ou de façon non ordonnée,
comme dans un graphe.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 8 / 54
Caractéristiques des structures de données

Les structures de données sont souvent classées en fonction de leurs

caractéristiques. Les principales caractéristiques sont :
Homogènes ou non homogènes :
cette caractéristique indique si tous les éléments de données d'un référentiel
spécique sont du même type ou de types diérents.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 9 / 54
Caractéristiques des structures de données

Les structures de données sont souvent classées en fonction de leurs

caractéristiques. Les principales caractéristiques sont :
Statiques ou dynamiques :
cette caractéristique décrit la façon dont les structures de données sont
compilées. Les structures statiques présentent des tailles, des structures et
des emplacements de mémoire xes au moment de la compilation. Dans une
structure de données dynamique, en revanche, la taille, les structures et les
emplacements de mémoire peuvent diminuer ou s'agrandir, selon l'utilisation
qui en est faite.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 10 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 11 / 54
Types de structures de données

Le type d'une structure de données est déterminé par les types d'opérations
requis ou les types d'algorithmes qui seront appliqués. Les principaux types
sont :
le tableau,
la pile,
la le,
la liste chainée,
les arbres,
le graphe,
le trie,
les tables de hachage.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 12 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 13 / 54
Importance des structures de données
Organiser le code et les informations dans l'espace numérique.
I Exemple : les listes et les dictionnaires Python, les tableaux et objets
JavaScript sont des structures de codage couramment utilisées pour
stocker et récupérer des informations.
Elles constituent un élément essentiel dans la conception de logiciels
ecaces.
Indispensables pour gérer ecacement de grandes quantités de
données, comme les informations stockées dans une base de données ou
des services d'indexation.
Les facteurs à prendre en compte lors du choix d'une structure de
données : le type d'information qui sera stocké, l'emplacement de
stockage des données existantes, le mode de stockage des données et la
quantité de mémoire à réserver aux données.
un mauvais choix pourrait entraîner un ralentissement des temps de
traitement ou une absence de réponse du programme.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 14 / 54
Importance des structures de données
Organiser le code et les informations dans l'espace numérique.
I Exemple : les listes et les dictionnaires Python, les tableaux et objets
JavaScript sont des structures de codage couramment utilisées pour
stocker et récupérer des informations.
Elles constituent un élément essentiel dans la conception de logiciels
ecaces.
Indispensables pour gérer ecacement de grandes quantités de
données, comme les informations stockées dans une base de données ou
des services d'indexation.
Les facteurs à prendre en compte lors du choix d'une structure de
données : le type d'information qui sera stocké, l'emplacement de
stockage des données existantes, le mode de stockage des données et la
quantité de mémoire à réserver aux données.
un mauvais choix pourrait entraîner un ralentissement des temps de
traitement ou une absence de réponse du programme.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 14 / 54
Importance des structures de données
Organiser le code et les informations dans l'espace numérique.
I Exemple : les listes et les dictionnaires Python, les tableaux et objets
JavaScript sont des structures de codage couramment utilisées pour
stocker et récupérer des informations.
Elles constituent un élément essentiel dans la conception de logiciels
ecaces.
Indispensables pour gérer ecacement de grandes quantités de
données, comme les informations stockées dans une base de données ou
des services d'indexation.
Les facteurs à prendre en compte lors du choix d'une structure de
données : le type d'information qui sera stocké, l'emplacement de
stockage des données existantes, le mode de stockage des données et la
quantité de mémoire à réserver aux données.
un mauvais choix pourrait entraîner un ralentissement des temps de
traitement ou une absence de réponse du programme.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 14 / 54
Importance des structures de données
Organiser le code et les informations dans l'espace numérique.
I Exemple : les listes et les dictionnaires Python, les tableaux et objets
JavaScript sont des structures de codage couramment utilisées pour
stocker et récupérer des informations.
Elles constituent un élément essentiel dans la conception de logiciels
ecaces.
Indispensables pour gérer ecacement de grandes quantités de
données, comme les informations stockées dans une base de données ou
des services d'indexation.
Les facteurs à prendre en compte lors du choix d'une structure de
données : le type d'information qui sera stocké, l'emplacement de
stockage des données existantes, le mode de stockage des données et la
quantité de mémoire à réserver aux données.
un mauvais choix pourrait entraîner un ralentissement des temps de
traitement ou une absence de réponse du programme.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 14 / 54
Qu'est ce qu'une liste ?

Une liste est une collection nie d'éléments qui se suivent. C'est donc une
structure de données séquentielle ou linéaire.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 15 / 54
Qu'est ce qu'une liste ?

Une liste est une collection nie d'éléments qui se suivent. C'est donc une
structure de données séquentielle ou linéaire.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 15 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 16 / 54
Les listes simples

Dénition
Une liste est un ensemble d'objets de même type constituant les éléments de
la liste. Les éléments sont chaînés entre eux et on peut facilement ajouter
ou extraire un ou plusieurs éléments. Une liste simple est une structure de
données telle que chaque élément contient :
Des informations caractéristiques de l'application (les caractéristiques
d'une personne par exemple),
un pointeur vers un autre élément ou une marque de n s'il n'y a pas
d'élément successeur.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 17 / 54
Les listes simples
Une liste d'attente de patients chez un médecin

Figure: 2.1 : Liste de patients en salle d'attente

Quel est le troisième élément de la liste ?

Et le dernier élément ?
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 18 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 19 / 54
Représentation en mémoire des listes

Nous identions deux modes de représentation en mémoire des listes. Il

s'agit de :
L'allocation dynamique et
l'allocation contiguë.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 20 / 54
Représentation en mémoire des listes

Allocation dynamique
En allocation dynamique à la demande :
L'espace est réservé au fur et à mesure des créations d'éléments.
La seule limite est la taille de la mémoire centrale de l'ordinateur ou
l'espace mémoire alloué au processus.
Les diérents éléments sont dispersés en mémoire centrale.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 21 / 54
Représentation en mémoire des listes

Allocation contiguë
En allocation contiguë :
L'espace est réservé sur des cases consécutives avec une dimension
maximale (lgMax sur le schéma) à préciser lors de cette réservation
Si la limite est trop basse, on ne peut résoudre les problèmes ayant de
nombreuses valeurs, ou alors, il faut réallouer une zone plus grande et
déplacer les informations.
Si la limite est trop grande, l'espace est alloué inutilement

L'allocation dynamique à la demande présente beaucoup plus de

souplesse puisqu'il n'y a pas de limite à xer.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 22 / 54
Représentation en mémoire des listes

Exemple

Figure: 2.2 : Liste de patients en salle d'attente

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 23 / 54
Représentation en mémoire des listes

Allocation dynamique (à la demande)

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 24 / 54
Plan de la présentation
1 Cours introductif
Qu'est ce qu'une structure de données ?
Caractéristiques des structures de données
Types de structures de données
Importance des structures de données
2 Les listes
Les listes simples
Représentation en mémoire des listes
Module de gestion des listes
Les fonctions d'insertion

Les fonctions de parcours de liste

Retrait d'un objet de liste

Destruction de listes

Recopie de listes

Types de listes

Liste doublement chaînée

Liste circulaire

Les piles

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 25 / 54
Module de gestion des listes
Un élément de liste contient toujours un pointeur sur l'élément suivant
ou une marque indiquant qu'il n'y a plus de suivant (marque NULL en
C).
La liste peut être représentée par un pointeur sur le premier élément de
la liste.
Le type Liste peut ausi être déni comme une structure contenant trois
pointeurs d'éléments
I Un pointeur sur le premier élément et un pointeur sur le dernier élément
de façon à faciliter les insertions en tête et en n de liste;
I et un pointeur courant qui repère l'élément courant à traiter pour
faciliter le parcours des listes.
I Le nombre d'éléments est également inséré dans la tête de liste, ainsi
que le type de la liste (non ordonnée, ordonnée croissante ou ordonnée
décroissante).
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 26 / 54
Module de gestion des listes
Les déclarations correspondantes pour l'allocation dynamique à la demande
sont les suivantes :

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 27 / 54
Module de gestion des listes

Une liste ne contenant aucun élément a ses trois pointeurs à NULL

pour indiquer qu'il n'y a ni premier, ni dernier, ni élément courant.

Figure: 2.3 : Liste vide

li est l'adresse d'une structure de type Liste ;

La barre oblique (/) représente NULL sur la Figure 23.
li → premier : indique le champ premier de la structure pointée par li.
Par défaut, l'objet référencé par l'élément de liste est une chaîne de
caractères.
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 28 / 54
Module de gestion des listes

Fonctions de création d'un élément de liste

La liste contient des éléments ; chaque élément référence un objet
spécique de l'application.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 29 / 54
Module de gestion des listes

Fonctions de création d'une liste

Fournir le nombre d'éléments dans la liste.

Si l liste est vide, la fonction retourne 0.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 30 / 54
Les fonctions d'insertion

Ajout d'un objet en tête de liste

insérer objet en tête de la liste li
l'objet est repéré par le champ reference de l'élément de la liste

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 31 / 54
Les fonctions d'insertion

Ajout d'un objet en tête de liste

Insertion d'objet en tête de la liste li de type 0 (non ordonnée). Après
insertion, la liste contient 3 éléments.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 32 / 54
Les fonctions d'insertion
Ajout après l'élément précédent
L'élément doit être ajouté à une place particulière après l'élément
precedent.
Il faut d'abord trouver l'élément precedent avant d'appeler la fonction
insererApres() .

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 33 / 54
Les fonctions d'insertion
Ajout après l'élément précédent
Insertion de nouveau (référençant objet) dans la liste li, après l'élément
pointé par precedent.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 34 / 54
Les fonctions d'insertion

Ajout en n de liste
L'ajout en n de liste se fait en tête de liste si la liste est vide ou après
le dernier élément si la liste contient déjà un élément.
La fonction précédente peut donc être utilisée pour dénir cette
fonction.
Le pointeur sur le dernier élément conservé dans la tête de liste permet
une insertion en n de liste rapide sans parcours de la liste pour se
positionner sur le dernier élément. Si la liste est vide, li -> dernier vaut
NULL.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 35 / 54
Les fonctions de parcours de liste

Permettent à l'utilisateur du module liste de parcourir une liste en

faisant abstraction des structures de données sous-jacentes;
Ces fonctions s'apparentent à celles utilisées pour parcourir
séquentiellement les chiers;
L'utilisateur a besoin de se positionner en début de liste, de demander
l'objet suivant de la liste, et de savoir s'il a atteint la n de la liste.
L'utilisateur n'accède pas aux champs de la structure de la tête de liste
(premier, dernier, courant), ni au champ suivant des éléments.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 36 / 54
Les fonctions de parcours de liste

Se positionner sur le premier élément de la liste li.

void ouvrirListe(Liste* li) {
li -> courant = li -> premier;
}
La fonction booléenne nListe() indique si on a atteint la n de la liste
li ouverte préalablement par ouvrirListe().
booleen nListe(Liste* li) {
return li -> courant == NULL;
}

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 37 / 54
Les fonctions de parcours de liste

La fonction locale elementCourant() fournit un pointeur sur l'élément

courant de la liste li et se positionne sur l'élément suivant qui devient
l'élément courant.
static Element* elementCourant(Liste* li) {
Element* ptc = li->courant;
return li -> courant == NULL;
if (li->courant != NULL) {
li->courant = li->courant->suivant;
}
return ptc;
}

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 38 / 54
Les fonctions de parcours de liste

La fonction listerListe(Liste* li) eectue un parcours complet de la liste

ache les éléments de liste au fur et à mesure
void listerListe (Liste* li) {
ouvrirListe (li);
while (!nListe (li)) {
Objet* objet = objetCourant (li);
printf ("%s\n", li->toString (objet)); }
}

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 39 / 54
Les fonctions de parcours de liste

La fonction chercherUnObjet() eectue un parcours de liste en

comparant l'objet cherché et l'objet courant de la liste.
Une fonction de comparaison est utilisée, retourne 0 si les duex
éléments correspondent
Objet* chercherUnObjet (Liste* li, Objet* objetChercher) {
booleen trouve = faux; Objet* objet;
ouvrirListe (li);
while (!nListe (li) && !trouve) {
objet = objetCourant (li);
trouve = li->comparer (objetChercher, objet) == 0;
}
return trouve ? objet : NULL;
}
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 40 / 54
Retrait d'un objet de liste
Retrait en tête de liste
Il s'agit de retirer l'objet en tête de la liste pointée par li, et de fournir
un pointeur sur l'objet extrait.
Si la liste est vide, on ne peut retirer aucun élément, la fonction
retourne NULL pour indiquer un échec.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 41 / 54
Retrait d'un objet de liste

Retrait en tête de liste

Objet* extraireEnTeteDeListe (Liste* li) {
Element* extrait = li->premier;
if (!listeVide(li)) {
li->premier = li->premier->suivant;
if (li->premier==NULL) li->dernier=NULL; // Liste devenue vide
li->nbElt - -;
}
return extrait != NULL ? extrait->reference : NULL;
}

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 42 / 54
Retrait d'un objet de liste

De même, il est possible de :

Rétirer l'objet en n de liste
I Connaître l'avant-dernier pour en modier le pointeur suivant.
I Faire un parcours de la liste pour repérer le précédent du dernier.
Retirer un objet à partir de sa référence
I extrait un objet connaissant un pointeur sur cet objet.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 43 / 54
Les fonctions de parcours de liste

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 44 / 54
Destruction de listes
Eectuer un parcours de liste avec destruction de chaque élément.
La tête de liste est réinitialisée. Il faut se positionner en début de liste,
et tant qu'on n'a pas atteint la n de la liste, il faut prendre l'élément
courant et le détruire.
Le pointeur sur le prochain élément est conservé dans le champ courant
de la tête de liste.
void detruireListe (Liste* li) {
ouvrirListe (li);
while (!nListe (li)) {
Element* ptc = elementCourant (li);
free (ptc); }
initListe (li);
}
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 45 / 54
Recopie de listes

permet de transférer la liste x dans la liste y en réinitialisant la liste y

qui est vide.
void recopierListe (Liste* x, Liste* y) {
detruireListe (x);
*x = *y;
initListe (y);
}

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 46 / 54
Types de listes

Liste chaînée simple constituée d'éléments reliés entre eux par des
pointeurs.
Liste chaînée ordonnée où l'élément suivant est plus grand que le
précédent. L'insertion et la suppression d'élément se font de façon à ce
que la liste reste triée.
Liste doublement chaînée où chaque élément dispose non plus d'un
mais de deux pointeurs pointant respectivement sur l'élément précédent
et l'élément suivant. Ceci permet de lire la liste dans les deux sens, du
premier vers le dernier élément ou inversement.
Liste circulaire où le dernier élément pointe sur le premier élément de
la liste. S'il s'agit d'une liste doublement chaînée alors de premier
élément pointe également sur le dernier.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 47 / 54
Liste doublement chaînée

Une liste est dite doublement chaînée si chaque n÷ud de cette liste
contient :
I une partie donnée,
I un pointeur sur l'élément suivant,
I un pointeur sur l'élément précédent
C'est une liste simplement chaînée avec en plus un chainage arrière.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 48 / 54
Liste circulaire
Une liste est dite circulaire si :
I le dernier n÷ud de cette liste a un pointeur sur leu premier n÷ud de
cette liste ;
I cela implique que la case pointeur du dernier élément ne contient pas
Nil mais l'adresse du premier élément (tete).
Il n'est pas recommandé de traiter les n élément de cette liste, mais
plutôt les n − 1 éléments ensemble et de s'assurer à repeter le
traitement uniquement sur les noeuds non traités.
utiliser la boucle répéter au lieu du Tantque.

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 49 / 54
Les piles

Une pile : LIFO

Une pile est une liste d'objets auxquels on ne peut accéder que par le
dessus
C'est à dire dans l'ordre LIFO = Last In First Out.
Exemples : une pile de cahiers...
NB : Une pile peut être implémentée à l'aide d'une liste chaînée
typedef struct pi pile
struct pi {
int info;
struct pile *prec;
}

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 50 / 54
Les piles

Opérations sur les piles

Les opérations possibles sont :
empiler un nouvel élément au sommet de la pile;
dépiler l'élément qui était au sommet de la pile;
acher tous les éléments : le sommet, puis le reste de la pile;
tester si la pile est vide ou non...

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 51 / 54
Les les
Une le : FIFO
Une le est une liste d'objets où :
l'on accède par la queue
En se déplaçant, on ressort par la tête.
C'est à dire dans l'ordre First In First Out
Exemple : La le d'attente devant le guichet d'inscription
Une le peut être implémentée à l'aide d'une liste chaînée :
typedef struct  le
struct  {
int info;
struct le *suiv;
}
Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes
October
d'exploitation
19, 2022 52 / 54
Les les

Opérations sur les les

Deux éléements sont importants dans une le : le premier et le dernier
ajouter un nouvel éléement en queue, donc le dernier ;
retirer l'élément de tête de la le, donc le premier
acher tous les éléments de la le;
tester si une le est vide ou non

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 53 / 54
 Fin !

Dr Coulibaly Kadidiatou DJIBO INF1301 : Structures de données et Programmation, Systèmes

October
d'exploitation
19, 2022 54 / 54