Allocation Mémoire et Gestion des Structures de Données

PROCEDURE Remplir_tab (VAR t : tableau de [1..31] d’entier)

VAR i :entier

DEBUT

Pour i de 1 à 31 faire

Lire(t[i]) ;

Fin_pour

FIN

PROCEDURE afficher_tab (VAR t : tableau de [1..31] d’entier)

VAR i :entier

DEBUT

Pour i de 1 à 31 faire

ecrire(t[i]) ;

Fin_pour

FIN

DEBUT

Ecrire(« saisir les informations sur un employé » ) ;

Lire (emp.cin)

Lire(emp.nom) ;

Pour i de 1 à 31 faire

Lire(emp.heures[i]) ;

Fin_pour

Lire (emp.date_embauche.jour) ;

Lire (emp.date_embauche.mois) ;

Lire (emp.date_embauche.annee) ;

Ecrire(« Les informations sur l’employé sont » ) ;

Ecrire (emp.cin)

Ecrire (emp.nom) ;

Pour i de 1 à 31 faire

Ecrire (emp.heures[i]) ;

Fin_pour

Ecrire (emp.date_embauche.jour) ;

Ecrire (emp.date_embauche.mois) ;

Ou bien

Remplir_tab(emp.heures) ; // appel

de la procédure Remplir_tab qui permet de

remplir un tableau par des entiers

Ou bien

afficher_tab(emp.heures) ; // appel

de la procédure afficher_tab qui permet

d’afficher un tableau d’ entiers

Mme Wiem Yaiche Elleuch

Page 4

Ecrire (emp.date_embauche.annee) ;

FIN

Exemple 2 : Ecrire un algorithme qui remplit et affiche un tableau de n employés

ALGORITHME exemple2

EMPLOYE =enregistrement

Cin :entier

Nom : chaine

Heures : tableau de [1..31] d’entier

Date_embauche : DATE

Fin_enregistrement

TAB_EMP : tableau de [1..50] de EMPLOYE.

VAR

i , j: entier ;

t : TAB_EMP ;

DEBUT

Ecrire(« Remplissage du tableau d’employés » ) ;

Pour i de 1 à n faire

Lire (t[i].cin)

Lire(t[i].nom) ;

Pour j de 1 à 31 faire

Lire(t[i].heures[j]) ;

Fin_pour

Lire (t[i].date_embauche.jour) ;

Lire (t[i].date_embauche.mois) ;

Lire (t[i].date_embauche.annee) ;

Fin_pour

Ecrire(« Affichage du tableau d’employés » ) ;

Pour i de 1 à n faire

Ecrire (t[i].cin)

Ecrire (t[i].nom) ;

Pour j de 1 à 31 faire

Ecrire (t[i].heures[j]) ;

Fin_pour

Ecrire (t[i].date_embauche.jour) ;

Ecrire (t[i].date_embauche.mois) ;

Ecrire (t[i].date_embauche.annee) ;

Fin_pour

FIN

Ou bien

Remplir_tab(t[i].heures) ; // appel de

la procédure Remplir_tab de exemple1

Ou bien

afficher_tab(t[i].heures) ; // appel de

la procédure afficher_tab de exemple1

5. Enregistrement et fonction, enregistrement et procedure

(cid:4) Les mêmes principes de passage par valeur et passage par adresse s’appliquent aux

variables enrregistrements

Exemple : Réécrire l’algorithme de l’exemple 1 (saisir et afficher les informations sur un

employé), en utilisant des procedures ou des fonctions.

Mme Wiem Yaiche Elleuch

Page 5

ALGORITHME exemple1_version2

EMPLOYE =enregistrement

Cin :entier

Nom : chaine

Heures : tableau de [1..31] d’entier

Date_embauche : DATE

Fin_enregistrement

VAR

emp : EMPLOYE

PROCEDURE Remplir_un_employe (VAR emp : EMPLOYE) // passage par adresse

DEBUT

Lire (emp.cin)

Lire(emp.nom) ;

Remplir_tab(emp.heures) ;

Lire (emp.date_embauche.jour) ;

Lire (emp.date_embauche.mois) ;

