Algorithmique et

structures de
données

Paternité - Pas d'Utilisation Commerciale - Partage des Conditions Initiales

à l'Identique : [Link]
 Table des
matières

Objectifs 5

Introduction 7

I - Introduction à l'algorithmique et à la programmation en C 9

A. Généralités sur les algorithmes.......................................................................9

1. Définitions........................................................................................................................9
2. Problème, algorithme, algorigramme et programme............................................................13
3. Structure générale d'un algorithme....................................................................................14
4. Premiers algorithmes ......................................................................................................15
5. Symboles de l'algorigramme.............................................................................................16
6. Premiers algorigrammes..................................................................................................17

B. Variables, expressions et affectations............................................................17

1. Notions de variables, d'expressions et d'affectations............................................................17
2. Affectation et opérations..................................................................................................18

C. Enchaînement d'instructions.........................................................................20
1. Saisie et affichage...........................................................................................................20
2. Enchaînement séquentiel..................................................................................................20
3. Enchaînement alternatif...................................................................................................21
4. Enchaînement répétitif.....................................................................................................21

D. Fonctions...................................................................................................22
1. Généralités sur les fonctions.............................................................................................23
2. Fonctions récursives........................................................................................................24

E. Langage C..................................................................................................26
1. Généralités.....................................................................................................................26
2. Enchaînement d'instructions.............................................................................................34
3. Fonctions en C................................................................................................................40

II - Structures de données statiques 47

A. Types de données composés........................................................................47

1. Énumération...................................................................................................................48
2. Union............................................................................................................................48
3. Tableaux........................................................................................................................48
4. Structures......................................................................................................................50

B. Tableaux et structures en C..........................................................................52

1. Tableaux........................................................................................................................52
2. Structures......................................................................................................................54

III - Structures de données dynamiques 57

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

3
 A. Notions élémentaires sur les pointeurs...........................................................57
1. Généralités sur les pointeurs.............................................................................................57
2. Déréférencement et indirection.........................................................................................60
3. Passage de paramètres....................................................................................................62
4. Arithmétique des pointeurs...............................................................................................64
5. Pointeurs et tableaux.......................................................................................................64
6. Les chaînes de caractères.................................................................................................66

B. Notions élémentaires sur les pointeurs en C...................................................66

C. Allocation dynamique de mémoire en C..........................................................66

D. Fichiers en C..............................................................................................66

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

4
 Objectifs

Donner aux apprenants les outils nécessaires pour réaliser des

algorithmes sur la plupart des structures de données et les
implémenter dans le langage de programmation C.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

5
 Introduction

