Chapitre 8

Structures des données

1
LES ENREGISTREMENTS:
STRUCT

2
Définition de (struct)
struct nom_enreg
{ type champs1;
type champs2;
type champs3;
};

Exemple
struct personne
{ char nom[30];
char prenom [20];
int age;
};
Instanciation de struct
struct nom_enreg vble1, vble2, …, vblen;

Exemple:
struct personne pers1, pers2;

Noter la recommandation du mot clé struct dans

l’instanciation syntaxe un peu lourde
Un typedef allège l’écriture:
typedef struct personne s_pers
….
s_pers pers1, pers2;
Accès aux champs : avec l’opérateur (.)

struct nom_enreg vble1, vble2, …, vblen;

nom_enreg.champs

Exemple:
struct personne pers1, pers2;

pers1.prenom=“Salah”;
pers1.age = 20;
printf(“l’age de M.%s est:%d”, pers1.prenom,pers1.age);
Initialisation des (struct)
Il est possible d’initialiser un enregistrement lors de sa
déclaration
struct nom_enreg {val1, val2, …, valn};
Exemple:
struct pers1 = {“salah”, “ali”, 15}

L’initialisation peut être également par lecture ou bien

par affectation directe
Exemple:
pers1.prenom=“Salah”;
scanf(“%s”, &pers1.prenom);
Tableaux de structures (struct)
Chaque case du tableau contient un élément de type
structure
struct point
{
int absc;
int ord;
};
struct point courbe[50];
/*Accès à l’abscisse de la case de d’indice i*/
courbe[i].absc = 5;

Initialisation lors de la déclaration du tableau

struct point courbe[3]= {{5,2},{6,8},{9,3}};
 Imbrication de structures
struct date
{ int jour;
int mois;
int an;
};
struct personne
{char nom[30];
char prenom [20];
date dat_nais;
};
……
/*saisie de la date d’une vble pers1 */
Scanf("%d%d%d", &pers1.dat_nais.jour, &pers1.dat_nais.mois,
&pers1.dat_nais.an);
Passage d’une structure en paramètre
d’une fonction

Passage par valeur

struct point
{ int absc;
int ord;
};

/* prototype de fonction*/
void fct(struct point y);
 Exemple:
int main()
{ struct p1;
p1.absc = 5; p1.ord = 3;
printf(“valeurs avant appel : %d %d”,
p1.absc, p1.ord);
fct (p1);
printf(“valeurs après appel : %d %d”,
p1.absc, p1.ord);
return 0;
}
void fct (struct point s)
{s.absc = 0; s.ord = 0;}

valeurs avant appel : 5 3 Pas de

valeurs avant appel : 5 3 modification
Passage par valeur: inconvénient

11
Passer une structure par adresse

12
Précautions de passages en paramètres

13
Exemple:
int main()
{ struct p1;
p1.absc = 5; p1.ord = 3;
printf(“valeurs avant appel : %d %d”,
p1.absc, p1.ord);
fct (&p1);
printf(“valeurs après appel : %d %d”,
p1.absc, p1.ord);
return 0;
}
void fct (struct point * s)
{s->absc = 0; s->ord = 0;}

valeurs avant appel : 5 3 Modification

valeurs avant appel : 0 0 effectuée
Résumé

Une variable de type structure peut être :

 Variable locale à une fonction
 Variable globale à un programme
 Retour d’une fonction
 Paramètre d’une fonction
LES UNIONS

16
Les unions

• S’utilisent comme les structures

17
Taille de l’union

18
Utilité

19
Unions et Champs binaires
• Un champ binaire peut être utilisé pour indiquer quelle
information considérer dans l’union;
• Ce champ est défini en tant que structure;
struct flag
{ type nom1 : longueur1
…
type nomn : longueurn
} ;

• nom1, nomn indiquent les noms des champs binaires;

• longueur1 et longueurn indiquent la longueur des
champs en bits (1 bit, 2 bits, etc.).

20
Unions complexes

21
LES ÉNUMÉRATIONS:
ENUM

22
Définition

Le type énuméré enum permet de déclarer des

constantes entières nommées
Ceci donne plus de lisibilité au programmes

23
Déclaration
Syntaxe:
 enum tag {liste_enumeree} liste_variables;
 tag: le nom de l’énumération
 Liste_variables: liste des variables de type tag
 Liste_enumeres: liste de noms énumérées représentant
des constantes entières.
Exemple:
• enum automobile {4chv, 5chv, 6chv};
 Il es possible de définir des variables de type enum ainsi:
• enum automobile japonaise, américaine;
• Équivaut aussi à:
• enum automobile {4chv, 5chv, 6chv} japonaise, américaine;