Lire (emp.date_embauche.annee) ;

// procédure développée ci dessus

FIN

FONCTION Remplir_un_employe_2() : EMPLOYE

VAR emp :EMPLOYE

DEBUT

Lire (emp.cin)

Lire(emp.nom) ;

Remplir_tab(emp.heures) ;

Lire (emp.date_embauche.jour) ;

Lire (emp.date_embauche.mois) ;

Lire (emp.date_embauche.annee) ;

Retourner emp ;

FIN

PROCEDURE Afficher_un_employe (emp : EMPLOYE) //passage par valeur

DEBUT

Ecrire (emp.cin) ;

Ecrire (emp.nom) ;

afficher_tab(emp.heures) ;

Ecrire (emp.date_embauche.jour) ;

Ecrire (emp.date_embauche.mois) ;

Ecrire (emp.date_embauche.annee) ;

// procédure développée ci dessus

FIN

DEBUT

Ecrire(« saisir les informations sur un employé » ) ;

// procedure

Remplir_un_employe (emp)

// ou bien

emp(cid:3) Remplir_un_employe_2

Afficher_un_employe(emp)

FIN

//fonction

Mme Wiem Yaiche Elleuch

Page 6

6. Pointeur et enregistrement

Un pointeur sur enregistrement est déclaré de la manière suivante :

Nom_pointeur : pointeur sur type

Exemple :

emp : EMPLOYE ;

p : pointeur sur EMPLOYE ;

p(cid:3) &emp ;

// variable emp de type EMPLOYE

// p est un pointeursur une variable de type EMPLOYE

p

F800

F800

emp

cin

nom

heures

jour

mois

annee

Date_embauche

F800

F820

F850

F940

Il est possible d’accèder aux différents champs (cin, nom, etc) en utilisant la variable emp ou

bien le pointeur p.

Avec la variable emp, l’accès aux différents champs se fait en utilisant (.).

Exemple : emp.cin ; emp.date_embauche.jour ; etc

Avec le pointeur p, l’accès aux différents champs se fait généralement en utilisant ((cid:6)).

Exemple : p(cid:6)cin ; p(cid:6)date_embauche.jour ; etc

Ou bien (p).cin ; (p).date_embauche.jour

Remarque :

*p : représente le contenu de la variable pointée par p (c’est la variable emp).

=> (*p (cid:7) emp) ;

Mme Wiem Yaiche Elleuch

Page 7

Allocation de la mémoire

Problème

• Souvent, nous devons travailler avec des données dont nous ne pouvons pas prévoir le

nombre.

• Ce serait alors un gaspillage de réserver toujours l'espace maximal prévisible.

•

Il faut donc un moyen de gérer la mémoire lors de l'exécution du programme.

La fonction allouer

• La fonction allouer permet de localiser et de réserver de la mémoire au cours d'un

algorithme.

• La fonction allouer retourne l'adresse d'un bloc en mémoire libre ou la valeur NIL s'il n'y a

pas assez de mémoire.

• D’une manière générale

P : pointeur sur TYPE

P (cid:3) allouer ( n * TYPE)

(cid:1) Crée un tableau de n éléments.

(cid:1) Chaque élément est de type TYPE.

(cid:1) P contient l’adresse de début de l’espace alloué en mémoire

Exemple 1:

P : pointeur sur entier

P(cid:3) allouer (3* entier) ;

=> création d’un tableau de 3 entiers

=> cet espace alloué s’étend sur les adresses F800, F810 et F820

=> p reçoit l’adresse de début : F800

=> (p) ou ((p+0)) représentent le 1er élément du tableau : 3

=> (*(p+1)) : représente le 2ème élément du tableau : 6

=> (*(p+i)) : représente le (i+1)ème élément du tableau

p

F800

3

6

2

F800

F810

F820

Exemple 2 :

P : pointeur sur EMPLOYE

P(cid:3) allouer (3* EMPLOYE) ;

(cid:1) Création d’un tableau pour 3 employés

(cid:1) L’adresse de début de cet espace alloué (F800) est affectée à P.

Mme Wiem Yaiche Elleuch

Page 8

p

F800

Employé 1

Employé 2

Employé 3

