Dreferwaeq 2 R [PDF]

Zitiervorschau

SUPPORT DE COURS Année académique / Semestre Intitulé du cours

2023-2024/ SEMESTRE N° …. Structures de données avancées 2

Classe / Niveau Enseignant Coordonnées

GL/ Niveau 2 M. NDJE MAN Dieudonné François Tél. : 654080512 Email : [email protected] CM : 20 TD : 10

Volume horaire global

45

TP :

15

OBJECTIFS GÉNÉRAUX DU COURS : Ce cours vise à fournir aux étudiants une compréhension approfondie des structures de données avancées en utilisant le langage de programmation C.

OBJECTIFS SPECIFIQUES : ▪

Pour réussir ce cours, l'étudiant doit :

▪

Comprendre les structures et pointeurs

▪

Comprendre et manipuler les listes chainées

▪

Comprendre la gestion des fichiers

▪

Comprendre et implémenter une table de hachage

TABLE DES MATIERES CHAPITRE 1 RAPPELS SUR LES STRUCTURES DE DONNEES .............................. 1 1.1

LA STRUCTURE .............................................................................................................. 1

1.1.1

DEFINITION ............................................................................................................... 1

1.1.2

MANIPULATION D’UNE STRUCTURE .......................................................... 4

1.1.3

STRUCTURE ET POINTEURS ........................................................................... 9

1.1.4

PORTEE ET DECLARATION ............................................................................ 14

1.1.5

PRINCIPE DES LISTES CHAINEES .............................................................. 16

1.2

EXERCICES DE FIN DE CHAPITRE ...................................................................... 21

CHAPITRE 2 LES FICHIERS .................................................................................................... 23 2.1

DEFINITION ..................................................................................................................... 23

2.1.1

EXTENSION DE FICHIER .................................................................................. 23

2.1.2

SYSTEME DE FICHIERS .................................................................................... 24

2.1.3

HIERARCHIE ........................................................................................................... 25

2.1.4

HIERARCHIE SOUS UNIX ................................................................................. 26

2.1.5

LE CHEMIN D'ACCES.......................................................................................... 27

2.1.6

METADONNEES..................................................................................................... 28

2.1.7

LES FLUX : UN PEU DE THEORIE ................................................................ 29

2.1.8

ÉCRITURE VERS UN FLUX DE TEXTE....................................................... 31

2.1.9

ÉCRITURE VERS UN FLUX BINAIRE .......................................................... 35

2.1.10

LECTURE DEPUIS UN FLUX BINAIRE ................................................... 37

2.1.11

RESUME ................................................................................................................ 38

2.2

EXERCICES DE FIN DE CHAPITRE ...................................................................... 38

2.2.1

EXERCICE 1 : OBJECTIF : MANIPULATION DE FICHIERS TEXTE

EN LANGAGE C ..................................................................................................................... 38 2.2.2

EXERCICE 2 : OBJECTIF : MANIPULATION DE FICHIERS

BINAIRES EN LANGAGE C .............................................................................................. 39 2.2.3

EXERCICE 3 : GESTION DYNAMIQUE DE LA MEMOIRE .................. 39

2.2.4

EXERCICE 4 : PROGRAMME QUI PERMET DE LIRE UN FICHIER

TEXTE 39 2.2.5

EXERCICE 2 : PROGRAMME QUI PERMET DE LIRE UN FICHIER

TEXTE ET D’EN COMPTER LE NOMBRE DE MOTS ............................................. 39

CHAPITRE 3 LES LISTES CHAINEES ................................................................................. 41 3.1

INTRODUCTION ............................................................................................................ 41

3.2

CONCEPT DE LISTE CHAINEE .............................................................................. 41

3.2.1

RAPPEL SUR LES LISTES CHAINEES ........................................................ 42

3.2.2

CONSTRUIRE UNE LISTE CHAINEE ........................................................... 43

3.2.3

GEREZ LA LISTE A L'AIDE DE FONCTIONS ........................................... 45

3.2.4

OPERATION SUR UNE LISTE CHAINEE ................................................... 46

3.3

CONCEPT DE PILE ET DE FILE ............................................................................. 50

3.4

LISTE CHAINEE SIMPLE (FILE) ............................................................................ 51

3.4.1

LA CONSTRUCTION DU PROTOTYPE D'UN ELEMENT DE LA FILE 53

3.4.2

OPERATIONS SUR LES FILES ....................................................................... 53

3.5

LISTE CHAINEE SIMPLE (PILE) ............................................................................ 60

3.5.2 3.6

OPERATIONS SUR LES PILES ....................................................................... 63

LISTE DOUBLEMENT CHAINEE ............................................................................ 71

3.6.1

INTRODUCTION .................................................................................................... 71

3.6.2

LA CONSTRUCTION DU PROTOTYPE D'UN ELEMENT DE LA

LISTE 73 3.6.3 3.7

OPERATIONS DE LISTE DOUBLEMENT CHAINEE .............................. 74

EXERCICES DE FIN DE CHAPITRE .................................................................... 104

3.7.1

EXERCICE 1 .......................................................................................................... 104

3.7.2

EXERCICE 2 .......................................................................................................... 105

3.7.3

EXERCICE 3 .......................................................................................................... 105

3.7.4

EXERCICE 4 .......................................................................................................... 105

3.7.5

EXERCICE 5 (Files)............................................................................................ 106

3.7.6

EXERCICE 6 (Piles et Files) .......................................................................... 107

CHAPITRE 4 TABLE DE HACHAGE ................................................................................... 108 4.1

INTRODUCTION .......................................................................................................... 108

4.2

CONCEPT ....................................................................................................................... 109

4.2.1

DEFINITION ET PRESENTATION ............................................................... 109

4.2.2

PRESENTATION .................................................................................................. 110

4.2.3

INTERET D'UNE TABLE DE HACHAGE .................................................... 110

CHAPITRE 1 RAPPELS SUR LES STRUCTURES DE DONNEES Les structures de données en C sont des moyens permettant de regrouper différentes variables sous un même nom. Elles offrent la possibilité de créer des types de données personnalisés en regroupant des données hétérogènes sous une seule entité. Les structures de données sont un élément fondamental de la programmation en C, car elles permettent de représenter et de manipuler des informations de manière organisée. On en distingue plusieurs parmi lesquelles nous pouvons citer : Les structures de données en C sont des composants essentiels pour organiser et manipuler des données de manière efficace. Voici une exploration plus détaillée des structures de données couramment utilisées en C : ▪

Tableau (Array) : structure de données linéaire qui stocke des éléments du même type sous un seul nom. Les éléments sont accessibles à l'aide d'indices entiers.

▪

Structure (Struct) : structure permet de regrouper des éléments de différents types sous un même nom. Elle est utile pour représenter des entités complexes.

▪

Liste chaînée (Linked List) : structure de données dynamique qui consiste en des nœuds liés les uns aux autres. Chaque nœud contient une valeur et une référence (pointeur) vers le nœud suivant.

▪

Pile (Stack) : structure de données linéaire basée sur le principe Last In, First Out (LIFO). Les éléments sont ajoutés et retirés uniquement du sommet de la pile.

▪

File (Queue) : structure de données linéaire basée sur le principe First In, First Out (FIFO). Les éléments sont ajoutés à l'arrière et retirés du devant de la file.

▪

Arbre (Tree) : structure de données hiérarchique constituée de nœuds. Chaque nœud a un parent et zéro ou plusieurs enfants.

▪

Graphe (Graph) : structure de données composée de nœuds (sommets) et d'arêtes qui les relient. Les graphes peuvent être dirigés ou non dirigés.

Ces structures de données fournissent des outils puissants pour résoudre une variété de problèmes algorithmiques. Le choix de la structure de données dépend du problème spécifique que vous cherchez à résoudre et des opérations que vous prévoyez d'effectuer fréquemment sur les données.

1.1 LA STRUCTURE 1.1.1 DEFINITION Une structure est un moyen de regrouper des variables de types différents sous un seul nom. Cela permet de créer des enregistrements complexes. • Chaque élément déclaré à l’intérieur de la structure est appelé un champ ou membre. 1

• Le nom donné à la structure est appelé étiquette de la structure. 1.1.1.1 SYNTAXE DÉCLARATIVE Les syntaxes suivantes permettent de déclarer une structure en C : struct NomDeLaStructure { // Membres de la structure TypeDeMembre1 NomMembre1; TypeDeMembre2 NomMembre2; // ... (autres membres) }; Ou typedef struct NomDeLaStructure { // Membres de la structure TypeDeMembre1 NomMembre1; TypeDeMembre2 NomMembre2; // ... (autres membres) } NomAlias;

Exemple 1.1 : Déclaration d’une structure nommée Étudiant qui représente les informations associées à un étudiant. La structure a trois membres : ▪

nom: Un tableau de caractères (chaîne de caractères) de taille 50, utilisé pour stocker le nom de l'étudiant.

▪

age: Une variable de type entier (int), utilisé pour stocker l'âge de l'étudiant.

▪

moyenne: Une variable de type flottant (float), utilisé pour stocker la moyenne de l'étudiant. #include // Définition de la structure struct Etudiant { char nom[50]; int age; float moyenne; };

Ou typedef struct Etudiant { char nom[50]; int age; float moyenne; } Etudiant;

Le tableau ci-dessous compare ces deux approches pour la définition d'une structure en langage C : l'utilisation de typedef et la définition traditionnelle sans typedef.

2

1.1.1.2 REPRESENTATION EN MEMOIRE

En C, la représentation en mémoire d'une structure dépend de plusieurs facteurs, tels que l'alignement de la mémoire et le type de données que la structure contient. La mémoire est généralement organisée de manière à être efficace en termes d'accès et d'utilisation. La mémoire pourrait être organisée comme suit pour une instance de la structure Etudiant : --------------------------------------------| nom (50 octets) | age (4 octets) | moyenne (4 octets) | --------------------------------------------Chaque membre de la structure occupe une certaine quantité d'octets en mémoire. Dans cet exemple, le tableau de caractères `nom` occupe 50 octets, l'entier `age` occupe 4 octets, et le nombre à virgule flottante (réel) `moyenne` occupe également 4 octets. La taille totale de la structure est donc de 58 octets.

3

1.1.1.2.1

ALIGNEMENT DE LA MEMOIRE

Les compilateurs C peuvent introduire des octets de bourrage 1pour garantir que chaque membre de la structure commence à une adresse mémoire compatible avec son type de données. La taille totale de la structure peut être plus grande en raison de l'alignement de la mémoire. Par exemple, si l'alignement de la mémoire pour les entiers est sur 4 octets, le compilateur pourrait ajouter 2 octets de bourrage après le tableau de caractères `nom` (50 octets) et 2 octets de bourrage après l'entier `age` (4 octets) pour s'assurer que la `moyenne` commence à une adresse qui est un multiple de 4. Ainsi, la représentation exacte en mémoire dépend des spécificités de la plateforme, du compilateur et des options de compilation. 1.1.1.2.2

ACCES AUX MEMBRES DE LA STRUCTURE

Lorsque vous accédez aux membres d'une structure en C, le compilateur utilise l'offset de chaque membre 2par rapport au début de la structure pour accéder directement à la bonne position en mémoire. Par exemple, pour accéder à la valeur de l'âge dans une instance de la structure `Etudiant` : struct Etudiant etudiant; int valeurAge = etudiant.age;

Le compilateur sait que l'âge est situé à un certain offset par rapport au début de la structure et génère le code nécessaire pour accéder directement à cette position en mémoire. 1.1.2 MANIPULATION D’UNE STRUCTURE La manipulation d'une structure en langage C implique l'accès et la modification des membres de la structure via diverses opérations telles que l'initialisation, la modification et l'affichage des valeurs de la structure. Considérons la structure Etudiant créé ci-dessus. La manipuler revient à effectuer les opérations ci-dessous :

1

Les "octets de bourrage" sont des octets supplémentaires ajoutés à une structure de données pour garantir un alignement correct des membres de la structure en mémoire. Les architectures matérielles ont souvent des exigences d'alignement pour améliorer l'efficacité des accès aux données. Ainsi, les compilateurs insèrent des octets de bourrage entre les membres d'une structure afin de s'assurer que chaque membre commence à une adresse mémoire qui est une multiple de la taille de son type. Bien que cela puisse augmenter la taille totale de la structure, cela permet d'optimiser les performances d'accès aux données, en particulier sur des architectures spécifiques. 2

L'offset d'un membre dans une structure représente la distance, en octets, entre le début de la structure et le début du membre spécifié. C'est l'index ou la position relative d'un membre par rapport au début de la structure. 'offset est important lors de l'accès aux membres d'une structure, car il permet au compilateur de calculer où se trouve chaque membre en mémoire par rapport au début de la structure

4

a. INITIALISATION ET AFFICHAGE Objectif : Créer une variable de la structure et afficher ses valeurs. Dans la fonction main, nous allons créer une variable de type struct Etudiant nommée etudiant1 et la déclarer puis l’initialiser avec des valeurs spécifiques, par la suite, accéder aux membres de la structure accéder aux membres en utilisant l’opérateur (point) et afficher les informations correspondantes. Nous utiliserons la fonction strcpy pour attribuer une nouvelle valeur à la chaîne de caractères nom de la structure etudiant2. Avant l'appel à strcpy, la chaîne de caractères nom de etudiant2 était initialement vide car la structure etudiant2 a été déclarée sans initialisation explicite. Enfin, les informations de cette structure seront affichées à l'aide de la fonction printf. Implémentation sans typedef #include // Définition de la structure struct Etudiant { char nom[50]; int age; float moyenne; }; int main() { // Déclaration et initialisation d'une variable de la struct Etudiant etudiant1 = {"SANI NGATCHUI", 20, // Affichage des informations printf("Nom: %s\n", etudiant1.nom); printf("Age: %d\n", etudiant1.age); printf("Moyenne: %.2f\n", etudiant1.moyenne); // Autre manière d'initialiser struct Etudiant etudiant2; strcpy(etudiant2.nom, "SILINOU"); etudiant2.age = 20; etudiant2.moyenne = 17.5; // Accès aux membres et Affichage des informations de printf("Informations de l'étudiant 1 :\n"); printf("Nom: %s\n", etudiant1.nom); printf("Age: %d\n", etudiant1.age); printf("Moyenne: %.2f\n\n", etudiant1.moyenne); // Accès aux membres et Affichage des informations de printf("Informations de l'étudiant 2 :\n"); printf("Nom: %s\n", etudiant2.nom); printf("Age: %d\n", etudiant2.age); printf("Moyenne: %.2f\n", etudiant2.moyenne);

structure Etudiant 18.5};

la première structure

la deuxième structure

return 0; }

Implémentation avec typedef #include #include // Inclure la bibliothèque pour utiliser la fonction strcpy // Définition de la structure

5

typedef struct { char nom[50]; int age; float moyenne; } Etudiant; int main() { // Déclaration et initialisation d'une variable de la structure Etudiant Etudiant etudiant1 = {"SANI NGATCHUI", 20, 18.5}; // Affichage des informations printf("Nom: %s\n", etudiant1.nom); printf("Age: %d\n", etudiant1.age); printf("Moyenne: %.2f\n", etudiant1.moyenne); // Autre manière d'initialiser Etudiant etudiant2; strcpy(etudiant2.nom, "SILINOU"); etudiant2.age = 20; etudiant2.moyenne = 17.5; // Accès aux membres et Affichage des informations de la première structure printf("Informations de l'étudiant 1 :\n"); printf("Nom: %s\n", etudiant1.nom); printf("Age: %d\n", etudiant1.age); printf("Moyenne: %.2f\n\n", etudiant1.moyenne); // Accès aux membres et Affichage des informations de la deuxième structure printf("Informations de l'étudiant 2 :\n"); printf("Nom: %s\n", etudiant2.nom); printf("Age: %d\n", etudiant2.age); printf("Moyenne: %.2f\n", etudiant2.moyenne); return 0; }

Comparaison des deux codes

Si nous voulons afficher les informations de plusieurs étudiants, il faudrait créer un tableau de structures Etudiant et initialiser chaque élément du tableau avec des données spécifiques. 6

Ensuite, écrire une boucle for qui va parcourir le tableau et afficher les informations pour chaque étudiant. #include // Définition de la structure typedef struct { char nom[50]; int age; float moyenne; } Etudiant; int main() { // Déclaration et initialisation d'un tableau de structures Etudiant Etudiant etudiants[3] = { {"SANI NGATCHUI", 20, 19.7}, {"NJOYA SAMUEL", 22, 19.5}, {"FOMO NDANDA", 21, 19.2} }; // Affichage des informations pour chaque étudiant for (int i = 0; i < 3; ++i) { printf("Étudiant %d:\n", i + 1); printf("Nom: %s\n", etudiants[i].nom); printf("Age: %d\n", etudiants[i].age); printf("Moyenne: %.2f\n", etudiants[i].moyenne); printf("\n"); } return 0; }

b. MODIFICATION DES VALEURS Objectif : Modifier les valeurs des membres d'une structure après son initialisation. Dans le code ci-dessous nous allons modifier les valeurs de la structure initiale pour l’étudiant 1 et afficher les informations mises à jour en changeant le nom en "NJOYA SAMUEL", l'âge est modifié à 21, et la moyenne est mise à jour à 19.5. #include #include // inclure la bibliothèque pour utiliser strcpy // Définition de la structure typedef struct { char nom[50]; int age; float moyenne; } Etudiant; int main() { // Initialisation d'une structure Etudiant Etudiant etudiant1 = {"SANI NGATCHUI", 20, 18.5}; // Modification des valeurs strcpy(etudiant1.nom, "NJOYA SAMUEL"); etudiant1.age = 21; etudiant1.moyenne = 19.5; // Affichage des informations après modification printf("Nom: %s\n", etudiant1.nom);

7

printf("Age: %d\n", etudiant1.age); printf("Moyenne: %.2f\n", etudiant1.moyenne); return 0; }

Exercice d'Application : Gestion des Étudiants Objectif : Écrire un programme qui permet à l'utilisateur de saisir les informations de plusieurs étudiants, puis affiche ces informations à l’écran. Instructions : 1. Déclaration de la structure : - Définissez une structure nommée `Etudiant` avec les membres suivants : - nom (tableau de caractères de taille 50), - age (entier), - moyenne (nombre à virgule flottante). 2. Programme principal : - Demandez à l'utilisateur de saisir le nombre d'étudiants (n). - Déclarez un tableau de structures `Etudiant` avec une taille égale à n. - Utilisez une boucle pour permettre à l'utilisateur de saisir les informations de chaque étudiant (nom, âge, moyenne). - Utilisez une autre boucle pour afficher les informations de chaque étudiant après leur saisie. 3. Exemple d'exécution : - Le programme doit demander à l'utilisateur de saisir le nombre d'étudiants. - Ensuite, pour chaque étudiant, le programme doit permettre à l'utilisateur de saisir le nom, l'âge et la moyenne. - Enfin, le programme doit afficher les informations de tous les étudiants. Remarques : - Assurez-vous de gérer correctement les espaces dans les noms des étudiants lors de la saisie. - Vous pouvez ajouter des vérifications pour vous assurer que les données saisies sont valides (par exemple, l'âge ne peut pas être négatif). Note 1.1 : Nous pouvons écrire la structure dans un autre fichier hors du code main () principal. Pour l’appeler, vous devez séparer la déclaration de la structure de sa définition. Vous déclarez la structure dans un fichier d'en-tête (header file), et vous définissez la structure dans un fichier source (source file). Ensuite, vous incluez le fichier d'en-tête dans le fichier source où vous souhaitez utiliser la structure. Fichier d'en-tête (etudiant.h) #ifndef ETUDIANT_H #define ETUDIANT_H // Définition de la structure

8

typedef struct { char nom[50]; int age; float moyenne; } Etudiant; #endif // ETUDIANT_H

Fichier source (main.c) #include #include #include "etudiant.h"

// Inclut le fichier d'en-tête

int main() { // Déclaration d'une variable de type Etudiant Etudiant etudiant1; // Initialisation des membres de la structure strcpy(etudiant1.nom, "SANI NGATCHUI"); etudiant1.age = 20; etudiant1.moyenne = 18.5; // Affichage des informations printf("Nom: %s\n", etudiant1.nom); printf("Age: %d\n", etudiant1.age); printf("Moyenne: %.2f\n", etudiant1.moyenne); return 0; }

1.1.3 STRUCTURE ET POINTEURS Les structures et les pointeurs sont des concepts souvent associés. Une structure est un moyen de regrouper des variables de types différents sous un même nom. Elle permet de créer des types de données personnalisés regroupant des éléments apparentés. Un pointeur est une variable qui contient l'adresse mémoire d'une autre variable. Il permet d'accéder et de manipuler directement la mémoire, offrant des fonctionnalités avancées telles que la gestion dynamique de la mémoire. Les structures sont utilisées pour créer des objets complexes en regroupant plusieurs types de données sous un seul nom, ce qui facilite la gestion et la manipulation de données structurées. Les pointeurs sont utilisés pour des tâches avancées, telles que la gestion de la mémoire dynamique, la manipulation d'adresses mémoire, et la création de structures de données complexes. Interaction entre Structures et Pointeurs ▪

Allocation Dynamique : Les pointeurs sont souvent utilisés avec des structures pour allouer dynamiquement de la mémoire. Par exemple, l'allocation dynamique d'une structure en C se ferait avec malloc ou calloc.

▪

Accès aux Éléments : Les pointeurs permettent d'accéder aux éléments d'une structure de manière dynamique en utilisant l'opérateur de flèche (->). Par exemple, si p est un pointeur vers une structure Point, p->x accède à la variable x de cette structure. 9

▪

Passage par Référence : Les pointeurs peuvent être utilisés pour passer des structures par référence à des fonctions, permettant des modifications directes sur la structure d'origine. a. POINTEURS ET STRUCTURES

Objectif : Utiliser des pointeurs pour accéder et manipuler les membres d'une structure. En nous servant de notre Structure Etudiant, nous allons utiliser un pointeur pour accéder aux membres de la structure, ce qui va nous offrir une manière alternative d'interagir avec les données de la structure. Le code ci-dessous illustre cela. #include // Définition de la structure typedef struct { char nom[50]; int age; float moyenne; } Etudiant; int main() { // Initialisation d'une structure Etudiant Etudiant etudiant1 = {"SANI NGATCHUI", 20, 18.5}; // Déclaration d'un pointeur vers la structure Etudiant *ptrEtudiant = &etudiant1; // Accès aux membres via le pointeur printf("Nom: %s\n", ptrEtudiant->nom); printf("Age: %d\n", ptrEtudiant->age); printf("Moyenne: %.2f\n", ptrEtudiant->moyenne); return 0; }

1.1.3.1 ALLOCATION ET DESALLOCATION DE LA MEMOIRE L'allocation de mémoire est le processus de réservation d'espace mémoire pour les données nécessaires à l'exécution d'un programme. Elle peut être effectuée de deux manières : ▪

Allocation statique : la mémoire est allouée lors de la compilation du programme. Elle est libérée automatiquement à la fin du programme.

▪

Allocation dynamique : la mémoire est allouée à l'exécution du programme. Elle doit être libérée manuellement par le programmeur.

L'allocation et la désallocation de mémoire en langage C, en particulier en ce qui concerne les structures et les pointeurs, peuvent être réalisées à l'aide des fonctions `malloc`, `calloc`, `realloc` et `free`. La désallocation de mémoire est le processus de libération de l'espace mémoire qui n'est plus nécessaire. Elle est nécessaire pour éviter les fuites de mémoire, qui peuvent entraîner des problèmes de performance et de stabilité. La désallocation de la mémoire allouée statiquement

10

est effectuée automatiquement par le système d'exploitation. La désallocation de la mémoire allouée dynamiquement doit être effectuée manuellement par le programmeur. Exemple : Le code ci-dessous crée dynamiquement un tableau d'entiers de taille 10 en utilisant la fonction `malloc`, puis remplit ce tableau avec des valeurs correspondant à leurs indices à l'aide d'une boucle. Enfin, il libère la mémoire allouée dynamiquement à l'aide de la fonction `free` pour éviter les fuites de mémoire. // Allocation de mémoire dynamique int* tableau = (int*)malloc(10 * sizeof(int)); // Utilisation de la mémoire allouée for (int i = 0; i < 10; i++) { tableau[i] = i; } // Désallocation de la mémoire free(tableau);

Le tableau ci-dessus permet de présenter les deux concepts.

Allocation Dynamique de Mémoire avec des Structures :

11

1. Allocation de mémoire pour une structure :

// Définition de la structure typedef struct { int x; int y; } Point; // Allocation dynamique pour un objet de type Point Point *dynamicPoint = (Point*)malloc(sizeof(Point)); Ici, `dynamicPoint` est un pointeur vers une structure `Point`, et `malloc` alloue de la mémoire pour un objet de taille équivalente à celle de la structure `Point`. 2. Utilisation de la mémoire allouée : if (dynamicPoint != NULL) { dynamicPoint->x = 5; dynamicPoint->y = 10; } On peut accéder aux membres de la structure via le pointeur `dynamicPoint` comme s'il s'agissait d'une variable de type `Point`. 3. Désallocation de mémoire : // Libération de la mémoire allouée free(dynamicPoint); Il est crucial de libérer la mémoire allouée avec `free` pour éviter les fuites mémoire. Allocation Dynamique de Mémoire pour un Tableau de Structures : 1. Allocation de mémoire pour un tableau de structures : // Allocation dynamique pour un tableau de 5 structures Point Point *dynamicArray = (Point*)malloc(5 * sizeof(Point)); Cette fois, `dynamicArray` pointe vers le début d'un bloc de mémoire contenant un tableau de 5 structures `Point`. 2. Utilisation du tableau de structures : if (dynamicArray != NULL) { dynamicArray[0].x = 1; dynamicArray[0].y = 2; // ... } On peut accéder aux éléments du tableau de structures de manière similaire à un tableau statique. 3. Désallocation de mémoire pour un tableau de structures : // Libération de la mémoire allouée pour le tableau free(dynamicArray); Allocation Dynamique de Mémoire avec calloc : 12

La fonction `calloc` est similaire à `malloc`, mais elle initialise la mémoire allouée à zéro. Son utilisation est la même que `malloc`. Point *dynamicPoint = (Point*)calloc(1, sizeof(Point)); Allocation Dynamique de Mémoire avec realloc : La fonction `realloc` permet de redimensionner une zone de mémoire précédemment allouée. // Redimensionnement du tableau à 10 éléments Point *resizedArray = (Point*)realloc(dynamicArray, 10 * sizeof(Point)); Remarque importante : Après toute utilisation, il est impératif de libérer la mémoire allouée avec `free`. Ne pas le faire entraînerait des fuites de mémoire. free(dynamicPoint); free(resizedArray); 1.1.3.2 APPLICATION A LA STRUCTURE ETUDIANT Dans la structure Etudiant que nous manipulons depuis, nous allons écrire un code qui définit la structure Etudiant. Ensuite, il alloue dynamiquement de la mémoire pour une instance de cette structure à l'aide de malloc. Après avoir vérifié que l'allocation a réussi, il utilise un pointeur pour remplir les champs de la structure avec des valeurs spécifiques. Enfin, il affiche ces informations et libère la mémoire allouée dynamiquement pour éviter les fuites de mémoire. Si l'allocation échoue, un message d'échec est affiché.. #include #include #include // Définition de la structure Etudiant typedef struct { char nom[50]; int age; float moyenne; } Etudiant; int main() { // Allocation dynamique d'une structure Etudiant avec pointeur Etudiant *etudiant1 = (Etudiant *)malloc(sizeof(Etudiant)); // Vérification de l'allocation if (etudiant1 != NULL) { // Utilisation de la structure via le pointeur strcpy(etudiant1->nom, "BEYAS"); etudiant1->age = 21; etudiant1->moyenne = 18.7; // Affichage des informations printf("Nom : %s, Age : %d, Moyenne : %.2f\n", etudiant1->nom, etudiant1->age, etudiant1->moyenne); // Libération de la mémoire allouée free(etudiant1); } else { printf("Échec de l'allocation de mémoire.\n");

13

} return 0; }

