‫الجمهورية الجزائرية الديمقراطية الشعبية‬

‫وزارة التكوين و التعليم المهنيين‬

 Avant Propos
Ce polycopié est structuré en huit chapitres comme suit :

Dans le premier chapitre, des notions de base sur la structure globale

d’un algorithme sont données, ainsi que les différentes parties qui le
composent suivie par les instructions de base les plus élémentaires.

Le deuxième chapitre décrit en détails les différentes structures de

contrôles (boucles) qui peuvent être utilisées dans un algorithme (ex. Pour,
tant que, ..).

Le chapitre trois aborde l’utilisation des tableaux dans la programmation.

Le quatrième chapitre est consacré aux sous programmes (fonctions et

procédures). Dans le cinquième chapitre, l’utilisation des enregistrements
et des fichiers dans le cadre de l’algorithmique est expliquée.

Le sixième chapitre traite la récursivité afin de faciliter l’écriture des

algorithmes qui peuvent être récursifs. Dans le septième chapitre, nous
avons illustré comment calculer la complexité algorithmique de n’importe
quel algorithme.

Enfin, le chapitre huit est consacré à la programmation dynamique. La

notion de pointeur est illustrée. Des modèles de programmation pour les
listes linéaires chainée, les files, les piles ainsi que les arbres sont donnés.
Chapitre 1 : Généralités et Notions de Base 4

Chapitre 2 : Les Structures de Contrôle 12

Chapitre 3 : Les Tableaux 17

Chapitre 4 : Les Fonctions et les Procédures 20

Chapitre 5 : Les Enregistrements et les Fichiers 24

Chapitre 6 : La Récursivité 30

Chapitre 7 : La Complexité Algorithmique 35

Chapitre 8 : Les Pointeurs 39

Références bibliographiques 54
 Chapitre 1:
Généralités et Notions de Base

1. Introduction

L'algorithmique est l'étude des algorithmes. Un algorithme est une méthode permettant de
résoudre un problème donne en un temps fini ;

Un algorithme est une suite de raisonnements ou d'opérations qui fournit la solution

d'un problème. Le programme ne sera que la traduction de l'algorithme dans un langage de
programmation, c'est-à-dire, un langage plus simple que le français dans sa syntaxe, sans
ambiguïtés, que la machine peut utiliser et transformer pour exécuter les actions qu'il peut
décrire. Pascal, C, Java et Visual Basic sont des noms de langages de programmation.

 Réalisation d’un programme

La réalisation d'un programme passe par l'analyse descendante du problème : il faut réussir
à trouver les actions élémentaires qui, en partant d'un environnement initial, nous conduisent à
l'état final. Une fois ces actions déterminées, il suffit de les traduire dans le langage de
programmation choisi.

Durant l'écriture d'un programme, on peut être confronté à 2 types d'erreur :

Les erreurs syntaxiques : elles se remarquent à la compilation et sont le résultat d'une

mauvaise écriture dans le langage de programmation.
Les erreurs sémantiques : elles se remarquent à l'exécution et sont le résultat d'une
mauvaise analyse. Ces erreurs sont beaucoup plus graves car elles peuvent se
déclencher en cours d'exploitation du programme.

Page 4
 Chapitre 1:
2. Base d’un langage algorithmique
Le langage algorithmique est un langage générique permettant de traiter tous type de
problème par la concaténation des instructions.

2.1. Structure de Base

La structure générale d’un algorithme (Programme) est la suivante :

Algorithme Nom-d’Algorithme ;

déclaration des variables et des constantes

Déclaration des fonctions

Début

. …..

Liste des instructions

. ………..

Fin.

2.2. Variables et constantes

Une variable est un espace mémoire nommé de taille fixe, prenant au cours de
déroulement de l’algorithme un nombre indéfini de valeurs différentes. Ce changement de
valeur se fait par l’opération d’affectation notée (←). La variable diffère de la notion de
constante qui, comme son nom l’indique, ne prend qu’une valeur unique au cours de
l’exécution de l’algorithme.

La partie déclaration permet de spécifier quelles seront les variables utilisées au cours de
l’algorithme ainsi que le type de valeur quelles doivent respectivement prendre.

Parmi les types des variables les plus utilisés, on trouve :

Page 5
 Chapitre 1:
2.2.1. Entier : (1,2, 3,….)
Le type entier caractérise l’ensemble des nombres entiers. Les opérations arithmétiques
possibles sur ce type sont : L’addition ‘+’, ‘-‘, ‘*’, ‘/’. Appliquées sur des opérandes de type
entier, elles fournissent un résultat entier sauf l’opération ‘/’ qui fournit un résultat réel.

Tandis que les opérations de relation notées par ‘<’, ‘>’, ‘>=’, ‘<=’, ‘<>’ fournissent un
résultat logique.

Exemples :

Const x = 1 ;

Var A : entier ;

Var A, b : entier ;

Var coefficient_module : entier ;

2.2.2. Réel : (flottant : 1.0, 1.35, 1E+12, …)

Représente l’ensemble des nombres réels. Les opérations ‘+’,’-‘, ‘*’, ‘/’ appliqués sur des
opérandes de type réel fournissent un résultat de type réel.

Exemples

Var A : réel ;

Var A, b : réel ;

Var moyen_générale : réel ;

2.2.3. Caractère : (A, a, Z, …)

Ce type englobe tous les caractères nécessaires à l’écriture de texte.

Exemples :

Const x = 1.1 ;

Var A : Caractère ;

Page 6
 Chapitre 1:
Var A, b : Caractère ;

Var xxxxxxxxxxxx : Caractère;

2.2.4. Booléen : (Vrai, Faux)

Ce type de variable ne peut prendre que les valeurs vrai ou faux. Les opérateurs logiques ET,

OU, NON, appliqués à des opérandes de type booléen fournissent un résultat booléen.

Exemples :

Const x = ‘a’ ;

Var A : Booléen ;

Var A, b : Booléen;

Var Admis : Booléen;

2.3. Identificateurs et mots clés

 Un identificateur est le nom d’une variable, d’une constante ou le nom d’un
algorithme (programme), c’est un seul mot composé de chiffres et des caractères à
l’exception de quelques uns.
 Un mot clé est un mot réservé, il a une utilisation spéciale dans un programme comme
par exemple : program, begin, end, if, else, case, repeat, until, for, do, while, then, var,

 Règles d’écriture des identificateurs

1. Un identificateur ne peut être un mot clé

2. Un identificateur doit commencer par un caractère alphanumérique

3. Un identificateur ne doit pas contenir des caractères spéciaux comme : ?, !, *, …

Exemple

Quels sont les identificateurs valides et ceux qui ne sont pas valides ?

Page 7
 Chapitre 1:
M, ax, 8b, s_m, farid, exo1, exo ?, 34, then, nom programme, ….

2.4. Instructions
Une instruction est une action élémentaire commandant à l’ordinateur un calcul, une
instruction de base peut être :

A : Une affectation ou une opération arithmétique

L’affectation est l’action élémentaire principale puisque c’est par son intermédiaire

que l’on peut modifier la valeur d’une variable, elle a pour syntaxe : Variable← valeur ou
variable ←expression ;

Exemple

Algorithme exemple-Affectation ;

Var A, B : Entier ;

Debut

………………..

A←10 ;

B← A+15 ;

Fin.

B : Cas d’utilisation d’une affectation

 Pour modifier la valeur d’une variable

…

A_10 ;

B_5 ;

A_A+B ;

Page 8
 Chapitre 1:
 Pour affichage sur écran