Cin nom heures date_embauche

Cin nom heures date_embauche

Cin nom heures date_embauche

F800

F850

F900

(p) ou ((p+0)): représente l’employé 1 (cin, nom, heures et date_embauche), de type

EMPLOYE.

*(p+1) : représente l’employé 2.

*(p+i) : représente l’employé i+1.

*(p).cin ou bien p->cin: représente le cin du 1er employé du tableau

*(p).date_embauche.jour ou bien p->date_embauche.jour : représente le jour de la date

d’embauche du 1er employé du tableau

*(p+0).cin ou bien (p+0)->cin: représente le cin du 1er employé du tableau

*(p+0).date_embauche.jour ou bien p+0->date_embauche.jour : représente le jour de la

date d’embauche du 1er employé du tableau

*(p+1).cin ou bien (p+1)->cin: représente le cin du 2ème employé du tableau

*(p+1).date_embauche.jour ou bien p+1->date_embauche.jour : représente le jour de la

date d’embauche du 2ème employé du tableau

*(p+i).cin ou bien (p+i)->cin: représente le cin du (i+1)ème employé du tableau

*(p+i).date_embauche.jour ou bien (p+i)->date_embauche.jour : représente le jour de la

date d’embauche du (i+1)ème employé du tableau

La procédure libérer

• Si nous n'avons plus besoin d'un bloc de mémoire que nous avons réservé à l'aide de la

fonction allouer, alors nous pouvons le libérer à l'aide de la procédure libérer

libérer (P) ; libère le bloc de mémoire désigné par le pointeur (P);

•

• La procédure libérer ne change pas le contenu du pointeur; il est conseillé d'affecter la

valeur NIL au pointeur immédiatement après avoir libéré le bloc de mémoire qui y était

attaché.

• Avec procédure libérer, on ne peut pas libérer une partie de l’espace alloué.

P : pointeur sur TYPE

P (cid:3) allouer ( n * TYPE)

…….

libérer (P) ;

P(cid:3) NIL ;

Mme Wiem Yaiche Elleuch

Page 9

Tableau de pointeurs sur enregistrements

ETUDIANT= enregistrement

cin : entier

nom : chaine

moy : réel

Fin_enregistrement

tab : tableau de [1..3] de pointeur sur ETUDIANT

tab

F800 F100 F500

étudiant1

étudiant2

étudiant3

11 abc 15.8

12 def 17.9

13 ghi 12.3

Cin nom moy

Cin nom moy

Cin nom moy

F800

F100

F500

tab est un tableau de 3 pointeurs sur ETUDIANT.

Chaque élément du tableau tab contient l’adresse d’un étudiant.

F800 est l’adresse de l’étudiant1. F100 est l’adresse de l’étudiant2. etc

tab[1] : F800.

*(tab[1]) : l’étudiant1 ayant comme adresse (tab[1] :F800). C’est tout l’enregistrement

(11,abc,15.8).

tab[2] : F100.

*(tab[2]) : l’étudiant2 (12,def,17.9).

tab[1]->cin : cin de l’étudiant1

tab[2]->moy : moyenne de l’étudiant2

d’une manière générale :

tab[i] : l’adresse de l’étudiant i.

*(tab[i]) : l’étudiant ayant comme adresse (tab[i]) : tout l’enregistrement (cin, nom, moy).

tab[i]->champ : correspond au champ de l’étudiant i.

ALGORITHME tableau_pointeur

TYPE

ETUDIANT= enregistrement

cin : entier

nom : chaine

moy : réel

Fin_enregistrement

Tab_point : tableau de [1..50] de pointeur sur ETUDIANT

Mme Wiem Yaiche Elleuch

Page 10

VAR

i,n :entier

tab : Tab_point ;

DEBUT

Lire(n) ;

pour i de 1 à n faire

tab[i]<- allouer (ETUDIANT) ;

lire(tab[i]->cin) ; // ou bien lire(*(tab[i]).cin) ;

lire(tab[i]->nom) ; // ou bien lire(*(tab[i]).nom) ;

lire(tab[i]->moy) ; // ou bien lire(*(tab[i]).moy) ;

fin_pour ;

