Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Algorithmique II
Pr. Ilyass OUAZZANI TAYBI
E-mail : [email protected]
Département : Informatique FSSM
Université Cadi Ayyad
Filière TC-INFO S2
Année universitaire : 2023/2024
Plan du cours
q Rappel (Algorithmique I)
q Tableaux
q Fonctions et procédures
q Récursivité
q Algorithmes de tri
q Pointeurs et Enregistrements
q Fichiers
q Complexité algorithmique
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 2
Plan du cours
CHAPITRE 5 : POINTEURS ET ENREGISTREMENTS
1. Introduction
2. Pointeurs
3. Allocation dynamique
4. Arithmétique des pointeurs
5. Enregistrements
6. Pointeur vers un enregistrement
7. Pointeurs et tableaux
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 3
V. Pointeurs et Enregistrements
1. Introduction
Ø La mémoire centrale utilisée par les programmes est découpée en octets, dont chacun est
représenté par un numéro séquentiel nommé adresse.
Ø Par convention, une adresse est notée en hexadécimal et précédée par 0x.
Mémoire centrale
…
0x4EFA10
0x4EFA11
0x4EFA12 Octet
0x4EFA13
0x4EFA14
0x4EFA15
… 4
V. Pointeurs et Enregistrements
1. Introduction
Ø Déclarer une variable c’est attribuer un identificateur (un nom) à une zone de la mémoire
centrale. Cette zone (1 ou plusieurs octets) est définie par:
Ø Sa position: l’adresse de son premier octet;
Mémoire centrale
Ø Sa taille: le nombre d’octets.
…
Exemple :
0x4EFA10
Variable note : Entier; 0x4EFA11
note ß 16;
0x4EFA12
16 note
0x4EFA13
Par conséquent, on peut accéder à une variable de 2 façons :
0x4EFA14
ü Grâce à son identificateur.
ü Grace à l’adresse du 1er octet de la zone allouée à la variable. 0x4EFA15
…
5
V. Pointeurs et Enregistrements
2. Pointeur
Ø Un pointeur est une variable un peu particulière, car elle ne stocke ni un entier, ni un réel, ni
un caractère, mais une adresse.
Ø Il est tentant de penser qu’une adresse étant un numéro de zone mémoire, elle est
comparable à un entier. Cependant, une adresse ne s’utilise pas comme un entier, puisqu’une
adresse ne peut pas être négative, et ne sert pas à faire des calculs.
Ø Une adresse est donc en ce sens un nouveau type.
6
V. Pointeurs et Enregistrements
2. Pointeur
Ø Etant donné qu’un pointeur est une variable, il possède donc un nom, une valeur (qui est une
adresse) et un type. Il possède en plus une autre caractéristique, qui est son contenu.
Ø Le contenu d’un pointeur est la valeur de la zone mémoire dont ce pointeur stocke l’adresse.
Ø Puisque ces deux notions sont différentes( la valeur et le contenu d’un pointeur), il existe une
nouvelle notation pour indiquer l’accès à un contenu : cette notion est l’opérateur * (lire
étoile).
Ø Une règle très simple et très utile pour l’utilisation de cet opérateur *: il se lit toujours comme
«contenu de», et non pas «pointeur». Cette règle évitera de nombreuses confusions par la
suite.
7
V. Pointeurs et Enregistrements
2. Pointeur – Déclaration –
Syntaxe :
Variable *nomPointeur : Type;
Exemple :
Variable *p_note : Entier;
Remarques :
v Le type d’un pointeur ne décrit pas ce qu’il contient (c’est une adresse, donc en principe d’une
longueur de 32 ou 64 bits selon les architectures), mais le type de la variable qu’il pointe. Un
pointeur sur une variable de type entier devrait donc être déclaré avec un type entier.
v La convention de nommage d’un pointeur veut que son nom débute par p_ ou ptr.
8
V. Pointeurs et Enregistrements
2. Pointeur – Initialisation –
Ø Il existe 3 manières pour initialiser un pointeur :
ü Initialisation avec la constante NIL (Not Identified Link, NULL en C), c-à-d le pointeur ne
pointe sur rien;
ü Initialisation avec l’adresse d’une donnée existante (adresse d’une variable ou valeur d’un
autre pointeur);
ü Initialisation avec l’allocation dynamique de mémoire (ALLOUER);
Ø Pour un pointeur, seule une des trois manières peut être utilisée.
9
V. Pointeurs et Enregistrements
2. Pointeur – Initialisation –
Attention
Ø Les pointeurs sont la source principale d’erreurs durant l’exécution des programmes. Le
problème le plus fréquent, souvent dû à l’absence d’initialisation, est un pointeur qui ne
désigne rien d’utilisable : on parle de pointeur pendant. Il est vital encore plus que pour les
autres types, que les pointeurs soient initialisés. Faites-en une règle.
Ø Toute déclaration de pointeur doit être associée à une initialisation, ou à une affectation
proche. Utilisez NIL si vous ne connaissez pas encore la mémoire pointée au moment de
l’initialisation.
10
V. Pointeurs et Enregistrements
2. Pointeur – Initialisation – Mémoire centrale
Exemple : …
Algorithme exemplePointeur; 0x4EFA10
variables note : Entier; 0x4EFA11
*p_val : Entier; //Déclaration d’une variable pointeur 0x4EFA12
Début 16 note
0x4EFA13
p_val ← Nil; //Initialisation de p_val par Nil
0x4EFA14
note ß 16;
p_val ß ¬e; //Affectation de l’adresse de la variable note 0x4EFA15
//en utilisant l’opérateur adresse (&). 0x4EFA16
Ecrire(p_val); //Affichage de la valeur du pointeur p_val. 0x4EFA17
//La valeur affichée est 0x4EFA11. 0x4EFA11 p_val
0x4EFA18
Ecrire(*p_val); //Affichage du contenu du pointeur p_val.
0x4EFA19
//La valeur affichée est 16.
Fin …
11
V. Pointeurs et Enregistrements
3. Allocation dynamique
Code Instructions du programme
Mémoire
Données statiques
statique
Pile (Stack)
Mémoire Piles d’appels de fonctions
automatique
Tas (Heap)
Mémoire Allocation dynamique de mémoire
dynamique
12
V. Pointeurs et Enregistrements
3. Allocation dynamique
Ø Mémoire statique : zone de la mémoire où sont stockés les données qui ont la même durée
de vie que le programme (e.g. variables globales).
Ø Mémoire automatique : zone de la mémoire appelée Pile d’exécution où sont stockés les
paramètres, les adresses, les valeurs du retour et les variables locales des fonctions empilées.
Cette mémoire est gérée automatiquement par le compilateur (réservation et libération).
Ø Mémoire dynamique : zone de la mémoire appelée Tas dans laquelle le programmeur peut
réserver explicitement de la place. Il devra la libérer explicitement.
13
V. Pointeurs et Enregistrements
3. Allocation dynamique
Ø La déclaration permet d’allouer un emplacement dans la PILE ou dans la mémoire statique.
Les variables déclarées dans la PILE possèdent un nom et leur portée (c-à-d là où elles
peuvent être utilisées) est déterminée par l’endroit où elles sont déclarées. Elles sont crées
dès l’entrée dans la portée et détruites dès la sortie de leur portée.
Ø L’allocation dynamique permet d’allouer un emplacement dans le TAS. Les variables du TAS
ne sont pas déclarées. Elles sont créées par une instruction spécifiques. Elles ne portent pas
de nom, mais on peut y accéder par leurs adresses. Elles peuvent être utilisées partout
jusqu’à leurs destructions.
14
V. Pointeurs et Enregistrements
3. Allocation dynamique
Ø Pour obtenir une zone de mémoire dans le tas, on utilise l’instruction ALLOUER suivi du
pointeur dans lequel on veut stocker l’adresse de la zone mémoire allouée.
Exemple:
Algorithme allocationDynamique;
Variables *p_val : Entier; //Déclaration d’une variable pointeur
Début
ALLOUER (p_val); //Allouer réserve de la mémoire dans le TAS
//p_val contient alors l’adresse de la zone allouée
//NIL si il n’ya plus de mémoire disponible.
Si p_val <> NIL alors //On vérifie si la valeur de p_val est différent de NIL
*p_val ß 20; //On affecte 20 à la zone mémoire allouée dans le TAS
FinSi
Fin
15
V. Pointeurs et Enregistrements
3. Allocation dynamique
Ø Lorsque la place en mémoire dynamique n’est plus utile, on doit la libérer en utilisant
l’instruction LIBERER (pointeur).
Exemple: Algorithme allocationDynamique;
Variables *p_val : Entier; //Déclaration d’une variable pointeur
Début
ALLOUER (p_val); //Allouer réserve de la mémoire dans le TAS
… //p_val contient alors l’adresse de la zone allouée
//NIL si plus de mémoire disponible
Si p_val <> NIL alors //On vérifie si la valeur de p_val est différent de NIL
LIBERER (p_val); //On libère la zone mémoire pointée par p_val
p_val ß NIL; //On affecte NIL à p_val
FinSi
Fin
16
V. Pointeurs et Enregistrements
3. Allocation dynamique
Attention :
Ø Pour prévenir la saturation de la mémoire, il est essentiel de libérer les zones mémoires
allouées dans le TAS une fois qu'elles ne sont plus nécessaires.
Ø il est interdit de :
Ø Libérer un pointeur de valeur NIL;
Ø Libérer une zone mémoire déjà libérée;
Ø Accéder à une zone mémoire libérée;
Ø Libérer de la mémoire allouée automatiquement par le compilateur (variable nommée).
17
V. Pointeurs et Enregistrements
4. Arithmétique de pointeurs
Les seules opérations arithmétiques valides sur les pointeurs sont :
Ø L’addition d’un entier à un pointeur. Le résultat est un pointeur de même type que le
pointeur de départ.
Ø La soustraction d’un entier à un pointeur. Le résultat est un pointeur de même type que le
pointeur de départ.
Ø La différence entre deux pointeurs pointant sur des variables de même type. Le résultat est
un entier.
18
V. Pointeurs et Enregistrements
4. Arithmétique de pointeurs
Ø Si i est un entier et p un pointeur sur une variable de type X, l’expression p+i (resp. p-i)
désigne un pointeur sur une variable de type X dont la valeur de l’adresse est égale l’adresse
de p incrémentée (resp. décrémentée) de i * taille type X. Mémoire centrale
…
Exemple :
Algorithme incrementePointeur; 0x4EFA10
Variables *p_val : Entier; 0x4EFA11
n :Entier 0x4EFA12
Début 20 n
0x4EFA13
n ß 20;
0x4EFA14
P ß &n; //La valeur de p est 0x4EFA11
p ß p+1; // La valeur de p est 0x4EFA15 0x4EFA15
Fin …
19
V. Pointeurs et Enregistrements
5. Enregistrements
Ø Un enregistrement est un type de données défini par le programmeur, permettant de
regrouper un nombre fini d'éléments de types éventuellement différents.
Ø Un enregistrement, appelé aussi structure en analogie avec le langage C, est une variable
complexe qui permet de désigner sous un seul nom un ensemble de valeurs pouvant être de
types différents (simples ou complexes). Champs
Enregistrement
§ Chaque élément de l’enregistrement est appelé champ.
§ L’accès à un champ se fait à travers son nom dans l’enregistrement.
20
V. Pointeurs et Enregistrements
5. Enregistrements – Définition –
Ø Pour définir un enregistrement, il faut en premier lieu lui choisir un nom, puis dresser la liste
de tous les champs que l’on souhaite stocker à l’intérieur de cet enregistrement.
Ø Chacun des champs est identifié par un nom, ce qui permet au programmeur de le choisir
parmi ceux qui sont stockés dans l’enregistrement, et d’un type, pour que le système sache le
manipuler.
Ø Par convention de nommage, un nom d’enregistrement doit systématiquement commencer
par ‘t’ ou ‘t_’.
21
V. Pointeurs et Enregistrements
5. Enregistrements – Définition –
Ø Pour définir un enregistrement on utilise simplement la syntaxe suivante :
nomType = Enregistrement
nomChamp1 : typeChamp1;
nomChamp2 : typeChamp2;
…
nomChampN : typeChampN;
FinEnregistrement
Exemple : t_etudiant = Enregistrement
nom : Chaine de caractères;
prenom : Chaine de caractères;
CNE : Chaine de caractères;
note : Réel;
age : Entier;
FinEnregistrement 22
V. Pointeurs et Enregistrements
5. Enregistrements – Déclaration –
Ø Une fois que l'enregistrement est défini, il peut être utilisé dans un algorithme presque de la
même manière que les types de base de l'algorithmique, tels que les entiers, les réels et les
caractères. Il est notamment possible de déclarer des variables ayant pour type un
enregistrement en suivant la syntaxe classique de déclaration de variables :
Variable nomVar : NomType;
Exemple :
Variable e1, e2 : t_etudiant;
23
V. Pointeurs et Enregistrements
5. Enregistrements – Accès aux champs–
Ø L’opérateur utilisé pour accéder à un champ à partir du nom d’une variable est l’opérateur ‘.’,
dont la syntaxe d’utilisation est la suivante :
nomVar.nomChamp
Ø Cela s’interprète comme : le champ nomChamp de la variable nomVar. Cette écriture est une
expression dont le type est celui du champ référencé.
Exemple :
e1.note
Nom de la variable Nom du champ
24
V. Pointeurs et Enregistrements
5. Enregistrements – Accès aux champs–
Ø L'assignation de valeurs à un champ d'une variable de type enregistrement s'effectue de la
manière suivante : nomVar.nomChamp ß valeur;
Exemple : e1.note ß 16,5;
Ø Utilisation pour une opération de lecture : Lire(nomVar.champ);
Exemple : Lire(e1.note);
Ø Utilisation pour une opération d’écriture : Ecrire(nomVar.champ);
Exemple : Ecrire(e1.note);
25
V. Pointeurs et Enregistrements
5. Enregistrements – Imbrication d’enregistrements –
Supposons que dans le type t_etudiant, nous voulions plus l'âge de l’étudiant, mais sa date de
naissance.
Ø Une date est composée de trois variables (jour, mois, année) indissociables.
Ø Une date correspond donc à une entité du monde réel qu'on doit représenter par un type
enregistrement à 3 champs.
Ø Si on déclare le type date au préalable, on peut l'utiliser dans la déclaration du type
t_etudiant pour le type de la date de naissance.
26
V. Pointeurs et Enregistrements
5. Enregistrements – Imbrication d’enregistrements –
Exemple :
t_date = Enregistrement
jour : Entier;
mois : Entier;
annee : Entier; Remarque :
FinEnregistrement
Pour accéder à l'année de naissance d'un
t_etudiant = Enregistrement étudiant, il faut utiliser deux fois l'opérateur ‘.’:
nom : Chaine de caractères;
prenom : Chaine de caractères; e1.dateNaissance.annee;
CNE : Chaine de caractères;
note : Réel;
dateNaissance : t_date;
FinEnregistrement 27
V. Pointeurs et Enregistrements
5. Enregistrements – Passage en paramètre d'un sous-algorithme –
Ø Il est possible de passer tout un enregistrement en paramètre d'une fonction ou d'une
procédure (on n'est pas obligé de passer tous les champs uns à uns, ce qui permet de
diminuer le nombre de paramètres à passer).
Exemple :
Fonction differenceAge(e1, e2 : t_etudiant): entier
Début
Si (e1.dateNaissance.annee > e2.dateNaissance.annee) Alors
Retourner (e1.dateNaissance.annee – e2.dateNaissance.annee);
Sinon
Retourner (e2.dateNaissance.annee – e1.dateNaissance.annee);
FinSi
FinFonction
28
V. Pointeurs et Enregistrements
6. Pointeur vers un enregistrement
Ø Nous pouvons utiliser un pointeur pour mémoriser l’adresse d’un enregistrement.
Exemple : Variable *p_e : t_etudiant;
Ø Nous pouvons accéder aux champs de l’enregistrement en utilisant les opérateurs ‘*’ et ‘. ’ ou
l’opérateur ‘à’.
Exemple :
Algorithme pointeurEnregistrement; Variable e1, *p_e : t_etudiant;
Type Début
t_etudiant = Enregistrement p_e ← &e1;
nom : Chaine de caractères; e1.prenom ← "Mohammed";
prenom : Chaine de caractères; Ecrire(*p_e.prenom); // ou Ecrire(p_e à prenom)
CNE : Chaine de caractères; Fin
note : Réel;
age : Entier;
FinEnregistrement 29
V. Pointeurs et Enregistrements
6. Pointeur vers un enregistrement
Ø L’opérateur ’à’ n’est pas à proprement parler indispensable, son rôle est de procurer une
syntaxe plus intuitive que le couple ’*’ et ’.’
*PointeurSurEnregistrement.champ PointeurSurEnregistrementàchamp
Exemple :
Variable e1, *p_e : t_etudiant; Variable e1, *p_e : t_etudiant;
Début Début
p_e ← &e1; p_e ← &e1;
*p_e.prenom ← "Mohammed"; p_eàprenom ← "Mohammed";
*p_e.note ← 15,5; p_eànote ← 15,5;
Ecrire(*p_e.prenom); Ecrire(p_eàprenom);
Ecrire(*p_e.note); Ecrire(p_eànote);
Fin Fin
30
V. Pointeurs et Enregistrements
7. Pointeurs et tableaux
Ø Les identificateurs de tableaux et de pointeurs sont très similaires;
Ø L’identificateur d’un pointeur désigne l’adresse du premier octet de la variable sur laquelle
pointe le pointeur;
Ø De même, l’identificateur d’un tableau désigne l’adresse du premier octet du tableau;
Ø Il existe cependant une différence majeure :
Ø La valeur du pointeur peut être modifiée;
Ø L’adresse du tableau ne peut pas être modifiée.
Ø L’identificateur d’un tableau peut être considéré comme un pointeur constant.
31
V. Pointeurs et Enregistrements
7. Pointeurs et tableaux
Tout tableau, en algorithmique (et en C), est en fait un pointeur constant.
Exemple: Variable Tableau T[10] : Entier;
Ø T est un pointeur constant dont la valeur est l’adresse du premier élément (octet) du
tableau;
Ø T est égal à &T[0];
Ø *T est égal à T[0];
Ø *(T+1) est égal à T[1];
Ø *(T+i) est égal à T[i];
32
V. Pointeurs et Enregistrements
7. Pointeurs et tableaux
Nous pouvons manipuler les éléments d’un tableaux à travers un pointeur.
Algorithme pointeurTableau;
Exemple : Variables *p_tab : Entier;
Tableau T[10] :Entier;
Début
p ß T; //On affecte l’adresse du 1er élément du tableau à p
*P ß 15; //T[0]ß15
p ß p+1; // On incrémente la valeur du pointeur
*p ß 20; //T[1]ß20
p ß &T[2]; //On affecte l’adresse du 3ème élément du tableau à p
*pß30; // T[2]ß30
pßT+3; //On affecte l’adresse du 4ème élément du tableau à p
*pß30; // T[3]=30
p ß T; //On affecte l’adresse du 1er élément du tableau à p
*(p+4)ß40; //T[4]ß40
p[5]ß 50; // T[5]ß50
Fin 33
V. Pointeurs et Enregistrements
7. Pointeurs et tableaux
Ø On utilise l’instruction Allouer(p_T, N) pour créer un tableau dynamique de N cases. p_T doit
être déclaré comme un pointeur sur le type des éléments du tableau.
Ø Dans le cas particulier où les éléments du tableau sont des caractères on dit qu’on a fait une
allocation dynamique pour une chaîne de caractères.
Ø L’instruction Allouer(p_T, N) :
Ø Réserve un bloc mémoire pour contenir un tableau de N cases.
Ø Récupère l’adresse du 1er octet de ce tableau et la met dans la variable p_T.
Exemple :
Algorithme tableauDynamique;
Variables *p_T : Entier;
Début
Allouer(p_T, 10); //Tableau 10 entiers
…
Fin
34
V. Pointeurs et Enregistrements
Exercice 1 :
Ecrire un algorithme qui lit le nom, le prénom et la moyenne générale d’un étudiant puis il
affiche si cet étudiant a réussi ou non selon que sa moyenne est >= 10 ou non. Utiliser un
enregistrement pour représenter l’étudiant.
35
Merci de votre
attention
Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 38
Royaume du Maroc
Université Cadi Ayyad
Faculté des Sciences Semlalia
Marrakech
Algorithmique II
Pr. Ilyass OUAZZANI TAYBI
E-mail : [email protected]
Département : Informatique FSSM
Université Cadi Ayyad
Filière TC-INFO S2
Année universitaire : 2023/2024
