MODULE

STRUCTRURE DE DONNEES ET
PROGRAMMATION
Université Thomas SANKARA
Sciences et Technologies
LIME-LISE L2S3

Boureima KOUSSOUBE
❖Doctorant en Informatique à l’UNB
❖Ingénieur de conception
❖Enseignant/Formateur
1
 Objectifs
Objectif final : à la fin du module vous devez être capable de manipuler les
données
Objectif intermédiaire 1: à la fin du cours vous devez capable de vous
d’utiliser pointeurs dans les programmes
Objectif intermédiaire 2: à la fin du cours vous devez capable de créer des
structure de données
Objectif intermédiaire 3: à la fin du cours vous devez capable de manipuler
les listes chainées
Objectif intermédiaire 4: à la fin du cours vous devez capable de créer des
piles, des files et des arbres binaires
Objectif intermédiaire 5: à la fin du cours vous devez capable de manipuler
des fichiers
2
 Programme
Volume horaire 24 heures
Cours Magistral (CM) : 14 heures
Travaux Dirigés (TD) : 04 heures
Travaux Pratiques (TP) : 06 heures

Evaluations
Projet

3
 Plan du cours
I. Révision sur le langage C
II. Pointeurs
III. Tableaux
IV. Types énumérés
V. Structure de données
VI. Liste chainée
VII. Pile et file
VIII. Arbre binaire
IX. Fichiers
4
 I. Révision sur le langage C
Application 1

Ecrire programme en C en utilisant une fonction

qui permet de calculer la somme de deux entiers

Application 2

Ecrire programme en C en utiliser une fonction qui

permet de permuter deux entiers
5
 II. Pointeurs
1. VARIABLES
Dans un programme, il apparaît des variables qui permettent de donner des
noms à des données. Chaque variable doit avoir un type (nombre entier,
nombre réel, caractère, suite de caractères, ou type plus complexe). Chaque
variable a aussi un identificateur qui est le nom de la variable. Une
déclaration d’une variable peut être de la forme :
int nbre1;
➢ int type de la variable nbre1
➢ nbre1 nom de la variable
➢ &nbre1 adresse de la variable

6
II. Pointeurs
2. MÉMOIRE CENTRALE ET ADRESSES (Exemple)
Adresses Valeurs

0x0000001 00110110 nbre1

0x0000002 Déclaration de
… variable
…
0x0000A01 int nbre1 = 54;
0x0000A02 00001110 Nbre 2 int nbre2 = 14;
…
…
0x00B0001
0x0000D04
…
7
 II. Pointeurs
1. VARIABLES
Pour afficher l'adresse d'une variable en langage C en utilisant la
bibliothèque <stdlib.h>, vous pouvez utiliser la fonction printf avec le
format spécifique %p. Le spécificateur de format %p est utilisé pour afficher
l'adresse en hexadécimal.

8
 II. Pointeurs