ecrire (« affichage des étudiants ») ;

pour i de 1 à n faire

écrire(tab[i]->cin) ; // ou bien écrire(*(tab[i]).cin) ;

écrire (tab[i]->nom) ; // ou bien écrire(*(tab[i]).nom) ;

écrire (tab[i]->moy) ; // ou bien écrire(*(tab[i]).moy) ;

fin_pour ;

FIN

Tableau de pointeurs sur tableaux d’enregistrements

tab

F800 F100 F500

étud1 étud2

étud3 étud4 étud5

étud6 étud7 étud8 étud9

cin nom moy cin nom moy

cin nom moy cin nom moy cin nom moy

cin nom moy cin nom moy cin nom moy cin nom moy

F800

F810

F100

F110

F120

Tableau de 2 étudiants (p=2)

Tableau de 3 étudiants (p=3)

F500

F510

F520

F530

Tableau de 4 étudiants (p=4)

Dans ce schéma, il y a 9 étudiants (étud1…étud9)

tab est un tableau de pointeurs sur ETUDIANT.

Plusieurs appellations sont possibles :

•

•

•

tab[1] : contient l’adresse de début (F800) d’un tableau de 2 étudiants.

tab[1] pointe sur un tableau de 2 étudiants.

tab[1] est un pointeur sur un tableau de 2 étudiants

tab[1] ou (tab[1]+0) => F800

(tab[1]) ou (tab[1]+0) => étud1 (tout l’enregistrement étud1 : cin, nom, moy)

tab[1]->cin ou (tab[1]+0)->cin => cin de étud1

(tab[1]) .cin ou (tab[1]+0).cin => cin de étud1

**

Mme Wiem Yaiche Elleuch

Page 11

tab[1] +1 : F810

*( tab[1] +1 ) : étud2 (tout l’enregistrement étud2 : cin, nom, moy)

(tab[1] +1)-> cin : cin de étud2

*( tab[1] +1 ).cin : cin de étud2.

**

tab[2] ou tab[2]+0 => F100

(tab[2]) ou (tab[2]+0) => étud3 (tout l’enregistrement étud3 : cin, nom, moy)

tab[2]->cin ou (tab[2]+0) ->cin => cin de étud3

(tab[2]) .cin ou (tab[2]+0).cin =>cin de étud3

**

tab[2] +1 => F110

*( tab[2] +1 ) => étud4 (tout l’enregistrement étud4 : cin, nom, moy)

(tab[2] +1)-> cin => cin de étud4

*( tab[2] +1 ).cin => cin de étud4.

*

tab[3] +3 => F530

*( tab[3] +3 ) => étud9 (tout l’enregistrement étud9 : cin, nom, moy)

(tab[3] +3)-> cin => cin de étud9

*( tab[3] +3 ).cin => cin de étud9.

D’une manière générale :

tab[i] +j => représente l’adresse du ((j+1)ème étudiant du tableau dont l’adresse de début se

trouve dans le ième élément du tableau tab.

*(tab[i] +j) => représente le ((j+1)ème étudiant du tableau dont l’adresse de début se trouve

dans le ième élément du tableau tab.

(tab[i] +j)->champ => représente le champ du ((j+1)ème étudiant du tableau dont l’adresse de

début se trouve dans le ième élément du tableau tab.

*(tab[i] +j).champ => représente le champ du ((j+1)ème étudiant du tableau dont l’adresse

de début se trouve dans le ième élément du tableau tab.

ALGORITHME tableau_pointeur_tableau

TYPE

ETUDIANT= enregistrement

cin : entier

nom : chaine

moy : réel

Fin_enregistrement

Tab_point : tableau de [1..50] de pointeur sur ETUDIANT

VAR

i,j,n,p :entier

tab : Tab_point ;

DEBUT

Lire(n) ; // n représente la taille du tableau n

pour i de 1 à n faire

lire(p) // p représente la taille des tableaux d’étudiants (voir schémà).

Mme Wiem Yaiche Elleuch

Page 12

tab[i]<- allouer (p * ETUDIANT) ;

pour j de 0 à p-1 faire

lire (tab[i] +j)->cin)

lire (tab[i] +j)->nom)

lire (tab[i] +j)->moy)

fin_pour

fin_pour

ecrire (« affichage des étudiants ») ;

pour i de 1 à n faire

pour j de 0 à p-1 faire

ecrire (tab[i] +j)->cin)

