STRUCTURE DE DONNEES

Chapitre 1 : Notions générales

A/ Objectifs du cours
Ce cours vise à initier les étudiants aux structures de données fondamentales et avancées,
essentielles pour la conception et l’optimisation des algorithmes en génie logiciel. Il permet
d’acquérir les compétences nécessaires pour choisir et implémenter efficacement les
structures adaptées à divers problèmes informatiques.

Objectifs généraux :
 Comprendre les principes fondamentaux des structures de données et leur impact sur
la performance
 Savoir choisir la structure de données la plus appropriée en fonction des contraintes et
des exigences
 Maîtriser les concepts d’allocation dynamique et de gestion de la mémoire.

B/ Plan du cours
1. Introduction aux structures de données
 Définition
 Différences entre structures de données statiques et dynamiques
 Analyse
2. Structures de données linéaires
 Tableaux : déclaration, manipulation et optimisation
 Listes chaînées :simple
 **Hémorroïdes
 Fichiers (FIFO) :
3. Structures de données arborescentes
 Arbres binaires : définition, insertion, suppression et parcours (préfixé, infixé,
postfixé)
 **Arbres de recherche binaires (BST)
 Arbres AVL et Red-Black : auto-équilibrage et applications
**4. Structure
 Graphiques :
 Parcours de graphes : DFS (Depth First Search) et BFS (Breadth First Search)
 Algorithmes de plus court chemin : Dijkstra, Bellman-Ford
5. Gestion de la mémoire et allocation dynamique
 Pointeurs et allocation dynamique en C
 Gestion des fuites mémoire et utilisation des structures adaptées
 Implémentation des listes et arbres en mémoire dynamique
6. Applications avancées et optimisation
 Utilisation des structures de données pour le stockage et la manipulation efficace des
données
 Applications dans la gestion des bases de données et les systèmes de fichiers
 Analyse et comparaison des performances des structures de données

Page 1 sur 191

C/ Compétences acquises à la fin du cours :
 Concevoir et implémenter différentes structures de données
 Résoudre des problèmes algorithmiques en utilisant les structures appropriées
 Analyser et optimiser les performances des structures de données
 Comprendre les principes de gestion de la mémoire et les appliquer efficacement

D/ La compétence en informatique c’est quoi ?

En informatique, une compétence désigne la capacité d'une personne à appliquer ses
connaissances et son savoir-faire pour résoudre des problèmes techniques, concevoir des
solutions et utiliser efficacement les outils et technologies informatiques.

Les compétences en informatique peuvent être classées en plusieurs catégories :

1. Compétences techniques (Hard Skills)

 Programmation : maîtrise de langages comme C, Java, Python, etc.

 Base de données : SQL, NoSQL, conception et gestion de bases de données.
 Développement Web : HTML, CSS, JavaScript, frameworks (React, Angular).
 Systèmes et Réseaux : administration de serveurs, protocoles de communication.
 Sécurité informatique : cryptographie, gestion des vulnérabilités.
 Analyse des données et Big Data : manipulation et traitement de grandes quantités de
données.
 Cloud Computing : AWS, Azure, Google Cloud.
 Intelligence Artificielle et Machine Learning : apprentissage automatique, réseaux
de neurones.
 Cybersécurité : protection des systèmes et réseaux contre les cyberattaques.

2. Compétences analytiques

 Résolution de problèmes.
 Algorithmes et structures de données.
 Modélisation UML pour la conception de logiciels.
 Optimisation des performances d’un système informatique.

3. Compétences en gestion de projet

 Méthodologies Agile, Scrum, Kanban.

 Gestion des versions avec Git.
 Rédaction de documentation technique.

4. Compétences en communication et travail collaboratif (Soft Skills)

 Capacité à expliquer des concepts techniques à des non-techniciens.

 Travail en équipe sur des projets informatiques.
 Adaptabilité aux nouvelles technologies.

📌 Pourquoi les compétences sont-elles importantes en informatique ?

Page 2 sur 191

  Elles permettent d’exercer des métiers variés : développeur, administrateur système,
analyste en cybersécurité, data scientist, etc.
 Elles facilitent la résolution de problèmes techniques et l’innovation.
 Elles sont essentielles pour s’adapter à l’évolution rapide des technologies.

E/ Champ d’application des structures de données

 Développement de logiciels : conception d’algorithmes efficaces pour les applications

mobiles, web et bureautiques.
 Bases de données : indexation et recherche optimisée des informations.
 Systèmes d’exploitation : gestion des processus, mémoire et fichiers.
 Intelligence artificielle et Big Data : traitement et structuration de grandes quantités
de données.
 Réseaux et télécommunications : routage des paquets, gestion des connexions et
optimisation des flux.
 Sécurité informatique : cryptographie et gestion des accès sécurisés.

F/ Introduction aux structures de données

Définition

Une structure de données est une manière d’organiser, de stocker et de gérer les données
afin d’en faciliter l’accès et la manipulation de manière efficace. Elle permet d’optimiser le
traitement des informations en fonction des besoins spécifiques d’un programme ou d’un
système informatique.

Les structures de données sont essentielles en informatique et en génie logiciel, car elles
influencent la performance des algorithmes en termes de temps d’exécution et d’utilisation de
la mémoire.

Classification des structures de données

Les structures de données peuvent être classées en deux grandes catégories :

1. Structures de données linéaires

o Les éléments
o Exemples :
 Tableaux
 Listes chaînées
 Piles (LIFO)
 Files (FIFO)
2. Structures de données non linéaires
o Les éléments sont organisés de manière hiérarchique ou relationnelle.
o Exemples :
 Arbres (arbres binaires, arbres de recherche)
 Graphes (matrices d'adjacence, listes d’adjacence)

Page 3 sur 191

Les structures de données sont fondamentales en programmation et jouent un rôle clé dans la
résolution de nombreux problèmes en génie logiciel. 🚀

Différences entre structures de données statiques et dynamiques

Structures de Données
Critères Structures de Données Statiques
Dynamiques
Les structures de données statiques ont Les structures de données
Définition une taille fixe définie au moment de la dynamiques peuvent changer de
compilation. taille à l’exécution.
L’allocation mémoire est faite à la L’allocation mémoire est effectuée
compilation (mémoire statique ou dynamiquement à l’exécution
pile). (tas/heap).
La mémoire est réservée même si elle
Gestion de la La mémoire est allouée et libérée
n’est pas totalement utilisée, ce qui
mémoire dynamiquement selon les besoins
peut entraîner du gaspillage.
Modification de Peut être modifiée dynamiquement
Imposer
la taille (ajout ou suppression d’éléments).
L’accès peut être plus lent car il
Accès aux L’accès est plus rapide car la mémoire
nécessite des pointeurs pour
éléments est contiguë et indexée directement.
naviguer dans la structure.
Exemples - Listes chaînées (simple, double,
- Tableaux statiques
courants circulaire)
- Statistiques des matrices -Hémorroïdes
- Corrections de structures - Arbres et graphes dynamiques
Recommandé pour les situations où la Recommandé pour les cas où la
Utilisation taille des données est connue à taille des données varie
l’avance et ne change pas. fréquemment.

3. Exemples d’application selon les besoins

Structure
Problème Justification
recommandée
Accès rapide et gestion efficace
Stockage de données fixes Tableau statique
si la taille est connue.
Plus flexible qu’un tableau
Manipulation fréquente d’éléments
Liste chaînée pour l’insertion et la
(addition/suppression)
suppression.
Gestion d’un historique ou d’une Permet une gestion efficace du
Pile (LIFO)
pile d’exécution dernier entré, premier sorti.
Gestion des tâches dans un Idéale pour la gestion des
Fichier (FIFO)
système d’exploitation processus et files d’attente.
Stockage structuré en hiérarchie Représente naturellement les
Arbre
(ex. système de fichiers) relations parent-enfant.
Optimisation des trajets et des Graphe Permet de représenter des

Page 4 sur 191

 Structure
Problème Justification
recommandée
réseaux relations complexes entre
objets.

Chapitre 2. Structures de données linéaires : Tableaux

Les tableaux (ou Tableaux) sont des structures de données linéaires utilisées pour stocker
des éléments du même type en mémoire contiguë. Ils permettent un accès rapide aux éléments
via leur index, mais présentent certaines limitations en termes de flexibilité.

1. Déclaration des tableaux en C

En langage C, un tableau peut être déclaré de la manière suivante :

Déclaration et initial

// Déclaration d'un tableau de 5 entiers

int T[5];

// Initialisation avec des valeurs

int T1[5] = {10, 20, 30, 40, 50};

// Déclaration et initialisation automatique

int T2[] = {1, 2, 3, 4, 5};
 La taille doit être spécifiée sauf si on initialise directement avec des valeurs.
 Tous les éléments d’un tableau sont du même type.

2. Manipuler
[Link]ès

L’accès à un élément du tableau se fait via son Indice :

int T[5] = {10, 20, 30, 40, 50};

printf("Premier élément : %d\n", T[0]); // Affiche 10
printf("Troisième élément : %d\n", T[2]); // Affiche 30

b. Parcours d’un tableau

1. Parcours avec une boucle pour

T[5] = {10, 20, 30, 40, 50};
for(int i = 0; i < 5; i++) {
printf("Élément %d : %d\n", i, T[i]);
Page 5 sur 191
}

2. Parcours avec une boucle '

int T[5] = {10, 20, 30, 40, 50};

int i = 0;
while(i < 5) {
printf("Élément %d : %d\n", i, T[i]);
i++;
}

c. Modification des éléments

int T[3] = {1, 2, 3};

T[1] = 10; // Remplace l’élément à l’index 1 (2 devient 10)
printf("%d\n", tab[1]); // Affiche 10

3. Optimisation des tableaux

Problèmes liés aux tableaux statiques

 Taille fixe : On ne peut pas modifier la taille après allocation.

 Perte de mémoire : Un tableau peut contenir des espaces inutilisés.
 Insertion/Suppression coûteuse : Décalage des éléments requis.

Utilisation de l’allocation dynamique

Pour pallier ces limitations, on peut utiliser l'**allocation dynamique

#include <stdio.h>
#include <stdlib.h>

int main() {
int *T;
int n = 5;

// Allocation dynamique de mémoire

T= (int*) malloc(n * sizeof(int));

if (T == NULL) {
printf("Échec de l'allocation mémoire.\n");
return 1;
}

// Initialisation
for(int i = 0; i < n; i++) {
T[i] = i * 10;
}

Page 6 sur 191

 // Affichage
for(int i = 0; i < n; i++) {
printf("Élément %d : %d\n", i, T[i]);
}

// Libération de la mémoire
free(T);
return 0;
}

Recherche et tri dans un tableau

1. Recherche d’un élément (Recherche séquentielle)

int recherche(int tab[], int taille, int valeur) {

for (int i = 0; i < taille; i++) {
if (tab[i] == valeur) {
return i; // Retourne l’index
}
}
return -1; // Non trouvé
}

2. Tri d’un tableau (Tri à bulles)

void triBulles(int T[], int taille) {

for (int i = 0; i < taille - 1; i++) {
for (int j = 0; j < taille - i - 1; j++) {
if (T[j] > T[j + 1]) {
int temp = T[j];
T[j] = T[j + 1];
T[j + 1] = temp;
}
}
}
}

3. Cas d’utilisation des tableaux

Cas d’utilisation Pourquoi utiliser un tableau ?

Stockage de données fixes Permet un accès rapide par index.
Algorithmes de tri et de recherche Manipulation rapide des éléments.
Traitement d’images et signaux Gestion efficace des matrices de pixels.
Intelligence artificielle Stockage et manipulation des poids de neurones.

Page 7 sur 191

 Conclusion

Les tableaux sont une structure de données simple et efficace pour stocker et manipuler des
données. Cependant, leur taille fixe peut être limitante, et leur optimisation passe par une
bonne gestion de la mémoire, notamment via l’allocation dynamique.

Chapitre 3 : Les Listes Chaînées

On commencera par le concept général de liste chaînée, que l'on particularisera
ensuite aux structures de pile et file.

Listes chaînées
Cette partie sera consacrée à l'étude des listes chaînées, structures de données où l'on
passe d'un élément à un autre grâce à un pointeur.

Principe
En C et C++ on a présenté une structure de données nommée tableau permettant de
stocker des valeurs de même type au sein d’une seule variable. Le principal défaut d'un
tableau est qu'une fois déclaré on ne peut pas modifier simplement sa taille. Le
problème de l’insertion de nouvelles valeurs est donc difficile à gérer avec une telle
structure. De même pour la suppression.

On pourrait éventuellement sur-dimensionner le tableau lors de sa déclaration afin d’avoir un peu de

manœuvre, mais cette solution n’est pas très satisfaisante.

On va maintenant introduire une structure plus souple, celle de liste chaînée. Il s’agit
d’une succession de maillons, liés entre eux par des pointeurs.
Un maillon sera un objet composé de deux attributs :
 Le premier sera celui de la donnée.
 Le second sera un pointeur vers le maillon suivant.

On verra que l’on peut même avoir éventuellement un troisième attribut avec un
maillon précédent si le chaînage est double.

Voici donc l'allure d'une liste chaînée :

Page 8 sur 191

On dénombre plusieurs avantages à l'utilisation d'une telle structure :
 Il s'agit d'une structure linéaire à accès séquentiel, chaque élément permettant
l'accès au suivant.
 La recherche d’un élément se fait par balayage depuis le premier, il s'agit donc
d'une recherche séquentielle.
 Cette structure est modulable, on peut facilement insérer ou supprimer des
éléments.

Listes simplement chaînées

Il s'agit du cas le plus fréquent de liste chaînée, à partir d'un maillon on ne peut accéder qu'à son
successeur.

Représentation générale

On doit distinguer deux cas selon que le dernier maillon pointe vers le premier ou non. Si c'est le
cas on qualifie alors le chaînage de circulaire.

Une liste simplement chaînée non circulaire ressemble donc à cela :

Pour une liste simplement chaînée circulaire l'attribut pointeur du dernier maillon
contient donc l'adresse du premier :

Page 9 sur 191

Les principales méthodes de la classe liste

Pour manipuler les listes, il convient d'implémenter un certain nombre de

méthodes de mise à jour ou de recherche. L'énumération suivante n’est pas
exhaustive et varie selon les besoins :

 Construction d’une liste vide.

 Insertion d’un élément au début de la liste.
 Insertion d’un élément à la fin de la liste.
 Insertion d’un élément à n’importe quelle position de la liste.
 Opérateur d'indexation.
 Suppression d’un élément (par valeur ou par position).
 Recherche d’un élément.
 Modification d’un élément.

Définition de la structure d'une liste chaînée

Nous utiliserons une structure de base pour une liste chaînée simple :

#include <stdio.h>

#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee; // Valeur stockée dans le nœud
struct Noeud* suivant; // Pointeur vers le prochain nœud
} Noeud;
1. Construction d’une liste vide
Noeud* creerListeVide() {
return NULL;
}

2. Insertion d’un élément au début de la liste

Noeud* insererAuDebut(Noeud* tete, int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
Page 10 sur 191
 if (!nouveauNoeud) {
printf("Erreur d'allocation de mémoire\n");
return tete;
}
nouveauNoeud->donnee = valeur;
nouveauNoeud->suivant = tete;
return nouveauNoeud;
}

3. Insertion d’un élément à la fin de la liste

Noeud* insererALaFin(Noeud* tete, int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
if (!nouveauNoeud) {
printf("Erreur d'allocation de mémoire\n");
return tete;
}
nouveauNoeud->donnee = valeur;
nouveauNoeud->suivant = NULL;

if (tete == NULL) return nouveauNoeud;

Noeud* temp = tete;

while (temp->suivant != NULL) {
temp = temp->suivant;
}
temp->suivant = nouveauNoeud;
return tete;
}

4. Insertion d’un élément à une position donnée

Noeud* insererAPosition(Noeud* tete, int valeur, int position) {
if (position < 1) {
printf("Position invalide\n");
return tete;
}

Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));

if (!nouveauNoeud) {
printf("Erreur d'allocation de mémoire\n");
return tete;
}
nouveauNoeud->donnee = valeur;

if (position == 1) {
nouveauNoeud->suivant = tete;
return nouveauNoeud;
}

Noeud* temp = tete;

for (int i = 1; i < position - 1 && temp != NULL; i++) {
Page 11 sur 191
 temp = temp->suivant;
}

if (temp == NULL) {
printf("Position hors limites\n");
free(nouveauNoeud);
return tete;
}

nouveauNoeud->suivant = temp->suivant;
temp->suivant = nouveauNoeud;
return tete;
}

Synthèse
#include <stdio.h>
#include <stdlib.h>

typedef struct ElementListe {

char *donnee;
struct ElementListe *suivant;
} Element;

typedef struct ListeRepere {

Element *debut;
Element *fin;
int taille;
} Liste;

/* initialisation de la liste */
void initialisation (Liste * liste);

/* INSERTION */ /* insertion dans une liste vide */

int ins_dans_liste_vide (Liste * liste, char *donnee);

/* insertion au début de la liste */

int ins_debut_liste (Liste * liste, char *donnee);

/* insertion à a fin de la liste */

int ins_fin_liste (Liste * liste, Element * courant, char *donnee);

/* insertition ailleurs */
int ins_liste (Liste * liste, char *donnee, int pos);

/* SUPPRESSION */
int supp_debut (Liste * liste);
int supp_dans_liste (Liste * liste, int pos);
int menu (Liste *liste,int *k);
void affiche (Liste * liste);
void detruire (Liste * liste);

Page 12 sur 191

/* -------- FIN liste.h --------- */

/*************************** * liste_function.h * ***************************/

void initialisation (Liste * liste) {
liste->debut = NULL;
liste->fin = NULL;
liste->taille = 0;
}
/* insertion dans une liste vide */
int ins_dans_liste_vide (Liste * liste, char *donnee)
{
Element *nouveau_element;
if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
nouveau_element->suivant = NULL;
liste->debut = nouveau_element;
liste->fin = nouveau_element;
liste->taille++;
return 0;
}

/* insertion au début de la liste */

int ins_debut_liste (Liste * liste, char *donnee)
{
Element *nouveau_element;
if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
nouveau_element->suivant = liste->debut;
liste->debut = nouveau_element;
liste->taille++;
return 0;
}

/*insertion à la fin de la liste */

int ins_fin_liste (Liste * liste, Element * courant, char *donnee)
{
Element *nouveau_element;
if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
courant->suivant = nouveau_element; nouveau_element->suivant = NULL;
liste->fin = nouveau_element; liste->taille++;
return 0;
Page 13 sur 191
 }
/* insertion à la position demandée */
int ins_liste (Liste * liste, char *donnee, int pos)
{
if (liste->taille < 2)
return -1;
if (pos < 1 || pos >= liste->taille)
return -1;
Element *courant;
Element *nouveau_element;
int i;
if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
return -1;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) ==
NULL)
return -1;
courant = liste->debut;
for (i = 1; i < pos; ++i)
courant = courant->suivant;
if (courant->suivant == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
nouveau_element->suivant = courant->suivant;
courant->suivant = nouveau_element;
liste->taille++;
return 0;
}
/* suppression au début de la liste */
int supp_debut (Liste * liste)
{
if (liste->taille == 0)
return -1;
Element *supp_element;
supp_element = liste->debut;
liste->debut = liste->debut->suivant;
if (liste->taille == 1)
liste->fin = NULL;
free (supp_element->donnee);
free (supp_element);
liste->taille--;
return 0;
}
/* supprimer un element après la position demandée */
int supp_dans_liste (Liste * liste, int pos)
{
if (liste->taille <= 1 || pos < 1 || pos >= liste->taille)
return -1;
int i;
Element *courant;
Element *supp_element;
courant = liste->debut;
Page 14 sur 191
 for (i = 1; i < pos; ++i)
courant = courant->suivant;
supp_element = courant->suivant;
courant->suivant = courant->suivant->suivant;
if(courant->suivant == NULL)
liste->fin = courant;
free (supp_element->donnee);
free (supp_element);
liste->taille--; return 0;
}

void affiche (Liste * liste)

{
Element *courant;
courant = liste->debut;
while (courant != NULL)
{
printf ("\n -> %s ", courant->donnee);
courant = courant->suivant;
}
}

void detruire (Liste * liste)

{
while (liste->taille > 0)
supp_debut (liste);
}

int menu (Liste *liste,int *k)

{
int choix;
printf("\n********** MENU ********** ");
if (liste->taille == 0)
{
printf ("\n 1. Ajout du 1er element ");
printf ("\n 2. Quitter ");
}
else
if(liste->taille == 1 || *k == 1)
{
printf ("\n 1. Ajout au debut de la liste ");
printf ("\n 2. Ajout a la fin de la liste ");
printf ("\n 4. Suppression au debut de la liste ");
printf ("\n 6. Detruire la liste ");
printf ("\n 7. Quitter ");
}
else
{
printf ("\n 1. Ajout au debut de la liste ");
printf ("\n 2. Ajout a la fin de la liste ");
Page 15 sur 191
 printf ("\n 3. Ajout apres la position specifie ");
printf ("\n 4. Suppression au debut de la liste ");
printf ("\n 5. Suppression apres la position specifie ");
printf ("\n 6. Detruire la liste ");
printf ("\n 7. Quitter ");
}
printf ("\n Faites votre choix : ");
scanf ("%d", &choix);
getchar();
if (liste->taille == 0 && choix == 2)
choix = 7;
return choix;
}

/********************** * liste.c * **********************/

int main (void) {
char choix;
char *nom;
Liste *liste;
Element *courant;
if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL)
return -1;
if ((nom = (char *) malloc (50)) == NULL)
return -1;
courant = NULL;
choix = 'o';
initialisation (liste);
int pos, k;
while (choix != 7){
choix = menu (liste, &k);
switch (choix){
case 1: printf("\nEntrez un element : ");
scanf ("%s", nom);
getchar ();
if (liste->taille == 0)
ins_dans_liste_vide (liste, nom);
else
ins_debut_liste (liste, nom);
printf ("%d elements:deb=%s,fin=%s ", liste->taille, liste->debut->donnee, liste-
>fin->donnee);
affiche (liste);
break;
case 2: printf("\nEntrez un element : ");
scanf ("%s", nom);
getchar ();
ins_fin_liste (liste, liste->fin, nom);
printf ("\n%d elements:deb=%s,fin=%s ", liste->taille, liste->debut->donnee, liste-
>fin->donnee);
affiche (liste);
break;
Page 16 sur 191
 case 3:
printf ("Entrez un element : ");
scanf ("%s", nom); getchar ();
do{
printf ("Entrez la position : ");
scanf ("%d", &pos);
}
while (pos < 1 || pos > liste->taille);
getchar ();
if (liste->taille == 1 || pos == liste->taille)
{
k = 1;
printf("\n----------------------------------------------- ");
printf("\n Insertion [Link] le menu {1|2} \n");
printf("\n----------------------------------------------- ");
break;
}
ins_liste (liste, nom, pos);
printf ("\n%d elements:deb=%s,fin=%s ", liste->taille, liste->debut->donnee,
liste->fin->donnee);
affiche (liste);
break;

case 4: supp_debut (liste);

if (liste->taille != 0)
printf ("%d elements:deb=%s,fin=%s ", liste->taille, liste->debut->donnee,
liste->fin->donnee);
else
printf ("liste vide ");
affiche (liste);
break;

case 5:
do{
printf ("Entrez la position : ");
scanf ("%d", &pos);
}
while (pos < 1 || pos > liste->taille);
getchar ();
supp_dans_liste (liste, pos);
if (liste->taille != 0)
printf ("%d elements:deb=%s,fin=%s ", liste->taille, liste->debut->donnee,liste->fin-
>donnee);
else
printf ("liste vide ");
affiche (liste);
break;

case 6: detruire (liste);

printf ("\nla liste a ete detruite : %d elements ", liste->taille);
break;
Page 17 sur 191
 }
}
return 0;
}

Fonctionnement de la méthode d'insertion

Intéressons nous ici au fonctionnement algorithmique de la méthode d'insertion.

On suppose que l'on dispose d'une liste chaînée et que l'on souhaite insérer un élément à
une certaine position.

Il faut naturellement commencer par construire un nouveau maill on avec cet élément :

On est donc confronté à cette situation :

Il faut ensuite faire pointer le maillon nouvellement construit vers le "bon" maillon de la
liste :

Page 18 sur 191

Il ne reste plus alors qu'à faire pointer le "bon" maillon de la liste vers le maillon
nouvellement construit :

Notre opération d'insertion est ainsi terminée :

Fonctionnement de la méthode de suppression

Procédons de même pour la méthode de suppression.

Supposons que l'on soit dans ce cas de figure :

Page 19 sur 191

Il est possible que l'on souhaite conserver la valeur de l'élément à retirer, commençons
donc par la mémoriser :

Il faut ensuite relier les maillons d'avant et d'après celui que l'on veut supprimer :

Il ne reste plus alors qu'à détruire le maillon voulu :

Notre opération de suppression est ainsi terminée :

Page 20 sur 191

Exercice 1 : Suppression d’un élément dans une liste chaînée

Énoncé :
On dispose d’une liste chaînée et l’on souhaite supprimer un élément donné en fonction de
sa valeur.

 Si la valeur existe, elle est supprimée de la liste.

 Si la valeur n'existe pas, un message d'erreur est affiché.
 Si la liste est vide, un message doit l’indiquer.

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {
int valeur;
struct Noeud* suivant;
} Noeud;

// Fonction pour créer un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = valeur;
nouveau->suivant = NULL;
return nouveau;
}

// Fonction pour insérer un élément en fin de liste

void insererEnFin(Noeud** tete, int valeur) {
Noeud* nouveau = creerNoeud(valeur);
if (*tete == NULL) {
*tete = nouveau;
return;
}
Noeud* courant = *tete;

Page 21 sur 191

 while (courant->suivant != NULL) {
courant = courant->suivant;
}
courant->suivant = nouveau;
}

// Fonction pour supprimer un élément par sa valeur

void supprimerElement(Noeud** tete, int valeur) {
if (*tete == NULL) {
printf("La liste est vide. Suppression impossible.\n");
return;
}

Noeud* courant = *tete;

Noeud* precedent = NULL;

// Vérifier si l'élément à supprimer est en tête

if (courant != NULL && courant->valeur == valeur) {
*tete = courant->suivant; // Modifier la tête
free(courant); // Libérer la mémoire
printf("Élément %d supprimé avec succès.\n", valeur);
return;
}

// Parcourir la liste pour trouver l'élément à supprimer

while (courant != NULL && courant->valeur != valeur) {
precedent = courant;
courant = courant->suivant;
}

// Si l'élément n'est pas trouvé

if (courant == NULL) {
printf("Élément %d non trouvé dans la liste.\n", valeur);
return;
}

// Supprimer l'élément
precedent->suivant = courant->suivant;
free(courant);
printf("Élément %d supprimé avec succès.\n", valeur);
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
if (tete == NULL) {
printf("La liste est vide.\n");
return;
}
Noeud* courant = tete;
printf("Liste chaînée : ");
while (courant != NULL) {
Page 22 sur 191
 printf("%d -> ", courant->valeur);
courant = courant->suivant;
}
printf("NULL\n");
}

// Fonction principale
int main() {
Noeud* tete = NULL;

// Insérer des éléments dans la liste

insererEnFin(&tete, 10);
insererEnFin(&tete, 20);
insererEnFin(&tete, 30);
insererEnFin(&tete, 40);

printf("Avant suppression :\n");

afficherListe(tete);

// Suppression de différents éléments

supprimerElement(&tete, 20);
supprimerElement(&tete, 10);
supprimerElement(&tete, 50); // Élément non présent

printf("\nAprès suppression :\n");

afficherListe(tete);

return 0;
}

Remarque

 Si la liste est vide, affichage d’un message.

 Si l’élément est en tête, suppression directe et mise à jour de la tête.
 Si l’élément est au milieu ou à la fin, modification des pointeurs pour le
supprimer.
 Si l’élément n’existe pas, affichage d’un message d’erreur

Exercice 2 : Ajout d’une fonction pour supprimer un élément en fonction de

sa position dans la liste.

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {
int valeur;
Page 23 sur 191
 struct Noeud* suivant;
} Noeud;

// Fonction pour créer un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = valeur;
nouveau->suivant = NULL;
return nouveau;
}

// Fonction pour insérer un élément en fin de liste

void insererEnFin(Noeud** tete, int valeur) {
Noeud* nouveau = creerNoeud(valeur);
if (*tete == NULL) {
*tete = nouveau;
return;
}
Noeud* courant = *tete;
while (courant->suivant != NULL) {
courant = courant->suivant;
}
courant->suivant = nouveau;
}

// Fonction pour supprimer un élément par sa position

void supprimerParPosition(Noeud** tete, int position) {
if (*tete == NULL) {
printf("La liste est vide. Suppression impossible.\n");
return;
}

Noeud* courant = *tete;

// Suppression de l'élément en tête

if (position == 0) {
*tete = courant->suivant; // Mise à jour de la tête
printf("Élément en position %d (%d) supprimé.\n", position, courant->valeur);
free(courant); // Libération de la mémoire
return;
}

Noeud* precedent = NULL;

int index = 0;

// Parcourir la liste pour atteindre la position

while (courant != NULL && index < position) {
precedent = courant;
courant = courant->suivant;
index++;
}
Page 24 sur 191
 // Si la position est hors de portée
if (courant == NULL) {
printf("Position %d invalide. Suppression impossible.\n", position);
return;
}

// Supprimer le nœud à la position donnée

precedent->suivant = courant->suivant;
printf("Élément en position %d (%d) supprimé.\n", position, courant->valeur);
free(courant);
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
if (tete == NULL) {
printf("La liste est vide.\n");
return;
}
Noeud* courant = tete;
printf("Liste chaînée : ");
while (courant != NULL) {
printf("%d -> ", courant->valeur);
courant = courant->suivant;
}
printf("NULL\n");
}