Au final, l'allocation et la désallocation de mémoire en langage C avec des structures et des pointeurs impliquent l'utilisation de `malloc`, `calloc`, `realloc` pour l'allocation, suivi de `free` pour la libération de la mémoire allouée. Cela offre une gestion dynamique de la mémoire, particulièrement utile pour des structures dont la taille peut varier pendant l'exécution du programme. On peut donc dire que, les structures sont utilisées pour organiser des données, tandis que les pointeurs permettent une manipulation plus avancée de la mémoire, notamment avec les structures. Ensemble, ils offrent des moyens puissants de créer, organiser et manipuler des données complexes en programmation.

1.1.4 PORTEE ET DECLARATION 1.1.4.1 PORTEE Le choix d'utiliser une structure à l'intérieur ou à l'extérieur de la fonction main () dépend généralement de la portée que vous souhaitez donner à cette structure dans votre programme. Dans les exemples précédents, nous avons toujours placé notre définition de structure en dehors de toute fonction. Cependant, sachez que celle-ci peut être circonscrite à un bloc de sorte de limiter sa portée, comme pour les définitions de variables et les déclarations de variables et fonctions. Dans l’exemple ci-dessous, la structure Etudiant ne peut être utilisée que dans le bloc de la fonction main() et les éventuels sous-blocs qui la composent. #include int main(void) { typedef struct { char nom[50]; int age; float moyenne; } Etudiant; Etudiant etudiant; return 0; }

Tableau comparatif illustrant les avantages de placer une structure à l'intérieur ou à l'extérieur de la fonction main() :

14

Notez que le choix entre les deux dépendent du contexte spécifique de votre programme et des principes de conception que vous souhaitez suivre. Il n'y a pas de solution unique, et la meilleure approche dépend des besoins et de la structure de votre application. 1.1.4.2 DECLARATIONS Jusqu’à présent, nous avons parlé de définitions de structures, toutefois, comme pour les variables et les fonctions, il existe également des déclarations de structures. La déclaration consiste à spécifier le nom de la structure et à indiquer au compilateur qu'elle existe, mais sans fournir tous les détails de sa composition. La définition consiste à inclure la spécification complète des membres de la structure et de leur type. Elle alloue également l'espace mémoire nécessaire pour chaque instance de la structure. L'inconvénient majeur d'utiliser des structures sans déclaration préalable est lié à la déclaration et à l'allocation de la mémoire. En C, lorsque vous déclarez une structure, le compilateur a besoin de connaître la taille de cette structure pour allouer l'espace mémoire nécessaire. Si la structure contient des références à elle-même (comme dans le cas des structures interdépendantes ou avec des membres pointeurs vers elles-mêmes), le compilateur ne peut pas déterminer la taille de la structure tant que la définition complète de la structure n'est pas connue. Cela pose un problème lors de la création d'instances de ces structures ou lors de la manipulation de ces structures dans votre programme. Si vous essayez de déclarer une variable de la structure avant sa définition complète, le compilateur ne sait pas combien d'espace mémoire allouer, ce qui entraîne une erreur de compilation.

15

Pour éviter cela, la plupart des programmeurs C utilisent des déclarations préalables (prototypes) pour informer le compilateur de l'existence de la structure avant sa définition complète. Par exemple, vous pourriez déclarer la structure avant la fonction main comme suit: Une déclaration de structure est en fait une définition sans le corps de la structure. // Déclaration préalable de la structure (sans la définition complète) typedef struct Node Node; int main() { // Utilisation de la structure récursive Node node1, node2, node3; return 0; } // Définition complète de la structure struct Node { int data; Node* next; // Membre pointeur vers la même structure };

L’intérêt de cette déclaration vise à résoudre deux types de problèmes : les structures interdépendantes3 et les structures comportant un ou des membres qui sont des pointeurs vers elle-même4.

1.1.5 PRINCIPE DES LISTES CHAINEES Une liste chaînée est une structure de données dynamique constituée d'éléments appelés nœuds, où chaque nœud ou maillon ou élément contient des données et un pointeur vers le nœud suivant dans la séquence.

▪

La tête d’une liste chainée est son premier nœud. La queue d’une liste peut se référer soit au reste de la liste après la tête, soit au dernier nœud de la liste.

3

Les structures interdépendantes se réfèrent à des situations où une structure contient des membres qui sont du même type que la structure elle-même. Cela crée une dépendance récursive. 4

Les structures comportant un ou des membres qui sont des pointeurs vers elle-même se réfèrent à une situation où une structure a un membre qui est un pointeur vers la même structure. La principale différence avec les structures interdépendantes réside dans le fait que le membre pointeur n'est pas obligatoirement du même type que la structure elle-même.

16

▪

Le champ de chaque nœud qui contient l’adresse du nœud suivant ou précédent est généralement appelé lien ou pointeur. Le contenu est placé dans un ou plusieurs autres champs appelés données, informations ou valeur.

Les listes chaînées permettent de stocker et d'organiser des données de manière flexible, en allouant de la mémoire au fur et à mesure de l'ajout d'éléments. De manière simple, les listes chaînées sont des structures de données fondamentales en informatique, utilisées pour stocker et organiser des données de manière dynamique. Une liste chaînée est constituée d'éléments appelés nœuds, et chaque nœud contient des données et une référence (ou pointeur) vers le nœud suivant dans la séquence. Explorons le principe des listes chaînées en détail : 1.1.5.1 NŒUD D'UNE LISTE CHAINEE Un nœud dans une liste chaînée est une structure qui contient deux composants principaux • Données : Le contenu du nœud, c'est-à-dire l'information que vous souhaitez stocker. • Pointeur (ou référence) : Une référence vers le nœud suivant dans la liste. Voici à quoi ressemble généralement la structure d'un nœud en C : #include // Définition de la structure Node typedef struct Node { int data; // Données du nœud struct Node* next; // Pointeur vers le nœud suivant } Node; int main() { // Utilisation de la structure Node Node myNode; myNode.data = 42; myNode.next = NULL; // Affichage des données du nœud printf("Data: %d\n", myNode.data); printf("Next: %p\n", (void*)myNode.next); return 0; }

1.1.5.2 STRUCTURE GLOBALE DE LA LISTE CHAINEE Une liste chaînée est simplement une séquence de nœuds connectés les uns aux autres. Le premier nœud s'appelle généralement la tête de liste, et le dernier nœud peut avoir un pointeur vers `NULL` pour indiquer la fin de la liste. Visuellement, une liste chaînée ressemble à ceci : H -> [data1|next] -> [data2|next] -> [data3|next] -> ... -> [dataN|NULL] ▪

H : Tête de liste (pointe vers le premier nœud).

▪

data1, data2, data3, ..., dataN : Données stockées dans chaque nœud.

▪

next :Pointeur vers le nœud suivant.

17

Figure II.1. Schéma de deux listes chainées en C L'image ci-dessus montre deux exemples de listes chainées : une liste vide et une liste non vide. La tête de liste est un élément important de la liste chainée. Elle est utilisée pour accéder au début de la liste et pour parcourir la liste. On pourrait également expliquer que les listes chainées sont des structures de données dynamiques. Cela signifie qu'elles peuvent être modifiées à la volée, sans avoir à redimensionner la mémoire allouée à la liste. ❖ Liste vide La liste vide est représentée par un seul nœud. Le nœud a un pointeur vers NULL, ce qui signifie qu'il n'y a pas d'autre nœud dans la liste. ❖ Liste non vide La liste non vide est représentée par deux nœuds. Le premier nœud est la tête de la liste. Il contient la donnée 7777 et un pointeur vers le deuxième nœud. Le deuxième nœud est le dernier nœud de la liste. Il contient un pointeur vers NULL, ce qui signifie qu'il n'y a pas d'autre nœud après lui. ❖ Légende La légende de l'image explique les différents éléments d'une liste chainée. ▪

Tête de liste : le nœud qui pointe vers le début de la liste.

▪

Donnée : la valeur stockée dans un nœud.

▪

Lien (Pointeur) : un pointeur vers le nœud suivant dans la liste.

1.1.5.3 PRINCIPES DE BASE •

Accès Séquentiel : L'accès aux éléments d'une liste chaînée se fait séquentiellement à partir de la tête. Pour accéder à un élément spécifique, vous devez traverser la liste depuis la tête jusqu'à cet élément.

•

Insertion : Pour insérer un nouvel élément dans une liste chaînée, vous ajustez les pointeurs dans les nœuds environnants pour inclure le nouveau nœud. 18

•

Suppression : Pour supprimer un nœud, vous ajustez les pointeurs dans les nœuds environnants pour contourner le nœud à supprimer, puis vous libérez la mémoire du nœud.

1.1.5.4 EXEMPLE APPROFONDI Imaginez que vous ayez une liste de choses à faire, telles que vous rendre à l'école, faire vos devoirs et ranger votre chambre. Vous pouvez écrire cette liste sur un papier ou la mémoriser. Si vous écrivez la liste sur un papier, chaque élément de la liste est séparé par une virgule. Par exemple, votre liste pourrait ressembler à ceci : - Aller à l'école, - Faire vos devoirs, - Ranger votre chambre. Pour trouver un élément de la liste, vous devez parcourir tous les éléments jusqu'à ce que vous trouviez celui que vous cherchez. Par exemple, pour trouver l'élément "Faire vos devoirs" dans cet exemple, vous devriez parcourir la liste de la première à la deuxième virgule, car il s'agit du deuxième élément de la liste. Si vous mémorisez la liste, vous devez vous souvenir de l'ordre de tous les éléments. Pour trouver un élément de la liste, vous devez simplement vous rappeler de son ordre. Par exemple, pour trouver l'élément "faire vos devoirs", vous devriez vous rappeler que c'est le deuxième élément de la liste. Les listes chaînées sont un moyen de stocker des données en mémoire de manière similaire à une liste écrite sur un papier. Chaque élément de la liste chaînée est appelé un nœud. Un nœud contient deux informations : - La valeur que vous voulez stocker - Une référence vers le nœud suivant La référence vers le nœud suivant est un pointeur qui indique l'emplacement du nœud suivant dans la liste. Imaginez que vous ayez une liste chaînée de nombres. Le premier nœud pourrait contenir le nombre 1, le deuxième nœud pourrait contenir le nombre 2, et ainsi de suite. La référence vers le nœud suivant serait le pointeur vers le nœud suivant dans la liste. Pour trouver un élément dans une liste chaînée, vous devez commencer par le premier nœud. Si le nœud contient la valeur que vous cherchez, vous avez trouvé l'élément. Sinon, vous devez suivre la référence vers le nœud suivant. Vous continuez à suivre les références jusqu'à ce que vous trouviez l'élément que vous cherchez ou jusqu'à ce que vous arriviez à la fin de la liste.

19

CODE DU PROBLEME // Structure représentant un nœud de la liste chaînée typedef struct node { char *value; struct node *next; } node; // Fonction pour créer un nouveau nœud node *create_node(char *value) { node *new_node = malloc(sizeof(node)); new_node->value = value; new_node->next = NULL; return new_node; } // Fonction pour ajouter un nœud à la fin d'une liste chaînée void append_node(node **head, node *new_node) { if (*head == NULL) { *head = new_node; } else { node *current_node = *head; while (current_node->next != NULL) { current_node = current_node->next; } current_node->next = new_node; } } // Fonction pour trouver un nœud dans une liste chaînée node *find_node(node *head, char *value) { node *current_node = head; while (current_node != NULL) { if (strcmp(current_node->value, value) == 0) { return current_node; } current_node = current_node->next; } return NULL; } // Fonction principale int main(){ // Création de la liste chaînée node *head = NULL; node *node_1 = create_node("Aller à l'école"); node *node_2 = create_node("Faire vos devoirs"); node *node_3 = create_node("Ranger votre chambre"); append_node(&head, node_1); append_node(&head, node_2); append_node(&head, node_3); // Recherche du nœud "Faire vos devoirs" node *found_node = find_node(head, "Faire vos devoirs"); if (found_node != NULL) { printf("Le nœud trouvé est : %s\n", found_node->value); } else { printf("Le nœud n'a pas été trouvé.\n"); }

20

return 0; }

Note : Un pointeur simple, déclaré comme `node *new_node`, est utilisé pour stocker l'adresse d'un objet ou d'une structure, tandis qu'un pointeur double, noté `**head` dans le contexte d'une liste chaînée, est un pointeur vers un pointeur. Ce dernier est couramment employé pour passer l'adresse d'un pointeur en tant qu'argument à une fonction, permettant ainsi de modifier le pointeur original à l'intérieur de la fonction et de refléter ces changements à l'extérieur. Dans le cas d'une liste chaînée, `**head` représente un pointeur vers le pointeur de début de la liste, permettant des modifications dynamiques de la structure de la liste, telles que l'ajout ou la suppression de nœuds, avec une mise à jour cohérente de la tête de liste. 1.1.5.5 AVANTAGES DES LISTES CHAINEES ▪

Taille Dynamique : Les listes chaînées permettent d'ajouter ou de supprimer des éléments sans avoir besoin de spécifier la taille à l'avance, contrairement à certains tableaux.

▪

Insertions et Suppressions Efficaces : Les opérations d'insertion et de suppression peuvent être plus efficaces qu'avec d'autres structures de données, notamment pour des opérations au milieu de la liste.

1.1.5.6 INCONVENIENTS DES LISTES CHAINEES ▪

Accès Séquentiel : L'accès direct à un élément nécessite une traversée séquentielle depuis le début de la liste.

▪

Utilisation de la Mémoire : Chaque nœud nécessite un espace supplémentaire pour stocker le pointeur, ce qui peut entraîner une surcharge mémoire par rapport à un tableau statique.

Les listes chaînées sont largement utilisées dans de nombreuses applications et offrent une flexibilité considérable en termes d'ajout et de suppression d'éléments. Elles sont particulièrement utiles lorsque la taille de la structure de données peut changer fréquemment pendant l'exécution du programme.

1.2 EXERCICES DE FIN DE CHAPITRE 1.2.1.1 PROBLEME 1 : MANIPULATION DES STRUCTURES EN C Objectif : Écrire un programme en langage C qui gère une liste d'étudiants. Chaque étudiant est représenté par une structure comprenant son nom, son âge et sa moyenne. Le programme doit permettre à l'utilisateur d'ajouter de nouveaux étudiants, d'afficher la liste des étudiants, et de libérer la mémoire allouée dynamiquement. 1. Déclarez la structure "Etudiant" avec les membres nécessaires. 2. Implémentez une fonction qui ajoute un nouvel étudiant à la liste. Cette fonction devrait allouer dynamiquement de la mémoire pour le nouvel étudiant. 21

3. Implémentez une fonction qui affiche la liste des étudiants. 4. Dans la fonction principale (main), utilisez un menu pour permettre à l'utilisateur d'ajouter des étudiants et d'afficher la liste. 5. N'oubliez pas de libérer la mémoire allouée dynamiquement à la fin du programme. 1.2.1.2 PROBLEME : GESTION D'UNE FILE EN C Objectif : Écrire un programme en langage C qui simule le fonctionnement d'une file (queue). La file doit être implémentée à l'aide d'une liste chaînée. Le programme doit permettre à l'utilisateur d'enfiler et de défiler des éléments de la file. 1. Déclarez la structure "ElementFile" avec les membres nécessaires. 2. Implémentez une fonction qui ajoute un nouvel élément à la file (enfiler). 3. Implémentez une fonction qui retire un élément de la file (défiler). 4. Implémentez une fonction qui affiche le contenu actuel de la file. 5. Dans la fonction principale (main), utilisez un menu pour permettre à l'utilisateur d'enfiler, de défiler et d'afficher la file. 6. N'oubliez pas de libérer la mémoire allouée dynamiquement à la fin du programme.

22

CHAPITRE 2 LES FICHIERS L'utilisation et la manipulation de fichiers occupent une place cruciale dans le domaine de la programmation en langage C. Les fichiers constituent un moyen essentiel de stocker et d'organiser des données de manière persistante, permettant ainsi aux programmes de communiquer avec le monde extérieur. Que ce soit pour la lecture de fichiers existants, l'écriture de nouveaux contenus ou la modification de données déjà enregistrées, la gestion des fichiers en langage C revêt une importance fondamentale. Cette interaction avec les fichiers offre aux programmeurs une puissante flexibilité pour créer des applications robustes et polyvalentes. La bibliothèque standard du langage C propose une panoplie de fonctions dédiées à la manipulation de fichiers, permettant aux développeurs de concevoir des programmes capables de lire et d'écrire des informations structurées de manière efficace. Dans cette exploration du monde des fichiers en langage C, nous plongerons dans les différentes techniques pour ouvrir, fermer, lire et écrire dans des fichiers. Nous aborderons également les concepts fondamentaux tels que les modes d'ouverture, les pointeurs de fichiers, ainsi que la gestion appropriée des erreurs liées à la manipulation des fichiers. En comprenant ces aspects essentiels, les programmeurs seront mieux équipés pour créer des applications qui tirent pleinement parti de la gestion de fichiers en langage C.

2.1 DEFINITION En informatique, un fichier est un ensemble d’informations stockées sur un support, réuni sous un même nom et manipulé comme une unité.

2.1.1 EXTENSION DE FICHIER En informatique, une extension de fichier est un suffixe de nom de fichier fait pour identifier son format. Elle est généralement composée de trois ou quatre caractères, séparés du nom de fichier par un point. Par exemple, le fichier "exemple.txt" a l'extension ".txt". Les extensions de fichiers sont utilisées par les systèmes d'exploitation et les applications pour identifier le type de données contenues dans un fichier. Elles permettent de déterminer quel programme est capable d'ouvrir et d'afficher un fichier, ainsi que l'icône à utiliser pour le représenter. Chaque fichier possède une organisation interne déterminée par le format des données qu'il contient. Ces formats sont divers et spécifiques à chaque type de données, comprenant, par exemple : - Audio : Ogg, MP3, MP4, FLAC, Wave, etc. ; - Vidéo : Ogg, WebM, MP4, AVI, etc. ; - Documents : ODT, DOC et DOCX, XLS et XLSX, PDF, Postscript, etc. 23

Afin d'aider l'utilisateur à identifier le contenu d'un fichier, ces formats sont généralement indiqués par une extension, un suffixe ajouté au nom du fichier. Il est crucial de noter que cette extension est purement indicative et facultative, n'affectant en rien le contenu du fichier. Son unique but est d'assister l'utilisateur dans la reconnaissance du type de contenu d'un fichier. Les extensions de fichiers peuvent être définies par les développeurs de logiciels ou par des organisations standardisées. Il existe des centaines de milliers d'extensions de fichiers différentes, chacune correspondant à un type de données spécifique. Elles sont un élément important de l'organisation des fichiers sur un ordinateur. Elles permettent de faciliter la recherche et l'ouverture des fichiers, ainsi que de garantir que les fichiers sont ouverts avec le programme approprié.

2.1.2 SYSTEME DE FICHIERS En informatique, un système de fichiers est un ensemble de règles et de structures de données qui organisent les fichiers et les répertoires sur un périphérique de stockage. Il fait référence à la manière dont les fichiers sont nommés et organisés logiquement à des fins de stockage et de récupération et permet de localiser et d'accéder aux fichiers, de les créer, de les modifier et de les supprimer. Un système de fichiers est généralement organisé en une hiérarchie de répertoires. Un répertoire est un ensemble de fichiers et de sous-répertoires. Le répertoire racine est le répertoire parent de tous les autres répertoires. Par exemple, les systèmes d'exploitation (ou OS) DOS, Windows, OS/2, Mac OS et Unix possèdent tous un système de fichiers, où les fichiers sont enregistrés à des emplacements précis selon une structure hiérarchique (ou arborescente). Un fichier est placé dans un répertoire (appelé dossier sous Windows) ou dans un sous-répertoire, à l'emplacement souhaité dans l'arborescence. Le système de fichiers définit les conventions de nommage des fichiers, notamment le nombre maximal de caractères, les caractères autorisés et, dans certains systèmes, la taille du suffixe du nom de fichier. Il détermine en outre le format permettant de déterminer le chemin d'accès à un fichier à travers la structure de répertoires. L’exemple de schéma d'arborescence de fichiers ci-dessous montre un diagramme de la structure d'un dossier nommé "Tom". Le dossier contient quatre sous-dossiers : "Data", "Thesis", "Notes.txt" et "Tools". Le dossier "Data" contient deux fichiers texte : "One.txt" et "Two.txt". Le dossier "Tools" contient trois fichiers texte : "Format", "Stats" et "Old".