ecrire (tab[i] +j)->nom)

ecrire (tab[i] +j)->moy)

fin_pour

fin_pour

FIN

Exercice d’application (de la série):

Un étudiant est caractérisé par : cin, nom, date de naissance et moyenne. Ecrire un algorithme

qui remplit et affiche un tableau de n étudiants, ensuite affiche les informations sur l’étudiant

ayant la meilleure moyenne et l’étudiant ayant la plus mauvaise moyenne. Afficher le nombre

d’étudiants ayant une moyenne supérieure ou égale à 10.

Utiliser un tableau statique, ensuite un tableau dynamique.

Utiliser les fonctions et/ou les procédures.

Version utilisant un tableau statique

ALGO ex1_tab_stat

TYPE

TJOUR :1..31

TMOIS : 1..12

TANNEE : 1900..2100

DATE= enregistrement

Jour : TJOUR

Mois : TMOIS

Annee : TANNEE

Fin_enregistrement

ETUDIANT= enregistrement

Cin : entier

Nom : chaine

Date_naiss : DATE

Moy : réel

Fin_enregistrement

TE : tableau de [1..50] d’ETUDIANT

VAR : meilleur : ETUDIANT

mauvais : ETUDIANT

nb_etud,n : entier

t : TE

PROCEDURE remplir_un_etudiant (VAR e :ETDUDIANT)

// passage par adresse

Mme Wiem Yaiche Elleuch

Page 13

DEBUT

Lire(e.cin)

Lire(e.nom)

Lire(e.date_naiss.jour)

Lire(e.date_naiss.jour)

Lire(e.date_naiss.jour)

Lire(e.moy)

FIN

FONCTION remplir_un_etudiant_2(): ETUDIANT

VAR : e :ETUDIANT

DEBUT

Lire(e.cin)

Lire(e.nom)

Lire(e.date_naiss.jour)

Lire(e.date_naiss.jour)

Lire(e.date_naiss.jour)

Lire(e.moy)

Retourner e ;

FIN

PROCEDURE Remplir(VAR t :TE, n :entier)

DEBUT

Pour i de 1 à n faire

remplir_un_etudiant(t[i]) //ou bien t[i](cid:3)remplir_un_etudiant_2()

// remplir_un_etudiant est une procédure, remplir_un_etudiant_2 est une fonction

Fin_pour

FIN

PROCEDURE afficher_un (e :ETUDIANT)

DEBUT

// passage par valeur

ecrire(e.cin)

ecrire (e.nom)

ecrire (e.date_naiss.jour)

ecrire (e.date_naiss.jour)

ecrire (e.date_naiss.jour)

ecrire (e.moy)

FIN

PROCEDURE afficher (VAR t :TE, n : entier)

DEBUT

Pour i de 1 à n faire

Afficher_un (t[i])

(t :TE,n :entier, VAR meilleur :ETUDIANT, VAR mauvais :ETUDIANT, VAR

Fin_pour

FIN

PROCEDURE chercher

nb_etud :entier)

VAR i : entier

DEBUT

Nb_etud(cid:3)0 ;

Meilleur(cid:3)t[1] ;

Mauvais(cid:3)t[1] ;

Pour i de 2 à n faire

SI (t[i].moyenne>=meilleur.moyenne) alors meilleur(cid:3)t[i]

FIN_SI

SI (t[i].moyenne<=mauvais.moyenne) alors mauvais(cid:3)t[i]

FIN_SI

Si (t[i].moyenne>=10) alors nb_etud(cid:3)nb_etud+1

FIN_SI

Mme Wiem Yaiche Elleuch

Page 14

Fin_pour

Si (t[1].moyenne>=10) alors nb_etud(cid:3)nb_etud+1

FIN_SI

// le parcours du tableau a commencé à partir du 2ème élément, donc il faut faire un test sur le 1er

FIN