24
Affecter des valeurs aux noms énumérés
Les éléments des listes énumérées sont incrémentés de 0
à n. Exemple:
o enum automobile {4chv, 5chv, 6chv} japonaise, américaine;
o 4chv = 0, 5chv= 1 et 6chv=1
Il est possible d’affecter d’autres valeurs entières:
o enum automobile {4chv=60, 5chv=30, 6chv=10};
o  4chv représente le nombre 60
o  5chv représente le nombre 30
o  6chv représente le nombre 10
o enum automobile {4chv=60, 5chv=30, 6chv};
o  4chv représente le nombre 60
o  5chv représente le nombre 30
o  6chv représente le nombre 31 31= 30 + 1

25
Exemple

26
Exemple: conversion minuscule majuscule

27
Exemple: conversion minuscule majuscule

28
Exemple: conversion minuscule majuscule

POETE 1
POETE 2
POETE 3

29
TYPEDEF

30
TYPEDEF

31
TYPEDEF

32
LAB_CHAP9

33
Exercice 1

Ecrire un programme en C qui déclare le type

computer défini par un coût, année, vitesse CPU,
type CPU.
Le programme fait appel à deux fonctions permettant
de faire respectivement la saisie et l’affichage des
caractéristiques d’un nombre d’ordinateurs déterminé
par l’utilisateur.

34
Exercice 2
Ecrire un programme qui permet à un utilisateur de
fournir des informations personnelles (nom, âge) ainsi
que des informations sur son téléopérateur (une société
de diffusion par câble ou bien une société de diffusion
par satellite), le nom de la société et le nombre d’heures
consacrées à la télé (par semaine).
Modifiez le programme en ajoutant un champ binaire
concernant le type de connexion

35
LISTES CHAÎNÉES

36
Principe
Pour stocker des éléments de même type, on a
recours aux structures :
 Tableaux ou,
 Listes chaînées

Inconvénients majeurs des tableaux :

 Taille fixe
 Risque de débordement de la taille du tableau
 Coûts de certaines opérations nécessitant un
décalage (insertion, suppression, etc.)

Listes chaînées sont des structures dynamiques de

taille variable
37
Définitions
Listes chaînées : une suite d’éléments appelés nœuds
liés par des liens d’adressage;

Chaque nœud est une structure composée de :

 zone de données : pour stocker l’information

 zone d’adressage : contenant l’adresse du nœud

suivant

Le dernier nœud possède un suivant NULL

A partir du premier nœud, on peut accéder à n’importe

quel autre nœud de la liste grâce au chaînage
Illustration
Pointeur de tête

Données Données Données NULL

suivant suivant suivant

1er nœud 2eme nœud 3eme nœud

Le pointeur tête (ou sommet) est un pointeur vers le

premier élément d’une liste

A partir de l’adresse tête, on peut accéder à n’importe

quel autre nœud grâce au chaînage
Typologie
On distingue 3 types de listes chaînées

 Listes chaînées simples

 Listes chaînées Doubles

 Listes chaînées circulaires

Listes chaînées simples

Chaque nœud dispose d’une seule zone d’adressage :

suivant

Pointeur de tête

Données Données Données NULL

suivant suivant suivant
Listes chaînées Doubles
Chaque nœud dispose de deux zones d’adressage :
précédent et suivant

Pointeur de tête

précédent précédent précédent NULL

NULL
Données Données Données
suivant suivant suivant
Listes chaînées circulaires
Le dernier possède comme suivant le premier élément
Ces listes peuvent être simples ou doubles

Pointeur de tête

Données Données Données

suivant suivant suivant
Opérations de base
Création et Initialisation
Insertion au début
Insertion à la fin
Insertion au milieu
Suppression

44
Création & Initialisation
Exemple
struct person
{ char nom[20];
struct person * suiv;
};

int main()
{ struct person * tete;
/* initialisation d’une liste vide */
tete = NULL;
return 0;
}

Illustration
Pointeur de tête

NULL
45
Insertion au début
Étapes :
1. Création d’une structure en réservant l’espace
mémoire nécessaire avec malloc
2. Mise à jour de la valeur de la zone d’adressage
et la zone de données du nouvel élément
3. Modification du pointeur de tête avec l’adresse
du nouvel élément

struct person * nouv;

……
/*création du nouvel élément */
nouv = (person*) malloc (sizeof(struct person));
/* Mise à jour des pointeurs du chaînage */
nouv->suiv = tete;
Tete = nouv
46
Insertion au début
Il est recommandé de tester le retour de malloc pour
contrôler une allocation de mémoire
Avant Insertion

nouv Pointeur de tête

NULL
Nv_Don info1 info2 info3
suiv suiv suiv suiv