3. VARIABLES DE TYPE POINTEUR
• Un pointeur est une variable d'un type spécial qui contient l'adresse
d'une autre variable.
• On dit qu'il pointe vers cette variable. Celui-ci devra aussi connaitre
le type de la variable vers laquelle il pointe puisque la taille d'une
variable (en octets) dépend de son type. La déclaration d'un pointeur
devra donc indiquer le type de la variable vers laquelle il pointe (on
dit d'un pointeur qu’il est typé)

9
II. Pointeurs
• MÉMOIRE CENTRALE, ADRESSES et POINTEURS
Exemple : int* Nbre1
Adresses Valeurs
0x0000001 000110 Nbre1
0x0000002
…
…
0x0000A01
0x0000A02 *Nbre1
…
…
0x00B0001
0x0000D04
… 10
II. Pointeurs
• LES SYNTAXES DE DECLARATION
❑type *identificateur;
int *X;
oX : adresse de la variable pointée
o*X : valeur de la variable pointée
o&X : adresse du pointeur

❑type *identificateur;
int *x, y;
❑Type* identificateur;
int* x, y;
11
II. Pointeurs
Accès aux valeurs
On accède à la valeur stockée a l'adresse contenue dans un pointeur
grâce a l'operateur unaire
int a;
int* x;
x=&a;

a et *x font référence au même emplacement mémoire

*x = 3; /* la variable pointé (a) par x prend pour valeur 3 */

12
II. Pointeurs
EXEMPLE
#include <stdio.h>
int main(void)
{
int x = 2;
int *p = &x; /* x et *p deviennent synonymes */
*p = 3;
printf("La nouvelle valeur de x est %d\n", x);
/* doit afficher la valeur 3 */
return 0;
}
13
 II. Pointeurs
Initialisation d’un pointeur
La déclaration d'un pointeur alloue un espace mémoire
pour le pointeur mais pas pour l'objet pointe. Le pointeur
pointe sur n'importe quoi au moment de sa déclaration. Il
est conseille d'initialiser tout pointeur avant son utilisation
effective avec la valeur NULL (constante prédéfinie qui vaut
0) ce qui, par convention, indique que le pointeur ne pointe
sur rien.

14
II. Pointeurs
• PASSAGE DE PARAMÈTRE PAR VALEUR
Lorsqu’on passe un paramètre à une fonction, la
fonction ne peut pas modifier la variable. La variable
est automatiquement recopiée et la fonction travaille
sur une copie de la variable. La modification de la
copie n’entraîne pas une modification de la variable
originale. C’est le passage de paramètre par valeur.

15
II. Pointeurs
• PASSAGE DE PARAMÈTRE PAR VALEUR
#include <stdio.h>
void NeModifiePas(int x)
{
x = x+1; /* le x local est modifie, pas le x du main */
}
int main(void)
{
int x=1;
NeModifiePas(x);
printf("%d", x); /* affiche 1 : valeur de x inchangee */
return 0;
}
16
II. Pointeurs
• PASSAGE DE PARAMÈTRE PAR ADRESSE
L’idée du passage par adresse est que, pour modifier une
variable par un appel de fonction, il faut passer en paramètre
non pas la variable, mais un pointeur qui pointe sur la
variable. Ainsi, le paramètre est l’adresse de x. Lorsqu’on
modifie la mémoire à cette adresse, la donnée x est modifiée,
car on travaille bien sur l’emplacement mémoire de x

17
 II. Pointeurs
PASSAGE DE PARAMÈTRE PAR ADRESSE : Exemple
#include <stdio.h>
void Modifie(int *p) /* la fonction suivante prend en paramètre un pointeur */
{ *p = *p+1;
}

int main(void)
{ int x=1; /* la varible x n’est pas un pointeur */
int *p=NULL;
p = &x; /* pointeur qui pointe sur x */
Modifie(p);
printf("%d", x); /* affiche 2 */
return 0;
}
18
 II. Pointeurs
• PASSAGE DE PARAMÈTRE PAR ADRESSE
❑Lors de l’appel de la fonction Modifie, le pointeur p est recopié, et la
fonction Modifie travaille sur une copie du pointeur p. Cependant, les
pointeurs p et sa copie contiennent la même valeur, qui est l’adresse de x.

❑ Lorsqu’on modifie l’objet qui se trouve à cette adresse, on modifie x.

L’utilisation explicite d’un pointeur dans le main est superflue, on peut
passer directement l’adresse de x à la fonction, sans avoir besoin de définir
une variable de type pointeur dans le main.

19
 II. Pointeurs
• PASSAGE DE PARAMÈTRE PAR ADRESSE
#include <stdio.h>
void Modifie(int *p) /* parametre de type pointeur */
{
*p = *p+1; /* ce pointeur p a pour valeur &x (x du main) */
}
int main(void)
{
int x=1;
Modifie(&x); /* on passe directement l’adresse de x */
printf("%d", x); /* affiche 2 */
return 0;
}
20
 III. Tableaux
• Révision
Ecrire une programme qui demande a l’utilisateur d’entre la taille
du tableau, saisi et affiche les éléments
• Pointeur de tableau
La déclaration d'un tableau réserve de la place en mémoire de
manière contiguë.

21
 III. Tableaux
• Pointeur de tableau : exemple
La déclaration d'un tableau réserve de la place en mémoire de manière
contiguë.
Déclare un tableau de 10 éléments : int tab[10];
tab contient l'adresse du premier élément et donc l'expression:
tab == &tab[0] est VRAIE.
On a donc de même:
*tab == tab[0]
tab[1] == *(tab+1)
tab[2] == *(tab+2)
tab[3] == *(tab+3)
tab[k] == *(tab+k) 22
 III. Tableaux
• Pointeur de tableau : exemple

23
 III. Tableaux
• Pointeur de tableau : exemple

24
 III. Tableaux
• Les chaines de caractères

25
 III. Tableaux
• Les caractères

26
 III. Tableaux
• Les chaines de caractères

27
 III. Tableaux
• Les chaines de caractères

28
 III. Tableaux
• Les chaines de caractères

29
 III. Tableaux
• Les chaines de caractères

30
 III. Tableaux
• Les chaines de caractères

31
 III. Tableaux
• Les chaines de caractères

32
 III. Tableaux
• Les chaines de caractères

33
 Allocation dynamique
• ALLOCATION AVEC malloc (calloc)
La déclaration de variables dans la fonction main ou globalement réserve
de l'espace en mémoire pour ces variables pour toute la durée de vie du
programme. Elle impose par ailleurs de connaitre avant le début de
l’exécution l'espace nécessaire aux stockage de ces variables et en
particulier la dimension des tableaux. Or dans de nombreuses applications
le nombre d’éléments d'un tableau peut varier d'une exécution du
programme a l'autre. La bibliothèque stdlib fournit des fonctions qui
permettent de réserver et de libérer de manière dynamique (a
l’exécution) la mémoire. La fonction qui permet de réserver de la mémoire
est malloc. Par exemple, pour réserver de la mémoire pour un entier x, on
écrira:
type* nomvariable;
Nomvariable = (type*) malloc(sizeof(type));
• int* x;
• x=(int*) malloc(sizeof(int)); 34
 Allocation dynamique
• ALLOCATION AVEC malloc

35
 LES STRUCTURES
• DÉFINITION
Une structure est un type qui permet de stocker plusieurs
données, de même type ou de types différents, dans une même
variable de type structure. Une structure est composée de
plusieurs champs, chaque champ correspondant à une donnée.
• UTILISATION
• La gestion d'un répertoire
• Représentation de nombre complexe

36
 LES STRUCTURES
• SYNTAXE
struct nom
{
type1 champ1 ;
type2 champ2 ;
-------
typen champn ;
};

37
LES STRUCTURES
• EXEMPLE 1: DÉCLARATION D’UNE STRUCTURE
Déclaration d’une structure étudiant qui contient trois
champs de type différent.
Struct etudiant
{
char nom [30];
char prenom [30];
float matricule;
};
❖La déclaration d’une variable de type struct etudiant :
struct etudiant E1;
38
LES STRUCTURES
• EXEMPLE 2: DÉCLARATION D’UNE STRUCTURE
Le langage C permet de créer de nouveaux noms de
types de données grâce a la fonction typedef.
typedef struct Etudiant
{
char nom [30];
char prenom [30];
float matricule;
} etudiant;
❖La déclaration d’une variable de type etudiant :
etudiant E1;

39
LES STRUCTURES
• EXEMPLE 3: INITIALISATION
• struct etudiant
{
char nom [30] ;
char prenom [20] ;
int age ;
};
struct etudiant E1 = {"KABORE", "Paul", 10} ;
struct etudiant E2 ;
❑Possibilité de l’affectation globale : E1=E2
40
LES STRUCTURES
• UTILISATION D’UNE STRUCTURE
Exercice
Ecrire un programme (en utilisant les structures) qui
demande l’utilisateur d’entrer les coordonnées de
deux vecteurs puis calcul et affiche la somme des
vecteurs

41
 LES STRUCTURES
• UTILISATION D’UNE STRUCTURE ET DES FONCTIONS
Exercice application
1. Ecrire une fonction de saisie des coordonnées d’un vecteur,
2. Ecrire une fonction qui prend en paramètre deux vecteurs et
qui renvoi leur somme.
3. Ecrire une fonction qui prend en paramètre deux vecteurs et
qui renvoi leur produit scalaire.
4. Ecrire une fonction qui affiche des coordonnées d’un vecteur,
5. Tester toutes ces fonctions dans un programme principal

42
 LES STRUCTURES
• Type pointeur de structure
#include <string.h>
typedef struct etudiant
{
char nom [30] ;
char prenom [30] ;
int note;
} ETD;
struct etudiant *ptr, E1 ; ETD *ptr, E1;
ptr = &E1 ;
strcpy((*ptr).nom, "KABORE");
strcpy((*ptr).prenom, ‘’Moussa");
strcpy((*ptr).note, 0) ;
Les parenthèses dans l’accès au champ (*ptr).nom sont obligatoires. Pour
ne pas alourdir les notations, on peut utiliser l’opérateur flèche équivalent
qui donne : strcpy(ptr->nom, "Paul") ;
43
 LES STRUCTURES
• Structure comme paramètre de fonction
Une structure peut servir de paramètre à une fonction, avec passage par
valeur ou par adresse, et peut être le résultat d’une fonction, sans qu’il n’y
ait rien de plus à en dire.
des fonctions affiche() et saisie() pour une structure
❑Les déclarations seront :
void affiche( struct donnee personne) ;
void saisieE( struct donnee *personne) ;
❑les appels se faisant sous la forme :
affiche(personne) ;
saisie(&personne) ;;

44
 LES LISTES CHAINEES
• Définition
Une liste chaînée est un ensemble de cellules liées entre elles par des pointeurs.
Chaque cellule est une structure contenant les champs suivants :
✓une ou plusieurs données comme dans n’importe quelle structure ;
✓un pointeur suivant sur la cellule suivante.
On accède à la liste par un pointeur L sur la première cellule, puis en parcourant la liste
d’une cellule à l’autre en suivant les pointeurs suivant. Le dernier pointeur suivant
vaut NULL, ce qui indique la fin de la liste.

45
 LES LISTES CHAINEES
• DÉCLARER UNE LISTE CHAÎNÉE
Pour créer une liste chaînée, il faut déclarer une nouvelle structure de
données : la structure qui représentera une cellule.
typedef float TypeDonnee;
typedef struct Cell
{
TypeDonnee donnee; /* float donnee */
struct Cell *suivant; /* pointeur sur la structure suivante */
}TypeCellule;
TypeCellule *L; /* déclaration d’une liste */
La structure TypeCellule contient un pointeur sur TypeCellule. En fait, on ne
peut pas déclarer directement un pointeur sur le type TypeCellule qui est en
cours de définition. Par contre, le langage C permet de définir un pointeur
sur une structure non encore définie en employant le mot struct

46
 LES LISTES CHAINEES
Création d’une liste chainée
❖Les fonctions d’entrée-sortie
Voici les fonctions (code générique) d’entrée-sortie de TypeDonnée (dont
l’implémentation dépend du type) :
void AfficheDonnee(TypeDonnee donnee)
{
printf("%f ", donnee); /* ici donnee est de type float */
}
TypeDonnee SaisieDonnee(void)
{
TypeDonnee donnee;
scanf("%f", &donnee); /* ici donnee est de type float */
return donnee;
}
47
 LES LISTES CHAINEES
Création d’une liste chainée
INSERTION EN TÊTE DE LISTE
Elle se fait avec une fonction qui prend en paramètre une liste et
une donnée, et ajoute la donnée en tête de liste. La fonction
renvoie la nouvelle adresse de la tête de liste

48
 LES LISTES CHAINEES
Création d’une liste chainée
INSERTION EN TÊTE DE LISTE
TypeCellule* InsereEnTete(TypeCellule *ancienL, TypeDonnee donnee)
{
TypeCellule *nouveauL; /* nouvelle tete de liste */
nouveauL = (TypeCellule*)malloc(sizeof(TypeCellule)); /* creation d’une nouvelle cellule */
nouveauL->donnee=donnee; /* on met la donnee a ajouter dans la cellule */
nouveauL->suivant=ancienL; /* chainage */
return nouveauL; /* on retourne la nouvelle tete de liste */
}
• Ne pas confondre l’utilisation du point . et l’utilisation de la flèche -> pour accéder aux
champs d’une structure. On utilise le point pour une variable de type structure, et une flèche
pour une variable de type pointeur sur structure.

49
 LES LISTES CHAINEES
Création d’une liste chainée
CONSTRUCTION D’UNE LISTE CHAÎNÉE
Les listes chaînées se construisent par des insertions successives.
La fonction suivante réalise la saisie d’une liste chaînée au clavier.
TypeCellule* SaisieListeEnvers()
{
char choix;
TypeDonnee donnee;
TypeCellule *L=NULL; /* declaration d’une liste vide : */ /* initialisation obligatoire ! */
puts("Voulez-vous entrer une liste non vide ?");
choix = getchar();
getchar();

50
 LES LISTES CHAINEES
Création d’une liste chainée
CONSTRUCTION D’UNE LISTE CHAÎNÉE
. while (choix == ’o’)
{
puts("Entrez une donnée");
donnee = SaisieDonnee(); /* saisie au clavier */
getchar();
L = InsereEnTete(L, donnee); /* insertion en tete */
puts("Voulez-vous continuer ?");
choix = getchar();
getchar();
}
return L;
}
51
 LES LISTES CHAINEES
CONSTRUCTION D’UNE LISTE CHAÎNÉE
Avec des insertions en tête de liste, la liste obtenue est classée
à l’envers, le dernier élément saisi étant le premier élément de
la liste. Pour obtenir les éléments à l’endroit, il faudrait faire
les insertions en queue de liste

52
 LES LISTES CHAINEES
• PARCOURS DE LISTE
L’idée du parcours de liste chaînée est de prendre un pointeur auxiliaire
p. On fait pointer p sur la première cellule, puis le pointeur p passe à la
cellule suivante (par une affectation p=p->suivant), etc. Le parcours
s’arrête lorsque p vaut le suivant de la dernière cellule, c’est-à-dire
lorsque p vaut NULL.

53
 LES LISTES CHAINEES
• PARCOURS DE LISTE
• Exemple : la fonction suivante réalise l’affichage d’une liste chaînée.
void Affichage(TypeCellule* L)
{
TypeCellule *p;
p = L; /* on pointe sur la premiere cellule */
while (p != NULL) /* tant qu’il y a une cellule */
{
AfficheDonnee(p->donnee); /* on affiche la donnee */
p = p->suivant; /* on passe a la cellule suivante */
}
puts(""); /* passage a la ligne */
}

54
 LES LISTES CHAINEES
• PARCOURS DE LISTE
Lors du parcours, on s’arrête lorsque p vaut NULL, et non pas lorsque
p->suivant vaut NULL. En effet, p->suivant vaut NULL lorsque p pointe
sur la dernière cellule

55
 LES LISTES CHAINEES
• PARCOURS DE LISTE
Programme principale
int main(void)
{

TypeCellule *L; /* déclaration du pointeur sur tète de liste : */

L = SaisieListeEnvers(); /* on récupère l’adresse de la première cellule */
Affichage(L); /* on affiche la liste saisie */
return 0;
}

56
 LES PILES
• Définition
Une pile est une structure de données dans laquelle on peut
ajouter et supprimer des éléments suivant la règle du dernier
arrivé premier sorti ou encore LIFO (Last In First Out).
Le nom de pile vient d’une analogie avec une pile d’assiettes (par
exemple) où l’on poserait toujours les assiettes sur le dessus de la
pile, et ou l’on prendrait toujours les assiettes sur le dessus de la
pile. Ainsi, la dernière assiette posée sera utilisée avant toutes les
autres.

57
 LES PILES
• Les primitives
Une pile peut être implémentée par un tableau ou par une liste
chaînée. Dans les deux cas, il est commode de réaliser sur les
piles des opérations de base, appelées primitives de gestion des
piles. Les primitives de gestion des piles sont les suivantes :
❑Initialiser : cette fonction crée une pile vide.
❑EstVide : renvoie 1 si la pile est vide, 0 sinon.
❑EstPleine : renvoie 1 si la pile est pleine, 0 sinon.
❑AccederSommet : cette fonction permet l’accès à l’information
contenue dans le sommet de la pile.
❑Empiler : cette fonction permet d’ajouter un élément au sommet de la
pile. La fonction renvoie un code d’erreur si besoin en cas de manque de
mémoire.
58
 LES PILES
• Les primitives
Depiler : cette fonction supprime le sommet de la pile.
L’élément supprimé est retourné par la fonction Depiler pour
pouvoir être utilisé.
Vider : cette fonction vide la pile.
Detruire : cette fonction permet de détruire la pile.

Le principe de gestion des piles est que, lorsqu’on utilise une

pile, on ne se préoccupe pas de la manière dont elle a été
implémentée, mais on utilise uniquement les primitives qui sont
toujours les mêmes. Nous allons étudier l’implémentation des
primitives de gestion des piles.
59
 LES PILES
• IMPLÉMENTATION SOUS FORME DE LISTE CHAÎNÉE
Création d’une structure de donnée
Pour implémenter une pile sous forme de liste chaînée, on
crée la structure de données suivante. Le principe est le
même pour n’importe quel type de données.
typedef float TypeDonnee;
typedef struct Cell
{
TypeDonnee donnee;
struct Cell *suivant; /* pointeur sur la cellule suivante */
}TypeCellule;
typedef TypeCellule* Pile; /* la pile est un pointeur sur la tete de liste */

60
 LES PILES
• IMPLÉMENTATION SOUS FORME DE LISTE CHAÎNÉE
Création d’une pile vide
La fonction permettant de créer une pile vide est la suivante :
Pile Initialiser()
{ return NULL; /* on retourne une liste vide */
}
Pile vide
La fonction permettant de savoir si la pile est vide est la suivante. La fonction
renvoie1 si la pile est vide, et renvoie 0 dans le cas contraire.
int EstVide(Pile P)
{ return (P == NULL) ? 1 : 0;
}
61
 LES PILES
• IMPLÉMENTATION SOUS FORME DE LISTE CHAÎNÉE
Pile pleine
La fonction permettant de savoir si la pile est pleine est la suivante :
int EstPleine(Pile P)
{
return 0; /* une liste chainee n’est jamais pleine */
}

62
 LES PILES
• IMPLÉMENTATION SOUS FORME DE LISTE CHAÎNÉE
Accéder au sommet de la pile
Le sommet de la pile est le dernier élément entré qui est la tête de liste. La
fonction renvoie 1 en cas de liste vide, 0 sinon.
int AccederSommet(Pile P, TypeDonnee *pelem)
{
if (EstVide(P))
return 1; /* on retourne un code d’erreur */
*pelem = P->donnee; /* on renvoie l’element */
return 0;
}

63
 LES PILES
• IMPLÉMENTATION SOUS FORME DE LISTE CHAÎNÉE
Ajouter un élément au sommet
La fonction d’ajout d’un élément est une fonction d’insertion en tête de liste
void Empiler(Pile* pP, TypeDonnee elem)
{
Pile q;
q = (TypeCellule*)malloc(sizeof(TypeCellule)); /* allocation */
q->donnee = elem; /* ajout de l’element a empiler
*/
q->suivant = *pP; /* insertion en tete de liste */
*pP =q; /* mise a jour de la tete de liste
*/
}
64
 LES PILES
• IMPLÉMENTATION SOUS FORME DE LISTE CHAÎNÉE
Ajouter un élément au sommet
La fonction d’ajout d’un élément est une fonction d’insertion en tête de liste
void Empiler(Pile* pP, TypeDonnee elem)
{
Pile q;
q = (TypeCellule*)malloc(sizeof(TypeCellule)); /* allocation */
q->donnee = elem; /* ajout de l’element a empiler
*/
q->suivant = *pP; /* insertion en tete de liste */
*pP =q; /* mise a jour de la tete de liste
*/
}
65
 LES PILES
• Supprimer un élément
La fonction Depiler supprime la tête de liste en cas de pile non vide. La
fonction renvoie 1 en cas d’erreur, et 0 en cas de succès. La pile est passée par
adresse, on a donc un double pointeur.
int Depiler(Pile *pP, TypeDonnee *pelem)
{ Pile q;
if (EstVide(*pP))
return 1; /* on ne peut pas supprimer d’element */
*pelem = (*pP)->donnee; /* on renvoie l’element de tete */
q = *pP; /* memorisation d’adresse de la premiere
cellule */
*pP = (*pP)->suivant; /* passage au suivant */
free(q); /* destruction de la cellule memorisee */
return 0; }
66
 LES PILES
• Vider et détruire
La destruction de la liste doit libérer toute la mémoire de la liste chaînée
(destruction individuelle des cellules).

void Detruire(Pile *pP)

{ Pile q;
while (*pP != NULL) /* parcours de la liste */
{ q = *pP;
*pP = (*pP)->suivant; }
free(q);
*pP = NULL; /* liste vide */
}

67
 LES PILES
void Vider(Pile *pP)
{
Detruire(pP); /* destruction de la liste */
*pP = NULL; /* liste vide */
}
❑COMPARAISON ENTRE TABLEAUX ET LISTES CHAÎNÉES
Dans les deux types de gestion des piles, chaque primitive ne prend
que quelques opérations (complexité en temps constant). Par contre,
la gestion par listes chaînées présente l’énorme avantage que la pile a
une capacité virtuellement illimitée (limitée seulement par la capacité
de la mémoire centrale), la mémoire étant allouée à mesure des
besoins. Au contraire, dans la gestion par tableaux, la mémoire est
allouée au départ avec une capacité fixée.
68
 LES FILES
• Définition
Une file est une structures de données dans laquelle
on peut ajouter et supprimer des éléments suivant la
règle du premier arrivé premier sorti, ou encore
FIFO (First In First Out). Le nom de file vient d’une
analogie avec une file d’attente à un guichet, dans
laquelle le premier arrivé sera le premier servi. Les
usagers arrivent en queue de file, et sortent de la file
à sa tête.

69
 LES FILES
Implémentation d’une file
Une file peut être implémentée par une liste chaînée, ou par
un tableau avec une gestion circulaire. Comme dans le cas
des piles, la gestion par tableaux présente l’inconvénient que
la file a une capacité limitée, contrairement à la gestion par
listes chaînées.

70
 LES FILES
Primitive d’une file
Comme dans le cas des piles, on gère les files à l’aide de primitives. Les
primitives de gestion des files sont les suivantes :
Initialiser : cette fonction crée une file vide.
EstVide : renvoie 1 si la file est vide, 0 sinon.
EstPleine : renvoie 1 si la file est pleine, 0 sinon.
AccederTete : cette fonction permet l’accès à l’information contenue dans la
tête de file.
Enfiler : cette fonction permet d’ajouter un élément en queue de file. La
fonction renvoie un code d’erreur si besoin en cas de manque de mémoire.
Defiler : cette fonction supprime la tête de file. L’élément supprimé est
retourné par la fonction Defiler pour pouvoir être utilisé.

71
 LES FILES
Primitive d’une file
.

Vider : cette fonction vide la file.

Detruire : cette fonction permet de détruire la file.
Comme dans le cas des piles, lorsqu’on utilise une file, on ne
se préoccupe pas de la manière dont elle a été implémentée,
mais on utilise uniquement les primitives qui sont toujours
les mêmes.

72
 ARBRE BINAIRE
Définition
Un arbre binaire fini est un ensemble fini de cellules, chaque cellule
étant liée à 0, 1 ou 2 autres cellules appelées cellules filles. Dans un
arbre, toutes les cellules sauf une ont exactement une cellule mère. Si
l’arbre est non vide, une seule cellule n’a pas de cellule mère, et celle-ci
est appelée racine de l’arbre . Enfin, un arbre est connexe, c’est-à-dire
que toute cellule est descendante de la racine.

73
 ARBRE BINAIRE
Arbre binaire en C
Dans la terminologie des arbres, les cellules sont appelées des nœuds
ou des sommets. Un nœud n’ayant pas de fils s’appelle une feuille. En
langage C, on représente un nœud d’un arbre comme une structure,
chaque nœud contenant deux pointeurs vers les éventuels nœuds fils.
En d’autres termes, un arbre binaire est une structure analogue à une
liste chaînée, sauf que chaque cellule possède deux suivants. Par
convention, on convient d’appeler fils gauche et fils droit les nœuds fils
d’un nœud. Les fils gauche et fils droit d’un nœud peuvent ne pas
exister (pointeur égal à NULL). L’accès à l’arbre est donné par pointeur
qui contient l’adresse de la racine. La structure de données précise pour
représenter un arbre binaire peut être définie comme suit :

74
 ARBRE BINAIRE
Structure données
La structure de données précise pour représenter un arbre binaire peut
être définie comme suit :
typedef int TypeDonnee;
typedef struct cell
{
TypeDonnee donnee;
struct cell *fg, *fd; /* fils gauche et droit */
}TypeNoeud;

75
 ARBRE BINAIRE
Sous-arbre
On appelle sous-arbre d’un nœud N l’arbre dont la racine est N et
dont les nœuds sont les descendants de N. Chaque nœud N
possède aussi un sous-arbre gauche, qui est l’ensemble des
descendants de son fils gauche, et un sous-arbre droit, qui est
l’ensemble des descendants de son fil droit. Les sous-arbres
gauche et droit de l’arbre peuvent être vides si les fils gauche ou
droit du nœud n’existent pas (pointeurs fg ou fd égaux à NULL).

76
 TRAVAUX PRATIQUES
PARTIE 1 : les pointeurs
Afficher l’adresse d’une variables : Ecrire un programme en C dans lequel vous allez
déclarer une variable puis afficher la l’adresse de la variable. Exécuter 5 fois de suite le
programme; que constatez vous ?
Programme qui incrémente un nombre et programme qui échange deux nombres.
Utiliser une fonction qui ne renvoi pas de valeurs dans les 2 cas
Programme qui rempli un tableau et affiche les valeurs. Utiliser une fonction de saisie de
tableau
PARTIE 2 : les structures
Structure sur les nombres complexe
Structure sur les vecteurs (Addition, soustraction, la norme, produit scalaire, produit
vectoriel)
Structure sur le personnel d’une entreprise
PARTIE 3 : les listes chainées
Construire et afficher une liste chainée des articles(code, libelle, prixU, quantite,
montant) d’un magasin

77
 EXERCICE

Soit un nombre complexe Z défini par Z = a + bi .

1- Donner la déclaration d’un nombre complexe en utilisant une structure,
2- Ecrire les fonctions : ReelZ, ImagZ et Module donnant les attributs d'un
nombre complexe respectivement : la partie réelle, la partie imaginaire et le
module),
3- Ecrire les fonctions: SommeZ, DiffZ et ProdZ respectivement pour
l’addition, la soustraction et la multiplication,
4- Ecrire une fonction ConjZ qui calcule le conjugué d’un nombre complexe.
5- Ecrire une fonction EgaleZ qui teste l'égalité de deux nombres complexes.
6- Ecrire une fonction EcrireZ qui permet d’afficher un nombre complexe.

78