L’affichage est l’action élémentaire permettant à un algorithme de fournir des résultats à
l’utilisateur, il se fait par l’intermédiaire de la commande (Fonction) Ecrire.

A_10 ;

B _5 ;

C_A+B ;

Ecrire (« j’ai calculé la somme de A+B ») ;

 Pour une lecture au clavier

La lecture au clavier est une action élémentaire permettant de spécifier par une intervention
humaine la valeur d’une variable. La saisie se fait par l’intermédiaire de la commande

(Fonction) Lire.

A_10 ;

Lire (B) ;

C_A+B ;

Exercice 1 : (Savoir déchiffrer une séquence d’instructions)

Dite que fait l’ensemble des instructions suivantes

A_1 ;

B_10 ;

Page 9
 Chapitre 1:
C_A*2+B-3 ;

Ecrire (C) ;

….

2.5. Commentaires
Un commentaire est un texte facultatif (des phrases) situé entre les symboles et { et } qui n’a
aucun effet sur le fonctionnement du l’algorithme. Elle sert à expliquer le pourquoi de
certaines instructions utilisés dans un programme.

Exemple

Algorithme exo ;

Var A : entier ;

Debut

/* ce programme calcul la somme de deux nombre*/

Lire (A) ;

Lire (B) ;

C :=A+B ;

Ecrire (C) ;

Fin.

2.6. Expressions
Une expression est une combinaison de plusieurs opérandes (éventuellement des fonctions) et
opérandes. Ils existent plusieurs types d’expressions :

 Les expressions arithmétiques

Elles font intervenir les operateurs arithmétiques (+, -, /, *) ainsi que les deux operateurs DIV
et MOD.

Page
10
 Chapitre 1:
Exemple : a + b – c/d est une expression arithmétique

 Les expressions booléennes (logiques)

Elles font intervenir les operateurs logiques (and, or, not, …) ainsi que les operateurs

de relation (>, <, <=, <>, …).

Exemple : (a > b et b <= c) et une expression logique

Priorité des operateurs :

Une expression est évaluée suivant la priorité des operateurs, on commençant par le plus
prioritaire. Dans le cas ou deux operateurs ont la même priorité, on commence par la plus à
gauche.

Non (not)
/ div
Priorité et (and)
+ - mod
Ou (or)

<, > , <>, >=, <=, ont la même priorité.

Les parenthèses ouvrantes et fermantes sont considérées des opérateurs les plus prioritaires.

2.7. Operateurs MOD et DIV

L’opérateur MOD fournit la partie entière de la division entre deux opérandes

Exemple : a ← b div 5 ;

L’operateur MOD fournit le reste de la division entière entre deux opérandes

Exemple : a ← b mod 5 ;

3. Conclusion
Ce chapitre permet de se familiariser avec le langage algorithmique afin d’écrire des petits
algorithmes pour résoudre des petits problèmes. Cependant, les instructions vues dans ce
chapitre sont omniprésents dans tous les futurs algorithmes.

Page
11
 Chapitre 2:
Les Structures de Contrôle

1. Introduction
On appel structure de contrôle toute action qui permet d’effectuer un groupe d’actions sous
condition(s), et permet donc d’orienter le déroulement d’un programme suivant la réalisation
de ces conditions. Il existe plusieurs formes de structure de contrôle :

2. L’action conditionnelle ou alternative

Sa forme est :

Si <Condition> alors <Action 1>

Sinon <Action 2 >

Fin_si

Cette action est s’exécute de la manière suivante :

 Si la condition définie dans <Condition> est vérifiée il faut exécuter l’action (ou le
groupe d’action) définie dans <Action 1>, puis les actions qui suivent le fsi
 Si cette condition n’est pas vérifiée il faut exécuter l’action (ou le groupe d’actions)
définie dans <Action 2>, puis les actions qui suivent le fsi.
L’organigramme associé est :

Il existe une seconde forme de cette action conditionnelle :

Si <Condition> alors <Action 1> Fsi

Et dans ce cas :

Page
12
 Chapitre 2:
Si la condition <Condition> est vérifiée, l’action (ou le groupe d’actions) <Action 1> est
exécutée puis les actions qui suivent le fsi.

Par contre si la condition n’est pas vérifiée, seules les actions qui suivent le fsi seront
exécutées.

L’organigramme associé est :

3. L’action répétitive ‘Tant que’

Sa forme est :

Tant que <Condition> faire

<Action>

Fin_tq ;

Cette action spécifie qu’une action (ou groupe d’actions) doit être répétée tant que la
condition reste vérifiée.

 Remarque : L’action <Action> étant répétée jusqu'à ce que la condition devienne

fausse, il faut donc que la partie action soit capable de modifier les paramètres
intervenant dans la condition « condition » afin de sortir de tant que.

Page
13
 Chapitre 2:

4. L’action répétitive ‘pour’

Sa forme est :

Pour <nom_var> allant de <val_initiale> à <val_finale> faire

<Action>

Fin_Pour ;

Cette action permet de répéter une action (ou groupe d’actions) un nombre de fois déterminé
par les valeurs initiale et finale de paramètre <nom_var>. La partie action est exécutée la
première fois en affectant au paramètre <nom_var> que l’on appelle aussi compteur, la valeur

<val_initiale>. Apres chaque exécution on rajoute au compteur la valeur 1. L’action est ré

exécuté jusqu'à ce que la valeur du compteur dépasse la valeur spécifiée par <val_finale>.

Page
14
 Chapitre 2:
5. L’action répétitive ‘répéter--------jusqu'à’

Cette action permet de répéter une action (groupe d’actions) jusqu'à ce que la condition soit
vérifiée. Sa forme est la suivante :

Repeter

<Actions>

Jusqu'à (condition)

 Remarque : L’action est exécutée au moins une fois à l’inverse de l’action répétitive
«tantque » ou l’action ne peut être exécutée

6. L’action conditionnelle à choix multiple

Sa forme est la suivante :

Case variable of

1 : Action 1 ;

2 : Action 2 ;

Default: Action n;

Fin;

: peut être une constante ou plusieurs constantes séparées par des virgules ou bien un
intervalle

Page
15
 Chapitre 2:
Cas ch of

‘a’..’z’ : ecrire (‘lettre’) ;

‘0’..’9’ : ecrire (‘chiffres’) ;

‘+’, ‘-’, ‘*’, ‘/’ : ecrire (‘operation’) ;

sinon

Ecrire (‘caractère spéciale’);

fin,

7. Conclusion

Les structures de contrôles sont très importantes pour contrôler le déroulement des
algorithmes, chacune est adéquate pour une situation donnée afin d’optimiser l’exécution des
algorithmes.

Page
16
 Chapitre 3:

Les Tableaux

1. Introduction
Imaginons que dans un programme, nous avons besoin simultanément de 12 valeurs (par
exemple, des notes pour calculer une moyenne). Evidemment, la seule solution dont nous
disposons à l’heure actuelle consiste à déclarer douze variables, appelées par exemple : Notea,
Noteb, Notec, etc. Bien sûr, on peut opter pour une notation un peu simplifiée, par exemple
N1, N2, N3, etc. Mais cela ne change pas fondamentalement notre problème, car arrivé au
calcul, et après une succession de douze instructions « Lire » distinctes, donnera
obligatoirement une atrocité du genre :
Moy ← (N1+N2+N3+N4+N5+N6+N7+N8+N9+N10+N11+N12)/12 ;
C’est pourquoi la programmation nous permet de rassembler toutes ces variables en une seule,
au sein de laquelle chaque valeur sera désignée par un numéro. Autrement dit, cela donnerait
donc quelque chose du genre « la note numéro 1 », « la note numéro 2 », « la note numéro 8
». C’est largement plus pratique.