L'algorithmique est une science assez vaste qui va de l'étude de la structuration des
algorithmes aux types de données statiques (simples ou composées) et dynamiques en
passant par les enchaînements possibles. On associe aussi généralement un langage de
programmation pour implémenter les algorithmes écrits.
Dans ce cours nous présentons d'abord les notions de base en algorithmique en répondant
aux questions qu'est ce qu'un algorithme ? comment est-il se structuré ? quels sont les
données utilisées ? Comment définir des données en entrée et comment en définir en
sortie ?
Puis nous introduisons les enchaînements d'instructions possibles à travers les structures
séquentielle, conditionnelle, et itérative avant d'introduire les notions de fonctions et
procédures. Par la suite nous introduirons les types de données composées (tableaux
d'éléments, enregistrements, énumérations et unions) avant d'introduire les structures de
données dynamiques par les pointeurs puis les listes chaînées, les piles et les files.
Nous utiliserons trois façon d'implémenter ou représenter les algorithmes à savoir l'écriture
littérale, l'utilisation d'organigramme (algorigramme) et à l'utilisation du langage de
programmation C. Nous choisirons la terminologie en fonction de son intérêt pour la partie
vue et nous verrons certaines notions (fichier, chaînes de caractères) que dans l'étude du
langage C.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

7
 Introduction à
I-

I
l'algorithmique et
à la
programmation
en C

Généralités sur les algorithmes 9

Variables, expressions et affectations 17
Enchaînement d'instructions 20
Fonctions 22
Langage C 26

A. Généralités sur les algorithmes

1. Définitions

Définition : Qu'est-ce qu'un algorithme ?

Un algorithme est une une suite d'opérations élémentaires obéissant à un
enchaînement déterminé permettant de décrire le fonctionnement d'un système
automatique.

Définition : Qu'est-ce que l'algorithmique ?

L'algorithmique est la science des algorithmes.

Caractéristiques d'un algorithme

On dira d'un algorithme qu'il est :
 réutilisable s'il peut être réutilisé pour résoudre des tâches équivalentes à
celle pour laquelle il a été conçu ;
 robuste s'il est protégé contre les conditions anormales d'utilisation ;
 valide s'il permet de réaliser exactement la tâche pour laquelle il a été

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

9
 Introduction à l'algorithmique et à la programmation en C

conçu ;
 efficace s'il utilise de manière optimale les ressources du PC qui l'exécute.
La complexité d'un algorithme est le nombre d'instructions élémentaires à
exécuter pour réaliser la tâche pour laquelle il a été conçu.
Tout algorithme peut être décrit à l'aide de trois structures fondamentales : la
séquence, l'alternative et l'itération.
Un algorithme est dit structuré s'il dispose d'un seul point d'entrée et un seul point
de sortie et peut donc être schématisé comme un bloc d'instruction avec un début
et une fin.

Définition : Qu'est-ce qu'un programme informatique ?

Un programme informatique est la traduction d'un algorithme dans un langage
compréhensible par l'ordinateur.
Un programme informatique réalise en général trois grandes choses :
 Il lit des données en entrées comme les saisies de l'utilisateur au clavier.
Ces données sont la matière pour les calculs à effectuer ;
 Il effectue des calculs : le programme applique des méthodes pour traiter
les données en entrée et produire le résultat escompté ;
 Il écrit des données en sortie : quand le programme obtient le résultat il
l'écrit quelque part pour qu'on puisse les utiliser ou visualiser (écran,
fichier ).

Définition : Qu'est-ce qu'un algorigramme ?

L'algorigramme est un organigramme utilisé pour représenter un algorithme c'est-
à-dire une représentation graphique normalisée d'un programme de commande. Il
est construit à partir d'un algorithme et a un lien direct avec le programme qui en
découle.

2. Problème, algorithme, algorigramme et programme

Quelle(s) différence(s)?
Pour résumer le fonctionnement d'un système automatique de résolution d'un
problème donné, est expliqué par un algorithme, représenté graphiquement par un
organigramme, et mise en œuvre par un programme.
La différence entre algorithme et programme tient au fait qu'un algorithme exprime
la structure logique d'un système automatique: il est indépendant du langage de
programmation tandis qu'un programme est le résultat d'un code source écrit dans
un langage de programmation spécifique.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

10
 Introduction à l'algorithmique et à la programmation en C

3. Structure générale d'un algorithme

Principales parties d'un algorithme

Un algorithme se présente comme suit :

Algorithme: nom-de-l'algorithme
Entrées :
Type2 nom_param21, nom_param22 ;
Sorties :
Type1 nom_param_sortie ;
Précondition :

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

11
 Introduction à l'algorithmique et à la programmation en C

//Conditions sur les paramètres en entrée

nom_param21<nom_param22 ;
Postcondition :
//Relation entre les paramètres en entrée et ceux en sortie
nom_param1<nom_param_sortie;
Déclarations :
Type2 nom_param_intermediaire ;
Constantes :
Pi<-3,14 ;
début
//Suite d'opérations élémentaires permettant de calculer les
paramètres en sortie en fonction des paramètres en entrée
(contenu de l'algorithme)
instruction1 ;
...
instructionN ;
Fin

Remarque : Les règles d'écritures

 Pour chaque paramètre en entrée, en sortie ou intermédiaire (partie
déclaration), préciser son type (Entier, Réel, ...) et son nom;
 Pour chaque constante, préciser son nom et sa valeur. Cette valeur ne
change plus ;
 Les paramètres de même type peuvent être définis sur la même ligne en les
séparant par des virgules comme Entier a, b, c ;
 A part certaines instructions particulières (Si, Pour, Tant Que, Répeter)
toutes les instructions se terminent par ;

Exemple : Algorithme de résolution d'équation du second degré

Algorithme : equation_second_degre
Entrées : //Données sur lesquelles travaille l'algorithme, issues de l'énoncé du
problème
Réel a, b, c ;
Sorties ://Données résultats
Réel r1, r2 ;
Précondition : // conditions à prendre que doivent respecter les entrées
b2 + 4ac >= 0 et a != 0
Postcondition : //conditions respectées par les sorties
ar12+ br1 + c = ar22 + br2 + c = 0 i.e. r1 et r2 sont les deux solutions de l'équation
ax2 + bx + c = 0
Déclarations : //Déclarations des variables et constantes intermédiaires

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

12
 Introduction à l'algorithmique et à la programmation en C

puremment utilisées dans le processus de résolution

Réel delta ;
début//Début du programme
//Suite d'opérations élémentaires permettant de calculer r1 et r2 à partir de a, b et
c.
Fin//Fin du programme

4. Premiers algorithmes

Exemple : Algorithme Bonjour

Algorithme Bonjour
Début
Afficher("Bonjour !") ;
Fin

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

13
 Introduction à l'algorithmique et à la programmation en C

Exemple : Algorithme Lire un nombre

Algorithme LectureNombre
Entrées
Réel x ; /* Déclaration d'une variable réelle*/
Début
Afficher("Entrer un nombre entier s'il vous plaît : ") ;
Lire (x) ;
Afficher("Vous avez tapez", x, "félicitation") ;
Fin

5. Symboles de l'algorigramme

Symboles de l'algorigramme

6. Premiers algorigrammes

B. Variables, expressions et affectations

1. Notions de variables, d'expressions et d'affectations

Un problème est spécifié par une relation entre les valeurs des paramètres en
entrée et des valeurs de paramètres en sortie. Pour calculer les valeurs des
paramètres en sortie à partir des valeurs en entrée, un algorithme peut utiliser des

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

14
 Introduction à l'algorithmique et à la programmation en C

données intermédiaires, appelées variables locales.

L'algorithme manipule alors trois catégories de données appelées variables : les
paramètres en entrée, les paramètres en sortie et les variables locales ; ce qui peut
être schématisé de la façon suivante :

Par exemple, le problème consistant à résoudre une équation du second degré peut
être décrit par

Définition : Qu'est-ce que c'est qu'une variable ?

Une variable est un espace mémoire dont on peut modifier le contenu.
Elle est caractérisée par un nom, permettant de désigner l'espace mémoire, un
type, permettant de caractériser la nature des informations que l'on pourra déposer
dans l'espace mémoire, et une valeur, désignant l'information effectivement
contenue dans l'espace mémoire.

Nom d'une variable

Le nom d'une variable est la représentation symbolique de l'adresse de l'espace qui
lui est réservée dans la mémoire. C'est une suite de caractères alpha-numériques,
commençant par une lettre. Le nom de la variable doit être choisi judicieusement
pour donner une indication sur la nature et le rôle de la donnée. Par exemple si la
variable correspond à la racine d'une équation, il est préférable de l'appeler racine
ou solution plutôt que toto ou y.

Type d'une variable

On utilisera dans la suite les types de données suivants :
 Les types de données simples désignent des variables élémentaires:
- le type entier, désignant un entier relatif ;
- le type réel, désignant un réel ;
- le type caractère, désignant un caractère alpha-numérique ou un
caractère spécial ;
- le type booléen désignant la valeur vrai ou faux ;
 Les types de données composés désignent des variables constituées de
groupes d'éléments:
- le type tableau, désignant une suite comportant un nombre variable
mais borné de données de même type ;
- le type structure, désignant une suite comportant un nombre de

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

15
 Introduction à l'algorithmique et à la programmation en C

données de types différents ;

- le type fichier, désignant une suite comportant un nombre variable mais
non borné a priori de données de même type (ce type sera étudié en fin
de cours).

Valeur d'une variable

La valeur d'une variable est contenue dans l'emplacement mémoire se trouvant à
l'adresse représentée par le nom de la variable. Ce contenu est interprété en
fonction du type de la variable.
Attention : à la suite de sa déclaration, la valeur d'une variable n'est pas définie.

Définition : Qu'est-ce qu'une constante ?

Certaines variables ont une valeur constante, qui ne change pas pendant toute
l'exécution de l'algorithme. Ces variables sont appelées constantes. Elles sont
déclarées au début de l'algorithme en faisant suivre le nom de la variable par sa
valeur.

2. Affectation et opérations

Définition : L'affectation
En algorithme elle est représentée par <-- ou <==et permet de changer la valeur
d'une variable, c'est à dire de modifier le contenu de la mémoire dédiée à la
variable. Syntaxiquement, une affectation sera représentée par :
nom_variable<==expr et a pour signification : la variable nom_variable prend la
valeur de l'expression expr, ce qui revient à stocker la valeur de l'expression expr
dans la mémoire dédiée à nom_variable. La valeur de l'expression expr doit être du
même type que celui de la variable nom_variable.

Définition d'une expression

L'expression affectée à une variable peut être :
 une valeur explicite : par exemple, l'instruction a<==25 affecte la valeur 25
à la variable de nom a ;
 une valeur contenue dans une autre variable : par exemple, l'instruction
a<==b affecte à a la valeur contenue dans la variable b ;
 un résultat d'une opération entre d'autres expressions.
Il existe 3 types d'opérations : les opérations arithmétiques, les opérations de
comparaison et les opérations logiques.

Les opérations arithmétiques

 Les opérations arithmétiques binaires sont : l'addition "+", la
soustraction "-", la multiplication "*", la division réelle "/", la division
entière "div" et le modulo "mod". Ces opérations prennent en argument
deux expressions numériques et rendent la valeur numérique correspondant
à l'application de l'opération sur les valeurs de ces expressions.
Elles sont définies sur les réels et sur les entiers, sauf "div" et "mod" qui ne
sont définies que sur les entiers.
La multiplication, la division et le modulo sont prioritaires (et donc évalués
avant) à l'addition et la soustraction. Une expression arithmétique peut être
parenthésée pour spécifier l'ordre de son évaluation.
 Les opérations arithmétiques unaires sont le plus unaire noté "+", et le

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

16
 Introduction à l'algorithmique et à la programmation en C

moins unaire noté "-". Ces opérations prennent en argument une expression
numérique et rendent une valeur numérique.

Les opérations de comparaison

Une opération de comparaison prend en argument deux expressions de même type
élémentaire (2 entiers,2 réels, 2 caractères ou 2 chaînes de caractères), et rend
une valeur logique (vrai ou faux). On utilisera les opérations de comparaison
suivantes : <;<=;=; != ou <>;=>et >.
 Les entiers et les réels sont comparés selon l'ordre numérique usuel.
 Les caractères sont comparés selon l'ordre défini par le code ASCII.
 Les chaînes de caractères sont comparées selon l'ordre lexicographique : un
texte t1 est inférieur à un texte t2 s'il existe un caractère c de t1 tel que
pour chaque caractère se trouvant avant c dans t1, le caractère
correspondant de t2 soit identique, et le caractère correspondant à c dans t2
soit supérieur à c.
Par exemple, "aabcd" < "aax" et "10" < "9".

Les opérations logiques

 Les opérations logiques binaires sont la disjonction ou, et la conjonction et.
Elles prennent en argument 2 expressions à valeur logique et rendent une
valeur logique ;
(table de vérité)
 L'opération logique unaire est la négation non notée aussi !. Cet opérateur
prend en argument une expression de valeur logique et rend la valeur
logique opposée ;

C. Enchaînement d'instructions

1. Saisie et affichage

Saisie et affichage de données

Pour lire une saisie de l'utilisateur, on utilisera l'instruction lire(x) qui lit au clavier
une valeur de même type que la variable x et affecte cette valeur à x. De même,
pour afficher à l'écran la valeur d'une variable x, on utilisera l'instruction
afficher(x).

2. Enchaînement séquentiel

Exécution séquentielle
L'enchaînement séquentiel d'une suite d'instructions permet de les exécuter les
unes à la suite des autres. Syntaxiquement, les instructions seront notées les unes
en dessous des autres (une instruction par ligne). Dans le cas d'instructions
courtes, on pourra noter plusieurs instructions les unes à coté des autres, séparées
par un point virgule. Dans ce cas, les instructions sont toutes naturellement
exécutées de la gauche vers la droite.

Exemple : Exemple d'algorithme séquentiel

Algorithme calcul_cercle

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

17
 Introduction à l'algorithmique et à la programmation en C

Entrée
Réel rayon ;
Sorties
Réel diametre, perimetre, surface ;
Constante
Pi<==3,14 ;
Début
Afficher("Entrer le rayon : ") ;
Lire (rayon) ;
diametre<==rayon*2 ;
perimetre<==diametre*Pi ;
surface<==2*Pi*rayon*rayon ;
Afficher("Le diamètre du cercle est ", diametre, ". Son périmètre est ", perimetre, ".
Sa surface est " surface ".") ;
Fin

Complément : Algorigramme associé

3. Enchaînement alternatif

Structure alternative
L'enchaînement alternatif permet d'exécuter alternativement une première suite
d'instructions, si une certaine condition est vérifiée, ou bien une autre série
d'instructions, si la condition n'est pas vérifiée.
La syntaxe d'un enchaînement alternatif est
si condition alors
suite-1
sinon
suite-2
Fin si
où condition est une expression logique, et suite-1 et suite-2 sont des suites
d'instructions
Une version simplifiée est
si condition alors
suite-1
Fin si
Dans le cas où l'on a plus de deux alternatives dont toutes les conditions sont
exclusives, on pourra utiliser l'énoncé suivant :
si condition1 alors
suite-1
sinon si condition2 alors
suite-2
sinon si condition3 alors
suite-3
sinon si condition4 alors
suite-4

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

18
 Introduction à l'algorithmique et à la programmation en C

sinon
suite-5
Fin si

Exemple : Exercice d'application

Recherche du plus petit nombre parmi trois nombres

Complément : Algorigramme correspondant

4. Enchaînement répétitif

Définition : Qu'est-ce qu'une itération ?

Une itération permet de répéter plusieurs fois une série d'instructions données

Répéter ... jusqu'à

On réalise une action jusqu'à ce qu'une condition soit remplie. Dans ce cas la forme
générale est
répéter
suite instructions
jusqu'à Condition

Exemple : Exercice d'application

Écrire un algorithme qui annonce un événement qui aura lieu à une date donnée
jusqu'à ce qu'il ait lieu. Par exemple dans 5 jours aura lieu l'examen algorithmique.

Complément : Algorigramme correspondant

Pour ... faire

On a un nombre d' itérations connues à l'avance par exemple faisons tourner une
roue 10 fois. ( On prend un compteur de tours de roue ) Dans ce cas la forme
générale est
Pour la valeur du compteur allant de 1 à une valeur connue Faire
une série d'actions ou traitement
Fin Pour ( dès qu'on a atteint le nombre prédéfini on sort de la boucle )

Exemple : Exercice d'application

Écrire un algorithme qui permet d'afficher dix fois le même message.

Complément : Algorigramme correspondant

Tant que ... faire

Si le nombre de fois est déterminé par une condition logique la forme générale est
tant que Conditionfaire
suite instructions
Fin tant que

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

19
 Introduction à l'algorithmique et à la programmation en C

Exemple : Exercice d'application

Écrire un algorithme permettant de calculer le factoriel d'un nombre entier entré
par l'utilisateur

Remarque : Différence entre répeter et tant que

Avec Répeter ... jusqu'à, la condition est vérifiée après chaque itération, tandis
qu'avec Tant que ... faire elle est vérifiée avant chaque itération.

D. Fonctions

L'intérêt de structurer un programme avec des fonctions est de décomposer le

programme en phases (acquisition de données, calcul, affichage de résultats, ...).
Cela augmente la modularité et la réutilisabilité des fonctions dans d'autres
programmes. Cela augmente aussi la lisibilité des programmes.

1. Généralités sur les fonctions

a) Définitions et notions

Définition : Fonction
Une fonction est un bloc d'instructions retournant une valeur associée à des
variables en entrée. Elle est utilisée pour faire un même calcul sur des entrées à
plusieurs endroits de l'algorithme.

Définition : Procédure
Une procédure est comme une fonction mais qui ne retourne rien. C'est
généralement un ensemble d'instructions pouvant être répéter à plusieurs endroits
de l'algorithme.

Prototype d'une fonction

Le prototype d'une fonction précise comment elle doit être utilisée (type retourné,
type de paramètres).
De façon générale le prototype est de la forme : FONCTION nom_fonction(type1
param1, type2 param2, ..., typen paramn) : type_retouravec :
 type_retour le type du résultat de la fonction ;
 nom_fonction le nom de la fonction ;
 typei et nomi représentent le type et le nom des paramètres en entrées.
Les paramètres sont séparés par des virgules et sont tous écrits avec leurs
types suivis de leurs noms. Au cas où il n'y a pas de paramètre on ne met
rien
Le prototype d'une procédure est de la forme PROCEDURE
nom_procedure(type1 param1, type2 param2, ..., typen paramn). On peut
remarquer qu'il n'y a pas de retour.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

20
 Introduction à l'algorithmique et à la programmation en C

Définition : Déclaration d'une fonction

On appelle déclaration d'une fonction, le prototype de cette fonction suivi d'un
point-virgule. La déclaration indique de quelle sorte de fonction il s'agit et permet
d'utiliser la fonction avant sa définition.

Exemple : Exemple de déclaration

Fonction minimum(Entier x, Entier y) :Entier ;
Procedure afficher_menu();

Définition : Définition de fonction

On appelle définition de fonction le prototype suivi d'un corps de la fonction
(partie Début à Fin). La définition doit apparaître une seule fois dans le programme
et indique ce que fait la fonction en terme d'opérations.

Exemple : Exemple de définition

Fonction minimum(Entier x, Entier y) :Entier
Début
Si (x<y) alors
retourner x ;
sinon
retourner y ;
Fin

Définition : Variables locales

Les variables déclarées à l'intérieur de la fonction sont des variables locales , i.e.
qu'on ne peut les utiliser qu'à l'intérieur de cette fonction . On peut trouver des
variables de même nom quelque part d'autre dans le programme mais qui ne
contiennent pas les mêmes données.

b) Fonctions polymorphes

Définition : Polymorphisme
Un élément typable d'un programme (identificateur, variable, fonction, ...) est dit
polymorphe s'il peut admettre plusieurs typages distincts.
Pour les fonctions, on dira qu'elles sont polymorphes si elles ont plusieurs
prototypes (avec des arguments et/ou le résultat qui peuvent être de types
différents dans les différents prototypes).

Exemple : Exemple d'utilisation de polymorphisme : fonctions

minimum pour 2 et 3 entiers
Fonction minimum(Entier x, Entier y) :Entier /*permet de calculer le minimum de
deux entiers*/
Fonction minimum(Entier x, Entier y, Entier y) :Entier /*permet de calculer le
minimum de trois entiers*/

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

21
 Introduction à l'algorithmique et à la programmation en C

Exemple : Exemple d'utilisation de polymorphisme : fonctions

division entière et réelle
Fonction division(Entier x, Entier y) :Entier /* division entière*/
Fonction division(Entier x, Entier y) :Reel /* division réelle*/

2. Fonctions récursives

a) Notion de récursivité