// Fonction principale
int main() {
Noeud* tete = NULL;

// Insérer des éléments dans la liste

insererEnFin(&tete, 10);
insererEnFin(&tete, 20);
insererEnFin(&tete, 30);
insererEnFin(&tete, 40);
insererEnFin(&tete, 50);

printf("Avant suppression :\n");

afficherListe(tete);

// Suppression par position

supprimerParPosition(&tete, 2); // Supprime l'élément en position 2
supprimerParPosition(&tete, 0); // Supprime l'élément en tête
supprimerParPosition(&tete, 10); // Position invalide

printf("\nAprès suppression :\n");

afficherListe(tete);

return 0;
Page 25 sur 191
}

Listes doublement chaînées

Avec ce type de chaînage, on peut à partir d'un maillon accéder à la fois à son
prédécesseur et à son successeur.

Pour réaliser ce chaînage, les maillons devront être des objets composés de trois
attributs :

 Le premier sera celui de la donnée.

 Le second sera un pointeur vers le maillon précédent.
 Le troisième sera un pointeur vers le maillon suivant.
Voici donc l'allure d'une liste doublement chaînée non circulaire :

Pour un chaînage circulaire, le premier maillon pointe vers le dernier et réciproquement

:

Les méthodes de traitement des listes doublement chaînées sont bien sûr du même type
que celles des listes simplement chaînées. Leur écriture est juste plus complexe dans la

Page 26 sur 191

mesure où l’on a deux pointeurs à gérer par maillon. Nous laissons le lecteur réfléchir lui -
même à la question.

Exercice 1 : Insertion en tête d'une liste doublement chaînée

Écrire un programme en C qui implémente une liste doublement chaînée et insère un élément
en tête.

#include <stdio.h>
#include <stdlib.h>

// Structure d'un élément de la liste doublement chaînée

typedef struct Noeud {
int donnee;
struct Noeud* precedent;
struct Noeud* suivant;
} Noeud;

// Fonction pour créer un nouveau nœud

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;
}

// Fonction pour insérer un nœud en tête de la liste

void insererEnTete(Noeud** tete, int donnee) {
Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete != NULL) {
nouveauNoeud->suivant = *tete;
(*tete)->precedent = nouveauNoeud;
}
*tete = nouveauNoeud;
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
printf("Liste : ");

Page 27 sur 191

 while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Programme principal
int main() {
Noeud* tete = NULL;

insererEnTete(&tete, 10);
insererEnTete(&tete, 20);
insererEnTete(&tete, 30);

afficherListe(tete);

return 0;
}

Exercice 2 : Insertion en fin d'une liste doublement chaînée

Écrire un programme qui insère un élément en fin d'une liste doublement chaînée.

#include <stdio.h>
#include <stdlib.h>

// Structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud* precedent;
struct Noeud* suivant;
} Noeud;

// Fonction pour créer un nouveau nœud

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;
}

// Fonction pour insérer un nœud en fin de liste

void insererEnFin(Noeud** tete, int donnee) {
Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete == NULL) {
*tete = nouveauNoeud;
return;
}
Page 28 sur 191
 Noeud* temp = *tete;
while (temp->suivant != NULL) {
temp = temp->suivant;
}
temp->suivant = nouveauNoeud;
nouveauNoeud->precedent = temp;
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
printf("Liste : ");
while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Programme principal
int main() {
Noeud* tete = NULL;

insererEnFin(&tete, 10);
insererEnFin(&tete, 20);
insererEnFin(&tete, 30);

afficherListe(tete);

return 0;
}

Exercice 3 :Insertion d’un élément dans une liste chaînée à une certaine position

Énoncé :
On dispose d’une liste chaînée et l’on souhaite insérer un nouvel élément à une position
donnée.
Si la position est 0, l’élément sera inséré au début.
Si la position dépasse la taille de la liste, l’élément sera ajouté à la fin.

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {
int valeur;
struct Noeud* suivant;
Page 29 sur 191
} Noeud;

// Fonction pour créer un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->valeur = valeur;
nouveau->suivant = NULL;
return nouveau;
}

// Fonction pour insérer un élément à une position donnée

void insererElement(Noeud** tete, int valeur, int position) {
Noeud* nouveau = creerNoeud(valeur);

// Cas où l'élément doit être inséré en tête

if (position == 0) {
nouveau->suivant = *tete;
*tete = nouveau;
return;
}

Noeud* courant = *tete;

int index = 0;

// Parcourir la liste jusqu'à l'avant-dernier élément ou la position voulue

while (courant != NULL && index < position - 1) {
courant = courant->suivant;
index++;
}

// Si la position dépasse la taille, insérer à la fin

if (courant == NULL) {
printf("Position trop grande, insertion à la fin.\n");
courant = *tete;
if (courant == NULL) {
*tete = nouveau;
} else {
while (courant->suivant != NULL) {
courant = courant->suivant;
}
courant->suivant = nouveau;
}
} else {
// Insérer entre deux nœuds
nouveau->suivant = courant->suivant;
courant->suivant = nouveau;
}
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
Page 30 sur 191
 Noeud* courant = tete;
printf("Liste chaînée : ");
while (courant != NULL) {
printf("%d -> ", courant->valeur);
courant = courant->suivant;
}
printf("NULL\n");
}

// Fonction principale
int main() {
Noeud* tete = NULL;

// Insertion de quelques éléments

insererElement(&tete, 10, 0); // Insère 10 en tête
insererElement(&tete, 20, 1); // Insère 20 à la position 1
insererElement(&tete, 30, 2); // Insère 30 à la position 2
insererElement(&tete, 5, 0); // Insère 5 en tête
insererElement(&tete, 25, 2); // Insère 25 à la position 2
insererElement(&tete, 40, 10); // Position trop grande -> ajout en fin

// Affichage de la liste
afficherListe(tete);

return 0;
}

Exercice 4 : Tri d'une liste doublement chaînée avec le tri par insertion
Objectif : Implémenter le tri par insertion pour une liste doublement chaînée.

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud *precedent;
struct Noeud *suivant;
} Noeud;

// Fonction pour créer un nœud

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;

Page 31 sur 191

}

// Fonction pour insérer un élément en fin de liste

void insererFin(Noeud** tete, int donnee) {
Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete == NULL) {
*tete = nouveauNoeud;
return;
}
Noeud* temp = *tete;
while (temp->suivant != NULL)
temp = temp->suivant;

temp->suivant = nouveauNoeud;
nouveauNoeud->precedent = temp;
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Fonction pour trier la liste doublement chaînée par insertion

void triParInsertion(Noeud** tete) {
if (*tete == NULL || (*tete)->suivant == NULL)
return;

Noeud* trie = NULL;

Noeud* courant = *tete;

while (courant != NULL) {

Noeud* suivant = courant->suivant;
if (trie == NULL || trie->donnee >= courant->donnee) {
courant->suivant = trie;
if (trie != NULL) trie->precedent = courant;
trie = courant;
trie->precedent = NULL;
} else {
Noeud* temp = trie;
while (temp->suivant != NULL && temp->suivant->donnee < courant->donnee)
temp = temp->suivant;

courant->suivant = temp->suivant;
if (temp->suivant != NULL) temp->suivant->precedent = courant;
temp->suivant = courant;
courant->precedent = temp;
Page 32 sur 191
 }
courant = suivant;
}
*tete = trie;
}

// Programme principal
int main() {
Noeud* tete = NULL;

insererFin(&tete, 40);
insererFin(&tete, 20);
insererFin(&tete, 10);
insererFin(&tete, 30);

printf("Liste avant tri :\n");

afficherListe(tete);

triParInsertion(&tete);

printf("Liste après tri par insertion :\n");

afficherListe(tete);

return 0;
}
Exercice 5 : Tri d'une liste doublement chaînée avec le tri à bulles
Objectif : Implémenter le tri à bulles pour une liste doublement chaînée.

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud *precedent;
struct Noeud *suivant;
} Noeud;

// Fonction pour créer un nœud

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;
}

// Fonction pour insérer un élément en fin de liste

void insererFin(Noeud** tete, int donnee) {

Page 33 sur 191

 Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete == NULL) {
*tete = nouveauNoeud;
return;
}
Noeud* temp = *tete;
while (temp->suivant != NULL)
temp = temp->suivant;

temp->suivant = nouveauNoeud;
nouveauNoeud->precedent = temp;
}

// Fonction pour afficher la liste

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Fonction pour trier la liste doublement chaînée par tri à bulles

void triABulles(Noeud* tete) {
if (tete == NULL)
return;

int echange;
Noeud* ptr;
Noeud* dernier = NULL;

do {
echange = 0;
ptr = tete;

while (ptr->suivant != dernier) {

if (ptr->donnee > ptr->suivant->donnee) {
// Échange des valeurs
int temp = ptr->donnee;
ptr->donnee = ptr->suivant->donnee;
ptr->suivant->donnee = temp;
echange = 1;
}
ptr = ptr->suivant;
}
dernier = ptr;
} while (echange);
}

// Programme principal
Page 34 sur 191
int main() {
Noeud* tete = NULL;

insererFin(&tete, 40);
insererFin(&tete, 20);
insererFin(&tete, 10);
insererFin(&tete, 30);

printf("Liste avant tri :\n");

afficherListe(tete);

triABulles(tete);

printf("Liste après tri à bulles :\n");

afficherListe(tete);

return 0;
}

Exercice 6 :Fusionner deux listes doublement chaînées triées

Objectif :

Écrire une fonction qui prend en entrée deux listes doublement chaînées triées.
Fusionner ces listes tout en maintenant l'ordre croissant.
Retourner une nouvelle liste doublement chaînée triée.
#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud *precedent;
struct Noeud *suivant;
} Noeud;

// Fonction pour créer un nœud

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;
}

// Fonction pour insérer un élément à la fin d'une liste

void insererFin(Noeud** tete, int donnee) {
Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete == NULL) {
*tete = nouveauNoeud;

Page 35 sur 191

 return;
}
Noeud* temp = *tete;
while (temp->suivant != NULL)
temp = temp->suivant;

temp->suivant = nouveauNoeud;
nouveauNoeud->precedent = temp;
}

// Fonction pour afficher une liste doublement chaînée

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Fonction pour fusionner deux listes doublement chaînées triées

Noeud* fusionnerListesTriees(Noeud* tete1, Noeud* tete2) {
if (tete1 == NULL) return tete2;
if (tete2 == NULL) return tete1;

Noeud* resultat = NULL; // Pointeur vers la liste fusionnée

// Déterminer le premier élément de la liste fusionnée

if (tete1->donnee < tete2->donnee) {
resultat = tete1;
tete1 = tete1->suivant;
} else {
resultat = tete2;
tete2 = tete2->suivant;
}

Noeud* temp = resultat; // Pointeur pour parcourir la liste fusionnée

while (tete1 != NULL && tete2 != NULL) {

if (tete1->donnee < tete2->donnee) {
temp->suivant = tete1;
tete1->precedent = temp;
tete1 = tete1->suivant;
} else {
temp->suivant = tete2;
tete2->precedent = temp;
tete2 = tete2->suivant;
}
temp = temp->suivant;
}

Page 36 sur 191

 // Ajouter les éléments restants de tete1 ou tete2
if (tete1 != NULL) {
temp->suivant = tete1;
tete1->precedent = temp;
}
if (tete2 != NULL) {
temp->suivant = tete2;
tete2->precedent = temp;
}

return resultat;
}

// Programme principal
int main() {
Noeud* liste1 = NULL;
Noeud* liste2 = NULL;

// Remplir la première liste triée : 10 <-> 20 <-> 30

insererFin(&liste1, 10);
insererFin(&liste1, 20);
insererFin(&liste1, 30);

// Remplir la deuxième liste triée : 15 <-> 25 <-> 35

insererFin(&liste2, 15);
insererFin(&liste2, 25);
insererFin(&liste2, 35);

printf("Liste 1 :\n");
afficherListe(liste1);

printf("Liste 2 :\n");
afficherListe(liste2);

// Fusion des deux listes

Noeud* listeFusionnee = fusionnerListesTriees(liste1, liste2);

printf("Liste fusionnée triée :\n");

afficherListe(listeFusionnee);

return 0;
}
Exercice 7 : Fusionner plusieurs listes doublement chaînées triées
Objectif :
Écrire une fonction qui prend en entrée N listes doublement chaînées triées.
Fusionner toutes ces listes en une seule liste triée.
Retourner une nouvelle liste doublement chaînée triée.
#include <stdio.h>
#include <stdlib.h>

Page 37 sur 191

// Définition de la structure d'un nœud
typedef struct Noeud {
int donnee;
struct Noeud *precedent;
struct Noeud *suivant;
} Noeud;

// Fonction pour créer un nœud

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;
}

// Fonction pour insérer un élément à la fin d'une liste

void insererFin(Noeud** tete, int donnee) {
Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete == NULL) {
*tete = nouveauNoeud;
return;
}
Noeud* temp = *tete;
while (temp->suivant != NULL)
temp = temp->suivant;

temp->suivant = nouveauNoeud;
nouveauNoeud->precedent = temp;
}

// Fonction pour afficher une liste doublement chaînée

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Fonction pour fusionner deux listes doublement chaînées triées

Noeud* fusionnerDeuxListesTriees(Noeud* tete1, Noeud* tete2) {
if (tete1 == NULL) return tete2;
if (tete2 == NULL) return tete1;

Noeud* resultat = NULL; // Pointeur vers la liste fusionnée

// Déterminer le premier élément de la liste fusionnée

if (tete1->donnee < tete2->donnee) {
resultat = tete1;
Page 38 sur 191
 tete1 = tete1->suivant;
} else {
resultat = tete2;
tete2 = tete2->suivant;
}

Noeud* temp = resultat; // Pointeur pour parcourir la liste fusionnée

while (tete1 != NULL && tete2 != NULL) {

if (tete1->donnee < tete2->donnee) {
temp->suivant = tete1;
tete1->precedent = temp;
tete1 = tete1->suivant;
} else {
temp->suivant = tete2;
tete2->precedent = temp;
tete2 = tete2->suivant;
}
temp = temp->suivant;
}

// Ajouter les éléments restants

if (tete1 != NULL) {
temp->suivant = tete1;
tete1->precedent = temp;
}
if (tete2 != NULL) {
temp->suivant = tete2;
tete2->precedent = temp;
}

return resultat;
}

// Fonction pour fusionner plusieurs listes triées

Noeud* fusionnerPlusieursListesTriees(Noeud* listes[], int taille) {
if (taille == 0) return NULL;
if (taille == 1) return listes[0];

// Fusion progressive des listes deux par deux

while (taille > 1) {
int nouvelleTaille = 0;
for (int i = 0; i < taille; i += 2) {
if (i + 1 < taille) {
listes[nouvelleTaille] = fusionnerDeuxListesTriees(listes[i], listes[i + 1]);
} else {
listes[nouvelleTaille] = listes[i];
}
nouvelleTaille++;
}
taille = nouvelleTaille;
Page 39 sur 191
 }

return listes[0];
}

// Programme principal
int main() {
Noeud* liste1 = NULL;
Noeud* liste2 = NULL;
Noeud* liste3 = NULL;
Noeud* liste4 = NULL;

// Remplir la première liste triée : 10 <-> 20 <-> 30

insererFin(&liste1, 10);
insererFin(&liste1, 20);
insererFin(&liste1, 30);

// Remplir la deuxième liste triée : 15 <-> 25 <-> 35

insererFin(&liste2, 15);
insererFin(&liste2, 25);
insererFin(&liste2, 35);

// Remplir la troisième liste triée : 5 <-> 50 <-> 60

insererFin(&liste3, 5);
insererFin(&liste3, 50);
insererFin(&liste3, 60);

// Remplir la quatrième liste triée : 12 <-> 22 <-> 32

insererFin(&liste4, 12);
insererFin(&liste4, 22);
insererFin(&liste4, 32);

printf("Liste 1 :\n");
afficherListe(liste1);
printf("Liste 2 :\n");
afficherListe(liste2);
printf("Liste 3 :\n");
afficherListe(liste3);
printf("Liste 4 :\n");
afficherListe(liste4);

// Stocker les listes dans un tableau

Noeud* listes[] = {liste1, liste2, liste3, liste4};

// Fusion des listes

Noeud* listeFusionnee = fusionnerPlusieursListesTriees(listes,4);

printf("Liste fusionnée triée :\n");

afficherListe(listeFusionnee);

return 0;
Page 40 sur 191
 }

Exercice 8 : Fusion de plusieurs listes doublement chaînées triées en

utilisant une file de priorité (Min Heap)
L'objectif ici est d'utiliser une file de priorité (Min Heap) pour optimiser la fusion de
plusieurs listes doublement chaînées triées. Cette approche est plus efficace que la fusion
naïve.
Approche
Au lieu de fusionner deux listes à la fois, on utilise un tas (Min Heap) pour extraire
les plus petits éléments en priorité.
#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud de liste doublement chaînée

typedef struct Noeud {
int donnee;
struct Noeud *precedent;
struct Noeud *suivant;
} Noeud;

// Définition de la structure d'un élément du tas (Min Heap)

typedef struct NoeudTas {
Noeud* noeud;
} NoeudTas;

// Définition de la structure du Min Heap

typedef struct TasMin {
NoeudTas* tableau;
int taille;
int capacite;
} TasMin;

// Fonction pour créer un nœud de liste

Noeud* creerNoeud(int donnee) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = donnee;
nouveauNoeud->precedent = NULL;
nouveauNoeud->suivant = NULL;
return nouveauNoeud;
}

// Fonction pour insérer un élément à la fin d'une liste

void insererFin(Noeud** tete, int donnee) {
Noeud* nouveauNoeud = creerNoeud(donnee);
if (*tete == NULL) {
*tete = nouveauNoeud;
return;
}

Page 41 sur 191

 Noeud* temp = *tete;
while (temp->suivant != NULL)
temp = temp->suivant;

temp->suivant = nouveauNoeud;
nouveauNoeud->precedent = temp;
}

// Fonction pour afficher une liste doublement chaînée