2. Tableau à une dimension (vecteur)

Un tableau à une dimension est un ensemble de valeurs portant le même nom de variable,
et repérées par un nombre appelé indice, et qui sert à repérer chaque valeur du tableau
séparément. A chaque fois qu’on doit désigner un élément du tableau, on fait figurer le nom
du tableau, suivi de l’indice de l’élément entre deux crochets. Le schéma ci-dessous
représente un tableau à une dimension.

Page
17
 Chapitre 3:
2.1. Déclaration des tableaux à une dimension
Un tableau à une dimension est déclaré de la manière citée ci-dessous, en précisant le nombre
et le type de valeurs qu’il contiendra.
Exemples
Tab : tableau [1..100] d’entiers ;
Note : tableau [1..10] de réels ;
2.2. Remarques
 Les cases du tableau (éléments) sont numérotées à partir de 1,
 Lors de déclaration du tableau, on précise la plus grande valeur de l’indice, qui est le
nombre d’éléments du tableau

3. Tableau à deux dimensions (Matrice)

L’algorithmique (la programmation) nous offre la possibilité de déclarer et d’utiliser des
tableaux dans lesquels les valeurs ne sont pas repérées par un seul indice comme les tableaux
à une seule dimension, mais par deux indices (coordonnées), le premier indice sert à
représenter les lignes et le second indice pour les colonnes. Le schéma ci-dessous représente
un tableau à deux dimensions.

3.1. Déclaration des tableaux à deux dimensions

Un tableau à deux dimensions est déclaré de la manière citée ci-dessous, en précisant le
nombre (lignes et colonnes) et le type des valeurs qu’il contiendra.
Exemples
Achat : tableau [1..100, 1..100] d’entiers ;
Vente : tableau [1..10, 1..47] de réels ;
Le tableau de la figure précédente peut être déclaré de la manière suivante :
Taexemple : tableau [1..5,1..5] d’entiers ;

Page
18
 Chapitre 3:
4. Tableaux à N dimensions
Un tableau à N dimensions est déclaré de la manière citée ci-dessous, en précisant le nombre
et le type de valeurs qu’il contiendra.
Exemples
Achat : tableau [1..100, 1..100, 1…300] d’entiers ;
Vente : tableau [1..10, 1..47, 1..12, 1..7] de réels ;
Le premier est un tableau à trois dimensions et le deuxième est un tableau à quatre
dimensions.
La référence d’un élément dans un tableau à N dimensions, se fait de la même manière que
celle pour un tableau à une ou à deux dimensions, en précisant l’indice de chaque dimension.

5. Conclusion
Les tableaux sont des structures de programmation statiques, la taille de tableau doit être
précisée à l’avance. Un espace mémoire peut être réservé sans être utilisé si un tableau n’est
pas exploité complètement. Un tableau, une fois déclaré, sa taille ne peut pas être modifiée.

Page
19
 Chapitre 4:
Les Fonctions et les Procédures
1. Introduction
Les fonctions et les procédures sont appelés aussi les sous-programmes, elles fournissent aux
programmeurs un moyen simple d’abstraction en lui permettant de nommer une séquence
d’instructions et de l’appeler autant de fois qu’il sera nécessaire au cours d’un même
programme. En outre, les langages de programmation tels que Pascal, permettent de passer
des données à la procédure ou la fonction. Les valeurs de ces données pouvant variés d’un
appel à l’autre, ce mécanisme est appelé passage de paramètres. Un sous-programme
(fonction ou procédure) à la même structure qu’un programme, les seules différences
importantes sont les notions de paramètres et de variables locales.

2. Fonctions
Une fonction est un ensemble d’instructions qui forment un sous-programme, les fonctions en
algorithmique (programmation) ressemblent à celles de mathématique, Chaque fois que l’on
appelle elle renvoie au programme appelant une valeur qui est le résultat du traitement
effectués par des instructions de la fonction. Une fonction peut renvoyer n’importe quel type
de base.

2.1. Déclaration des fonctions

La structure générale d’une fonction est comme suit :

Fonction NomFonction (Var1 : type1, Var2 : type2, …VarN : typeN) : Type ; {l’entete

de la fonction}

Var variable1, …VariableN : type ; {déclaration des variables propres à la fonction}

Begin

Instructions ; {corps de la fonction}

End ;

Où : Nomfonction est le nom de la fonction (Identificateur)

 Type1, Type2, …,TypeN sont les type des paramètres de la fonction

Page
20
 Chapitre 4:
 Type est le type de résultat retourné.
Instructions est le calcul effectué par la fonction.

Remarque : À la fin d’une fonction, il faut affecter le résultat du traitement au nom de la

fonction.

2.2. Utilisation des fonctions

Une fonction, une fois déclarée, pourra être appelée depuis le programme principal, ou une
autre fonction.

Exemple : Calcul de

Algorithme CalculCNP ;

Var cnp, n, p : entiers ;

Fonction fact (n : entier) : entier

Var t, i : entiers ;

Debut

T ←1 ;

Pour i allant de 1 à n faire

Debut

T ← t*i ;

Fin ;

Fact← p ; {le résultat doit être affecté au nom de la fonction}

Fin ;

Debut

Ecrire (‘donner la valeur de n et p’) ;

Lire (n,p) ;

Cnp ←fact(n)/(fact(n-p)*fact(p)) ;

Page
21
 Chapitre 4:
Ecrire (‘cnp=’,cnp);

Fin.

2.3. Variables locales et variables globales

Les variables qui sont déclarées dans la partie déclaration de la fonction s’appellent variables
locales. Elles sont inconnues par le programme principal ou la fonction à été déclarée. Les
variables qui sont déclarées dans le programme principal ne sont pas connues par les
fonctions déclarées dans le même programme, ils sont appelées variables globales.

2.4. Paramètres formels et paramètres réels (effectifs)

Les paramètres décrites dans l’entête de la fonction lors de déclaration sont appelées
paramètres formels, ils servent à représenter la structure et le fonctionnement de la fonction.

Par contre ceux qui les remplacent dans les appels des fonctions sont appelées paramètres
effectifs ou réels.

2.5. Appel d’une fonction

Pour appeler une fonction, on fait apparaître le nom de la fonction à droite d'une affectation
de variable souvent appelée variable de retour. La syntaxe est :

Variable ←Nom_fonction (paramètres) ;

3. Procédures
Le deuxième type de sous-programme est appelé procédure. La procédure ressemble
parfaitement à la fonction sauf que cette dernière peut renvoyer zéro ou plusieurs résultats.

3.1. Déclaration d’une procédure

Une procédure est déclarée dans la partie déclaration d’un programme de la manière suivante

Procedure Nom_procedure (Var1 : type11, Var2 : type12, …VarN : type1N, Res1 :

Type21, Res2 : type22, …,Res2N : type2N)

Begin

Liste des instructions; {le corps de la procédure}

End;

Page
22
 Chapitre 4:
Où : Nom_procedure est le nom de la procédure (Identificateur)

 Var1, var2, … : sont les paramètres d’entré,

 Res1, Res2, … : sont les paramètres de sortie (les résultats fournis par la procédure)
 : est le type de paramètre associé ;
Remarques

 les dernières instructions dans une procédure sont généralement réservées pour
affecter les résultats de traitement effectué par la procédure aux paramètres de sortie
de cette dernière.
 Les notions de variables globales, locales, les paramètres formels et effectifs pour les