Définition : Définition de la récursivité

En algorithme, une fonction est dite récursive si elle se fait appel à elle-même, i.e.
que dans sa définition se contient elle-même en partie.

Pourquoi la récursivité ?
La récursivité permet de décrire des algorithmes de façon concise et naturelle. Le
principe est d'utiliser, pour décrire l'algorithme sur une donnée D, l'algorithme lui-
même appliqué à un ou plusieurs sous-ensembles de D, jusqu'à ce que le
traitement puisse s'effectuer sans nouvelle décomposition.
Dans une fonction récursive, il y a deux notions à retenir :
 la procédure s'appelle elle-même : on recommence avec de nouvelles
données ;
 il y a un test de fin : dans ce cas, il n'y a pas d'appel récursif.
Il est souvent préférable d'indiquer le test de fin des appels récursifs en début de
procédure.

Exemple : Algorithme d'illustration de la récursivité

FONCTION function_recursive(type1 param1, type2 param2, ..., typen
paramn) :type_retour
DEBUT
si condition faire /*condition d'arrêt*/
retourner calcul_fin ; /*cas élémentaire*/
sinon faire
function_recursive (d) ;
retourner calcul_intermediaire ;
fin si
FIN

b) Exemple d'utilisation de la récursivité

Factoriel d'un nombre
Le factoriel d'un nombre n donné est le produit des nombres entiers strictement
positifs inférieurs ou égaux à ce nombre n.
Si n=0, alors n ! = 1 ; sinon n ! = n * (n-1) !

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

22
 Introduction à l'algorithmique et à la programmation en C

La dernière définition permet de définir une fonction récursive pour le calcul du

factoriel d'un nombre car elle se rappelle une fois en factorielle (n-1) et il y a fin
des appels récursifs lorsque n vaut 0. La fonction factoriel (n) suivante permet de
calculer le factoriel de n :

Nombres de Fibonacci
On peut formuler la suite de Fibonacci sous forme de fonction pour n >= 0 :
si n <= 1 alors fibonacci (n) = n;
sinon fibonacci (n) = fibonacci (n-1) + fibonacci (n-2);
La fonction fibonacci(n) est récursive car elle s'appelle 2 fois en fibonacci(n-1) et
fibonacci (n-2) et s'arrête quand n=1.
Le programme C récursif correspondant est donné ci-dessous :

Puissance d'un nombre

Pour calculer un nombre xn (n>=0), on effectue n fois la multiplication de x par lui-
même, sauf si n vaut zéro auquel cas x0 vaut 1.
Ainsi, pour calculer 34 (3 à la puissance 4), on fait 3*3*3*3.
Une autre façon plus efficace de faire est de calculer 3 2 (3*3), et de multiplier ce
résultat par lui-même 3*3. Ainsi, si n est pair, le calcul de xn se ramène au calcul
de xn/2 que l'on multiplie par lui-même. Si n est impair, prenons le cas de 3 5 (3 à la
puissance 5), on calcule de même 32 que l'on multiplie par lui-même 32 puis par 3.
On applique récursivement la même méthode pour calculer 32. Le programme qui
en découle est donné ci-dessous. On pourrait ajouter un cas particulier pour n=1,
mais il n'est pas nécessaire du point de vue algorithmique.

E. Langage C

1. Généralités

Dans cette partie nous définirons des notions élémentaires sur le langage C

a) Compilateur

Définition : Qu'est-ce qu'un compilateur ?