Après Insertion

nouv Pointeur de tête

NULL
Nv_Don info1 info2 info3
suiv suiv suiv suiv
Insertion en queue
Étapes :
1. Création d’une structure en réservant
l’espace mémoire nécessaire avec malloc
2. Mise à jour de la valeur de la zone d’adressage
du dernier élément pour qu’il pointe vers le
nouvel élément
3. Mise à jour de la zone de données et la zone
d’adressage du nouvel élément

48
Insertion en queue
Exemple :

struct person * nouv;

struct person * parc; /* pointeur de parcours de la liste */
……
/*parcours de la liste jusqu’à atteindre le dernier élément*/
parc = tete;
While(parc->suiv != NULL) {parc = parc->suiv;}
nouv = (person*) malloc (sizeof(struct person));
/* Mise à jour des pointeurs */
parc->suiv = nouv;
Nouv ->suiv = NULL;

49
Insertion au milieu
Étapes :
1. Localisation l’élément de la liste après lequel
le nouveau maillon devra être inséré =>
élément de référence
2. Création d’une structure en réservant l’espace
mémoire nécessaire avec malloc
3. Mise à jour de la valeur de la zone
d’adressage de l’élément de référence
4. Mise à jour de la valeur de la zone
d’adressage du nouvel élément

50
Insertion au milieu
Exemple:
struct person * nouv;
struct person * ref;/*pointeur vers l’élément de référence*/
….
/* insérer ici le code nécessaire pour initialiser ref avec l’adresse de
l’élément référence*/
……
/*création du nouvel élément */
nouv = (person*) malloc (sizeof(struct person));
/* Mise à jour des pointeurs */
nouv->suiv = ref->suiv ;
ref->suiv = nouv

51
Suppression d’un élément
Procédure:
Trois cas se présentent selon la position de
l’élément à supprimer:
1. Si premier , modifier le pointeur tête vers le
deuxième élément
2. Si dernier, modifier la zone d’adressage de
l’avant dernier élément
3. Si intermédiaire, modifier la zone d’adressage
de l’élément qui le précède pour le faire pointer
vers l’élément qui le suit

N.B.: La structure à supprimer doit être libérée à la fin

52
Suppression d’un élément
Cas 1: Suppression du 1er élément

struct person * ptr; /* pointeur de sauvegarde*/

……
ptr = tete;
tete = tete->suiv;
free(ptr);/*libération de l’élément en question*/
Suppression d’un élément
Cas 2: Suppression du dernier élément

struct person * prec, *parc; /* 2 pointeurs de parcours avec

prec décalé d’un niveau par rapport à parc*/
prec = tete;
parc = tete -> suiv;
while (parc->suiv != NULL)
{ prec = parc;
parc = parc->suiv;
}
/* MAJ de la zone d’adressage de l’avant dernier*/
prec->suiv = NULL;
/* Libération de l’élément en question*/
free(parc);

54
Suppression d’un élément
Cas 3: Suppression d’un élément intermédiaire

struct person * prec, * parc; /* 2 pointeurs de parcours

avec prec décalé d’un niveau par rapport à parc*/

…… /* insérer le code nécessaire pour que parc pointe sur l’élément

à supprimer et prec sur l'élément précédent */

/* MAJ de la zone d’adressage de l’élément pointé par prec*/

prec->suiv = parc ->suiv;

/* Libération de l’élément en question pointé par parc*/

free(parc);

55
LAB_CHAP9/LISTE_CHAINEE

56
Exercice 1

Implémenter un programme permettant de :

1. Définir une liste chaînée de caractères initialement vide;
2. Insérer un nouvel caractère dans la liste d’une manière triée
(traitement à répéter pour 5 caractères par exemple);
3. Libérer la totalité de la mémoire acquise par la liste
Exercice 2

Implémenter un programme permettant de :

1. Définir la structure Pile d’entiers à l’aide des listes chaînées;
2. Implémenter la méthode Empiler qui permet d’ajouter un nouvel
entier au sommet de la pile;
3. Implémenter la méthode Dépiler qui permet de retirer l’élément
au sommet de la pile ;
4. A quoi correspondent les deux méthodes Empiler et Dépiler dans
le cas des listes chaînées ?
Exercice 3

Implémenter un programme permettant de :

1. Définir la structure File modélisant une file d’attente de fichiers
prêts à être imprimés, et ce à l’aide des listes chaînées;
2. Implémenter la méthode Enfiler qui permet d’ajouter un nouvel
entier à la fin de la file
3. Implémenter la méthode Défiler qui permet de retirer l’élément
au début de la file
4. A quoi correspondent les deux méthodes Enfiler et Défiler dans
le cas des listes chaînées ?