procédures ont les mêmes significations que pour les fonctions.
 L’appel d’une procédure se fait en écrivons son nom et en remplaçons les paramètres
formels par les paramètres effectifs.
4. Fonctions prédéfinies
Ils existent certaines fonctions et procédures prédéfinies, et intégrées avec les langages de
programmation (Pascal). Citons à titre d’exemple : Read (pour la lecture des donnés), write
(pour l’affichage des résultas), Textcolor (numéro) (pour modifier la couleur de texte),
gotoxy (x,y) (pour positionner le curseur au point de coordonnées x, y au moment de
l’exécution), clrscrn (pour effacer l’écran), sound (numéro) (pour déclencher un bip sonore),
…

5. Conclusion
Les sous programmes (fonctions et procédures) sont des portions des programmes qui se
répètent souvent soit dans un même programme, soit dans plusieurs programmes, il est donc
préférable de les écrire une fois pour toute, et de les utiliser au besoin. Ils aussi à simplifier le
développement des programmes volumineux.

Page
23
 Chapitre 5:
Les Enregistrements et les Fichiers
1. Introduction
Jusqu’à présent, les informations utilisées dans nos programmes ne pouvaient provenir que de
deux sources : soit elles étaient inclues dans l’algorithme lui-même, par le programmeur, soit
elles étaient entrées en cours de route par l’utilisateur. Mais évidemment, cela ne suffit pas à
combler les besoins réels des informaticiens. Les fichiers servent à stocker des informations
de manière permanente, entre deux exécutions d’un programme. Car si les variables
classiques, qui sont des adresses de mémoire vive, disparaissent à chaque fin d’exécution, les
fichiers, eux sont stockés sur des périphériques à mémoire de masse (disquette, disque dur,
CD Rom…).

2. Le type chaine de caractère

Formellement une chaîne de caractères est une suite de zéro, un ou plusieurs caractères
accolés.

Remarques :

 La chaîne formée d'aucun caractère s'appelle la chaîne vide.

 Un constant de type caractère peut être vue comme une constante chaîne de caractères
de longueur (taille) 1.
 Une chaîne de caractères se déclare au moyen du mot réservé string,
Exemples:

- string [ 10 ] (* chaîne de taille égale à 10 *)

- string [ 1 ] (* la plus petite chaîne possible *)
- string [ 255 ] (* la plus grande chaîne possible *)
Les constantes d'un type chaîne sont écrites entre apostrophes:

'Abcd' chaine de taille et de longueur courante 4

' ' chaîne vide (taille = longueur courante = 0)

'x' chaine de taille et de longueur courante égale à 1. C'est aussi un constant caractère

Page
24
 Chapitre 5:
3. Enregistrement
On peut regrouper au sein d’une même structure des informations n’ayant pas nécessairement
toutes le même type dans une structure appelée enregistrement (Record), par exemple, les
différentes informations (nom, prénom, sexe, nombre d’enfant, …) relatives à un employé
d’une entreprise. C’est un type de données défini par l’utilisateur.

Exemple :

Type personne = record

Nom : string[30] ;

Prenom : string[30] ;

Sex : char ;

Nb_enfant : integer ;

End ;

Ces variables (enregistrement ou record) pouvant être manipulé champ par champ de la
même façon que les variables de type simple (entier, caractère, …). Pour ce faire, un champ
d’une variable de type enregistrement est désigné par le nom de la variable, suivi d’un point et
du nom du champ concerné.

Exemple

Var employe : type personne ;

Employe. prenom := ‘karim’ ;

4. Fichier
4.1. Définition
Des fois, il est nécessaire de conserver certaines données après la fin du programme les ayant
créées, ceci pour une utilisation future, les fichiers ont été conçus pour ces fins.

Un fichier est une structure de données toutes de même type mais dont le nombre n'est pas
connu à priori. L'accès à un élément (à une donnée) du fichier se fait :

Page
25
 Chapitre 5:
 Séquentiellement c'est-à-dire en parcourant le fichier élément par élément depuis le
début jusqu'à l'élément choisi
 Directement en donnant la position de l'élément cherché
 Selon une clé chaque valeur de la clé désignant un élément on obtient ainsi l'élément
désiré
Les fichiers sont conservés en mémoire secondaire (disques et bandes magnétiques,
disquettes, flash disk...), les données qui les constituent reste toujours tant que cette mémoire
secondaire n'est pas effacée ou endommagée. Chaque fichier est désigné par un nom et
possède des attributs tels que date de création, taille, icône...

Il existe deux types de fichiers :

- Les fichiers binaires : Contenant du code binaire représentant chaque élément. Ces
fichiers ne doivent être manipulés que par des programmes!
- Les fichiers texte : appelés aussi imprimables, contenant des caractères et
susceptibles d'être lus, éditées, imprimés....
4.2. Operations sur les fichiers
4.2.1. Création
Pour créer un fichier il faut d’abord définit sa structure : son nom logique et physique, …

Exemple

Type note = fichier de réel ;

Type info_etud = structure

Mat : string[10] ;

Nom : string [15] ;

Prenom : string[15] ;

Note: reel;

Fin;

Type etudiant = fichier info_etud;

Le fichier sera reconnu par l’algorithme (programme) par un nom dit logique. Le nom logique
est attribué au fichier dans la partie déclaration au moyen d’une variable de type fichier.

Page
26
 Chapitre 5:
Exemples

var fichier1 : etudiant ;

var fichier2 : fichier info_etud ;

var fichier3 : fichier de caractere ;

Un fichier n’est reconnu par le SGF (système de gestion des fichiers) que par un nom
physique, et par conséquent, un nom physique est associé au nom logique du fichier.

L’affectation (ou l’association) du nom logique au nom physique est réalisée par la procédure
prédéfinie ASSIGN dont la syntaxe est :

ASSIGN (nom logique, nom physique) ;

Exemple :

ASSIGN (fichier1, ‘c:\[Link]’) ;

Cela veut dire que fichier1 est le fichier [Link] qui est stocké dans la racine de la partition

«C:»

4.2.2. Ouverture d’un fichier

Pour pouvoir agir sur le contenu d’un fichier existant il faut l’ouvrir, il y a deux modes
d’ouvertures des fichiers :

 Ouverture en mode écriture : cette opération revient à créer un nouveau fichier et à

le préparer pour l’écriture, cela est effectué par la procédure prédéfinie Rewrite
Exemple : Rewrite (fichier1) ;

Remarque : si cette procédure est appliquée sur un fichier déjà existant, son contenu sera
perdu.

 Ouverture en mode lecture : c’est une opération qui permet d’ouvrir un fichier
stocké sur disque pour la lecture et la modification grâce à la procédure RESET.
Exemple : Reset (fichier1) ;

Page
27
 Chapitre 5:
4.2.3. Fermeture d’un fichier
Une fois l’utilisation d’un fichier est terminée, il faut le fermer par la procédure « CLOSE ».

Exemple : Close (Fichier1) ;

4.2.4. Lecture et écriture d’un enregistrement dans un fichier

La lecture d’un enregistrement à partir d’un fichier existant s’effectue au moyen de la
procédure « READ ».

Read (fichier2, enregistrement) ;

L’écriture d’un enregistrement dans un fichier s’effectue au moyen de la procédure « Write ».

Exemple : Write (fichier1, enregistrement) ;

4.2.5. Autres opérations

 Suppression d’un fichier : pour supprimer un fichier c’est la procédure « ERASE »