Un compilateur est un programme informatique qui traduit un code dans un
langage, le code source, en un autre code dans un autre langage appelé le code
cible.
Un compilateur sert le plus souvent à traduire un code source écrit dans un langage
de programmation en un code habituellement en langage d'assemblage ou
langage machine. Le code en langage machine produit par un compilateur est
appelé code objet.
Pour avoir un programme exécutable il faut faire une édition de liens du code
objet ; ce qui fournira un code exécutable ou code machine.

b) Structuration d'un code source en C

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

23
 Introduction à l'algorithmique et à la programmation en C

Exemple : Exemple avec la résolution d'équation du second degré

/*Importation de librairies*/
#include <stdio.h>
#include <conio.h>
/*Déclarations de variable*/
float a, b, c, r1, r2, delta ;
/*Programme principale*/
int main(){
.........
getch() ; // permet d'attendre que l'utisateur saisisse avant de quitter
l'interface d'exécution
return 0 ; // le lanceur est une fonction qui retourne int donc on retourne
0 par exemple
}

c) Premier code C: Bonjour

Exemple : Implémentation en C de Bonjour

#include <stdio.h>
#include <conio.h>
int main(){
printf("Bonjour !\n") ; //affiche bonjour
getch() ;
return 0 ;
}

Exemple : Lire un nombre en C

#include <stdio.h> /*Pour lire et écrire*/
/*déclaration de variable*/
int age ;
char sexe ;
float moyenne ;
/*Programme principal*/
int main()
{
puts("Bonjour et bienvenue") ;
printf("Entrer votre age :") ;
scanf("%d",&age) ;
printf("Entrer votre sexe :") ;
sexe=getch() ; putchar(sexe) ;getch() ;
printf("Entrer votre moyenne :") ;
scanf("%f",&moyenne) ;
/*affichage */
puts("Merci ! Recaputilatif") ;
return 0 ;
}

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

24
 Introduction à l'algorithmique et à la programmation en C

Le format d'affichage et de lecture correspondant aux réels (float) est %f. Dans
l'exemple cela est remplacé, lors de l'affichage par la valeur de x.

d) Types de donnée en C
Variables et opérations
Une déclaration de variables a la forme : type nom_variable ou type
nom_variable=valeur
Exemple :
float x ;
int matricule = 12 ;
int min, max=1000 ;

Type entier int

Le type int (abbréviation de integer) est le type des entiers en C.
Il est codé sur 4 octets, donc les valeurs sont comprises entre -2 31 et 231-1. Mais
sur certains anciens systèmes c'est toujours codé en 2 octets.
Les opérations : +, -, * sont définies sur les int et donnent des int. La division
/entre deux int est une division euclidienne. L'opération modulo, % donne le reste
de la division entre deux int.
Exemple : pour lire un entier saisie
int x ;
scanf("%d", x) ;

Les types réels float et double

float (codé sur 4 octets) et double (codé sur 8 octets) permettent de représenter
les réels avec une certaine précision.
Les opérations sont -, +, *, / ainsi que le moins unaire.
Exemple : pour lire un float saisie
float x ;
double y ;
scanf("%f%lf", x,y) ;

Le type char
Le type char codé sur 1 octet représente les caractères.
Un char peut être considéré comme un int (code ASCII) et les valeurs de -126 à
125 servent à représenter les caractères.
Exemple : pour lire un caractère saisie
char x ;
scanf("%c", x) ;

Les types unsigned

Aux types char et int correspondent des types unsigned int et unsigned char qui
représentent seulement les valeurs positives.
Exemple : pour lire un entier positif saisie
unsigned int x ;
scanf("%u", x) ;

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

25
 Introduction à l'algorithmique et à la programmation en C

Affectations et conversions
L'affectation consiste à recopier le contenu d'une variable dans une autre
En C cela se matérialise par l'opérateur =
Si les deux variables sont de types différents on peut réaliser dans l'affectation une
conversion, quand c'est possible .
Exemple :
int var1=0 , var2=2;
float x=3.6 ;
unsigned char c ;
unsigned int a=366 ;
var1=var2+9 ; // var1 est égale alors à 11
var2=(int)x ;//conversion de réels en entier var2 vaut 3 soit la partie entière de x
c=(unsigned char) a ;// c vaut alors 110 soit 366%256

Définition des constantes

Les constantes en C se déclarent juste après les #include à l'aide du mot clé
#define
Exemple :
#define Pi 3.14

e) Affectation et opérations

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

26
 Introduction à l'algorithmique et à la programmation en C

Définition : L'affectation
L'affectation permet de changer la valeur d'une variable, c'est à dre de modifier le
contenu de la mémoire à l'adresse symbolisée par le nom de la variable.
Syntaxiquement, une affectation sera représentée par : nom_variable=expr et a
pour signification : la variable de nom nom_variable prend pour valeur la valeur de
l'expression expr, ce qui revient à stocker la valeur de l'expression expr dans la
mémoire à l'adresse symbolisée par le nom nom_variable. La valeur de l'expression
expr doit appartenir au type déclaré pour la variable nom_variable.

Définition d'une expression

 L'expression affectée à une variable peut être une valeur explicite : par
exemple, l'instruction a=25 affecte la valeur 25 à la variable de nom a.
 L'expression affectée à une variable peut également être la valeur contenue
dans une autre variable : par exemple, l'instruction a=b affecte à la variable
de nom a la valeur contenue dans la variable de nom b.
 Enfin, l'expression affectée à une variable peut être le résultat d'une
opération entre d'autres expressions.
Il existe 3 types d'opérations : les opérations arithmétiques, les opérations de
comparaison et les opérations logiques.

Les opérations arithmétiques

 Les opérations arithmétiques binaires sont : l'addition notée "+", la
soustraction notée "-", la multiplication notée "*", la division réelle notée "/",
la division entière notée "div" et le modulo noté "mod". Ces opérations
prennent en argument deux expressions numériques et rendent la valeur
numérique correspondant à l'application de l'opération sur les valeurs des
expressions en argument.
Ces opérations sont définies sur les réels et sur les entiers, sauf "div" et
"mod" qui ne sont dé?finies que sur les entiers.
Enfin, les opérateurs de multiplication, de division et de modulo sont plus
prioritaires (et donc évalués avant) que les opérateurs d'addition et de
soustraction. Une expression arithmétique peut être parenthésée pour
spécifier l'ordre de son évaluation.
 Les opérations arithmétiques unaires sont le plus unaire noté "+", et le
moins unaire noté "-". Ces opérations prennent en argument une expression
numérique et rendent une valeur numérique.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

27
 Introduction à l'algorithmique et à la programmation en C

Définition : Les opérations de comparaison

Une opération de comparaison prend en argument deux expressions de même type
élémentaire (2 entiers,2 réels, 2 caractères ou 2 chaînes de caractères), et rend
une valeur logique (vrai ou faux). On utilisera les opérations de comparaison
suivantes : <;<=;==; != ou <>;=>et >.
 Les entiers et les réels sont comparés selon l'ordre numérique usuel.
 Les caractères sont comparés selon l'ordre défini par le code ASCII.
 Les chaînes de caractères sont comparées selon l'ordre lexicographique : un
texte t1 est inférieur à un texte t2 s'il existe un caractère c de t1 tel que
pour chaque caractère se trouvant avant c dans t1, le caractère
correspondant de t2 soit identique, et le caractère correspondant à c dans t2
soit supérieur à c.
Par exemple, "aabcd" < "aax" et "10" < "9".

Les opérations logiques

 Les opérations logiques binaires sont la disjonction ||, et la conjonction &&.
Elles prennent en argument 2 expressions à valeur logique et rendent une
valeur logique ;
Vrai et Vrai fait Vrai, le reste Faux et Faux ou Faux fait Faux le reste fait Vrai
 L'opération logique unaire est la négation !. Cet opérateur prend en
argument une expression de valeur logique et rend la valeur logique
opposée ; !Vrai fait Faux

f) Entrées-sorties en C avec stidio.h

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

28
 Introduction à l'algorithmique et à la programmation en C

Définition : Qu'est-ce qu'une bibliothèque ?

Une bibliothèque est un ensemble de fonctionnalités ajoutées à un langage de
programmation et qui porte sur un thème donné.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

29
 Introduction à l'algorithmique et à la programmation en C

Complément : Exemples de bibliothèques

En C on a comme exemples de bibliothèques les bibliothèques suivantes :
 math.h contient les fonctions mathématiques de calcul numérique ;
 time.h contient les types et fonctions pour gérer la date, l'heure, le temps
d'exécution du programme, ...
 float.h contient les limites et constantes des types float et double ;
 stdio.h contient les types et fonctions pour gérer les entrées-sorties, c'est à
dire les saisies au clavier, l'affichage de texte, mais aussi les fichiers
Pour utiliser une bibliothèque, on met en début de programme le mot clé #include
suivi du nom de la bibliothèque entre < et >
Exemple : #include <stdio.h>

Afficher des données à l'écran

 Pour afficher un caractère on peut utilisé putchar('caractère') ou
putchar(code caractère)
Exemple : putchar('A') et putchar(65) affiche les mêmes choses
 Pour afficher une chaîne de caractère ou un texte on utilise puts ou printf