24

Figure 2.1. Exemple de schéma d'arborescence de fichiers

2.1.3 HIERARCHIE •

Chaque fichier doit avoir un nom univoque o

•

éventuellement plusieurs…

L’espace de nom est structuré en hiérarchie : o

notions de répertoire et de chemin

o

notion de répertoire racine (point d’entrée de la hiérarchie)

o

notions de chemin relatif et de répertoire courant

2.1.3.1 HIERARCHIE SOUS MS DOS / WINDOWS Chaque périphérique possède sa propre racine, identifiée par une lettre.

25

Figure 2.2. Exemple de schéma d'arborescence de fichiers

2.1.4 HIERARCHIE SOUS UNIX On a une hiérarchie unique ; chaque périphérique ancre sa racine dans un répertoire (montage).

Figure 2.3. Exemple de schéma d'arborescence de fichiers Les fichiers sont des unités de données qui contiennent des informations. Ils peuvent être de différents types, tels que des fichiers texte, des fichiers binaires, des fichiers images, des fichiers audios ou des fichiers vidéo. Le langage C fournit une bibliothèque standard de fonctions pour accéder aux fichiers. Ces fonctions permettent de lire, d'écrire, de créer, de modifier et de supprimer des fichiers. Pour faciliter la localisation et la gestion des fichiers, ceux-ci sont classés et organisés sur leur 26

support conformément à un système de fichiers. Ce système permet à l'utilisateur de structurer ses fichiers dans une arborescence de dossiers et de les localiser à partir d'un chemin d'accès spécifique.

2.1.5 LE CHEMIN D'ACCES Le chemin d'accès d'un fichier est une suite de caractères décrivant sa position dans le système de fichiers. Il se compose au minimum du nom du fichier visé et au maximum de la suite de tous les dossiers qu'il est nécessaire de traverser pour l'atteindre depuis le répertoire racine. Les dossiers sont séparés par un caractère spécifique : "/" sous Unix et "\" sous Windows. La racine d'un système de fichier est le point de départ de l'arborescence des fichiers et dossiers. Sous Unix, c'est le répertoire "/", tandis que sous Windows, chaque lecteur constitue une racine, comme par exemple "C :". Un chemin d'accès absolu commence par la racine, permettant d'atteindre le fichier depuis n'importe quelle position dans l'arborescence. Un chemin d'accès relatif, ne commençant pas par la racine, n'est valide que depuis un point spécifique dans la hiérarchie des fichiers. Ainsi, pour accéder à un fichier nommé "texte.txt" dans le dossier "Documents" situé dans le dossier "utilisateur" à la racine, le chemin d'accès absolu serait /utilisateur/documents/texte.txt sous Unix et C:\utilisateur\documents\texte.txt sous Windows (supposant qu'il soit sur le lecteur C:). Cependant, si nous sommes déjà dans le dossier "utilisateur", un chemin relatif comme documents/texte.txt ou documents\texte.txt serait utilisable. L’explication ci-dessus est représentée par la démarche ci-dessous. Implémentation : "exemple.txt" situé dans le dossier "Documents" du répertoire utilisateur sur les systèmes Windows et Linux : ▪

Sous Windows :