Exemple : Erase (fichier1) ;

 Changement du nom physique : pour changer le nom physique d’un fichier c’est la
procédure « RENAME ».
Exemple : Rename (fichier1, nom physique2) ;

 Consultation d’un fichier

Les enregistrements (contenu) d’un fichier peuvent être lus de deux manières :

1er. Accès séquentiel : parcourt du fichier de premier élément au dernier (fin du

fichier). La fin du fichier est détectée par la fonction booléenne EOF, qui retourne la
valeur vrai si la fin du fichier, faux sinon.
Exemple : si EOF (fichier1) alors

2e. Accès direct : il est possible d’accéder directement à un élément du fichier en

précisant son numéro d’ordre. Ceci est réalisé par la procédure « SEEK ».
Exemple : SEEK (nom logique, position) ;

3e. Accès Indexé : pour simplifier, il combine la rapidité de l'accès direct et la

simplicité de l'accès séquentiel (en restant toutefois plus compliqué). Il est
particulièrement adapté au traitement des gros fichiers, comme les bases de données
importantes.

Page
28
 Chapitre 5:
 Suppression des enregistrements : Il existe deux techniques pour la suppression des
enregistrements à partir d’un fichier : suppression logique et suppression physique.
1er. Suppression logique : dans la définition de la structure des enregistrements du
fichier, on réserve un champ qui indique l’état de l’enregistrement (supprimé ou non),
ainsi la suppression logique consiste à mettre ce champ à la valeur appropriée.
2e. Suppression physique : elle consiste à recopier le fichier dans un autre fichier
en ne prenons que les enregistrements qui ne sont pas logiquement supprimés. A la fin,
on supprime l’ancien fichier tout entier.
Remarque :Apres une série de suppressions logiques. La suppression physique est
recommandée.

6. Conclusion
Les fichiers sont les seules structures de données qui permettent la sauvegarde permanant des
données, ils sont la structure de base pour les bases de données.

Page
29
 Chapitre 6:
La Récursivité
1. Introduction
La récursivité est un concept général qui peut être illustré dans (quasiment) tous les langages
de programmation, et qui peut être utile dans de nombreuses situations.

2. Définition : la programmation récursive est une technique de programmation qui

remplace les instructions de boucles (while, for, etc.) par des appels de fonction.
L'idée est de diviser un problème P en sous-problèmes (certains de la même forme), de
résoudre ces sous-problèmes de manière directe si c'est possible sinon de la même manière
que P (le problème initial), puis de combiner le résultat de ces sous-problèmes pour résoudre
le problème initial P. Autrement dit, on traite le problème P en le ramenant à un problème de
la même forme mais plus petit.

Exemple :

n!= n (n-1) ! et comme il faut s’arrêter, il faut définir une condition d’arrêt, on pose donc

0 !=1.

Le principe de l’exécution est simple : l’algorithme met de côté (en fait dans une PILE) ce
qu’il ne sait pas faire quitte à les reprendre après. Par conséquent, on doit dire à l’algorithme
comment faire dans les cas les plus simples.

Les conditions d’arrêt : ces cas non récursifs sont appelés cas de base et les conditions que
doivent satisfaire les données dans ces cas de base sont appelées conditions d’arrêt ou de
terminaison. Dans les cas complexes, l’algorithme va faire appel à lui-même en simplifiant
ces cas jusqu’à tomber sur l’une des conditions d’arrêt.

Tout algorithme récursif doit distinguer plusieurs cas, dont l’un au moins ne doit pas
comporter d’appel récursif. Souvent ce sont les cas les plus simples. Sans cela, on risque de
tourner en rond et de faire des exécutions qui ne se finissent pas.

Si ces principes ne sont pas appliqués, l’algorithme risque soit de ne pas produire de résultat,
soit de tourner à l’infini

On doit conduire le programme vers les cas de base : tout appel récursif doit se faire avec des
données plus proches des conditions de terminaison.

Page
30
 Chapitre 6:
Théoriquement, on peut toujours dé-récursiver un algorithme récursif, c’est-à-dire le
transformer en algorithme itératif. En pratique, ce n’est pas toujours facile!

3. Exemple de raisonnement récursif : les tours de Hanoi

Un exemple très connu de raisonnement récursif apparaît dans le problème des tours de
Hanoi. Il s’agit de N disques de tailles différentes, trouées au centre, qui peuvent être empilés
sur trois piliers. Au début, tous les disques sont empilés sur le pilier de gauche, en ordre
croissant de la taille, comme dans la figure suivante. Le but du jeu (exemple) est de déplacer
les disques un par un pour reconstituer la tour initiale sur le pilier de droite. Il y a deux règles
à respecter:

 On peut seulement déplacer un disque qui se trouve au sommet d’une pile (non
couvert par un autre disque) ;
 Un disque ne doit jamais être placé sur un autre plus petit.
Le jeu est illustré dans la figure ci-dessous

La solution s’exprime très facilement par récursivité. On veut déplacer une tour de disques du
pilier de gauche vers le pilier de droite, en utilisant le pilier du milieu comme position
intermédiaire.

 Il faut d’abord déplacer vers le pilier du milieu la tour de n-1 disques du dessus du
pilier de gauche (en utilisant le pilier de droite comme intermédiaire).
 Il reste sur le pilier de gauche seul le grand disque à la base. On déplace ce disque sur
le pilier de droite.
 Enfin, on déplace la tour de n -1 disques du pilier du milieu vers le pilier de droite, au-
dessus du grand disque déjà placé (en utilisant le pilier de gauche comme
intermédiaire).

Page
31
 Chapitre 6:
La fonction récursive est donnée comme suit :

Fonction Hanoi (nb_disques, départ, destination, intermédiaire)

Début

si (nb_disques = 1) alors

déplacer le disque 1 de départ vers la destination

sinon

Hanoi (nb_disques -1, départ, intermédiaire, destination)

déplacer le disque nb_disques de départ vers destination

Hanoi (nb_disques -1, intermédiaire, destination, départ)

fsi

Fin.

L’exécution d’un programme qui utilise la fonction Hanoi avec nombre de disque = 3 produit
le résultat suivant :

Combien de disques ? 3

Déplacer le disque de gauche - droite

Déplacer le disque de v gauche - milieu

Déplacer le disque de droit - milieu

Déplacer le disque de gauche - droite

Déplacer le disque de milieu - gauche

Déplacer le disque de milieu - droite

Déplacer le disque de gauche - droite

4. Exemple de raisonnement récursif : La suite de Fibonacci

Page
32
 Chapitre 6:
Les nombres de la suite de Fibonacci sont égaux à la somme des deux termes précédents, ils
suivent donc la formule de récurrence :

F(n+2)=F(n)+F(n+1)

Pour initialiser la suite, on prend généralement F(0) = 0 et F(1) = 1

Calcul récursif de Fibonacci

fib(4) -> fib(3) + fib(2)

-> (fib(2) + fib(1)) + fib(2)

-> ((fib (1) + fib (1)) + fib(1)) + fib(2)

-> ((1 + fib(1)) + fib(1)) + fib(2)

-> ((1 + 1) + fib(1)) + fib(2)

-> (2 + fib(1)) + fib(2)

-> (2 + 1) + fib(2)

-> 3 + fib(2)

-> 3 + (fib(1) + fib(1))

-> 3 + (1 + fib(1))

-> 3 + (1 + 1)

-> 3 + 2

-> 5

5. Conclusion
Certains problèmes peuvent être résolus plus logiquement en utilisant la récursivité.