Exemple :
puts("Welcome") ;
printf("in the classroom") ;
Avec puts on revient à la ligne tandis qu'avec printf on reste sur la même
ligne
 Pour afficher des nombres, on utilise printf et on spécifie un format
Par exempl :
char car='C' ;
printf("%c", car) affiche C tandis que printf("%d", car) affiche 67
La spécification du format est nécessaire avec le printf et il faut
veiller à ce que ce soit conforme au type à afficher !
- Le format des entiers (int) est %d ;
Exemple :
int n =12;
printf("%d", n) ;
- Le format des réels (float et double) usuel est %f et le format le plus
précis %lf ;
Exemple :
float f =2.0/3.0;
printf("%f", f) ; //ou printf("%lf", f) ;
On peut préciser le nombre de chiffres après la virgule avec %. ?f où ?
est le nombre de chiffres
printf("%.3f", f) affiche 0.667
- Pour afficher une chaîne de caractères le format est %s
On peut combiner l'affichage des messages avec l'affichage des données
numériques comme suit :
printf("La partie entière est %d et la partie réelle est %f", n, f) ;
Avec printf on peut provoquer un retour à la ligne avec \n comme dans
printf("Bonjour \n") ;

Lecture au clavier
 getchar permet de lire les caractères ;

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

30
 Introduction à l'algorithmique et à la programmation en C

 Pour les autres on utilise scanf et on spécifies les formats comme suit :
- %d pour les int ;
- %u pour les unsigned int ;
- %f pour les float ;
- %lf pour les double ;
- %c pour les char ;
- %s pour les chaines de caractères
En plus on utilise le &dans scanf devant chaque variable comme dans scanf("%d",
&n) ;

2. Enchaînement d'instructions

a) Exécution conditionnelle en C
Condition Si ... alors
if(expression){
//instructions ;
}
expression est une expression booléenne qui peut retourner vraie ou faux. Les
instructions s'exécutent si expression est vraie.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

31
 Introduction à l'algorithmique et à la programmation en C

Exemple
if(delta<0){
printf("Pas de solution dans R") ;
}

Condition Si ... alors ... sinon

if(expression){
//instructions si vraie;
}else{
//instructions si faux ;
}
Dans ce cas "instructions si vraie" s'exécutent, lorsque expression est vraie et
"instructions si faux" sinon.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

32
 Introduction à l'algorithmique et à la programmation en C

Exemple
if(delta<0){
printf("Pas de solution dans R") ;
}else{
r1=(-b-sqrt(delta))/(2*a) ;
r2=(-b+sqrt(delta))/(2*a) ;
printf("La solution est (%f ;%f)", r1, r2) ;
}

Le switch
Le if permet de distinguer deux cas selon la valeur d'une expression logique. Le
switch permet de distinguer plusieurs cas selon les valeurs d'une variable entière.
char choix=getchar();
switch(choix){
case 'a' : puts("Votre choix est a") ;
break ;
case 'b' : puts("Votre choix est b") ;
break ;
case 'c' : puts("Votre choix est c") ;
break ;
default : puts("Votre choix est différent de a, b, et c") ;
}

b) Itération en C
Boucle While pour implémenter Tant que ... faire
while (condition){
...
}

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

33
 Introduction à l'algorithmique et à la programmation en C

Exemple
int i=1 ;
int resultat=1 ;
while(i<10){
resultat = resultat * i ;
i++ ;// équivalent de i=i+1 ;
}
print ("%d", resultat) ; //affiche factoriel de 9

Boucle do ... while pour implémenter répéter ... jusqu'à

do{
...
}while(condition)

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

34
 Introduction à l'algorithmique et à la programmation en C

Exemple
int i=1 ;
int resultat=1 ;
do{
resultat = resultat * i ;
i++ ;
}while(i<10)

Boucle for pour implémenter pour

for(compteur=valeur_initiale ; compteur=valeur_finale ; incrément){
...
}

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

35
 Introduction à l'algorithmique et à la programmation en C

Exemple
int i=1 ;
int resultat=1 ;
for(i=0 ;i<10 ;i++{
resultat = resultat * (i+1) ;
}

3. Fonctions en C

a) Déclaration, définition et appel

Déclaration
On appelle prototype d'une fonction la syntaxe qui donne ses paramètres et son
type de retour :
type nom_fonction(type1 param1, ..., typen paramn) ;
Par exemple int minimum(int x, int y) ; est le prototype d'une fonction minimum
qui permet de déterminer le minimum de deux entiers.
La déclaration d'une fonction consiste à écrire son prototype dans la partie de
déclaration des autres variables.

Définition
La définition d'une fonction consiste à donner le code de la fonction ; c'est à dire
l'ensemble des instructions qu'elle exécute pour fournir le résultat demandé. On
peut définir la fonction avant ou après la fonction main(). Si on veut le faire après
la fonction main il est impératif de la déclarer avant.
Un exemple de définition de la fonction minimum est :
int minimum(int x, int y){
if(x>y)
return y ;
else
return x ;
}
le mot clé return permet de retourner la variable du type de retour demandé.

Appel
Pour utiliser une fonction on fait ce qu'on appelle un appel de la fonction. La
syntaxe est la suivante :
nom_fonction(param1, ..., paramn) ;
ici on ne met plus les types des paramètres ou de la fonction.
Par exemple :
int minimum(int x, int y){
if(x>y)
return y ;
else
return x ;
}
int main(){

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

36
 Introduction à l'algorithmique et à la programmation en C

int a, b ;
printf("Entrer deux entiers :") ;
scanf("%d %d", &a, &b) ;//Lecture de deux entiers à partir d'un seul scanf.
L'espace entre les %d ; oblige à taper espace entre le premier et le second comme
10 26.
printf("Le minimum est %d", minimum(a,b)) ; //appel de la fonction minimum
}

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

37
 Introduction à l'algorithmique et à la programmation en C

Exemple : Fonction de lecture des éléments d'un rationnel lors du

produit de deux rationnels
#include <stdio.h>
#include <conio.h>
typedef struct{
int num;
int den;
}rationnel;
rationnel lecture() ; //déclaration d'une fonction rationnel qui retourne un rationnel
mais qui ne prend rien en paramètres
int main(){
rationnel a, b, prod;
a=lecture() ;
b=lecture() ;
[Link]=[Link]*[Link];
[Link]=[Link]*[Link];
printf("Le produit de %d/%d par %d/%d est %d/%d .", [Link], [Link], [Link],
[Link], [Link], [Link]);
getch();
return 0;
}
rationnel lecture(){ //définition de la fonction lecture
rationnel a ;
printf("Entrer le numérateur du rationnel: ");
scanf("%d", &[Link]);
printf("Entrer le denominateur du rationnel: ");
scanf("%d", &[Link]);
return a ; //renvoie le rationnel lu.
}

b) Polymorphisme et récursivité
Polymorphisme
Une fonction polymorphe est une fonction qui peut avoir plusieurs prototypes. Pour
chacune des prototypes il faudra faire la définition et on pourra ensuite appeler la
fonction avec l'une ou l'autre des prototypes sans rien préciser.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

38
 Introduction à l'algorithmique et à la programmation en C

Exemple : Fonctions polymorphes

#include <stdio.h>
#include <conio.h>
int minimum(int x,int y) ;//minimum de deux entiers
int minimum(int x,int y, int z) ;// minimum de 3 entiers;
int main(){
int a, b, c;
printf("Entrer trois entiers : ") ;
scanf("%d %d %d", &a, &b, &c) ;
printf("Le minimum de %d et %d est %d et le minimum de %d, %d, et %d est
%d", a, b, minimum(a,b),a, b, c, minimum(a,b,c));
getch();
return 0;
}
int minimum(int x, int y){ //définition de la fonction division entière
return x>y? y:x ; //renvoie le résultat. la partie x>y? y:x; est la forme contractée
de si x>y le minimum est y sinon le minimum est x
}
int minimum(int x, int y, int z){ //définition de la fonction division réelle
return z>minimum(x,y)? minimum(x,y) : z ; //renvoie le résultat
}
permet d'avoir deux fonctions minimum pour les calculs du minimum de deux ou
trois entiers.

Récursivité
Une fonction récursive est simplement une fonction qui fait appel à elle même.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

39
 Introduction à l'algorithmique et à la programmation en C

Exemple : Fonction récursive

long factoriel (int n){
if(n==0)
return 1 ;
else
return factoriel(n-1)*n ; // appel récursif
}

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

40
 Structures de
II -

II
données statiques

Types de données composés 47

Tableaux et structures en C 52

A. Types de données composés

 Considérons l'exercice suivant :

Soit N un entier donné. Ecrire un algorithme permettant de :
- Lire le nombre N ;
- Lire N entiers ;
- Calculer le nombre de doublons parmi les n entiers.
Comme à chaque entier saisi par l'utilisateur il faut vérifier s'il n'est pas
identique aux entiers précédents, on a besoin de sauvegarder quelque part
les n entiers. La façon de le faire serait de déclarer n variables qui
contiendraient les n entiers et comparer ces n variables. Mais comme le n
peut être très grand, ce n'est pas réaliste de définir autant de variables et
par ailleurs la déclaration se faisant avant la lecture du n on aurait du mal à
déclarer le nombre adéquat de variables.
Pour pallier à ce problème on définit un autre type de données qui permet
de sauvegarder n données de même type à partir d'un seul nom de variable.
Il s'agit du tableau.
 Supposons maintenant que l'on veuille écrire un algorithme qui calcule le
classement par rang en fonction des moyennes des étudiants . On aura alors
besoin pour chaque étudiant de connaître sa moyenne (entrée), son rang
(sortie) et son identifiant (admettons que cela soit un numéro). Pour
représenter ces informations on a besoin de définir un type de données qui
puisse contenir des données de types différents. Il s'agit des structures ou
enregistrements.
 Il y a aussi deux autres types composés qu'on utilise souvent :
- Les énumérations permettent de définir un ensemble de constantes
possibles qui peuvent correspondre à une donnée;
- Les unions permettent de définir des types de données possibles pour
une donnée

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

41
 Structures de données statiques

1. Énumération

a) Énumération
Énumération
2. Union