void afficherListe(Noeud* tete) {
Noeud* temp = tete;
while (temp != NULL) {
printf("%d <-> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

// Fonction pour échanger deux nœuds dans le Min Heap

void echangerNoeuds(NoeudTas* a, NoeudTas* b) {
NoeudTas temp = *a;
*a = *b;
*b = temp;
}

// Fonction pour réorganiser le Min Heap (Heapify)

void tasMinifier(TasMin* tas, int index) {
int plusPetit = index;
int gauche = 2 * index + 1;
int droite = 2 * index + 2;

if (gauche < tas->taille && tas->tableau[gauche].noeud->donnee <tas-

>tableau[plusPetit].noeud->donnee)
plusPetit = gauche;

if (droite < tas->taille && tas->tableau[droite].noeud->donnee <tas-

>tableau[plusPetit].noeud->donnee)
plusPetit = droite;

if (plusPetit != index) {
echangerNoeuds(&tas->tableau[plusPetit], &tas->tableau[index]);
tasMinifier(tas, plusPetit);
}
}

// Fonction pour extraire le plus petit élément du Min Heap

Noeud* extraireMin(TasMin* tas) {
if (tas->taille == 0) return NULL;

Noeud* temp = tas->tableau[0].noeud;

tas->tableau[0] = tas->tableau[tas->taille - 1];
Page 42 sur 191
 tas->taille--;

tasMinifier(tas, 0);
return temp;
}

// Fonction pour insérer un élément dans le Min Heap

void insererTasMin(TasMin* tas, Noeud* noeud) {
if (noeud == NULL) return;

tas->taille++;
int i = tas->taille - 1;
while (i > 0 && noeud->donnee < tas->tableau[(i - 1) / 2].noeud->donnee) {
tas->tableau[i] = tas->tableau[(i - 1) / 2];
i = (i - 1) / 2;
}
tas->tableau[i].noeud = noeud;
}

// Fonction pour fusionner plusieurs listes doublement chaînées triées en utilisant un

Min Heap
Noeud* fusionnerListesAvecTasMin(Noeud* listes[], int taille) {
if (taille == 0) return NULL;

// Création du Min Heap

TasMin* tas = (TasMin*)malloc(sizeof(TasMin));
tas->tableau = (NoeudTas*)malloc(taille * sizeof(NoeudTas));
tas->taille = 0;
tas->capacite = taille;

// Remplissage du tas avec les premiers éléments de chaque liste

for (int i = 0; i < taille; i++)
if (listes[i] != NULL)
insererTasMin(tas, listes[i]);

// Construction de la liste fusionnée

Noeud* resultat = NULL;
Noeud* dernier = NULL;

while (tas->taille > 0) {

Noeud* minNoeud = extraireMin(tas);

if (resultat == NULL) {
resultat = minNoeud;
dernier = minNoeud;
} else {
dernier->suivant = minNoeud;
minNoeud->precedent = dernier;
dernier = dernier->suivant;
}

Page 43 sur 191

 if (minNoeud->suivant != NULL)
insererTasMin(tas, minNoeud->suivant);
}

free(tas->tableau);
free(tas);

return resultat;
}

// Programme principal
int main() {
Noeud* liste1 = NULL;
Noeud* liste2 = NULL;
Noeud* liste3 = NULL;
Noeud* liste4 = NULL;

// Création de listes triées

insererFin(&liste1, 10);
insererFin(&liste1, 20);
insererFin(&liste1, 30);

insererFin(&liste2, 15);
insererFin(&liste2, 25);
insererFin(&liste2, 35);

insererFin(&liste3, 5);
insererFin(&liste3, 50);
insererFin(&liste3, 60);

insererFin(&liste4, 12);
insererFin(&liste4, 22);
insererFin(&liste4, 32);

printf("Liste 1 :\n");
afficherListe(liste1);
printf("Liste 2 :\n");
afficherListe(liste2);
printf("Liste 3 :\n");
afficherListe(liste3);
printf("Liste 4 :\n");
afficherListe(liste4);

// Tableau contenant les listes

Noeud* listes[] = {liste1, liste2, liste3, liste4};

// Fusion des listes

Noeud* listeFusionnee = fusionnerListesAvecTasMin(listes, 4);

printf("Liste fusionnée triée :\n");

afficherListe(listeFusionnee);
Page 44 sur 191
 return 0;

Synthèse
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ---------- dliste.h ----------- */
typedef struct ElementListe
{
char *donnee;
struct ElementListe *precedent;
struct ElementListe *suivant;
} Element;

typedef struct ListeRepere

{
Element *debut;
Element *fin;
int taille;
} Liste;

/* initialisation de la liste */
void initialisation (Liste * uneListe);
Element *alloc (Element * nouveau_element);

/* INSERTION */
int ins_dans_liste_vide ( Liste * uneListe, char *donnee);
int ins_debut_liste (Liste * uneListe, char *donnee);
int ins_fin_liste (Liste * uneListe, char *donnee);
int ins_apres (Liste * uneListe, char *donnee, int pos);
int ins_avant (Liste * uneListe, char *donnee, int pos);

/* SUPPRESSION */
int supp(Liste * uneListe, int pos);
void affiche (Liste * uneListe);

/**************************/
void affiche_inv (Liste * uneListe);
void detruire (Liste * uneListe);

int main (void)

{

int choix = 0,pos;

char *donnee;
donnee = malloc(50);
Liste *uneListe;

Page 45 sur 191

 Element *pilote = NULL;
uneListe = (Liste *) malloc (sizeof(Liste));

initialisation(uneListe);

while(choix != 7){
choix = menu(uneListe);
switch(choix){
case 1:
printf("Entrez un element : ");
scanf("%s",donnee);
getchar();
if(uneListe->taille == 0)
insertion_dans_liste_vide(uneListe,donnee);
else
ins_debut_liste (uneListe, donnee);
printf("%d elements: deb=%s,fin=%s ",uneListe->taille,uneListe->debut-
>donnee,uneListe->fin->donnee);
affiche(uneListe);
break;
case 2:
printf("Entrez un element : ");
scanf("%s",donnee);
getchar();
ins_fin_liste (uneListe, donnee);
printf("%d elements: deb=%s,fin=%s ",uneListe->taille,uneListe->debut-
>donnee,uneListe->fin->donnee);
affiche(uneListe);
break;
case 3:
if(uneListe->taille == 1){
printf("Utiliser l'insertion au debut ou a la fin (Entree Menu : 1 ou 2)\n");
break;
}
printf("Entrez un element : ");
scanf("%s",donnee);
getchar();
do{
printf("Entrez la position : ");
scanf("%d",&pos);
}while (pos < 1 || pos > uneListe->taille);
getchar();
ins_avant(uneListe,donnee,pos);
printf("%d elements: deb=%s fin=%s ",uneListe->taille,uneListe->debut-
>donnee,uneListe->fin->donnee);
affiche(uneListe);
break;
case 4:
if(uneListe->taille == 1)
{
printf("Utiliser l'insertion au debut ou a la fin (Entree Menu : 1 ou 2)\n");
Page 46 sur 191
 break;
}
printf("Entrez un element : ");
scanf("%s",donnee);
getchar();
do{
printf("Entrez la position : ");
scanf("%d",&pos);
}while (pos < 1 || pos > uneListe->taille);
getchar();
ins_apres(uneListe,donnee,pos);
printf("%d elements: deb=%s,fin=%s ",uneListe->taille,uneListe->debut-
>donnee,uneListe->fin->donnee);
affiche(uneListe);
break;
case 5:
do{
printf("Entrez la position : ");
scanf("%d",&pos);
}while (pos < 1 || pos > uneListe->taille);

getchar();
supp(uneListe,pos);
if(uneListe->taille != 0)
printf("%d elements: deb=%s,fin=%s ",uneListe->taille,uneListe->debut-
>donnee,uneListe->fin->donnee);
else
printf("liste vide : %d elements",uneListe->taille);
affiche(uneListe);
break;
case 6:
detruire(uneListe);
printf("la liste a ete detruite : %d elements\n",uneListe->taille);
break;
}
}
return 0;
}

void initialisation (Liste * uneListe){

uneListe->debut = NULL;
uneListe->fin = NULL;
uneListe->taille = 0;
}

int insertion_dans_liste_vide (Liste * uneListe, char *donnee){

Element *nouveau_element;
if ((nouveau_element = alloc (nouveau_element)) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
nouveau_element->precedent = NULL;
Page 47 sur 191
 nouveau_element->suivant = NULL;
uneListe->debut = nouveau_element;
uneListe->fin = nouveau_element;
uneListe->taille++;
return 0;
}

int ins_debut_liste (Liste * uneListe, char *donnee)

{
Element *nouveau_element;
if ((nouveau_element = alloc (nouveau_element)) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
nouveau_element->precedent = NULL;
nouveau_element->suivant = uneListe->debut;
uneListe->debut->precedent = nouveau_element;
uneListe->debut = nouveau_element;
uneListe->taille++;
return 0;
}

int ins_fin_liste (Liste * uneListe, char *donnee){

Element *nouveau_element;
if ((nouveau_element = alloc (nouveau_element)) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
nouveau_element->suivant = NULL;
nouveau_element->precedent = uneListe->fin;
uneListe->fin->suivant = nouveau_element;
uneListe->fin = nouveau_element;
uneListe->taille++;
return 0;
}

int ins_apres (Liste * uneListe, char *donnee, int pos){

int i;
Element *nouveau_element, *courant;
if ((nouveau_element = alloc (nouveau_element)) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
courant = uneListe->debut;
for (i = 1; i < pos; ++i)
courant = courant->suivant;
nouveau_element->suivant = courant->suivant;
nouveau_element->precedent = courant;
if(courant->suivant == NULL)
uneListe->fin = nouveau_element;
else
courant->suivant->precedent = nouveau_element;
courant->suivant = nouveau_element;
uneListe->taille++;
Page 48 sur 191
 return 0;
}

int ins_avant (Liste * uneListe, char *donnee, int pos)

{
int i;
Element *nouveau_element, *courant;
if ((nouveau_element = alloc (nouveau_element)) == NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);
courant = uneListe->debut;
for (i = 1; i < pos; ++i)
courant = courant->suivant;
nouveau_element->suivant = courant;
nouveau_element-> precedent = courant->precedent;
if(courant->precedent == NULL)
uneListe->debut = nouveau_element;
else
courant->precedent->suivant = nouveau_element;
courant->precedent = nouveau_element;
uneListe->taille++;
return 0;
}

int supp(Liste * uneListe, int pos){

int i;
Element *supp_element,*courant;

if(uneListe->taille == 0)
return -1;

if(pos == 1){ /* suppresion de 1er élément */

supp_element = uneListe->debut;
uneListe->debut = uneListe->debut->suivant;
if(uneListe->debut == NULL)
uneListe->fin = NULL;
else
uneListe->debut->precedent == NULL;
}else if(pos == uneListe->taille){ /* suppression du dernier élément */
supp_element = uneListe->fin;
uneListe->fin->precedent->suivant = NULL;
uneListe->fin = uneListe->fin->precedent;
}else { /* suppression ailleurs */
courant = uneListe->debut;
for(i=1;i<pos;++i)
courant = courant->suivant;
supp_element = courant;
courant->precedent->suivant = courant->suivant;
courant->suivant->precedent = courant->precedent;
}
free(supp_element->donnee);
Page 49 sur 191
 free(supp_element);
uneListe->taille--;
return 0;
}

void detruire(Liste * uneListe){

while(uneListe->taille > 0)
supp(uneListe,1);
}

Element *alloc (Element * nouveau_element){

if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
return NULL;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
== NULL)
return NULL;
return nouveau_element;
}

int menu (Liste * uneListe){

int choix;
if (uneListe->taille == 0){
printf ("1. Ajout du 1er element\n");
printf ("2. Quitter\n");
} else{
printf ("1. Ajout au debut de la liste\n");
printf ("2. Ajout a la fin de la liste\n");
printf ("3. Ajout avant la position specifie\n");
printf ("4. Ajout apres la position specifie\n");
printf ("5. Suppression a la position specifie\n");
printf ("6. Detruire la liste\n");
printf ("7. Quitter\n");
}
printf ("\n\nFaites votre choix : ");
scanf ("%d", &choix);
getchar();
if(uneListe->taille == 0 && choix == 2)
choix = 7;
return choix;
}

int supp(Liste * uneListe, int pos);

void affiche(Liste *uneListe){
Element *courant;
courant = uneListe->debut;
printf("[ ");
while(courant != NULL){
printf("%s ",courant->donnee);
courant = courant->suivant;
}
printf("]\n");
Page 50 sur 191
}

void affiche_inv(Liste *uneListe)

{
Element *courant;
courant = uneListe->fin;
while(courant != NULL){
printf("%s : ",courant->donnee);
courant = courant->precedent;
}
printf("\n");
}
/* -------- FIN dliste_function.h --------- */

Piles
Nous allons ici nous intéresser aux piles, i.e. aux listes chaînées soumises au
principe L.I.F.O..
Principe
Une pile est une liste simplement chaînée bien particulière où les opérations
d’insertion et de suppression d’élément ne se font qu’à la fin. Cette structure de
donnée obéit ainsi à la règle L.I.F.O., Last In First Out. Cela signifie concrètement
que l’on ne peut supprimer que le dernier élément inséré.

Puisque c'est un cas particulier de liste chaînée, une pile sera constituée elle aussi
d'une succession de maillons, qui seront comme précédemment des objets possédant
deux attributs, l'un pour la donnée, l'autre pour pointer vers un autre maillon.

Illustrons maintenant avec quelques images le fonctionnement d'une pile afin que le
lecteur en saisisse bien son principe.

Considérons par exemple une pile constituée d'un seul élément :

L'insertion d'un élément se fait donc nécessairement à la fin de la pile :

Page 51 sur 191

Une autre insertion d'élément :

Encore une insertion :

La suppression d’un élément se fait également obligatoirement à la fin de la pile :

Une autre suppression d'élément :

Page 52 sur 191

Puisque la classe pile suit le principe L.I.F.O. elle contient juste les méthodes suivantes :

 Construction d’une pile vide.

 Empilage d’un élément.
 Dépilage d’un élément.
 Récupération de l’élément au sommet de la pile sans le dépiler.
Il est temps pour le lecteur d'évaluer la complexité de chacune de ces méthodes.

Exercice corrigé : complexité des méthodes de la classe pile

Pour finir cette partie, citons quelques applications importantes des piles :

 Gestion de certains registres des processeurs (voir à ce sujet le cours

d'architecture des ordinateurs).
 Mémorisation de l’historique dans un navigateur web.
 Logiciels de calculs fonctionnant en notation polonaise inversée

Exercice 1 : Construction d’une pile vide

Enoncé :
Ecrire un programme qui définit une structure de pile vide en utilisant une liste chaînée.
#include <stdio.h>
#include <stdlib.h>

// Structure pour représenter un nœud de la pile

typedef struct Noeud {
int donnee;
struct Noeud* suivant;
} Noeud;

// Fonction pour créer une pile vide

Noeud* creerPile() {
return NULL; // Une pile vide est simplement représentée par NULL
}

// Fonction pour vérifier si la pile est vide

int estVide(Noeud* sommet) {
return sommet == NULL;
}

Page 53 sur 191

// Fonction pour afficher l'état de la pile
void afficherPile(Noeud* sommet) {
if (estVide(sommet)) {
printf("La pile est vide.\n");
return;
}
printf("Pile : ");
while (sommet != NULL) {
printf("%d -> ", sommet->donnee);
sommet = sommet->suivant;
}
printf("NULL\n");
}

// Programme principal
int main() {
Noeud* pile = creerPile();
afficherPile(pile);

return 0;
}

Exercice 2 : Empilage d’un élément

Énoncé :

Ecrire une fonction empiler() qui permet d’ajouter un élément au sommet de la pile.

// Fonction pour empiler un élément

void empiler(Noeud** sommet, int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
if (nouveauNoeud == NULL) {
printf("Erreur : Allocation mémoire échouée.\n");
return;
}
nouveauNoeud->donnee = valeur;
nouveauNoeud->suivant = *sommet; // Le nouveau nœud pointe vers l'ancien sommet
*sommet = nouveauNoeud; // Mettre à jour le sommet de la pile
}

// Programme principal
int main() {
Noeud* pile = creerPile();

empiler(&pile, 10);
empiler(&pile, 20);
empiler(&pile, 30);

Page 54 sur 191

 afficherPile(pile); // Affiche : 30 -> 20 -> 10 -> NULL

return 0;
}

Exercice 3 : Dépilage d’un élément

Enoncé :

Ecrire une fonction depiler() qui supprime et retourne l’élément au sommet de la pile.

// Fonction pour dépiler un élément

int depiler(Noeud** sommet) {
if (estVide(*sommet)) {
printf("Erreur : La pile est vide.\n");
return -1; // Valeur indicatrice d'erreur
}
Noeud* temp = *sommet;
int valeur = temp->donnee;
*sommet = temp->suivant; // Déplacer le sommet vers l'élément suivant
free(temp); // Libérer la mémoire de l'ancien sommet
return valeur;
}

// Programme principal
int main() {
Noeud* pile = creerPile();

empiler(&pile, 10);
empiler(&pile, 20);
empiler(&pile, 30);

afficherPile(pile); // Affiche : 30 -> 20 -> 10 -> NULL

printf("Élément dépilé : %d\n", depiler(&pile));

afficherPile(pile); // Affiche : 20 -> 10 -> NULL

return 0;
}

Exercice 4 : Récupération de l’élément au sommet sans le dépiler

Enoncé :

Ecrire une fonction sommet() qui retourne l’élément en haut de la pile sans le retirer.

// Fonction pour récupérer l’élément au sommet sans le dépiler

int sommet(Noeud* pile) {

Page 55 sur 191
 if (estVide(pile)) {
printf("Erreur : La pile est vide.\n");
return -1; // Valeur indicatrice d'erreur
}
return pile->donnee;
}

// Programme principal
int main() {
Noeud* pile = creerPile();

empiler(&pile, 10);
empiler(&pile, 20);
empiler(&pile, 30);

afficherPile(pile); // Affiche : 30 -> 20 -> 10 -> NULL

printf("Élément au sommet : %d\n", sommet(pile)); // Affiche : 30

return 0;
}

Exercice 5 : Implémentation d'un historique avec une pile

Enoncé :
Implémentez un programme en C qui gère l'historique d'un navigateur web en utilisant une
pile. L'utilisateur peut :

1. Visiter une nouvelle page (ajout dans l'historique).

2. Revenir en arrière (retour à la page précédente).
3. Afficher l'historique des pages visitées.
4. Quitter le programme.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100 // Taille maximale de l'historique
typedef struct {
char url[100];
} Page;

typedef struct {
Page pages[MAX];
int top;
} Historique;

// Initialisation de la pile
void initHistorique(Historique *h) {
h->top = -1;
}

Page 56 sur 191

// Vérifier si la pile est vide
int estVide(Historique *h) {
return h->top == -1;
}

// Vérifier si la pile est pleine

int estPleine(Historique *h) {
return h->top == MAX - 1;
}

// Ajouter une nouvelle page (push)

void visiterPage(Historique *h, char url[]) {
if (estPleine(h)) {
printf("Historique plein !\n");
return;
}
h->top++;
strcpy(h->pages[h->top].url, url);
}

// Revenir en arrière (pop)

void revenirArriere(Historique *h) {
if (estVide(h)) {
printf("Aucune page précédente !\n");
return;
}
printf("Revenir à : %s\n", h->pages[h->top].url);
h->top--;
}

// Afficher l'historique
void afficherHistorique(Historique *h) {
if (estVide(h)) {
printf("Historique vide !\n");
return;
}
printf("Historique des pages visitées :\n");
for (int i = h->top; i >= 0; i--) {
printf("%d. %s\n", i + 1, h->pages[i].url);
}
}

int main() {
Historique historique;
initHistorique(&historique);

int choix;
char url[100];

do {
printf("\n1. Visiter une page\n");
Page 57 sur 191
 printf("2. Revenir en arrière\n");
printf("3. Afficher l'historique\n");
printf("4. Quitter\n");
printf("Choix : ");
scanf("%d", &choix);
getchar(); // Pour absorber le retour à la ligne

switch (choix) {
case 1:
printf("Entrer l'URL : ");
fgets(url, sizeof(url), stdin);
url[strcspn(url, "\n")] = '\0'; // Enlever le \n de fgets
visiterPage(&historique, url);
break;
case 2:
revenirArriere(&historique);
break;
case 3:
afficherHistorique(&historique);
break;
case 4:
printf("Fermeture du navigateur...\n");
break;
default:
printf("Choix invalide !\n");
}
} while (choix != 4);

return 0;
}

Exercice 6 : Gestion avancée avec une liste doublement chaînée

Énoncé :
Améliorez l'exercice précédent en utilisant une liste doublement chaînée permettant :

1. De visiter une page.

2. De naviguer en avant et en arrière dans l'historique.
3. D'afficher tout l'historique.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Définition d'un nœud de la liste doublement chaînée

typedef struct Noeud {
char url[100];
struct Noeud *suivant;
struct Noeud *precedent;
} Noeud;

Page 58 sur 191

// Structure de l'historique
typedef struct {
Noeud *actuel;
} Historique;

// Initialiser l'historique
void initHistorique(Historique *h) {
h->actuel = NULL;
}

// Visiter une nouvelle page

void visiterPage(Historique *h, char url[]) {
Noeud *nouveau = (Noeud*)malloc(sizeof(Noeud));
strcpy(nouveau->url, url);
nouveau->suivant = NULL;
nouveau->precedent = h->actuel;

if (h->actuel != NULL) {
h->actuel->suivant = nouveau;
}
h->actuel = nouveau;
}

// Revenir en arrière
void revenirArriere(Historique *h) {
if (h->actuel == NULL || h->actuel->precedent == NULL) {
printf("Impossible de revenir en arrière !\n");
return;
}
h->actuel = h->actuel->precedent;
printf("Page actuelle : %s\n", h->actuel->url);
}

// Aller en avant
void allerEnAvant(Historique *h) {
if (h->actuel == NULL || h->actuel->suivant == NULL) {
printf("Impossible d'aller en avant !\n");
return;
}
h->actuel = h->actuel->suivant;
printf("Page actuelle : %s\n", h->actuel->url);
}

// Afficher l'historique complet

void afficherHistorique(Historique *h) {
if (h->actuel == NULL) {
printf("Historique vide !\n");
return;
}

Noeud *temp = h->actuel;

Page 59 sur 191
 while (temp->precedent != NULL) {
temp = temp->precedent;
}

printf("Historique des pages visitées :\n");

while (temp != NULL) {
printf("%s\n", temp->url);
temp = temp->suivant;
}
}

int main() {
Historique historique;
initHistorique(&historique);

int choix;
char url[100];

do {
printf("\n1. Visiter une page\n");
printf("2. Revenir en arrière\n");
printf("3. Aller en avant\n");
printf("4. Afficher l'historique\n");
printf("5. Quitter\n");
printf("Choix : ");
scanf("%d", &choix);
getchar(); // Absorber le retour à la ligne

switch (choix) {
case 1:
printf("Entrer l'URL : ");
fgets(url, sizeof(url), stdin);
url[strcspn(url, "\n")] = '\0'; // Supprimer le \n
visiterPage(&historique, url);
break;
case 2:
revenirArriere(&historique);
break;
case 3:
allerEnAvant(&historique);
break;
case 4:
afficherHistorique(&historique);
break;
case 5:
printf("Fermeture du navigateur...\n");
break;
default:
printf("Choix invalide !\n");
}
} while (choix != 5);
Page 60 sur 191
 return 0;
}

Exercice 7 : Sauvegarde et chargement de l’historique dans un fichier.

Enoncé :
Modifiez l’implémentation de la liste doublement chaînée pour que l’historique soit
sauvegardé dans un fichier et rechargé au démarrage du programme. L’utilisateur pourra
ainsi :

1. Visiter une nouvelle page (ajout dans l'historique).

2. Revenir en arrière (navigation vers la page précédente).
3. Aller en avant (navigation vers la page suivante).
4. Afficher l'historique des pages visitées.
5. Sauvegarder l'historique dans un fichier.
6. Recharger l'historique depuis le fichier au lancement du programme.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FICHIER_HISTORIQUE "[Link]"

// Définition d'un nœud de la liste doublement chaînée

typedef struct Noeud {
char url[100];
struct Noeud *suivant;
struct Noeud *precedent;
} Noeud;

// Structure de l'historique
typedef struct {
Noeud *actuel;
} Historique;

// Initialiser l'historique
void initHistorique(Historique *h) {
h->actuel = NULL;
}

// Visiter une nouvelle page

void visiterPage(Historique *h, char url[]) {
Noeud *nouveau = (Noeud*)malloc(sizeof(Noeud));
if (nouveau == NULL) {
printf("Erreur d'allocation mémoire !\n");
return;
}

Page 61 sur 191

 strcpy(nouveau->url, url);
nouveau->suivant = NULL;
nouveau->precedent = h->actuel;

if (h->actuel != NULL) {
h->actuel->suivant = nouveau;
}
h->actuel = nouveau;
}

// Revenir en arrière
void revenirArriere(Historique *h) {
if (h->actuel == NULL || h->actuel->precedent == NULL) {
printf("Impossible de revenir en arrière !\n");
return;
}
h->actuel = h->actuel->precedent;
printf("Page actuelle : %s\n", h->actuel->url);
}

// Aller en avant
void allerEnAvant(Historique *h) {
if (h->actuel == NULL || h->actuel->suivant == NULL) {
printf("Impossible d'aller en avant !\n");
return;
}
h->actuel = h->actuel->suivant;
printf("Page actuelle : %s\n", h->actuel->url);
}

// Afficher l'historique
void afficherHistorique(Historique *h) {
if (h->actuel == NULL) {
printf("Historique vide !\n");
return;
}

Noeud *temp = h->actuel;

while (temp->precedent != NULL) {
temp = temp->precedent;
}

printf("Historique des pages visitées :\n");

while (temp != NULL) {
printf("%s\n", temp->url);
temp = temp->suivant;
}
}

// Sauvegarder l'historique dans un fichier

void sauvegarderHistorique(Historique *h) {
Page 62 sur 191
 FILE *fichier = fopen(FICHIER_HISTORIQUE, "w");
if (fichier == NULL) {
printf("Erreur lors de l'ouverture du fichier !\n");
return;
}

Noeud *temp = h->actuel;

while (temp != NULL && temp->precedent != NULL) {
temp = temp->precedent; // Aller au début
}

while (temp != NULL) {

fprintf(fichier, "%s\n", temp->url);
temp = temp->suivant;
}

fclose(fichier);
printf("Historique sauvegardé avec succès !\n");
}

// Charger l'historique depuis un fichier

void chargerHistorique(Historique *h) {
FILE *fichier = fopen(FICHIER_HISTORIQUE, "r");
if (fichier == NULL) {
printf("Aucun historique trouvé.\n");
return;
}

char url[100];
while (fgets(url, sizeof(url), fichier) != NULL) {
url[strcspn(url, "\n")] = '\0'; // Supprimer le retour à la ligne
visiterPage(h, url);
}

fclose(fichier);
printf("Historique chargé avec succès !\n");
}

// Libérer la mémoire
void libererMemoire(Historique *h) {
Noeud *temp = h->actuel;
while (temp != NULL) {
Noeud *precedent = temp->precedent;
free(temp);
temp = precedent;
}
}

int main() {
Historique historique;
initHistorique(&historique);
Page 63 sur 191
 // Charger l'historique existant depuis le fichier
chargerHistorique(&historique);

int choix;
char url[100];

do {
printf("\n1. Visiter une page\n");
printf("2. Revenir en arrière\n");
printf("3. Aller en avant\n");
printf("4. Afficher l'historique\n");
printf("5. Sauvegarder l'historique\n");
printf("6. Quitter\n");
printf("Choix : ");
scanf("%d", &choix);
getchar(); // Absorber le retour à la ligne

switch (choix) {
case 1:
printf("Entrer l'URL : ");
fgets(url, sizeof(url), stdin);
url[strcspn(url, "\n")] = '\0'; // Supprimer le \n
visiterPage(&historique, url);
break;
case 2:
revenirArriere(&historique);
break;
case 3:
allerEnAvant(&historique);
break;
case 4:
afficherHistorique(&historique);
break;
case 5:
sauvegarderHistorique(&historique);
break;
case 6:
sauvegarderHistorique(&historique); // Sauvegarde avant de quitter
printf("Fermeture du navigateur...\n");
break;
default:
printf("Choix invalide !\n");
}
} while (choix != 6);

libererMemoire(&historique);
return 0;
}

Page 64 sur 191

Files
Cette dernière partie sera consacrée aux listes chaînées régies par le principe F.I.F.O.,
que l'on appelle des files.
Principe
Une file est une liste simplement chaînée bien particulière où l'opération d’insertion
d’un élément ne se fait qu’à la fin, et celle de suppression qu’au début. Cette structure
de donnée obéit ainsi à la règle F.I.F.O., First In First Out. Cela signifie concrètement
que l’on ne peut supprimer que le premier élément inséré.

Puisque c'est un cas particulier de liste chaînée, une file sera constituée elle aussi d'une
succession de maillons, qui seront comme précédemment des objets possédant deux
attributs, l'un pour la donnée, l'autre pour pointer vers un autre maillon.

Illustrons maintenant avec quelques images le fonctionnement d'une file afin que le
lecteur en saisisse bien son principe.

Considérons par exemple une file constituée d'un seul élément :

L'insertion d'un élément se fait donc nécessairement à la fin de la file :

Une autre insertion d'élément :

Page 65 sur 191

Encore une insertion :

La suppression d’un élément se fait elle obligatoirement au début de la file :

Une autre suppression d'élément :

Puisque la classe file suit le principe F.I.F.O. elle contient juste les méthodes suivantes :
 Construction d’une file vide.
 Enfilage d’un élément.
 Défilage d’un élément.
 Récupération du premier élément de la file sans le défiler.

Page 66 sur 191

Un dernier effort est maintenant demandé au lecteur, celui d'éval uer la complexité de ces
méthodes.

Exercice 1 : Implémentation d'une file en utilisant une liste chaînée

Enoncé :

1. Implémentez une file en utilisant une liste chaînée.

2. Implémentez les fonctions suivantes :
o Créer une file vide
o Enfiler un élément (enqueue)
o Défiler un élément (dequeue)
o Récupérer le premier élément sans le défiler (peek)
3. Affichez la file après chaque opération.

Définition de la structure d'une file

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud* suivant;
} Noeud;

// Définition de la structure d'une file

typedef struct File {
Noeud* debut; // Pointeur vers le premier élément
Noeud* fin; // Pointeur vers le dernier élément
} File;

1. Construction d’une file vide

// Fonction pour créer une file vide

File* creerFile() {
File* file = (File*)malloc(sizeof(File));
file->debut = NULL;
file->fin = NULL;
return file;
}

2. Enfilage d’un élément (enqueue)

// Fonction pour enfiler un élément

void enfiler(File* file, int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;

Page 67 sur 191

 nouveauNoeud->suivant = NULL;

if (file->fin == NULL) {
file->debut = file->fin = nouveauNoeud;
return;
}

file->fin->suivant = nouveauNoeud;
file->fin = nouveauNoeud;
}

3. Défilage d’un élément (dequeue)

// Fonction pour défiler un élément

int defiler(File* file) {
if (file->debut == NULL) {
printf("Erreur : la file est vide\n");
return -1;
}

Noeud* temp = file->debut;

int valeur = temp->donnee;
file->debut = file->debut->suivant;

if (file->debut == NULL) // Si la file devient vide

file->fin = NULL;

free(temp);
return valeur;
}

4. Récupération du premier élément sans le défiler (peek)

// Fonction pour récupérer le premier élément sans le défiler

int premier(File* file) {
if (file->debut == NULL) {
printf("Erreur : la file est vide\n");
return -1;
}
return file->debut->donnee;
}

5. Affichage de la file

// Fonction pour afficher les éléments de la file

void afficherFile(File* file) {
Noeud* temp = file->debut;
printf("File : ");

Page 68 sur 191

 while (temp != NULL) {
printf("%d -> ", temp->donnee);
temp = temp->suivant;
}
printf("NULL\n");
}

6. Programme principal (test des fonctions)

int main() {
File* file = creerFile();

// Enfilage des éléments

enfiler(file, 10);
enfiler(file, 20);
enfiler(file, 30);
afficherFile(file);

// Défilage
printf("Élément défilé : %d\n", defiler(file));
afficherFile(file);

// Récupération du premier élément

printf("Premier élément de la file : %d\n", premier(file));

return 0;
}

Synthèse

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud* suivant;
} Noeud;

// Définition de la structure d'une file

typedef struct File {
Noeud* debut; // Pointeur vers le premier élément
Noeud* fin; // Pointeur vers le dernier élément
} File;

// Fonction pour créer une file vide

File* creerFile() {
File* file = (File*)malloc(sizeof(File));
file->debut = NULL;
file->fin = NULL;
Page 69 sur 191
 return file;
}
// Fonction pour enfiler un élément
void enfiler(File* file, int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->suivant = NULL;

if (file->fin == NULL) {
file->debut = file->fin = nouveauNoeud;
return;
}

file->fin->suivant = nouveauNoeud;
file->fin = nouveauNoeud;
}

// Fonction pour défiler un élément

int defiler(File* file) {
if (file->debut == NULL) {
printf("Erreur : la file est vide\n");
return -1;
}

Noeud* temp = file->debut;

int valeur = temp->donnee;
file->debut = file->debut->suivant;

if (file->debut == NULL) // Si la file devient vide

file->fin = NULL;

free(temp);
return valeur;
}
// Fonction pour récupérer le premier élément sans le défiler
int premier(File* file) {
if (file->debut == NULL) {
printf("Erreur : la file est vide\n");
return -1;
}
return file->debut->donnee;
}

//Affichage de la file
// Fonction pour afficher les éléments de la file
void afficherFile(File* file) {
Noeud* temp = file->debut;
printf("File : ");
while (temp != NULL) {
printf("%d -> ", temp->donnee);
temp = temp->suivant;
Page 70 sur 191
 }
printf("NULL\n");
}

// Programme principal (test des fonctions)

int main() {
File* file = creerFile();

// Enfilage des éléments

enfiler(file, 10);
enfiler(file, 20);
enfiler(file, 30);
afficherFile(file);

// Défilage
printf("Élément défilé : %d\n", defiler(file));
afficherFile(file);

// Récupération du premier élément

printf("Premier élément de la file : %d\n", premier(file));

return 0;
}

Liste Circulaire
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* ---------- liste_circ.h ----------- */

typedef struct ElementListeCirc {
char *donnee;
struct ElementListeCirc *suivant;
} Element;

typedef struct ListeRepereCirc {

Element *debut;
Element *fin;
int taille;
} Liste;

/* initialisation de la liste */
void initialisation (Liste * liste);

/* INSERTION */
/* insertion dans une liste vide */
int ins_liste_circ_vide(Liste * liste, char *donnee);
int ins_liste_circ(Liste * liste, Element *courant, char *donnee);

/* SUPPRESSION */
Page 71 sur 191
int supp_liste_circ (Liste * liste);
int supp_liste_circ_unique (Liste * liste);

int menu (Liste *liste);

void affiche (Liste * liste);
void affiche_infini (Liste * liste);
void detruire (Liste * liste);
/* -------- FIN liste_circ.h --------- */
/******************************\

* liste_circ_function.h *
\******************************/
void initialisation (Liste * liste){
liste->debut = NULL;
liste->fin = NULL;
liste->taille = 0;
}

/* insertion dans une liste vide */

int ins_liste_circ_vide(Liste * liste, char *donnee){
Element *nouveau_element;
if ((nouveau_element = (Element *) malloc (sizeof (Element)))
== NULL)
return -1;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);

nouveau_element->suivant = nouveau_element;
liste->debut = nouveau_element;
liste->fin = nouveau_element;
liste->taille++;
return 0;
}

/* insertion dans une liste non-vide */

int ins_liste_circ(Liste * liste, Element *courant, char *donnee){
Element *nouveau_element;
if ((nouveau_element = (Element *) malloc (sizeof (Element)))
== NULL)
return -1;
if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (nouveau_element->donnee, donnee);

if(courant != liste->fin)
return -1;

nouveau_element->suivant = courant->suivant;
Page 72 sur 191
 courant->suivant = nouveau_element;
liste->fin = nouveau_element;
liste->taille++;
return 0;
}

/* suppression au début de la liste */

int supp_liste_circ(Liste * liste){
if (liste->taille < 2)
return -1;
Element *supp_element;

supp_element = liste->debut;
liste->debut = liste->debut->suivant;
liste->fin->suivant = liste->debut;

free (supp_element->donnee);
free (supp_element);
liste->taille--;
return 0;
}

/* suppression dans une liste avec un seul élément*/

int supp_liste_circ_unique(Liste *liste){
if (liste->taille != 1)
return -1;
Element *supp_element;

supp_element = liste->debut;
liste->debut = NULL;
liste->fin = NULL;

free (supp_element->donnee);
free (supp_element);
liste->taille--;
return 0;
}

/* affichage de la liste */
void affiche (Liste * liste){
Element *courant;
courant = liste->debut;
int i;
for(i=0;i<liste->taille;++i){
printf ("-> %s\n", courant->donnee);
courant = courant->suivant;
}
}

/* parcourir la liste à l'infini*/

void affiche_infini (Liste * liste){
Page 73 sur 191
 Element *courant;
courant = liste->debut;
while (1){
printf ("-> %s\n", courant->donnee);
courant = courant->suivant;
}
}

/* detruire la liste */
void detruire (Liste * liste){
while (liste->taille > 0){
if(liste->taille > 1)
supp_liste_circ (liste);
else
supp_liste_circ_unique(liste);
}
}

int menu (Liste *liste){

int choix; printf("********** MENU **********\n");
if (liste->taille == 0){
printf ("1. Ajout du 1er element\n");
printf ("2. Quitter\n");
}else {
printf ("1. Ajout d'un element\n");
printf ("2. Suppression au debut (la liste doit avoir au moins 2 elements)\n");
printf ("3. Suppression dans une liste avec un seul element\n");
printf ("4. Affiche liste circulaire\n");
printf ("5. Affiche liste circulaire [Ctrl-C] pour quitter le programme\n");
printf ("6. Detruire la liste\n");
printf ("7. Quitter\n");
}
printf ("\n\nFaites votre choix : ");
scanf ("%d", &choix);
getchar();
if(liste->taille == 0 && choix == 2)
choix = 7;
return choix;
}
/* -------- FIN liste_circ_function --------- *
/**********************\

* liste_circ.c *
\**********************/

int main (void)

{
char choix;
char *nom;
Liste *liste;
Page 74 sur 191
Element *courant;

if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL)

return -1;
if ((nom = (char *) malloc (50)) == NULL)
return -1;
courant = NULL;
choix = 'o';

initialisation (liste);

while (choix != 7){

choix = menu (liste);
switch (choix){
case 1:
printf ("Entrez un element : ");
scanf ("%s", nom);
getchar ();
if(liste->taille == 0)
ins_liste_circ_vide (liste,nom);
else
ins_liste_circ (liste,liste->fin,nom);
printf ("%d elements:deb=%s, fin=%s\n",
liste->taille,
liste->debut->donnee,
liste->fin->donnee);
affiche (liste);
break;
case 2:
if(liste->taille < 2)
break;
supp_liste_circ (liste);
if (liste->taille != 0)
printf ("%d elements:deb=%s, fin=%s\n",
liste->taille,
liste->debut->donnee,
liste->fin->donnee);
affiche(liste);
break;
case 3:
if(liste->taille != 1)
break;
supp_liste_circ_unique(liste);
printf("La liste est vide\n");
break;
case 4:
affiche(liste);
break;
case 5:
affiche_infini(liste);
Page 75 sur 191
 break;
case 6:
detruire (liste);
printf ("la liste a ete detruite : %d elements\n", liste->taille);
break;
}
}
return 0;
}

Chapitre 4: Les Arbres

1. Notions générales sur les arbres

La structure d'arbre est très utilisée en informatique. Sur le fond on peut

considérer un arbre comme une généralisation d'une liste car les listes
peuvent être représentées par des arbres. La complexité des
algorithmes d’insertion de suppression ou de recherche est généralement
plus faible que dans le cas des listes (cas particulier des arbres équilibrés).
Les mathématiciens voient les arbres eux-mêmes comme des cas particuliers
de graphes non orientés connexes et acycliques, donc contenant des sommets
et des arcs :

fig-1 fig-2 fig-3

Ci dessus 3 représentations graphiques de la même structure d'arbre, dans la

figure fig-1 tous les sommets ont une disposition équivalente, dans la figure
fig-2 et dans la figure fig-3 le sommet "rouge" se distingue des autres.
Lorsqu'un sommet est distingué par rapport aux autres, on le
dénomme racine et la même structure d'arbre s'appelle une arborescence,
par abus de langage dans tout le reste du document nous utiliserons le
vocablearbre pour une arborescence.

Enfin certains arbres particuliers nommés arbres binaires sont les plus
utilisés en informatique et les plus simples à étudier. En outre il est toujours

Page 76 sur 191

possible de "binariser" un arbre non binaire, ce qui nous permettra dans ce
chapitre de n'étudier que les structures d'arbres binaires.

1.1 Vocabulaire employé sur les arbres

Etiquette

Un arbre dont tous les noeuds sont nommés est dit étiqueté. L'étiquette (ou
nom du sommet) représente la "valeur" du noeud ou bien l'information
associée au noeud. Ci-dessous un arbre étiqueté dans les entiers entre 1 et 10
:

Racine, noeud, branche, feuille

Nous rappellons la terminologie de base sur les arbres sur le schéma ci-
dessous :

Hauteur, profondeur ou niveau d'un noeud

Nous conviendrons de définir la hauteur(ou profondeur ou niveau ) d'un

noeud X comme égale au nombre de noeuds à partir de la racine pour
Page 77 sur 191
aller jusqu'au noeud X. En reprenant l'arbre précédant et en notant h la
fonction hauteur d'un noeud :

Pour atteindre le noeud étiqueté 9 , il faut parcourir le lien 1--5, puis 5--8,
puis enfin 8--9 soient 4 noeuds donc 9 est de profondeur ou de hauteur égale
à 4, soit h(9) = 4.

Pour atteindre le noeud étiqueté 7 , il faut parcourir le lien 1--4, et enfin 4--7,
donc 7 est de profondeur ou de hauteur égale à 3, soit h(7) = 3.

Par définition la hauteur de la racine est égal à 1.

h(racine) =1 (pour tout arbre non vide)

(Certains auteurs adoptent une autre convention pour calculer la hauteur

d'un noeud: la racine a pour hauteur 0 et donc n'est pa comptée dans le
nombre de noeuds, ce qui donne une hauteur inférieure d'une unité à notre
définition).

Chemin d'un noeud

On appelle chemin du noeud X la suite des noeuds par lesquels il faut passer
pour aller de la racine vers le noeud X :

Page 78 sur 191

Chemin du noeud 10 = (1,5,8,10)
Chemin du noeud 9 = (1,5,8,9)
.....
Chemin du noeud 7 = (1,4,7)
Chemin du noeud 5 = (1,5)
Chemin du noeud 1 = (1)

Remarquons que la hauteur h d'un noeud X est égale au nombre de noeuds

dans le chemin :

h( X ) = NbrNoeud( Chemin( X ) ).

Noeuds frères, parents, enfants, ancêtres

Le vocabulaire de lien entre noeuds de niveaux différents et reliés entres eux

est emprunté à la généalogie :

9 est l'enfant de 8 10 est l'enfant de 8

8 est le parent de 9 8 est le parent de 10 9 et 10 sont des frères

5 est le parent de 8 et l'ancêtre de 9 et 10.

On parle aussi d'ascendant, de descendant ou de fils pour évoquer des

relations entres les noeuds d'un même arbre reliés entre eux.

Nous pouvons définir récursivement la hauteur h d'un noeud X à partir de

celle de son parent :

h (racine) = 1;
h ( X ) = 1+ h ( parent ( X ) )

Reprenons l'arbre précédent en exemple :

Page 79 sur 191

Calculons récursivement la hauteur du noeud 9, notée h(9) :

h(9) = 1+h(8)
h(8) = 1+h(5)
h(5) = 1+h(1)
h(1) = 1 => h(5)=2 => h(8)=3 => h(9)=4

Degré d'un noeud

Par définition le degré d'un noeud est égal au nombre de ses

descendants (enfants). Soient les deux exemples ci-dessous extraits de
l'arbre précédent :

Le noeud 1 est de degré 4, car il a 4 enfants

Le noeud 5 n'ayant qu'un enfant son degré est 1.

Le noeud 8 est de degré 2 car il a 2 enfants.

Remarquons que lorsqu'un arbre a tous ses noeuds de degré 1, on le

nomme arbre dégénéré et que c'est en fait une liste.

Page 80 sur 191

Hauteur ou profondeur d'un arbre

Par définition c'est le nombre de noeuds du chemin le plus long dans

l'arbre. La hauteur h d'un arbre correspond donc au nombre de niveau
maximum :

h (Arbre) = max { h ( X ) / X, X noeud de Arbre }

si Arbre = alors h( Arbre ) = 0

La hauteur de l'arbre ci-dessous :

Degré d'un arbre

Le degré d'un arbre est égal au plus grand des degrés de ses noeuds :

d°(Arbre) = max { d° ( X ) / X, X noeud de Arbre }

Soit à répertorier dans l'arbre ci-dessous le degré de chacun des noeuds :

d°(1) = 4 d°(2) = 0
d°(3) = 0 d°(4) = 2
d°(5) = 1 d°(6) = 0
d°(7) = 0 d°(8) = 2
d°(9) = 0 d°(10) = 0

La valeur maximale est 4 , donc cet arbre est de degré 4.

Page 81 sur 191

Taille d'un arbre

On appelle taille d'un arbre le nombre total de noeuds de cet arbre :

taille(< r , fg , fd >) = 1 + taille( fg ) + taille( fd )

Cet arbre a pour taille 10 (car il a 10 noeuds)

Arbre lexicographique

Rangement de mots par ordre lexical (alphabétique)

Soient les mots BON, BONJOUR, BORD, BOND, BOREALE, BIEN, il est
possible de les ranger ainsi dans une structure d'arbre :

Cet arbre se dénomme un arbre lexicographique.

Page 82 sur 191

Arbre d'héritage (exemple sur les graphiques)

Arbre de recherche

Voici à titre d'exemple que nous étudierons plus loin en détail, un arbre dont
les noeuds sont de degré 2 au plus et qui est tel que pour chaque noeud la
valeur de son enfant de gauche lui est inférieure ou égale, la valeur de son
enfant de droite lui est strictement supérieure.

Ci-dessous un tel arbre ayant comme racine 30 et stockant des entiers selon
cette répartition :

Page 83 sur 191

2. Les arbres binaires

Un arbre binaire est un arbre de degré 2 (dont les noeuds sont de degré 2 au
plus).

L'arbre abstrait de l'expression a*b + c-(d+e) est un arbre binaire :

Vocabulaire :
Les descendants (enfants) d'un noeud sont lus de gauche à droite et sont
appelés respectivement fils gauche (descendant gauche) et fils
droit(descendant droit) de ce noeud.

Exemple, soit l'arbre binaire A :

Page 84 sur 191

A =

Les sous-arbres gauche et droit de l'arbre A :

filsG( A ) = < * , a , b >

filsD( A ) = < - , c , < + , d , e > >

2.2 Exemples et implémentation d'arbre binaire étiqueté

Nous proposons de représenter un arbre binaire étiqueté selon deux

spécifications différentes classiques :

1°) Une implantation fondée sur une structure de tableau en allocation de

mémoire statique, nécessitant de connaître au préalable le nombre maximal
de noeuds de l'arbre (ou encore sa taille).

2°) Une implantation fondée sur une structure d'allocation de mémoire

dynamique implémentée soit par des pointeurs (variables dynamiques) soit
par des références (objets) .

2.2.1 - Implantation dans un tableau statique

Spécification concrète

Un noeud est une structure statique contenant 3 éléments :

o l'information du noeud
o le fils gauche
o le fils droit
Page 85 sur 191
Pour un arbre binaire de taille = n, chaque noeud de l'arbre binaire est
stocké dans une cellule d'un tableau de dimension 1 à n cellules. Donc
chaque noeud est repéré dans le tableau par un indice (celui de la cellule le
contenant).

Le champ fils gauche du noeud sera l'indice de la cellule contenant le

descendant gauche, et le champ fils droit vaudra l'indice de la cellule
contenant le descendant droit.

Exemple

Soit l'arbre binaire ci-après :

Selon l'implantation choisie, par hypothèse de départ, la racine <a, vers b,

vers c> est contenue dans la cellule d'indice 2 du tableau, les autres noeuds
sont supposés être rangés dans les cellules 1, 3,4,5 :

racine = table[2]
table[1] = < d , 0 , 0 >
table[2] = < a , 4 , 5 >
table[3] = < e , 0 , 0 >
table[4] = < b , 0 , 0 >
table[5] = < c , 1 , 3 >

Explications :

Page 86 sur 191

table[2] = < a , 4 , 5 > signifie que le fils gauche de ce noeud est dans
table[4] et son fils droit dans table[5]
table[5] = < c , 1 , 3 > signifie que le fils gauche de ce noeud est dans
table[1] et son fils droit dans table[3]
table[1] = < d , 0 , 0 > signifie que ce noeud est une feuille
...etc

Spécification d'implantation en Pascal

Nous proposons d'utiliser les déclarations suivantes :

const
taille = n; // n valeur effective 10, 1000, 10000 etc...
type
Noeud = record
info : T0;
filsG , filsD : 0..taille ;
end;
Tableau = Array[1..taille] of Noeud ;

ArbrBin = record
ptrRac : 0..taille;
table : Tableau ;
end;
Var
Tree : ArbrBin ;

Explications :

Lorsque [Link] = 0 on dit que l'arbre est vide.

L'accès à la racine de l'arbre s'effectue ainsi : [Link][ptrRac]
L'accès à l'info de la racine de l'arbre s'effectue ainsi
: [Link][ptrRac].info
L'accès au fils gauche de la racine de l'arbre s'effectue ainsi :
var
ptr:0..taille ;
ptr := [Link][ptrRac].filsG;
[Link][ptr] ....

L'insertion ou la suppression d'un noeud dans l'arbre ainsi représenté

s'effectue directement dans une cellule du tableau. Il faudra donc posséder
une structure (de liste, de pile ou de file par exemple) permettant de
connaître les cellules libres ou de ranger une cellule nouvellement libérée.
Une telle structure se dénomme "espace libre".
Page 87 sur 191
L'insertion se fera dans la première cellule libre, l'espace libre diminuant
d'une unité.
La suppression rajoutera une nouvelle cellule dans l'espace libre qui
augmentera d'une unité.

2.2.2 - Implantation avec des variables dynamiques

Spécification concrète

Le noeud reste une structure statique contenant 3 éléments dont 2 sont

dynamiques :

o l'information du noeud
o une référence vers le fils gauche
o une référence vers le fils droit

Exemple

Soit l'arbre binaire ci-après :

Selon l'implantation choisie, par hypothèse de départ, la référence vers

la racine pointe vers la structure statique (le noeud) < a, ref vers b, ref vers
c>

ref racine < a, ref vers b, ref vers c >

ref vers b < b, null, null >
ref vers c < a, ref vers d, ref vers e >
ref vers d < d, null, null >
ref vers e < e, null, null >

Page 88 sur 191

Spécification d'implantation en Pascal

Nous proposons d'utiliser les déclarations de variables dynamiques suivantes

:

type
ArbrBin = ^Noeud ;
Noeud = record
info : T0;
filsG , filsD : ArbrBin ;
end;
Var
Tree : ArbrBin ;

Explications :

Lorsque Tree = nil on dit que l'arbre est vide.

L'accès à la racine de l'arbre s'effectue ainsi : Tree
L'accès à l'info de la racine de l'arbre s'effectue ainsi : Tree^.info
L'accès au fils gauche de la racine de l'arbre s'effectue ainsi : Tree^.filsG
L'accès au fils gauche de la racine de l'arbre s'effectue ainsi : Tree^.filsD

Nous noterons une simplification notable des écritures dans cette

implantation par rappoprt à l'implantation dans un tableau statique. Ceci
provient du fait que la structure d'arbre est définie récursivement et que
la notion de variable dynamique permet une définition récursive donc plus
proche de la structure.

Page 89 sur 191

 2.2.3 - Implantation avec une classe

Nous livrons ci-dessous une écriture de la signature et l'implementation

minimale d'une classe d'arbre binaire nommée TreeBin en Delphi
(l'implementation complète est à faire lors des exercices sur les classes) :

interface
// dans cette classe tous les champ sont publics afin de simplifier l'écriture
TreeBin = class
public
Info : string;
filsG , filsD : TreeBin;
constructor CreerTreeBin(s:string);overload;
constructor CreerTreeBin(s:string; fg , fd : TreeBin);overload;
destructor Liberer;
end;

implementation
......
end.

Exercices : Arbre Binaire

Exercice 1 : Définition et insertion dans un arbre binaire

Enoncé :
Implémentez une structure représentant un nœud d’un arbre binaire en C, puis écrivez une
fonction permettant d’insérer un élément dans cet arbre en respectant l’ordre des valeurs
(arbre binaire de recherche).

Correction

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud d'arbre binaire

typedef struct Noeud {
int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

// Fonction de création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;

Page 90 sur 191

}

// Fonction d'insertion dans un arbre binaire de recherche

Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur);
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Affichage en ordre croissant (parcours In-Order)

void parcoursInfixe(Noeud* racine) {
if (racine != NULL) {
parcoursInfixe(racine->gauche);
printf("%d ", racine->donnee);
parcoursInfixe(racine->droite);
}
}

int main() {
Noeud* racine = NULL;

racine = inserer(racine, 50);

racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);
racine = inserer(racine, 60);
racine = inserer(racine, 80);

printf("Affichage en parcours In-Order : ");

parcoursInfixe(racine);
printf("\n");

return 0;
}

Exercice 2 : Recherche d'un élément dans un arbre binaire

Énoncé :
Implémentez une fonction permettant de rechercher un élément dans un arbre binaire de
recherche.
Page 91 sur 191
Correction :

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure d'un nœud

typedef struct Noeud {
int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

// Fonction de création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;
}

// Fonction d'insertion
Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur);
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Fonction de recherche d'un élément

Noeud* rechercher(Noeud* racine, int cle) {
if (racine == NULL || racine->donnee == cle) {
return racine;
}

if (cle < racine->donnee) {

return rechercher(racine->gauche, cle);
}

return rechercher(racine->droite, cle);

}

int main() {
Noeud* racine = NULL;
racine = inserer(racine, 50);
Page 92 sur 191
 racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);
racine = inserer(racine, 60);
racine = inserer(racine, 80);

int cle = 40;

Noeud* noeudTrouve = rechercher(racine, cle);

if (noeudTrouve != NULL) {
printf("L'élément %d a été trouvé dans l'arbre.\n", cle);
} else {
printf("L'élément %d n'existe pas dans l'arbre.\n", cle);
}

return 0;
}