PROCEDURE resultat (meilleur : ETUDIANT, mauvais : ETUDIANT, nb_etud : entier)

DEBUT

Afficher_un(meilleur) ;

Afficher_un(mauvais) ;

Ecrire(nb_etud) ;

FIN

// appel de la procedure afficher_un développée ci dessus

DEBUT

Ecrire(« saisir nbre etudiants ») ;

Lire(n) ;

Remplir(t,n) ;

Afficher(t,n) ;

Chercher(t,n,meilleur,mauvais,nb_etud)

resultat(meilleur, mauvais, nb_etud)

FIN

Version utilisant un tableau dynamique

ALGO ex1_tab_dynamique

TYPE

TJOUR :1..31

TMOIS : 1..12

TANNEE : 1900..2100

DATE= enregistrement

Jour : TJOUR

Mois : TMOIS

Annee : TANNEE

Fin_enregistrement

ETUDIANT= enregistrement

Cin : entier

Nom : chaine

Date_naiss : DATE

Moy : réel

Fin_enregistrement

// on ne déclare pas un tableau

VAR : meilleur : ETUDIANT

mauvais : ETUDIANT

nb_etud,n : entier

p : pointeur sur ETUDIANT

PROCEDURE Remplir_dyn (p :pointeur sur ETUDIANT, n :entier)

DEBUT

Pour i de 0 à n-1 faire

// il faut commencer à partir de 0 parceque (p+0) (cid:7) p représente le premier étudiant du tableau

Remplir_un_etudiant ((p+i)) // ou bien (p+i)(cid:3)remplir_un_etudiant2()

// appel de la procédure Remplir_un_etudiant et de la fonction remplir_un_etudiant2 développées ci-dessus pour tableau

statique

Fin_pour

FIN

Ou bien

PROCEDURE Remplir_dyn (p :pointeur sur ETUDIANT, n :entier)

DEBUT

Mme Wiem Yaiche Elleuch

Page 15

Pour i de 0 à n-1 faire

Lire((p+i)->cin)

Lire((p+i)->nom)

Lire((p+i)->date_naiss.jour)

Lire(((p+i)->date_naiss.mois)

Lire(((p+i)->date_naiss.annee)

Lire((p+i)->moy)

FIN

PROCEDURE afficher (p :pointeur sur ETUDIANT, n : entier)

DEBUT

Pour i de 0 à n-1 faire

Afficher_un (*(p+i))

Fin_pour

FIN

PROCEDURE

chercher

mauvais :ETUDIANT, VAR nb_etud :entier)

(p :pointeur

sur ETUDIANT, n :entier, VAR meilleur :ETUDIANT, VAR

DEBUT

VAR i : entier

Nb_etud(cid:3)0 ;

Meilleur(cid:3)*p ;

Mauvais(cid:3)*p ;

// *p représente le 1er étudiant du tableau

Pour i de 1 à n faire

// on commence le parcours à partir du 2ème étudiant : *(p+1)

SI ((p+i)->moyenne>=meilleur.moyenne) alors meilleur(cid:3)*(p+i) ;

FIN_SI

//Ou bien SI ((p+i).moyenne>=meilleur.moyenne) alors meilleur(cid:3)(p+i) ;

FIN_SI

SI ((p+i)->moyenne<=mauvais.moyenne) alors mauvais(cid:3)*(p+i) ;

FIN_SI

Si ((p+i)->moyenne>=10) alors nb_etud(cid:3)nb_etud+1

FIN_SI

Fin_pour

Si (p->moyenne>=10) alors nb_etud(cid:3)nb_etud+1

FIN_SI // il faut faire un test sur le 1er étudiant puisque le parcours du tableau a commencé à partir du 2ème étudiant

FIN

DEBUT

Ecrire(« saisir nbre etudiants ») ;

Lire(n) ;

p(cid:3) allouer (n* ETUDIANT) ;

Remplir_dyn (p, n) ;

Afficher_dyn(p,n) ;

Chercher_dyn (t,n,meilleur,mauvais,nb_etud)

resultat(meilleur, mauvais, nb_etud)

FIN

// même procédure resultat pour tableau statique

Mme Wiem Yaiche Elleuch

Page 16