a) Union
Union
3. Tableaux

a) Déclaration d'un tableau

Déclaration
Pour déclarer un tableau on utilise la syntaxe Tableau
[index_minimal,...,index_maximal] de nom_Type nom_variable ; où :
 Tableau est un mot clé à utiliser dans chaque déclaration de tableau ;
 [index_minimal,...,index_maximal] représente les index du tableau (donc les
index utilisables sur le tableau pour accéder à ses éléments) ;
 nom_Type représente le type des données dans le tableau ;
 et nom_variable est le nom de la variable représentant le tableau qui va
servir à lire et écrire les éléments du tableau.
Par exemple :
Tableau [1, ..., 10] de Réel Notes ;// Permet de stocker et utiliser 10 Notes qui sont
des nombres flottants.
Tableau ['a', ..., 'e'] d'Entier codes ;// Permet aussi de stocker et utiliser 5 codes
qui sont des valeurs entières.

Initialisation à la déclaration
Si l'on veut déclarer un tableau à sa déclaration on utilisera la syntaxe
Tableau [index_1,...,index_max] de nom_Type nom_variable <==
{val_index_1, val_index_2, ..., val_index_max};
Par exemple :
Tableau [1, ..., 10] de Réel Notes <=={12.6, 15, 14, 11, 17, 10.5, 11.5, 15, 13.7,
14.2} ;
Tableau ['a', ..., 'e'] d'Entier codes <=={356, 251, 142, 36, 17} ;

b) Accès aux élément d'un tableau

Accès aux éléments d'un tableau
Pour accéder à l'élément à l'index i d'un tableau on utilise la syntaxe
nom_variable_Tableau[i] ;
Par exemple :
Notes[1]<==12.6 ;
Codes["c"]<==127 ;
NB : il faut que l'index utilisé soit inclus dans les index possibles (intervalle) sinon
on lira une donnée erronée.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

42
 Structures de données statiques

c) Nombre d'éléments du tableau

Nombre d'éléments du tableau
Dans la déclaration d'un tableau, on a besoin de désigner sa taille. Il y a deux
façons de faire :
 La première est utilisée lorsque le nombre d'éléments est fixé dans le
problème. On peut alors utilisé une constante pour l'index maximal.
Par exemple :
...
Déclarations
Entier i ;
Constantes
MAX<==10 ;
Tableau [1, ...,MAX] de Réels Notes ;
...
Pour i allant de 1 à MAX faire
Notes[i]<==i ;
Fin Faire
 Dans le deuxième cas, le nombre d'éléments du tableau n'est pas connue ;
on borne alors ce nombre. On utilise aussi une constante mais on calcule par
la suite la taille réelle du tableau qu'on utilisera dans les autres calculs.
Par exemple :
...
Déclarations
Entier i , taille_tableau; // on suppose alors que taille_tableau <=MAX
Constantes
MAX<==100 ;
Tableau [1, ...,MAX] de Réels Notes ;
...
Lire(taille_tableau) ;
Pour i allant de 1 à taille_tableau faire
Notes[i]<==i ;
Fin Faire
MAX sera le nombre de places mémoires réservées et taille_tableau
représentera le nombre de places utiles.

d) Tableaux à plusieurs dimensions

Tableaux à plusieurs dimensions
On peut déclarer un tableau à plusieurs dimensions de la même manière qu'un
tableau simple avec la syntaxe
Tableau [index_minimal_dim1,...,index_maximal_dim1]
[index_minimal_dim2,...,index_maximal_dim2] ...
[index_minimal_dim_max,...,index_maximal_dim_max] de nom_Type
nom_variable ;
Par exemple
Tableau [1, ..., 3][1,..., 5] d'Entier matrice ;
matrice[1][1]<==0 ;

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

43
 Structures de données statiques

e) Opérations sur les tableaux

Opérations sur les tableaux
Pour des tableaux de même dimension, de même taille, et contenant des valeurs de
même type on peut faire les opérations suivantes :
 l'affectation nom_tab1<==nom_tab2 ; initialise le tableau nom_tab1 avec
les valeurs dans nom_tab2 ;
 la comparaison nom_tab1==nom_tab2 ; retourne vrai si les valeurs dans
les deux tableaux sont identiques suivant les index, faux sinon;
 la comparaison nom_tab1!=nom_tab2 ; retourne vrai si deux des valeurs
dans les deux tableaux sont aux mêmes index mais non identiques en
valeur, faux sinon.

4. Structures

a) Les structures ou enregistrements

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

44
 Structures de données statiques

Définition : Qu'est-ce qu'une structure ?

Une structure, encore appelée enregistrement, est une entité de stockage de
données comme un tableau mais qui à la différence du tableau peut contenir des
valeurs de types différents.

Déclaration d'une structure en algorithmique

Dans les algorithmes nous utiliserons la déclaration suivante pour les structures :
Enregistrement nom_structure
Début
type1 variable1 ;
type2 variable2 ;
...
typen variablen ;
Fin
Dans ce cas on déclarera les entités de type nom_structure comme suite :
Enregistrement nom_struture enregistrement1, enregistrement2;

Exemple : Exemple de structures de données

Enregistrement Etudiant
Début
Entier age ;
Tableau [1...20] de caractères nom ;
Tableau [1...40] de caractères prenom ;
Fin
Enregistrement Etudiant Aly, Lisa ;

Utilisations d'une structure

 Pour accéder au champ variable1 d'une structure nom_structure on utilisera
la notation nom_structure.variable1 comme dans « [Link]<==19 » ou
« Lire([Link] »« ) »;
 On peut affecter une entité d'une structure à une autre structure comme
dans « Aly=Lisa ; » ce qui donnera aux valeurs de champs d'Aly les valeurs
des champs de Lisa ;
 On peut aussi initialiser le contenu d'une structure comme on le fait avec les
tableaux. Par exemple Aly<=={19, "Sanou", "Aly Ben"} ;
 Les structures sont des types et à ce titre on peut :
- définir des tableaux de structures
Par exemple : Tableau [1,...,100] d'Enregistrement Etudiant fc2 permet
de définir un tableau pour 100 étudiants (donc 100 ages, 100 noms et
100 prénoms) ;
- définir des structures à l'intérieur de structures
Par exemple on peut définir une structure identifiant pour le nom et le
prénom et l'utiliser dans la définition de la structure Etudiant comme suit
Enregistrement identifiant
Début
Tableau de caractères nom[20] ;
Tableau de caractères prenom[40] ;
Fin
Enregistrement Etudiant

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

45
 Structures de données statiques

Début
Entier age ;
Enregistrement identifiant nom_prenom ;
Fin
Dans ce cas si on a Enregistrement Etudiant Aly, alors pour accéder à
son champ nom on fera Aly.nom_prenom.nom.

B. Tableaux et structures en C

1. Tableaux

Déclaration d'un tableau en C

Pour déclarer un tableau en C, on utilise la syntaxe :
type_elements nom_variable_tableau[constante_taille_du_tableau] ;
où :
 type_elements représente le type des éléments contenus dans le tableau ;
 nom_variable_tableau le nom de la variable qui représente le tableau ;
 et constante_taille_du_tableau un entier ou une constante entière