Exercice 3 : Suppression d'un élément dans un arbre binaire

Enoncé :
Écrivez une fonction pour supprimer un nœud dans un arbre binaire de recherche.

Correction :

#include <stdio.h>
#include <stdlib.h>

// Définition du nœud
typedef struct Noeud {
int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

// Création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;
}

// Fonction d'insertion
Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur);
}

if (valeur < racine->donnee) {

Page 93 sur 191
 racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Trouver le minimum dans un sous-arbre

Noeud* noeudValeurMin(Noeud* noeud) {
Noeud* courant = noeud;
while (courant && courant->gauche != NULL) {
courant = courant->gauche;
}
return courant;
}

// Fonction de suppression
Noeud* supprimerNoeud(Noeud* racine, int cle) {
if (racine == NULL) return racine;

if (cle < racine->donnee) {

racine->gauche = supprimerNoeud(racine->gauche, cle);
} else if (cle > racine->donnee) {
racine->droite = supprimerNoeud(racine->droite, cle);
} else {
// Cas 1 : Nœud avec un seul enfant ou aucun
if (racine->gauche == NULL) {
Noeud* temp = racine->droite;
free(racine);
return temp;
} else if (racine->droite == NULL) {
Noeud* temp = racine->gauche;
free(racine);
return temp;
}

// Cas 2 : Nœud avec deux enfants

Noeud* temp = noeudValeurMin(racine->droite);
racine->donnee = temp->donnee;
racine->droite = supprimerNoeud(racine->droite, temp->donnee);
}

return racine;
}

// Fonction d'affichage en ordre croissant (parcours In-Order)

void parcoursInfixe(Noeud* racine) {
if (racine != NULL) {
parcoursInfixe(racine->gauche);
printf("%d ", racine->donnee);
Page 94 sur 191
 parcoursInfixe(racine->droite);
}
}

int main() {
Noeud* racine = NULL;
racine = inserer(racine, 50);
racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);
racine = inserer(racine, 60);
racine = inserer(racine, 80);

printf("Arbre avant suppression : ");

parcoursInfixe(racine);
printf("\n");

racine = supprimerNoeud(racine, 50);

printf("Arbre après suppression de 50 : ");

parcoursInfixe(racine);
printf("\n");

return 0;
}

2.3 Arbres binaires de recherche

 Nous avons étudié au chap4.6 des algorithmes de recherche en table,

en particulier la recherche dichotomique dans une table triée dont la
recherche s'effectue en O(log(n)) comparaisons.

 Toutefois lorsque le nombre des éléments varie (ajout ou suppression)

ces ajouts ou suppressions peuvent nécessiter des temps en O(n).

Page 95 sur 191

  En utilisant une liste chaînée qui approche bien la structure
dynamique (plus gourmande en mémoire qu'un tableau) on aura en
moyenne des temps de suppression ou de recherche au pire de l'ordre
de O(n). L'ajout en fin de liste ou en début de liste demandant un
temps constant noté O(1).

Les arbres binaires de recherche sont un bon compromis pour un

temps équilibré entre ajout, suppression et recherche.

Un arbre binaire de recherche satisfait aux critères suivants :

 L'ensemble des étiquettes est totalement ordonné.

 Une étiquette est dénommée clef.
 Les clefs de tous les noeuds du sous-arbre gauche d'un noeud X,
sont inférieures ou égales à la clef de X.
 Les clefs de tous les noeuds du sous-arbre droit d'un noeud X,
sont supérieures à la clef de X.

Nous en avons déjà vu un plus haut :

Prenons par exemple le noeud (25) son sous-arbre droit est bien composé de
noeuds dont les clefs sont supérieures à 25 : (29,26,28). Le sous-arbre
gauche du noeud (25) est bien composé de noeuds dont les clefs sont
inférieures à 25 : (18,9).

On appelle arbre binaire dégénéré un arbre binaire dont le degré = 1, ci-

dessous 2 arbres binaires de recherche dégénérés :

Page 96 sur 191

 Nous remarquons dans les deux cas que nous avons affaire à une liste
chaînée donc le nombre d'opérations pour la suppression ou la recherche est
au pire de l'ordre de O(n). Il faudra utiliser une catégorie spéciale d'arbres
binaires qui restent équilibrés (leurs feuilles sont sur 2 niveaux au plus) pour
assurer une recherche au pire en O(log(n)).

2.4 Arbres binaires partiellement ordonnés (tas)

Arbre parfait :

c'est un arbre binaire dont tous les noeuds de chaque niveau sont présents sauf éventuellement
au dernier niveau où il peut manquer des noeuds (noeuds terminaux = feuilles), dans ce cas
l'arbre parfait est un arbre binaire incomplet et les feuilles du dernier niveau doivent être
regroupées à partir de la gauche de l'arbre.

1 - Un arbre parfait complet :

(parfait complet : le dernier niveau est complet car il contient tous les
enfants )

Page 97 sur 191

2 - Un autre arbre parfait incomplet :

(parfait incomplet : le dernier niveau est incomplet car il manque 3 enfants,

mais ils
sont manquant à la droite du niveau, les feuilles sont regroupées à gauche)

3.a - Un arbre non parfait :

(non parfait : le dernier niveau est incomplet car il manque 1 enfant, les
feuilles
ne sont pas regroupées à gauche)

3.b - Un autre arbre non parfait :

(non parfait : les feuilles sont bien regroupées à gauche, mais

il manque 1 enfant à l'avant dernier niveau )

Un arbre binaire parfait se représente classiquement dans un tableau :

Les noeuds de l'arbre sont dans les cellules du tableau, il n'y a pas d'autre
information dans une cellule du tableau, l'accès à la topologie arborescente
est simulée à travers un calcul d'indice permettant de parcourir les cellules
du tableau selon un certain 'ordre' de numérotation correspondant en fait à
Page 98 sur 191
un parcours hiérarchique de l'arbre. En effet ce sont les numéros de ce
parcours qui servent d'indice aux cellules du tableau :

Si t est ce tableau, nous avons donc les règles d'accès suivantes :

 t[1] est la racine :

Lorsque l'indice i d'une cellule (d'un noeud) est fixé :

 t[i div 2] est le père de t[i] pour i > 1 :

 t[2 * i] et t[2 * i + 1] sont les deux fils, s'ils existent, de t[i] :

Page 99 sur 191

  si p est le nombre de noeuds de l'arbre et si 2 * i = p, t[i] n'a qu'un fils,
t[p].

si i est supérieur à p div 2, t[i] est une feuille.

Exemple de rangement d'un tel arbre dans un tableau (pour une vision
pédagogique on a figuré l'indice de numérotation hiérarchique de chaque
noeud dans le rectangle associé au noeud) :

Cet arbre sera stocké dans un tableau en disposant séquentiellement et de

façon contigüe les noeuds selon la numérotation hiérarchique (l'index de la
cellule = le numéro hiérarchique du noeud).

Dans cette disposition le passage d'un noeud de numéro k (indice dans le

tableau) vers son fils gauche s'effectue par calcul d'indice, le fils gauche se
trouvera dans la cellule d'index 2*k du tableau, son fils droit se trouvant
dans la cellule d'index 2*k + 1 du tableau. Ci-dessous l'arbre précédent est
stocké dans un tableau : le noeud d'indice hiérarchique 1 (la racine) dans la
cellule d'index 1, le noeud d'indice hiérarchique 2 dans la cellule d'index
2, etc...

Le nombre qui figure dans la cellule (nombre qui vaut l'index de la cellule =
le numéro hiérarchique du noeud) n'est mis là qu'à titre pédagogique afin de
bien comprendre le mécanisme.

Page 100 sur 191

 On voit par exemple, que par calcul on a bien le fils gauche du noeud
d'indice 2 est dans la cellule d'index 2*2 = 4 et son fils droit se trouve dans la
cellule d'index 2*2+1 = 5 ...

Exemple d'un arbre parfait étiqueté avec des caractères :

arbre parfait parcours hiérarchique

rangement de l'arbre
dans un tableau
numérotation hiérarchique

Soit le noeud 'b' de numéro hiérarchique 2

(donc rangé dans la cellule de rang 2 du
tableau), son fils gauche est 'd', son fils
droit est 'e'.

Arbre partiellement ordonné :

C'est un arbre étiqueté dont les valeurs des noeuds appartiennent à un ensemble muni d'une
relation d'ordre total (les nombres entiers, réels etc... en sont des exemples) tel que pour un
noeud donné tous ses fils ont une valeur supérieure ou égale à celle de leur père.
Page 101 sur 191
Exemple de deux arbres partiellement ordonnés sur
l'ensemble {20,27,29,30,32,38,45,45,50,51,67,85} d'entiers naturels :

Nous remarquons que la racine d'un tel arbre est toujours l'élément de
l'ensemble possédant la valeur minimum (le plus petit élément de
l'ensemble), car la valeur de ce noeud par construction est inférieure à celle
de ses fils et par transitivité de la relation d'ordre à celles de ses descendants
c'est le minimum. Si donc nous arrivons à ranger une liste d'éléments dans
un tel arbre le minimum de cette liste est atteignable immédiatement comme
racine de l'arbre.

En reprenant l'exemple précédent sur 3 niveaux : (entre parenthèses le

numéro hiérarchique du noeud)

Voici réellement ce qui est stocké dans le tableau :(entre parenthèses l'index
de la cellule contenant le noeud)

Page 102 sur 191

 Le tas :

On appelle tas un tableau représentant un arbre parfait partiellement ordonné.

L'intérêt d'utiliser un arbre parfait complet ou incomplet réside dans le fait que le tableau est
toujours compacté, les cellules vides s'il y en a se situent à la fin du tableau.

Le fait d'être partiellement ordonné sur les valeurs permet d'avoir immédiatement un
extremum à la racine.

2.5 Parcours d'un arbre binaire

Objectif : les arbres sont des structures de données. Les informations sont
contenues dans les noeuds de l'arbre, afin de construire des algorithmes
effectuant des opérations sur ces informations (ajout, suppression,
modification,...) il nous faut pouvoir examiner tous les noeuds d'un arbre.
Nous devons avoir à notre disposition un moyen de parcourir ou traverser
chaque noeud de l'arbre et d'appliquer un traitement à la donnée rattachée à
chaque noeud.

Parcours :

L'opération qui consiste à retrouver systématiquement tous

les noeuds d'un arbre et d'y appliquer un même traitement se
dénomme parcours de l'arbre.

Parcours en largeur ou hiérarchique :

Un algorithme classique consiste à explorer chaque noeud

d'un niveau donné de gauche à droite, puis de passer au
niveau suivant. On dénomme cette stratégie le parcours en
largeur de l'arbre.

Exemple (déjà cité ci-haut) :

Page 103 sur 191

 Algorithme de parcours en largeur (hiérarchique)

Cet algorithme nécessite l'utilisation d'un file du type Fifo

dans laquelle l'on stocke les noeuds.

Largeur ( Arbre )
si Arbre alors
ajouter racine de l'Arbre dans Fifo;
tantque Fifo faire
prendre premier de Fifo;
traiter premier de Fifo;
ajouter filsG de premier de Fifo dans Fifo;
ajouter filsD de premier de Fifo dans Fifo;
ftant
Fsi

Un autre algorithme général de parcours d'un arbre est employé très souvent,
il s'agit du parcours dit "en profondeur".

Parcours en profondeur :

La stratégie consiste à descendre le plus profondément

soit jusqu'aux feuilles d'un noeud de l'arbre, puis lorsque
toutes les feuilles du noeud ont été visitées, l'algorithme
"remonte" au noeud plus haut dont les feuilles n'ont pas
encore été visitées.

Notons que ce parcours peut s'effectuer systématiquement en commençant

par le fils gauche, puis en examinant le fils droit ou bien l'inverse.

Parcours en profondeur par la gauche :

Traditionnellement c'est l'exploration fils gauche, puis

ensuite fils droit qui est retenue on dit alors que l'on traverse
l'arbre en "profondeur par la gauche".

Schémas montrant le principe du parcours exhaustif en "profondeur par la

gauche" :

Soit l'arbre binaire suivant:

Page 104 sur 191

Appliquons lui la méthode de parcours proposée :

Chaque noeud a bien été examiné selon les principes du parcours en

profondeur :

En fait pour ne pas surcharger les schémas arborescents, nous omettons de

dessiner à la fin de chaque noeud de type feuille les deux noeuds enfants
vides qui permettent de reconnaître que le parent est une feuille :

Lorsque la compréhension nécessitera leur dessin nous conseillons au lecteur

de faire figurer explicitement dans son schéma arborescent les noeuds vides
au bout de chaque feuille.

Algorithme général récursif de parcours en profondeur :

Page 105 sur 191

 parcourir ( Arbre )
si Arbre alors
Traiter-1 (info([Link])) ;
parcourir ( [Link] ) ;
Traiter-2 (info([Link])) ;
parcourir ( [Link] ) ;
Traiter-3 (info([Link])) ;
Fsi

Les différents traitements Traiter-1 ,Traiter-2 et Traiter-3 consistent à traiter

l'information située dans le noeud actuellement traversé soit lorsque l'on
descend vers le fils gauche ( Traiter-1 ), soit en allant examiner le fils droit
( Traiter-2 ), soit lors de la remonté après examen des 2 fils ( Traiter-3 ).

En fait on n'utilise que trois variantes de cet algorithme, celles qui

constituent des parcours ordonnés de l'arbre en fonction de l'application du
traitement de l'information située aux noeuds. Chacun de ces 3
parcours définissent un ordre implicite (préfixé, infixé, postfixé) sur
l'affichage et le traitement des données contenues dans l'arbre.

Algorithme de parcours en pré-ordre : (ordre préfixé)

parcourir ( Arbre )
si Arbre alors
Traiter-1 (info([Link])) ;
parcourir ( [Link] ) ;
parcourir ( [Link] ) ;
Fsi

Algorithme de parcours en post-ordre : (ordre postfixé)

parcourir ( Arbre )
si Arbre alors
parcourir ( [Link] ) ;
parcourir ( [Link] ) ;
Traiter-3 (info([Link])) ;
Fsi

Algorithme de parcours en ordre symétrique : (ordre infixé)

parcourir ( Arbre )

Page 106 sur 191

si Arbre alors
parcourir ( [Link]) ;
Traiter-2 (info([Link])) ;
parcourir ( [Link] ) ;
Fsi

Illustration pratique d'un parcours général en profondeur

Le lecteur trouvera ailleurs des exemples de parcours selon l'un des 3 ordres
infixé, préfixé, postfixé, nous proposons un exemple didactique de parcours
général avec les 3 traitements.

L'assistant d'algorithmes propose des exemples d'arbres de programmation

d'algorithmes simples, en particulier celui de l'équation du second degré.
Nous allons voir comment utiliser une telle structure arborescente afin de
restituer du texte algorithmique linéaire.

Voici ce que nous donne l'assistant :

Nous pouvons établir un modèle d'arbre (binaire ici) où les informations au

noeud sont au nombre de 3 (nous les nommerons attribut n°1, attribut
n°2 et attribut n°3). Chaque attribut est une chaîne de caractères, vide s'il y
a lieu.

Page 107 sur 191

Nous noterons ainsi un attribut contenant une chaîne vide :

Ci-dessous une représentation de l'arbre de programmation précédent :

Traitement des attributs pour produire le texte :

Traiter-1 ([Link] n°1) consiste à écrire le contenu de