- Chemin absolu : `C:\Users\NomUtilisateur\Documents\exemple.txt` - Chemin relatif (si le répertoire de travail actuel est `C:\Users\NomUtilisateur\`) : `Documents\exemple.txt` ▪

Sous Linux :

- Chemin absolu : `/home/NomUtilisateur/Documents/exemple.txt` - Chemin relatif (si le répertoire de travail actuel est `/home/NomUtilisateur/`) : `Documents/exemple.txt` NB : le chemin absolu est spécifié depuis la racine du système, tandis que le chemin relatif est défini par rapport au répertoire de travail actuel. L'utilisation de l'un ou l'autre dépend du contexte et des besoins spécifiques de localisation des fichiers ou répertoires dans une hiérarchie de fichiers. 27

2.1.6 METADONNEES Les métadonnées sont des données qui décrivent d'autres données. Elles fournissent des informations supplémentaires sur les données réelles, telles que leur contenu, leur format, leur provenance, leur utilisation ou leur signification. Elles peuvent être utilisées à diverses fins, notamment : ▪

Améliorer la découverte et l'accès aux données : les métadonnées peuvent être utilisées pour indexer les données et les rendre plus faciles à trouver. Par exemple, les moteurs de recherche utilisent les métadonnées pour indexer les pages Web.

▪

Faciliter la gestion des données : les métadonnées peuvent être utilisées pour organiser et structurer les données. Par exemple, les bibliothèques utilisent les métadonnées pour organiser leurs collections de livres et de documents.

▪

Soutenir l'analyse des données : les métadonnées peuvent être utilisées pour enrichir les données et fournir des informations contextuelles. Par exemple, les analystes de données peuvent utiliser les métadonnées pour comprendre le contexte dans lequel les données ont été collectées.

Les métadonnées peuvent être structurées ou non structurées. Les métadonnées structurées sont organisées dans un format défini, tel que XML ou JSON. Les métadonnées non structurées ne sont pas organisées dans un format défini, comme le texte libre ou les images. Exemples de métadonnées Pour une image : le titre, la description, les mots-clés, la date de prise de vue, le lieu de prise de vue, le format du fichier. Pour un document : le titre, l'auteur, le sujet, la date de création, le format du fichier. Pour une base de données : les tables, les colonnes, les types de données, les contraintes. Les métadonnées sont un élément essentiel de la gestion des données. Elles peuvent être utilisées pour améliorer la découverte, l'accès, la gestion et l'analyse des données. En outre, le système de fichiers conserve généralement des métadonnées pour chaque fichier, incluant des informations telles que sa taille, ses droits d'accès, la date de dernier accès, la date de dernière modification, etc. Ces données supplémentaires contribuent à une gestion plus complète des fichiers.

28

2.1.7 LES FLUX : UN PEU DE THEORIE La bibliothèque standard fournit différentes fonctions pour manipuler les fichiers, toutes déclarées dans l’en-tête . Toutefois, celles-ci manipulent non pas des fichiers, mais des flux de données en provenance ou à destination de fichiers. Ces flux peuvent être de deux types : ▪

des flux de textes qui sont des suites de caractères terminées par un caractère de fin de ligne (\n) et formant ainsi des lignes ;

▪

des flux binaires qui sont des suites de multiplets.

2.1.7.1 POURQUOI UTILISER DES FLUX ? Les flux de données en programmation C, manipulés à travers la bibliothèque standard et déclarés dans l'en-tête , sont essentiels pour la manipulation de fichiers. Ces flux peuvent être de deux types : les flux de texte, constitués de suites de caractères formant des lignes, et les flux binaires, constitués de suites de multiplets. L'utilisation de flux plutôt que la manipulation directe de fichiers est motivée par deux raisons majeures. Premièrement, les disparités entre les systèmes d'exploitation dans la représentation des fins de ligne nécessitent une gestion complexe si l'on manipule directement les fichiers. Deuxièmement, les opérations de lecture et d'écriture impliquent souvent des accès au disque dur, la mémoire la plus lente de l'ordinateur. Pour pallier cela, la bibliothèque standard utilise la temporisation, soit par blocs, soit par lignes, minimisant ainsi les accès au disque et améliorant les performances. La bibliothèque standard fournit également trois flux par défaut lors du démarrage d'un programme : stdin (entrée standard), stdout (sortie standard) et stderr (sortie d'erreur standard). Ces flux facilitent les interactions avec l'utilisateur et la gestion des erreurs. Stdin est utilisé pour récupérer les informations fournies par l'utilisateur, stdout pour transmettre des informations à l'utilisateur (affichées généralement dans le terminal), et stderr pour transmettre des messages d'erreurs ou des avertissements, privilégiant une temporisation rapide pour une transmission efficace des informations d'erreur à l'utilisateur. 2.1.7.2 FICHIER : OUVERTURE ET FERMETURE D'UN FLUX 2.1.7.2.1 LA FONCTION FOPEN FILE *fopen(char *chemin, char *mode); La fonction fopen() permet d’ouvrir un flux. Celle-ci attend deux arguments : un chemin d’accès vers un fichier qui sera associé au flux et un mode qui détermine le type de flux (texte ou binaire) et la nature des opérations qui seront réalisées sur le fichier via le flux (lecture, écriture ou les deux). Elle retourne un pointeur vers un flux en cas de succès et un pointeur nul en cas d’échec. 29

Le mode Le mode est une chaîne de caractères composée d’une ou plusieurs lettres qui décrit le type du flux et la nature des opérations qu’il doit réaliser. Cette chaîne commence obligatoirement par la seconde de ces informations. Il existe six possibilités reprises dans le tableau ci-dessous. Mode r r+ w

Type(s) d’opération(s) Lecture Lecture et écriture Écriture

w+ a

Lecture et écriture Écriture

a+

Lecture et écriture

Effets Néant Néant Si le fichier n’existe pas, il est créé. Si le fichier existe, son contenu est effacé. Idem Si le fichier n’existe pas, il est créé. Place les données à la fin du fichier Idem

Par défaut, les flux sont des flux de textes. Pour obtenir un flux binaire, il suffit d’ajouter la lettre b à la fin de la chaîne décrivant le mode. EXEMPLE Le code ci-dessous tente d’ouvrir un fichier nommé « texte.txt » en lecture seule dans le dossier courant. Notez que dans le cas où il n’existe pas, la fonction fopen() retournera un pointeur nul (seul le mode r permet de produire ce comportement). #include #include int main(void) { FILE *fp = fopen("texte.txt", "r"); if (fp == NULL) { printf("Le fichier texte.txt n'a pas pu être ouvert\n"); return EXIT_FAILURE; } printf("Le fichier texte.txt existe\n"); return 0; }

Le code est correct, mais il serait prudent de s'assurer que l’on ferme le fichier après l'avoir ouvert. D’où intervient la fonction fclose() pour éviter des fuites de mémoire. Cela garantit que le fichier est correctement fermé avant que le programme ne se termine. 2.1.7.2.2 LA FONCTION FCLOSE int fclose(FILE *flux);

30

La fonction fclose() termine l’association entre un flux et un fichier. S’il reste des données temporisées, celles-ci sont écrites. La fonction retourne zéro en cas de succès et EOF en cas d’erreur. NB : EOF est une constante définie dans l’en-tête et est utilisée par les fonctions déclarées dans ce dernier pour indiquer soit l’arrivée à la fin d’un fichier (nous allons y venir) soit la survenance d’une erreur. La valeur de cette constante est toujours un entier négatif. Nous pouvons désormais compléter l’exemple précédent comme suit. #include #include int main(void) { FILE *fp = fopen("texte.txt", "r"); if (fp == NULL) { printf("Le fichier texte.txt n'a pas pu être ouvert\n"); return EXIT_FAILURE; } printf("Le fichier texte.txt existe\n"); if (fclose(fp) == EOF) { printf("Erreur lors de la fermeture du flux\n"); return EXIT_FAILURE; } return 0; }

Veillez qu’à chaque appel à la fonction fopen() corresponde un appel à la fonction fclose().

2.1.8 ÉCRITURE VERS UN FLUX DE TEXTE 2.1.8.1 ÉCRIRE UN CARACTERE int putc(int ch, FILE *flux); int fputc(int ch, FILE *flux); int putchar(int ch);

Les fonctions putc() et fputc() écrivent un caractère dans un flux. Il s’agit de l’opération d’écriture la plus basique sur laquelle reposent toutes les autres fonctions d’écriture. Ces deux fonctions retournent soit le caractère écrit, soit EOF si une erreur est rencontrée. La fonction putchar(), quant à elle, est identique aux fonctions putc() et fputc() si ce n’est qu’elle écrit dans le flux stdout.

31

NB : Techniquement, putc() et fputc() sont identiques, si ce n’est que putc() est en fait le plus souvent une macrofonction. Étant donné que nous n’avons pas encore vu de quoi il s’agit, préférez utiliser la fonction fputc() pour l’instant. L’exemple ci-dessous écrit le caractère « C » dans le fichier « texte.txt ». Étant donné que nous utilisons le mode w, le fichier est soit créé s’il n’existe pas, soit vidé de son contenu s’il existe (revoyez le tableau des modes à la section précédente si vous êtes perdus). #include #include int main(void) { FILE *fp = fopen("texte.txt", "w"); if (fp == NULL) { printf("Le fichier texte.txt n'a pas pu être ouvert\n"); return EXIT_FAILURE; } if (fputc('C', fp) == EOF) { printf("Erreur lors de l'écriture d'un caractère\n"); return EXIT_FAILURE; } if (fclose(fp) == EOF) { printf("Erreur lors de la fermeture du flux\n"); return EXIT_FAILURE; } return 0; }

2.1.8.2 ÉCRIRE UNE LIGNE int fputs(char *ligne, FILE *flux); int puts(char *ligne);

La fonction fputs() écrit une ligne dans le flux flux. La fonction retourne un nombre positif ou nul en cas de succès et EOF en cas d’erreurs. La fonction puts() est identique si ce n’est qu’elle ajoute automatiquement un caractère de fin de ligne et qu’elle écrit sur le flux stdout. Maintenant que nous savons comment écrire une ligne dans un flux précis, nous allons pouvoir diriger nos messages d’erreurs vers le flux stderr afin que ceux-ci soient affichés le plus rapidement possible. L’exemple suivant écrit le mot « Bonjour » suivi d’un caractère de fin de ligne au sein du fichier « texte.txt ».

32

#include #include int main(void) { FILE *fp = fopen("texte.txt", "w"); if (fp == NULL) { fputs("Le fichier texte.txt n'a pas pu être ouvert\n", stderr); return EXIT_FAILURE; } if (fputs("Bonjour\n", fp) == EOF) { fputs("Erreur lors de l'écriture d'une ligne\n", stderr); return EXIT_FAILURE; } if (fclose(fp) == EOF) { fputs("Erreur lors de la fermeture du flux\n", stderr); return EXIT_FAILURE; } return 0; }

La norme garantit qu’une ligne peut contenir jusqu’à 254 caractères (caractère de fin de ligne inclus). Aussi, veillez à ne pas écrire de ligne d’une taille supérieure à cette limite. 2.1.8.3 LECTURE DEPUIS UN FLUX DE TEXTE 2.1.8.3.1 RECUPERER UN CARACTERE int getc(FILE *flux); int fgetc(FILE *flux); int getchar(void);

Les fonctions getc() et fgetc() sont les exacts miroirs des fonctions putc() et fputc() : elles récupèrent un caractère depuis le flux fourni en argument. Il s’agit de l’opération de lecture la plus basique sur laquelle reposent toutes les autres fonctions de lecture. Ces deux fonctions retournent soit le caractère lu, soit EOF si la fin de fichier est rencontrée ou si une erreur est rencontrée. La fonction getchar(), quant à elle, est identique à ces deux fonctions si ce n’est qu’elle récupère un caractère depuis le flux stdin. NB : Comme putc(), la fonction getc() est le plus souvent une macrofonction. Utilisez donc plutôt la fonction fgetc() pour le moment. L’exemple ci-dessous lit un caractère provenant du fichier texte.txt. #include #include int main(void) { FILE *fp = fopen("texte.txt", "r");

33

if (fp == NULL) { fprintf(stderr, "Le fichier texte.txt n'a pas pu être ouvert\n"); return EXIT_FAILURE; } int ch = fgetc(fp); if (ch != EOF) printf("%c\n", ch); if (fclose(fp) == EOF) { fprintf(stderr, "Erreur lors de la fermeture du flux\n"); return EXIT_FAILURE; } return 0; }

2.1.8.4 RECUPERER UNE LIGNE char *fgets(char *tampon, int taille, FILE *flux);

La fonction fgets() lit une ligne depuis le flux flux et la stocke dans le tableau tampon. Cette dernière lit au plus un nombre de caractères égal à taille diminué de un afin de laisser la place pour le caractère nul, qui est automatiquement ajouté. Dans le cas où elle rencontre un caractère de fin de ligne : celui-ci est conservé au sein du tableau, un caractère nul est ajouté et la lecture s’arrête. La fonction retourne l’adresse du tableau tampon en cas de succès et un pointeur nul si la fin du fichier est atteinte ou si une erreur est survenue. L’exemple ci-dessous réalise donc la même opération que le code précédent, mais en utilisant la fonction fgets(). NB : Étant donné que la norme nous garantit qu’une ligne peut contenir jusqu’à 254 caractères (caractère de fin de ligne inclus), nous utilisons un tableau de 255 caractères pour les contenir (puisqu’il est nécessaire de prévoir un espace pour le caractère nul). #include #include int main(void) { char buf[255]; FILE *fp = fopen("texte.txt", "r"); if (fp == NULL) { fprintf(stderr, "Le fichier texte.txt n'a pas pu être ouvert\n");

34

return EXIT_FAILURE; } if (fgets(buf, sizeof buf, fp) != NULL) printf("%s\n", buf); if (fclose(fp) == EOF) { fprintf(stderr, "Erreur lors de la fermeture du flux\n"); return EXIT_FAILURE; } return 0; }

Toutefois, il y a un petit problème : la fonction fgets() conserve le caractère de fin de ligne qu’elle rencontre. Dès lors, nous affichons deux retours à la ligne : celui contenu dans la chaîne buf et celui affiché par printf(). Aussi, il serait préférable d’en supprimer un, de préférence celui de la chaîne de caractères. Pour ce faire, nous pouvons faire appel à une petite fonction (que nous appellerons chomp() en référence à la fonction éponyme du langage Perl) qui se chargera de remplacer le caractère de fin de ligne par un caractère nul. void chomp(char *s) { while (*s != '\n' && *s != '\0') ++s; *s = '\0'; }

2.1.8.5 LA FONCTION FSCANF La fonction fscanf() est identique à la fonction scanf() si ce n’est qu’elle récupère les données depuis le flux fourni en argument (au lieu de stdin pour scanf()). NB : Le flux stdin étant le plus souvent mémorisé par lignes, ceci vous explique pourquoi nous lisions les caractères restant après un appel à scanf() jusqu’à rencontrer un caractère de fin de ligne : pour vider le tampon du flux stdin. La fonction fscanf() retourne le nombre de conversions réussies (voire zéro, si aucune n’est demandée ou n’a pu être réalisée) ou EOF si une erreur survient avant qu’une conversion n’ait eu lieu.

2.1.9 ÉCRITURE VERS UN FLUX BINAIRE 2.1.9.1 ÉCRIRE UN MULTIPLET int putc(int ch, FILE *flux); int fputc(int ch, FILE *flux);

35

Comme pour les flux de texte, il vous est possible de recourir aux fonctions putc() et fputc(). Dans le cas d’un flux binaire, ces fonctions écrivent un multiplet (sous la forme d’un int converti en unsigned char) dans le flux spécifié. 2.1.9.2 ÉCRIRE UNE SUITE DE MULTIPLETS size_t fwrite(void *ptr, size_t taille, size_t nombre, FILE *flux);

La fonction fwrite() écrit le tableau référencé par ptr composé de nombre éléments de taille multiplets dans le flux flux. Elle retourne une valeur égale à nombre en cas de succès et une valeur inférieure en cas d’échec. L’exemple suivant écrit le contenu du tableau tab dans le fichier binaire.bin. Dans le cas où un int fait 4 octets, 20 octets seront donc écrits. #include #include #include int main(void) { int tab[5] = { 1, 2, 3, 4, 5 }; const size_t n = sizeof tab / sizeof tab[0]; FILE *fp = fopen("binaire.bin", "wb"); if (fp == NULL) { fprintf(stderr, "Le fichier binaire.bin n'a pas pu être ouvert\n"); return EXIT_FAILURE; } if (fwrite(&tab, sizeof tab[0], n, fp) != n) { fprintf(stderr, "Erreur lors de l'écriture du tableau\n"); return EXIT_FAILURE; } if (fclose(fp) == EOF) { fprintf(stderr, "Erreur lors de la fermeture du flux\n"); return EXIT_FAILURE; } return 0; }

NB : La ligne de code `const size_t n = sizeof tab / sizeof tab[0];` calcule le nombre d'éléments dans le tableau `tab` en divisant la taille totale du tableau par la taille d'un élément individuel. Cette opération utilise l'opérateur `sizeof` pour obtenir la taille en octets du tableau entier (`sizeof tab`) et celle d'un élément unique (`sizeof tab[0]`). Le résultat de cette division est attribué à la variable `n`, de type `size_t`, représentant ainsi le nombre d'éléments dans le 36

tableau. L'utilisation de cette approche permet d'écrire un code plus flexible, car elle ajuste automatiquement le nombre d'éléments si la taille des éléments du tableau change, facilitant ainsi la maintenance et l'adaptabilité du programme. Le tableau tab ici est déclaré avec cinq éléments de type entier. En supposant que la taille d'un élément (int) soit de 4 octets, la taille totale du tableau serait de 20 octets, et la taille d'un élément serait de 4 octets. Par conséquent, la division 20 / 4 donnerait 5, et la variable n serait initialisée avec la valeur 5, représentant ainsi le nombre d'éléments dans le tableau tab. Si on a `int tab[6] = { 1, 2, 3, 4, 5, 6 };`, cela signifie que le tableau `tab` contient six éléments de type entier. En supposant que la taille d'un élément (int) soit de 4 octets, la taille totale du tableau serait de 24 octets (6 éléments * 4 octets/élément). La taille d'un élément individuel du tableau serait toujours de 4 octets. Ainsi, le calcul `const size_t n = sizeof tab / sizeof tab[0];` dans ce contexte donnerait 24 / 4, ce qui équivaut à 6. La variable `n` serait donc initialisée avec la valeur 6, représentant le nombre d'éléments dans le tableau `tab`.

2.1.10 LECTURE DEPUIS UN FLUX BINAIRE 2.1.10.1 LIRE UN MULTIPLET int getc(FILE *flux); int fgetc(FILE *flux);

Lors de la lecture depuis un flux binaire, les fonctions fgetc() et getc() permettent de récupérer un multiplet (sous la forme d’un unsigned char converti en int) depuis un flux. 2.1.10.2 LIRE UNE SUITE DE MULTIPLETS size_t fread(void *ptr, size_t taille, size_t nombre, FILE *flux); La fonction fread() est l’inverse de la fonction fwrite() : elle lit nombre éléments de taille multiplets depuis le flux flux et les stocke dans l’objet référencé par ptr. Elle retourne une valeur égale à nombre en cas de succès ou une valeur inférieure en cas d’échec. Dans le cas où nous disposons du fichier binaire.bin produit par l’exemple de la section précédente, nous pouvons reconstituer le tableau tab. #include #include #include int main(void) { int tab[5] = { 0 }; const size_t n = sizeof tab / sizeof tab[0]; FILE *fp = fopen("binaire.bin", "rb"); if (fp == NULL) {

37

fprintf(stderr, "Le fichier binaire.bin n'a pas pu être ouvert\n"); return EXIT_FAILURE; } if (fread(&tab, sizeof tab[0], n, fp) != n) { fprintf(stderr, "Erreur lors de la lecture du tableau\n"); return EXIT_FAILURE; } if (fclose(fp) == EOF) { fprintf(stderr, "Erreur lors de la fermeture du flux\n"); return EXIT_FAILURE; } for (unsigned i = 0; i < n; ++i) printf("tab[%u] = %d\n", i, tab[i]); return 0; }

Résultat tab[0] = 1 tab[1] = 2 tab[2] = 3 tab[3] = 4 tab[4] = 5

2.1.11 RESUME L’extension d’un fichier fait partie de son nom et est purement indicative ; Les fichiers sont manipulés à l’aide de flux afin de s’abstraire des disparités entre systèmes d’exploitation et de recourir à la temporisation ; Trois flux de texte sont disponibles par défaut : stdin, stdout et stderr ; La fonction fopen() permet d’associer un fichier à un flux, la fonction fclose() met fin à cette association ; Les fonctions fputc(), fputs() et fprintf() écrivent des données dans un flux de texte ; Les fonctions fgetc(), fgets() et fscanf() lisent des données depuis un flux de texte ; Les fonctions fputc() et fwrite() écrivent un ou plusieurs multiplets dans un flux binaire ; Les fonctions fgetc() et fread() lisent un ou plusieurs multiplets depuis un flux binaire.

2.2 EXERCICES DE FIN DE CHAPITRE 2.2.1 EXERCICE 1 : OBJECTIF : MANIPULATION DE FICHIERS TEXTE EN LANGAGE C 1. Écrivez un programme en langage C qui crée un fichier texte nommé "donnees.txt" et y écrit les entiers de 1 à 10, un entier par ligne. 38

2. Ensuite, lisez le contenu du fichier "donnees.txt" et affichez les entiers à l'écran. 3. Ajoutez une fonction au programme qui calcule la somme des entiers lus depuis le fichier et affiche le résultat.

2.2.2 EXERCICE 2 : OBJECTIF : MANIPULATION DE FICHIERS BINAIRES EN LANGAGE C 1. Créez une structure en langage C appelée "Etudiant" avec les champs suivants : nom (chaîne de caractères), numéro d'étudiant (entier), et moyenne (nombre à virgule flottante). 2. Écrivez une fonction qui génère un tableau de structures "Etudiant" avec des données fictives pour trois étudiants. 3. Écrivez ces structures dans un fichier binaire appelé "etudiants.dat". 4. Ensuite, lisez le contenu du fichier binaire "etudiants.dat" et affichez les informations des étudiants à l'écran. 5. Ajoutez une fonction au programme qui calcule la moyenne générale des étudiants et affiche le résultat.

2.2.3 EXERCICE 3 : GESTION DYNAMIQUE DE LA MEMOIRE Objectif : Écrire un programme en langage C qui demande à l'utilisateur de saisir la taille d'un tableau, alloue dynamiquement de la mémoire pour ce tableau, puis demande à l'utilisateur de remplir le tableau avec des entiers. Enfin, le programme doit afficher la somme des éléments du tableau et libérer la mémoire allouée.

2.2.4 EXERCICE 4 : PROGRAMME QUI PERMET DE LIRE UN FICHIER TEXTE Écrire un programme qui permet de lire un fichier texte et d’en afficher le contenu à l’écran, un mot par ligne. EXPLICATIONS Pour réaliser cet exercice, il faudra utiliser les fonctions fopen(), fgets() et printf(). ▪

La fonction fopen() permet d’ouvrir un fichier. Nous allons utiliser le mode r pour lire le fichier en lecture seule.

▪

La fonction fgets() permet de lire une ligne depuis un fichier. Nous allons utiliser cette fonction pour lire les mots du fichier un par un.

▪

La fonction printf() permet d’afficher des données à l’écran. Nous allons utiliser cette fonction pour afficher les mots du fichier, un par ligne.

2.2.5 EXERCICE 2 : PROGRAMME QUI PERMET DE LIRE UN FICHIER TEXTE ET D’EN COMPTER LE NOMBRE DE MOTS Écrire un programme qui permet de lire un fichier texte et d’en compter le nombre de mots. 39

EXPLICATIONS Pour réaliser cet exercice, il faudra utiliser les fonctions fopen(), fgets() et atoi(). ▪

La fonction fopen() permet d’ouvrir un fichier. Nous allons utiliser le mode r pour lire le fichier en lecture seule.

▪

La fonction fgets() permet de lire une ligne depuis un fichier. Nous allons utiliser cette fonction pour lire les mots du fichier un par un.

▪

La fonction atoi() permet de convertir une chaîne de caractères en entier. Nous allons utiliser cette fonction pour convertir chaque mot en entier.

40

CHAPITRE 3 LES LISTES CHAINEES 3.1 INTRODUCTION Les listes chainées sont des structures de données dynamiques qui permettent de stocker des données de manière non contiguë en mémoire. Elles sont composées d'éléments, appelés nœuds, qui sont reliés entre eux par des pointeurs. Elles permettent de stocker et organiser des données de manière dynamique, facilitant l'ajout, la suppression et la modification d'éléments sans nécessiter une allocation statique de mémoire. Deux types courants de listes chaînées sont les listes chaînées simples et les listes chaînées doubles, chacune avec ses propres caractéristiques et avantages. Ces structures apparaissent naturellement dans un certain nombre de problèmes ou de situations de tous les jours, et offrent une flexibilité accrue par rapport aux tableaux statiques, car elles permettent l'insertion et la suppression efficaces d'éléments sans nécessiter une allocation de mémoire préalable. En C, la mise en œuvre de listes chaînées se base sur des nœuds qui contiennent les données ainsi que des pointeurs vers les éléments suivants ou précédents de la liste.

3.2 CONCEPT DE LISTE CHAINEE Un tableau peut être représenté en mémoire comme ceci :

Tableau de 4 cases en mémoire (représentation horizontale) Les tableaux posent un problème parce qu'ils restent fixes. On ne peut pas les rendre plus grands, sauf en en créant de nouveaux qui sont plus grands. De même, on ne peut pas ajouter une case au milieu sans déplacer tous les autres éléments.

Il n'est pas possible d'augmenter la taille d'un tableau une fois qu'il est créé, et le langage C ne fournit pas d'autres moyens de stockage de données. Cependant, il est envisageable de

41

créer un système personnalisé à partir de zéro. La clé réside dans la compréhension de la marche à suivre, et c'est précisément ce que ce chapitre aidera à comprendre.

3.2.1 RAPPEL SUR LES LISTES CHAINEES Une liste chaînée (ou liste liée) est une structure de données composées d’une séquence d’éléments de liste. Chaque enregistrement d’une liste chaînée est souvent appelé élément, nœud ou maillon. C’est un moyen d'organiser une série de données en mémoire. Cela consiste à assembler des structures en les liant entre elles à l'aide de pointeurs. On pourrait les représenter comme ceci :

Chaque élément peut contenir ce que l'on veut : un ou plusieurs int, double… En plus de cela, chaque élément possède un pointeur vers l'élément suivant :

Souvenez-vous de la manière dont les éléments sont disposés les uns par rapport aux autres : ils constituent une chaîne de pointeurs, d'où le terme "liste chaînée". Chaque élément (ou maillon) M de la liste est composé : ▪

D’un contenu utile M.val (de n’importe quel type),

▪

D’un pointeur M.suiv pointant vers l’élément suivant de la séquence.

Le dernier élément de la liste possède un pointeur M.suiv vide : NOTE 1 : La tête d’une liste est son premier nœud. La queue d’une liste peut se référer soit au reste de la liste après la tête, soit au dernier nœud de la liste. Le champ de chaque nœud qui contient l’adresse du nœud suivant ou précédent est généralement appelé lien ou pointeur. 42

Le contenu est placé dans un ou plusieurs autres champs appelés données, informations ou valeur. Une liste chainée L est entièrement définie par son maillon de tête L.tete, c’est à dire l’adresse de son premier maillon.On peut également lui ajouter un attribut L.cur pour mémoriser l’adresse d’un maillon « courant ». NOTE 2 : Contrairement aux tableaux, les éléments d'une liste chaînée ne sont pas placés côte à côte dans la mémoire. Chaque case pointe vers une autre case en mémoire, qui n'est pas nécessairement stockée juste à côté.

3.2.2 CONSTRUIRE UNE LISTE CHAINEE Nous allons essayer de créer une structure qui fonctionne sur le principe que nous venons de découvrir. 3.2.2.1 CREEZ LA STRUCTURE DE LA LISTE DES ELEMENTS Nous allons créer une liste chaînée de nombres entiers. NB : On pourrait aussi bien créer une liste chaînée contenant des nombres décimaux ou même des tableaux et des structures. Le principe des listes chaînées s'adapte à n'importe quel type de données, mais ici, je propose de faire simple pour que vous compreniez bien le principe. Chaque élément de la liste aura la structure suivante : typedef struct Element Element; struct Element { int nombre; Element *suivant; };

Cette structure contient ▪

Une donnée, ici un nombre de type int: on pourrait remplacer cela par n'importe quelle autre donnée (un double, un tableau…). Cela correspond à ce que vous voulez stocker, c'est à vous de l'adapter en fonction des besoins de votre programme.

Si on veut travailler de manière générique, l'idéal est de faire un pointeur sur void :void*. Cela permet de faire pointer vers n'importe quel type de données. ▪

Un pointeur vers un élément du même type appelé suivant. C'est ce qui permet de lier les éléments les uns aux autres : chaque élément sait où se trouve l'élément suivant en mémoire. Souvenez-vous : les cases ne sont pas côte à côte en mémoire ; c'est la grosse différence par rapport aux tableaux. Cela offre davantage de souplesse car on peut plus facilement ajouter de nouvelles cases par la suite au besoin.

43

En revanche, il ne sait pas quel est l'élément précédent, il est donc impossible de revenir en arrière à partir d'un élément avec ce type de liste. On parle de liste "simplement chaînée", alors que les listes "doublement chaînées" ont des pointeurs dans les deux sens et n'ont pas ce défaut. Elles sont néanmoins plus complexes. 3.2.2.2 CREEZ LA STRUCTURE DE CONTROLE En plus de la structure qu'on vient de créer (que l'on dupliquera autant de fois qu'il y a d'éléments), nous allons avoir besoin d'une autre structure pour contrôler l'ensemble de la liste chaînée. Elle aura la forme suivante : typedef struct Liste Liste; struct Liste { Element *premier; };

Cette structure Liste contient un pointeur vers le premier élément de la liste. En effet, il faut conserver l'adresse du premier élément pour savoir où commence la liste. Si on connaît le premier élément, on peut retrouver tous les autres en "sautant" d'élément en élément à l'aide des pointeurs suivant. NB : Une structure composée d'une seule sous-variable n'est en général pas très utile. Néanmoins, je pense que l'on aura besoin d'y ajouter des sous-variables plus tard, je préfère donc prendre les devants en créant ici une structure. On pourrait par exemple y stocker en plus la taille de la liste, c'est-à-dire le nombre d'éléments qu'elle contient. Nous n'aurons besoin de créer qu'un seul exemplaire de la structure Liste. Elle permet de contrôler toute la liste :

N'oubliez pas le dernier élément de la liste. Il est essentiel de terminer la traversée de la liste à un certain point. Pour cela, il faut indiquer au programme "Stop, c'est le dernier élément". Il suffit de faire pointer le dernier élément de la liste vers NULL, en d'autres termes, en mettant son pointeur suivant à NUL L :

44

Nous avons mis en place deux structures pour gérer une liste chaînée : ▪

Element : Représente un élément de la liste et peut être reproduit autant de fois que nécessaire.

▪

Liste : Contrôle l'ensemble de la liste. Nous n'aurons besoin que d'une seule instance de cette structure.

C'est un bon début, mais l'élément essentiel manque toujours : les fonctions qui vont manipuler la liste chaînée. En effet, il n'est pas pratique de modifier manuellement le contenu des structures à chaque besoin ! Il est préférable d'utiliser des fonctions qui automatisent cette tâche.

3.2.3 GEREZ LA LISTE A L'AIDE DE FONCTIONS À première vue, il semble évident que l'on aura besoin de fonctions pour : ▪

Initialiser la liste ;

▪

Ajouter un élément ;

▪

Supprimer un élément ;

▪

Afficher le contenu de la liste ;

▪

Supprimer la liste entière.

Il faut Commencer par initialiser la liste. La fonction d'initialisation est la première à être appelée. Elle crée la structure de contrôle et le premier élément de la liste : Liste *initialisation() { Liste *liste = malloc(sizeof(*liste)); Element *element = malloc(sizeof(*element)); if (liste == NULL || element == NULL) { exit(EXIT_FAILURE); } element->nombre = 0; element->suivant = NULL; liste->premier = element; return liste; }

45

EXPLICATIONS : Nous commençons par créer la structure de contrôle pour la liste. Le type de données est "Liste", et la variable associée est appelée "liste". L'utilisation de majuscules permet de les distinguer. Nous allouons dynamiquement la structure de contrôle avec un malloc. La taille à allouer est calculée automatiquement avec sizeof(*liste). L'ordinateur saura qu'il doit allouer l'espace nécessaire pour le stockage de la structure Liste. Nous aurions également pu écrire sizeof(Liste), mais si nous décidons ultérieurement de modifier le type du pointeur "liste", nous devrions également ajuster le sizeof. Ensuite, nous allouons de la même manière la mémoire nécessaire pour stocker le premier élément. Nous vérifions si les allocations dynamiques ont réussi. En cas d'erreur, le programme s'arrête immédiatement en utilisant exit(). Si tout s'est bien déroulé, nous définissons les valeurs de notre premier élément : ▪

La donnée "nombre" est initialisée à 0 par défaut.

▪

Le pointeur "suivant" pointe vers NULL, car le premier élément de notre liste est également le dernier pour le moment. Rappel : le dernier élément doit pointer vers NULL pour signaler qu'il est en fin de liste.

Nous avons ainsi créé en mémoire une liste composée d'un seul élément :

La liste vient d'être initialisée.

3.2.4 OPERATION SUR UNE LISTE CHAINEE 3.2.4.1 AJOUTEZ UN ELEMENT La première chose à savoir dans le cas de l’ajout d’un nouvel élément dans une liste chainée, c’est où est-ce qu'on devrait le mettre. On peut choisir. Pour le moment, de le mettre au début parce que c'est plus facile à comprendre. 46

On doit créer une fonction qui peut mettre un nouveau élément au début de la liste. Prenons un exemple : imaginons qu'il y ait déjà trois éléments dans la liste et qu'on veuille en ajouter un nouveau au début :

Il va falloir adapter le pointeur premier de la liste ainsi que le pointeur suivant de notre nouvel élément pour "insérer" correctement celui-ci dans la liste. Le codeci-dessous représente une fonction d'insertion dans une liste chaînée. La fonction prend en paramètres un pointeur vers une structure Liste et un entier représentant le nouveau nombre à insérer. Elle crée un nouvel élément de liste (struct Element) en allouant dynamiquement de la mémoire avec malloc, puis vérifie si la liste et le nouvel élément ont été correctement alloués. Ensuite, elle assigne la valeur du nouvel entier à l'attribut "nombre" du nouvel élément, et insère ce nouvel élément au début de la liste chaînée en mettant à jour les pointeurs appropriés. Si la liste ou le nouvel élément n'ont pas pu être alloués, le programme se termine avec un code d'erreur. void insertion(Liste *liste, int nvNombre) { /* Création du nouvel élément */ Element *nouveau = malloc(sizeof(*nouveau)); if (liste == NULL || nouveau == NULL) { exit(EXIT_FAILURE); } nouveau->nombre = nvNombre; /* Insertion de l'élément au début de la liste */ nouveau->suivant = liste->premier; liste->premier = nouveau; }

Nous avons ici choisi pour simplifier d'insérer l'élément en début de liste. Pour mettre à jour correctement les pointeurs, nous devons procéder dans cet ordre précis :

47

1. Faire pointer notre nouvel élément vers son futur successeur, qui est l'actuel premier élément de la liste. 2. Faire pointer le pointeur premier vers notre nouvel élément. Cela aura pour effet d'insérer correctement notre nouvel élément dans la liste chaînée :

NB : On ne peut pas suivre ces étapes dans l'ordre inverse. Si vous faites d'abord pointer premier vers notre nouvel élément, vous perdez l'adresse du premier élément de la liste. 3.2.4.2 SUPPRIMER UN ELEMENT Dans une liste chainée, la suppression ne pose pas de difficulté supplémentaire. Il faut cependant adapter les pointeurs de la liste dans le bon ordre pour ne perdre aucune information. Le code ci-dessous représente une fonction de suppression dans une liste chaînée. La fonction prend en paramètre un pointeur vers une structure Liste. Elle commence par vérifier si la liste existe. Si la liste existe et n'est pas vide (c'est-à-dire que le premier élément n'est pas NULL), la fonction crée un pointeur vers l'élément à supprimer (aSupprimer), met à jour le pointeur du premier élément de la liste pour pointer vers l'élément suivant, puis libère la mémoire de l'élément à supprimer à l'aide de la fonction free(). Ainsi, la fonction supprime l'élément en tête de la liste si la liste n'est pas vide. Si la liste est vide, aucun élément n'est supprimé. Si la liste n'existe pas, le programme se termine avec un code d'erreur. void suppression(Liste *liste) { if (liste == NULL) { exit(EXIT_FAILURE); } if (liste->premier != NULL) { Element *aSupprimer = liste->premier; liste->premier = liste->premier->suivant; free(aSupprimer); } }

48

Suppression d'un élément de la liste chaînée réussie. Il faut bien comprendre qu'on doit faire les choses dans un ordre précis : ▪

Faire pointer premier vers le second élément.

▪

Supprimer le premier élément avec un free.

Si on fait l'inverse, on perd l'adresse du second élément. 3.2.4.3 AFFICHEZ LA LISTE CHAINEE Pour afficher la liste chainée, il suffit de partir du premier élément et d'afficher chaque élément un à un en "sautant" de bloc en bloc. Le code ci-dessous représente une fonction d'affichage d'une liste chaînée. La fonction prend en paramètre un pointeur vers une structure Liste. Elle commence par vérifier si la liste existe. Si la liste existe, la fonction initialise un pointeur (actuel) sur le premier élément de la liste, puis utilise une boucle while pour parcourir la liste. À chaque itération, elle affiche la valeur de l'élément actuel suivi de " -> " et met à jour le pointeur actuel pour pointer vers l'élément suivant. La boucle continue jusqu'à ce que le pointeur actuel devienne NULL, ce qui indique la fin de la liste. Enfin, la fonction affiche "NULL" pour indiquer la fin de la liste. Si la liste n'existe pas, le programme se termine avec un code d'erreur. Cette fonction permet d'afficher les éléments d'une liste chaînée de manière séquentielle. void afficherListe(Liste *liste) { if (liste == NULL) { exit(EXIT_FAILURE); } Element *actuel = liste->premier; while (actuel != NULL) { printf("%d -> ", actuel->nombre); actuel = actuel->suivant; } printf("NULL\n"); }

▪

On part du premier élément et on affiche le contenu de chaque élément de la liste (un nombre).

▪

On se sert du pointeur suivant pour passer à l'élément qui suit à chaque fois. 49

IMPLEMENTATION DE LA LISTE DANS LE MAIN On peut tester la création de notre liste chaînée et son affichage avec un main. Le programme principal commence par initialiser une liste chaînée à l'aide de la fonction `initialisation()`. Ensuite, il insère les nombres 4, 8 et 15 dans la liste à l'aide de la fonction `insertion()`, suivi d'une opération de suppression utilisant la fonction `suppression()` pour retirer le premier élément de la liste. Enfin, la fonction `afficherListe()` est appelée pour afficher les éléments restants de la liste après ces opérations. Le programme illustre ainsi le fonctionnement des opérations d'insertion, suppression et affichage sur une liste chaînée, offrant un exemple pratique de manipulation de données structurées dans le contexte des structures de données en C. int main() { Liste *maListe = initialisation(); insertion(maListe, 4); insertion(maListe, 8); insertion(maListe, 15); suppression(maListe); afficherListe(maListe); return 0; }

En plus du premier élément (que l'on a laissé ici à 0), on en ajoute trois nouveaux à cette liste. Puis on en supprime un. Au final, le contenu de la liste chaînée sera donc : 8 -> 4 -> 0 -> NULL

3.3 CONCEPT DE PILE ET DE FILE Imaginez que vous gérez une liste d'articles qui évolue avec le temps. Vous pouvez ajouter et retirer des éléments de cette liste. Supposons que l'on ajoute toujours les nouveaux éléments au début de la liste. Lorsqu'il s'agit de retirer des éléments, deux scénarios simples sont intéressants à examiner : ▪

On retire toujours les éléments du début de la liste.

▪

On retire toujours les éléments de la fin de la liste.

Ces deux situations se produisent fréquemment dans la vie quotidienne. Dans le premier cas, on parle d'une structure de pile, et dans le deuxième cas, d'une structure de file. Par exemple, imaginez qu'un professeur ait donné un devoir à ses étudiants avec une limite de temps. Juste avant la fin du temps imparti, certains étudiants commencent à rendre leurs copies en avance. Le professeur décide de commencer à corriger les copies qu'il reçoit pour gagner du temps. Il a une pile de copies sur son bureau, et voici comment cela fonctionne : o

Un étudiant termine son devoir et le remet au professeur, qui le place au-dessus de la pile.

o

Lorsqu'il a fini de corriger une copie, il prend la première copie de la pile pour la corriger. 50

Cela correspond à ce qu'on appelle une pile. On décrit souvent ce comportement par l'expression "dernier entré, premier sorti" (ou LIFO, Last In, First Out) : la dernière copie remise est la première à être corrigée. En revanche, lorsque vous faites la queue à la caisse d'un supermarché, cela correspond à une file d'attente : les clients arrivent d'un côté de la file (au "début de la file"), et la caissière est à l'autre bout (à la "fin de la file"). Lorsqu'elle a fini de traiter les achats d'un client, elle fait avancer le client qui est à la fin de la file. C'est le comportement "premier entré, premier sorti" (ou FIFO, First In, First Out). Question : Imaginons un boulanger qui cuit du pain, le stocke, puis le vend à ses clients. Les clients préfèrent avoir du pain le plus frais possible (juste sorti du four), et le boulanger ne peut pas vendre du pain trop sec (qui est sorti du four depuis longtemps). Quels sont les avantages d'une pile ou d'une file dans ce cas ? Quelle structure choisirait-il ? o

S'il utilise une pile, il vendra toujours le pain le plus frais possible à ses clients en donnant à chaque client le pain en haut de la pile, c'est-à-dire celui qui vient de sortir du four. Cependant, le pain en bas de la pile risque d'attendre trop longtemps et pourrait devenir invendable.

o

S'il utilise une file, il vendra toujours du pain un peu moins frais à ses clients, mais le pain ne restera jamais trop longtemps chez le boulanger, évitant ainsi de devenir trop sec.

En pratique, les boulangers n'appliquent généralement aucune de ces méthodes : ils préparent le pain le matin pour la journée, s'assurant de vendre tout avant la fin de la journée. Ainsi, le pain n'attend jamais plus d'un jour chez le boulanger.

3.4 LISTE CHAINEE SIMPLE (FILE) Une File (ou Queue) est une structure de données linéaire dans laquelle les éléments sont accessibles selon une discipline FIFO (“First-In First-Out”) : le premier élément inséré dans la liste est le premier à en sortir.

51

▪

Insérer un élément dans la file est appelé enfiler (enqueue)

▪

Supprimer un élément de la file est appelé défiler (dequeue)

L’accès aux objets de la file se fait grâce à deux pointeurs, l’un pointant sur l’élément qui a été inséré en premier et l’autre pointant sur celui inséré en dernier. Les listes chaînées simples, souvent appelées files, sont constituées de nœuds successivement liés les uns aux autres. Chaque nœud contient un élément de données et un pointeur vers le nœud suivant dans la séquence. La file commence par un nœud appelé "tête" et se termine par un nœud particulier dont le pointeur vers le nœud suivant est nul, indiquant ainsi la fin de la liste. La file est une structure de données, qui permet de stocker les données dans l'ordre FIFO (First In First Out) - en français Premier Entré Premier Sorti). La récupération des données sera faite dans l'ordre d'insertion.

52

L'image ci-dessus montre un diagramme d'une file qui permet de stocker des données dans un ordre FIFO (premier entré, premier sorti). Les données sont stockées dans une liste chaînée, où chaque élément de la liste contient les données elles-mêmes et un pointeur vers l'élément suivant dans la liste. Le premier élément de la file est appelé le premier entré (First In). Le dernier élément de la file est appelé le dernier entré (Last In). Dans une file, les éléments sont placés les uns à côtés des autres on sort les éléments du plus ancien vers le plus récent. Cela correspond à ce qui se passe dans une file d'attente : si on prend l'exemple d’un garagiste, il reçoit les clients le matin et réceptionne leurs fiches dans une file d'attente. Pour effectuer les travaux sur le véhicule, le garagiste va récupérer les fiches en commençant par le premier client arrivé, c'est à dire la première fiche entrée dans la file. C'est la loi du premier arrivé, premier servi ou FIFO (First In First out). C'est le comportement classique d'une file d'attente.

3.4.1 LA CONSTRUCTION DU PROTOTYPE D'UN ELEMENT DE LA FILE Pour définir un élément de la file, le type struct sera utilisé, comprenant un champ "donnee" et un pointeur "suivant". Il est essentiel que le pointeur suivant soit du même type que l'élément lui-même, garantissant ainsi sa capacité à pointer vers l'élément. Ce mécanisme de pointage via le pointeur suivant facilitera l'accès au prochain élément de la file. typedef struct ElementListe { char *donnee; struct ElementListe *suivant; }Element;

Pour assurer le contrôle de la file, il est recommandé de sauvegarder certains éléments clés tels que le premier élément, le dernier élément et le nombre total d'éléments. Pour mettre en œuvre cette gestion, une autre structure sera utilisée, bien que l'utilisation de variables ne soit pas exclue. La composition de cette structure est la suivante : typedef struct ListeRepere{ Element *debut; Element *fin; int taille; } File;

3.4.2 OPERATIONS SUR LES FILES 3.4.2.1 INITIALISATION La fonction initialisation initialise les pointeurs debut et fin avec NULL ainsi que la taille avec la valeur 0. Cela doit être effectué avant toute autre opération sur la file. void initialisation (File * suite){ suite->debut = NULL; suite->fin = NULL; suite->taille = 0;

53

}

3.4.2.2 INSERTION D'UN ELEMENT DANS LA FILE L'algorithme d'insertion implique la déclaration d'éléments à insérer, l'allocation de mémoire pour le nouvel élément, le remplissage des données, la mise à jour des pointeurs debut et fin, et l'ajustement de la taille de la file. Etapes ▪

Déclaration d'élément(s) à insérer

▪

Allocation de la mémoire pour le nouvel élément

▪

Remplir le contenu du champ de données

▪

Mettre à jour le pointeur debut vers le 1er élément (le début de file)

▪

Mettre à jour le pointeur fin (ça nous servira pour l'insertion vers la fin de la file)

▪

Mettre à jour la taille de la file

La 1ère image affiche le début de l'insertion, donc la liste a la taille 1 après l'insertion.

Dans la file, l'élément à récupérer c'est le 1er entré. Pour cela, l'insertion se fera toujours à la fin de la file. Il s'agit de l'ordre normal de l'insertion (1er, 2ème, 3ème ...... etc.).

54

LA FONCTION

Le code ci-dessous représente une fonction "enfiler" qui prend en paramètres une file (File) représentée par une structure, un élément courant (courant) et une donnée (donnee) à insérer dans la file. La fonction crée un nouveau élément (nouveau_element) en allouant dynamiquement de la mémoire pour la structure de l'élément ainsi que pour la donnée à stocker. Ensuite, la donnée est copiée dans le nouveau élément. En fonction de la position du courant (tête de la file ou un élément existant), le nouveau élément est inséré à la position appropriée dans la file, et les liens sont mis à jour en conséquence. Enfin, la taille de la file est mise à jour, et la fonction renvoie 0 en cas de succès ou -1 en cas d'échec (manque de mémoire). int enfiler(File *suite, Element *courant, char *donnee) { // Création d'un nouveau_element et allocation mémoire Element *nouveau_element; if ((nouveau_element = (Element *)malloc(sizeof(Element))) == NULL) return -1; // Allocation mémoire pour la donnée if ((nouveau_element->donnee = (char *)malloc(50 * sizeof(char))) == NULL) { free(nouveau_element); // Libération de la mémoire en cas d'échec return -1; } // Copie de la donnée dans le nouveau_element strcpy(nouveau_element->donnee, donnee); // Ajout du nouveau_element à la file if (courant == NULL) { // Cas où la file est vide

55

if (suite->taille == 0) suite->fin = nouveau_element; // Mise à jour des liens pour ajouter le nouveau_element en tête nouveau_element->suivant = suite->debut; suite->debut = nouveau_element; } else { // Cas où la file n'est pas vide if (courant->suivant == NULL) suite->fin = nouveau_element; // Mise à jour des liens pour insérer le nouveau_element après le courant nouveau_element->suivant = courant->suivant; courant->suivant = nouveau_element; } // Mise à jour de la taille de la file suite->taille++; return 0; } IMPLEMENTATION DE LA FONCTION DANS LE MAIN()

Dans l’exemple ci-dessous, la fonction main initialise une file, ajoute quelques éléments à l'aide de la fonction enfiler, puis affiche le contenu de la file. Enfin, elle libère la mémoire allouée pour les éléments de la file. Vous pouvez adapter ce code en fonction de vos besoins spécifiques. #include #include #include // Structure pour un élément de la file typedef struct Element { char *donnee; struct Element *suivant; } Element; // Structure pour la file typedef struct File { Element *debut; Element *fin; int taille; } File; // Prototype de la fonction d'insertion int enfiler(File *suite, Element *courant, char *donnee); int main() { // Initialisation de la file File maFile; maFile.debut = NULL; maFile.fin = NULL; maFile.taille = 0; // Exemple d'utilisation de la fonction enfiler char donnee1[] = "Premier element"; char donnee2[] = "Deuxieme element"; char donnee3[] = "Troisieme element"; enfiler(&maFile, NULL, donnee1); enfiler(&maFile, maFile.debut, donnee2); enfiler(&maFile, maFile.fin, donnee3); // Affichage des éléments de la file Element *actuel = maFile.debut;

56

printf("Contenu de la file : "); while (actuel != NULL) { printf("%s -> ", actuel->donnee); actuel = actuel->suivant; } printf("NULL\n"); // Libération de la mémoire allouée pour les éléments actuel = maFile.debut; while (actuel != NULL) { Element *temp = actuel; actuel = actuel->suivant; free(temp->donnee); free(temp); } return 0; }

3.4.2.3 RETIRER UN ELEMENT DE LA FILE La fonction "defiler" supprime l'élément vers lequel pointe le pointeur début, décrémente la taille de la file, et libère la mémoire associée à cet élément. La fonction renvoie -1 en cas d'échec et 0 sinon. ETAPES : ▪

Le pointeur supp_elem contiendra l'adresse du 1er élément

▪

Le pointeur debut pointera vers le 2ème élément (après la suppression du 1er élément, le 2ème sera au début de la file)

▪

La taille de la file sera décrémentée d'un élément

57

LA FONCTION

Le code suivant représente une fonction "défiler" qui prend en paramètre une file (File) représentée par une structure. La fonction vise à retirer l'élément en tête de la file. Tout d'abord, elle vérifie si la file n'est pas vide (taille égale à zéro), renvoyant -1 en cas contraire. Ensuite, un pointeur "supp_element" est utilisé pour pointer vers l'élément en tête de la file. Les liens de la file sont mis à jour pour pointer vers l'élément suivant comme nouveau début de file. Ensuite, la mémoire allouée pour la donnée de l'élément et pour l'élément lui-même est libérée à l'aide de la fonction "free". Enfin, la taille de la file est réduite et la fonction renvoie 0 pour indiquer le succès de l'opération. int defiler (File * suite){ Element *supp_element; if (suite->taille == 0) return -1; supp_element = suite->debut; suite->debut = suite->debut->suivant; free (supp_element->donnee); free (supp_element); suite->taille--; return 0; } IMPLEMENTATION DE LA FONCTION DANS LE MAIN()

Dans ce code, le programme principal initialise une file vide et tente de retirer un élément, affichant un message indiquant le succès ou l'échec de l’opération (La fonction "défiler" retire l'élément en tête de la file.). #include #include // Structure de l'élément de la file typedef struct Element { // Données de l'élément int donnee; // Pointeur vers l'élément suivant dans la file struct Element *suivant; } Element; // Structure de la file typedef struct File { // Pointeur vers le début de la file Element *debut; // Pointeur vers la fin de la file Element *fin; // Taille de la file (nombre d'éléments) int taille; } File; // Déclaration de la fonction retirer int defiler(File *suite); int main() { // Initialisation de la file File maFile; maFile.debut = NULL;

58

maFile.fin = NULL; maFile.taille = 0; // Exemple d'utilisation de la fonction retirer int resultat = retirer(&maFile); if (resultat == 0) { printf("Retrait réussi.\n"); } else { printf("La file est vide, impossible de retirer.\n"); } return 0; }

3.4.2.4 AFFICHAGE DE LA FILE Pour afficher la file entière, il faut se positionner au début de la file (le pointeur debut le permettra). Ensuite en utilisant le pointeur suivant de chaque élément, la file est parcourue du 1er vers le dernier élément. La condition d'arrêt est donnée par la taille de la file. La fonction "affiche" parcourt la file du premier au dernier élément en utilisant les pointeurs suivants. LA FONCTION

La procédure `affiche` ci-dessous prend en entrée un pointeur vers une structure de file (`File`) et parcourt ses éléments à l'aide d'une boucle `for`. Pour chaque élément, elle affiche la donnée associée (supposée être une chaîne de caractères) en utilisant la fonction `printf`. La fonction utilise un pointeur `courant` pour traverser la file, en partant du début, et se déplace à l'élément suivant à chaque itération. Ainsi, l'affichage résultant est une ligne de texte montrant les données de chaque élément de la file, dans l'ordre où ils sont stockés, séparés par des espaces. void affiche(File *suite){ Element *courant; int i; courant = suite->debut; for(i=0;itaille;++i){ printf(" %s ", courant->donnee); courant = courant->suivant; } } IMPLEMENTATION DE LA PROCEDURE DANS LE MAIN() Le code suivant définit une structure de données de file (`File`) implémentée comme une liste chaînée de structures élémentaires (`Element`). Il crée une file (`suite`) dans la fonction `main`, ajoute deux éléments à la file avec des données spécifiques, puis affiche le contenu de la file à l'aide de la fonction `affiche`. #include typedef struct Element { char *donnee; struct Element *suivant; } Element;

59

typedef struct File { Element *debut; int taille; } File; void affiche(File *suite) { Element *courant; int i; courant = suite->debut; for (i = 0; i < suite->taille; ++i) { printf(" %s ", courant->donnee); courant = courant->suivant; } } int main() { File suite; suite.debut = NULL; suite.taille = 0; // Ajout d'éléments à la suite suite.debut = malloc(sizeof(Element)); suite.debut->donnee = "élément 1"; suite.debut->suivant = NULL; suite.taille++; suite.debut->suivant = malloc(sizeof(Element)); suite.debut->suivant->donnee = "élément 2"; suite.debut->suivant->suivant = NULL; suite.taille++; // Affichage de la suite affiche(&suite); return 0; }

En C, la création d'une liste chaînée simple implique la définition d'une structure de nœud et la manipulation des pointeurs pour gérer les liaisons entre les éléments. Les opérations courantes sur les listes chaînées simples incluent l'insertion en tête, l'insertion en fin de liste, la suppression d'un élément spécifique et la traversée de la liste.

3.5 LISTE CHAINEE SIMPLE (PILE) Une Pile (ou Stack) est une structure de données linéaire dans laquelle les éléments sont accessibles selon une discipline LIFO (“Last-In First-Out”) : l’élément inséré en dernier est le premier à sortir.

60

▪

Ajouter un élément dans la pile est appelé empiler ou pousser (push)

▪

Supprimer un élément de la pile est appelé dépiler (pop)

L’accès aux objets de la pile se fait grâce à un unique pointeur vers le sommet de la pile, appelé top. Les listes chaînées simples, souvent utilisées pour implémenter des piles, sont des structures de données linéaires qui stockent des éléments de manière séquentielle. Une liste chaînée se compose d'éléments appelés "nœuds", où chaque nœud contient une valeur et une référence (ou un pointeur) vers le nœud suivant dans la séquence. Les piles, qui suivent le principe "dernier entré, premier sorti" (LIFO - Last In, First Out), peuvent être implémentées efficacement à l'aide de listes chaînées. Une pile est une structure de données qui permet de stocker des éléments de manière ordonnée. Les éléments sont ajoutés et supprimés au sommet de la pile, ce qui signifie que le dernier élément ajouté est le premier élément à être supprimé. Par analogie, elle peut être représentée par une pile d'assiettes. Les assiettes sont ajoutées au sommet de la pile, et la première assiette à être retirée est la dernière à avoir été ajoutée. Le schéma ci-dessous illustre une pile composée de trois éléments : "Donnée 1", "Donnée 2", "Donnée 3". "Donnée 1" occupe la position supérieure de la pile, tandis que "Donnée 3" se trouve à la base. Chaque élément est représenté par un rectangle, relié aux autres par des lignes pour indiquer leurs relations(pointeurs). Pour ajouter un élément, il suffit de le placer au sommet, et pour le supprimer, il doit être retiré de la base de la pile.

61

3.5.1.1 LA CONSTRUCTION DU PROTOTYPE D'UN ELEMENT DE LA PILE La mise en place du prototype d'un élément de la pile implique l'utilisation du type struct. Chaque élément de la pile comprendra un champ "donnee" et un pointeur "suivant". Il est essentiel que le type du pointeur suivant soit le même que celui de l'élément pour garantir un pointage correct. Ce pointeur "suivant" facilitera l'accès au prochain élément. La définition de cette structure est réalisée avec le typedef de la struct ElementListe. typedef struct ElementListe { char *donnee; struct ElementListe *suivant; }Element;

Pour effectuer des opérations sur la pile, des informations clés seront sauvegardées, notamment le premier élément et le nombre total d'éléments. Le premier élément, situé en haut de la pile, permettra l'opération de récupération des données en haut de la pile. Une autre structure, ListeRepere, sera utilisée pour cette fin, composée d'un pointeur "debut" contenant l'adresse du premier élément et d'une variable "taille" indiquant le nombre total d'éléments. typedef struct ListeRepere{ Element *debut; int taille; } Pile;

Notons que contrairement aux listes simplement chaînées, nous n'utilisons pas de pointeur "fin" ici, car le pointeur "debut" suffit pour travailler uniquement au début de la liste. Peu importe la position dans la liste, le pointeur "debut" pointe toujours vers le premier élément en haut de la pile, et le champ "taille" indique le nombre d'éléments, quelle que soit l'opération effectuée sur la pile.

62

3.5.2 OPERATIONS SUR LES PILES 3.5.2.1 INITIALISATION La fonction d'initialisation doit être exécutée en premier avant toute autre manipulation de la pile. Elle se caractérise par le prototype suivant : void initialisation(Pile *tas); Cette opération initialise le pointeur "debut" avec la valeur NULL et la taille avec la valeur 0. Voici l'implémentation de la fonction : void initialisation(Pile *tas) { tas->debut = NULL; tas->taille = 0; }

3.5.2.2 INSERTION D'UN ELEMENT DANS LA PILE L'insertion d'un élément dans la pile s'effectue avec la fonction empiler, dont le prototype est le suivant : int empiler(Pile *tas, char *donnee); Le processus d'insertion consiste en la déclaration de l'élément à insérer, l'allocation de mémoire pour le nouvel élément, le remplissage du champ de données, la mise à jour du pointeur "debut" vers le nouvel élément (le sommet de la pile), et enfin, la mise à jour de la taille de la pile. ETAPES D’INSERTION D'UN ELEMENT DANS LA PILE ▪

Déclaration D'élément(S) A Insérer

▪

Allocation De La Mémoire Pour Le Nouvel Elément

▪

Remplir Le Contenu Du Champ De Données

▪

Mettre A Jour Le Pointeur Debut Vers Le 1er Elément (Le Haut De La Pile)

▪

Mettre A Jour La Taille De La Pile

La 1ère image montre le début de l'insertion, donc la liste a la taille 1 après l'insertion. La caractéristique de la pile n'est pas très bien mise en évidence avec un seul élément, puisque c'est le seul à récupérer.

En revanche la 2ème image nous permet d'observer le comportement de la pile.

63

La chose qu'il faut retenir, c'est que l'insertion se fait toujours en haut de la pile (au début de la liste).

LA FONCTION

Le code ci-dessous implémente une fonction `empiler` qui prend en paramètres une structure de pile (`Pile`) et une chaîne de caractères (`donnee`). Dans la fonction, un nouveau nœud (`Element`) est créé dynamiquement à l'aide de l'allocation de mémoire (`malloc`). Si l'allocation échoue, la fonction renvoie -1. Ensuite, un espace mémoire est alloué pour stocker la chaîne de caractères dans le nouveau nœud. La fonction utilise la fonction `strcpy` pour copier la chaîne de caractères fournie en paramètre dans le champ `donnee` du nouveau nœud. Ensuite, le nouveau nœud est inséré au début de la pile en ajustant les pointeurs appropriés, et la taille de la pile est incrémentée. Ainsi, la fonction réalise l'insertion d'un nouvel élément contenant une chaîne de caractères au sommet de la pile spécifiée. int empiler(Pile *tas, 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 = tas->debut; tas->debut = nouveau_element; tas->taille++; } IMPLEMENTATION DE LA FONCTION DANS LE MAIN()

64

Le code ci-dessous implémente une structure de pile (stack) à l'aide de listes chaînées. Il définit une structure d'élément (`Element`) qui contient une chaîne de caractères (`donnee`) et un pointeur vers l'élément suivant dans la pile (`suivant`). Il crée également une structure de pile (`Pile`) qui contient un pointeur vers le premier élément de la pile (`debut`) et la taille de la pile (`taille`). Le programme utilise une fonction `inserer` pour ajouter des éléments à la pile, en allouant dynamiquement de la mémoire pour chaque élément et sa donnée. Ensuite, il affiche le contenu de la pile et libère la mémoire allouée à la fin du programme. La pile est mise en œuvre de manière dynamique, ce qui signifie qu'elle peut grandir ou diminuer en fonction des ajouts et des suppressions d'éléments. #include #include #include // Définition de la structure Element typedef struct Element { char *donnee; struct Element *suivant; } Element; // Définition de la structure Pile typedef struct { Element *debut; size_t taille; } Pile; // Déclaration de la fonction inserer int empiler(Pile *tas, char *donnee); int main(void) { // Création d'une pile Pile maPile = {NULL, 0}; // Ajout d'éléments à la pile en utilisant la fonction inserer if (inserer(&maPile, "Premier element") == -1) { fprintf(stderr, "Erreur lors de l'ajout du premier element.\n"); return EXIT_FAILURE; } if (inserer(&maPile, "Deuxieme element") == -1) { fprintf(stderr, "Erreur lors de l'ajout du deuxieme element.\n"); return EXIT_FAILURE; } // Affichage de la pile Element *courant = maPile.debut; printf("Contenu de la pile :\n"); while (courant != NULL) { printf("%s\n", courant->donnee); courant = courant->suivant; } // Libération de la mémoire à la fin du programme courant = maPile.debut; while (courant != NULL) { Element *temp = courant; courant = courant->suivant; free(temp->donnee); free(temp); } return EXIT_SUCCESS;

65

} // Définition de la fonction empiler int empiler(Pile *tas, 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) { free(nouveau_element); return -1; } strcpy(nouveau_element->donnee, donnee); nouveau_element->suivant = tas->debut; tas->debut = nouveau_element; tas->taille++; return 0; }

3.5.2.3 RETIRER UN ELEMENT DE LA PILE La suppression d'un élément de la pile (dépilage) se réalise avec la fonction « depiler », il faut tout simplement supprimer l'élément vers lequel pointe le pointeur debut. Cette opération ne permet pas de récupérer la donnée en haut de la pile, mais seulement de la supprimer. Dont le prototype est le suivant : int depiler(Pile *tas); Cette opération supprime simplement l'élément pointé par le pointeur "debut", sans permettre de récupérer la donnée en haut de la pile. La fonction renvoie -1 en cas d'échec et 0 sinon. LES ETAPES ▪

Le Pointeur Supp_Elem Contiendra L'adresse Du 1er Elément

▪

Le Pointeur Debut Pointera Vers Le 2ème Elément (Après La Suppression Du 1er Elément, Le 2ème Sera En Haut De La Pile)

▪

La Taille De La Pile Sera Décrémentée D'un Elément

66

LA FONCTION

Le code de la fonction "depiler" ci-dessous prend en paramètre un pointeur vers une structure de pile (`Pile`). La fonction vise à retirer l'élément en haut de la pile. Elle commence par vérifier si la pile est vide en examinant la variable "taille" de la pile. Si la pile est vide, la fonction retourne -1 pour indiquer une erreur. Si la pile n'est pas vide, la fonction procède à la suppression de l'élément en haut de la pile. Elle utilise un pointeur temporaire (`supp_element`) pour stocker l'adresse de l'élément à supprimer, puis ajuste le pointeur de début de la pile pour pointer vers l'élément suivant. Ensuite, la mémoire allouée pour la donnée de l'élément est libérée, suivie de la libération de la mémoire de l'élément lui-même. Enfin, la taille de la pile est décrémentée, et la fonction retourne 0 pour indiquer une suppression réussie de l'élément en haut de la pile. int depiler(Pile *tas) { Element *supp_element; if (tas->taille == 0) return -1; supp_element = tas->debut; tas->debut = tas->debut->suivant; free(supp_element->donnee); free(supp_element); tas->taille--; return 0; } IMPLEMENTATION DE LA FONCTION DANS LE MAIN()

Le code ci-dessous implémente une structure de pile avec des fonctions associées, permettant d'ajouter des éléments à la pile et de retirer l'élément situé au sommet. La pile est représentée par une structure `Pile` contenant un pointeur vers le début et une variable de taille. Chaque élément de la pile est une structure `Element` contenant un pointeur vers les données et un pointeur vers l'élément suivant. Le programme principal démontre l'ajout d'éléments à la pile, affiche son contenu avant et après le retrait, puis libère la mémoire allouée à la fin du programme pour éviter les fuites de mémoire. #include #include // Structure pour un élément de la pile typedef struct Element { int *donnee; struct Element *suivant; } Element; // Structure pour la pile typedef struct { Element *debut; int taille; } Pile; // Fonction pour depiler un élément de la pile int depiler(Pile *tas) {

67

Element *supp_element; if (tas->taille == 0) return -1; supp_element = tas->debut; tas->debut = tas->debut->suivant; free(supp_element->donnee); free(supp_element); tas->taille--; return 0; } int main() { // Création d'une pile Pile maPile; maPile.debut = NULL; // Initialisation du début de la pile à NULL maPile.taille = 0; // Initialisation de la taille de la pile à 0 // Exemple d'ajout de données à la pile (à adapter selon le type de données) int *donnee1 = malloc(sizeof(int)); *donnee1 = 42; Element *element1 = malloc(sizeof(Element)); element1->donnee = donnee1; element1->suivant = maPile.debut; maPile.debut = element1; maPile.taille++; int *donnee2 = malloc(sizeof(int)); *donnee2 = 17; Element *element2 = malloc(sizeof(Element)); element2->donnee = donnee2; element2->suivant = maPile.debut; maPile.debut = element2; maPile.taille++; // Affichage du contenu de la pile avant le retrait printf("Contenu de la pile avant retrait : "); Element *courant = maPile.debut; while (courant != NULL) { printf("%d ", *(courant->donnee)); courant = courant->suivant; } printf("\n"); // Retrait d'un élément de la pile int resultatRetrait = depiler(&maPile); if (resultatRetrait == 0) { printf("Retrait réussi.\n"); } else { printf("La pile est vide, impossible de retirer un élément.\n"); } // Affichage du contenu de la pile après le retrait printf("Contenu de la pile après retrait : "); courant = maPile.debut; while (courant != NULL) { printf("%d ", *(courant->donnee)); courant = courant->suivant; } printf("\n"); // Libération de la mémoire utilisée par la pile (à faire à la fin du programme)

68

courant = maPile.debut; while (courant != NULL) { Element *temp = courant; courant = courant->suivant; free(temp->donnee); free(temp); } return 0; }

3.5.2.4 AFFICHAGE DE LA PILE Pour afficher la pile entière, la fonction affiche utilise le pointeur "debut" pour se positionner au début de la pile. En parcourant la pile du premier au dernier élément à l'aide du pointeur suivant, elle affiche les données. La condition d'arrêt est déterminée par la taille de la pile. LA FONCTION

Le code de la procédure "affiche" ci-dessous prend en paramètre un pointeur vers une structure de pile (Pile). La pile est représentée sous forme de liste chaînée, où chaque élément de la pile est un nœud (Element) contenant une donnée (donnee) et un pointeur vers l'élément suivant dans la pile (suivant). La fonction parcourt la pile à partir du début, affichant chaque élément de la pile (représenté par la donnée) sur la sortie standard (stdout) à l'aide de la fonction printf. Elle utilise une boucle for pour itérer à travers les éléments de la pile en utilisant le pointeur "courant", et la variable "i" pour suivre le nombre d'éléments déjà affichés. void affiche(Pile *tas) { Element *courant; int i; courant = tas->debut; for (i = 0; i < tas->taille; ++i) { printf("\t\t%s\n", courant->donnee); courant = courant->suivant; } } IMPLEMENTATION DE LA PROCEDURE DANS LE MAIN() Le code ci-dessous définit une structure de pile (stack) avec des opérations associées. Il utilise une structure d'élément comprenant une donnée sous forme de chaîne de caractères et un pointeur vers l'élément suivant. La pile est représentée par une structure comprenant un pointeur vers le premier élément et une variable pour la taille. Trois fonctions sont implémentées : initialiserPile initialise une pile vide, empiler ajoute un nouvel élément au sommet de la pile, et affiche affiche les éléments de la pile. Dans la fonction principale, une pile est créée, initialisée, et alimentée avec trois éléments de test, puis affichée. #include #include #include // Structure d'un élément de la pile typedef struct Element {

69

char donnee[50]; // Changer la taille selon vos besoins struct Element* suivant; } Element; // Structure de la pile typedef struct Pile { Element* debut; int taille; } Pile; // Prototypes des fonctions void initialiserPile(Pile* tas); void empiler(Pile* tas, const char* donnee); void affiche(Pile* tas); int main() { // Création d'une pile Pile maPile; initialiserPile(&maPile); // Empilement de quelques empiler(&maPile, "Element empiler(&maPile, "Element empiler(&maPile, "Element // Affichage de la pile affiche(&maPile);

éléments de test 1"); 2"); 3");

return 0; } // Initialisation d'une pile vide void initialiserPile(Pile* tas) { tas->debut = NULL; tas->taille = 0; } // Fonction pour empiler un élément void empiler(Pile* tas, const char* donnee) { Element* nouvelElement = (Element*)malloc(sizeof(Element)); if (nouvelElement == NULL) { // Gestion d'erreur si l'allocation échoue fprintf(stderr, "Erreur d'allocation de mémoire\n"); exit(EXIT_FAILURE); } strcpy(nouvelElement->donnee, donnee); nouvelElement->suivant = tas->debut; tas->debut = nouvelElement; tas->taille++; } // Fonction pour afficher les éléments de la pile void affiche(Pile* tas) { Element* courant; int i; courant = tas->debut; for (i = 0; i < tas->taille; ++i) { printf("\t\t%s\n", courant->donnee); courant = courant->suivant; } }

Tableau Comparatif Et Résumé Entre La File Et La Pile 70

3.6 LISTE DOUBLEMENT CHAINEE 3.6.1 INTRODUCTION Après avoir vu les listes simplement chaînées, pour cette seconde partie, nous allons nous attarder sur les listes doublement chaînées. Une liste doublement chaînée permet de gagner en complexité sur l'insertion et la suppression par rapport à la liste simplement chaînée, en plus de permettre un parcours des éléments à l'envers. Mais on utilise un pointeur supplémentaire par élément. Il faut donc maintenir cohérentes deux fois plus de variables que dans une liste simplement chaînée. 3.6.1.1 DEFINITION Une liste doublement chaînée est une liste chaînée dans laquelle on peut accéder à l’élément prédécesseur. C’est une structure de données qui représente une séquence d'éléments. Chaque élément de la liste contient deux pointeurs : un vers l'élément suivant et un vers l'élément précédent. Ici, chaque nœud possède des liens vers le nœud précédant et suivant.

71

Les nœuds dans les listes doublement chaînée se composent de trois éléments : l'un contient les données et deux autres sont des pointeurs du nœud suivant et précédent. Ces deux pointeurs aident à avancer ou à reculer à partir d'un nœud particulier. La différence entre une liste doublement chainée et une liste simplement chainée est donc que, dans une liste doublement chainée, chaque élément connait l'élément précédent et l'élément suivant (la liaison entre les éléments se fait grâce à deux pointeurs (un qui pointe vers l'élément précédent et un qui pointe vers l'élément suivant). En bref, le déplacement se fait dans les deux directions, du premier vers le dernier élément et/ou du dernier vers le premier élément. Cela permet de simplifier l'insertion ou la suppression d'un élément donné, ainsi que le parcours en sens inverse.

NB : Chaque liste chaînée est pourvue d'un nœud de tête et d'un nœud de queue. Le nœud principal, également appelé nœud de tête, ne possède pas de nœud « précédent » (pointeur précédent), tandis que le nœud de queue n'est pas relié à un nœud « suivant ». Quelques termes essentiels relatifs à une liste chaînée double sont les suivants : ▪

Précédant : Chaque nœud est relié à son nœud précédent par le biais d'un pointeur ou d'un lien. Ce lien est utilisé pour établir une connexion vers le nœud situé avant lui dans la séquence.

▪

Suivant : Chaque nœud est relié à son nœud suivant par le biais d'un pointeur ou d'un lien. Ce mécanisme permet d'établir une liaison vers le nœud suivant dans la séquence.

▪

Données : Ce terme fait référence à l'espace réservé dans un nœud destiné au stockage d'informations. Les « données » peuvent englober diverses structures de données internes, telles qu'une chaîne de caractères, un dictionnaire, un ensemble, un hashmap, etc. Ainsi, les « Données » peuvent contenir des structures de données complexes.

Exemple d'une liste doublement chainée contenant les éléments 1, 2, 3, 4 et 5 : [1] -> [2] -> [3] -> [4] -> [5] Dans cet exemple, chaque élément contient un pointeur vers l'élément suivant. Le premier élément, [1], pointe sur le deuxième élément, [2]. Le deuxième élément, [2], pointe sur le troisième élément, [3], et ainsi de suite. 72

L'élément [5], le dernier de la liste, pointe sur NULL. Cela signifie qu'il n'y a pas d'élément suivant. Les opérations courantes sur les listes doublement chainées sont les suivantes : ▪

Insertion : pour insérer un élément à la fin de la liste, il suffit de créer un nouvel élément et de pointer son pointeur suivant vers l'élément suivant de la liste.

▪

Suppression : pour supprimer un élément de la liste, il suffit de modifier les pointeurs des éléments précédents et suivants de l'élément à supprimer.

▪

Parcours : pour parcourir la liste, il suffit de commencer par l'élément de tête et de suivre le pointeur suivant de chaque élément jusqu'à ce que l'on atteigne NULL.

Les listes doublement chainées sont une structure de données versatile qui peut être utilisée dans de nombreux contextes. Elles sont notamment utilisées dans les algorithmes de tri, de recherche et de parcours.

3.6.2 LA CONSTRUCTION DU PROTOTYPE D'UN ELEMENT DE LA LISTE Pour définir un élément de la liste le type struct sera utilisé. L'élément de la liste contiendra un champ donnee, un pointeur precedent et un pointeur suivant. Les pointeurs precedent et suivant doivent être du même type que l'élément, sinon ils ne pourront pas pointer vers un élément de la liste. Le pointeur "precedent" permettra l'accès vers l'élément précédent tandis que le pointeur suivant permettra l'accès vers le prochain élément. Le code ci-dessous définit une structure de données `dl_ElementListe`, représentant un élément d'une liste doublement chaînée. Chaque élément contient un pointeur vers une chaîne de caractères (`donnee`), ainsi que deux pointeurs vers des éléments adjacents dans la liste, l'un vers l'élément précédent (`precedent`) et l'autre vers l'élément suivant (`suivant`). La structure est ensuite renommée en tant que `dl_Element` à l'aide du typedef, permettant ainsi de déclarer des variables de type `dl_Element` plus facilement. typedef struct dl_ElementListe { char *donnee; struct dl_ElementListe *precedent; struct dl_ElementListe *suivant; }dl_Element;

Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments : le premier élément, le dernier élément, le nombre d'éléments. Pour réaliser cela une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées). Le code suivant définit une structure de données `dl_ListeRepere`, qui représente une liste doublement chaînée repérée. La structure comporte trois membres : `debut` et `fin` sont des pointeurs vers le premier et le dernier élément de la liste, respectivement, et `taille` est un 73

entier représentant le nombre d'éléments dans la liste. Cette structure fournit un moyen de suivre les extrémités de la liste et de maintenir la taille de la liste de manière efficace. La structure est renommée en tant que `dl_Liste` à l'aide du typedef pour faciliter la déclaration de variables de ce type. typedef struct dl_ListeRepere { dl_Element *debut; dl_Element *fin; int taille; }dl_Liste;

Le pointeur debut contiendra l'adresse du premier élément de la liste. Le pointeur fin contiendra l'adresse du dernier élément de la liste. La variable taille contient le nombre d'éléments. Quelle que soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément. Le champ taille contiendra le nombre d'éléments de la liste quelle que soit l'opération effectuée sur la liste.

3.6.3 OPERATIONS DE LISTE DOUBLEMENT CHAINEE Les opérations d'une liste doublement chaînée incluent l'ajout et la suppression de nœuds, l'insertion et la suppression de nœuds et le parcours de la liste chaînée de haut en bas. Pour l'insertion ainsi que pour la suppression, une seule fonction est largement suffisante si elle est bien conçue en fonction des besoins. 3.6.3.1 INITIALISATION Prototype de la procédure : void initialisation (Liste *liste); Cette opération doit être faite avant toute autre opération sur la liste. Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0. Le code ci-dessous définit une procédure `initialisation`, prenant en paramètre un pointeur vers une structure de type `Liste`. La fonction initialise les membres de la structure en mettant à zéro les pointeurs `debut` et `fin`, les faisant pointer vers NULL, et en attribuant la valeur 0 à la variable `taille`. En d'autres termes, la procédure prépare la liste pour une utilisation ultérieure en la vidant et en réinitialisant sa taille à zéro. void initialisation (Liste *liste){ liste->debut = NULL; liste->fin = NULL; liste->taille = 0; }

3.6.3.2 INSERTION D'UN ELEMENT DANS LA LISTE ALGORITHME D'INSERTION ET DE SAUVEGARDE DES ELEMENTS : 74

▪

Déclaration D'élément(S) A Insérer

▪

Allocation De La Mémoire Pour Le Nouvel Elément

▪

Remplir Le Contenu Du Champ De Données

▪

Mettre A Jour Les Pointeurs Vers L'élément Précédent Et L'élément Suivant

▪

Mettre A Jour Les Pointeurs Vers Le 1er Et Le Dernier Elément Si Nécessaire.

▪

Cas Particulier : Dans Une Liste Avec Un Seul Elément, Le 1er Est En Même Temps Le Dernier.

▪

Mettre A Jour La Taille De La Liste

Pour ajouter un élément dans la liste il y a plusieurs situations : 1. Insertion dans une liste vide 2. Insertion au début de la liste 3. Insertion à la fin de la liste 4. Insertion avant un élément 5. Insertion après un élément 3.6.3.2.1 INSERTION DANS UNE LISTE VIDE Prototype de la fonction : int ins_dans_liste_vide (dl_Liste * liste, char *donnee); La fonction renvoie -1 en cas d'échec sinon elle renvoie 0. ❖ Étapes ▪

Allocation De La Mémoire Pour Le Nouvel Elément

▪

Remplir Le Champ De Données Du Nouvel Elément

▪

Le Pointeur Precedent Du Nouvel Elément Pointera Vers Null (Vu Que L'insertion Est Faite Dans Une Liste Vide On Utilise L'adresse Du Pointeur Debut Qui Vaut Null)

▪

Le Pointeur Suivant Du Nouvel Elément Pointera Vers Null (Vu Que L'insertion Est Faite Dans Une Liste Vide On Utilise L'adresse Du Pointeur Fin Qui Vaut Null)

▪

Les Pointeurs Debut Et Fin Pointeront Vers Le Nouvel Elément

▪

La Taille Est Mise A Jour

75

LA FONCTION

Le code ci-dessous définit une fonction `insertion_dans_liste_vide`, qui insère une nouvelle donnée dans une liste doublement chaînée vide. La fonction alloue un nouvel élément de liste, copie la donnée fournie, met à jour les pointeurs `precedent` et `suivant` pour indiquer le début et la fin de la liste, incrémente la taille de la liste, puis renvoie 0 pour signaler une insertion réussie. En cas d'échec de l'allocation mémoire, la fonction renvoie -1. Notez que la fonction utilise une fonction `alloc` pour allouer de la mémoire, mais les détails de cette fonction ne sont pas fournis dans le code donné. int insertion_dans_liste_vide (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = liste->debut; nouveau_element->suivant = liste->fin; liste->debut = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; }

3.6.3.2.2 INSERTION AU DEBUT DE LA LISTE Prototype de la fonction : int ins_debut_liste (dl_Liste * liste, char *donnee); La fonction renvoie -1 en cas d'échec sinon elle renvoie 0. ❖ Étapes ▪

Allocation De La Mémoire Pour Le Nouvel Elément

▪

Remplir Le Champ De Données Du Nouvel Elément

▪

Le Pointeur Precedent Du Nouvel Elément Pointe Vers Null

▪

Le Pointeur Suivant Du Nouvel Elément Pointe Vers Le 1er Elément

▪

Le Pointeur Precedent Du 1er Elément Pointe Vers Le Nouvel Elément 76

▪

Le Pointeur Debut Pointe Vers Le Nouvel Elément

▪

Le Pointeur Fin Ne Change Pas

▪

La Taille Est Incrémentée

LA FONCTION

Le code suivant présente la fonction `ins_debut_liste` qui vise à insérer une nouvelle donnée au début d'une liste doublement chaînée. La fonction alloue un nouvel élément de liste, copie la donnée fournie, met à jour les pointeurs `precedent` et `suivant` pour refléter la nouvelle configuration de la liste, incrémente la taille de la liste, puis renvoie 0 pour indiquer une insertion réussie. En cas d'échec de l'allocation mémoire, la fonction renvoie -1. Notons que la fonction utilise une fonction `alloc` pour allouer de la mémoire, mais les détails de cette fonction ne sont pas inclus dans le code fourni. Il est important de souligner que le code peut provoquer des erreurs si la liste est vide (le pointeur `liste->debut` est NULL), car la tentative d'accès à `liste->debut->precedent` dans ce cas peut entraîner un comportement indéfini. int ins_debut_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = NULL; nouveau_element->suivant = liste->debut; liste->debut->precedent = nouveau_element;

77

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

3.6.3.2.3 INSERTION A LA FIN DE LA LISTE Prototype de la fonction : int ins_fin_liste (dl_Liste * liste, char *donnee); La fonction renvoie -1 en cas d'échec sinon elle renvoie 0. ❖ Étapes ▪

Allocation De La Mémoire Pour Le Nouvel Elément

▪

Remplir Le Champ De Données Du Nouvel Elément

▪

Le Pointeur Suivant Du Nouvel Elément Pointe Vers Null

▪

Le Pointeur Precedent Du Nouvel Elément Pointe Vers Le Dernier Elément (C'est Le Pointeur Fin Qui Contient Pour L'instant Son Adresse

▪

Le Pointeur Suivant Du Dernier Elément Va Pointer Vers Le Nouvel Elément

▪

Le Pointeur Fin Pointe Vers Le Nouvel Elément

▪

Le Pointeur Debut Ne Change Pas

▪

La Taille Est Incrémentée

LA FONCTION

Le code ci-dessous implémente une fonction `ins_fin_liste`, conçue pour insérer une nouvelle donnée à la fin d'une liste doublement chaînée. La fonction alloue un nouvel élément de liste, 78

copie la donnée fournie, met à jour les pointeurs `precedent` et `suivant` pour refléter la nouvelle configuration de la liste, incrémente la taille de la liste, puis renvoie 0 pour signaler une insertion réussie. En cas d'échec de l'allocation mémoire, la fonction renvoie -1. Il est important de noter que le code peut entraîner des erreurs si la liste est vide (le pointeur `liste>fin` est NULL), car la tentative d'accès à `liste->fin->suivant` dans ce cas peut provoquer un comportement indéfini. De plus, le fonctionnement de la fonction dépend de la disponibilité d'une fonction `alloc` pour allouer de la mémoire, mais les détails de cette fonction ne sont pas inclus dans le code fourni. int ins_fin_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = NULL; nouveau_element->precedent = liste->fin; liste->fin->suivant = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; }

3.6.3.2.4 INSERTION AVANT UN ELEMENT DE LA LISTE Prototype de la fonction : int ins_avant (dl_Liste * liste, char *donnee, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0. L'insertion s'effectuera avant une certaine position passée en argument à la fonction. La position indiquée ne doit pas être ni le 1er ni le dernier élément. Dans ce cas il faut utiliser les fonctions d'insertion au début et/ou à la fin de la liste. ❖ ÉTAPES ▪

Allocation De La Mémoire Pour Le Nouvel Elément

▪

Remplir Le Champ De Données Du Nouvel Elément

▪

Choisir Une Position Dans La Liste (L'insertion Se Fera Après La Position Choisie)

▪

Le Pointeur Suivant Du Nouvel Elément Pointe Vers L'élément Courant.

▪

Le Pointeur Precedent Du Nouvel Elément Pointe Vers L'adresse Sur La Quelle Pointe Le Pointeur Precedent D'élément Courant. (Une Explication Un Peu Tordue Avec L'espoir Que L'image Vous Eclaira ;-)

▪

Le Pointeur Suivant De L'élément Qui Précède L'élément Courant Pointera Vers Le Nouveau Elément

▪

Le Pointeur Precedent D'élément Courant Pointe Vers Le Nouvel Elément

▪

Le Pointeurs Fin Ne Change Pas

▪

Le Pointeur Debut Change Si Et Seulement La Position Choisie Est La Position1 79

▪

La Taille Est Incrémentée D'une Unité

LA FONCTION

Le code suivant présente une fonction nommée `ins_avant`, destinée à insérer une nouvelle donnée avant la position spécifiée dans une liste doublement chaînée. La fonction commence par allouer un nouvel élément de liste, puis copie la donnée fournie. Elle utilise une boucle for pour atteindre l'élément à la position indiquée (`pos`). Ensuite, elle met à jour les pointeurs `precedent` et `suivant` pour refléter l'insertion du nouvel élément. Si l'élément à la position spécifiée a un prédécesseur, le pointeur `suivant` de ce prédécesseur est ajusté pour pointer vers le nouvel élément. Si l'élément à la position spécifiée n'a pas de prédécesseur (c'est-à-dire, il est le premier de la liste), le pointeur `debut` de la liste est mis à jour pour pointer vers le nouvel élément. Enfin, la taille de la liste est augmentée, et la 80

fonction renvoie 0 pour indiquer une insertion réussie. En cas d'échec de l'allocation mémoire, la fonction renvoie -1. Comme dans les exemples précédents, le fonctionnement de la fonction dépend de l'existence d'une fonction `alloc` pour allouer de la mémoire, mais les détails de cette fonction ne sont pas fournis dans le code donné. int ins_avant (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant; nouveau_element-> precedent = courant->precedent; if(courant->precedent == NULL) liste->debut = nouveau_element; else courant->precedent->suivant = nouveau_element; courant->precedent = nouveau_element; liste->taille++; return 0; }

3.6.3.2.5 INSERTION APRES UN ELEMENT DE LA LISTE Prototype de la fonction : int ins_apres (dl_Liste * liste, char *donnee, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0. L'insertion s'effectuera après une certaine position passée en argument à la fonction. La position indiquée ne doit pas être le dernier élément. Dans ce cas il faut utiliser la fonction d'insertion à la fin de la liste. ❖ ÉTAPES ▪

Allocation de la mémoire pour le nouvel élément

▪

Remplir Le Champ De Données Du Nouvel Elément

▪

Choisir Une Position Dans La Liste (L'insertion Se Fera Après La Position Choisie)

▪

Le Pointeur Suivant Du Nouvel Elément Pointe Vers L'adresse Sur La Quelle Pointe Le Pointeur Suivant D'élément Courant (Voir L'image)

▪

Le Pointeur Precedent Du Nouvel Elément Pointe Vers L'élément Courant.

▪

Le Pointeur Precedent De L'élément Qui Succède L'élément Courant Pointera Vers Le Nouveau Elément

▪

Le Pointeur Suivant D'élément Courant Pointe Vers Le Nouvel Elément

▪

Le Pointeurs Debut Ne Change Pas

▪

Le Pointeur Fin Change Si Et Seulement La Position Choisie Est La Position Du Dernier Elément (La Taille De Liste) 81

▪

La Taille Est Incrémentée D'une Unité

LA FONCTION

Le code suivant fournit une fonction "ins_apres" qui prend en paramètres une liste doublement chaînée (dl_Liste), une donnée de type chaîne de caractères (donnee), et une position (pos). La fonction insère un nouvel élément contenant la donnée fournie après l'élément situé à la position spécifiée dans la liste. Le code commence par allouer de la mémoire pour le nouvel élément et renvoie -1 en cas d'échec de l'allocation. Ensuite, il copie la donnée dans le champ correspondant du nouvel élément. En utilisant une boucle for, la fonction parcourt la liste jusqu'à atteindre la position spécifiée. Ensuite, elle ajuste les pointeurs pour insérer le nouvel élément après l'élément à la position indiquée. Si l'élément à la position spécifiée est le dernier élément de la liste, le pointeur "fin" de la liste est mis à jour. Finalement, la taille de la liste est augmentée de 1, et la fonction renvoie 0 pour indiquer le succès de l'insertion.

82

int ins_apres (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant->suivant;5 nouveau_element->precedent = courant; if(courant->suivant == NULL) liste->fin = nouveau_element; else courant->suivant->precedent = nouveau_element; courant->suivant = nouveau_element; liste->taille++; return 0; }

3.6.3.2.6 SUPPRESSION D’UN ELEMENT DE LA LISTE L'algorithme de suppression d'un élément de la liste utilise un pointeur temporaire pour conserver l'adresse de l'élément à supprimer. L'emplacement de l'élément peut être n'importe où dans la liste. Comparé aux listes simplement chaînées, où la suppression est limitée à un élément spécifique, les listes doublement chaînées sont plus flexibles grâce à leurs deux pointeurs qui permettent de suivre les éléments tant en amont qu'en aval. Les étapes générales de suppression comprennent la libération de la mémoire occupée par l'élément supprimé et la mise à jour de la taille de la liste. Les différentes situations de suppression sont les suivantes : 1. Suppression au début de la liste 2. Suppression à la fin de la liste 3. Suppression avant un élément 4. Suppression après un élément 5. Suppression d'un élément Toutefois, la suppression au début et à la fin de la liste doublement chaînées ainsi qu'avant ou après un élément revient à la suppression à la position 0 (zéro) ou à la position N (N = nombre d'éléments de la liste) ou ailleurs dans la liste. Dans le cas des listes doublement chaînées la suppression à n'importe quelle position ne pose pas des problèmes grâce aux pointeurs précédant et suivant, qui permettent de garder la liaison entre les éléments de la liste. C'est la raison pour laquelle nous allons créer une seule fonction.

5

La ligne "courant->suivant->precedent = nouveau_element;" est utilisée pour mettre à jour les liens précédents lors de l'insertion d'un nouvel élément dans une liste doublement chaînée. Cela assure la continuité des liens dans la structure de la liste.

83

▪

Si Nous Voulons Supprimer L'élément Au Début De La Liste Nous Choisirons La Position Zéro

▪

Si Nous Voulons Supprimer L'élément A La Fin De La Liste Nous Choisirons La Position N (Le Nombre D'éléments)

▪

Si Nous Désirons Supprimer Un Elément Quelconque Alors On Choisit Sa Position Dans La Liste

SUPPRESSION DANS LA LISTE Prototype de la fonction : int supp(dl_Liste *liste, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0. Nous distinguons plusieurs situations : ▪

Suppression A La Position 1 Dans Une Liste Avec Un Seul Elément

▪

Suppression A La Position 1 Dans Une Liste Avec Plusieurs Eléments

▪

Suppression A La Dernière Position (Le Dernier Elément)

▪

Suppression Ailleurs Dans La Liste A Une Certaine Position

La suppression dans une liste vide n'a pas de sens. ❖ ÉTAPES ▪

La Position Choisie Est 1 (Le Cas De Suppression Du 1er Elément De La Liste)

▪

Le Pointeur Supp_Element Contiendra L'adresse Du 1er Elément

▪

Le Pointeur Debut Contiendra L'adresse Contenue Par Le Pointeur Suivant Du 1er Elément Que Nous Voulons Supprimer (Si Ce Pointeur Vaut Null Alors Nous Mettons A Jour Le Pointeur Fin Puisqu'on Est Dans Le Cas D'une Liste Avec Un Seul Elément, Sinon Nous Faisons Pointer Le Pointeur Precedent Du 2ème Elément Vers Null)

84

▪

La Position Choisie Est Egale Avec Le Nombre D'éléments De La Liste

▪

Le Pointeur Supp_Element Contiendra L'adresse Du Dernier Elément

▪

Nous Faisons Pointer Le Pointeur Suivant De L'avant Dernier Elément (C'est L'élément Vers Le Quel Pointe Le Pointeur De Dernier Elément), Vers Null

▪

Nous Mettons A Jour Le Pointeur Fin

▪

La Position Choisie Est Aléatoire Dans La Liste

▪

Le Pointeur Supp_Element Contiendra L'adresse De L'élément A Supprimer

▪

Le Pointeur Suivant D'élément Qui Précède L'élément A Supprimer Pointe Vers L'adresse Contenu Par Le Pointeur Suivant D'élément A Supprimer

▪

Le Pointeur Precedent D'élément Qui Succède L'élément A Supprimer Pointe Vers L'adresse Contenu Par Le Pointeur Precedent D'élément A Supprimer. 85

▪

La Taille De La Liste Sera Décrémentée D'un Elément

LA FONCTION Le code ci-dessous fournit une fonction "supp" qui prend en paramètres une liste doublement chaînée (dl_Liste) et la position d'un élément à supprimer (pos). La fonction commence par vérifier si la taille de la liste est nulle, renvoyant -1 en cas de liste vide. Ensuite, elle gère trois cas de suppression d'élément en fonction de la position spécifiée : suppression du premier élément, suppression du dernier élément, et suppression d'un élément ailleurs dans la liste. La fonction ajuste les pointeurs de début et de fin de la liste en conséquence. Après la suppression de l'élément, elle libère la mémoire occupée par la donnée associée à l'élément supprimé, puis libère la mémoire de l'élément lui-même. Enfin, la taille de la liste est décrémentée, et la fonction renvoie 0 pour indiquer le succès de la suppression. Il convient de noter une possible erreur de syntaxe dans le code : l'utilisation du double égal (==) au lieu de l'opérateur d'affectation (=) lors de la mise à jour du pointeur "precedent" dans la branche "else" après la suppression du premier élément. int supp(dl_Liste *liste, int pos){ int i; dl_Element *supp_element,*courant; if(liste->taille == 0) return -1; if(pos == 1){ /* suppresion de 1er élément */ supp_element = liste->debut; liste->debut = liste->debut->suivant; if(liste->debut == NULL) liste->fin = NULL; else

86

liste->debut->precedent == NULL; }else if(pos == liste->taille){ /* suppression du dernier élément */ supp_element = liste->fin; liste->fin->precedent->suivant = NULL; liste->fin = liste->fin->precedent; }else { /* suppression ailleurs */ courant = liste->debut; for(i=1;isuivant; supp_element = courant; courant->precedent->suivant = courant->suivant; courant->suivant->precedent = courant->precedent; } free(supp_element->donnee); free(supp_element); liste->taille--; return 0; }

3.6.3.2.7 AFFICHAGE DE LA LISTE Pour afficher l'intégralité de la liste, deux approches peuvent être adoptées : se positionner soit au début, soit à la fin de la liste, en fonction du pointeur de début ou de fin. Ensuite, en utilisant les pointeurs suivant ou précédent de chaque élément, la liste est parcourue soit du premier au dernier élément, soit du dernier au premier élément. La condition d'arrêt du parcours est déterminée par le pointeur suivant du dernier élément, qui prend la valeur NULL lors de la lecture du début vers la fin de la liste. Dans le cas d'une lecture de la fin vers le début de la liste, la condition d'arrêt est donnée par le pointeur précédent du premier élément, qui prend la valeur NULL. LES PROCEDURES Les deux procédures suivantes, "affiche()" et "affiche_inv()", sont destinées à l'affichage des éléments d'une liste doublement chaînée (dl_Liste) dans l'ordre direct et inverse, respectivement. La fonction "affiche" parcourt la liste en partant du premier élément (debut) et imprime les données de chaque élément séparé par des espaces, encadrées par des crochets. La fonction "affiche_inv" parcourt la liste en partant du dernier élément (fin) et imprime les données de chaque élément suivi de deux points, également encadrées par des crochets. Ces fonctions utilisent une boucle while pour itérer à travers les éléments de la liste, en mettant à jour le pointeur courant selon la direction de l'affichage. Les affichages sont suivis d'un saut de ligne pour améliorer la lisibilité. void affiche(dl_Liste *liste){ /* affichage en avançant */ dl_Element *courant; courant = liste->debut; /* point du départ le 1er élément */ printf("[ "); while(courant != NULL){ printf("%s ",courant->donnee); courant = courant->suivant; }

87

printf("]\n"); } void affiche_inv(dl_Liste *liste){ /* affichage en reculant */ dl_Element *courant; courant = liste->fin; /* point du départ le dernier élément */ printf("[ "); while(courant != NULL){ printf("%s : ",courant->donnee); courant = courant->precedent; } printf("]\n"); }

3.6.3.2.8 DESTRUCTION DE LA LISTE Pour détruire l'intégralité de la liste, on a opté pour la suppression à la position 1 tant que la taille de la liste est supérieure à zéro. Le code définit par la procédure `detruire()` ci-dessous utilise une liste doublement chaînée (`dl_Liste`). Elle utilise une boucle pour supprimer tous les éléments de la liste jusqu'à ce que la taille de la liste (`liste->taille`) soit réduite à zéro. La fonction `supp` est probablement une fonction qui supprime un élément de la liste à une position donnée. void detruire(dl_Liste *liste){ while(liste->taille > 0) supp(liste,1); }

EXEMPLE COMPLET DE LA LISTE DOUBLEMENT CHAINEE 1. PREMIERE PARTIE La première partie du code ci-dessous définit des opérations pour l'initialisation, l'insertion, la suppression, l'affichage et la destruction d'une liste doublement chaînée (dl_Liste). /* initialisation de la liste */ void initialisation (dl_Liste * liste); dl_Element *alloc (dl_Element * nouveau_element); /* INSERTION */ int ins_dans_liste_vide (dl_Liste * liste, char *donnee); int ins_debut_liste (dl_Liste * liste, char *donnee); int ins_fin_liste (dl_Liste * liste, char *donnee); int ins_apres (dl_Liste * liste, char *donnee, int pos); int ins_avant (dl_Liste * liste, char *donnee, int pos); /* SUPPRESSION */ int supp(dl_Liste *liste, int pos); void affiche (dl_Liste * liste); /**************************/ void affiche_inv (dl_Liste * liste); void detruire (dl_Liste * liste); /* -------- FIN liste.h --------- */

88

2. DEUXIEME PARTIE La seconde partie du code regroupe toutes les procédures et fonctions vues dans cette partie du cours sur les listes doublement chainées. Il s’agit des fonctions et procédures pour l'initialisation, l'insertion, la suppression, l'affichage, et la destruction d'une liste doublement chaînée, avec une fonction de menu interactif pour choisir les opérations. /***************************\ * dliste_function.h * \***************************/ void initialisation (dl_Liste * liste){ liste->debut = NULL; liste->fin = NULL; liste->taille = 0; } int insertion_dans_liste_vide (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = NULL; nouveau_element->suivant = NULL; liste->debut = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; } int ins_debut_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = NULL; nouveau_element->suivant = liste->debut; liste->debut->precedent = nouveau_element; liste->debut = nouveau_element; liste->taille++; return 0; } int ins_fin_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = NULL; nouveau_element->precedent = liste->fin; liste->fin->suivant = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; } int ins_apres (dl_Liste * liste, char *donnee, int pos){

89

int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant->suivant; nouveau_element->precedent = courant; if(courant->suivant == NULL) liste->fin = nouveau_element; else courant->suivant->precedent = nouveau_element; courant->suivant = nouveau_element; liste->taille++; return 0; } int ins_avant (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant; nouveau_element-> precedent = courant->precedent; if(courant->precedent == NULL) liste->debut = nouveau_element; else courant->precedent->suivant = nouveau_element; courant->precedent = nouveau_element; liste->taille++; return 0; } int supp(dl_Liste *liste, int pos){ int i; dl_Element *supp_element,*courant; if(liste->taille == 0) return -1; if(pos == 1){ /* suppresion de 1er élément */ supp_element = liste->debut; liste->debut = liste->debut->suivant; if(liste->debut == NULL) liste->fin = NULL; else liste->debut->precedent == NULL; }else if(pos == liste->taille){ /* suppression du dernier élément */ supp_element = liste->fin; liste->fin->precedent->suivant = NULL; liste->fin = liste->fin->precedent;

90

}else { /* suppression ailleurs */ courant = liste->debut; for(i=1;isuivant; supp_element = courant; courant->precedent->suivant = courant->suivant; courant->suivant->precedent = courant->precedent; } free(supp_element->donnee); free(supp_element); liste->taille--; return 0; } void detruire(dl_Liste *liste){ while(liste->taille > 0) supp(liste,1); } dl_Element *alloc (dl_Element * nouveau_element){ if ((nouveau_element = (dl_Element *) malloc (sizeof (dl_Element))) == NULL) return NULL; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return NULL; return nouveau_element; } int menu (dl_Liste *liste){ int choix; if (liste->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 à la position specifie\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; } int supp(dl_Liste *liste, int pos); void affiche(dl_Liste *liste){ dl_Element *courant; courant = liste->debut; printf("[ "); while(courant != NULL){ printf("%s ",courant->donnee);

91

courant = courant->suivant; } printf("]\n"); } void affiche_inv(dl_Liste *liste){ dl_Element *courant; courant = liste->fin; while(courant != NULL){ printf("%s : ",courant->donnee); courant = courant->precedent; } printf("\n"); } /* -------- FIN dliste_function.h --------- */

3. TROISIEME PARTIE Le code de la dernière partie ci-dessous, utilise une liste doublement chaînée (`dl_Liste`) avec des opérations d'initialisation, d'insertion, de suppression, d'affichage, et de destruction. La fonction `menu` permet à l'utilisateur de choisir différentes opérations à effectuer sur la liste en fonction de son état. \**********************\ * dliste.c * \**********************/ #include #include #include #include "dliste.h" #include "dliste_function.h" int main (void) { int choix = 0,pos; char *donnee; donnee = malloc(50); dl_Liste *liste; dl_Element *pilote = NULL; liste = (dl_Liste *) malloc (sizeof(dl_Liste)); initialisation(liste); while(choix != 7){ choix = menu(liste); switch(choix){ case 1: printf("Entrez un element : "); scanf("%s",donnee); getchar(); if(liste->taille == 0) insertion_dans_liste_vide(liste,donnee); else ins_debut_liste (liste, donnee); printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee);

92

affiche(liste); break; case 2: printf("Entrez un element : "); scanf("%s",donnee); getchar(); ins_fin_liste (liste, donnee); printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 3: if(liste->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 > liste->taille); getchar(); ins_avant(liste,donnee,pos); printf("%d elements: deb=%s fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 4: if(liste->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 > liste->taille); getchar(); ins_apres(liste,donnee,pos); printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 5: do{ printf("Entrez la position : "); scanf("%d",&pos); }while (pos < 1 || pos > liste->taille); getchar(); supp(liste,pos); if(liste->taille != 0)

93

printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); else printf("liste vide : %d elements",liste->taille); affiche(liste); break; case 6: detruire(liste); printf("la liste a ete detruite : %d elements\n",liste->taille); break; } } return 0; } /* -------- FIN dliste.c --------- */

3.7 COMPLEXITE DES OPERATIONS SUR LES LISTES DOUBLEMENT CHAINEES La table récapitulative ci-dessous présente la complexité des principales opérations effectuées sur une liste doublement chaînée. Pour la recherche au sein de la liste, la complexité demeure linéaire (O(N)), nécessitant un parcours séquentiel des éléments. En revanche, les opérations de recherche de l'élément suivant ou précédent, ainsi que les opérations d'insertion en début, milieu ou fin de liste, affichent une complexité constante (O(1)). Cette caractéristique souligne l'efficacité de la liste doublement chaînée pour les opérations d'insertion et de suppression, où

les références aux éléments suivants et précédents facilitent des modifications rapides. Ainsi, la structure de la liste doublement chaînée est particulièrement avantageuse dans les scénarios où des opérations dynamiques d'insertion et de suppression sont fréquemment réalisées, même si la recherche linéaire reste une contrainte à prendre en compte.

3.8 LISTE POLYNOMIALES La gestion des polynômes avec les listes chaînées consiste à représenter un polynôme en utilisant une structure de données dynamique. Chaque terme du polynôme est stocké dans un 94

nœud de la liste chaînée, où chaque nœud contient le coefficient et l'exposant du terme, ainsi qu'un pointeur vers le prochain nœud. Cette approche permet une flexibilité accrue dans la manipulation des polynômes, car l'ajout, la suppression et la modification de termes peuvent être réalisés efficacement en modifiant les liens entre les nœuds. Les opérations mathématiques telles que l'addition, la soustraction et la multiplication de polynômes peuvent également être implémentées de manière efficace en parcourant les listes chaînées correspondantes. Ainsi, la gestion des polynômes avec les listes chaînées offre une solution efficace et extensible pour manipuler des structures polynomiales complexes de manière dynamique.

3.8.1 POLYNOME ET LISTE CHAINEE 3.8.1.1 POLYNOME Un polynôme p(x) est une expression algébrique en variable x qui se présente sous la forme (axn + bxn-1 + …. + jx+ k) , où a, b, c …., k appartiennent à la catégorie des nombres réels et 'n' est un entier non négatif, appelé le degré du polynôme. Il est composé de plusieurs termes, appelés monômes, qui sont reliés par des opérations d’addition ou de soustraction. Par exemple, le polynôme 3x2−5x+2 est formé de trois monômes : 3x2, −5x et 2. Une caractéristique importante des polynômes est que chaque terme de l'expression polynomiale se compose de deux parties : ▪

Le Coefficient

▪

L'exposant

Exemple : Dans 10x2 + 26x, les coefficients sont 10 et 26, et les exposants sont 2 et 1. Points à garder à l'esprit lors de la manipulation des polynômes : Le signe de chaque coefficient et exposant est stocké dans le coefficient et l'exposant luimême. Des termes supplémentaires ayant le même exposant sont possibles. L'allocation de stockage pour chaque terme dans le polynôme doit être effectuée dans l'ordre

croissant et décroissant de leurs exposants. 3.8.1.2 LISTE CHAINEE Une liste chainée est une structure de données qui permet de stocker une séquence d’éléments, appelés nœuds, de manière dynamique. Chaque nœud contient une valeur et un pointeur vers le nœud suivant dans la liste. Par exemple, la liste chainée [1 -> 2 -> 3 -> NULL] est formée de trois nœuds : [1 ->], [2 ->] et [3 ->]. On peut représenter un polynôme par une liste chainée, en associant à chaque nœud un monôme. Le coefficient et la puissance du monôme sont stockés dans la valeur du nœud, et 95

le pointeur vers le nœud suivant permet de passer au terme suivant du polynôme. Les monômes sont ordonnés par ordre croissant de puissance dans la liste. Par exemple, le polynôme 3x2−5x+2peut être représenté par la liste chainée [(2, 0) -> (-5, 1) -> (3, 2) -> NULL], où chaque paire (a, b) représente le monôme axb. La gestion des polynômes avec les listes chainées consiste à définir des opérations sur les polynômes, comme la création, l’affichage, l’évaluation, la dérivation, la somme, le produit, etc., en utilisant les opérations sur les listes chainées, comme l’allocation, la libération, l’insertion, la suppression, la recherche, etc. Le figure ci-dessous illustre un algorithme combinatoire utilisé pour additionner deux polynômes représentés par des listes chaînées de coefficients et de puissances. L'algorithme parcourt les deux listes terme par terme, additionne les coefficients correspondants, et stocke le résultat dans une nouvelle liste chaînée. La figure est divisée en deux parties, décrivant les étapes initiales (lecture des données et initialisation des variables) et les étapes finales (addition des coefficients et stockage du résultat). Les blocs spécifiques comprennent la lecture des données, l'initialisation des variables, l'addition des coefficients, et le stockage du résultat dans une nouvelle liste chaînée. Au final, l'algorithme réalise une addition polynomiale en suivant un processus clairement défini.

3.8.1.3 REPRESENTATION DES POLYNOMES

Les polynômes peuvent être représentés de différentes manières. Voici quelques méthodes : ▪

À l'aide de tableaux

▪

À l'aide de listes chaînées

3.8.1.3.1 REPRESENTATION DES POLYNOMES A L'AIDE DE TABLEAUX Il peut arriver que vous ayez besoin d'évaluer de nombreuses expressions polynomiales et d'effectuer des opérations arithmétiques de base telles que l'addition et la soustraction avec ces nombres. Pour cela, vous devrez trouver un moyen de représenter ces polynômes. La méthode simple consiste à représenter un polynôme de degré 'n’, et à stocker les coefficients

96

des termes de degré n+1 du polynôme dans un tableau. Ainsi, chaque élément du tableau contiendra deux valeurs : Le coefficient et L'exposant. 3.8.1.3.2 REPRESENTATION

DES

POLYNOMES

A

L'AIDE

DE

LISTES

CHAINEES Un polynôme peut être considéré comme une liste ordonnée de termes non nuls. Chaque terme non nul est un couple qui contient deux informations : ▪

La partie exponentielle

▪

La partie coefficient

3.8.1.3.2.1 ADDITION DE DEUX POLYNOMES A L'AIDE DE LISTES CHAINEES L'addition de deux polynômes à l'aide de listes chaînées implique la fusion de deux structures de données dynamiques représentant les polynômes. Chaque terme des polynômes est stocké dans un nœud de la liste chaînée, comprenant le coefficient et l'exposant du terme, ainsi qu'un pointeur vers le prochain nœud. Pour réaliser l'addition, les listes chaînées des polynômes sont parcourues simultanément, en additionnant les coefficients des termes ayant le même exposant. Les termes résultants sont ajoutés à une nouvelle liste chaînée représentant le polynôme somme. Si un exposant est présent dans un seul des polynômes, le terme correspondant est simplement ajouté à la liste somme. Cette approche permet une manipulation efficace des polynômes, tout en évitant les opérations coûteuses associées à la représentation statique des polynômes. Ainsi, l'addition de polynômes à l'aide de listes chaînées offre une méthode flexible et optimale pour combiner des structures polynomiales de manière dynamique. Étant donné deux nombres polynomiaux représentés par une liste chaînée, écrivez une fonction qui additionne ces listes, c'est-à-dire qui additionne les coefficients ayant les mêmes puissances variables. Exemple :

Entrée : 1er nombre = 5x^2 + 4x^1 + 2x^0

2e nombre = 5x^1 + 5x^0 Sortie : 5x^2 + 9x^1 + 7x^0 Entrée : 1er nombre = 5x^3 + 4x^2 + 2x^0 2e nombre = 5x^1 + 5x^0 Sortie : 5x^3 + 4x^2 + 5x^1 + 7x^0 97

L'image ci-dessous présente la procédure de sommation de deux polynômes représentés par des listes chaînées, Liste 1 et Liste 2. La procédure commence par créer une nouvelle liste chaînée vide appelée Liste résultante. En parcourant simultanément les deux listes d'origine, chaque terme est additionné, et le résultat est stocké dans un nouveau nœud de la Liste résultante. Cette étape se répète jusqu'à ce que les deux listes soient entièrement parcourues. La procédure se conclut avec la Liste résultante contenant la somme des deux polynômes d'origine. Les étapes détaillées comprennent la création de la Liste résultante, le parcours des listes d'origine avec l'addition des coefficients et des puissances, et la création de nouveaux nœuds pour stocker les résultats. En fin de procédure, la Liste résultante est renvoyée.

CODE DE L’EXEMPLE Le code ci-dessous définit une structure de données `Node` pour représenter des termes de polynômes, avec des champs pour le coefficient, la puissance et un pointeur vers le prochain terme. Les fonctions incluses permettent de créer des nœuds pour les termes de polynômes, d'additionner deux polynômes représentés par des listes chaînées, et d'afficher le résultat. Dans la fonction `main`, deux polynômes sont créés, affichés, additionnés, et le résultat est affiché. Le code facilite la manipulation des polynômes en utilisant une structure de données chaînée pour représenter les termes, offrant une approche modulaire pour effectuer des opérations sur les polynômes. struct Node { int coeff; // Coefficient du terme int pow; // Puissance du terme struct Node *next; // Pointeur vers le prochain terme };

98

void create_node(int x, int y, struct Node **temp) { struct Node *r, *z; z = *temp; if (z == NULL) { r = (struct Node *)malloc(sizeof(struct Node)); r->coeff = x; r->pow = y; *temp = r; r->next = (struct Node *)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } else { r->coeff = x; r->pow = y; r->next = (struct Node *)malloc(sizeof(struct Node)); r = r->next; r->next = NULL; } } void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly) { while (poly1->next && poly2->next) { if (poly1->pow > poly2->pow) { poly->pow = poly1->pow; poly->coeff = poly1->coeff; poly1 = poly1->next; } else if (poly1->pow < poly2->pow) { poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next; } else { poly->pow = poly1->pow; poly->coeff = poly1->coeff + poly2->coeff; poly1 = poly1->next; poly2 = poly2->next; } poly->next = (struct Node *)malloc(sizeof(struct Node)); poly = poly->next; poly->next = NULL; } while (poly1->next || poly2->next) { if (poly1->next) { poly->pow = poly1->pow; poly->coeff = poly1->coeff;

99

poly1 = poly1->next; } if (poly2->next) { poly->pow = poly2->pow; poly->coeff = poly2->coeff; poly2 = poly2->next; } poly->next = (struct Node *)malloc(sizeof(struct Node)); poly = poly->next; poly->next = NULL; } } void show(struct Node *node) { while (node->next != NULL) { printf("%dx^%d", node->coeff, node->pow); node = node->next; if (node->next != NULL) printf(" + "); } } int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL; // Créer la première liste de 5x^2 + 4x^1 + 2x^0 create_node(5, 2, &poly1); create_node(4, 1, &poly1); create_node(2, 0, &poly1); // Créer la deuxième liste de 5x^1 + 5x^0 create_node(5, 1, &poly2); create_node(5, 0, &poly2); printf("1er Nombre : "); show(poly1); printf("\n2e Nombre : "); show(poly2); poly = (struct Node *)malloc(sizeof(struct Node)); // Fonction pour additionner deux polynômes polyadd(poly1, poly2, poly); // Afficher la liste résultante printf("\nPolynôme additionné : "); show(poly); return 0; }

3.8.1.3.2.2 MULTIPLICATION DE DEUX POLYNOMES A L'AIDE DE LISTES CHAINEES La multiplication de deux polynômes à l'aide de listes chaînées implique une approche plus complexe que l'addition. Pour effectuer cette opération, chaque terme du premier polynôme doit être multiplié par chaque terme du deuxième polynôme, et les résultats sont additionnés en fonction des exposants. On crée une nouvelle liste chaînée pour stocker les termes du 100

polynôme résultant. Pendant le processus de multiplication, on doit gérer les exposants et coefficients de manière à éviter les doublons. Ainsi, lorsqu'un terme avec un exposant déjà présent dans la liste résultante est atteint, le coefficient existant est mis à jour en additionnant le produit du terme actuel. Cette méthode garantit que la nouvelle liste chaînée contienne tous les termes nécessaires pour représenter le polynôme résultant de la multiplication. En conclusion, la multiplication de polynômes à l'aide de listes chaînées implique une approche itérative et une gestion minutieuse des exposants et coefficients pour obtenir un résultat correct et efficace. Soit deux polynômes sous forme de liste chaînée. La tâche consiste à trouver la multiplication

des deux polynômes. Exemples : Entrée : Poly1 : 3x^2 + 5x^1 + 6, Poly2 : 6x^1 + 8 Sortie : 18x^3 + 54x^2 + 76x^1 + 48 En multipliant chaque élément du premier polynôme avec les éléments du deuxième polynôme, nous obtenons 18x^3 + 24x^2 + 30x^2 + 40x^1 + 36x^1 + 48 En ajoutant les valeurs avec la même puissance de x, 18x^3 + 54x^2 + 76x^1 + 48 Entrée : Poly1 : 3x^3 + 6x^1 - 9, Poly2 : 9x^3 - 8x^2 + 7x^1 + 2 Sortie : 27x^6 - 24x^5 + 75x^4 - 123x^3 + 114x^2 - 51x^1 - 18

Dans cette approche, nous multiplierons le 2e polynôme avec chaque terme du 1er polynôme. Stockeront la valeur multipliée dans une nouvelle liste chaînée.

101

Ensuite, nous ajouterons les coefficients des éléments ayant la même puissance dans le polynôme résultant. CODE DE L’EXEMPLE Le code ci-dessous implémente l’opération de multiplication sur des polynômes. Il utilise une structure de nœud pour représenter les termes du polynôme avec des coefficients et des puissances. La fonction `addnode` ajoute un nouveau nœud à la fin de la liste chaînée représentant un polynôme. La fonction `printList` affiche le polynôme. La fonction `removeDuplicates` élimine les termes avec la même puissance en combinant leurs coefficients. Enfin, la fonction `multiply` multiplie deux polynômes et stocke le résultat dans un

troisième polynôme, en utilisant les opérations sur les listes chaînées. Le programme principal crée deux polynômes, les affiche, multiplie les deux polynômes, et affiche le résultat. #include #include // Structure de nœud contenant le coefficient et la puissance de la variable struct Node { int coeff, power; struct Node* next; }; // Fonction pour ajouter un nouveau nœud à la fin de la liste struct Node* addnode(struct Node* start, int coeff, int power) { // Créer un nouveau nœud struct Node* newnode = (struct Node*)malloc(sizeof(struct Node)); newnode->coeff = coeff; newnode->power = power; newnode->next = NULL; // Si la liste chaînée est vide if (start == NULL) return newnode; // Si la liste chaînée a des nœuds struct Node* ptr = start; while (ptr->next != NULL) ptr = ptr->next; ptr->next = newnode; return start; } // Fonction pour afficher la liste chaînée void printList(struct Node* ptr) { while (ptr->next != NULL) { printf("%dx^%d", ptr->coeff, ptr->power); if (ptr->next != NULL && ptr->next->coeff >= 0) printf("+"); ptr = ptr->next; } printf("%d\n", ptr->coeff); }

102

// Fonction pour ajouter les coefficients de // deux éléments ayant la même puissance void removeDuplicates(struct Node* start) { struct Node *ptr1, *ptr2, *dup; ptr1 = start; /* Sélectionner les éléments un par un */ while (ptr1 != NULL && ptr1->next != NULL) { ptr2 = ptr1; // Comparer l'élément sélectionné // avec le reste des éléments while (ptr2->next != NULL) { // Si la puissance de deux éléments est la même if (ptr1->power == ptr2->next->power) { // Ajouter leurs coefficients et le mettre dans le 1er élément ptr1->coeff = ptr1->coeff + ptr2->next->coeff; dup = ptr2->next; ptr2->next = ptr2->next->next; // Supprimer le 2ème élément free(dup); } else ptr2 = ptr2->next; } ptr1 = ptr1->next; } } // Fonction pour multiplier deux polynômes struct Node* multiply(struct Node* poly1, struct Node* poly2, struct Node* poly3) { // Créer deux pointeurs et stocker // les adresses des 1er et 2ème polynômes struct Node *ptr1, *ptr2; ptr1 = poly1; ptr2 = poly2; while (ptr1 != NULL) { while (ptr2 != NULL) { int coeff, power; // Multiplier le coefficient des deux // polynômes et le stocker dans coeff coeff = ptr1->coeff * ptr2->coeff; // Ajouter la puissance des deux polynômes // et la stocker dans power power = ptr1->power + ptr2->power; // Appeler la fonction addnode pour créer // un nouveau nœud en passant trois paramètres poly3 = addnode(poly3, coeff, power); // Déplacer le pointeur du 2ème polynôme // pour obtenir son terme suivant ptr2 = ptr2->next; } // Déplacer le 2ème pointeur au // point de départ du 2ème polynôme ptr2 = poly2; // Déplacer le pointeur du 1er polynôme ptr1 = ptr1->next; }

103

// Cette fonction sera appelée pour ajouter // le coefficient des éléments ayant la même puissance // à partir de la liste chaînée résultante removeDuplicates(poly3); return poly3; } // Fonction principale int main() { struct Node *poly1 = NULL, *poly2 = NULL, *poly3 = NULL; // Création du 1er polynôme : 3x^2 + 5x^1 + 6 poly1 = addnode(poly1, 3, 3); poly1 = addnode(poly1, 6, 1); poly1 = addnode(poly1, -9, 0); // Création du 2ème polynôme : 9x^3 - 8x^2 + 7x^1 + 2 poly2 = addnode(poly2, 9, 3); poly2 = addnode(poly2, -8, 2); poly2 = addnode(poly2, 7, 1); poly2 = addnode(poly2, 2, 0); // Affichage du 1er polynôme printf("1er Polynôme : "); printList(poly1); // Affichage du 2ème polynôme printf("2ème Polynôme : "); printList(poly2); // Appel de la fonction multiply poly3 = multiply(poly1, poly2, poly3); // Affichage du polynôme résultant printf("Polynôme Résultant : "); printList(poly3); return 0; }

3.9 EXERCICES DE FIN DE CHAPITRE 3.9.1 EXERCICE 1 Considérons le code suivant, où tete pointe vers le début d'une liste chaînée : typedef struct nœud { int valeur; struct nœud *lien; } Nœud; Complétez la fonction C suivante qui renvoie un pointeur vers le nœud qui précède (vient avant) chercherNœud, s'il se trouve dans la liste chaînée. Si chercherNœudn'est pas trouvé ou si la liste chaînée est vide, la fonction doit renvoyer NULL. Lisez attentivement la fonction : vous devrez peut-être ajouter du code à plusieurs endroits. Nœud *predecesseur(Nœud *tete, Nœud *chercherNœud) { Nœud *courant; courant = tete; if (tete == chercherNœud) return NULL; // COMPLETER LA LIGNE QUI SUIT: while (…………………………………………………………………) { if (courant->lien== chercherNœud) return courant; // ECRIRE LE CODE ICI:

104

} return NULL; }

3.9.2 EXERCICE 2 La structure C suivante est utilisée pour définir chaque nœud dans une liste chaînée : typedef struct nœud { int donnees; struct nnœud *lien; } Nœud; Ecrivez une procédure C appelée printDuplicates() qui reçoit un pointeur vers le premier nœud ( tete) d'une liste chaînée en tant que paramètre. La fonction doit rechercher et imprimer les entiers en double dans la liste chaînée. Par exemple, si la liste chaînée contient les entiers 6,3,3,6,7,4, alors printDuplicates() devrait afficher : 6 3 Remarque : Dans votre solution, vous pouvez supposer qu'un entier donné apparaît au plus deux fois dans la liste chaînée.

3.9.3 EXERCICE 3 Créez une fonction qui transforme un arbre binaire donné en son miroir, comme illustré dans la figure ci-dessous. La fonction échangera les parties gauche et droite de chaque nœud dans l'arbre jusqu'aux feuilles. Vous avez le droit d'utiliser une seule variable locale supplémentaire, mais aucune variable globale. Il n'est pas permis d'allouer de mémoire dynamique.

3.9.4 EXERCICE 4 Considérons une liste L représentant les étudiants d'une classe, avec chaque étudiant caractérisé par son Matricule, Nom, Prénom et Moyenne. 1. Définissez une structure de données chaînée permettant de stocker la liste des étudiants, et déclarez une liste vide. 105

2. Rédigez une fonction qui calcule la moyenne générale d'une classe L. 3. Élaborez un programme qui divise la liste L en deux sous-listes L1 et L2, de telle manière que la première liste, L1, contienne uniquement les étudiants admis, et la deuxième liste, L2, contienne les étudiants non admis.

3.9.5 EXERCICE 5 (Files) Considérons le code d'une structure de File basée sur une liste chaînée, où initialiserFile() initialise une file vide, et enfiler() ajoute un nouvel élément à la fin de la file. typedef struct Element { int donnee; struct Element* suivant; } Element; typedef struct File { Element* avant; Element* arriere; } File; void initialiserFile(File* file) { file->avant = NULL; file->arriere = NULL; } void enfiler(File* file, int donnee) { Element* nouvelElement = (Element*)malloc(sizeof(Element)); nouvelElement->donnee = donnee; nouvelElement->suivant = NULL; if (file->arriere == NULL) { file->avant = nouvelElement; file->arriere = nouvelElement; } else { file->arriere->suivant = nouvelElement; file->arriere = nouvelElement; } } // Fonction pour libérer la mémoire d'une liste chaînée void freeListe(Element* actuel) { Element* temp; while (actuel != NULL) { temp = actuel; actuel = actuel->suivant; free(temp); } }

1. Écrivez une procédure, nommée afficherFile(), qui affiche tous les éléments d'une file. 2. Élaborez une autre procédure, nommée defilerJusqua(), qui défile la file jusqu'à atteindre l'élément spécifié (Elt). Notez que si l'élément Elt existe dans la file, il ne sera pas défilé, mais restera dans la file. Cependant, si l'élément n'appartient pas à la file, la fonction défilera tous les éléments de la file.

106

3.9.6 EXERCICE 6 (Piles et Files) Considérons le code d’une structure de pile basée sur une liste chaînée, où initStack initialise une pile vide, isEmpty vérifie si la pile est vide, push ajoute un élément au sommet de la pile, et pop retire l'élément du sommet de la pile. Écrivez une fonction inverser() pour inverser une pile `P1` contenant des nombres réels. Choisissez judicieusement entre l'utilisation d'une pile ou d'une file pour cette opération. Note : Pour l'exercice 4, il est suggéré de choisir une pile pour inverser les éléments, car l'inversion d'une pile suit le principe de dernier entré, premier sorti (LIFO), ce qui est approprié pour l'inversion.

3.9.7 EXERCICE 7 : GESTION DES POLYNOMES AVEC LES LISTES CHAINEES Le but de cet exercice est d’implémenter des opérations sur des polynômes par des listes chaînées. On représente un polynôme par une liste chaînée. Chaque cellule de la liste correspond à un monôme, avec son coefficient et son exposant. Par exemple, sur la figure ci-dessous, on représente la liste chaînée correspondant au polynôme 5x4+2x2+3

On représente le Polynôme nul par une liste vide. 1. Définir la structure Poly qui a pour champs : le coefficient (réel), l'exposant (entier positif). 2. Écrire une fonction de saisie au clavier d’un monôme. 3. Écrire une fonction qui ajout un monôme a la liste du polynôme, en traite tous les cas possibles. Attention : le Polynôme doit être trié toujours en exposant décroissant. 4. Écrire une fonction qui revoie une copie du polynôme. 5. Écrire une fonction qui créer et renvoi la somme de deux polynômes. 6. Écrire une fonction qui créer et renvoi le polynôme dérivé. 7. Écrire une fonction qui affiche le polynôme. .

107

CHAPITRE 4 TABLE DE HACHAGE 4.1 INTRODUCTION Les tables de hachage, en informatique, sont des structures de données cruciales pour la gestion efficace et rapide des données. En langage C, elles représentent un moyen puissant d'optimiser la recherche, l'insertion et la suppression d'éléments dans un ensemble de données. L'idée fondamentale derrière les tables de hachage est d'utiliser une fonction de hachage pour mapper chaque élément à une position spécifique dans une table, souvent appelée "bucket". Cette approche permet un accès direct aux éléments, réduisant ainsi le temps de recherche par rapport à d'autres structures de données telles que les listes chaînées. Les tables de hachage se démarquent particulièrement lorsqu'on les compare aux listes chaînées. Alors que les listes chaînées offrent une flexibilité considérable pour l'ajout dynamique d'éléments, elles peuvent devenir inefficaces en termes de recherche, surtout lorsque la taille de la liste augmente. En revanche, les tables de hachage exploitent une fonction de hachage pour répartir uniformément les éléments dans des emplacements prédéterminés, minimisant ainsi les collisions6. Les collisions surviennent lorsque deux éléments différents sont hashés vers la même position dans la table. Pour résoudre ce problème, les tables de hachage utilisent souvent des techniques telles que le chaînage, où chaque position de la table pointe vers une liste chaînée contenant tous les éléments hashés à cette position. Cette approche permet une gestion efficace des collisions tout en préservant la vitesse de recherche caractéristique des tables de hachage. Ainsi, en choisissant judicieusement une fonction de hachage et en traitant les collisions de manière appropriée, les tables de hachage en C fournissent une solution optimale pour la recherche rapide et la manipulation efficace des données, offrant des performances souvent supérieures à celles des listes chaînées dans de nombreux scénarios d'application.

6

Collision : Dans une table de hachage, une collision est une situation dans laquelle deux clés différentes ont la même valeur de hachage. Cela signifie qu'elles sont stockées dans la même alvéole de la table. Les collisions sont inévitables dans les tables de hachage, car la taille de la table est toujours inférieure ou égale à l'ensemble des valeurs possibles des clés. Par exemple, si la table a une taille de 10, et que les clés sont des nombres entiers, il y a une collision possible pour chaque paire de nombres entre 0 et 9.

108

4.2 CONCEPT 4.2.1 DEFINITION ET PRESENTATION 4.2.1.1 DEFINITION Une table de hachage est une structure de données qui associe des clés à des valeurs. C'est donc une implémentation d’un tableau associatif (tableau dans lequel les indices peuvent être autre chose que des petits entiers, aussi appelé dictionnaire) Elle utilise une fonction de hachage pour transformer chaque clé en un index d’un tableau mais il peut y avoir des collisions (= des clés différentes étant traduites en un même index) qu’il faut gérer. SCHEMA D’UNE TABLE DE HACHAGE Exemple

1

:

on

souhaite

stocker

{(Alice,Journaliste),

(Bob,Mécanicien),

(Charles,Informaticien)} ▪

La fonction de hachage est le nombre de lettres dans le prénom

▪

Le tableau sous-jacent a 10 cases

Exemple 2 : on souhaite ajouter (David,Médecin) ▪

Une collision apparaît entre les clés « Alice » et « David »

▪

Dans cet exemple, on traite la collision avec une liste chaînée

109

4.2.2 PRESENTATION Les listes chaînées ont un gros défaut lorsqu'on souhaite lire ce qu'elles contiennent : il n'est pas possible d'accéder directement à un élément précis. Il faut parcourir la liste en avançant d'élément en élément jusqu'à trouver celui qu'on recherche. Cela pose des problèmes de performance dès que la liste chaînée devient volumineuse. Les tables de hachage représentent une autre façon de stocker des données. Elles sont basées sur les tableaux du langage C. Elles permettent de retrouver instantanément un élément précis, que la table contienne 100, 1 000, 10 000 cases ou plus encore.

4.2.3 INTERET D'UNE TABLE DE HACHAGE Les listes chaînées permettent d'ajouter ou de supprimer des cases à tout moment. Toutefois, elles ont quand même un gros défaut : si on cherche à récupérer un élément précis de la liste, il faut parcourir celle-ci en entier jusqu'à ce qu'on le retrouve. Imaginons une liste chaînée qui contienne des informations sur des élèves : leur nom, leur âge et leur moyenne. Chaque élève sera représenté par une structure Eleve. Nous avons travaillé auparavant sur des listes chaînées qui contenaient des int . Cela dit, on peut stocker ce qu'on veut dans une liste, même un pointeur vers une structure, comme je le propose ici. Si on veut retrouver les informations sur YANSO TCHAPTCHET, il va falloir parcourir toute la liste en analysant chaque élément à partir du premier pour se rendre compte qu'il était à la fin :

110

Bien entendu, si on avait cherché FOM NOTAM, cela aurait été beaucoup plus rapide puisqu'il est au début de la liste. Néanmoins, pour évaluer l'efficacité d'un algorithme, on doit toujours envisager le pire des cas. Et le pire, c'est YANSO TCHAPTCHET. Ici, on dit que l'algorithme de recherche d'un élément a une complexité en O(n) , car il faut parcourir toute la liste chaînée pour retrouver un élément donné, dans le pire des cas où celui-ci est à la fin. Si la liste contient 9 éléments, il faudra 9 itérations au maximum pour retrouver un élément. Dans cet exemple, notre liste chaînée ne contient que quatre éléments. L'ordinateur retrouvera YANSO TCHAPTCHET très rapidement. Mais imaginez que celui-ci se trouve à la fin d'une liste chaînée de 10 000 éléments ! Ce n'est pas acceptable de devoir parcourir jusqu'à 10 000 éléments pour retrouver une information. C'est là que les tables de hachage entrent en jeu. 4.2.3.1 TABLE DE HACHAGE Les tableaux permettent un accès direct à un élément donné en utilisant son indice et non pas de problème pour la recherche d'un élément dans une liste chaînée. Cela signifie que si vous avez un tableau, vous pouvez accéder à n'importe quel élément en fournissant simplement son indice, sans avoir à parcourir les éléments un par un. Cette caractéristique rend la recherche plus efficace dans un tableau par rapport à une liste chaînée. Pour accéder à l'élément d'indice 2 dans notre tableau tableau, il nous suffisait d'écrire ceci : int tableau[4] = {12, 7, 14, 33}; printf("%d", tableau[2]);

Si on lui donne tableau[2], l'ordinateur va directement à la case mémoire où se trouve stocké le nombre 14. Il ne parcourt pas les cases du tableau une à une. Cependant comme nous l’avons dit dans le chapitre sur les listes chaînées, il est important de noter que les tableaux ont leurs propres limitations, notamment en ce qui concerne l'ajout et la suppression dynamiques d'éléments, ce qui est plus flexible avec les listes chaînées. En effet, les listes chaînées sont plus flexibles. Les tableaux, eux, permettent un accès plus rapide. Les tables de hachage constituent quelque part un compromis entre les deux. 111

Il y a un défaut important avec les tableaux dont on n'a pas beaucoup parlé jusqu'ici : les cases sont identifiées par des numéros qu'on appelle des indices. Il n'est pas possible de demander à l'ordinateur : "Dis-moi quelles sont les données qui se trouvent à la case « YANSO TCHAPTCHET ». Pour retrouver l'âge et la moyenne de YANSO TCHAPTCHET, on ne peut donc pas écrire : tableau["YANSO TCHAPTCHET"];

Ce serait pourtant pratique de pouvoir accéder à une case du tableau rien qu'avec le nom ! Eh bien avec les tables de hachage, c'est possible ; Les tables de hachage ne font pas partie du langage C. Il s'agit simplement d'un concept. On va réutiliser les briques de base du C que l'on connaît déjà pour créer un nouveau système intelligent. Puisque notre tableau doit forcément être numéroté par des indices, comment fait-on pour retrouver le bon numéro de case si on connaît seulement le nom " YANSO TCHAPTCHET " ? Un tableau reste un tableau, et celui-ci ne fonctionne qu'avec des indices numérotés. Imaginez un tableau dans lequel chaque case a un indice et possède un pointeur vers une structure de type Eleve :

Si on veut retrouver la case correspondant à Luc Doncieux, il faut transformer son nom en indice du tableau, et donc associer chaque nom à un numéro de case : ▪ ▪

FOM NOTAL = 0 ; COSTY BANKOUE = 1 ; 112

▪ ▪

SANI NGATCHUI = 2 ; YANSO TCHAPTCHET = 3.

NB : On ne peut pas écrire tableau ["YANSO TCHAPTCHET"] comme nous l’avons fait précédemment. Ce n'est pas valide en C. Pour transformer cette chaine de caractères en numéro, il faut écrire une fonction qui prend en entrée une chaîne de caractères, fait des calculs avec, puis retourne en sortie un numéro correspondant à cette chaîne. Ce numéro sera l'indice de la case dans notre tableau :

La fonction de hachage génère un indice correspondant au nom envoyé en paramètre 4.2.3.2 ECRITURE D’UNE FONCTION DE HACHAGE La création d'une fonction de hachage correcte pose un défi particulier. Comment peut-on convertir une chaîne de caractères en un nombre unique ? Pour commencer, clarifions les choses : une table de hachage ne se limite pas à 4 cases comme illustré dans mes exemples, mais plutôt à 100, 1 000, voire plus. Peu importe la taille du tableau, la recherche de l'élément reste rapide. On dit que c'est une complexité en O(1), car on peut trouver directement l'élément recherché. La fonction de hachage renvoie un indice, et il suffit de "sauter" directement à la case correspondante du tableau, éliminant ainsi la nécessité de parcourir toutes les cases. Imaginons un tableau de 100 cases destiné à stocker des pointeurs vers des structures d'élèves.

Eleve* tableau[100]; Nous devons concevoir une fonction qui génère, à partir d'un nom, un nombre compris entre 0 et 99 (les indices du tableau). C'est là que la créativité est nécessaire. Bien qu'il existe des 113

méthodes mathématiques complexes pour "hacher" des données, nous pouvons ici simplifier en proposant d'additionner les valeurs ASCII de chaque lettre du nom. 'Y'+'A'+'N'+'S'+'O'+' '+'T'+'C'+'H'+'A'+'P'+'T'+'C'+'H'+'E'+'T' Cependant, un problème se pose : la somme des valeurs ASCII peut dépasser 100. Chaque lettre dans la table ASCII peut être numérotée jusqu'à 255. On a donc vite fait de dépasser 100. Pour remédier à cela, l'opérateur modulo % est utilisé pour obtenir un nombre entre 0 et 99. Par exemple, si la somme fait 4 315, le reste de la division par 100 est 15. La fonction de hachage retournera donc 15. La fonction ci-dessous calcule une somme des valeurs ASCII des caractères dans la chaîne et renvoie le reste de la division par 100 de cette somme, ce qui donne un résultat entre 0 et 99.: int hachage(char *chaine) { int i = 0, nombreHache = 0; for (i = 0 ; chaine[i] != '\0' ; i++) { nombreHache += chaine[i]; } nombreHache %= 100; return nombreHache; }

Grâce à cette fonction de hachage, on sait dans quelle case du tableau placer les données. Lorsqu'on souhaite y accéder ultérieurement pour récupérer les informations, il suffit de hacher à nouveau le nom de la personne pour retrouver l'indice de la case du tableau où les données sont stockées. Il est recommandé de créer une fonction de recherche qui hachera la clé (le nom) et renverra un pointeur vers les données recherchées.

114