Les programmes sont plus compacts, plus faciles à écrire et à comprendre. Son usage est
naturel quand le problème à traiter peut se décomposer en deux ou plusieurs sous-problèmes

Page
33
 Chapitre 6:
identiques au problème initial mais avec des valeurs de paramètres différentes. Refuser la
récursivité dans ce dernier cas oblige l'utilisateur à gérer lui-même une pile des différentes
valeurs des variables, ce que le système fait automatiquement lors de l'utilisation de la
récursivité.

Page
34
 Chapitre 7:
La Complexité Algorithmique
Introduction

On n'exige pas seulement d'un algorithme qu'il résolve un problème, on veut également qu'il
soit efficace, c'est-à-dire rapide (en termes de temps d'exécution) ; peu gourmand en
ressources (espace de stockage, mémoire utilisée). On a donc besoin d'outils qui nous
permettre d'évaluer la qualité théorique des algorithmes proposés. Pour toutes ces raisons,
l’étude de la complexité algorithmique est primordiale.

La théorie de la complexité (algorithmique) vise à répondre à ces besoins ;

1. de classer les problèmes selon leur difficultés ;

2. de classer les algorithmes selon leur efficacités ;
3. de comparer les algorithmes résolvant un problème donné avant de faire un choix et
sans les implémenter ;
Pour cela, on utilise des unités de temps abstraites et proportionnelles au nombre d'opérations
effectuées. Au besoin, on pourra adapter ces quantités en fonction de la machine sur laquelle
l'algorithme s'exécute ;

La notation la plus utilisée pour exprimer la complexité d'un algorithme est la notation O

(pour ordre de...), qui dénote un ordre de grandeur. Par exemple, on dira d'un algorithme qu'il
est O(15) s'il nécessite au plus 15 opérations (dans le pire cas) pour se compléter. En langage
naturel, on dira qu'il est O de 15 ou encore de l'ordre de 15.

Pour calculer cette complexité, on applique les règles suivantes :

1. Chaque instruction basique consomme une unité de temps ; (affectation d'une variable,
comparaison, +, -, *, =, ...). Les instructions de base prennent un temps constant, notée
O(1).
2. Chaque itération d'une boucle rajoute le nombre d'unités de temps consommées dans
le corps de cette boucle ;
3. Chaque appel de fonction rajoute le nombre d'unités de temps consommées dans cette
fonction ;
4. On additionne les complexités d'opérations en séquence :
O(f1(n)) + O(f2(n)) =O(f1(n) + f2(n)).

Page
35
 Chapitre 7:
C’est la même chose pour les branchements conditionnels :
5. Pour avoir le nombre d'opérations effectuées par l'algorithme, on additionne le tout

L’exemple suivant illustre comment calculer la complexité de la fonction factorielle.

La complexité d'un algorithme est une mesure de sa performance asymptotique (des données
très grandes) dans le pire cas ;

L’exemple suivant illustre comment calculer la complexité dans l’alternative if-else.

Dans les boucles, on multiplie la complexité du corps de la boucle par le nombre d'itérations.

Par exemple, la complexité d'une boucle while se calcule comme suit :

Page
36
 Chapitre 7:
La notation O, dite notation de Landau, vérifie les propriétés suivantes :

- Si f=O(g) et g=O(h) alors f=O(h)

- si f=O(g) et k un nombre, alors k*f=O(g)

- si f1=O(g1) et f2=O(g2) alors f1+f2 = O(g2+g2)

- si f1=O(g1) et f2=O(g2) alors f1*f2 = O(g2*g2)

Pour calculer la complexité d'un algorithme :

1. on calcule la complexité de chaque partie de l'algorithme ;

2. on combine ces complexités conformément aux règles qu'on vient de voir ;
3. on simplifie le résultat grâce aux règles de simplification (élimination des constantes,
et conservation du (des) terme(s) dominant(s))
 Quelques équivalences
 f (n) = O(g(n)) n'implique pas g(n) = O(f (n)) ,
contre-exemple : 5n + 43 = O(n2), mais n2 ≠ O(n) ;

 f (n) ≠ O(g(n)) n'implique pas g(n) ≠ O(f (n)) :

contre-exemple : 18 n3 – 35 n ≠ O(n), mais n = O(n3) ;

 On dit que deux fonctions f(n) et g (n) sont équivalentes si f(n)= O (g (n)) et g(n) = o
(f (n))
D'un point de vue algorithmique, trouver un nouvel algorithme de même complexité pour un
problème donné ne présente donc pas beaucoup d'intérêt ;

Lorsque, pour une valeur donnée du paramètre de complexité, le temps d'exécution varie
selon les données d'entrée, on peut distinguer :

1. La complexité au pire : temps d'exécution maximum, dans le cas le plus défavorable.