l'Attribut n°1 :

si Attribut n°1 non vide alors

ecrire( Attribut n°1 )
Fsi

Traiter-2 ([Link] n°2) consiste à écrire le contenu de

l'Attribut n°2 :

si Attribut n°2 non vide alors

ecrire( Attribut n°2 )
Fsi

Traiter-3 ([Link] n°3) consiste à écrire le contenu de

l'Attribut n°3 :

Page 108 sur 191

 si Attribut n°3 non vide alors
ecrire( Attribut n°3 )
Fsi

Parcours en profondeur de l'arbre de programmation de l'équation du second

degré :

parcourir ( Arbre )
si Arbre alors
Traiter-1 (Attribut n°1)
;
parcourir
( [Link] ) ;
Traiter-2 (Attribut n°2)
;
parcourir
( [Link] ) ;
Traiter-3 (Attribut n°3)
;
Fsi

Texte produit après parcours :

si A=0 alors
si B=0 alors
si C=0 alors
ecrire(R est sol)
sinon

ecrire(pas de sol)
Fsi
sinon

X1=-C/B;
ecrire(X1);
Fsi
sinon

Equation2
Fsi

Page 109 sur 191

Rappellons que le symbole représente la chaîne vide il est uniquement
mis dans le texe dans le but de permettre le suivi du parcours de l'arbre.

Pour bien comprendre le parcours aux feuilles de l'arbre précédent, nous

avons fait figurer ci-dessous sur un exemple, les noeuds vides de chaque
feuille et le parcours complet associé :

Le parcours partiel ci-haut produit le texte algorithmique suivant (le

symbole est encore écrit pour la compréhension de la traversée) :

si B=0 alors
si C=0 alors
ecrire(R est sol)
sinon

ecrire(pas de sol)
Fsi
sinon

Exercice proposé au lecteur

Page 110 sur 191

Soit l'arbre suivant possédant 2 attributs par noeuds (un symbole de type
caractère)

On propose le traitement en profondeur de l'arbre comme suit :

L'attribut de gauche est écrit en descendant, l'attribut de droite est écrit
en remontant, il n'y a pas d'attribut ni de traitement lors de l'examen du fils
droit en venant du fils gauche.

écrire la chaîne de caractère obtenue par le parcours ainsi défini.

Réponse : abcdfghjkiemnoqrsuv

Terminons cette revue des descriptions algorithmiques des différents

parcours classiques d'arbre binaire avec le parcours en largeur (Cet
algorithme nécessite l'utilisation d'un file du type Fifo dans laquelle l'on
stocke les nœuds).

Algorithme de parcours en largeur

Largeur ( Arbre )

si Arbre alors
ajouter racine de l'Arbre dans Fifo;
tantque Fifo faire
prendre premier de Fifo;
traiter premier de Fifo;
ajouter filsG de premier de Fifo
dans Fifo;
ajouter filsD de premier de Fifo
dans Fifo;
ftant
Fsi

Page 111 sur 191

Exercices : Arbre Binaire de Recherche (ABR)
Exercice 1 : Création et insertion dans un arbre binaire de recherche

Enoncé :
Ecrire un programme qui permet de :
Définir un nœud pour un arbre binaire de recherche (ABR).
Insérer des éléments dans cet ABR.
Afficher l’arbre en parcours infixe (ordre croissant).
#include <stdio.h>
#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {
int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

// Fonction de création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;
}

// Fonction d'insertion dans un arbre binaire de recherche

Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur);
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Affichage en ordre croissant (parcours infixe)

void parcoursInfixe(Noeud* racine) {
if (racine != NULL) {
parcoursInfixe(racine->gauche);
printf("%d ", racine->donnee);
parcoursInfixe(racine->droite);
}
}

int main() {
Noeud* racine = NULL;

racine = inserer(racine, 50);

racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);

Page 112 sur 191

 racine = inserer(racine, 60);
racine = inserer(racine, 80);

printf("Affichage en parcours infixe (ordre croissant) : ");

parcoursInfixe(racine);
printf("\n");

return 0;
}

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {
int donnee; // Valeur stockée dans le nœud
struct Noeud* gauche; // Pointeur vers le sous-arbre gauche
struct Noeud* droite; // Pointeur vers le sous-arbre droit
} Noeud;

// Fonction de création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); //
Allocation dynamique de mémoire
nouveauNoeud->donnee = valeur; // Affectation de la valeur au
nœud
nouveauNoeud->gauche = nouveauNoeud->droite = NULL; //
Initialisation des sous-arbres à NULL
return nouveauNoeud;
}

// Fonction d'insertion dans un arbre binaire de recherche

Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur); // Création d'un nouveau nœud si
l'arbre est vide
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur); //
Insertion dans le sous-arbre gauche
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur); //
Insertion dans le sous-arbre droit
}

return racine;
}

// Fonction d'affichage en ordre croissant (parcours infixe)

void parcoursInfixe(Noeud* racine) {
if (racine != NULL) {
parcoursInfixe(racine->gauche); // Parcours du sous-arbre
gauche
printf("%d ", racine->donnee); // Affichage de la valeur du
nœud
parcoursInfixe(racine->droite); // Parcours du sous-arbre
droit
}
}

Page 113 sur 191

 int main() {
Noeud* racine = NULL; // Initialisation de la racine à NULL

// Insertion de valeurs dans l'arbre binaire de recherche

racine = inserer(racine, 50);
racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);
racine = inserer(racine, 60);
racine = inserer(racine, 80);

printf("Affichage en parcours infixe (ordre croissant) : ");

parcoursInfixe(racine); // Affichage de l'arbre trié
printf("\n");

return 0;
}

Exercice 2 : Recherche d’un élément dans un arbre binaire de recherche

Enoncé :
Ecrire une fonction qui recherche un élément donné dans un arbre binaire de recherche. La
fonction doit :
1. Retourner le nœud trouvé si l’élément existe.
2. Retourner NULL si l’élément n’est pas trouvé.
Correction :

#include <stdio.h>
#include <stdlib.h>

// Définition du nœud
typedef struct Noeud {
int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

// Création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;
}

// Fonction d'insertion
Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur);
}

Page 114 sur 191

 if (valeur < racine->donnee) {
racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Fonction de recherche d'un élément

Noeud* rechercher(Noeud* racine, int cle) {
if (racine == NULL || racine->donnee == cle) {
return racine;
}

if (cle < racine->donnee) {

return rechercher(racine->gauche, cle);
}

return rechercher(racine->droite, cle);

}

int main() {
Noeud* racine = NULL;
racine = inserer(racine, 50);
racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);
racine = inserer(racine, 60);
racine = inserer(racine, 80);

int cle = 40;

Noeud* noeudTrouve = rechercher(racine, cle);

if (noeudTrouve != NULL) {
printf("L'élément %d a été trouvé dans l'arbre.\n", cle);
} else {
printf("L'élément %d n'existe pas dans l'arbre.\n", cle);
}

return 0;
}

#include <stdio.h>
#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {
int donnee; // Valeur contenue dans le nœud
struct Noeud* gauche; // Pointeur vers le sous-arbre gauche
Page 115 sur 191
 struct Noeud* droite; // Pointeur vers le sous-arbre droit
} Noeud;

// Fonction de création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {
Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Allocation dynamique de
mémoire
nouveauNoeud->donnee = valeur; // Affectation de la valeur au nœud
nouveauNoeud->gauche = nouveauNoeud->droite = NULL; // Initialisation des sous-arbres
à NULL
return nouveauNoeud;
}

// Fonction d'insertion dans un arbre binaire de recherche

Noeud* inserer(Noeud* racine, int valeur) {
if (racine == NULL) {
return creerNoeud(valeur); // Création d'un nouveau nœud si l'arbre est vide
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur); // Insertion dans le sous-arbre gauche
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur); // Insertion dans le sous-arbre droit
}

return racine;
}

// Fonction de recherche d'un élément dans l'arbre binaire de recherche

Noeud* rechercher(Noeud* racine, int cle) {
if (racine == NULL || racine->donnee == cle) {
return racine; // Retourne le nœud trouvé ou NULL si l'élément n'existe pas
}

if (cle < racine->donnee) {

return rechercher(racine->gauche, cle); // Recherche dans le sous-arbre gauche
}

return rechercher(racine->droite, cle); // Recherche dans le sous-arbre droit

}

int main() {
Noeud* racine = NULL; // Initialisation de la racine à NULL

// Insertion de valeurs dans l'arbre binaire de recherche

racine = inserer(racine, 50);
racine = inserer(racine, 30);
racine = inserer(racine, 70);
racine = inserer(racine, 20);
racine = inserer(racine, 40);
racine = inserer(racine, 60);
Page 116 sur 191
 racine = inserer(racine, 80);

// Recherche d'un élément dans l'arbre

int cle = 40;
Noeud* noeudTrouve = rechercher(racine, cle);

if (noeudTrouve != NULL) {
printf("L'élément %d a été trouvé dans l'arbre.\n", cle);
} else {
printf("L'élément %d n'existe pas dans l'arbre.\n", cle);
}

return 0;
}

Explications :

1. Définition de la structure Noeud : Un nœud contient une valeur (donnee) et deux

pointeurs (gauche et droite) pour les sous-arbres.
2. Création d'un nœud : creerNoeud(int valeur) alloue dynamiquement un nœud et
initialise ses enfants à NULL.
3. Insertion dans l'arbre : inserer(Noeud* racine, int valeur) insère un élément
tout en respectant la propriété de l'arbre binaire de recherche.
4. Recherche d'un élément : rechercher(Noeud* racine, int cle) parcourt l'arbre
récursivement pour trouver la clé spécifiée.
5. Programme principal main() :
o Crée un arbre binaire de recherche et insère plusieurs valeurs.
o Recherche l'élément 40 dans l'arbre.
o Affiche un message indiquant si l'élément a été trouvé ou non.

Exercice 3 : Suppression d’un élément dans un arbre binaire de recherche

Enoncé :
Implémentez une fonction pour supprimer un élément d’un arbre binaire de recherche en
respectant les règles suivantes :
1. Si le nœud à supprimer n’a pas d’enfant, il est supprimé directement.
2. S’il a un seul enfant, cet enfant remplace le nœud supprimé.
3. S’il a deux enfants, on le remplace par son successeur en ordre.
Correction :
#include <stdio.h>
#include <stdlib.h>

typedef struct Noeud {

int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

Noeud* creerNoeud(int valeur) {

Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
Page 117 sur 191
 nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;
}

Noeud* inserer(Noeud* racine, int valeur) {

if (racine == NULL) {
return creerNoeud(valeur);
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Fonction de suppression
Noeud* supprimerNoeud(Noeud* racine, int cle) {
if (racine == NULL) return racine;

if (cle < racine->donnee) {

racine->gauche = supprimerNoeud(racine->gauche, cle);
} else if (cle > racine->donnee) {
racine->droite = supprimerNoeud(racine->droite, cle);
} else {
if (racine->gauche == NULL) {
Noeud* temp = racine->droite;
free(racine);
return temp;
} else if (racine->droite == NULL) {
Noeud* temp = racine->gauche;
free(racine);
return temp;
}
}
return racine;
}

int main() {
Noeud* racine = NULL;
racine = inserer(racine, 50);
racine = supprimerNoeud(racine, 50);
return 0;
}

#include <stdio.h>
#include <stdlib.h>
Page 118 sur 191
typedef struct Noeud {
int donnee;
struct Noeud* gauche;
struct Noeud* droite;
} Noeud;

Noeud* creerNoeud(int valeur) {

Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud));
nouveauNoeud->donnee = valeur;
nouveauNoeud->gauche = nouveauNoeud->droite = NULL;
return nouveauNoeud;
}

Noeud* inserer(Noeud* racine, int valeur) {

if (racine == NULL) {
return creerNoeud(valeur);
}

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur);
} else if (valeur > racine->donnee) {
racine->droite = inserer(racine->droite, valeur);
}

return racine;
}

// Fonction de suppression
Noeud* supprimerNoeud(Noeud* racine, int cle) {
if (racine == NULL) return racine;

if (cle < racine->donnee) {

racine->gauche = supprimerNoeud(racine->gauche, cle);
} else if (cle > racine->donnee) {
racine->droite = supprimerNoeud(racine->droite, cle);
} else {
if (racine->gauche == NULL) {
Noeud* temp = racine->droite;
free(racine);
return temp;
} else if (racine->droite == NULL) {
Noeud* temp = racine->gauche;
free(racine);
return temp;
}
}
return racine;
}

int main() {
Page 119 sur 191
 Noeud* racine = NULL;
racine = inserer(racine, 50);
racine = supprimerNoeud(racine, 50);
return 0;
}

Explications :

1. Définition de la structure Noeud : Un nœud contient une valeur (donnee) et deux

pointeurs (gauche et droite) pour les sous-arbres.
2. Création d'un nœud : creerNoeud(int valeur) alloue dynamiquement un nœud et
initialise ses enfants à NULL.
3. Insertion dans l'arbre : inserer(Noeud* racine, int valeur) insère un élément
tout en respectant la propriété de l'arbre binaire de recherche.
4. Suppression d'un nœud : supprimerNoeud(Noeud* racine, int cle) :
o Recherche le nœud à supprimer.
o Si le nœud a un seul enfant, il est remplacé par son sous-arbre non NULL.
o Si le nœud n'a aucun enfant, il est simplement supprimé.
5. Programme principal main() :
o Crée un arbre avec une racine contenant la valeur 50.
o Supprime le nœud 50.
o La racine devient NULL après suppression.

Voici une version améliorée du programme qui gère tous les cas de suppression, y
compris le cas où le nœud à supprimer a deux enfants. Dans ce cas, on remplace le
nœud par son successeur immédiat (le plus petit élément du sous-arbre droit).

#include <stdio.h>

#include <stdlib.h>

// Définition de la structure du nœud

typedef struct Noeud {

int donnee; // Valeur stockée dans le nœud

struct Noeud* gauche; // Pointeur vers le sous-arbre gauche

struct Noeud* droite; // Pointeur vers le sous-arbre droit

} Noeud;

Page 120 sur 191

// Fonction de création d'un nouveau nœud

Noeud* creerNoeud(int valeur) {

Noeud* nouveauNoeud = (Noeud*)malloc(sizeof(Noeud)); // Allocation dynamique de

mémoire

nouveauNoeud->donnee = valeur; // Affectation de la valeur au nœud

nouveauNoeud->gauche = nouveauNoeud->droite = NULL; // Initialisation des sous-arbres

à NULL

return nouveauNoeud;

// Fonction d'insertion dans un arbre binaire de recherche

Noeud* inserer(Noeud* racine, int valeur) {

if (racine == NULL) {

return creerNoeud(valeur); // Création d'un nouveau nœud si l'arbre est vide

if (valeur < racine->donnee) {

racine->gauche = inserer(racine->gauche, valeur); // Insertion dans le sous-arbre gauche

} else if (valeur > racine->donnee) {

racine->droite = inserer(racine->droite, valeur); // Insertion dans le sous-arbre droit

return racine;

Page 121 sur 191

// Fonction pour trouver le plus petit nœud dans un sous-arbre

Noeud* trouverMinimum(Noeud* noeud) {

while (noeud->gauche != NULL) {

noeud = noeud->gauche;

return noeud;

// Fonction de suppression d'un nœud dans l'arbre binaire de recherche

Noeud* supprimerNoeud(Noeud* racine, int cle) {

if (racine == NULL) return racine; // Retourner NULL si l'arbre est vide

// Recherche du nœud à supprimer

if (cle < racine->donnee) {

racine->gauche = supprimerNoeud(racine->gauche, cle); // Recherche dans le sous-arbre

gauche

} else if (cle > racine->donnee) {

racine->droite = supprimerNoeud(racine->droite, cle); // Recherche dans le sous-arbre

droit

} else {

// Cas où le nœud a un seul enfant ou aucun enfant

if (racine->gauche == NULL) {

Noeud* temp = racine->droite;

free(racine);

return temp; // Retourne le sous-arbre droit

} else if (racine->droite == NULL) {

Page 122 sur 191

 Noeud* temp = racine->gauche;

free(racine);

return temp; // Retourne le sous-arbre gauche

// Cas où le nœud a deux enfants : trouver le successeur (plus petit élément du sous-arbre
droit)

Noeud* temp = trouverMinimum(racine->droite);

racine->donnee = temp->donnee; // Remplace la valeur du nœud à supprimer par celle du

successeur

racine->droite = supprimerNoeud(racine->droite, temp->donnee); // Supprime le

successeur

return racine;

// Fonction d'affichage en ordre croissant (parcours infixe)

void parcoursInfixe(Noeud* racine) {

if (racine != NULL) {

parcoursInfixe(racine->gauche); // Parcours du sous-arbre gauche

printf("%d ", racine->donnee); // Affichage de la valeur du nœud

parcoursInfixe(racine->droite); // Parcours du sous-arbre droit

int main() {

Page 123 sur 191

 Noeud* racine = NULL; // Initialisation de la racine à NULL

// Insertion de valeurs dans l'arbre

racine = inserer(racine, 50);

racine = inserer(racine, 30);

racine = inserer(racine, 70);

racine = inserer(racine, 20);

racine = inserer(racine, 40);

racine = inserer(racine, 60);

racine = inserer(racine, 80);

printf("Arbre avant suppression : ");

parcoursInfixe(racine);

printf("\n");

// Suppression du nœud contenant la valeur 50 (racine de l'arbre)

racine = supprimerNoeud(racine, 50);

printf("Arbre après suppression de 50 : ");

parcoursInfixe(racine);

printf("\n");

return 0;

Page 124 sur 191

 Explications des améliorations :

1. Ajout de la fonction trouverMinimum(Noeud* noeud) :

o Cette fonction trouve le plus petit nœud dans un sous-arbre.
o Elle est utilisée pour gérer le cas où le nœud à supprimer a deux enfants.
2. Correction de supprimerNoeud() :
o Lorsqu'un nœud a deux enfants, on remplace sa valeur par celle du
successeur immédiat.
o Le successeur immédiat est le plus petit élément du sous-arbre
droit.
o Après le remplacement, on supprime ce successeur du sous-arbre droit.
3. Ajout de parcoursInfixe() :
o Cette fonction affiche l’arbre en ordre croissant pour mieux visualiser
les modifications.
4. Modification du main() :
o L'arbre est affiché avant et après suppression pour observer les
changements.

Chapitre 5 : Les Graphes

Graphes non orientés
La définition d'un graphe non orienté correspond tout à fait à l'idée que l'on s'en fait
intuitivement : un ensemble de points, dont certains sont reliés par des lignes
parcourables dans les deux sens.

Soyons tout de même un peu plus précis à la fois dans la terminologie et dans
la définition.

Définition

Un graphe non orienté G=(V,E)G=(V,E) est la donnée :

 D’un ensemble VV dont les éléments sont appelés les sommets du graphe.
 D’un ensemble EE dont les éléments sont des parties à un ou deux éléments
de VV, et sont appelés les arêtes du graphe.

Donnons de suite un exemple afin de fixer les idées.

Example 1.1. Un graphe non orienté

Pour définir un graphe non orienté, il faut donc commencer par décrire l'ensemble de
ses sommets :

Page 125 sur 191

 V={A,B,C,D,E}V={A,B,C,D,E}
On peut alors donner l'ensemble de ses arêtes :

E={{A,B},{B},{B,C},{B,D},{C,D},{E,C}}E={{A,B},{B},{B,C},{B,D},{C,D},{E,C}}

Cette définition mathématique d'un graphe est rigoureuse et autosuffisante. Pour

autant, on la complètera souvent par une représentation graphique afin de la rendre
plus parlante et interprétable.

Définition

La représentation sagittale d’un graphe non orienté est sa représentation sous forme
de schéma, les sommets étant modélisés par des disques et les arêtes par des lignes.

Complétons maintenant le premier exemple.

Example 1.2. Des représentations sagittales

Reprenons le graphe GG de l'exemple précédent. Il est défini par :
V={A,B,C,D,E}V={A,B,C,D,E}
et

E={{A,B},{B},{B,C},{B,D},{C,D},{E,C}}E={{A,B},{B},{B,C},{B,D},{C,D},{E,C}}
Sa représentation sagittale va donc comporter cinq disques (un pour chacun des
sommets) et six lignes (une pour chacune des arêtes) :

A noter qu'un même graphe peut bien sûr avoir plusieurs représentations sagittales.
En voici par exemple une autre du même graphe :

Page 126 sur 191

Introduisons un peu de vocabulaire complémentaire.

Définitions

Deux sommets reliés par une arête sont dits adjacents.

L’ordre d’un graphe est le nombre de ses sommets.
Une boucle est une arête ne possédante qu'un seul élément.
Un graphe ne comportant pas de boucles est un graphe simple.

Nous pouvons à présent terminer notre exemple récurrent.

Example 1.3. Illustration des termes techniques

Reprenons le graphe GG des exemples précédents :

 Les sommets DD et CC sont adjacents car le graphe GG comporte

l'arête {C,D}{C,D}.
 L'ordre du graphe GG est égal à 55.
 Le graphe GG n'est pas un graphe simple car il comporte une boucle,
l'arête {B}{B}.

Page 127 sur 191

 Graphes orientés
Comme le lecteur s'y attend, ce qui va différer avec les graphes orientés est que l'on va
imposer une direction sur les liaisons entre sommets.

Définition

Un graphe orienté G=(V,E) est la donnée :

 D’un ensemble V dont les éléments sont appelés les sommets du graphe.
 D’un ensemble E dont les éléments sont des couples d'éléments de VV, et sont
appelés les arcs du graphe.

Comme souvent, un petit exemple ne sera pas superflu.

Example 1.4. Un graphe orienté

Pour définir un graphe orienté, il faut donc commencer par décrire l'ensemble de
ses sommets :

V={A,B,C,D,E}V={A,B,C,D,E}
On peut alors donner l'ensemble de ses arcs :

E={(A,A),(A,B),(B,D),(C,B),(C,D),(D,C),(E,A)}E={(A,A),(A,B),(B,D),(C,B),(C,D),(D,
C),(E,A)}

Comme dans le cas des graphes non orientés, une représentation graphique permettra
une meilleure appréhension.

Définition

La représentation sagittale d’un graphe orienté est sa représentation sous forme

de schéma, les sommets étant modélisés par desdisques et les arcs par des flèches.

Poursuivons notre exemple.

Example 1.5. Une représentation sagittale

Reprenons le graphe GG de l'exemple précédent. Rappelons qu'il est défini par :
V={A,B,C,D,E}V={A,B,C,D,E}
et

E={(A,A),(A,B),(B,D),(C,B),(C,D),(D,C),(E,A)}E={(A,A),(A,B),(B,D),(C,B),(C,D),(D,
C),(E,A)}
Sa représentation sagittale va donc comporter cinq disques (un pour chacun des
sommets) et sept flèches (une pour chacun des arcs) :

Page 128 sur 191

On définit les notions de boucle, de graphe simple et d’ordre comme dans le cas des
graphes non orientés. Par contre la notion de sommets adjacents n'a plus lieu d'être, il
faut la substituer par un concept prenant en compte l'orientation.

Définition

En présence d'un arc de la forme (x,y)(x,y), on dit que yy est un successeur de xx et

que xx est un prédécesseur de yy.
On dit également que xx est l’origine de l’arc (x,y)(x,y) et que yy est son extrémité.

Revenons sur notre exemple et terminons le.

Example 1.6. Illustration des termes techniques

Reprenons le graphe GG des exemples précédents :

 Le graphe GG possède l'arc (B,D)(B,D) donc BB est un prédécesseur

de DD et DD un successeur de BB.
 Le sommet EE est l'origine de l'arc (E,A)(E,A) et AA son extrémité.
 L'ordre du graphe GG est égal à 55.

Page 129 sur 191

  Le graphe GG n'est pas un graphe simple car il comporte une boucle,
l'arc (A,A)(A,A).

Définitions complémentaires
Nous allons terminer cette première partie par quelques définitions
générales concernant les deux types de graphes, orientés ou non.

Graphes complets

Dans un graphe complet tous les sommets sont reliés entre eux.

Définition

Un graphe non orienté est complet s’il est simple et si deux sommets quelconques sont
reliés par une arête.
Un graphe orienté est complet s’il est simple et si pour toute paire de
sommets {x,y}{x,y} il existe au moins un des deux arcs (x,y)(x,y) ou (y,x)(y,x).

Example 1.7. Des graphes complets

Voici le graphe complet non orienté d'ordre 55 :

Voici un graphe complet orienté d'ordre 44 :

Page 130 sur 191

Vu sa structure bien particulière, il est facile de dénombrer le nombre d'arêtes d'un
graphe complet non orienté.

Propriété

Un graphe non orienté complet d'ordre nn possède n(n−1)2n(n-1)2 arêtes.

Démonstrations

Chacun des nn sommets est adjacent aux n−1n-1 autres. Ce qui donne a
priori n(n−1)n(n-1) arêtes. Mais dans ce calcul chaque arête est comptabilisée deux fois,
une pour chacune de ses extrémités. On a donc bien finalement n(n−1)2n(n-1)2 arêtes.
Q.E.D.
On peut également faire une preuve combinatoire de ce résultat. Une arête est en fait une
combinaison de deux éléments d'un ensemble à nn éléments (l'ensemble des sommets
du graphe). Le graphe étant complet il possèdera autant d'arêtes que le nombre de ces
combinaisons, i.e. (n2)=n(n−1)2(n2)=n(n-1)2. Q.E.D.

Multigraphes et sous-graphes

D’après les définitions des deux premières sous-parties, entre deux sommets d’un graphe
on a au plus une arête dans le cas non orienté, et au plus un arc de même sens dans le
cas orienté. Cela provient du fait que dans un ensemble tous les éléments sont différents,
donc en particulier dans celui des arcs ou arêtes il n'y a pas de doublons.

Si l'on autorise le fait d’avoir plusieurs arêtes ou plusieurs arcs de même sens entre deux
sommets, on ne parle plus de graphes mais de multigraphes.

Example 1.8. Des multigraphes

Un multigraphe non orienté :

Page 131 sur 191

Un multigraphe orienté :

Les définitions suivantes concernent des graphes construits comme sous-parties d'un
graphe existant.

Définitions

Soit G=(V,E)G=(V,E) un graphe orienté ou non.

Un graphe G′=(V′,E′)G′=(V′,E′) est un sous-graphe de GG si V′⊆VV′⊆V et E′⊆EE′⊆E.
Un sous-graphe recouvrant de GG est un sous-graphe de la
forme G′=(V,E′)G′=(V,E′), i.e. un sous-graphe de GG possédant tous les sommets
de GG.
Un sous-graphe induit de GG est un sous graphe G′=(V′,E′)G′=(V′,E′) dont les arêtes
ou arcs sont toutes celles de GG ayant leurs extrémités dans V′V′.

Illustrons tout cela par un exemple.

Example 1.9. Des sous-graphes

Considérons le graphe GG suivant :

Page 132 sur 191

Voici un sous-graphe de GG, constitué donc de certains sommets et arcs de GG :

Le sous-graphe suivant de GG ne comporte que trois sommets B,C,DB,C,D. Il

est induit, car il contient tous les arcs de GG ayant B,CB,C ou DD pour extrémités :

Le sous-graphe ci-dessous de G est recouvrant car il possède tous les sommets

de GG :

Page 133 sur 191

Graphes planaires

Concluons cette partie par la notion de graphe planaire.

Définition

Soit GG un graphe orienté ou non.

On dira que GG est planaire s’il admet une représentation sagittale où ses arêtes (ou
arcs) ne se coupent pas.

On n’étudiera pas de façon exhaustive les graphes planaires dans ce cours. C’est une
question assez difficile. On se contentera donc principalement d'exemples.

Example 1.10. Un graphe planaire

Considérons le graphe GG suivant :

Ce graphe est planaire car il admet aussi cette représentation sagittale :

Page 134 sur 191

 corrigé : l'énigme des trois maisons

Trois maisons doivent être chacune reliées à trois usines d’eau, de gaz et d’électricité. Peut-on disposer les cana
chevauchent pas ?

Ci-dessous figure l'illustration originale de l'auteur du problème :

Il est facile de voir que les maisons, usines et canalisations peuvent être modélisées par ce graphe :

La question peut alors se reformuler comme suit : le graphe précédent est -il planaire ?

Nous laissons le lecteur y réfléchir de façon intuitive, sans considérations mathématiques.

Page 135 sur 191

Exercices

Exercice 1 : Représentation et affichage d'un graphe avec une matrice

d'adjacence
Enoncé :
Ecrire un programme en C qui utilise une matrice d'adjacence pour stocker un graphe non
orienté et l'afficher.
Données :
 Le programme doit demander à l’utilisateur d’entrer le nombre de sommets n.
 Ensuite, l'utilisateur entre les arêtes sous forme (u, v), où u et v sont les sommets
connectés.
Exemple d'entrée :
Nombre de sommets : 4
Nombre d'arêtes : 3
Saisir les arêtes (format u v) :
01
12
23
Exemple de sortie :
Matrice d'adjacence :
0100
1010
0101
0010

#include <stdio.h>

#define MAX 100 // Nombre maximum de sommets

void afficherMatrice(int matrice[MAX][MAX], int n) {

printf("Matrice d'adjacence :\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", matrice[i][j]);
}
printf("\n");
}
}

int main() {
int n, m; // n = nombre de sommets, m = nombre d'arêtes
int matrice[MAX][MAX] = {0}; // Initialisation de la matrice à 0

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

printf("Saisir les arêtes (format u v) :\n");

for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
matrice[u][v] = 1;
matrice[v][u] = 1; // Graphe non orienté

Page 136 sur 191

 }

afficherMatrice(matrice, n);

return 0;
}

Exercice 2 : Représentation et affichage d'un graphe avec une liste

d'adjacence

Énoncé :
Écrire un programme en C qui utilise une liste d'adjacence pour stocker un graphe non
orienté et l'afficher.
Données :
 L’utilisateur entre le nombre de sommets et le nombre d'arêtes.
 Il entre ensuite les paires de sommets connectés (u, v).
 Le programme affiche la liste d'adjacence.
Exemple d'entrée :
rust
CopierModifier
Nombre de sommets : 4
Nombre d'arêtes : 3
Saisir les arêtes (format u v) :
01
12
23
Exemple de sortie :

Liste d'adjacence :
0→1
1→0→2
2→1→3
3→2

Correction en C :
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct Noeud {

int sommet;
struct Noeud* suivant;
} Noeud;

Noeud* listeAdj[MAX]; // Tableau de listes chaînées

void ajouterArete(int u, int v) {

Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->sommet = v;
nouveau->suivant = listeAdj[u];
listeAdj[u] = nouveau;
Page 137 sur 191
 // Graphe non orienté, donc on ajoute aussi dans l'autre sens
nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->sommet = u;
nouveau->suivant = listeAdj[v];
listeAdj[v] = nouveau;
}

void afficherListeAdj(int n) {
printf("Liste d'adjacence :\n");
for (int i = 0; i < n; i++) {
printf("%d →", i);
Noeud* temp = listeAdj[i];
while (temp) {
printf(" %d", temp->sommet);
temp = temp->suivant;
}
printf("\n");
}
}

int main() {
int n, m; // Nombre de sommets et d'arêtes

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

// Initialisation de la liste d'adjacence

for (int i = 0; i < n; i++) {
listeAdj[i] = NULL;
}

printf("Saisir les arêtes (format u v) :\n");

for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
ajouterArete(u, v);
}

afficherListeAdj(n);

return 0;
}

Exercice 3 : Vérification de l'existence d'une arête

Enoncé :

Page 138 sur 191

Modifier le programme précédent (matrice et liste) pour ajouter une fonction qui vérifie si
une arête existe entre deux sommets u et v.

Correction pour la matrice d'adjacence

Ajoutez cette fonction dans le programme de la matrice d'adjacence :

int existeAreteMatrice(int matrice[MAX][MAX], int u, int v) {

return matrice[u][v]; // Retourne 1 si l'arête existe, sinon 0
}
Puis ajoutez dans main() :

int u, v;
printf("Vérifier l'existence d'une arête (format u v) : ");
scanf("%d %d", &u, &v);

if (existeAreteMatrice(matrice, u, v))
printf("L'arête (%d, %d) existe.\n", u, v);
else
printf("L'arête (%d, %d) n'existe pas.\n", u, v);

Correction pour la liste d'adjacence

Ajoutez cette fonction dans le programme de la liste d'adjacence :

int existeAreteListe(Noeud* listeAdj[MAX], int u, int v) {

Noeud* temp = listeAdj[u];
while (temp) {
if (temp->sommet == v) return 1; // Arête trouvée
temp = temp->suivant;
}
return 0; // Arête non trouvée
}
Puis ajoutez dans main() :

int u, v;
printf("Vérifier l'existence d'une arête (format u v) : ");
scanf("%d %d", &u, &v);

if (existeAreteListe(listeAdj, u, v))
printf("L'arête (%d, %d) existe.\n", u, v);
else
printf("L'arête (%d, %d) n'existe pas.\n", u, v);

Exercice 4 : Parcours en largeur (BFS)

Enoncé :

Page 139 sur 191

Implémentez l'algorithme BFS (Breadth-First Search - Parcours en largeur) pour un
graphe représenté en liste d'adjacence.
Données :
 L’utilisateur entre le nombre de sommets et d’arêtes.
 Il entre les paires de sommets connectés (u, v).
 Il donne un sommet de départ pour le BFS.
Exemple d’entrée :
rust
CopierModifier
Nombre de sommets : 5
Nombre d'arêtes : 6
Saisir les arêtes :
01
02
13
14
24
34
Sommet de départ : 0
Exemple de sortie :
bash
CopierModifier
Parcours BFS à partir du sommet 0 : 0 1 2 3 4

Correction en C (BFS) :

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct Noeud {

int sommet;
struct Noeud* suivant;
} Noeud;

Noeud* listeAdj[MAX]; // Liste d'adjacence

int visite[MAX]; // Tableau pour suivre les sommets visités

void ajouterArete(int u, int v) {

Noeud* nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->sommet = v;
nouveau->suivant = listeAdj[u];
listeAdj[u] = nouveau;

// Graphe non orienté

nouveau = (Noeud*)malloc(sizeof(Noeud));
nouveau->sommet = u;
nouveau->suivant = listeAdj[v];
listeAdj[v] = nouveau;
}
Page 140 sur 191
void BFS(int debut) {
int file[MAX], debutFile = 0, finFile = 0;
file[finFile++] = debut;
visite[debut] = 1;

printf("Parcours BFS à partir du sommet %d : ", debut);

while (debutFile < finFile) {

int sommet = file[debutFile++];
printf("%d ", sommet);

Noeud* temp = listeAdj[sommet];

while (temp) {
if (!visite[temp->sommet]) {
file[finFile++] = temp->sommet;
visite[temp->sommet] = 1;
}
temp = temp->suivant;
}
}
printf("\n");
}

int main() {
int n, m, u, v, debut;

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

for (int i = 0; i < n; i++) {

listeAdj[i] = NULL;
visite[i] = 0;
}

printf("Saisir les arêtes :\n");

for (int i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
ajouterArete(u, v);
}

printf("Sommet de départ : ");

scanf("%d", &debut);
BFS(debut);

return 0;
}

Page 141 sur 191

Exercice 5 : Parcours en profondeur (DFS)

Correction en C (DFS) :

Ajoutez cette fonction DFS au programme précédent :

void DFS(int sommet) {

visite[sommet] = 1;
printf("%d ", sommet);

Noeud* temp = listeAdj[sommet];

while (temp) {
if (!visite[temp->sommet]) {
DFS(temp->sommet);
}
temp = temp->suivant;
}
}

int main() {
int debut;

// Après avoir créé le graphe comme dans BFS

printf("Sommet de départ : ");
scanf("%d", &debut);

for (int i = 0; i < MAX; i++) visite[i] = 0;

printf("Parcours DFS à partir du sommet %d : ", debut);

DFS(debut);
printf("\n");

return 0;
}

Exemple de sortie :

bash
CopierModifier
Parcours DFS à partir du sommet 0 : 0 1 3 4 2

Exercice 6 : Algorithme de Dijkstra (Plus Court Chemin)

Enoncé :
Implémentez l'algorithme de Dijkstra en utilisant une matrice d'adjacence.
Données :
 L’utilisateur entre n sommets et m arêtes pondérées (u, v, poids).
 Il donne un sommet source.
 Le programme affiche la distance minimale entre la source et tous les sommets.
Exemple d’entrée :
Page 142 sur 191
Nombre de sommets : 5
Nombre d'arêtes : 7
Saisir les arêtes (format u v poids) :
0 1 10
043
122
144
239
347
421
Sommet source : 0

Exemple de sortie :

Distances minimales depuis le sommet 0 :

0→0
1→7
2→4
3 → 13
4→3

Correction en C (Dijkstra) :
#include <stdio.h>
#include <limits.h>

#define MAX 100

#define INF INT_MAX

int matrice[MAX][MAX]; // Matrice d'adjacence

int distance[MAX]; // Distance minimale
int visite[MAX]; // Marquage des sommets visités
int n; // Nombre de sommets

int minDistance() {
int min = INF, index = -1;
for (int i = 0; i < n; i++) {
if (!visite[i] && distance[i] < min) {
min = distance[i];
index = i;
}
}
return index;
}

void dijkstra(int source) {

for (int i = 0; i < n; i++) {
distance[i] = INF;
visite[i] = 0;
}
distance[source] = 0;
Page 143 sur 191
 for (int i = 0; i < n - 1; i++) {
int u = minDistance();
visite[u] = 1;

for (int v = 0; v < n; v++) {

if (!visite[v] && matrice[u][v] && distance[u] != INF &&
distance[u] + matrice[u][v] < distance[v]) {
distance[v] = distance[u] + matrice[u][v];
}
}
}

printf("Distances minimales depuis le sommet %d :\n", source);

for (int i = 0; i < n; i++) {
printf("%d → %d\n", i, distance[i]);
}
}

int main() {
int m, u, v, poids, source;

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)
matrice[i][j] = 0;

printf("Saisir les arêtes (u v poids) :\n");

for (int i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &poids);
matrice[u][v] = poids;
}

printf("Sommet source : ");

scanf("%d", &source);

dijkstra(source);

return 0;
}

Exercice7 : Algorithme de Bellman-Ford (Plus Court Chemin avec Poids

Négatifs)

Enoncé :

Page 144 sur 191

Ecrire un programme en C qui implémente l’algorithme Bellman-Ford pour calculer le plus
court chemin à partir d’un sommet donné.

Données :

 L’utilisateur entre le nombre de sommets et le nombre d’arêtes.

 Chaque arête est définie par (u, v, poids), où u et v sont les sommets connectés.
 Le programme affiche la distance minimale depuis la source.

Correction en C :

#include <stdio.h>
#include <limits.h>

#define MAX 100

#define INF INT_MAX

typedef struct {
int u, v, poids;
} Arete;

Arete aretes[MAX];
int distance[MAX];

void bellmanFord(int n, int m, int source) {

for (int i = 0; i < n; i++) {
distance[i] = INF;
}
distance[source] = 0;

for (int i = 0; i < n - 1; i++) {

for (int j = 0; j < m; j++) {
int u = aretes[j].u;
int v = aretes[j].v;
int poids = aretes[j].poids;

if (distance[u] != INF && distance[u] + poids < distance[v]) {

distance[v] = distance[u] + poids;
}
}
}

printf("Distances minimales depuis le sommet %d :\n", source);

for (int i = 0; i < n; i++) {
printf("%d → %d\n", i, distance[i]);
}
}

Page 145 sur 191

int main() {
int n, m, source;

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

printf("Saisir les arêtes (u v poids) :\n");

for (int i = 0; i < m; i++) {
scanf("%d %d %d", &aretes[i].u, &aretes[i].v, &aretes[i].poids);
}

printf("Sommet source : ");

scanf("%d", &source);

bellmanFord(n, m, source);

return 0;
}

Exercice 8 : Algorithme de Floyd-Warshall (Plus Court Chemin entre Tous

les Sommets)
Enoncé :
Implémentez l’algorithme de Floyd-Warshall pour trouver les plus courts chemins entre tous
les sommets.

Correction en C :

#include <stdio.h>
#include <limits.h>

#define MAX 100

#define INF INT_MAX

int matrice[MAX][MAX];

void floydWarshall(int n) {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrice[i][k] != INF && matrice[k][j] != INF &&
matrice[i][k] + matrice[k][j] < matrice[i][j]) {
matrice[i][j] = matrice[i][k] + matrice[k][j];
}
}
}
}

Page 146 sur 191

 printf("Matrice des distances minimales :\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrice[i][j] == INF)
printf("INF ");
else
printf("%d ", matrice[i][j]);
}
printf("\n");
}
}