représentant la taille (le nombre d'éléments que peut contenir le tableau) du
tableau.
Exemple :
#define const_taille 15 ;
int tab[10] ; //déclaration d'un tableau de 10 entiers
float tab1[const_taille] ; //déclaration d'un tableau de 15 réels

Accès aux éléments d'un tableau en C

Pour accéder aux éléments d'un tableau en C on utilise la syntaxe :
nom_variable_tableau[index_element] ; où
 nom_variable_tableau est le nom de la variable déclaré en tant que
tableau ;
 et index_element est un entier positif indiquant l'index de l'élément auquel
on veut accéder.
Exemple :
tab[5]=102 ;
printf("%d", tab[5]) ;// affiche 102 ;

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

46
 Structures de données statiques

Remarque : Attention !
 En C, le premier élément est à l'index 0. Par conséquent pour un tableau de
taille N les index iront de 0 à N-1 ;
 Un élément du tableau (tab[i]) peut être considéré comme une variable d'où
l'écriture et la lecture formatées (printf("%d", tab[i]) ; et scanf("%d",
&tab[i]) ; ) ;
 On ne peut pas comparer directement deux tableaux (tab1==tab2 ou tab1 !
=tab2 ne signifient pas qu'on compare le contenu de tab1 et tab2 mais leur
adresse, c'est à dire les numéros des cases réservées pour chacun. Ces
numéros peuvent être différents et les contenus identiques. On fera donc les
tests pour chaque élément à l'aide d'itération comme dans :
« int i, test=1 ; »
« for (i=0 ; i<10 ; i++) »
« if(tab1[i] !=tab2[i]) »
« test=0 ; »
« if(test==1) »
« printf("tab1 est égal à tab2") ; »
« else »
« « printf("tab1 est différent de tab2") ; » »

Exemple : Programme pour remplir un tableau de 10 entiers avec

les puissances de 2 et l'afficher
#include <stdio.h>
#include <conio.h>
int main(){
int i,tab[10];
tab[0]=1; // 2 à la puissance 0 fait 1
for (i=1; i<10; i++) //Remplissage
{
tab[i]=2*tab[i-1];
}
for (i=0; i<10; i++)//Affichage
{
printf("%d\t", tab[i]); //\t permet d'afficher et décaler sur la prochaine colonne
}
getch();
return 0;
}

2. Structures

Déclaration de structures en C
Pour déclarer une structure en C, on utilise la syntaxe :
struct nom_structure{
type1 nom_variable1 ;
type2 nom_variable2 ;

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

47
 Structures de données statiques

...
typen nom_variablen ;
} [var1, var2, ..., vark] ; // [] signifie qu'on peut définir ou pas à la suite des
variables de type nom_structure. Au cas où on ne le fait pas, par exemple, on peut
ensuite définir à tout moment une variable de type nom_structure avec la syntaxe
struct nom_structure vari ;
Exemple :
struct etudiant{
int age ;
float moyenne ;
char nom[20] ;
} eric ; //eric est une variable de type structure etudiant ;
struct etudiant aly ; // aly est aussi une variable de type structure etudiant ;

Déclaration d'un nouveau type

Pour éviter les lourdeurs dans les déclarations on peut définir la structure comme
un nouveau type à l'aide de du mot clef typedef. La syntaxe pour le faire est :
typedef struct [nom]{
type1 var1 ;
type2 var2 ;
...
typen varn ;
}nom_nouveau_type [var_type_1, ..., var_type_2] ;
Par exemple :
typedef struct{
int age ;
float moyenne ;
char nom[20] ;
} etudiant ;
permet de définir etudiant comme un nouveau type ; c'est à dire qu'on peut ensuite
écrire etudiant a, b, c ; (comme int x, y ; etudiant est désormais un type comme
int, float, char).

Accès aux champs d'une structure

Pour accéder aux champs d'une structure, on utilise la syntaxe :
nom_var_structure.nom_champ ;
Par exemple avec
typedef struct{
int age ;
float moyenne ;
char nom[20] ;
} etudiant ;
et etudiant aly ;
on peut accéder à l'age d'aly par [Link].
Donc on peut écrire :
[Link]=36 ;
printf("%d", [Link]) ; //affiche 36 ;

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

48
 Structures de données statiques

Exemple : Produit de deux rationnels

#include <stdio.h>
#include <conio.h>
int main(){
typedef struct{
int num;
int den;
}rationnel;
rationnel a, b, prod;
printf("Entrer le numérateur du premier rationnel: ");
scanf("%d", &[Link]);
printf("Entrer le denominateur du premier rationnel: ");
scanf("%d", &[Link]);
printf("Entrer le numérateur du second rationnel: ");
scanf("%d", &[Link]);
printf("Entrer le denominateur du second rationnel: ");
scanf("%d", &[Link]);
[Link]=[Link]*[Link];
[Link]=[Link]*[Link];
printf("Le produit de %d/%d par %d/%d est %d/%d .", [Link], [Link], [Link],
[Link], [Link], [Link]); // affiche par exemple Le produit de 2/3 par 4/5 est
8/15.
getch();
return 0;
}

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

49
 Structures de
III -

III
données
dynamiques

Notions élémentaires sur les pointeurs 57

Notions élémentaires sur les pointeurs en C 66
Allocation dynamique de mémoire en C 66
Fichiers en C 66

A. Notions élémentaires sur les pointeurs

1. Généralités sur les pointeurs

Notion d'adresse
 Tout objet manipulé par l'ordinateur est stocké dans la mémoire. La
mémoire est comme une armoire constituée d'une série de “cases” dans
lesquelles sont stockées les valeurs des variables. Pour pouvoir accéder à la
valeur d'une variable, il faut alors connaître le numéro de cette case.
Autrement dit, il faut connaître l'emplacement en mémoire de l'objet à
manipuler. Cet emplacement est appelé l'adresse de la case mémoire, et par
extension, l'adresse de la variable stockée dans cette case et celles qui la
suivent.
 Toute case mémoire a une adresse unique.
 Lorsqu'on utilise une variable, le compilateur manipule l'adresse de cette
dernière pour y accéder. C'est lui qui connaît cette adresse, le programmeur
n'a pas à s'en soucier.

Définition : Qu'appelle-t-on pointeur

Un pointeur est une variable qui contient l'adresse d'un objet (par exemple une
autre variable). On dit que le pointeur pointe sur la variable pointée. Pointer
signifie “faire référence à”.

Remarques générales
 Une adresse est une valeur. Cette valeur est constante, car en général un
objet ne se déplace pas en mémoire.

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

51
 Structures de données dynamiques

 La valeur d'un pointeur peut changer: cela ne signifie pas que la

variable pointée est déplacée en mémoire, mais plutôt que le pointeur pointe
sur autre chose.
 Afin de savoir ce qui est pointé par un pointeur, les pointeurs disposent d'un
type. Ce type est construit à partir du type de l'objet pointé. Cela permet au
compilateur de vérifier que les manipulations réalisées en mémoire par
l'intermédiaire du pointeur sont valides. Le type des pointeur se lit “pointeur
de ...” où les points de suspension représentent le nom du type de l'objet
pointé.

Fondamental : Déclaration de pointeur

Les pointeurs se déclarent en donnant le type de l'objet qu'ils devront pointer, suivi
de leur identificateur précédé d'une étoile:
Type_Objet *identificateur ;
« Exemple : Entier *tableau ; »

Remarque : Déclaration de plusieurs pointeurs

Pour déclarer plusieurs pointeurs, l'étoile doit être répétée comme dans l'exemple
qui suit : Entier *pi1, j, *pi2;. Ici, pi1, pi2 sont des pointeurs d'entiers et j est un
entier.

2. Déréférencement et indirection

Notions de deréférencement et d'indirection

 On appelle indirection le fait d'accéder à l'adresse d'une variable ou d'une
fonction et l'opérateur associé est & .
 On appelle déréférencementle fait d'accéder à l'objet référencé par le
pointeur et l'opérateur associé est * .

Remarque : Initialisation des pointeurs

Il est important de s'assurer que les pointeurs que l'on manipule contiennent
l'adresse d'un objet valide. En effet, accéder à un pointeur non initialisé revient à
lire ou, plus grave, à écrire dans la mémoire à un endroit complètement aléatoire .
En général, on initialise les pointeurs dès leur création, ou, s'ils doivent être utilisés
ultérieurement, on les initialise avec le pointeur nul. Cela permettra de faire des
tests sur la validité du pointeur ou de détecter les erreurs car l'utilisation d'un
pointeur initialisé avec le pointeur nul génère souvent une faute de protection du
programme, que le débogueur est capable de détecter. Le pointeur nul se note
NULL.

Exemple : Déclaration de pointeurs

Entier i=0; /* Déclare une variable entière. */
Entier *pi; /* Déclare un pointeur sur un entier. */
pi=&i; /*Initialise pi avec l'adresse de i. */
*pi = *pi+1; /* Effectue un calcul sur la variable pointée par par pi, i.e. sur i lui-
même, puisque pi contient l'adresse de i.À ce stade, i ne vaut plus 0, mais 1. */

Fondamental : Pointeur de structures

L'accès aux champs d'une structure par le pointeur sur cette structure se fera avec

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

52
 Structures de données dynamiques

l'opérateur '->', qui remplace '(*).'.

Exemple : Utilisation de pointeurs de structures

Enregistrement Client
Début
Entier Age;
Fin
Enregistrement Client structure1;
Enregistrement Client *pstr = &structure1;
pstr->Age <== 35; /* équivalent de (*pstr).Age<==35; */

3. Passage de paramètres

Passage de paramètres à une fonction/procédure

Il y a deux méthodes pour passer des variables en paramètres dans une fonction:
le passage par valeur et le passage par adresse. Ces méthodes sont décrites
ci-dessous.

Passage par valeur

La valeur de la variable passée en paramètre est copiée dans une variable locale.
C'est cette variable qui est utilisée pour faire les calculs dans la fonction appelée.
Aucune modification de la variable locale dans la fonction appelée ne modifie la
variable passée en paramètre, parce que ces modifications ne s'appliquent qu'à une
copie de cette dernière.

Exemple : Passage de paramètre par valeur

...
Entier i <==2;
Debut
Afficher(test(i)); //Le retour est 3.
Afficher (i); // i n'est pas modifié. Il vaut toujours 2.
Fin
//fonction test
Fonction test(Entier j) :Entier //j= copie de la valeur passée en paramètre
Début
j<==3; // Modifie j, mais pas i
retourner j ;
Fin

Passage par adresse

La deuxième technique consiste à passer non plus la valeur des variables comme
paramètre, mais à passer les variables (adresses) elles-mêmes. Il n'y a donc plus
de copie, plus de variables locales. Toute modification du paramètre dans la
fonction appelée entraîne la modification de la variable passée en paramètre.

Exemple : Exemple Passage de paramètre par variable en C

...

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

53
 Structures de données dynamiques

Entier i <==2;
Debut
Afficher(test(&i)); //le retour est 3. Passage par adresse
Afficher(i); //Le contenu de i est modifié. Il vaut 3..
Fin
//fonction test
Fonction test(Entier *j) //j= adresse de i
Début
j<==3; // Modifie j et donc i
Fin

Avantages et inconvénients des deux méthodes

 Les passages par adresses sont plus rapides et plus économes en
mémoire que les passages par valeur, puisque les étapes de la création de la
variable locale et la copie de la valeur ne sont pas faites. Il faut donc éviter
les passages par valeur dans les cas d'appels récursifs de fonction ou de
fonctions travaillant avec des grandes structures de données (matrices par
exemple) ;
 Les passages par valeurs permettent d'éviter de détruire par
mégarde les variables passées en paramètre. Si l'on veut se prévenir
de la destruction accidentelle des paramètres passés par variable, il faut
utiliser le mot-clé const. Le compilateur interdira alors toute modification de
la variable dans la fonction appelée, ce qui peut parfois obliger cette fonction
à réaliser des copies de travail en local.

4. Arithmétique des pointeurs

Opérations arithmétiques sur les pointeurs

Il est possible d'effectuer des opérations arithmétiques sur les pointeurs. Les seules
opérations valides sont les opérations externes (addition et soustraction des
entiers) et la soustraction de pointeurs. Elles sont définies comme suit (la
soustraction d'un entier est considérée comme l'addition d'un entier négatif) :
 p + i = adresse contenue dans p + i*taille (élément pointé par p)
 p1 - p2 = adresse contenue dans p1 - adresse contenue dans p2
Si p est un pointeur d'entier, p+1 est donc le pointeur sur l'entier qui suit
immédiatement celui pointé par p. On retiendra surtout que l'entier qu'on
additionne au pointeur est multiplié par la taille de l'élément pointé pour obtenir la
nouvelle adresse.

5. Pointeurs et tableaux

Tableau et pointeur
 Le tableau est étroitement lié au pointeur parce que l'accès aux éléments du
tableau se fait par manipulation de son adresse de base, de la taille et de
l'indice de ses éléments.
 L'adresse du n-ième élément d'un tableau est calculée avec la formule:
Adresse_n = Adresse_Base + n*taille (élément) où taille(élément)
représente la taille de chaque élément du tableau et Adresse_Base
l'adresse de base du tableau.
 L'adresse de base est l'adresse du début du tableau, c'est à la fois l'adresse

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

54
 Structures de données dynamiques

du tableau et l'adresse de son premier élément. Ce lien apparaît au niveau

du langage dans les conversions implicites de tableau en pointeur, et dans le
passage de tableau en paramètre des fonctions.

Conversions de tableau en pointeur

Afin de pouvoir utiliser l'arithmétique des pointeurs pour manipuler les éléments
des tableaux, on effectue les conversions implicites suivantes lorsque nécessaire :
 tableau vers pointeur d'élément;
 pointeur d'élément vers tableau.
Cela permet de considérer les expressions suivantes comme équivalentes:
identificateur[n] et *(identificateur + n) si identificateur est soit un
identificateur de tableau, soit celui d'un pointeur.

Exemple : Accès aux éléments d'un tableau par pointeurs

Tableau[1,...,100] d'Entier tab;
Entier *pi<==tab;
tab[3]<==5; /* Le 3ème élément est initialisé à 5 */
*(tab+2)<==4; /* Le 2ème élément est initialisé à 4 */
pi[5]=1; /* Le 5ème élément est initialisé à 1 */

Remarque : Attention !
 On prendra garde à certaines subtilités. Les conversions implicites sont une
facilité introduite par le compilateur, mais en réalité, les tableaux ne sont
pas des pointeurs, ce sont des variables comme les autres, à ceci près : leur
type est convertible en pointeur sur le type de leurs éléments. Il en résulte
parfois quelques ambiguïtés lorsqu'on manipule les adresses des tableaux.
 En particulier, on a l'égalité suivante : &tableau == tableauen raison du
fait que l'adresse du tableau est la même que celle de son premier élément.
Il faut bien comprendre que dans cette expression, une conversion a lieu.
Cette égalité n'est donc pas exacte en théorie. En effet, si c'était le cas, on
pourrait écrire : *&tableau == *tableau. Mais puisque les opérateurs * et
& sont conjugués cela impliquerait: tableau == t[0] ce qui est faux (le
type du premier élément n'est en général pas convertible en type pointeur.).

Paramètres de fonction de type tableau

 La conséquence la plus importante de la conversion tableau vers pointeur se
trouve dans le passage par adresse des tableaux dans une fonction. Lors du
passage d'un tableau en paramètre d'une fonction, la conversion implicite a
lieu, les tableaux sont donc toujours passés par adresse, jamais par valeur.
Il est donc faux d'utiliser des pointeurs pour les passer en paramètre, car le
paramètre aurait le type pointeur de tableau. On ne modifierait pas le
tableau, mais bel et bien le pointeur du tableau. Le programme aurait donc
de fortes chances de boguer.
 Il est autorisé de ne pas spécifier la taille de la dernière dimension des
paramètres de type tableau dans les déclarations et les définitions de
fonctions. En effet, la borne supérieure des tableaux n'a pas besoin d'être
précisée pour manipuler leurs éléments (on peut malgré tout la donner si
cela semble nécessaire). Cependant, pour les dimensions deux et suivantes,
les tailles des premières dimensions restent nécessaires. Si elles n'étaient
pas données explicitement, le compilateur ne pourrait pas connaître le
rapport des dimensions. Par exemple, la syntaxe: Tableau[][] d'Entier

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

55
 Structures de données dynamiques

tab; utilisée pour référencer un tableau de 12 entiers ne permettrait pas de

faire la différence entre les tableaux de deux lignes et de six colonnes et les
tableaux de trois lignes et de quatre colonnes (et leurs transposés
respectifs). Une référence telle que : tab[2][4]ne représenterait alors rien.
Dans le premier cas l'élément référencé serait le quatrième élément de la
deuxième ligne (de six éléments), i.e. le dixième élément, et dans le second
cas le quatrième élément de la deuxième ligne (de quatre éléments) i.e. le
huitième élément du tableau. En précisant tous les indices sauf un, il est
possible de connaître la taille du tableau pour cet indice à partir de la taille
globale du tableau, en la divisant par les tailles sur les autres dimensions (2
= 12/6 ou 3 = 12/4 par exemple).

6. Les chaînes de caractères

Chaînes de caractères en C
Les chaînes sont en réalité des tableaux de caractères dont le dernier caractère est
le caractère nul. Cela a plusieurs conséquences :
 La première, c'est que les chaînes de caractères sont aussi des pointeurs sur
des caractères, ce qui se traduit dans la syntaxe de la déclaration d'une
chaîne de caractères constante : constante caractere *identificateur =
"chaîne"; où identificateur est déclaré ici comme étant un pointeur de
caractère, puis il est initialisé avec l'adresse de la chaîne de caractères
constante "chaîne" ;
 La deuxième est le fait qu'on ne peut pas faire, des affectations de chaînes
de caractères, ni des comparaisons. Par exemple, si “nom1” et “nom2” sont
des chaînes de caractères, l'opération: nom1<==nom2; n'est pas
l'affectation du contenu de nom2 à nom1. C'est une affectation de pointeur:
le pointeur nom1 est égal au pointeur nom2 et pointent sur la même chaîne!
Une modification de la chaîne pointée par nom1 entraîne donc la
modification de la chaîne pointée par nom2... De même, le test nom1=nom2
est un test entre pointeurs, pas entre chaînes de caractères. Même si deux
chaînes sont égales, le test sera faux si elles ne sont pas au même
emplacement mémoire.

B. Notions élémentaires sur les pointeurs en C

C. Allocation dynamique de mémoire en C

D. Fichiers en C

Ouattara Jean Serge Dimitri / ouattaradimitri@[Link]

56