2. La complexité au mieux : temps d'exécution minimum, dans le cas le plus favorable
(en pratique, cette complexité n'est pas très utile).
3. La complexité moyenne : temps d'exécution dans un cas médian, ou moyenne des
temps d'exécution.
Le plus souvent, on utilise la complexité au pire, car on veut borner le temps d'exécution. Le
tableau suivant illustre les principales classes de complexité.

Page
37
 Chapitre 7:

Conclusion

L’analyse de la complexité des algorithmes étudie formellement la quantité de ressources en

temps et en espace nécessitée par l'exécution d'un algorithme donnée. La complexité d'un
algorithme est une mesure du temps requis par l'algorithme pour accomplir sa tâche, en
fonction de la taille de l'échantillon à traiter.

Page
38
 Chapitre 8:
Les Pointeurs
1. Introduction
Un pointeur est une variable dont la valeur est une adresse mémoire. Un pointeur, noté
P, pointe sur une variable dynamique notée P^.

Le type de base est le type de la variable pointée. Le type du pointeur est l'ensemble des
adresses des variables pointées du type de base. Il est représenté par le symbole ^ suivi de
l'identificateur du type de base.

La variable pointeur P pointe sur l'espace mémoire P^ d'adresse 3. Cette cellule mémoire
contient la valeur "Essai" dans le champ Info et la valeur spéciale Nil dans le champ

Suivant. Ce champ servira à indiquer quel est l’élément suivant lorsque la cellule fera partie
d’une liste. La valeur Nil indique qu’il n’y a pas d'élément suivant. P^ est l'objet dont
l'adresse est rangée dans P.

Avec les pointeurs, plusieurs structures de données peuvent être définies : les listes linéaires
chainées, les files d’attente, les piles, les arbres.

2. Liste Linéaire Chainée

Une liste linéaire chaînée (LLC) est un ensemble de maillons, alloués dynamiquement,
chaînés entre eux. Schématiquement, on peut la représenter comme suit : « abcdef »

Page
39
 Chapitre 8:
Un élément ou maillon d’une LLC est toujours une structure (Objet composé) avec deux
champs : un champ Valeur contenant l’information et un champ Adresse donnant l’adresse du
prochain élément. A chaque maillon est associée une adresse. On utilise ainsi une nouvelle
classe d’objet : le type Pointeur qui est une variable contenant l’adresse d’un emplacement
mémoire.

Les listes chaînées entraînent l'utilisation de procédures d'allocation et de libération

dynamiques de la mémoire. Ces procédures sont les suivantes:

- Allouer(P) : réserve un espace mémoire P^ et donne pour valeur à P l'adresse de cet

espace mémoire. On alloue un espace mémoire pour un élément sur lequel pointe P.
- Désallouer(P) : libère l'espace mémoire qui était occupé par l'élément à supprimer P^
sur lequel pointe P.
Pour définir les variables utilisées dans l'exemple ci-dessus, il faut : définir le type des
éléments de la liste :

Type Cellule= Structure

Info : Chaîne

Suivant : Liste

fin Structure

 définir le type du pointeur : Type Liste = ^Cellule

 déclarer une variable pointeur : Var P : Liste
 allouer une cellule mémoire qui réserve un espace en mémoire et donne à P la valeur de
l'adresse de l'espace mémoire P^ : Allouer(P)
 affecter des valeurs à l'espace mémoire P^: P^.Info ← "Essai" ; P^.Suivant ← Nil
Quand P = Nil alors P ne pointe sur rien

Il faut commencer par définir un type de variable pour chaque élément de la chaîne. En
langage algorithmique ceci se fait comme suit :

Type Liste = ^Elément

Type Elément = Structure

Page
40
 Chapitre 8:
Info : variant

Suivant : Liste

Fin structure

Variables Tète, P : Liste

Le type de Info dépend des valeurs contenues dans la liste : entier, chaîne de caractères,
variant pour un type quelconque…

Une liste linéaire chainée est caractérisée par l’adresse de son premier élément souvent appelé

Tête. Nil constitue l’adresse qui ne pointe aucun maillon, utilisé pour indiquer la fin e la liste
dans le dernier maillon

La représentation réelle en mémoire de cette liste ressemble à la représentation suivante :

Dans le langage algorithmique, on définira le type d’un maillon comme suit :

Page
41
 Chapitre 8:
Afin de développer des algorithmes sur les listes linéaires chainées, on construit une machine
abstraite avec les opérations suivantes : Allouer, Libérer, Aff_Adr, Aff_Val, Suivant et Valeur
définies comme suit :

 Allouer(P) : allocation d’un espace de taille spécifiée par le type de P. L’adresse de

cet espace est rendue dans la variable P de type Pointeur.
 Libérer(P) : libération de l’espace pointé par P.
 Valeur(P) : consultation du champ Valeur du maillon pointé par P.
 Suivant(P) : consultation du champ Suivant du maillon pointé par P.
 Aff_Adr(P, Q) : dans le champ Suivant du maillon pointé par P, on range l’adresse Q.
 Aff_Val(P,Val) : dans le champ Valeur du maillon pointé par P, on range la valeur
Val.
Cet ensemble d’opérations (ou de méthodes ou fonctions) est appelé modèle.

Les principaux traitements qui peuvent être effectué sur des listes sont les suivants :

- Créer une liste.

- Ajouter un élément.
- Supprimer un élément.
- Modifier un élément.
- Parcourir une liste.
- Rechercher une valeur dans une liste.
Algorithme Création LLC avec N éléments et afficher ces valeurs à la fin de traitement.

Page
42
 Chapitre 8:

Il existe différents types de listes chaînées :

1. Liste chaînée simple constituée d'éléments reliés entre eux par des pointeurs.
2. Liste chaînée ordonnée où l'élément suivant est plus grand que le précédent. L'insertion
et la suppression d'élément se font de façon à ce que la liste reste triée.
3. Liste circulaire où le dernier élément pointe sur le premier élément de la liste. S'il s'agit
d'une liste doublement chaînée alors de premier élément pointe également sur le dernier.

Page
43
 Chapitre 8:
4. Listes linéaires chaînées bidirectionnelles : c’est une LLC où chaque maillon contient à
la fois l’adresse de l’élément précédent et l’adresse de l’élément suivant ce qui permet de
parcourir la liste dans les deux sens.

Un exemple de déclaration de listes linéaires chainées bidirectionnelles est donné comme

suit :

Un modèle sur les listes linéaires chaînées bidirectionnelles est donné comme suit :

- Allouer (p): création d’un maillon.

- Libérer (p): libérer un maillon.
- Valeur (P) : retourne la valeur du champ valeur du maillon pointé par P.
- Suivant(P) : retourne le pointeur se trouvant dans le champ suivant du maillon pointé
par P
- Précédent(P) : retourne le pointeur se trouvant dans le champ précédent du maillon
pointé par P
- Aff_Val(P,x) : Ranger la valeur de x dans le champs valeur du maillon pointé par P
- Aff_Adr_Précedent(P,Q) : Ranger Q dans le champs précédent du maillon pointé par P
- Aff_Adr_Suivant(P,Q) : Ranger Q dans le champs suivant du maillon pointé par P.

3. File

Une file est une structure de données dynamique dans laquelle on insère des nouveaux
éléments à la fin (queue) et où on enlève des éléments au début (tête de file). L’application la
plus classique est la file d’attente, et elle sert beaucoup en simulation. Elle est aussi très

Page
44
 Chapitre 8:
utilisée aussi bien dans la vie courante que dans les systèmes informatiques. Par exemple, elle
modélise la file d’attente des clients devant un guichet, les travaux en attente d’exécution dans
un système de traitement par lots, ou encore les messages en attente dans un commutateur de
réseau téléphonique. On retrouve également les files d’attente dans les programmes de
traitement de transactions telle que les réservations de sièges d’avion.

On note bien que dans une file, le premier élément inséré est aussi le premier retiré. On parle
de mode d’accès FIFO (First In Fist Out).

Les principales opérations sont :

 Enfiler : qui consiste à ajouter un nouveau élément en queue de la file et

 Défiler qui consiste à supprimer un élément de la file.

Pour ajouter un nouvel élément, on doit se déplacer en queue de la file en parcourant la file de
début jusqu’à la fin. Lorsque le dernier nœud est atteint, lui accrocher le nouvel élément qui
devient de ce fait le dernier.

Quatre opérations de base sont principalement utilisées dans une file d’attente:

1. Consulter le premier élément de la file,

2. Tester si la file est vide,
3. Enfiler un nouvel élément: le mettre en dernier,
4. Défiler un élément, le premier (le supprimer).

4. Pile

Les piles sont des structures linéaires pour lesquelles à chaque nœud on s’intéresse en
premier lieu non seulement à la valeur stockée mais aussi au moment où celle-ci est arrivée.

Page
45
 Chapitre 8:
Une pile est un type de liste particulier dans lesquels toute insertion ou suppression d’élément
se fait à une extrémité appelée sommet de la pile. Pour bien comprendre les mécanismes de
base, il suffit de penser à une pile d’assiettes.

 Empiler un élément dans la pile consiste à créer un nouveau nœud et à le placer au

sommet de la pile, il devient alors lui-même le nouveau sommet de la pile.
 Dépiler un élément de la pile consiste à récupérer le sommet de la pile et faire pointer
le sommet de la pile à son successeur (le second élément dans la pile)

Une pile est une liste sur laquelle on autorise seulement 4 opérations:

1. Consulter le dernier élément de la pile (le sommet de la pile),

2. Tester si la pile est vide,
3. Empiler un élément, le mettre au sommet de la pile ==> PUSH,
4. Dépiler un élément (par le sommet) ==> POP.

Toutes les opérations sont effectuées sur la même extrémité; on parle de structure en FIFO.

Comportement d'une pile: Last In First Out (LIFO).

5. Arbre

L'arbre est une structure de données qui généralise la liste, alors qu'une cellule de la liste a un
seul successeur (leur suivant), dans un arbre il peut y en avoir plusieurs. On parle alors de
nœud (au lieu de cellule). Un nœud père peut avoir plusieurs nœuds fils. Un fils n'a qu'un seul
père, et tous les nœuds ont un ancêtre commun appelé la racine de l'arbre (le seul nœud qui n'a
pas de père).