int main() {
int n, m, u, v, poids;

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)
matrice[i][j] = (i == j) ? 0 : INF;

printf("Saisir les arêtes (u v poids) :\n");

for (int i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &poids);
matrice[u][v] = poids;
}

floydWarshall(n);

return 0;
}

Exercice 9 : Algorithme de Prim (Arbre Couvrant Minimal)

Enoncé :

Implémentez Prim pour trouver l’arbre couvrant minimal.

Correction en C :

#include <stdio.h>
#include <limits.h>

#define MAX 100

#define INF INT_MAX

Page 147 sur 191

int matrice[MAX][MAX];
int parent[MAX], cle[MAX], visite[MAX];

int minCle(int n) {
int min = INF, index = -1;
for (int i = 0; i < n; i++)
if (!visite[i] && cle[i] < min)
min = cle[i], index = i;
return index;
}

void prim(int n) {
for (int i = 0; i < n; i++)
cle[i] = INF, visite[i] = 0;

cle[0] = 0;
parent[0] = -1;

for (int count = 0; count < n - 1; count++) {

int u = minCle(n);
visite[u] = 1;

for (int v = 0; v < n; v++) {

if (matrice[u][v] && !visite[v] && matrice[u][v] < cle[v]) {
parent[v] = u;
cle[v] = matrice[u][v];
}
}
}

printf("Arbre couvrant minimal :\n");

for (int i = 1; i < n; i++)
printf("%d - %d\n", parent[i], i);
}

int main() {
int n, m, u, v, poids;

printf("Nombre de sommets : ");

scanf("%d", &n);
printf("Nombre d'arêtes : ");
scanf("%d", &m);

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)
matrice[i][j] = 0;

printf("Saisir les arêtes (u v poids) :\n");

for (int i = 0; i < m; i++) {
scanf("%d %d %d", &u, &v, &poids);
matrice[u][v] = poids;
Page 148 sur 191
 matrice[v][u] = poids;
}

prim(n);

return 0;
}

Cas d’application : Structure Hémorroïde

Proposition d'une structure de données Hémorroïdes

Si l'on s'inspire du concept médical, une hémorroïde est une dilatation veineuse souvent
ramifiée. On pourrait donc imaginer une structure de données hiérarchique ou une
structure en graphe avec des connexions redondantes.

Remarque

Une dilatation veineuse désigne l'augmentation anormale du diamètre d'une veine en raison d'une
stagnation du sang ou d'une faiblesse des parois veineuses. Cela peut être causé par divers facteurs,
notamment une insuffisance veineuse, une augmentation de la pression sanguine dans la veine, ou une
altération des valves veineuses qui régulent le flux sanguin.
Causes possibles :
 Insuffisance veineuse chronique : Mauvais retour du sang vers le cœur, souvent lié à un
dysfonctionnement des valves veineuses.
 Varices : Veines superficielles dilatées et tortueuses, fréquentes sur les jambes.
 Thrombose veineuse : Formation d'un caillot sanguin qui bloque la circulation et entraîne une
dilatation en amont.
 Hypertension veineuse : Pression excessive dans les veines, par exemple en cas d'obésité, de
grossesse ou de station debout prolongée.
 Facteurs génétiques : Prédisposition familiale à la faiblesse des parois veineuses.
Symptômes possibles :
 Sensation de jambes lourdes
 Douleurs ou crampes
 Veines visibles sous la peau (bleutées ou gonflées)
 Œdèmes (gonflements) des jambes
 Risque de complications (ulcères, phlébites)
Traitements et Préventions :
 Compression veineuse (bas de contention)
 Activité physique régulière (marche, natation)
 Élévation des jambes pour favoriser le retour veineux
 Traitements médicaux (médicaments veinotoniques, sclérothérapie, chirurgie dans les cas
graves)
Fin Remarque

1. Modèle possible : Un graphe en arbre binaire ou un graphe cyclique

 Chaque nœud représente une veine avec un niveau de congestion (comme un poids
sur un graphe).
 Chaque nœud peut être connecté à d'autres veines pour former un système de flux.
 Un modèle de file d’attente pourrait être utilisé pour modéliser la pression et la
propagation d'un phénomène dans le système.
Page 149 sur 191
2. Implémentation en C d'une Structure "Hémorroïde"

Exemple d’une structure de graphe avec des poids (qui pourrait représenter des niveaux de
congestion dans un système inspiré des veines) :

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEINES 100 // Nombre maximal de veines

// Structure représentant une veine (nœud du graphe)

typedef struct Veine {
int id; // Identifiant de la veine
int niveau_congestion; // Niveau de congestion (poids du nœud)
struct Veine* suivante; // Pointeur vers la veine suivante (liste d'adjacence)
} Veine;

// Structure du graphe simulant le système veineux

typedef struct SystemeVeineux {
Veine* veines[MAX_VEINES]; // Liste d'adjacence pour chaque veine
int taille; // Nombre total de veines
} SystemeVeineux;

// Fonction pour créer une nouvelle veine

Veine* creerVeine(int id, int niveau_congestion) {
Veine* nouvelleVeine = (Veine*)malloc(sizeof(Veine));
nouvelleVeine->id = id;
nouvelleVeine->niveau_congestion = niveau_congestion;
nouvelleVeine->suivante = NULL;
return nouvelleVeine;
}

// Fonction pour ajouter une connexion entre deux veines

void ajouterConnexion(SystemeVeineux* systeme, int id1, int id2, int congestion) {
Veine* nouvelleVeine = creerVeine(id2, congestion);
nouvelleVeine->suivante = systeme->veines[id1];
systeme->veines[id1] = nouvelleVeine;
}

// Fonction pour afficher le système veineux

void afficherSystemeVeineux(SystemeVeineux* systeme) {
for (int i = 0; i < systeme->taille; i++) {
printf("Veine %d -> ", i);
Veine* courant = systeme->veines[i];
while (courant) {
printf("[%d (Congestion : %d)] -> ", courant->id, courant->niveau_congestion);
courant = courant->suivante;
}
printf("NULL\n");
}
}
Page 150 sur 191
// Programme principal
int main() {
SystemeVeineux systeme;
[Link] = 5;
for (int i = 0; i < [Link]; i++) {
[Link][i] = NULL;
}

// Ajout de connexions entre les veines (modélisant un système veineux)

ajouterConnexion(&systeme, 0, 1, 3);
ajouterConnexion(&systeme, 1, 2, 5);
ajouterConnexion(&systeme, 2, 3, 2);
ajouterConnexion(&systeme, 3, 4, 4);
ajouterConnexion(&systeme, 4, 0, 1); // Création d’un cycle

// Affichage du système
afficherSystemeVeineux(&systeme);

return 0;
}

Explication de la structure :

1. Les nœuds (Veine) : représentent des veines avec un niveau de congestion.

2. Les connexions (Graphe dirigé ou non dirigé) : permettent de modéliser le flux
sanguin et les problèmes de congestion.
3. Graphe cyclique possible : si certaines connexions se referment sur elles-mêmes.

Applications possibles :

 Problème
Modélisez un réseau de transport sous forme de graphe pondéré et implémenter un
algorithme de plus court chemin (Dijkstra) pour trouver le trajet optimal entre deux villes.

#include <stdio.h>
#include <limits.h>

#define V 5 // Nombre de villes (sommets)

// Fonction pour trouver le sommet avec la distance minimale

int distanceMinimale(int dist[], int ensembleSommets[]) {
int min = INT_MAX, indice_min;
for (int v = 0; v < V; v++) {
if (ensembleSommets[v] == 0 && dist[v] <= min) {
min = dist[v];
indice_min = v;
}
}
Page 151 sur 191
 return indice_min;
}

// Fonction pour afficher le plus court chemin

void afficherSolution(int dist[]) {
printf("Ville \t Distance depuis la source\n");
for (int i = 0; i < V; i++)
printf("%d \t %d\n", i, dist[i]);
}

// Implémentation de l'algorithme de Dijkstra

void dijkstra(int graphe[V][V], int source) {
int dist[V]; // Tableau des distances minimales
int ensembleSommets[V]; // Ensemble des sommets traités

// Initialisation des distances et du tableau ensembleSommets

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
ensembleSommets[i] = 0;
}

// La distance de la source à elle-même est toujours 0

dist[source] = 0;

// Trouver le plus court chemin pour tous les sommets

for (int compteur = 0; compteur < V - 1; compteur++) {
int u = distanceMinimale(dist, ensembleSommets);
// Sommet avec la plus petite distance
ensembleSommets[u] = 1; // Marquer le sommet comme traité

// Mise à jour des distances des sommets voisins

for (int v = 0; v < V; v++) {
if (!ensembleSommets[v] && graphe[u][v] && dist[u] != INT_MAX
&& dist[u] + graphe[u][v] < dist[v]) {
dist[v] = dist[u] + graphe[u][v];
}
}
}
// Affichage du résultat
afficherSolution(dist);
}

// Programme principal
int main() {
int graphe[V][V] = {
{0, 10, 0, 30, 100},
{10, 0, 50, 0, 0},
{0, 50, 0, 20, 10},
{30, 0, 20, 0, 60},
{100, 0, 10, 60, 0}
};
Page 152 sur 191
 int source = 0; // Ville de départ
printf("Calcul du plus court chemin depuis la ville %d :\n", source);
dijkstra(graphe, source);

return 0;
}
 Explication :
1. Graph modélisé :
o 5 villes (sommets du graphe).
o Routes entre les villes avec des distances pondérées.
o Stockage sous forme de matrice d’adjacence.
2. Algorithme de Dijkstra :
o Recherche du plus court chemin entre une ville source et les autres.
o Utilisation d’un tableau de distances et d’un ensemble des sommets visités.
3. Affichage des résultats :
o Affiche la distance minimale depuis la ville source vers chaque autre ville.

 Exécution :
Si on choisit la ville 0 comme point de départ, on obtient :

Calcul du plus court chemin depuis la ville 0 :

Ville Distance depuis la source
0 0
1 10
2 50
3 30
4 60

Ce concept humoristique peut être utilisé en informatique pour représenter des systèmes
où la congestion et la circulation sont des facteurs clés.

Exercices corrigés sur les structures de données inspirées du système veineux

Exercice 1 : Création et affichage d'un système veineux

Enoncé :
Écrire un programme en C qui :
1. Crée une structure de données pour représenter un système veineux sous forme de
graphe.
2. Ajoute des connexions entre plusieurs veines.
3. Affiche la liste des connexions entre les veines.
Correction :
#include <stdio.h>
#include <stdlib.h>

#define MAX_VEINES 10

// Structure représentant une veine

typedef struct Veine {

Page 153 sur 191

 int id;
int congestion;
struct Veine* suivante;
} Veine;

// Structure du système veineux

typedef struct SystemeVeineux {
Veine* veines[MAX_VEINES];
int taille;
} SystemeVeineux;

// Fonction pour créer une nouvelle veine

Veine* creerVeine(int id, int congestion) {
Veine* nouvelleVeine = (Veine*)malloc(sizeof(Veine));
nouvelleVeine->id = id;
nouvelleVeine->congestion = congestion;
nouvelleVeine->suivante = NULL;
return nouvelleVeine;
}

// Fonction pour ajouter une connexion

void ajouterConnexion(SystemeVeineux* systeme, int id1, int id2, int congestion) {
Veine* nouvelleVeine = creerVeine(id2, congestion);
nouvelleVeine->suivante = systeme->veines[id1];
systeme->veines[id1] = nouvelleVeine;
}

// Fonction pour afficher le système veineux

void afficherSystemeVeineux(SystemeVeineux* systeme) {
for (int i = 0; i < systeme->taille; i++) {
printf("Veine %d -> ", i);
Veine* courant = systeme->veines[i];
while (courant) {
printf("[%d (Congestion: %d)] -> ", courant->id, courant->congestion);
courant = courant->suivante;
}
printf("NULL\n");
}
}

// Programme principal
int main() {
SystemeVeineux systeme;
[Link] = 5;

for (int i = 0; i < [Link]; i++) {

[Link][i] = NULL;
}

// Création des connexions

ajouterConnexion(&systeme, 0, 1, 2);
Page 154 sur 191
 ajouterConnexion(&systeme, 1, 2, 5);
ajouterConnexion(&systeme, 2, 3, 3);
ajouterConnexion(&systeme, 3, 4, 4);
ajouterConnexion(&systeme, 4, 0, 1);

// Affichage du système veineux

afficherSystemeVeineux(&systeme);

return 0;
}
Exercice 2 : Détection d’une boucle dans le système veineux
Enoncé :
Modifiez le programme précédent pour vérifier s'il existe une boucle dans le système veineux
(c'est-à-dire si l'on peut revenir à une veine déjà visitée en suivant les connexions).
Correction :
#include <stdio.h>
#include <stdlib.h>

#define MAX_VEINES 10

// Structure de la veine
typedef struct Veine {
int id;
int congestion;
struct Veine* suivante;
} Veine;

// Structure du système veineux

typedef struct SystemeVeineux {
Veine* veines[MAX_VEINES];
int taille;
} SystemeVeineux;

// Création d'une veine

Veine* creerVeine(int id, int congestion) {
Veine* nouvelleVeine = (Veine*)malloc(sizeof(Veine));
nouvelleVeine->id = id;
nouvelleVeine->congestion = congestion;
nouvelleVeine->suivante = NULL;
return nouvelleVeine;
}

// Ajout d'une connexion

void ajouterConnexion(SystemeVeineux* systeme, int id1, int id2, int congestion) {
Veine* nouvelleVeine = creerVeine(id2, congestion);
nouvelleVeine->suivante = systeme->veines[id1];
systeme->veines[id1] = nouvelleVeine;
}

// Vérification de la présence d'une boucle (cycle)

int detecterBoucle(SystemeVeineux* systeme) {
Page 155 sur 191
 int visite[MAX_VEINES] = {0}; // Tableau pour suivre les veines visitées

for (int i = 0; i < systeme->taille; i++) {

Veine* courant = systeme->veines[i];
while (courant) {
if (visite[courant->id]) {
return 1; // Boucle détectée
}
visite[courant->id] = 1;
courant = courant->suivante;
}
}
return 0; // Aucune boucle détectée
}

// Programme principal
int main() {
SystemeVeineux systeme;
[Link] = 5;

for (int i = 0; i < [Link]; i++) {

[Link][i] = NULL;
}

// Création des connexions

ajouterConnexion(&systeme, 0, 1, 2);
ajouterConnexion(&systeme, 1, 2, 5);
ajouterConnexion(&systeme, 2, 3, 3);
ajouterConnexion(&systeme, 3, 4, 4);
ajouterConnexion(&systeme, 4, 0, 1); // Boucle créée ici

// Vérification de la boucle
if (detecterBoucle(&systeme)) {
printf("Une boucle a été détectée dans le système veineux.\n");
} else {
printf("Aucune boucle détectée.\n");
}

return 0;
}

Exercice 3 : Trouver la veine la plus congestionnée

Enoncé :
Ajoutez une fonction qui trouve et affiche la veine ayant le plus haut niveau de congestion.
Correction :
#include <stdio.h>
#include <stdlib.h>

#define MAX_VEINES 10

Page 156 sur 191

// Structure d'une veine
typedef struct Veine {
int id;
int congestion;
struct Veine* suivante;
} Veine;

// Structure du système veineux

typedef struct SystemeVeineux {
Veine* veines[MAX_VEINES];
int taille;
} SystemeVeineux;

// Fonction pour trouver la veine la plus congestionnée

void veineMaxCongestion(SystemeVeineux* systeme) {
int maxCongestion = -1;
int veineMax = -1;

for (int i = 0; i < systeme->taille; i++) {

Veine* courant = systeme->veines[i];
while (courant) {
if (courant->congestion > maxCongestion) {
maxCongestion = courant->congestion;
veineMax = courant->id;
}
courant = courant->suivante;
}
}

if (veineMax != -1) {
printf("La veine la plus congestionnée est la veine %d avec un niveau de congestion de
%d.\n", veineMax, maxCongestion);
} else {
printf("Aucune congestion détectée.\n");
}
}

// Programme principal
int main() {
SystemeVeineux systeme;
[Link] = 5;

for (int i = 0; i < [Link]; i++) {

[Link][i] = NULL;
}

ajouterConnexion(&systeme, 0, 1, 2);
ajouterConnexion(&systeme, 1, 2, 7);
ajouterConnexion(&systeme, 2, 3, 3);
ajouterConnexion(&systeme, 3, 4, 9);

Page 157 sur 191

 veineMaxCongestion(&systeme);

return 0;
}

Exercice4 : Implémentation de l'algorithme de Bellman-Ford appliqué au système

veineux

Enoncé :

Un système veineux est modélisé sous forme de graphe où :

 Chaque veine est un nœud.

 Chaque connexion entre deux veines est une arête avec un poids représentant le
niveau de congestion.

Votre tâche est d'implémenter l'algorithme de Bellman-Ford pour trouver le chemin le plus
court (c'est-à-dire la veine la moins congestionnée) depuis une veine source jusqu'à toutes les
autres veines.

Correction : Implémentation de l'algorithme de Bellman-Ford en C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VEINES 10
#define INF INT_MAX

// Structure représentant une arête (connexion entre deux veines)

typedef struct Arete {
int source, destination, poids;
} Arete;

// Structure du système veineux (graphe orienté)

typedef struct SystemeVeineux {
int nbVeines, nbAretes;
Arete* aretes;
} SystemeVeineux;

// Fonction pour créer un système veineux avec un nombre donné de veines et de connexions
SystemeVeineux* creerSystemeVeineux(int nbVeines, int nbAretes) {
SystemeVeineux* systeme = (SystemeVeineux*)malloc(sizeof(SystemeVeineux));
systeme->nbVeines = nbVeines;
systeme->nbAretes = nbAretes;
systeme->aretes = (Arete*)malloc(nbAretes * sizeof(Arete));
return systeme;
}

Page 158 sur 191

// Algorithme de Bellman-Ford pour trouver les chemins les plus courts depuis une veine
source
void bellmanFord(SystemeVeineux* systeme, int source) {
int nbVeines = systeme->nbVeines;
int nbAretes = systeme->nbAretes;
int distances[MAX_VEINES];

// Initialisation des distances à l'infini sauf pour la veine source

for (int i = 0; i < nbVeines; i++) {
distances[i] = INF;
}
distances[source] = 0;

// Détendre chaque arête (nbVeines - 1) fois

for (int i = 0; i < nbVeines - 1; i++) {
for (int j = 0; j < nbAretes; j++) {
int u = systeme->aretes[j].source;
int v = systeme->aretes[j].destination;
int poids = systeme->aretes[j].poids;

if (distances[u] != INF && distances[u] + poids < distances[v]) {

distances[v] = distances[u] + poids;
}
}
}

// Vérification des cycles négatifs

for (int j = 0; j < nbAretes; j++) {
int u = systeme->aretes[j].source;
int v = systeme->aretes[j].destination;
int poids = systeme->aretes[j].poids;

if (distances[u] != INF && distances[u] + poids < distances[v]) {

printf("Attention : Le système veineux contient un cycle de congestion négatif !\n");
return;
}
}

// Affichage des résultats

printf("Distances minimales depuis la veine %d :\n", source);
for (int i = 0; i < nbVeines; i++) {
if (distances[i] == INF) {
printf("Veine %d : INACCESSIBLE\n", i);
} else {
printf("Veine %d : %d\n", i, distances[i]);
}
}
}

// Programme principal
int main() {
Page 159 sur 191
 int nbVeines = 5;
int nbAretes = 7;

SystemeVeineux* systeme = creerSystemeVeineux(nbVeines, nbAretes);

// Définition des connexions (source, destination, niveau de congestion)

systeme->aretes[0] = (Arete){0, 1, 2};
systeme->aretes[1] = (Arete){0, 2, 4};
systeme->aretes[2] = (Arete){1, 2, 1};
systeme->aretes[3] = (Arete){1, 3, 7};
systeme->aretes[4] = (Arete){2, 4, 3};
systeme->aretes[5] = (Arete){3, 4, 2};
systeme->aretes[6] = (Arete){4, 1, -6}; // Ajout d'une congestion négative

int source = 0; // Veine de départ

// Exécution de Bellman-Ford
bellmanFord(systeme, source);

// Libération de la mémoire
free(systeme->aretes);
free(systeme);

return 0;
}

Explication du programme :

1. Modélisation du système veineux :

o Chaque veine est un nœud.
o Chaque connexion entre deux veines est une arête avec un niveau de
congestion (poids).
2. Application de l'algorithme de Bellman-Ford :
o Initialisation des distances (∞ sauf la veine source qui est à 0).
o On effectue (nombre de veines - 1) itérations pour mettre à jour les distances
minimales.
o On vérifie s'il existe un cycle négatif (ce qui indiquerait une boucle infinie de
congestion).
o On affiche la distance minimale de la veine source à toutes les autres veines.

Exemple d'exécution :
Entrée :
Veines : 0, 1, 2, 3, 4
Connexions :
- Veine 0 → Veine 1 (Congestion 2)
- Veine 0 → Veine 2 (Congestion 4)
- Veine 1 → Veine 2 (Congestion 1)
- Veine 1 → Veine 3 (Congestion 7)
- Veine 2 → Veine 4 (Congestion 3)
- Veine 3 → Veine 4 (Congestion 2)
- Veine 4 → Veine 1 (Congestion -6)
Page 160 sur 191
Sortie attendue :
Distances minimales depuis la veine 0 :
Veine 0 : 0
Veine 1 : 2
Veine 2 : 3
Veine 3 : 9
Veine 4 : 6
Si on remplace la congestion négative (-6) par un cycle de congestion négatif, le programme
afficherait un avertissement.

Pourquoi Bellman-Ford ?

 Cet algorithme est adapté aux graphes avec des poids négatifs (ce qui peut modéliser
des effets de décompression dans un système veineux).
 Il fonctionne même avec un grand nombre de veines.
 Il permet de détecter les congestions infinies (équivalent des cycles négatifs).

Exercice5 : Implémentation de l'algorithme de Dijkstra appliqué au système

veineux
Enoncé :
On modélise un système veineux sous forme de graphe pondéré :
 Chaque veine est un nœud.
 Chaque connexion entre deux veines est une arête pondérée représentant le niveau
de congestion.
L'objectif est d'utiliser l'algorithme de Dijkstra pour déterminer le chemin le moins
congestionné entre une veine source et toutes les autres veines.
Correction : Implémentation en C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VEINES 10
#define INF INT_MAX

// Structure du graphe (système veineux)

typedef struct SystemeVeineux {
int nbVeines;
int matrice[MAX_VEINES][MAX_VEINES]; // Matrice d'adjacence
} SystemeVeineux;

// Fonction pour créer un système veineux vide

void initialiserSysteme(SystemeVeineux* systeme, int nbVeines) {
systeme->nbVeines = nbVeines;
for (int i = 0; i < nbVeines; i++) {
for (int j = 0; j < nbVeines; j++) {
systeme->matrice[i][j] = (i == j) ? 0 : INF; // Distance de soi-même à soi-même = 0
}
}
Page 161 sur 191
}

// Fonction pour ajouter une connexion entre deux veines

void ajouterConnexion(SystemeVeineux* systeme, int u, int v, int congestion) {
systeme->matrice[u][v] = congestion;
systeme->matrice[v][u] = congestion; // Graphe non orienté
}

// Fonction pour trouver la veine avec la plus petite congestion non visitée
int trouverMinDistance(int distances[], int visite[], int nbVeines) {
int min = INF, minIndex = -1;
for (int i = 0; i < nbVeines; i++) {
if (!visite[i] && distances[i] < min) {
min = distances[i];
minIndex = i;
}
}
return minIndex;
}

// Algorithme de Dijkstra pour trouver les chemins les moins congestionnés

void dijkstra(SystemeVeineux* systeme, int source) {
int distances[MAX_VEINES], visite[MAX_VEINES], precedent[MAX_VEINES];

// Initialisation des distances et des veines visitées

for (int i = 0; i < systeme->nbVeines; i++) {
distances[i] = INF;
visite[i] = 0;
precedent[i] = -1;
}
distances[source] = 0;

// Boucle principale de l'algorithme

for (int count = 0; count < systeme->nbVeines - 1; count++) {
int u = trouverMinDistance(distances, visite, systeme->nbVeines);
if (u == -1) break;
visite[u] = 1;

// Mise à jour des distances des voisins de u

for (int v = 0; v < systeme->nbVeines; v++) {
if (!visite[v] && systeme->matrice[u][v] != INF &&
distances[u] + systeme->matrice[u][v] < distances[v]) {
distances[v] = distances[u] + systeme->matrice[u][v];
precedent[v] = u;
}
}
}

// Affichage des résultats

printf("Distances minimales depuis la veine %d :\n", source);
for (int i = 0; i < systeme->nbVeines; i++) {
Page 162 sur 191
 if (distances[i] == INF) {
printf("Veine %d : INACCESSIBLE\n", i);
} else {
printf("Veine %d : %d (chemin : ", i, distances[i]);
int chemin[MAX_VEINES], index = 0, temp = i;
while (temp != -1) {
chemin[index++] = temp;
temp = precedent[temp];
}
for (int j = index - 1; j >= 0; j--) {
printf("%d ", chemin[j]);
}
printf(")\n");
}
}
}

// Programme principal
int main() {
int nbVeines = 5;
SystemeVeineux systeme;
initialiserSysteme(&systeme, nbVeines);

// Ajout des connexions (veine1, veine2, congestion)

ajouterConnexion(&systeme, 0, 1, 2);
ajouterConnexion(&systeme, 0, 2, 4);
ajouterConnexion(&systeme, 1, 2, 1);
ajouterConnexion(&systeme, 1, 3, 7);
ajouterConnexion(&systeme, 2, 4, 3);
ajouterConnexion(&systeme, 3, 4, 2);

int source = 0; // Veine de départ

dijkstra(&systeme, source);

return 0;
}

Explication du programme :

1. Représentation du système veineux sous forme d'une matrice d'adjacence :

o matrice[u][v] représente le niveau de congestion entre les veines u et v.
o INF signifie qu'il n'existe pas de connexion directe.
2. Fonction dijkstra() :
o Initialise un tableau des distances à INF, sauf la source.
o Trouve à chaque itération la veine la moins congestionnée encore inexplorée.
o Met à jour les distances minimales aux veines adjacentes.
o Enregistre le chemin optimal dans un tableau precedent[].
3. Affichage du chemin optimal et de la distance minimale depuis la source.

Page 163 sur 191

Exemple d'exécution :

Veines : 0, 1, 2, 3, 4
Connexions :
- Veine 0 → Veine 1 (Congestion 2)
- Veine 0 → Veine 2 (Congestion 4)
- Veine 1 → Veine 2 (Congestion 1)
- Veine 1 → Veine 3 (Congestion 7)
- Veine 2 → Veine 4 (Congestion 3)
- Veine 3 → Veine 4 (Congestion 2)

Sortie attendue :

plaintext
CopierModifier
Distances minimales depuis la veine 0 :
Veine 0 : 0 (chemin : 0)
Veine 1 : 2 (chemin : 0 1)
Veine 2 : 3 (chemin : 0 1 2)
Veine 3 : 9 (chemin : 0 1 3)
Veine 4 : 6 (chemin : 0 1 2 4)

Pourquoi Dijkstra ?

 Permet de trouver le chemin le moins congestionné.

 Fonctionne efficacement pour les graphes sans poids négatif.
 Utilisé dans les réseaux de transport et de communication.

Exercice6 : Implémentation de l'algorithme de Floyd-Warshall appliqué au

système veineux

Enoncé :
On modélise un système veineux sous forme de graphe pondéré où :
 Chaque veine est un nœud.
 Chaque connexion entre deux veines est une arête pondérée représentant le niveau
de congestion.
L'objectif est d'utiliser l'algorithme de Floyd-Warshall pour déterminer les chemins les
moins congestionnés entre toutes les paires de veines.
Correction : Implémentation en C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VEINES 10
#define INF INT_MAX

// Structure du graphe (système veineux)

typedef struct SystemeVeineux {
int nbVeines;
int matrice[MAX_VEINES][MAX_VEINES]; // Matrice d'adjacence
Page 164 sur 191
} SystemeVeineux;

// Fonction pour initialiser le système veineux

void initialiserSysteme(SystemeVeineux* systeme, int nbVeines) {
systeme->nbVeines = nbVeines;
for (int i = 0; i < nbVeines; i++) {
for (int j = 0; j < nbVeines; j++) {
if (i == j)
systeme->matrice[i][j] = 0; // Distance d'une veine à elle-même = 0
else
systeme->matrice[i][j] = INF; // Absence de connexion
}
}
}

// Fonction pour ajouter une connexion entre deux veines

void ajouterConnexion(SystemeVeineux* systeme, int u, int v, int congestion) {
systeme->matrice[u][v] = congestion;
systeme->matrice[v][u] = congestion; // Graphe non orienté
}

// Algorithme de Floyd-Warshall pour trouver les chemins les moins congestionnés entre
toutes les veines
void floydWarshall(SystemeVeineux* systeme) {
int distances[MAX_VEINES][MAX_VEINES];
int nbVeines = systeme->nbVeines;

// Initialisation de la matrice des distances avec les valeurs initiales

for (int i = 0; i < nbVeines; i++) {
for (int j = 0; j < nbVeines; j++) {
distances[i][j] = systeme->matrice[i][j];
}
}

// Algorithme de Floyd-Warshall
for (int k = 0; k < nbVeines; k++) {
for (int i = 0; i < nbVeines; i++) {
for (int j = 0; j < nbVeines; j++) {
if (distances[i][k] != INF && distances[k][j] != INF &&
distances[i][k] + distances[k][j] < distances[i][j]) {
distances[i][j] = distances[i][k] + distances[k][j];
}
}
}
}

// Affichage des distances minimales entre toutes les veines

printf("Matrice des chemins les moins congestionnés :\n");
for (int i = 0; i < nbVeines; i++) {
for (int j = 0; j < nbVeines; j++) {
if (distances[i][j] == INF)
Page 165 sur 191
 printf("INF\t");
else
printf("%d\t", distances[i][j]);
}
printf("\n");
}
}

// Programme principal
int main() {
int nbVeines = 5;
SystemeVeineux systeme;
initialiserSysteme(&systeme, nbVeines);

// Ajout des connexions (veine1, veine2, congestion)

ajouterConnexion(&systeme, 0, 1, 2);
ajouterConnexion(&systeme, 0, 2, 4);
ajouterConnexion(&systeme, 1, 2, 1);
ajouterConnexion(&systeme, 1, 3, 7);
ajouterConnexion(&systeme, 2, 4, 3);
ajouterConnexion(&systeme, 3, 4, 2);

// Exécution de Floyd-Warshall
floydWarshall(&systeme);

return 0;
}

Explication du programme :

1. Représentation du système veineux sous forme d'une matrice d'adjacence :

o matrice[u][v] représente le niveau de congestion entre les veines u et v.
o INF signifie qu'il n'existe pas de connexion directe.
2. Fonction floydWarshall() :
o Initialise une matrice des distances avec les valeurs de congestion initiales.
o Applique l'algorithme de Floyd-Warshall, qui vérifie si un chemin
intermédiaire k améliore la distance entre i et j.
o Affiche la matrice des chemins les moins congestionnés entre toutes les
veines.

Exemple d'exécution :
Entrée :
plaintext
CopierModifier
Veines : 0, 1, 2, 3, 4
Connexions :
- Veine 0 → Veine 1 (Congestion 2)
- Veine 0 → Veine 2 (Congestion 4)

Page 166 sur 191

 - Veine 1 → Veine 2 (Congestion 1)
- Veine 1 → Veine 3 (Congestion 7)
- Veine 2 → Veine 4 (Congestion 3)
- Veine 3 → Veine 4 (Congestion 2)

Sortie attendue :
Matrice des chemins les moins congestionnés :
0 2 3 9 6
2 0 1 7 4
3 1 0 8 3
9 7 8 0 2
6 4 3 2 0
Chaque valeur représente le chemin le moins congestionné entre deux veines.

Pourquoi Floyd-Warshall ?

- Permet de calculer toutes les distances entre toutes les veines en un seul passage.
- Fonctionne pour les graphes denses (où chaque veine est connectée à plusieurs autres).
- Plus adapté que Dijkstra pour traiter toutes les paires de veines en même temps.

Exercice7 : Implémentation de l'algorithme de Kruskal appliqué au système veineux

Enoncé :
On modélise un système veineux sous forme de graphe pondéré où :
 Chaque veine est un nœud.
 Chaque connexion entre deux veines est une arête pondérée représentant le niveau
de congestion.
L'objectif est d'utiliser l'algorithme de Kruskal pour trouver l'arbre couvrant minimal
(ACM), c'est-à-dire le réseau veineux ayant le moins de congestion possible tout en
restant connecté.

Correction : Implémentation en C

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEINES 10

// Structure représentant une arête (connexion entre deux veines)

typedef struct Arete {
int source, destination, poids;
} Arete;

// Structure du graphe (système veineux)

typedef struct SystemeVeineux {
int nbVeines, nbAretes;
Arete* aretes;

Page 167 sur 191

} SystemeVeineux;

// Fonction pour créer un système veineux

SystemeVeineux* creerSystemeVeineux(int nbVeines, int nbAretes) {
SystemeVeineux* systeme = (SystemeVeineux*)malloc(sizeof(SystemeVeineux));
systeme->nbVeines = nbVeines;
systeme->nbAretes = nbAretes;
systeme->aretes = (Arete*)malloc(nbAretes * sizeof(Arete));
return systeme;
}

// Fonction de comparaison pour trier les arêtes par poids croissant

int comparerAretes(const void* a, const void* b) {
return ((Arete*)a)->poids - ((Arete*)b)->poids;
}

// Structure pour l'Union-Find (Détection de cycles)

typedef struct SousEnsemble {
int parent;
int rang;
} SousEnsemble;

// Fonction pour trouver l'ensemble (racine) d'un élément

int trouver(SousEnsemble sousEnsembles[], int i) {
if (sousEnsembles[i].parent != i)
sousEnsembles[i].parent = trouver(sousEnsembles, sousEnsembles[i].parent);
return sousEnsembles[i].parent;
}

// Fonction pour unir deux sous-ensembles (Union-Find)

void unionSousEnsemble(SousEnsemble sousEnsembles[], int x, int y) {
int racineX = trouver(sousEnsembles, x);
int racineY = trouver(sousEnsembles, y);

if (sousEnsembles[racineX].rang < sousEnsembles[racineY].rang)

sousEnsembles[racineX].parent = racineY;
else if (sousEnsembles[racineX].rang > sousEnsembles[racineY].rang)
sousEnsembles[racineY].parent = racineX;
else {
sousEnsembles[racineY].parent = racineX;
sousEnsembles[racineX].rang++;
}
}

// Algorithme de Kruskal pour trouver l'Arbre Couvant Minimal (ACM)

void kruskal(SystemeVeineux* systeme) {
Arete resultat[MAX_VEINES]; // Stocke les arêtes de l'ACM
int e = 0; // Nombre d'arêtes ajoutées à l'ACM
int i = 0; // Index de l'arête triée

// Trier les arêtes par ordre croissant de congestion

Page 168 sur 191
 qsort(systeme->aretes, systeme->nbAretes, sizeof(Arete), comparerAretes);

// Initialisation des sous-ensembles pour l'Union-Find

SousEnsemble sousEnsembles[MAX_VEINES];
for (int v = 0; v < systeme->nbVeines; v++) {
sousEnsembles[v].parent = v;
sousEnsembles[v].rang = 0;
}

// Construction de l'ACM
while (e < systeme->nbVeines - 1 && i < systeme->nbAretes) {
Arete prochaineArete = systeme->aretes[i++];
int x = trouver(sousEnsembles, [Link]);
int y = trouver(sousEnsembles, [Link]);

// Vérifier s'il n'y a pas de cycle

if (x != y) {
resultat[e++] = prochaineArete;
unionSousEnsemble(sousEnsembles, x, y);
}
}

// Affichage des résultats

printf("Arbre Couvant Minimal (ACM) - Connexions minimales :\n");
for (i = 0; i < e; i++) {
printf("Veine %d - Veine %d : Congestion %d\n",
resultat[i].source, resultat[i].destination, resultat[i].poids);
}
}

// Programme principal
int main() {
int nbVeines = 5;
int nbAretes = 7;

SystemeVeineux* systeme = creerSystemeVeineux(nbVeines, nbAretes);

// Définition des connexions (source, destination, congestion)

systeme->aretes[0] = (Arete){0, 1, 2};
systeme->aretes[1] = (Arete){0, 2, 4};
systeme->aretes[2] = (Arete){1, 2, 1};
systeme->aretes[3] = (Arete){1, 3, 7};
systeme->aretes[4] = (Arete){2, 4, 3};
systeme->aretes[5] = (Arete){3, 4, 2};
systeme->aretes[6] = (Arete){4, 1, 6};

// Exécution de Kruskal
kruskal(systeme);

// Libération de la mémoire
free(systeme->aretes);
Page 169 sur 191
 free(systeme);

return 0;
}

Explication du programme :

1. Représentation du système veineux sous forme d'un graphe pondéré :

o Chaque veine est un nœud.
o Chaque connexion entre deux veines est une arête pondérée.
2. Application de l'algorithme de Kruskal :
o Trie les arêtes par ordre croissant de congestion.
o Utilise Union-Find pour ajouter les arêtes une par une tout en évitant les
cycles.
o Génère l'Arbre Couvant Minimal (ACM), un réseau optimisé avec moins de
congestion.

Exemple d'exécution :

Entrée :

Veines : 0, 1, 2, 3, 4
Connexions :
- Veine 0 → Veine 1 (Congestion 2)
- Veine 0 → Veine 2 (Congestion 4)
- Veine 1 → Veine 2 (Congestion 1)
- Veine 1 → Veine 3 (Congestion 7)
- Veine 2 → Veine 4 (Congestion 3)
- Veine 3 → Veine 4 (Congestion 2)
- Veine 4 → Veine 1 (Congestion 6)
Sortie attendue :
plaintext
CopierModifier
Arbre Couvant Minimal (ACM) - Connexions minimales :
Veine 1 - Veine 2 : Congestion 1
Veine 0 - Veine 1 : Congestion 2
Veine 3 - Veine 4 : Congestion 2
Veine 2 - Veine 4 : Congestion 3

L'algorithme de Kruskal est utilisé pour trouver l'arbre couvrant minimal (MST - Minimum
Spanning Tree) d'un graphe pondéré, ce qui est utile pour la conception optimale des réseaux
d’électricité. Il permet de minimiser le coût des câbles tout en assurant la connectivité du
réseau.

Page 170 sur 191

Application de l’algorithme de Kruskal aux réseaux électriques

Dans un réseau d’électricité, chaque nœud représente une station électrique ou un

transformateur, et chaque arête représente une ligne de transmission avec un coût associé
(distance, pertes énergétiques, coût d’installation).
L’algorithme de Kruskal sélectionne les lignes de transmission (arêtes) de coût minimum
tout en évitant les cycles, assurant ainsi une couverture efficace et économique du réseau.
Implémentation en langage C

Implémentation de l’algorithme de Kruskal en C appliqué aux réseaux électriques :

#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Nombre maximum de sommets

#define MAX_ARETES 500 // Nombre maximum d'arêtes

// Structure pour représenter une arête

typedef struct {
int source, destination, poids;
} Arete;

// Structure pour représenter un graphe

typedef struct {
int nombreSommets, nombreAretes;
Arete aretes[MAX_ARETES];
} Graphe;

// Structure pour un sous-ensemble utilisé dans l'union-find

typedef struct {
int parent;
int rang;
} SousEnsemble;

// Fonction de comparaison pour trier les arêtes par poids

int comparerAretes(const void* a, const void* b) {
return ((Arete*)a)->poids - ((Arete*)b)->poids;
}

// Trouver le représentant d'un ensemble (avec compression de chemin)

int trouver(SousEnsemble sousEnsembles[], int i) {
if (sousEnsembles[i].parent != i)
sousEnsembles[i].parent = trouver(sousEnsembles, sousEnsembles[i].parent);
return sousEnsembles[i].parent;
}

// Union des ensembles (Union par rang)

void unir(SousEnsemble sousEnsembles[], int x, int y) {
int racineX = trouver(sousEnsembles, x);
int racineY = trouver(sousEnsembles, y);

Page 171 sur 191

 if (sousEnsembles[racineX].rang < sousEnsembles[racineY].rang)
sousEnsembles[racineX].parent = racineY;
else if (sousEnsembles[racineX].rang > sousEnsembles[racineY].rang)
sousEnsembles[racineY].parent = racineX;
else {
sousEnsembles[racineY].parent = racineX;
sousEnsembles[racineX].rang++;
}
}

// Algorithme de Kruskal pour trouver l’arbre couvrant de coût minimal

void kruskalMST(Graphe* graphe) {
Arete resultat[MAX]; // Stocke l'arbre couvrant minimal (MST)
int e = 0, i = 0; // e = nombre d'arêtes dans MST, i = index trié

// Trier les arêtes par poids

qsort(graphe->aretes, graphe->nombreAretes, sizeof(Arete), comparerAretes);

// Initialisation des sous-ensembles

SousEnsemble* sousEnsembles = (SousEnsemble*)malloc(graphe->nombreSommets *
sizeof(SousEnsemble));
for (int v = 0; v < graphe->nombreSommets; ++v) {
sousEnsembles[v].parent = v;
sousEnsembles[v].rang = 0;
}

while (e < graphe->nombreSommets - 1 && i < graphe->nombreAretes) {

Arete prochaineArete = graphe->aretes[i++];
int x = trouver(sousEnsembles, [Link]);
int y = trouver(sousEnsembles, [Link]);

if (x != y) { // Éviter les cycles

resultat[e++] = prochaineArete;
unir(sousEnsembles, x, y);
}
}

// Affichage du réseau électrique optimisé

printf("Lignes de transmission sélectionnées pour minimiser le coût :\n");
printf("Source - Destination : Coût\n");
for (i = 0; i < e; ++i)
printf(" %d - %d : %d\n", resultat[i].source, resultat[i].destination, resultat[i].poids);

free(sousEnsembles);
}

// Programme principal
int main() {
Graphe graphe;
[Link] = 6; // Nombre de stations électriques
[Link] = 9; // Nombre de lignes électriques possibles
Page 172 sur 191
 // Définition des lignes de transmission (station1, station2, coût)
[Link][0] = (Arete){0, 1, 4};
[Link][1] = (Arete){0, 2, 4};
[Link][2] = (Arete){1, 2, 2};
[Link][3] = (Arete){1, 3, 6};
[Link][4] = (Arete){2, 3, 8};
[Link][5] = (Arete){2, 4, 5};
[Link][6] = (Arete){3, 4, 9};
[Link][7] = (Arete){3, 5, 10};
[Link][8] = (Arete){4, 5, 7};

kruskalMST(&graphe);

return 0;
}

Exemple de sortie

Lignes de transmission sélectionnées pour minimiser le coût :

Source - Destination : Coût
1-2:2
0-1:4
0-2:4
2-4:5
3 - 5 : 10
Cette sortie indique les lignes de transmission optimisées pour assurer la connexion du réseau
à moindre coût.
Cet algorithme est utilisé dans les réseaux haute tension, les microgrids et les réseaux
intelligents (smart grids).

REMARQUE
Une veine congestionnée est une veine dans laquelle le sang s'accumule anormalement,
provoquant une augmentation de la pression et un gonflement. Cette congestion est souvent
due à une mauvaise circulation sanguine causée par une obstruction, une insuffisance
veineuse ou un dysfonctionnement des valves veineuses.

Causes possibles :

Insuffisance veineuse chronique : Les valves des veines ne fonctionnent pas correctement,
entraînant un reflux sanguin.
- Thrombose veineuse : Un caillot sanguin bloque partiellement ou totalement la veine,
empêchant le retour normal du sang.
- Compression veineuse : Une pression externe sur la veine (ex. : tumeur, grossesse, position
prolongée) limite le flux sanguin.
- Varices : Dilatation anormale des veines qui empêche un drainage efficace du sang.

Symptômes :
Page 173 sur 191
- Gonflement et douleur au niveau de la veine concernée
- Sensation de lourdeur ou de tension dans les jambes
- Rougeur ou bleuissement de la peau (dans les cas sévères)
- Apparition de veines visibles et dilatées

Traitements et prévention :

- Compression veineuse (bas de contention) pour favoriser le retour sanguin

- Exercice physique pour activer la circulation
- Elévation des jambes pour réduire la pression veineuse
- Traitements médicaux : anticoagulants, veinotoniques, voire intervention chirurgicale en
cas de complications

Chapitre 6:Généralités sur la complexité

Nous allons dans cette partie introduire la notion de complexité algorithmique, sorte de
quantification de la performance d'un algorithme.

But d'un calcul de complexité

L'objectif premier d'un calcul de complexité algorithmique est de pouvoir comparer l’efficacité
d’algorithmes résolvant le même problème. Dans une situation donnée, cela permet donc d'établir
lequel des algorithmes disponibles est le plus optimal.

Si nous devons par exemple trier une liste de nombres, est -il préférable d'utiliser un tri fusion ou
un tri à bulles ?

Ce type de question est primordial, car pour des données volumineuses la différence entre les
durées d'exécution de deux algorithmes ayant la même finalité peut être de l'ordre de plusieurs
jours.

Pour faire cela nous chercherons à estimer la quantité de ressources utilisée lors de l'exécution
d'un algorithme.

Les règles que nous utiliserons pour comparer et évaluer les algorithmes devront respecter
certaines contraintes très naturelles. On requerra principalement qu'elles ne soient pas tributaires
des qualités d'une machine ou d'un choix de technologie.

En particulier, cela signifiera que ces règles seront indépendantes des facteurs suivants :

 du langage de programmation utilisé pour l'implémentation.

 du processeur de l'ordinateur sur lequel sera exécuté le code.
Page 174 sur 191
  de l'éventuel compilateur employé.
Nous allons donc effectuer des calculs sur l’algorithme en lui même, dans sa version "papier".
Les résultats de ces calculs fourniront une estimation du temps d’exécution de l’algorithme, et de
la taille mémoire occupée lors de son fonctionnement.

Les deux types de complexité

On distinguera deux sortes de complexité, selon que l'on s'intéresse au temps d'exécution ou à
l'espace mémoire occupé.

Complexité en temps

Réaliser un calcul de complexité en temps revient à décompter le nombre d’opérations

élémentaires (affectation, calcul arithmétique ou logique, comparaison…) effectuées par
l’algorithme.

Pour rendre ce calcul réalisable, on émettra l'hypothèse que toutes les opérations élémentaires sont
à égalité de coût. En pratique ce n'est pas tout à fait exact mais cette approximation est cependant
raisonnable.

On pourra donc estimer que le temps d'exécution de l'algorithme est proportionnel au nombre
d’opérations élémentaires.

Complexité en espace

La complexité en espace est quand à elle la taille de la mémoire nécessaire pour stocker les
différentes structures de données utilisées lors de l'exécution de l'algorithme.

De quoi est fonction la complexité ?

La complexité d'un algorithme va naturellement être fonction de la taille des données passées en
paramètres. Cette dépendance est logique, plus ces données seront volumineuses, plus il faudra
d'opérations élémentaires pour les traiter.

Par exemple, pour un algorithme de tri cette taille sera le nombre de valeurs à trier.

On supposera de plus que nos algorithmes n'ont qu'une donnée, do nt la taille est nécessairement
un entier naturel. La complexité en temps d’un algorithme sera donc une fonction
de Nℕ dans R+ℝ+. Nous la noterons en général TT (pour Time).
Souvent la complexité dépendra aussi de la donnée en elle même et pas seulement de sa taille. En
particulier la façon dont sont réparties les différentes valeurs qui la constituent.

Imaginons par exemple que l'on effectue une recherche séquentielle d’un élément dans une liste
non triée. Le principe de l'algorithme est simple, on parcourt un par un les éléments jusqu'à
trouver, ou pas, celui recherché. Ce parcours peut s’arrêter dès le début si le premier élément est
"le bon". Mais on peut également être amené à parcourir la liste en entier si l’élément cherché est
en dernière position, ou même n'y figure pas. Le nombre d'opération élémentaires effectuées

Page 175 sur 191

dépend donc non seulement de la taille de la liste, mais également de la répartition de ses
valeurs.

Cette remarque nous conduit à préciser un peu notre définition de la complexité en temps. En
toute rigueur, on devra en effet distinguer trois formes de complexité en temps :

 la complexité dans le meilleur des cas : c'est la situation la plus favorable, qui
correspond par exemple à la recherche d'un élément situé à la première postion d'une liste,
ou encore au tri d'une liste déjà triée.
 la complexité dans le pire des cas : c'est la situation la plus défavorable, qui correspond
par exemple à la recherche d'un élément dans une liste alors qu'il n'y figure pas, ou encore
au tri par ordre croissant d'une liste triée par ordre décroissant.
 la complexité en moyenne : on suppose là que les données sont réparties selon une
certaine loi de probabilités.
On calculera le plus souvent la complexité dans le pire des cas, car elle est la plus pertinente. Il
vaut mieux en effet toujours envisager le pire.

Dernière chose importante à prendre en considération, si la donnée en elle même est un nombre
entier, la façon de le représenter influera beaucoup sur l’appréciation de la complexité.

Par exemple, si n=4096n=4096 on peut considérer que la taille de nn est :

 la valeur de nn en elle même, façon la plus naturelle de voir les choses, i.e. 40964096
 le nombre de chiffres que comporte l'écriture en binaire de nn, i.e. 1313
 le nombre de chiffres que comporte l'écriture en décimal de nn, i.e. 44
Vu la finalité informatique de nos algorithmes, nous choisirons souvent dans ces cas là le nombre
de chiffres dans l'écriture binaire de l'entier nn.
Quelques calculs de sommes usuelles
Nous allons dans cette sous-partie énoncer et démontrer quelques égalités bien connues relatives à
certaines sommes. Elles nous seront fort utiles lors de nos calculs de complexités.

Somme de n termes constants

Soit nn élément de N∗ℕ∗ et cc élément de Rℝ.

On a
n∑k=1c=n×c∑k=1nc=n×c

Démonstration

Cette égalité est triviale puisque l'on a nn termes dans cette somme, chacun d'eux étant égal à cc.

Somme des n premiers entiers

Soit nn élément de N∗ℕ∗.

On a
n∑k=1k=n×(n+1)2∑k=1nk=n×(n+1)2

Page 176 sur 191

Démonstration

Effectuons la preuve de ce résultat par récurrence :

 Initialisation : pour n=1n=1, on a 1∑k=1k=1∑k=11k=1 qui est bien égal

à 1×(1+1)2=11×(1+1)2=1.
 Hérédité : supposons que pour un n≥1n≥1 l'égalité soit vérifiée. Calculer une somme avec
un indice allant de 11 à n+1n+1 revient à calculer cette même somme avec un indice
allant de 11 à nn, puis à rajouter le terme d'indice n+1n+1. On a
ainsi n+1∑k=1k=n∑k=1k+n+1∑k=1n+1k=∑k=1nk+n+1, et donc d'après l'hypothèse de
récurrence n+1∑k=1k=n×(n+1)2+n+1∑k=1n+1k=n×(n+1)2+n+1. Une simple mise au
même dénominateur et une petite factorisation prouvent ensuite
que n+1∑k=1k=(n+1)×(n+2)2∑k=1n+1k=(n+1)×(n+2)2. Ce qui est bien l'égalité au
rang n+1n+1.
 On conclut alors en appliquant le principe de récurrence.

L'auteur ne peut s'empécher une petite digression en proposant une preuve sans mots du résultat précédent :

Pour d'autres démonstrations du même genre, consulter l'excellent livre de Roger B. Nelsen, "Proofs Without

Somme des n premiers carrés d'entiers

Soit nn élément de N∗ℕ∗.

On a
n∑k=1k2=n×(n+1)×(2n+1)6∑k=1nk2=n×(n+1)×(2n+1)6

Démonstration

Cette égalité se démontre également par récurrence, en utilisant les mêmes arguments que lors de
la preuve précédente. Nous laissons le lecteur y réfléchir.

Somme des n premiers termes d'une suite géométrique

Soit nn élément de N∗ℕ∗ et qq élément de Rℝ.

Si q≠1q≠1, on a

Page 177 sur 191

 n∑k=0qk=1−qn+11−q∑k=0nqk=1−qn+11−q

A noter que si q=1q=1, on retrouve la somme de termes constants.

Démonstration

Là aussi une simple récurrence prouve ce résultat.

Rappels sur la fonction logarithme

La fonction logarithme jouant un rôle important dans la suite de ce cours, nous allons consacrer
cette sous-partie à en rappeler sa définition et ses propriétés classiques.

Définition

Soit aa élement de R∗+ℝ+* tel que a≠1a≠1.

Le logarithme de base aa, noté logaloga, est l'unique fonction définie sur R∗+ℝ+* vérifiant les
deux propriétés suivantes :
1. loga(a)=1loga(a)=1.
2. ∀x,y>0, loga(xy)=loga(x)+loga(y)∀x,y>0, loga(xy)=loga(x)+loga(y).

Il existe ainsi une infinité de fonctions logarithmes différentes, autant que de réels strictement
positifs différents de 11. En voici les plus courantes.
Example 1.1. Fonctions logarithmes usuelles
 Si a=ea=e, il s'agit du logarithme népérien, noté également lnln.
 Si a=2a=2, il s'agit du logarithme binaire.
 Si a=10a=10, il s'agit du logarithme décimal.

Présentons maintenant les principales formules de calculs de la fonction logarithme.

Règles opératoires

Soit aa élement de R∗+ℝ+* tel que a≠1a≠1.

1. loga(1)=0loga(1)=0.
2. ∀x>0,loga(1x)=−loga(x)∀x>0,loga(1x)=-loga(x).
3. ∀x,y>0,loga(xy)=loga(x)−loga(y)∀x,y>0,loga(xy)=loga(x)-loga(y).
4. ∀x>0,∀n∈N,loga(xn)=n×loga(x)∀x>0,∀n∈ℕ,loga(xn)=n×loga(x).

Même si ce n'est bien sûr pas l'objet de ce cours, présentons quelques éléments de preuve de ces
formules. Cela permettra au lecteur de bien se familiariser avec cette fonction.

Démonstration

Page 178 sur 191

 1. Si l'on applique l'égalité définissant le logarithme avec x=1x=1 et y=1y=1, on
obtient loga(1)=2×loga(1)loga(1)=2×loga(1). Ce qui prouve bien sûr
que loga(1)=0loga(1)=0.
2. Appliquons cette même égalité avec cette fois xx et 1x1x. Il
vient loga(1)=loga(x)+loga(1x)loga(1)=loga(x)+loga(1x), ce qui prouve le résultat.
3. Utilisons maintenant l'égalité avec xx et 1y1y. On a
alors loga(xy)=loga(x)+loga(1y)loga(xy)=loga(x)+loga(1y). Il ne reste alors plus qu'à
utiliser la seconde formule pour conclure.
4. Cette dernière égalité se prouve sans soucis par récurrence en utilisant la définition du
logarithme.

Présentons la représentation graphique d'une fonction logarithme et de sa fonction réciproque. Nul

doute que le lecteur connaît déjà l'allure de ces courbes.

Figure 1.1. Le logarithme binaire et sa fonction réciproque

En rouge la courbe du logarithme binaire et en vert celle de sa fonction

réciproque, l'exponentielle binaire. Ces deux courbes sont symétriques par rapport à la droite
tracée en bleu d'équation y=xy=x.

Premiers calculs de complexité : algorithmes itératifs

Page 179 sur 191

Nous allons dans cette partie effectuer nos premiers calculs de complexité. Nous ne traiteront ici
que le cas des algorithmes itératifs, ceux récursifs seront étudiés dans le second chapitre de ce
cours.

Avant de commencer, rappelons notre hypothèse de base : toutes les opérations élémentaires
sont à égalité de côut. Cela permet donc d'affirmer que le temps d'exécution est proportionnel au
nombre de ces opérations élémentaires.

Les algorithmes étudiés seront présentés en Python. Comme remarqué précédemment, ce choix
n'influe bien sûr pas sur leur complexité.

Algorithmes sans structures de contrôle

Pour mémoire, une structure de contrôle est une structure itérative ou une structure
conditionnelle. Si un algorithme n'en comporte pas, pour évaluer sa complexité il suffit juste
de dénombrer le nombre d’opérations successives qu'il possède.

Example 1.2. Une fonction de conversion

La fonction suivante convertit un nombre de secondes en heures, minutes, secondes :
defconversion(n):
h = n // 3600
m = (n - 3600*h) // 60
s = n % 60
return h,m,s
Cet algorithme ne comporte pas de structures de contrôle.

On peut dénombrer cinq opérations arithmétiques et trois affectations. On a donc T(n)=8T(n)=8.

Le cas des structures conditionnelles
En présence d'une structure conditionnelle, il faut commencer par dénombrer le nombre de
conditions du test.

On décompte ensuite le nombre d’opérations élémentaires de chacune des alternatives, et l'on

prend le maximum de ce décompte afin d'obtenir la complexité dans le pire des cas.

Example 1.3. Un calcul de puissance

La fonction suivante calcule (−1)n(-1)n sans effectuer de produit mais en utilisant un test avec
une alternative :
defpuissanceMoinsUn(n):
if n%2==0:
res = 1
else:
res = -1
return res
Le test de la conditionnelle comporte une opération arithmétique et une comparaison.

Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes
alternatives est de un.
Page 180 sur 191
On a donc T(n)=3T(n)=3.
Le cas des structures itératives
Il y a deux possibilités lors du traitement d'une structure itérative.

Si chaque itération comporte le même nombre d'opérations élémentaires, pour évaluer la

complexité il suffit de multiplier le nombre d'itérations par le nombre d'opérations de chacune
d'elles.

Si chaque itération ne possède pas le même nombre d'opérations , il faudra alors distinguer ces
itérations, c'est-à-dire évaluer la complexité de chacune d'elle puis en faire la somme.

Example 1.4. Calcul itératif de la somme des nn premiers entiers

Cette fonction utilise une structure for pour calculer la somme des nn premiers entiers :

defsommeEntiers(n):
somme = 0
for i in range(n+1):
somme += i
return somme
Ici chaque itération a le même nombre d’opérations, à savoir cinq : deux affections ( i et somme),
deux additions (i et somme) et une comparaison.

On a d'autre part une affectation, lors de l'initialisation de la variable somme.

Ainsi T(n)=5n+1T(n)=5n+1.
Une autre méthode pour calculer cette somme est d'utiliser une formule explicite.

Example 1.5. Calcul de la somme des nn premiers entiers à l'aide d'une formule explicite
Cette fonction utilise l'une des formules présentées dans la sous-partie 1.4 :
defsommeEntiersBis(n):
return n*(n+1)//2
Cet algorithme ne comporte pas de structures de contrôle, il est juste constitué de trois opérations
arithmétiques.

On a donc T(n)=3T(n)=3.

Premiers exemples un peu plus élaborés

On va dans cette sous-partie se pencher sur des situations un peu plus délicates avec le calcul de
la complexité des algorithmes derecherche séquentielle et du tri par sélection.

Example 1.6. Recherche séquentielle d'un élément dans une liste

La fonction suivante recherche l'élément x dans la liste l. Si x appartient à l elle retourne l'indice
de la première occurence de xdans l, sinon elle retourne -1.

Son fonctionnement est simple, les éléments de la liste sont parcouru s un par un grâce à une
structure for :

Page 181 sur 191

defrecherche(l,x):
for i in range(len(l)):
if l[i]==x:
return i
return -1
Ici la complexité sera fonction de la longueur de la liste, que nous noterons nn.
Dans le pire des cas l'élément recherché n'appartient pas à la liste, et il a fallu la parcourir en
entier pour arriver à cette conclusion, c'est-à-dire effectuer nn itérations.
De plus, chaque itération comporte le même nombre d'opérations élémentaires, à savoir une
affectation, une addition et deux comparaisons.

On a donc T(n)=4nT(n)=4n.
L'exemple qui suit contient une imbrication de boucles, il demande donc un peu plus de vigilance.

Example 1.7. Tri par sélection

Il consiste dans un premier temps à mettre à la première place le plus petit élément de la liste, puis
à la seconde place le deuxième plus petit élément, etc.

Sa description est la suivante :

1. Rechercher dans la liste la plus petite valeur et la permuter avec le premier élément de la
liste.
2. Rechercher ensuite la plus petite valeur à partir de la deuxième case et la permuter avec le
second élément de la liste.
3. Et ainsi de suite jusqu’à avoir parcouru toute la liste.
En voici son implémentation en Python :
deftriSelection(l):
for i in range(len(l)-1):
indMini=i
for j in range(i+1,len(l)):
if l[j]<l[indMini]:
indMini=j
l[i],l[indMini]=l[indMini],l[i]
Ici aussi la complexité sera fonction de la longueur nn de la liste.
Le pire des cas correspond à une liste triée par ordre décroissant.

Chaque itération de la boucle principale, la plus externe, ne possède pas le même nombre
d'opérations. Il y a toujours les six mêmes (les opérations concernant la variable i, l'initialisation
de indMini et l'échange des valeurs), plus les opérations dues à la boucle la plus interne, qui ell es
sont en nombre variable.

La boucle interne a elle par contre le même nombre d'opérations par itération, à savoir cinq.

Le nombre d'itérations de la boucle interne varie d'une itération à l'autre de la boucle externe :

 à la première itération de la boucle externe la variable i vaut 00 et la boucle interne

effectue donc n−1n-1 itérations.
Page 182 sur 191
  à la seconde itération de la boucle externe la variable i vaut 11 et la boucle interne
effectue donc n−2n-2 itérations.
 etc.
La complexité de cet algorithme sera alors égale à la somme du nombre d'opérations de chaque
itération de la boucle externe. A savoir

6+5×(n−1)+6+5×(n−2)+...+6+5×1=n−1∑i=1(6+5×i)=6×(n−1)+5×n−1∑i=1i=6×(n−1)+5×(n−1
)×n2=52n2+72n−66+5×(n−1)+6+5×(n−2)+...+6+5×1=∑i=1n−1(6+5×i)=6×(n−1)+5×∑i=1n
−1i=6×(n−1)+5×(n−1)× n2=52n2+72n−6
Lors de ce calcul, on a utilisé la valeur d'une somme de termes constants et celle de la somme des
premiers entiers (voir sous-partie 1.4).

Conclusion, la complexité dans le pire des cas du tri par sélection

est T(n)=2n2+3n−5T(n)=2n2+3n-5.

Comportement asymptotique des fonctions de référence

Le but de cette partie va être de comparer les complexités calculées avec des fonctions de
référence (puissance, logarithme, exponentielle, etc.). Il faudra préalablement introduire quelques
notations classiques des études de fonctions.

Notations asymptotiques
Dans cette sous-partie de généralités, on supposera que toutes les fonctions considérées sont
définies sur Nℕ et à valeurs dans R+ℝ+.
Dans notre contexte ce n'est bien sûr pas une contrainte, car les fonctions exprimant une
complexité sont nécessairement positives.

Les définitions suivantes permettent de comparer le comportement à l'infini de deux fonctions

définies sur Nℕ. Plus précisément, il s'agit de critères pour affirmer qu'une fonction
en domine une autre, ou au contraire est du même ordre de grandeur, voir même équivalente.

Notion de grand O

Borne supérieure asymptotique

On dit qu’une fonction ff est un grand O d’une fonction gg si et seulement si

∃c>0, ∃n0>0 tel que ∀n>n0, f(n)<c×g(n)∃c>0, ∃n0>0 tel que ∀n>n0, f(n)<c×g(n)
On note alors f(n)=O(g(n))f(n)=Ο(g(n)).

Moralement, cela signifie qu'à partir d'un certain rang la fonction ff est majorée par une constante
fois la fonction gg. Il s'agit donc d'une situation de domination de la fonction ff par la
fonction gg.
Figure 1.2. Interprétation graphique de la notion de grand O

Page 183 sur 191

A partir du rang n0n0, la courbe de ff est au dessous de celle de cc fois gg.
Example 1.8. Quelques relations grand O
 Si T(n)=4T(n)=4 alors T(n)=O(1)T(n)=Ο(1). Pour le prouver, prendre par
exemple c=5c=5 et n0=0n0=0.
 Si T(n)=3n+2T(n)=3n+2 alors T(n)=O(n)T(n)=Ο(n). Pour le prouver, prendre par
exemple c=4c=4 et n0=2n0=2.
 Si T(n)=2n+3T(n)=2n+3 alors T(n)=O(n2)T(n)=Ο(n2). Pour le prouver, prendre par
exemple c=3c=3 et n0=1n0=1.

Notion de grand Oméga

Borne inférieure asymptotique

On dit qu’une fonction ff est un grand Oméga d’une fonction gg si et seulement si

∃c>0, ∃n0>0 tel que ∀n>n0, c×g(n)<f(n)∃c>0, ∃n0>0 tel que ∀n>n0, c×g(n)<f(n)
On note alors f(n)=Ω(g(n))f(n)=Ω(g(n)).

Cette fois-ci, à partir d'un certain rang la fonction ff est minorée par une constante fois la
fonction gg. Il s'agit donc d'une situation de domination de la fonction gg par la fonction ff.
Figure 1.3. Interprétation graphique de la notion de grand Oméga

Page 184 sur 191

 A partir du rang n0n0, la courbe de ff est au dessus de celle de cc fois gg.
Example 1.9. Quelques relations grand Oméga
 Si T(n)=4T(n)=4 alors T(n)=Ω(1)T(n)=Ω(1).
 Si T(n)=4n+2T(n)=4n+2 alors T(n)=Ω(n)T(n)=Ω(n).
 Si T(n)=4n2+1T(n)=4n2+1 alors T(n)=Ω(n)T(n)=Ω(n).

Notion de grand Théta

Borne asymptotique

On dit qu’une fonction ff est un grand Théta d’une fonction gg si et seulement si

∃c1>0, ∃c2>0, ∃n0>0 tel que ∀n>n0, c1×g(n)<f(n)<c2×g(n)∃c1>0, ∃c2>0, ∃n0>0 tel
que ∀n>n0, c1×g(n)<f(n)<c2×g(n)
On note alors f(n)=Θ(g(n))f(n)=Θ(g(n)).

Cette situation combine les deux précédentes, à partir d'un certain rang la
fonction ff est encadrée par des multiples de la fonction gg. Cela signifie que les
fonctions ff et gg sont du même ordre de grandeur.

Il est facile de voir que

f(n)=Θ(g(n))⇔(f(n)=O(g(n))etf(n)=Ω(g(n)))f(n)=Θ(g(n))⇔(f(n)=Ο(g(n))etf(n)=Ω(g(n)))
Figure 1.4. Interprétation graphique de la notion de grand Théta

Page 185 sur 191

A partir du rang n0n0, la courbe de ff est entre celle de c1c1 fois gg et celle de c2c2 fois gg.
Example 1.10. Quelques relations grand Théta
 Si T(n)=4T(n)=4 alors T(n)=Θ(1)T(n)=Θ(1).
 Si T(n)=4n+2T(n)=4n+2 alors T(n)=Θ(n)T(n)=Θ(n).
 Si T(n)=4n2+1T(n)=4n2+1 alors T(n)=Θ(n2)T(n)=Θ(n2).

Notion d'équivalence

Equivalence

On dit qu’une fonction ff est équivalente à une fonction gg si et seulement si

limn→∞f(n)g(n)=1limn→∞f(n)g(n)=1
On note alors f(n)∼g(n)f(n)∼g(n).

Il faut bien comprendre que cette notion est plus forte que celle de grand Théta, car non
seulement les fonctions sont du même ordre de grandeur mais leur quotient tend vers 11.
Example 1.11. Quelques équivalences
 Si f(n)=4n+2f(n)=4n+2 et g(n)=4n−666g(n)=4n-666, alors f(n)∼g(n)f(n)∼g(n).
 Si f(n)=4n2−3n+5f(n)=4n2-3n+5 et g(n)=4n2g(n)=4n2, alors f(n)∼g(n)f(n)∼g(n).

Croissance des fonctions de référence

Dans cette sous-partie nous allons énoncer quelques résultats permettant de comparer entre elles
les fonctions de référence, à savoir les fonctions logarithme, exponentielle et puissance.

Cette première propriété stipule que toutes les fonctions logarithmes sont du même ordre de
grandeur.

Comparaison des fonctions logarithmes

Page 186 sur 191

Soient a,ba,b éléments de Rℝ tels que a>1a>1 et b>1b>1.
Alors, loga(n)=Θ(logb(n))loga(n)=Θ(logb(n)).

Démonstration

D'après la propriété de proportionnalité entre les fonctions logarithmes, voir sous -partie 1.5, on
a loga(n)=logb(n)logb(a)loga(n)=logb(n)logb(a). Avec les notations de la définition de grand
Théta, il suffit alors de poser n0=1n0=1 et c1=c2=1logb(a)c1=c2=1logb(a) pour prouver le
résultat.

La formule suivante, due au mathématicien écossais James Stirling (1692-1770), montre la très
forte vitesse de croissance vers plus l'infini de la fonction factorielle.

Croissance de la fonction factorielle

On a
n!∼√ 2πn (ne)nn!∼2πn(ne)n

Finissons cette sous-partie avec un résultat bien connu des bacheliers scientifiques.

Croissances comparées

Considérons les
fonctions f1(n)=1f1(n)=1, f2(n)=log(n)f2(n)=log(n), f3(n)=nf3(n)=n, f4(n)=n×log(n)f4(n)=n
×log(n), f5(n)=n2f5(n)=n2, f6(n)=n3f6(n)=n3, f7(n)=2nf7(n)=2n et f3(n)=n!f3(n)=n!.
Elles sont classées de telle sorte
que ∀i∈{1,...,7},fi(n)=O(fi+1(n))∀i∈{1,...,7}, fi(n)=O(fi+1(n)).
Autre formulation, chacune de ces fonctions est un grand O de la fonction suivante.

Pour bien fixer les idées sur le comportement de ces fonctions, voici le tracé de leurs courbes.

Figure 1.5. Représentation graphique des fonctions de référence

Page 187 sur 191

Du "bas vers le haut" on a les fonctions log(x)log(x), xx, x×log(x)x×log(x), x2x2, x3x3, 2x2x.
Classes de complexité
Il est temps maintenant de revenir à notre sujet de départ.

Les complexités algorithmiques que nous allons calculer vont dorénavant être exprimées comme
des grand O ou grand Théta de fonctions de références. Cela va nous permettre de les classer.

Des algorithmes appartenant à une même classe seront alors considérés comme de complexité
équivalente. Cela signifiera que l'on considèrera qu'ils ont la même efficacité.

Le tableau suivant récapitule les complexités de référence :

OΟ Type de complexité

O(1)Ο(1) constant

O(log(n))Ο(log(n)) logarithmique

O(n)Ο(n) linéaire

O(n×log(n))Ο(n×log(n)) quasi-linéaire

O(n2)Ο(n2) quadratique

O(n3)Ο(n3) cubique

O(2n)Ο(2n) exponentiel

Page 188 sur 191

 OΟ Type de complexité

O(n!)Ο(n!) factoriel
Classes de complexité
Voici la réinterprétation en terme de classes de complexité de certains calculs déjà effectués :
 Le calcul de la somme des nn premiers entiers à l’aide d’une formule explicite est de
complexité constante.
 Ce même calcul réalisé de façon itérative est de complexité linéaire.
 Le tri par sélection est de complexité quadratique.

Annexes : Les exercices

Annexe 1: Exercices sur les manipulations de listes chaînées

Exercice1
 1. Créez une liste avec les n premiers entiers dans l’ordre décroissant.
 2. Calculez la moyenne d’une liste.
 3. Retournez la liste des carrés d’une autre liste passée en paramètre.
 4. Créez une liste contenant des mots. Retournez le mot le plus grand suivant l’ordre
alphanumérique.
 5. Retirez le premier élément d’une liste.
 6. Retirez le dernier élément d’une liste.
 7. Ecrire une fonction qui concatène deux listes.
Exercice2
Gestion d’une pile FIFO :
 - l’ajout d’un élément se fait au sommet de la pile,
 - la suppression d’un élément se fait également au sommet de la pile.

Ecrire les fonctions suivantes :

 - InitialiserPile () qui initialise une liste vide

 - PileVide() qui retourne vrai si la liste est vide
 - Empiler() qui permet d’ajouter un élément en tête de la liste
 - Depiler() qui enlève un élément en tête de la liste

Exercice 3 - Insertion dans une liste triée

Écrire une fonction qui prend en argument une liste triée ll et un entier eltelt et qui renvoie la liste triée obtenue
par insertion à sa place de eltelt dans ll. On fera attention à ce que la liste ll peut être vide.

Exercice 4 - Recherche du premier élément d'une liste

Écrire une fonction prenant en argument une liste Liste et une variable x, et qui retourne le plus petit indice k de
la liste tel que Liste[k] soit égal à x. Si la liste ne contient pas x, alors la fonction doit retourner -1

Exercice 5 - Fusion de deux listes

Écrire une fonction fusion qui prend en argument deux listes triées L1 et L2 et qui renvoie une seule liste triée
contenant les éléments de L1 et L2.

Exercice 6 - Nombre d'occurrences

Page 189 sur 191

 1. Écrire une fonction maxi(L)maxi(L) prenant en argument une liste d'entiers naturels LL et renvoyant
le maximum des entiers de cette liste (on n'utilisera pas de fonction spécifique déterminant ce
maximum). Quelle est le nombre d'opérations élémentaires effectué par cette fonction en fonction de la
longueur nn de la liste?
2. Écrire une fonction nboc(L)nboc(L) prenant en argument une liste d'entiers naturels LL et retournant
une liste TT de longueur M=maxi(L)+1M=maxi(L)+1 où, pour
tout i∈{0,…,M}i∈{0,…,M}, T[i]T[i] est le nombre d'occurences de ii dans la liste LL.
3. Quel est, en fonction de nn et MM, le nombre d'opérations élémentaires effectué par votre
fonction nboc(L)nboc(L)?
4. On veut que ce nombre ne dépende pas de LL. Modifier votre fonction si ce n'est pas le cas.

Exercice 7 - Recherche par dichotomie dans une liste triée

On propose l'algorithme suivant :

def rech_dicho(L,g,d,x)

if x>L(d) Alors
return d+1
else
a=g
b=d
while a!=b Faire
c=(a+b)//2
if x<=L[c]:
b=c
else:
a=c+1
return a

1. On prend L=[2,4,5,7,7,8,10] Que renvoient les instructions suivantes?

 rech_dicho(L,1,5,6)
 rech_dicho(L,0,5,1)
2. Que fait la fonction rech_dicho?
3. Quelle est la complexité de cette fonction, mesurée en nombre de comparaisons.

Annexe 2: Exercices sur les arbres

Exercice1
Définir une structure struct noeud_s permettant de coder un nœud d'un arbre binaire contenant une
valeur entière. Ajouter des typedef pour définir les nouveaux types noeud_t et arbre_t (ces types
devraient permettre de représenter une feuille, c'est à dire un arbre vide).

Exercice2
Écrire une fonction cree_arbre() qui prend en argument une valeur entière ainsi que deux arbres et
renvoie un arbre dont la racine contient cette valeur et les deux sous-arbres sont ceux donnés en
paramètre.

Exercice3
Écrire une fonction affiche_arbre2() permettant d'afficher les valeurs des nœuds d'un arbre binaire de
manière à lire la structure de l'arbre. Un nœuds sera affiché ainsi : {g,v,d} où g est le sous-arbre
gauche, v la valeur du nœuds et d le sous-arbre droit. Par exemple, l'arbre de la figure 1 sera affiché
par : {{{_,1,_},3,_},4,{{_,6,_},6,{{_,7,_},9,_}}}. Les '_' indiquent les sous-arbres vides.

Exercice4
Page 190 sur 191
Écrire une fonction compare() qui compare deux arbres binaires (la fonction renvoie une valeur nulle
si et seulement si les deux arbres binaires ont la même structure d'arbre et qu'ils portent les mêmes
valeurs aux nœuds se correspondant).

Exercice5
Écrire une fonction trouve_noeud() qui renvoie l'adresse d'un nœud de l'ABR donné en paramètre
contenant une certaine valeur (ou NULL si cette valeur ne figure pas dans l'arbre).

Exercice6
Écrire une fonction vérifie () qui renvoie un entier non nul si et seulement si l'arbre binaire passé en
paramètre est un arbre binaire de recherche. Remarque : on pourra écrire une fonction auxiliaire
(récursive) qui vérifie qu'un arbre binaire (non vide) satisfait les propriétés d'ABR et en même temps
détermine les valeurs minimales et maximales contenues dans cette arbre binaire (et les renvoie via
des pointeurs en argument...).

Exercice7
Écrire une fonction supprime() qui supprime une valeur de l'arbre (on supprimera la première
rencontrée) tout en conservant les propriétés d'ABR. L'algorithme est le suivant (une fois trouvé le
nœud contenant la valeur en question) :
si le nœud à enlever ne possède aucun fils, on l'enlève,
si le nœud à enlever n'a qu'un fils, on le remplace par ce fils,
si le noeud à enlever a deux fils, on le remplace par le sommet de plus petite valeur dans le sous-arbre
droit, puis on supprime ce sommet.

Page 191 sur 191