Comme les listes, la structure d’arbre est fortement utilisée en informatique, particulièrement
en base de données, pour représenter des algorithmes de recherche opérationnelle, en
traitement d’images, dans les programmes de calcul formel,

5.1. Définition : un arbre A est un ensemble fini d’éléments tels que :

- Il existe un élément particulier appelé racine d’arbre,
- Les autres éléments sont repartis de manière à former une partition en m classes
(m>=0), A1, A2, Am, chacune de ces classes étant elle-même un arbre (sous arbre),

Page
46
 Chapitre 8:
La racine est l’élément unique de l’arbre à partir duquel on a accès à ses éléments. Tous les
algorithmes de traitement d’arbres partiront de la racine. Pour s’orienter dans un arbre, on
utilise la terminologie classique des arbres généalogiques : père, fils, frères, ascendant,
descendant,… tel que :

 Père d’un sommet : le prédécesseur d’un sommet

 Fils d’un sommet : les successeurs d’un sommet
 Frères : des sommets qui ont le même père
 Nœud = sommet
 Racine : nœud sans père
 Feuille : nœud sans fils
 Branche : chemin entre deux nœuds
 Niveau (profondeur) d’un nœud : la longueur de la branche depuis la racine
 Hauteur d’un nœud : la longueur de la plus longue branche de ce nœud jusqu’à une
feuille
 Hauteur d’un arbre : la hauteur de la racine
 Taille d’un arbre : nombre de ses sommets

Le degré d’un nœud dans un arbre est égale au nombre de fils de ce nœud. Un nœud feuille
est un nœud de degré 0.

5.2. Parcours d’arbres

Les principales parcourt d’arbres sont :

1. Parcours en pré-ordre ou Parcours préfixe (Racine Gauche Droit) : au niveau de

chaque nœud, on traite la valeur disponible à cet endroit, puis on continue le parcours,

Page
47
 Chapitre 8:
cette fois sur le sous-arbre gauche puis sur le sous arbre droit. En d’autres mots : le nœud
racine est traité au premier passage avant le parcours des sous-arbres.

L’algorithme associé est donné comme suit.

ParcoursRGD (ARBIN A)
Début
Si (A est vide) Alors
terminaison (A)
Sinon
traitement (A)
Parcours (ABG de A)
Parcours (ABD de A)
Fsi
Fin

2. Parcours symétrique ou infixe (Gauche Racine Droit): cette fois-ci, le traitement se fait
entre les deux parcours, du sous arbre droit et du sous arbre gauche. En d’autres mots : le
nœud racine est traité au second passage après le parcours du sous-arbre gauche et avant le
parcours du sous-arbre droit.

ParcoursGRD (ARBIN A)
Début
Si (A est vide) alors
Terminaison (A)
Sinon
Parcours (ABG de A)
Traitement (A)
Parcours (ABD de A)
Fsi
Fin

3. Parcours terminal ou post fixe ou suffixe (Gauche Droit Racine): on commence à

parcourir les deux sous arbres de nœud courant puis ensuite effectuer le traitement
proprement dit. En d’autres mots : le nœud racine est traité au dernier passage après le
parcours des sous-arbres.

Page
48
 Chapitre 8:
ParcoursGDR (ARBIN A)
Début
Si (A est vide) Alors
terminaison (A)
Sinon
Parcours (ABG de A)
Parcours (ABD de A)
Traitement (A)
Fsi
Fin

D’autres types de parcourt d’arbres sont donnés comme suit :

- en largeur.
- en profondeur

Parcours en largeur d'abord.

On parcourt par distance croissante à la racine. La figure suivante illustre son principe.

Si le traitement d'un sommet consiste à l'afficher, on affichera dans l'ordre 3, 1, 4, 5, 2, 0.

L’algorithme associé est donné comme suit :

Parcours EnLargeur (ARBIN A)

Début
créer une file vide F
Si (A est non vide) Alors
Enfiler A dans F
TQ (F non vide) Faire
A ← Défiler (F)
traitement (A)
Si (ABG de A non vide) Alors
Enfiler ABG de A dans F

Page
49
 Chapitre 8:
Fsi
Si (ABD de A non vide) Alors
Enfiler ABD de A dans F
Fsi
Ftq
Fsi
détruire F
Fin

Parcours en profondeur d'abord

Deux cas peuvent se présenté : infixe et postfixe

La figure suivante illustre son principe.

Si le traitement d'un sommet consiste à l'afficher, on affichera dans l'ordre 3, 1, 5, 4, 2, 0.

Le programme associé est donné comme suit :

static void Affiche(Arbre a) {

i f (a==null) return;
[Link]([Link]+" ");
Affiche([Link]);
Affiche([Link]);
}

Page
50
 Chapitre 8:

Si le traitement d'un sommet consiste à l'afficher, on affichera dans l'ordre 5, 1, 3, 2, 4, 0.

Le programme associé est donné comme suit :

static void Affiche(Arbre a) {

i f (a==null) return;
Affiche([Link]);
[Link]([Link]+" ");
Affiche([Link]);
}

Si le traitement d'un sommet consiste à l'afficher, on affichera dans l'ordre 5, 1, 2, 0, 4, 3.

Le programme associé est donné comme suit :

Page
51
 Chapitre 8:
static void Affiche(Arbre a) {
i f (a==null) return;
Affiche([Link]);
Affiche([Link]);
[Link]([Link]+" ");
}

Ecriture des expressions

 Ecriture infixée

Le signe d'opération est entre ses arguments

((3 + 12) * 5 + (4 + 17) * 6) / (7 + (8 * 4))

 Ecriture postfixée

Le signe d'opération est après ses arguments

4 12 + 5 * 4 17 + 6 * + 7 8 4 * + /

 Ecriture préfixée

Le signe d'opération est avant ses arguments

/ + * + 3 12 5 * + 4 17 6 + 7 * 8 4

6. Conclusion

Certain langages ne permettent pas l'utilisation explicite de pointeurs. La majorité des

langages de programmation utilisent (ou au moins permettent) le passage de paramètres par
valeur. L'utilisation des pointeurs est très puissante dans certains langages. Cette puissance (et
surtout le fait que l'on touche directement à la mémoire sans aucun contrôle) complexifie le
développement d'une application.

Si l'on ne fait pas attention et que l'on accède à une zone mémoire qui ne nous est pas
allouée, le processeur via le système d'exploitation génèrera une erreur de segmentation qui

Page
52
 Chapitre 8:
provoquera une exception voire fera planter l'application. De plus, comme les allocations
mémoire sont réalisées en partie par le développeur, il doit également se charger de la
libération de la mémoire lorsqu'il n'en a plus besoin, au risque de voir une fuite mémoire
apparaître.

Page
53
 Références Bibliographiques

[1] : Jacques Courtin, Initiation à l'algorithmique et aux structures de données, Edition

DUNOD, 1998

[2] : Mc Belaid, Algorithmique et Structures de données, Edition les pages bleus

[3] : Michel Divay, Algorithmes et structures de données génériques - 2ème édition, Edition
Dunod

[4] : Zegour Djamel eddine, Structures de données et de fichiers. Programmation Pascal et

C, édition CHIHAB,

[5] : Thabet Slimani, Programmation et structures de données avancées en langage C, cours et

exercices corrigés, 2014

[6] : Claude Pair, Marie-Claude Gaudel, Les Structures de données et leur représentation en
mémoire, édition Iria, 1979

[7] : Dr. Mourad AMAD , Algorithmique et Structures de Données , Université

Abderrahmane Mira de Bejaia 2016

Page
54