Polycopié de Programmation

Structurée IMA3
 Version 2012/2013 

Polytech'Lille, Villeneuve d'Ascq

Laure Gonnord
 Premature optimization is the root of all evil (or
at least most of it) in programming.

Donald Knuth, Décembre 1974, Conférence du

Prix Turing 1974, Communications of the ACM.

An d'améliorer ce poly n'hésitez pas à me

soumettre toute critique, suggestion, remarque
ou correction, dans mon casier ou, électroni-
quement, à l'adresse

[Link]@[Link]
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Table des matières

1 Motivations et premiers pas en C 4

2 Algorithmique/programmation C de base 10
2.1 Concepts de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Programmes en C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Fonctions/Actions 29
3.1 Actions/fonctions : notions de base . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Notions de complexité et de correction . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Actions/fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 Vecteurs/Tableaux 44
5 Algorithmique du Tri 54
6 Variables modiables en C : les pointeurs 61
6.1 Notions de base sur les pointeurs . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 Pointeurs et tableaux et chaînes de caractères . . . . . . . . . . . . . . . . . . . 74

3/85
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Chapitre 1
Motivations et premiers pas en C
Dans ce cours nous abordons le concept de système informatique et nous motivons l'appren-
tissage de l'algorithmique et de la programmation.
Un premier programme C est étudié. Une démo illustre l'édition du programme, sa compilation,
son exécution.

Savoir répondre aux questions

 Qu'est-ce qu'un système informatique ?
 Qu'est-ce qu'un chier source ?
 Que fait la compilation ?
 Comment compiler avec clang le chier toto.c ?

Remarque 1 Attention, en 2012/2013 nous utilisons un nouveau compilateur, appelé clang.

Les années précédentes le compilateur était gcc.

4/85
 Plan

Algorithmique et Programmation, IMA

Cours 1 : Introduction et Hello World

Laure Gonnord 1 Introduction

[Link] Pourquoi ?
[Link]@[Link]

Université Lille 1 - Polytech Lille

2 Premier programme en C

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  2 / 13 

Introduction Introduction Pourquoi ?

Systèmes informatiques

1 Introduction Un système informatique :

Pourquoi ?
est conçu pour automatiser le traitement d’une tâche
est divisé en matériel (stockage, periphériques, unité
2 Premier programme en C
centrale, . . . ) et logiciel.
logiciels/applications : gestion, jeux, bureautique,
traitement de données, . . .
un système d’exploitation fait le lien et gère les ressources

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  3 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  4 / 13 
 Introduction Pourquoi ? Introduction Pourquoi ?

Systèmes informatiques Développement logiciel

Différents types :
Création, développement de logiciels suivant les besoins et les
temps réel (contraintes de temps) : contrôle d’une chaîne offres matérielles :
de production, ou le contrôle commande d’un avion.
Systèmes complexes
transactionnels : contrôles de bases de données, . . .
Gros logiciels
embarqués (pda), distribués (réservation de train), . . .

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  5 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  6 / 13 
Introduction Pourquoi ? Introduction Pourquoi ?

Programmation structurée Placement dans les enseignements IMA

Objectifs de l’enseignement :
Conception de bout en bout d’un logiciel : du cahier des
charges à l’implémentation et la documentation.
Analyse du problème initial et hiérarchisation des Cours prérequis des enseignements de : réseaux, systèmes,
priorités : notion de sous problème. programmation avancée, programmation objet, . . .
Réflexion sur la correction d’une solution et de son mais aussi analyse numérique, électronique, automatique !
implémentation : Preuve d’invariants.
Réflexions sur la pertinence des solutions et leur coût
d’exécution : Analyses de complexité.
Travail contraint en équipe et en temps : Réalisation de
projet.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  7 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  8 / 13 
 Premier programme en C Premier programme en C

Premier programme

# include < s t d i o . h>

1 Introduction
i n t main ( )
{
2 Premier programme en C p r i n t f ( " Bonjour t o u t l e monde ! \ n " ) ;
return 0;
}

Effet :
affiche Bonjour tout le monde!,
retourne le code 0 (tout s’est bien passé).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  9 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  10 / 13 
Premier programme en C Premier programme en C

Édition, compilation et exécution Édition, compilation et exécution

Lancement de l’éditeur en tâche de fond (&). Lancement de l’éditeur en tâche de fond (&).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13 
 Premier programme en C Premier programme en C

Édition, compilation et exécution Édition, compilation et exécution

On tape le texte du programme : édition. Il ne faut pas oublier de sauvegarder.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13 
Premier programme en C Premier programme en C

Édition, compilation et exécution Édition, compilation et exécution

Lancement de la compilation avec clang. Si le compilateur ne dit rien, tout s’est bien passé.
Un fichier [Link] “binaire” a été créé.
Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13 
 Premier programme en C Premier programme en C

Édition, compilation et exécution Édition, compilation et exécution

Lancement de l’exécutable. Le programme s’exécute et rend la main.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  11 / 13 
Premier programme en C Premier programme en C

Binaire généré Ligne de compilation à connaître

fixer le nom du binaire (output)

Le fichier [Link] généré est un fichier binaire (compréhensible
nom du fichier source
par l’ordinateur. On peut donner n’importe quel nom à ce
binaire : clang hello.c -o hello et ensuite l’exécuter clang −o nomdubinaire −Wall nomfichier.c

avec :./hello
nom du compilateur option Wall (tiret devant!)
I clang est un compilateur. On peut aussi utiliser gcc (plus
courant) ou encore (l’ordre est indifférent) :
clang -Wall nomfichier.c -o nombinaire
clang nomfichier.c -o nombinaire -Wall
clang peut être remplacé par gcc (autre compilateur).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  12 / 13  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 1 : Introduction et Hello World 2012  13 / 13 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Chapitre 2
Algorithmique/programmation C de base

2.1 Concepts de base

Dans ce cours nous abordons les concepts fondamentaux en algorithmique que sont la notion
de constante, de variable, de type, d'expression, de boucle. Un pseudo-code sera utilisé pour
décrire les programmes. L'équivalent en langage C est aussi donné.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Qu'est-ce qu'une variable ?
 Qu'est-ce que le type d'une variable ? Connaître les types de base.
 Qu'est-ce qu'une constante ? Savoir déclarer une constante symbolique en C.
 Donner un exemple d'expression numérique / d'expression booléenne.
 Qu'est-ce qu'une aectation ?
 Soit l'instruction x ← 42 + 23;. Expliquer ce que fait le programme lorsqu'il rencontre
cette instruction.
 Connaître les tests, la boucle pour, la boucle while (ce que ça fait, et la syntaxe).

10/85
 Plan

Algorithmique et Programmation, IMA

1 Notations, identificateurs
Cours 2 : C Premier Niveau / Algorithmique
2 Variables et Types de base
Laure Gonnord
[Link] 3 Expressions
[Link]@[Link]
4 Constantes
Université Lille 1 - Polytech Lille

5 Instructions
Instruction simple, instruction composée
Structures de contrôle
Itérations

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  2 / 40 

Notations, identificateurs Notations, identificateurs

Notations

1 Notations, identificateurs

2 Variables et Types de base Notations algorithmiques :

Faire
action
3 Expressions
Tantque condition ;
4 Constantes
Exemples en C :
char c ;
5 Instructions

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  3 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  4 / 40 
 Notations, identificateurs Variables et Types de base

Identificateurs

1 Notations, identificateurs

Mot désignant des variables, fonctions, types. 2 Variables et Types de base

Suite de charactères, chiffres et ’_’ (underscore) ;
Commence par une lettre 3 Expressions
Distinction majuscule/minuscule
Convention : les variables sont en minuscule. 4 Constantes

t o t o , a23_plouf , a89zZ_10 5 Instructions

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  5 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  6 / 40 
Variables et Types de base Variables et Types de base

Les variables et les types, pourquoi ? Variables

On veut stocker des informations qui ont un nom : Une variable est une place en mémoire qui a un nom
un entier x pour pouvoir exprimer la fonction x 7→ x + 1 (convention : en minuscules) :

une chaîne de caractères s qui contient le prénom de Une variable a un type qui définit quelles opérations sont
l’utilisateur valides (entier, booléen, réel, caractère, . . . )
x, s peuvent prendre des valeurs différentes dans un Elle doit être déclarée AVANT d’être utilisée.
programme donné, ce seront donc des variables. Une déclaration de variable est la donnée d’un type et d’un
De plus, on veut qu’il soit interdit de stocker autre chose qu’un nom (identificateur).
entier pour x, autre chose qu’une chaîne pour s, on va donc I Important ! Déclarer une variable d’un certain type interdit de
leur donner un type. l’utiliser pour stocker des informations d’un autre type !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  7 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  8 / 40 
 Variables et Types de base Variables et Types de base

Type entier Type booléen

Caractéristiques : Caractéristiques :
Codé sur 2 (ou 4 octets, ou 8) : range = [−215 , 215 − 1] N’existe pas en C : int,
sizeof(int) rend 2 ou 4 ou 8 Représentation : deux valeurs entières, 0 pour faux, 1 pour
vrai (en fait toute valeur différente de 0) : stdbool
Opérateurs : +, *, /, %(reste modulo), << (shift)
Opérateurs et (&&), ou (||) : paresseux de gauche à droite
Comparaison : !=, ==, <=
Déclaration pseudo-code
Déclaration pseudo-code
b : Booléen
x : Entier
Déclaration en C
Déclaration en C
# include < s t d b o o l . h>
int x ; // declaration simple
bool a ;
i n t z =10; / / declaration avec v a l e u r initiale
b o o l b= f a l s e ; / / a v e c i n i t i a l i s a t i o n

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  9 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  10 / 40 
Variables et Types de base Variables et Types de base

Type réel Type caractère - 1/2

Caractéristiques : Caractéristiques :
Float 4 octets et double 8. 1 octet : 256 valeurs de l’ASCII étendu
Notation décimale ou exponentielle (12.3, -.38, .5e-11) Notation 'a'
Opérateurs : mêmes que int sauf %. / est la division réelle. Caractères spéciaux \n saut de ligne, \t tabulation, . . .

Déclaration pseudo-code Déclaration pseudo-code

r : Réel c : Caractère

Déclaration en C Déclaration en C
float x ; / / declaration simple char c ; // declaration simple
f l o a t r =0.34; / / d e c l a r a t i o n avec v a l e u r initiale char c= ’ a ’ ; // declaration avec v a l e u r initiale

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  11 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  12 / 40 
 Variables et Types de base Variables et Types de base

Type caractère - 2/2 Autres types

En C : un caractère est un entier (les valeurs de l’ascii), donc :

int i = ’a ’ ; / / fonctionne aussi !
c = 80; / / a s c i i c o d e 80 == P Les types chaînes de caractères, tableaux, et les types
char d ; composés seront vus plus tard.
d= c +1; // d vaut ? Q!

I Le savoir, mais en général, éviter l’utilisation de la conversion

implicite !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  13 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  14 / 40 
Expressions Expressions

Expressions, pourquoi ?

1 Notations, identificateurs

2 Variables et Types de base On veut pouvoir effectuer des opérations avec les variables
d’un programme, par exemple :
3 Expressions Sommer des variables entières
Tester si une variable entière est plus petite qu’une autre
4 Constantes I Les opérations numériques seront des expressions
numériques, les opérations de tests seront des expressions
5 Instructions booléennes.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  15 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  16 / 40 
 Expressions Expressions

Expression numérique, expression booléenne Syntaxe générale des expressions en C

Expression numérique (C/pseudo-code) :

1+x+y+41 Une expression C peut être (entre autres) :

un identificateur : toto
Expression booléenne en pseudo-code : une constante : 42
(x<7 et y=2) ou b une chaîne littérale : ’ ’ hop’’
une expression numérique
Expression booléenne en C : une expression booléenne
( x<7 && y ==2) | | b une expression-affectation (à venir)
I Une expression est constituée d’opérateurs, de en C, l’affectation est une expression !
sous-expressions, de sous-expressions de base (variable ou
constante).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  17 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  18 / 40 
Expressions Expressions

Expression-affectation, pourquoi ? Expression-affectation

En C : En pseudo-code :
x = 7 x←7
t [ 2 ] = 23 t[2] ← 23

On veut stocker des valeurs numériques dans des variables À gauche de l’affectation : une expression qui doit délivrer une
entières, des valeurs booléennes dans des variables variable (par opp. à constante) : une variable simple, ou un
booléennes, . . . . élément de tableau.
I Cette opération est appelée affectation. Sémantique :
Effet de bord : la valeur de droite est calculée et affectée à
la variable de gauche.
(en C) La valeur de l’expression entière est cette valeur
calculée : x = (y=8) +1 est une expression dont la valeur
vaut .....

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  19 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  20 / 40 
 Constantes Constantes

Qu’est-ce qu’une constante ?

1 Notations, identificateurs

2 Variables et Types de base

Une constante est une valeur qui ne change pas tout au long
d’un programme.
3 Expressions
Cas d’utilisation : écrire du code paramétrique :
4 Constantes Nombre d’itérations d’un algo ;
Tailles de tableaux...
5 Instructions

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  21 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  22 / 40 
Constantes Constantes

Définition de constantes symboliques Danger des constantes symboliques

En pseudo-code :
Définition de constante symbolique 6= affectation de variable !
Entier X : Constante(2) affectation : évaluation,
constante symbolique : substitution littérale.
En C :
⇒ danger de “capture” syntaxique.
# define CST v a l e u r
Exemple d’erreur :
CST : identificateur, par convention en majuscules, # define N x+y
valeur : texte arbitraire, z = 3∗N ; / ∗ s i g n i f i e z = 3 ∗ x + y , p a s z = 3 ∗ ( x + y ) ∗ /
/∗ x et y peuvent aussi etre symboliques ! ∗/
doit occuper une ligne complète,
pas de point-virgule ; final. Solution :

Effet : dans la suite du programme, CST est remplacé par # define N ( ( x ) + ( y ) ) /∗ plus su ^ r ∗/

valeur (preprocessing C)

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  23 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  24 / 40 
 Instructions Instructions

Notion d’instruction
1 Notations, identificateurs

2 Variables et Types de base Une instruction est une ligne de pseudo-code/C qui effectue
un calcul, qui a un effet sur les variables du programme, . . .
3 Expressions Dans la suite, nous allons voir différentes formes
d’instructions :
4 Constantes les instructions simples
les instructions composées
5 Instructions
les instructions conditionnelles
Instruction simple, instruction composée
Structures de contrôle les instructions itération.
Itérations

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  25 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  26 / 40 
Instructions Instruction simple, instruction composée Instructions Instruction simple, instruction composée

Instruction simple en pseudo-code / en C Instruction composée ou bloc - en C

Un bloc (C uniquement) (entre accolades !) permet
Instruction simple en C : expression suivie d’un ; (point-virgule) de grouper l’ensemble d’instructions en lui donnant la
x=4 ; // affectation forme syntaxique d’une seule instruction (voir le IF)
z=42+x ;
de déclarer des variables accessibles uniquement à
p r i n t f ( " Hello ! " ) ; / / impression
s c a n f(%d ,& x ) ; / / demande d ’ un entier
l’intérieur du bloc.
toto (x ) ; // appel de procedure , ( cours 3)
w= f ( z , x ) ; // appel de f o n c t i o n ( cours 3) {
int x ; / / declaration
Attention 2+4; est donc bien une instruction simple ! x=4 ;
z=42+x ;
En pseudo-code c’est pareil :
}
x ← 7; {
t[2] ← f(z,x) ; x =2; / / e r r e u r , x n o n d e c l a r e d a n s l e b l o c
}

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  27 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  28 / 40 
 Instructions Structures de contrôle Instructions Structures de contrôle

Conditionnelle - 1 Conditionnelle - 2

Le test/la conditionnelle en pseudo code :

En C cela donne :
Si condition alors
action_alors i f ( 2 x+5<=b ) p r i n t f ( ‘ ‘ b l a b l a ’ ’ ) ;
Fsi
i f ( a>b ) max=a ; else max=b ;
Si condition alors
i f ( a>b ) i f c<d u=v ; else i = j ;
action_alors
// le else est associe au if le plus proche
Sinon
action_sinon if (a) // teste si a !=0
Fsi {
... // groupement d ’ instructions ( bloc )
condition est une expression booléenne. Si son évaluation }
donne "true" alors la première action est exécutée, sinon c’est
la deuxième.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  29 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  30 / 40 
Instructions Structures de contrôle Instructions Structures de contrôle

Conditionnelle - 3 Exercices

Important ! : l’instruction Écrire les suites d’instructions pour

i f ( x ==4) t =3; Afficher le maximum de deux entiers x et y
est différente de : Afficher la valeur absolue de l’entier z
i f ( x =4) t =3; Afficher pair ou impair selon la parité de l’entier x.
Afficher le maximum de 3 entiers
Cette dernière est fortement déconseillée !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  31 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  32 / 40 
 Instructions Itérations Instructions Itérations

Instruction d’itération : POUR - 1 (version simple) Instruction d’itération : POUR - 2

Affectation
i ← inf
Utilisation classique avec compteur
Pour i de inf à sup Faire non
corps i ≤ sup ?

Fpour
i ← i + inc
(augmentation implicite de 1 à chaque tour). oui

En C cela donne : corps de la boucle

f o r ( i = i n f ; i <=sup ; i = i + i n c )
corps
sortie
À utiliser en priorité lorsqu’on connaît le nombre d’itérations

I La boucle “pour” est en fait plus générale/complexe en C.

Nous verrons quelques utilisations en TP.
Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  33 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  34 / 40 
Instructions Itérations Instructions Itérations

Exercices Boucle POUR Instruction d’itération : TANTQUE - 1

La boucle tant que en pseudo code :

Écrire les suites d’instructions pour Tq condition faire
Afficher les entiers de 1 à 10 séparés par des espaces. action
Ftq
Afficher les entiers de 10 à 1 séparés par des espaces.
Ajouter les entiers de 1 à 100, puis afficher le résultat. En C cela donne :
Ajouter les entiers pairs de 6 à 2048, puis afficher le while ( x >0) x=x −1;
résultat.
Afficher la liste des multiples de 3 et des multiples de 5 while ( x >0) {
(dans l’ordre croissant) inférieurs à 60 ; puis un point. x=x −1;
z=z+x ;
}

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  35 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  36 / 40 
 Instructions Itérations Instructions Itérations

Instruction d’itération : TANTQUE - 2 Déroulement d’une boucle Tant que

En C :
eval expr
while ( e x p r e s s i o n )
{
instructions non
expr ?
}
Sémantique (effet) I Tant que l’expression est vraie, le bloc
eval expr
est exécuté. oui
Si la condition est initialement fausse, le bloc n’est jamais
exécuté. corps de la boucle

La condition est retestée après chaque tour de boucle.

Les parenthèses autour de la condition sont obligatoires.
sortie
Si une seule instruction : { et } facultatifs.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  37 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  38 / 40 
Instructions Itérations Instructions Itérations

Instruction d’itération TANTQUE - exemple C Instruction d’itération : DO WHILE

Longueur d’une ligne : Faire

action
l =0; c= g e t c h a r ( ) ; Tantque condition ;
while ( c ! = ’ \ n ’ )
{ En C cela donne :
l = l +1; / / a u g m e n t a t i o n du c o m p t e u r
do
c= g e t c h a r ( ) / / o n a v a n c e !
c = getchar ( ) ;
}
while ( c ! = ’ \ n ’ ) ;

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  39 / 40  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 : Algo et C de base 2012  40 / 40 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

2.2 Programmes en C

Dans ce cours est exposée la syntaxe de programmes C simples. Un programme C ayant

une syntaxe particulière, tous les chiers texte ne sont pas acceptés lors de la compilation,
nous verrons quels messages d'erreur nous obtenons alors. Nous verrons aussi comment un
programme C peut interagir avec son environnement (entrées/sorties au terminal). Le cours se
termine par des exercices simples.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Syntaxe d'un programme C simple.
 Usage et syntaxe de printf et scanf.
 Qu'est-ce une erreur de compilation ? Comment avoir le plus de messages d'erreurs de
compilation possible ?

21/85
 Plan

Algorithmique et Programmation, IMA

Cours 2b : C/Algo : Programmes 1 Structure générale d’un programme

Laure Gonnord 2 Exemple

[Link]
[Link]@[Link] 3 Printf et Scanf
Université Lille 1 - Polytech Lille
4 Les erreurs de compilation

5 Exercices

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  2 / 21 

Structure générale d’un programme Structure générale d’un programme

Syntaxe générale d’un programme

Un programme comprend :
1 Structure générale d’un programme Une liste de déclarations (de variables globales, de types,
de structures, . . . ) : optionnelle ;
2 Exemple Une liste de définitions de fonctions (cf cours 3) :
optionnelle aussi ;
3 Printf et Scanf Une fonction main, unique et obligatoire, qui est le point
d’entrée du programme
4 Les erreurs de compilation
En pseudo-code
...
5 Exercices Fonction main()
Imprimer(“bonjour”)
...
Retourner 0
FFonction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  3 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  4 / 21 
 Structure générale d’un programme Structure générale d’un programme

Syntaxe générale d’un programme - C Syntaxe générale du main - C

# include < s t d i o . h> / / liste de defs de fonctions ( lib )

Le main est un cas particulier de fonction (on verra plus tard).
// autres defs de fonctions ( internes )
i n t main ( )
... {
// declarations
// instructions
i n t main ( ) return 0;
{ }
p r i n t f ( " Hello world ! \ n " ) ;
return 0; / / c o n v e n t i o n o b l i g a t o i r e d a n s ce c o u r s
}

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  5 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  6 / 21 
Exemple Exemple

Exemple : Anatomie de bonjour.c

# include < s t d i o . h>
1 Structure générale d’un programme
i n t main ( )
2 Exemple {
p r i n t f ( " Bonjour t o u t l e monde ! \ n " ) ;
return 0 ;
3 Printf et Scanf }

4 Les erreurs de compilation

Tout programme C doit contenir une fonction appelée main.
5 Exercices L’exécution commence au début de main.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  7 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  8 / 21 
 Exemple Exemple

Exemple : Anatomie de bonjour.c Exemple : Anatomie de bonjour.c

# include < s t d i o . h> # i n c l u d e < s t d i o . h>

i n t main ( ) i n t main ( )
{ {
p r i n t f ( " Bonjour t o u t l e monde ! \ n " ) ; p r i n t f ( " Bonjour t o u t l e monde ! \ n " ) ;
return 0; return 0 ;
} }

Par convention, la fonction main renvoie un code de retour : La fonction printf permet d’écrire sur l’écran.
il est de type int (entier), elle fait partie de la bibliothèque C standard,
la convention est de retourner 0 si tout se passe bien, elle doit être importée depuis l’en-tête stdio.h.
les parenthèses de return sont facultatives,
le code de retour est exploitable depuis le shell.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  8 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  8 / 21 
Exemple Printf et Scanf

Exemple : Anatomie de bonjour.c

# include < s t d i o . h>
1 Structure générale d’un programme
i n t main ( )
{ 2 Exemple
p r i n t f ( " Bonjour t o u t l e monde ! \ n " ) ;
return ( 0 ) ;
}
3 Printf et Scanf

4 Les erreurs de compilation

printf prend en argument une chaîne de caractères :
tapée entre guillemets ",
5 Exercices
\ sert à entrer des caractères spéciaux :
\n signifie “retour à la ligne”.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  8 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  9 / 21 
 Printf et Scanf Printf et Scanf

Lire une information au clavier : scanf Écrire quelque chose sur le terminal : printf

La procédure scanf est bien utile pour demander des

informations à l’utilisateur.

int x ; La procédure printf est bien utile pour imprimer des

p r i n t f ( ‘ ‘ donnez un e n t i e r svp ! \ n ’ ’ ) ; informations au clavier.
s c a n f ( ’ ’%d ’ ’ ,& x ) ; / / o n p a s s e u n e a d r e s s e ( v o i r + t a r d )
int x ;
Le premier argument de scanf est une chaîne de formattage : p r i n t f ( ‘ ‘ donnez un e n t i e r svp ! \ n ’ ’ ) ;
"%d" si on demande un entier, "%f" si on demande un s c a n f ( ’ ’%d %d ’ ’ ,&x ,& y ) ;
flottant,. . . p r i n t f ( ‘ ‘ maintenant x=%d e t y=%d " , x , y ) ;

int x , y ;
p r i n t f ( ‘ ‘ donnez deux e n t i e r s svp ! \ n ’ ’ ) ;
s c a n f ( ’ ’%d %d ’ ’ ,&x ,& y ) ;

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  10 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  11 / 21 
Les erreurs de compilation Les erreurs de compilation

Qu’est-ce que c’est ?

1 Structure générale d’un programme

2 Exemple
Lorsque le fichier source n’est pas correct, le compilateur
(clang, gcc) génère des erreurs de compilation.
3 Printf et Scanf
Remarque : les schémas d’erreurs sont différents selon les
4 Les erreurs de compilation compilateurs. Certains compilateurs récents (clang) ont des
messages plus explicites.
5 Exercices

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  12 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  13 / 21 
 Les erreurs de compilation Les erreurs de compilation

Exemple d’erreur Exemple d’avertissement

1 i n t main ( )
1 # include < s t d i o . h>
2 {
2
3 p r i n t f ( " Bonjour t o u t l e monde ! \ n " ) ;
3 i n t main ( )
4 return ( 0 ) ;
4 {
5 }
5 p r i n t f ( " Bonjour t o u t l e monde ! \ n " )
6 return ( 0 ) ; Compilation : clang hello.c -o bonjour
7 }
hello.c:3:3: warning: implicitly declaring library function 'printf'
Compilation : clang hello.c -Wall -o bonjour with type 'int (const char *, ...)'
printf("Hello world!\n");
^
hello.c:5:27: error: expected ';' after expression hello.c:3:3: note: please include the header <stdio.h> or explicitly
printf("Hello world!\n") provide a declaration for 'printf'
^ 1 warning generated.

I Il manque un ;. Aucun binaire n’est généré. I Il manque un #include <stdio.h>. C’est un avertissement
non fatal.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  14 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  15 / 21 
Les erreurs de compilation Les erreurs de compilation

Les options -Wall et -Wextra Espacement

L’espacement et les sauts de lignes sont libres.

L’option -Wall attire l’attention, entres autres, sur :
# i n c l u d e < s t d i o . h>
les oublis d’imports #include, i n t main (
les ambiguïtés syntaxiques courantes, ){
les incohérences de types. printf
( " toto \n"
La norme est très laxiste ne considère pas ces points comme ) ; return ( 0 ) ;}
des erreurs !
Exceptions :
-Wextra ajoute des avertissements supplémentaires.
#include <stdio.h> doit être sur une seule ligne,
I Toujours compiler avec -Wall au moins. les sauts de ligne comptent dans les chaînes de
caractères.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  16 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  17 / 21 
 Les erreurs de compilation Exercices

Commentaires

Commentaires : tout ce qui est entre /* et */ est ignoré. 1 Structure générale d’un programme
# include < s t d i o . h> / ∗ p o u r a v o i r printf ∗/
2 Exemple
/∗ la fonction principale
∗/
3 Printf et Scanf
i n t main ( / ∗ r i e n i c i ∗ / )
{
p r i n t f ( " toto \n" ) ; 4 Les erreurs de compilation
r e t u r n ( 0 ) ; / ∗ OK ∗ /
} 5 Exercices

Conseils : - indentez votre code (TAB sous Emacs),

- commentez votre code.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  18 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  19 / 21 
Exercices Exercices

Exercice : programme et boucle while Exercice : Programme

Écrire un programme qui :

Écrire un programme qui : lit 50 entiers rentrés au clavier ;
Lit (au clavier) une suite de caractères qui finit par # et qui calcule la somme de tous ces entiers en affichant la
affiche le nombre de caractères lus différents de # somme partielle à chaque nouveau nombre lu ;
Lit au clavier une suite de notes entre 0 et 20 et qui affiche à la fin la somme et la moyenne de ces entiers ;
s’arrête lorsque l’utilisateur tape -1, puis affiche la modifier le programme pour qu’il affiche la moyenne des
moyenne des notes. entiers strictements positifs
modifier ... entiers pairs
I On a besoin d’une fonction de sélection

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  20 / 21  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 2 b: Algo et C de base 2012  21 / 21 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

28/85
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Chapitre 3
Fonctions/Actions

3.1 Actions/fonctions : notions de base

Dans ce cours la notion-clef de fonction, utile au découpage d'un algorithme/programme,

est introduite. La distinction entre action, qui ne retourne pas de résultat, et fonction, qui re-
tourne un unique résultat, est eectuée. La déclaration d'une fonction/d'une action ; ainsi que
son utilisation (appel) sont illustrés dans les deux syntaxes introduites précédemment (pseudo-
code/C). La principale diculté du cours est la notion de paramètre, et les diérentes va-
riantes de passage de ces paramètres.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Quand utilise-t-on les fonctions et les actions ?
 Fonctions : usage, syntaxe de la dénition d'une fonction, de l'appel.
 Actions : idem.
 Quelle est la diérence entre fonction et action ?
 Paramètres données, résultats, données résultat.
 Quelle est la diérence entre valeur de retour et paramètre résultat ?
 Savoir écrire une fonction ou une action simple en pseudo-code en C.
 Savoir simuler à la main l'exécution d'une fonction ou d'une action.

Figure 3.1  [Link] sous License Creative Commons

29/85
 Plan

Algorithmique et Programmation, IMA

Cours 3 : Actions, Procédures
1 Conception Structurée Descendante

Laure Gonnord
[Link] 2 Les Fonctions
[Link]@[Link]

Université Lille 1 - Polytech Lille 3 Les Actions / les Procédures

4 Résumé

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  2 / 24 

Conception Structurée Descendante Conception Structurée Descendante

Conception Structurée descendante - 1

1 Conception Structurée Descendante

Découper l’algorithme (action) en sous-algorithmes
2 Les Fonctions (sous-actions) plus simples, jusqu’à des opérations
considérées primitives. Buts :
3 Les Actions / les Procédures Simplification
Abstraction (ignorer les détails)
4 Résumé
Structuration
Réutilisation

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  3 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  4 / 24 
 Conception Structurée Descendante Les Fonctions

Conception Structurée descendante - 2

1 Conception Structurée Descendante

Exemple : sélectionner les entiers selon un certain critère 2 Les Fonctions

une fonction de sélection qui dit "oui" ou "non" et qui peut
être plus ou moins compliquée ; 3 Les Actions / les Procédures
un appel dans le "main".
4 Résumé
Outil : actions et fonctions paramétrées.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  5 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  6 / 24 
Les Fonctions Les Fonctions

Fonctions - Définition Fonctions - Appel de fonction

Une fonction est un sous-programme qui à partir de données Un appel de fonction est une expression du type de retour de
produit un (et un SEUL) résultat. la fonction.
Syntaxe Algo (exemple) Exemple :
Fonction max(a,b) : entier x ← max(3,43)
D: a,b : entiers {Données}
L: m : entier {Variable locale} Que se passe-t-il lors de l’appel ?
Si a<b alors Les données sont remplacées par des valeurs (ou des
m←b expressions)
Sinon
m←a Le code de la fonction est exécuté jusqu’au premier return.
Fsi Le résultat retourné par la fonction est la valeur de
Retourner m {Obligatoire} l’expression du return.
FFonction Ce résultat (valeur) est récupéré dans la variable x ici.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  7 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  8 / 24 
 Les Fonctions Les Fonctions

Fonctions en C - Syntaxe Fonctions en C - Exemple

Définition Définition d’une fonction

i n t max ( i n t a , i n t b )
type_de_retour nom_fonction(liste-params) {
{
liste-declarations (optionnelle) i n t m;
liste_instructions i f ( a>b ) m=a ; else m=b ;
}
r e t u r n (m) ;
La liste d’instructions comprend au moins une instruction }
return (du type type_de_retour).
attention au type de retour !
Appel
Appel
nom_fonction(liste-expressions) t o t o = max ( 3 , 4 5 ) ; / / i n t declare avant !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  9 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  10 / 24 
Les Fonctions Les Fonctions

Fonctions en C - Exercices Fonctions en C - Erreurs courantes

Oubli du ; dans le if :
toto.c:9:17: error: expected ';' after expression
if ( a>b ) m=a else m=b ;
Bons entiers ^
Modifier le programme de sélection des entiers inférieurs à Oubli du return :
100 pour utiliser la fonction d’entête : toto.c:11:1: warning: control reaches end of non-void
bool b o n _ e n t i e r ( i n t n ) function [-Wreturn-type]
}
Écrire la fonction bon_entier de façon à sélectionner les ^
entiers multiples de 3. appel avec des arguments du mauvais type : par exemple
max("tsoin",4) :
toto.c:42:18: warning: incompatible pointer to integer conversion passing
'char [6]' to parameter of type 'int' [-Wint-conversion]
int toto = max("tsoin",4);
^~~~~~~
toto.c:6:15: note: passing argument to parameter 'a' here
int max ( int a , int b )

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  11 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  12 / 24 
 Les Actions / les Procédures Les Actions / les Procédures

Les actions - définition

Une action ne retourne pas de résultat.

1 Conception Structurée Descendante
Action maxproc(a,b,maxi)
D: a,b : entiers {Données}
2 Les Fonctions
R: maxi : entier {Résultat}
Si a<b alors
3 Les Actions / les Procédures maxi ← b
Sinon
4 Résumé maxi ← a
Fsi
FAction
Les variables résultats servent à propager les informations
produites à l’extérieur de la définition.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  13 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  14 / 24 
Les Actions / les Procédures Les Actions / les Procédures

Les actions - Utilisation (1) Les actions - Utilisation (2)

Exemple
L’appel d’une action est une instruction. Les paramètres resu : entier ;
formels sont TOUS remplacés par des paramètres effectifs de maxproc(3,43,resu);
même type
I Après l’appel, la variable resu contient le max des deux
Une donnée par une valeur (ou une expression qui a une entiers.
valeur)
Les actions/procédures sont surtout utiles pour :
Un résultat par une variable dans laquelle la procédure doit
ranger le résultat imprimer des valeurs, des structures, des messages . . .
Une Donnée/Résultat par une variable valuée. modifier des paramètres qui ne peuvent être retournés
(tableaux, paires, structures compliquées) : ceux-ci sont
alors appelés Données/Résultats ou entrées/sorties.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  15 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  16 / 24 
 Les Actions / les Procédures Les Actions / les Procédures

Les actions en C - procédures Procédures en C - Syntaxe

Définition
En C les actions/procédures sont des fonctions qui ne
void nom_action(liste-params) {
retournent rien (mot clef void).
liste-declarations (optionnelle)
void p r i n t m a x p r o c ( i n t a , i n t b ) liste_instructions
{ / / i m p r e s s i o n d u max }
i n t maxi ;
i f ( a<b ) maxi=b ; else maxi=a ;
p r i n t f ( " Le max e s t %d \ n " , maxi ) ; Appel
}
nom_action(liste-expressions)
Paramètres R ? voir le chapitre « pointeurs »
I on ne récupère pas le résultat d’une procédure, il n’y en a
PAS.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  17 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  18 / 24 
Les Actions / les Procédures Résumé

Procédures en C - Exemples

1 Conception Structurée Descendante

Écrire les procédures suivantes :
2 Les Fonctions
Impression du maximum de 3 entiers en paramètres
Impression des 100 premiers termes de la suite suivante :
u0 = 32
3 Les Actions / les Procédures
un = 3 ∗ un−1 + 19
Impression des k premiers termes de la suite, avec k 4 Résumé
passé en paramètre.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  19 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  20 / 24 
 Résumé Résumé

Les fonctions Les actions

Une fonction retourne un et un seul résultat. Une action ne retourne pas de résultat.
Fonction ajoute_un(a) : Entier
D: a : Entier Action imprime_succ(a)
D: a : Entier
Retourner a+1
Imprime(a+1)
FFonction
FAction
Appel :
Appel :
Programme Main
Programme Main
L: x,y :Entiers
L: x :Entier
x ← 12
x ← 12
y ← ajoute_un(x)
imprime_succ(x)
Imprimer(y)
Retourner 0
Retourner 0
FProgramme
FProgramme

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  21 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  22 / 24 
Résumé Résumé

Et si ? Et si ?
I Et si je veux “retourner” deux résultats ?
I Et si je veux modifier un paramètre d’entrée ? Action quotient_et_reste(a,b,q,r)
Action inc(a) D: a,b : Entiers
D/R: a : Entier R: q,r : Entiers
a ← a+1 .....
FAction (calcul de q et r)
FAction
Programme Main
L: x :Entier Programme Main
x ← 12 L: x,y,vq,vr :Entiers
inc(x) x ← 37
Imprime(x) y←7
Retourner 0 quotient_et_reste(x,y,vq,vr)
FProgramme Imprime(vq,vr)
Retourner 0
FProgramme

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  23 / 24  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3 Actions Procédures 2012  24 / 24 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

3.2 Notions de complexité et de correction

Pour évaluer la performance d'un programme, ou de la solution à un problème, on utilise

la notion de complexité d'un programme, qui est une fonction des variables d'entrée et des
constantes du programme ou de la fonction/action considérée. Dans ce mini-cours, nous abor-
dons également une notion-clef pour prouver qu'un programme fait bien ce que l'on veut : la
notion d' invariant de boucle.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Dénition des complexités en temps et en mémoire.
 Calcul de cette complexité sur des programmes simples, asymptotiquement.
 Dénition de complexité linéaire, quadratique, exponentielle, . . .
 Qu'est-ce qu'un invariant ? Donner un invariant pour une boucle donnée d'un programme
simple.

36/85
 Complexité Algorithmique

Algorithmique et Programmation, IMA

Cours 3b : Notions de complexité algorithmique et de
correction de programme
1 Complexité Algorithmique
Laure Gonnord
[Link] 2 Correction
[Link]@[Link]

Université Lille 1 - Polytech Lille

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  2 / 12 

Complexité Algorithmique Complexité Algorithmique

Pourquoi la complexité ? Définition

La complexité d’un programme est une fonction de ses

variables d’entrée :
On désire :
valeurs demandées à l’utilisateur, données par des
estimer à l’avance la performance en temps/mémoire d’un
capteurs, . . .
programme donné ;
constantes (taille des tableaux par exemple)
estimer les limites d’utilisation d’un programme.
Elle mesure :
I On va évaluer le nombre d’opérations de base, d’itérations,
de cases mémoires, . . . le nombre d’opérations,
ou d’itérations (complexité en temps),
ou de cases mémoire (complexité mémoire) ;

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  3 / 12  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  4 / 12 
 Complexité Algorithmique Complexité Algorithmique

Définition - 2 Exemple 1

Action maxproc(a,b,maxi)
D: a,b : entiers
La complexité se calcule :
R: maxi : entier
en moyenne sur toutes les exécutions possibles du Si a<b alors
programme, maxi ← b
au mieux (le minimum), Sinon
maxi ← a
au pire (le maximum).
Fsi
et s’exprime (en général), asymptotiquement, c’est-à-dire FAction
comme une limite pour de grandes valeurs des paramètres
d’entrées. I quels que soient a et b, on ne fait qu’un test. La complexité
en temps/nb ops/mémoire, en moyenne, au pire, au mieux, est
donc O(1).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  5 / 12  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  6 / 12 
Complexité Algorithmique Complexité Algorithmique

Exemple 2 Un peu de vocabulaire

Fonction toto(n)
D: n : entier
L: i,s : entiers
s← 0 Supposons que N soit un paramètre d’un programme/d’une
Si n>0 alors fonction. Si la complexité est :
Pour i de 0 à n Faire O(N ), on dit que le programme est linéaire (au pire, en
s←s+i moyenne, . . . )
Fpour O(N 2 ) : il est quadratique.
Fsi
O(polynome en N) : polynômial.
Retourner s
FFonction O(2N ) : exponentiel.
I La complexité est :
au mieux 1 (si n 6 0)
au pire n (dans tous les autres cas)

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  7 / 12  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  8 / 12 
 Correction Correction

Que veut-on garantir ?

1 Complexité Algorithmique
On aimerait garantir d’un programme/une fonction satisfait ses
spécifications, c’est-à-dire calcule le “bon résultat” quelles
2 Correction
que soient ses paramètres (paramètres d’entrée, variables
données par l’utilisateur, données de capteurs physiques, . . . ).
I On montre la correction du pseudo-code et/ou de
l’implémentation C à l’aide d’invariants !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  9 / 12  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  10 / 12 
Correction Correction

Un exemple simple Et encore

Calcul de xn par la méthode itérative “naïve” :

Fonction expo(x,n) : entier
D: x,n : entiers
L: i,exp : entiers
D’autres exemples (complexité et calcul d’invariants) tout au
exp ← 1
cours des cours et TDs.
Pour i de 1 à n Faire
exp ← exp ∗ x Remarque : on peut aussi vouloir prouver la terminaison d’un
Fpour programme donné.
Retourner exp
FFonction
I Invariant “au ième tour de boucle, exp contient xi ”. Prouvé
par récurrence sur i.
I Conclusion ?

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  11 / 12  Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours : Complexité Algorithmique 2012  12 / 12 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

3.3 Actions/fonctions récursives

La notion de récursivité est une notion-clef en algorithmique. Une fonction récursive est
une fonction qui dans son code fait un appel à elle-même. Ce type de fonctions permet de réaliser
des algorithmes complexes sans utiliser de boucles. Il convient néanmoins de faire attention à
la terminaison du programme, en faisant en sorte que chaque appel récursif fasse décroitre
strictement une certaine quantité. Au début de la fonction, un test sur cette quantité retournera
directement le résultat voulu.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Qu'est-ce qu'une fonction récursive ?
 Savoir dérouler les appels récursifs d'une fonction.
 Savoir dire si une fonction est récursive terminale ou pas.
 Calculer la complexité en terme de nombre d'appels récursifs.

40/85
 Définition
Algorithmique et Programmation, IMA
Cours 3c - Récursivité

Laure Gonnord
[Link] Un algorithme (une fonction, une procédure) est dit récursif si
[Link]@[Link] sa définition (son code) contient un appel à lui-même.

Université Lille 1 - Polytech Lille Un algorithme qui n’est pas récursif est dit itératif.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 2/9

Utilisations usuelles Quelques exemples classiques - 1

Factorielle : n! = n.(n − 1)!

Fonction fact(n) : entier
Utilisations variées (liste non exhaustive) : D: n : entier positif ou nul
Si n=0 alors
Calcul de suite récursive (numérique, graphique. . . )
Retourner 1
Calcul de type « diviser pour régner » : recherche, tri, . . . Sinon
Calcul sur des structures de données inductives (listes, Retourner n*fact(n-1) {Appel récursif}
arbres, . . . ) I Prog avancéee (S6). Fsi
I Dans tous les cas, une version itérative est possible. FFonction
I Attention au type de retour et à l’orthographe du nom de la
fonction.
I Dérouler ! I Complexité en nb d’appels ?

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 3/9 Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 4/9
Quelques exemples classiques - 2 Quelques exemples classiques - 3
Fibonacci : F ibo(n) = F ibo(n − 1) + F ibo(n − 2)
Fonction fibo(n) : entier
D: n : entier positif ou nul Que calcule somme(5,0) ?
Si n=0 alors Fonction somme (n,r) :entier
Retourner 1 D: n,r : entier positifs ou nul
Sinon Si n = 1 alors
Si n=1 alors Retourner r + 1
Retourner 1 Sinon
Sinon Retourner somme (n -1 , r + n )
Retourner fibo(n-1)+fibo(n-2) {Appel récursif} Fsi
Fsi FFonction
Fsi I r est appelé paramètre d’accumulation.
FFonction
I Dérouler ! I Complexité en nb d’appels ?
I L’implémentation impérative est meilleure, pourquoi ?
Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 5/9 Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 6/9

Récursivité terminale (ou pas ?) Dérécursivons !

La factorielle :
Un algorithme récursif est dit récursif terminal si l’appel Fonction fact(n) : entier
récursif est la dernière instruction réalisée. Fonction fact(n) : entier
D: n : entier positif ou
I Stockage non nécessaire de la valeur obtenue par D: n : entier positif ou nul
nul
récursivité. L: i,f :entier
Si n=0 alors
f← 1
Retourner 1
Factorielle : f act(n − 1) puis multiplication par n, donc non Pour i de 0 à n Faire
Sinon
récursif terminal. Retourner f← f*i
n*fact(n-1) Fpour
Somme : récursif terminal :
Fsi Retourner f
somme(5, 0) = somme(4, 5) = somme(...) . . . = 15
FFonction
FFonction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 7/9 Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 8/9
Attention

Toujours bien vérifier que votre algorithme termine !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA Cours 3b récursivité 2012 9/9

Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Chapitre 4
Vecteurs/Tableaux
Lorsque l'on veut utiliser un grand nombre de variables dans un programme, ou lorsqu'on
veut stocker un résultat de grande taille, on utilise une suite de cases adjacentes en mémoire,
c'est-à-dire un vecteur (ou tableau, en C). Dans ce cours nous voyons comment déclarer et
utiliser un tableau statique en pseudo-code et en C. Des exemples classiques de tableaux
d'entiers, de charactères, sont donnés. Les tableaux en deux dimensions ( matrices) sont éga-
lement abordés.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Cas d'utilisation d'un tableau.
 Déclarer un tableau d'entiers de taille xée à l'avance, et initialiser toutes ses cases (par
exemple à 0).
 Connaître diérentes façons de parcourir toutes les cases d'un tableau (avec et sans rup-
ture prématurée de ot).
 Savoir déclarer et utiliser des matrices (tableaux 2d).
 Connaître l'encodage des chaînes de caractères sous forme de tableau avec marqueur de
n.
 Savoir concevoir des algorithmes de tableaux, de chaînes et évaluer leur complexité.
 Savoir utiliser la librairie string.h.
 Connaître la spécicité des tableaux en terme de paramètres (on ne peut retourner un
tableau, on passe le tableau en paramètre modiable, et tel quel en C).

Figure 4.1  [Link] sous License Creative Commons

44/85
 Plan

Algorithmique et Programmation, IMA 3

Cours 4 : Vecteurs/Tableaux 1 Vecteurs et Tableaux

Laure Gonnord 2 Algorithmes sur les tableaux d’entiers

[Link]
[Link]@[Link] 3 Algorithmes de mots
Université Lille 1 - Polytech Lille
4 Tableaux2d - Matrices

5 Erreurs sur les tableaux - à la compilation et exécution

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  2 / 35 

Vecteurs et Tableaux Vecteurs et Tableaux

Vecteurs - Algo

1 Vecteurs et Tableaux
Vecteur = suite de cases dont le contenu est de même type :
2 Algorithmes sur les tableaux d’entiers
2 3 −5 −8
3 Algorithmes de mots
Déclaration (tableau de taille N fixée) :
4 Tableaux2d - Matrices v : Vecteur[N] de (type de base)
Les cases sont numérotées de 0 à N − 1 (attention source
5 Erreurs sur les tableaux - à la compilation et exécution d’erreurs !)
Accès à la case i : v[i]

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  3 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  4 / 35 
 Vecteurs et Tableaux Vecteurs et Tableaux

Vecteurs - Syntaxe C Tableaux en C

Déclaration Les tableaux que nous utilisons au semestre 5 ont une taille
fixée à l’avance (à la déclaration), ce sont des tableaux
int t [23] ; // tableau d ’ entiers
statiques.
char c h a r t a b [ 9 0 0 ] ; / / t a b l e a u d e c h a r a c t e r e s
I Comment écrire des fonctions qui fonctionnent pour des
Utilisation : tableaux de taille quelconque ? Deux possibilités :
x = t [10]; / / appel l i c i t e Utiliser des constantes symboliques à la déclaration des
y = chartab [ 1 5 1 5 ] ; / / p l a n t a g e a l ’ e x e c u t i o n tableaux et dans l’écriture des fonctions
z = t [ expr compliquee ] ;
int t [12]={0}; / / declaration − i n i t Utiliser des fonctions dans lesquelles la taille du tableau
est un nouveau paramètre.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  5 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  6 / 35 
Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Accès direct

1 Vecteurs et Tableaux Exemple : échange de cases.

2 Algorithmes sur les tableaux d’entiers Action swap(i,j,t)

D: i,j : entiers {Données}
D/R: t : Vecteur[N] d’Entiers {Donnée/Résultat}
3 Algorithmes de mots
L: tmp : entier
tmp ← t[i];
4 Tableaux2d - Matrices t[i] ← t[j];
t[j] ← tmp;
5 Erreurs sur les tableaux - à la compilation et exécution FAction
Exercice : traduire en C et modifier pour les cas
« pathologiques ».

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  7 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  8 / 35 
 Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Swap, en C, avec constante symbolique (V1) Swap, en C, V2, en passant la taille en paramètre
# d e f i n e N 12 void swap ( i n t t [ ] , i n t i , i n t j , i n t s i z e ) {
i n t tmp ;
void swap ( i n t t [ N ] , i n t i , i n t j ) { i f ( i >=0 && i < s i z e && j >=0 && j < s i z e ) {
i n t tmp ; tmp = t [ i ] ;
i f ( i >=0 && i < N && j >=0 && j <N ) { t [ i ] = t [ j ];
tmp = t [ i ] ; t [ j ] = tmp ;
t [ i ] = t [ j ]; }
t [ j ] = tmp ; }
}
} i n t main ( ) {
i n t size = 12; / / ou s c a n f
i n t main ( ) { int t [ size ] ;
i n t t [N ] ; ...
... swap ( t , 2 , 3 , s i z e ) ;
swap ( t , 2 , 3 ) ; }
}
I Préférence pour celle-ci.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  9 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  10 / 35 
Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Parcours d’un tableau - 1 Parcours d’un tableau - 1 (impression) Code C

Exemple : impression de tous les éléments.

Action printtab(t)
D: t : Vecteur[N] d’Entiers {Données}
L: i : entier {Var d'itération}
Pour i de 0 à N-1 Faire
imprimeEntier(t[i]);
Fpour
FAction
Exercice : traduire en C

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  11 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  12 / 35 
 Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Parcours d’un tableau - 2 Parcours d’un tableau - 2 (copie) Code C

Exemple : copie d’un tableau dans un autre.

Action copytab(t,resu)
D: t : Vecteur[N] d’Entiers {Donnée}
D/R: resu : Vecteur[N] d’Entiers {Donnée/Résultat}
L: i : entier {Var d'itération}
Pour i de 0 à N-1 Faire
resu[i] ← t[i];
Fpour
FAction
Exercice : traduire en C

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  13 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  14 / 35 
Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Recherche dans un tableau - 1 Recherche dans un tableau - 2a

Exemple : recherche du maximum. Exemple : recherche d’une valeur particulière.
Fonction maxtab(t) : entier Fonction maxtab(val,t) : bool
D: t : Vecteur[N] d’Entiers {Donnée} D: t : Vecteur[N] d’Entiers {Donnée}
L: i : entier {Var d'itération} D: val : entier {Valeur à rechercher}
L: maxi : entier {Max temporaire} L: i : entier {Var d'itération}
maxi = t[0]; Pour i de 0 à N-1 Faire
Pour i de 1 à N-1 Faire Si t[i]=val alors
Si maxi<t[i] alors Retourner (Vrai)
maxi ← t[i]
Fsi
Fsi
Fpour
Fpour
Retourner (Faux)
Retourner (maxi) FFonction
FFonction
Exercice : correction, puis traduire en C.
I Correction de ce programme ?

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  15 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  16 / 35 
 Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Recherche dans un tableau - 2a Code C Recherche dans un tableau - 2b

Le même sans rupture prématurée du flot.
Fonction maxtabWhile(val,t) : bool
D: t : Vecteur[N] d’Entiers {Donnée}
D: val : entier {Valeur à rechercher}
L: i : entier {Var d'itération}
i← 0 ; fini← Faux
Tq non (fini) et i<N faire
Si t[i]=val alors
fini← Vrai
Fsi
i← i+1
Ftq
Retourner fini
FFonction
Exercice : correction, puis traduire en C.
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  17 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  18 / 35 
Algorithmes sur les tableaux d’entiers Algorithmes sur les tableaux d’entiers

Recherche dans un tableau - 2b Code C Encodages par tableaux

Les tableaux peuvent aussi servir à encoder :

des ensembles (cf TD)
des arbres

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  19 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  20 / 35 
 Algorithmes sur les tableaux d’entiers Algorithmes de mots

Retour sur les actions/fonctions

I Et si je veux retourner un tableau ? 1 Vecteurs et Tableaux
Important Les tableaux sont des paramètres modifiables en C !
Action calculetab(tab) 2 Algorithmes sur les tableaux d’entiers
R: tab : Vecteur[1..1000] d’Entiers
.....
tab[42] = 7070 3 Algorithmes de mots
FAction
4 Tableaux2d - Matrices
Programme Main
L: t : Vecteur[1..1000] d’Entiers
calculetab(t) 5 Erreurs sur les tableaux - à la compilation et exécution
Imprime(t[42])
Retourner 0
FProgramme

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  21 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  22 / 35 
Algorithmes de mots Algorithmes de mots

Les chaînes de caractères Parcours de chaîne

Exemple : nombre de ’a’ dans un mot.
Les chaînes de caractères sont souvent des types de base
Fonction nba(t) : entier
(string en Ocaml).
D: t : Vecteur[TMAX] de charactères {Donnée}
En C, les chaînes de caractères sont des tableaux de L: i : entier {Var d'itération}
charactères avec \0 comme marqueur de fin de chaîne. L: nb : entier {nb de 'a' temporaire}
nb = 0 ; i = 0 ;
0 t0 0 o0 0 t0 0 o0 0 \00 Tq t[i] 6= ‘\0‘ et i <TMAX faire
Si t[i]=’a’ alors
Syntaxe C : nb← nb+1
char ch [ 1 2 ] = { ’ t ’ , ’ o ’ , ’ t ’ , ’ o ’ } ; Fsi
char ch2 [ 1 0 0 ] = " t o t o " ; i ← i+1 {ne pas oublier !}
char ch3 [ ] = " t o t o " ; / / c h 3 a u r a 5 c a s e s Ftq
Retourner (nb)
char a = ch3 [ 2 ] ; // a est ’ t ’
FFonction
I Invariant de la boucle ?
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  23 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  24 / 35 
 Algorithmes de mots Algorithmes de mots

Algos de chaînes La librairie string

D’autres algorithmes classiques (à voir en TD, TP, . . . ) La librairie string fournit des fonctions de base sur les chaînes
Un mot donné (avec sa taille) est-il un palindrôme ? de caractères :
Calculer la concaténation de deux mots ? lecture à partir de l’entrée standard
Un mot est-il un sous mot d’un autre ? copie
Combien de fois apparaît un mot donné dans un texte (mot comparaison de chaînes
plus long) ? sous-chaîne, concaténation, . . .
I algorithmique du texte I Voir à la fin du chapitre sur les pointeurs !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  25 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  26 / 35 
Tableaux2d - Matrices Tableaux2d - Matrices

Matrices - Algo
Matrice = tableau 2D
1 Vecteurs et Tableaux
2 3 −5
2 Algorithmes sur les tableaux d’entiers 4 −13 42
1515 −77 0
3 Algorithmes de mots
Déclaration : matrice N × M (taille fixée)
m : Matrice[N][M] de (type de base)
4 Tableaux2d - Matrices

5 Erreurs sur les tableaux - à la compilation et exécution Accès à la case (ime ligne, j me colonne) : m[i][j]
Pour une ligne fixée, les cases sont numérotées de 0 à
M − 1 (il y a M colonnes).
Pour une colonne fixée, les cases sont numérotées de 0 à
N − 1 (il y a N lignes).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  27 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  28 / 35 
 Tableaux2d - Matrices Tableaux2d - Matrices

Matrices - Syntaxe C Ex : Impression de toutes les cases d’une matrice

carrée

Déclaration
Action ParcoursMat(t)
int t [23][42] ; // matrices d ’ entiers
L: i,j : Entiers
char c h a r t a b [ 9 0 0 ] [ 1 2 ] ; / / m a t r i c e d e c h a r a c t e r e s
D: t : Matrice[N][N] d’Entiers
Pour i de 0 à N-1 Faire
Utilisation :
Pour j de 0 à N-1 Faire
x = t [10][10]; / / appel Imprimer(t[i][j])
z = t [ expr compliquee ] [ exp2 ] ; Fpour
Important Les matrices sont des paramètres modifiables en C ! Fpour
FAction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  29 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  30 / 35 
Tableaux2d - Matrices Tableaux2d - Matrices

Ex : Impression de la diagonale d’une matrice carrée Ex : Recherche d’un élément dans une matrice
rectangulaire
Fonction ParcoursMat(t,el) :Booleen
L: i,j : Entiers
Action ParcoursMat(t) D: t : Matrice[N][M] d’Entiers
L: i,j : Entiers D: el : Entier
D: t : Matrice[N][N] d’Entiers Pour i de 0 à N-1 Faire
Pour i de 0 à N-1 Faire Pour j de 0 à M-1 Faire
Imprimer (t[i][i]) ; Si (t[i][j]=el) alors
Fpour Retourner Vrai
FAction Fsi
Fpour
Fpour
Retourner Faux
FFonction
I On n’effectue pas tout le programme si on trouve l’élément.
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  31 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  32 / 35 
 Tableaux2d - Matrices Erreurs sur les tableaux - à la compilation et exécution

Ex : Recherche d’un élément dans une matrice

rectangulaire
Version sans arrêt prématuré du flot : 1 Vecteurs et Tableaux
Fonction ParcoursMatWhile(t,el) :Booleen
D: idem 2 Algorithmes sur les tableaux d’entiers
L: i,j : Entiers
L: fini : Booléen 3 Algorithmes de mots
fini ← Faux ; i← 0 ; j← 0
Tq ( non fini) et i<N faire
4 Tableaux2d - Matrices
Tq ( non fini) et j<M faire
Si (t[i][j]=el) alors
fini ← Vrai 5 Erreurs sur les tableaux - à la compilation et exécution
Fsi
Ftq
Ftq
Retourner fini
FFonction
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  33 / 35  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  34 / 35 
Erreurs sur les tableaux - à la compilation et exécution

Erreurs classiques :
Tableau déclaré et pas initialisé : aucune erreur,
impression du contenu courant de la case mémoire.
Accès en dehors du tableau : pas d’erreur de compilation,
Segmentation Fault ou valeur quelconque à l’exécution.
Copie de tableau non case par case :
int t[12]={0};
int g[12];
g=t;
Erreur à la compilation :
tab.c:46:4: error: array type 'int [12]' is not assignable
g=t;
~^
1 error generated.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 4 Tableaux 2012  35 / 35 

Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Chapitre 5
Algorithmique du Tri
Premier chapitre d'algorithmique proprement dite ! Il s'agit ici de proposer des algorithmes
pour trier un tableau d'entiers. Les algorithmes classiques sont ainsi vus, et leur complexité est
évaluée. Ces algorithmes seront développés en TD et implémentés en C en TP.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Connaître les principes des principaux algorithmes d'entiers.
 Savoir dérouler les algos à la main sur des petits tableaux (même les algorithmes récursifs ).
 Savoir produire le pseudo-code rapidement.
 Connaître les invariants de ces algorithmes.
 Connaître (oui, par coeur !) leur complexité. Savoir la calculer.

Remarque 2 Le tribulle, algorithme classique mais peu ecace, n'est pas traité dans ce cours

54/85
 Trions !

Algorithmique et Programmation, IMA 3

Cours 5b Algos de tri

1 Trions !
Laure Gonnord
[Link] 2 Considérations diverses sur les tris
[Link]@[Link]

Université Lille 1 - Polytech Lille

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  2 / 22 

Trions ! Trions !

Énoncé du problème Action auxillaire

But
On va trier des tableaux d’entiers de taille N .
On dispose du test de comparaison entre entiers On dispose de l’action auxilliaire permuter de signature (ou
prototype) :
Exemple :
permuter(T:Tableau[N] d'Entiers,ind1:Entier,ind2:Entier)
11 -2 1515 42 2048 28 11 -78
devient qui permute les valeurs des éléments d’indices ind1 et ind2 du
-78 -2 11 11 28 42 1515 2048 tableau T .

I Let’s go !
I Attention transparents sans exemple ni dessin, donc, en
faire !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  3 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  4 / 22 
 Trions ! Trions !

Tri Sélection Sélection

Action tri-sélection(T)
D/R: T : Tableau[N] d’entiers
L: ideb,i : Entiers
Principe : L: imin : Entier {Indice de l'élément minimum courant}
Je cherche le minimum du tableau et je le permute avec la Pour ideb de 0 à N-2 Faire
case d’indice 0. {Recherche de l'indice de l'élément minimum}
imin := ideb;
Je cherche le minimum du tableau restant (le sous tableau
Pour i de ideb + 1 à N-1 Faire
T [1..N − 1]) et je le permute avec la case indice 1
Si T[i] < T[imin] alors
Je cherche ..... imin := i
I Algo, Correction, Complexité Fsi
Fpour
permuter(T,ideb,imin)
Fpour
FAction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  5 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  6 / 22 
Trions ! Trions !

Sélection : analyse Tri Insertion

Correction : « L’algorithme tri-selection conserve les éléments «Tri des cartes à jouer» :
du tableau T et les trie dans l’ordre croissant » Je trie les 2 premières cartes.
Invariant : « à la fin du tour ideb, le sous-tableau T [0..ideb] Je regarde la troisième et l’insère à sa bonne place (par
contient les ideb + 1 plus petits éléments de T, dans l’ordre décalages vers la droite).
croissant de leurs valeurs » ...
Coût (nb comparaisons) : (N − 1) + (N − 2) + . . . 1 = O(N 2 ). I Algo, Correction, Complexité

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  7 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  8 / 22 
 Trions ! Trions !

Insertion Insertion : analyse

Action tri-insertion(T)
D/R: T : Tableau[N] d’entiers
L: i : Entier
L: élt : Entier {Valeur à insérer}
L: ins : Entier {Indice d'insertion de élt} Correction : on prouve l’invariant suivant : « Au tour i, la boucle
Pour i de 1 à N-1 Faire insère l’élément T [i] dans le sous-tableau T [0..i − 1] déjà trié »
élt := T[i] {Initialisation}
ins := i Coût : O(N ) au mieux, O(N 2 ) au pire et en moyenne.
Tq (ins > 1 et T[ins-1] > élt) faire Améliorable en N ln2 (N ).
T[ins] := T[ins-1];
ins := ins - 1
Ftq
T[ins] := élt {Insertion de T[i]}
Fpour
FAction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  9 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  10 / 22 
Trions ! Trions !

Tri Fusion Tri Fusion - 1

Action tri-fusion-bis(T,premier,dernier)
D: premier,dernier : Entiers
Principe «diviser pour régner» : D: T : Tableau[N] d’entiers
Un tableau de taille 1 est trié ! L: milieu : entier
Je découpe en deux le tableau Si premier<dernier alors
milieu ← (premier+dernier)/2
Je trie chacun des sous-tableaux
tri-fusion-bis(T,premier,milieu) {Appel récursif 1}
Je fusionne tri-fusion-bis(T,milieu+1,dernier) {Appel réc. 2}
I Algo récursif !, Correction, Complexité fusion(T,premier,milieu,dernier)
Fsi
FAction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  11 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  12 / 22 
 Trions ! Trions !

Tri Fusion - 2 Tri Fusion - 3

Dessin ! On va garder en mémoire deux curseurs, c1 et c2, sur

chacun des bouts de tableaux à fusionner.
Action tri-fusion(T) Action fusion(T,premier1,dernier1,dernier2)
D: T : Tableau[N] d’entiers D: premier1,dernier1,dernier2 : Entiers
Si N>1 alors D: T : Tableau[N] d’entiers
tri-fusion-bis(T,0,N-1) L: fus : Tableau[dernier2-premier1+1] d’entiers
Fsi L: c1,c2,premier2 : Entiers
FAction premier2 := dernier1+1
c2 := premier2
I Il reste à écrire fusion. c1 := premier1
... suite page suivante ...
FAction

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  13 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  14 / 22 
Trions ! Trions !

Tri Fusion - 4 Fusion : analyse

Parcours de fusion : le tableau local fus est rempli, puis recopié
dans le tableau initial.
Pour i de 0 à dernier2-premier1 Faire
Si (c16dernier1 et (t[c1]<t[c2] ou c2> dernier2)) alors
fus[i]← t[c1] On suppose que fusionne fait bien son travail
c1++ Correction : « l’appel à tri-fusion sur un tableau de taille i trie le
Sinon tableau »
fus[i]← t[c2]
c2++ Coût : O(N ln2 N ) tout le temps. preuve au tableau
Fsi
Fpour
Pour i de 0 à dernier2-premier1 Faire
t[premier1+i] ← fus[i]
Fpour

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  15 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  16 / 22 
 Trions ! Considérations diverses sur les tris

Tri Rapide

1 Trions !
Principe du pivot
Je partitionne le tableau en fonction d’un pivot (premier 2 Considérations diverses sur les tris
élement du tableau).
Je trie récursivement sur chacun des tableaux à sa gauche
et à sa droite.
I Algo, Correction, Complexité, en TD !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  17 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  18 / 22 
Considérations diverses sur les tris Considérations diverses sur les tris

Tri de tableaux Tri de tableaux - récapitulatif

Théorème On évalue le nombre de comparaisons

Un tri de tableaux d’entiers par comparaisons ne peut être Algorithme Meilleur des cas En moyenne Pire des cas
réalisé en o(n ln2 n) comparaisons en moyenne et dans le pire Tri par sélection O(N 2 ) O(N 2 ) O(N 2 )
Tri par insertion O(N ) O(N 2 ) O(N 2 )
des cas. Tri fusion O(N × ln2 (N )) O(N × ln2 (N )) O(N × ln2 (N ))
Tri rapide O(N × ln2 (N )) O(N × ln2 (N )) O(N 2 )
I Un tri est alors optimal si il a une complexité de Ω(n ln2 n)
en moyenne et dans le pire des cas.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  19 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  20 / 22 
 Considérations diverses sur les tris Considérations diverses sur les tris

Un tri linéaire ! Caractères stable et en place

Et si on connaît à l’avance les valeurs des éléments ?

Exemple : tri comptage (ou tri par casiers) : Stable
On crée autant de casiers que de valeurs possibles Un algo de tri est stable si deux valeurs identiques restent
On compte les occurrences de ces valeurs dans le même "ordre" à la fin de l’algo.
On utilise pour trier
En place
Exemple : 1 10 3 1 3
Un algo de tri est en place si il trie sans création d’un tableau
Tableau d’occurences : auxiliaire.
2 0 2 0 3 0 0 0 0 1
et finalement : I Les algorithmes insertion, sélection sont en place
1 1 3 3 10

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  21 / 22  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 5 Ctes, Tris 2012  22 / 22 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Chapitre 6
Variables modiables en C : les pointeurs

6.1 Notions de base sur les pointeurs

Dans ce cours nous présentons l'implémentation C des variables modiables : les pointeurs.
En eet, le langage C donne un accès aux adresses de stockage des variables, et fournit un
nouveau type adresse que nous pouvons manipuler comme type de base. An de pouvoir com-
prendre nement ce qui se passe lors d'un appel de fonction C, nous aborderons aussi la notion
de schéma d'exécution, qui se veut une abstraction de ce qui se passe en mémoire lors de
l'exécution d'un programme C.

Savoirs (liste non exhaustive) (en C et pseudo-code)

 Quelle est la diérence entre passage de paramètres par valeur et passage par adresse ?
 Savoir faire le schéma d'exécution d'un programme simple.
 Déclarer et initialiser un pointeur d'entier, de caractère. . .
 Utiliser les pointeurs pour passer un paramètre par adresse.
 Le pointeur NULL.

Remarque 3 Attention ! La compréhension de ce cours est un prérequis au cours de S6 Pro-

grammation avancée

Figure 6.1  [Link] sous License Creative Commons

61/85
 Schémas d’exécution - variables modifiables

Algorithmique et Programmation, IMA 3

Cours 6a : Variables Modifiables, Pointeurs
1 Schémas d’exécution - variables modifiables
Laure Gonnord
[Link]
2 Les pointeurs
[Link]@[Link]
3 Quelques exemples
Université Lille 1 - Polytech Lille
4 Validité des pointeurs
d’après A. Miné (ÉNS Ulm)

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  2 / 32 

Schémas d’exécution - variables modifiables Schémas d’exécution - variables modifiables

Passage de paramètres par valeur Passage de paramètres par adresse

Variables D en langage algorithmique.
Variables R ou D/R en langage algorithmique.
Fonction ajoute_un(a) : Entier
D: a : Entier Exemple :
Retourner a+1 Action inc(x)
FFonction D/R: x : Entier {Donnée/Résultat}
x ← x+1
Appel : FAction
Programme Main
L: x,y :Entiers Que fait la suite d’instructions suivante :
x ← 12 y : Entier ;
y ← ajoute_un(x) y ← 100 ;
Imprimer(y) inc(y) ;inc(y) ;
Retourner 0 Que vaut y à la fin ?
FProgramme I Que se passe-t-il lors de l’appel de inc ?
I Que se passe-t-il lors de l’appel de ajoute_un ?

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  3 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  4 / 32 
 Schémas d’exécution - variables modifiables Schémas d’exécution - variables modifiables

Modèle mémoire simplifié Schéma d’exécution d’une fonction - 1

Fonction ajoute_un(a) : Entier
Pour expliquer : Mémoire ' tableau d’octets.
D: a : Entier
Chaque octet a une adresse en mémoire.
Retourner a+1
I Chaque variable déclarée a une adresse (début du FFonction
placement mémoire).
Appel :
type int int char ..... int Programme Main
nom x y c ..... z L: x,y :Entiers
adresse 3A00 3A04 3A08 ..... 3A40 x←1
valeur 10 42 ’a’ ..... ... y ← ajoute_un(x)
...
I La place en mémoire dépend du type de la variable (1 octet FProgramme
pour un char, 4 pour un int (ou 8), . . . )
I Représentons la mémoire.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  5 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  6 / 32 
Schémas d’exécution - variables modifiables Schémas d’exécution - variables modifiables

Schéma d’exécution d’une fonction - 2 Schéma d’exécution d’une fonction - 2

type nom adresse valeur type nom adresse valeur

int x 3A10
int y 3A20

main main

Programme Main Programme Main

Fonction ajoute_un(a) : Entier L: x,y :Entiers Fonction ajoute_un(a) : Entier L: x,y :Entiers
D: a : Entier x←1 D: a : Entier x←1
Retourner a+1 y ← ajoute_un(x) Retourner a+1 y ← ajoute_un(x)
FFonction ... FFonction ...
FProgramme FProgramme

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32 
 Schémas d’exécution - variables modifiables Schémas d’exécution - variables modifiables

Schéma d’exécution d’une fonction - 2 Schéma d’exécution d’une fonction - 2

type nom adresse valeur type nom adresse valeur type nom adresse valeur
int x 3A10 1 int x 3A10 1 int a 3F10
int y 3A20 int y 3A20 int retour 3F20

main main ajoute_un

Programme Main Programme Main
Fonction ajoute_un(a) : Entier L: x,y :Entiers Fonction ajoute_un(a) : Entier L: x,y :Entiers
D: a : Entier x←1 D: a : Entier x←1
Retourner a+1 y ← ajoute_un(x) Retourner a+1 y ← ajoute_un(x)
FFonction ... FFonction ...
FProgramme FProgramme

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32 
Schémas d’exécution - variables modifiables Schémas d’exécution - variables modifiables

Schéma d’exécution d’une fonction - 2 Schéma d’exécution d’une fonction - 2

type nom adresse valeur type nom adresse valeur type nom adresse valeur type nom adresse valeur
int x 3A10 1 int a 3F10 1 int x 3A10 1 int a 3F10 1
int y 3A20 int retour 3F20 int y 3A20 2 int retour 3F20 2

main ajoute_un main ajoute_un

Programme Main Programme Main
Fonction ajoute_un(a) : Entier L: x,y :Entiers Fonction ajoute_un(a) : Entier L: x,y :Entiers
D: a : Entier x←1 D: a : Entier x←1
Retourner a+1 y ← ajoute_un(x) Retourner a+1 y ← ajoute_un(x)
FFonction ... FFonction ...
FProgramme FProgramme

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32 
 Schémas d’exécution - variables modifiables Schémas d’exécution - variables modifiables

Schéma d’exécution d’une fonction - 2 Schéma d’exécution d’action

type nom adresse valeur

int x 3A10 1 Action inc(x)
D/R: x : Entier
int y 3A20 2
x ← x+1
FAction
main

Programme Main Appel :

Fonction ajoute_un(a) : Entier L: x,y :Entiers y : Entier ;
D: a : Entier x←1 y ← 100 ;
Retourner a+1 y ← ajoute_un(x) inc(y) ;
FFonction ...
FProgramme I Dessin !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  7 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  8 / 32 
Schémas d’exécution - variables modifiables Les pointeurs

Résumé

1 Schémas d’exécution - variables modifiables

un morceau de mémoire indépendant par fonction/action

2 Les pointeurs
la mémoire pour les variables locales est libérée après la
fin de l’appel de fonction.
3 Quelques exemples
lors d’un passage par valeur, il y a une copie des
valeurs
4 Validité des pointeurs
lors d’un passage par adesse, il y a une copie des
adresses

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  9 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  10 / 32 
 Les pointeurs Les pointeurs

En C Les adresses et le C

En C, on peut :
A SAVOIR :
obtenir l’adresse d’une variable existante (&),
le passage par valeur est le passage par défaut en C SAUF
pour les tableaux qui sont passés par adresse. accéder au contenu stocké à une adresse valide (*),
passer des adresses en argument, les retourner, les copier
(=),
I Pour passer un paramètre par adresse, on utilise les effectuer des opérations limitées sur les adresses (+, ==,
pointeurs . . . ).
I C’est l’objet des transparents suivants.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  11 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  12 / 32 
Les pointeurs Les pointeurs

L’opérateur d’adresse & Déréférencement *

Obtenir l’adresse d’un objet en mémoire :
Accéder au contenu stocké à une adresse valide (*)
&expr Si p est une adresse valide, alors ∗p donne le contenu de la
case située à l’adresse p.
expr doit être une lvalue (i.e., modifiable) existante !
void i n c ( i n t ∗ px )
variable scalaire,
{
case d’un tableau. ∗px=∗px+1
Exemple : }

int i , a [ 2 ] ; ( main )
&i / ∗ a d r e s s e de i ∗ / i n t y =100;
p r i n t f ( "%p " ,& i ) /∗ impression d ’ adresse ∗/ i n c (& y ) ;
&(a [ 0 ] ) &a [ 0 ] &a / ∗ a d r e s s e d e a [ 0 ] ∗ /
&( i +1) / ∗ e r r o r : l v a l u e r e q u i r e d as u n a r y ’& ’ operand ∗/ I De quel type est la variable px ? int* !
s c a n f ( "%d " ,& i ) ; /∗ acces a l ’ adresse ∗/

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  13 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  14 / 32 
 Les pointeurs Les pointeurs

Les types pointeur Les types pointeur - 2

Les variables passées en D/R seront donc de type “pointeur” :
pointeur d’entier : int* (destiné à stocker une adresse de
variable entière) Lorsqu’on déclare t* var, var peut contenir l’adresse de tout
pointeur de caractère : char* (destiné à stocker . . . ) objet de type t.
t* est un pointeur sur un objet de type t Attention ! Le type pointé est important ! Si t16=t2, alors t1* et
I si expr a pour type t, alors &expr a pour type t*. t2* sont incompatibles.
Donc, un pointeur de réels ne peut pas contenir une adresse
d’une valeur entière !
Exemple :
float f ;
i n t i =4; / ∗ i e s t un e n t i e r ∗ /
i n t ∗ p ; / ∗ p << p o i n t e u r d ’ e n t i e r >> ∗ /
int ∗ pi ; /∗ p pointeur d ’ entier ∗/
p = &f ; /∗ warning : assignment from i n c o m pa t i b le pointer type
pi = &i / ∗ a d r e s s e de i ∗ /

"pi pointe sur i"

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  15 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  16 / 32 
Les pointeurs Quelques exemples

Comparaison de pointeurs

1 Schémas d’exécution - variables modifiables

2 Les pointeurs
On peut comparer deux pointeurs pour :
l’égalité == (pointent sur la même adresse ?)
3 Quelques exemples
la différence != (pointent sur des adresses
différentes ?).
4 Validité des pointeurs

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  17 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  18 / 32 
 Quelques exemples Quelques exemples

Quelques exemples de & et * Ex : Permutation

void permuter ( i n t ∗ px , i n t ∗ py )
Rappel {
*p : contenu de la mémoire à l’adresse p. i n t temp ;
temp = ∗px ;
&x : adresse de la variable x. ∗px = ∗py ;
int x , y ; ∗py = temp ;
y = 12; }
i n t ∗ p i = &x ;
∗ pi = 2; / ∗ p l a c e 2 dans x ∗ / ( main )
p i = &y ; i n t a=1 ,b =3;
∗ p i = ∗ p i +1; / ∗ i n c r e m e n t e y ∗ / permuter (&a ,& b ) ;
p r i n t f ( "%d %d " , a , b ) ;
I Réalisons le schéma d’exécution de ce programme.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  19 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  20 / 32 
Quelques exemples Quelques exemples

Ex : Permutation - 2 Ex : Permutation - 2
appel de fonction

type nom adresse valeur type nom adresse valeur type nom adresse valeur
int a 3A10 1 int a 3A10 1 int* px 3F10 3A10
int b 3A20 3 int b 3A20 3 int* py 3F20 3A20

main main int temp 3F30

permuter
void permuter ( i n t ∗ px , i n t ∗ py ) void permuter ( i n t ∗ px , i n t ∗ py )
{ {
( main ) ( main )
i n t temp ; i n t temp ;
i n t a=1 ,b =3; i n t a=1 ,b =3;
temp = ∗px ; temp = ∗px ;
permuter (&a ,& b ) ; permuter (&a ,& b ) ;
∗px = ∗py ; ∗px = ∗py ;
p r i n t f ( "%d %d " , a , b ) ; p r i n t f ( "%d %d " , a , b ) ;
∗py = temp ; ∗py = temp ;
} }
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32 
 Quelques exemples Quelques exemples

Ex : Permutation - 2 Ex : Permutation - 2
*px

type nom adresse valeur type nom adresse valeur type nom adresse valeur type nom adresse valeur
int a 3A10 1 int* px 3F10 3A10 int a 3A10 1 int* px 3F10 3A10
int b 3A20 3 int* py 3F20 3A20 int b 3A20 3 int* py 3F20 3A20

int temp 3F30 int temp 3F30 1

main main

permuter permuter
void permuter ( i n t ∗ px , i n t ∗ py ) void permuter ( i n t ∗ px , i n t ∗ py )
{ {
( main ) ( main )
i n t temp ; i n t temp ;
i n t a=1 ,b =3; i n t a=1 ,b =3;
temp = ∗px ; temp = ∗px ;
permuter (&a ,& b ) ; permuter (&a ,& b ) ;
∗px = ∗py ; ∗px = ∗py ;
p r i n t f ( "%d %d " , a , b ) ; p r i n t f ( "%d %d " , a , b ) ;
∗py = temp ; ∗py = temp ;
} }
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32 
Quelques exemples Quelques exemples

Ex : Permutation - 2 Ex : Permutation - 2

type nom adresse valeur type nom adresse valeur type nom adresse valeur type nom adresse valeur
int a 3A10 1 int* px 3F10 3A10 int a 3A10 3 int* px 3F10 3A10
int b 3A20 3 int* py 3F20 3A20 int b 3A20 1 int* py 3F20 3A20

main int temp 3F30 1 main int temp 3F30 1

permuter permuter
void permuter ( i n t ∗ px , i n t ∗ py ) void permuter ( i n t ∗ px , i n t ∗ py )
{ {
( main ) ( main )
i n t temp ; i n t temp ;
i n t a=1 ,b =3; i n t a=1 ,b =3;
temp = ∗px ; temp = ∗px ;
permuter (&a ,& b ) ; permuter (&a ,& b ) ;
∗px = ∗py ; ∗px = ∗py ;
p r i n t f ( "%d %d " , a , b ) ; p r i n t f ( "%d %d " , a , b ) ;
∗py = temp ; ∗py = temp ;
} }
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32 
 Quelques exemples Quelques exemples

Ex : Permutation - 2 Ex : Division

(paramètres R)
type nom adresse valeur
void d i v i s e ( i n t a , i n t b , i n t ∗ pdiv , i n t ∗ prem ) {
int a 3A10 3 ∗ pdiv = a / b ;
int b 3A20 1 ∗prem = a % b ;
}
main
void f ( ) {
int x , y ;
d i v i s e ( 100 , 10 , &x , &y ) ;
void permuter ( i n t ∗ px , i n t ∗ py ) }
{
( main )
i n t temp ; Attention ! C’est à l’appelant de fournir une adresse valide pour
i n t a=1 ,b =3;
temp = ∗px ; les valeurs de “retour”.
permuter (&a ,& b ) ;
∗px = ∗py ;
p r i n t f ( "%d %d " , a , b ) ;
∗py = temp ;
}
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  21 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  22 / 32 
Quelques exemples Quelques exemples

Ex : Max de deux entiers Ex : Copies de pointeurs

(passage en donnée/résultat, cf cours 3) Soit : int x = 1, y = 2;

void minmaxproc ( i n t ∗ pa , i n t ∗pb ) int* p = &x; int* q = &y;
{ / / s t o c k e l e m i n d a n s pa , l e max d a n s p b
i n t tmp ; Que valent x, y, p et q après :
i f ( ∗ pa>∗pb ) { p = q; *p = -1;
tmp=∗pb ;
∗pb=∗pa ;
∗pa = tmp ;
}
*p = *q; *p = -1;
}

a =42; b =12;
minmaxproc (&a ,& b ) ;
?

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  23 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  24 / 32 
 Quelques exemples Quelques exemples

Ex : Copies de pointeurs Ex : Copies de pointeurs

Soit : int x = 1, y = 2; Soit : int x = 1, y = 2;

int* p = &x; int* q = &y; int* p = &x; int* q = &y;

Que valent x, y, p et q après : Que valent x, y, p et q après :

p = q; *p = -1; p = q; *p = -1;
p et q pointent sur y, (alias !) p et q pointent sur y, (alias !)
y = -1. x est inchangé.
*p = *q; *p = -1; *p = *q; *p = -1;

? ?

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  24 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  24 / 32 
Quelques exemples Quelques exemples

Ex : Copies de pointeurs Ex : Copies de pointeurs

Soit : int x = 1, y = 2; Soit : int x = 1, y = 2;

int* p = &x; int* q = &y; int* p = &x; int* q = &y;

Que valent x, y, p et q après : Que valent x, y, p et q après :

p = q; *p = -1; p = q; *p = -1;
p et q pointent sur y, (alias !) p et q pointent sur y, (alias !)
y = -1. x est inchangé. y = -1. x est inchangé.
*p = *q; *p = -1; *p = *q; *p = -1;
*q = y = 2 est placé dans *p = x, *q = y = 2 est placé dans *p = x,
puis -1 est placé dans *p = x. y est inchangé.
? !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  24 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  24 / 32 
 Quelques exemples Quelques exemples

Et les tableaux Utilité des pointeurs

Les pointeurs peuvent servir à

passer des variables par adresse,
En C, les tableaux sont passés par adresse :
« retourner » plusieurs valeurs,
lire des données entrées au clavier scanf
Dans une expression, tout tableau unidimensionnel est traverser des tableaux (non vu ici, voir TP)
remplacé par un pointeur vers son premier élément. gérer des blocs de mémoire dynamique (Semestre 6).
implémenter des listes (chaînées) (Semestre 6)
passer des fonctions en paramètre (Semestre 6)

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  25 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  26 / 32 
Validité des pointeurs Validité des pointeurs

Le pointeur NULL

1 Schémas d’exécution - variables modifiables

NULL : valeur pointeur spéciale "vide", souvent utilisé pour dire
"non défini". C’est souvent 0 mais pas toujours.
2 Les pointeurs
Attention Son déréférencement est impossible !
3 Quelques exemples Utilisations standard :
utilisée comme valeur pour “non définie”,
4 Validité des pointeurs renvoyée par une fonction pour indiquer une erreur,
passée en argument pour indiquer qu’on n’est pas
intéressé par une valeur de retour.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  27 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  28 / 32 
 Validité des pointeurs Validité des pointeurs

Le pointeur NULL - ex Pointeurs valides et invalides

Attention ! Avant de déréférencer un pointeur par *,
assurez-vous qu’il pointe vers un objet valide !
Ex d’utilisation : Pointeurs valides :
# include < s t d l i b . h> pointeur vers une variable globale,
void d i v i s e ( i n t a , i n t b , i n t ∗ d i v , i n t ∗ rem )
{ pointeur vers une variable locale existante.
i f ( d i v ! =NULL ) ∗ d i v = a / b ;
Pointeurs invalides :
i f ( rem ! =NULL ) ∗rem = a % b ;
} pointeur NULL ou non initialisé,
pointeur en dehors des bornes d’un tableau,
Note, si p est un pointeur :
pointeur vers une variable locale détruite,
if (p) équivaut à if (p!=NULL), ⇒ ne jamais retourner un pointeur vers une variable
if (!p) équivaut à if (p==NULL). locale !

Attention : la durée de vie d’une variable–pointeur peut

dépasser celle de l’objet sur lequel elle pointe !

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  29 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  30 / 32 
Validité des pointeurs Validité des pointeurs

Exemples incorrects Exemples incorrects

void g ( i n t ∗ x ) {
∗x = 2; int ∗ f ( ) {
} i n t z = 12;
r e t u r n &z ;
i n t main ( ) { }
int ∗ z ;
g(z ); / ∗ avec −Wall : void main ( )
warning : warning : variable ’z ’ is uninitialized when used h{e r e ∗/
{ int ∗ x = f ( ) ;
int k ; ∗x = 13; / ∗ ERREUR : z n ’ e x i s t e p l u s
z = &k ; m a i s pas d ’ e r r e u r de c o m p i l a t i o n ! ∗/
g(z ); / ∗ e q u i v a l e n t a g (& k ) : g m o d i f i e r a k ∗ / }
}
g(z ); /∗ k n ’ e x i s t e plus , z est invalide
mais pas d ’ erreur de compilation ∗/ Note : l’adresse d’une variable locale change entre deux
return 0; appels d’une même fonction !
}

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  31 / 32  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6 Pointeurs 2012  32 / 32 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

6.2 Pointeurs et tableaux et chaînes de caractères

Dans ce cours nous présentons l'utilisation des pointeurs pour parcourir des tableaux et des
chaînes de caractère. Nous faisons une petite introduction à l'arithmétique des pointeurs.

Savoirs (en C)
 Utiliser des pointeurs pour parcourir un tableau unidimensionnel.
 Utiliser les fonctions de base de la bibliothèque string.h.

74/85
 Pointeurs et tableaux

Algorithmique et Programmation, IMA 3

Cours 6b : Un peu plus sur les pointeurs

1 Pointeurs et tableaux
Laure Gonnord
[Link] 2 Le cas particulier des chaînes de caractères
[Link]@[Link]

Université Lille 1 - Polytech Lille

3 Et encore ...

d’après A. Miné (ÉNS Ulm)

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  2 / 20 

Pointeurs et tableaux Pointeurs et tableaux

Les tableaux Arithmétique de pointeurs

Si p pointe sur une case d’un tableau :

p+i ou i+p pointe i cases après p
Rappel : en C, les tableaux sont passés par adresse : p-i pointe i cases avant p
(ajouter i ' se déplacer de i × sizeof(∗p) octets. . . )
I Les raccourcis +=, -=, ++, -- marchent également.
Dans une expression, tout tableau unidimensionnel est
Attention, pour faire cela, il faut :
remplacé par un pointeur vers son premier élément.
Déplacer un pointeur sur un tableau valide (déclaré,
alloué) de taille >1.
Ne pas dépasser la taille du tableau

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  3 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  4 / 20 
 Pointeurs et tableaux Pointeurs et tableaux

Comparaison de pointeurs/tableaux Pointeurs et tableaux unidimensionnels

Dans une expression, tout tableau unidimensionnel est
remplacé par un pointeur vers son premier élément.

Équivalences
Si p et q pointent dans le même tableau, on peut : tab ' &tab[0]
comparer les indices des cases : p < q, p <= q, etc. tab+i ' &tab[i]
calculer la distance en cases : p - q. *tab ' tab[0]
*(tab+i) ' tab[i]
i[tab] ' tab[i] ( !)

Exception : sizeof(tab) renvoie la taille du type de tab.

(attention si tab est un argument !)
Tableaux multidimensionnels : c’est plus complexe et
moins utilisé.
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  5 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  6 / 20 
Pointeurs et tableaux Pointeurs et tableaux

Pointeurs et tableaux unidimensionnels - Ex 1 Pointeurs et tableaux unidimensionnels - Ex 2

Parcours d’un tableau d’entiers de taille N : Parcours d’une chaîne de caractères :

void imprimeTout ( i n t t [ N ] ) { void monparcours ( char s [ N ] ) {

int i ; i n t i =0;
f o r ( i =0; i <N ; i ++) while ( i <N && t [ i ] ! = ’ \ 0 ’ ) {
p r i n t f ( "%d , " , t [ i ] ) ; p r i n t f ( "%c , " , t [ i ] ) ;
} i ++;}
}
Avec un pointeur pi (t = &t[0])
Avec un pointeur :
void imprimeToutouPas ( i n t ∗ t , i n t N ) {
int ∗ pi ; void monparcours ( char ∗ s )
f o r ( p i = t ; p i <& t [ N ] ; p i ++) {
p r i n t f ( "%d , " , ∗ p i ) ; char ∗ ch= s ; / / p o i n t e u r
} while ( ∗ ch ! = ’ \ 0 ’ ) {
int a[100]; p r i n t f ( "%c , " , ∗ ch ) ;
monparcours ( a , 3 0 ) ; ch + + ; }
}
I Attention, on n’a jamais vérifié que l’accès est valide !
I Pas “besoin” de la taille de la chaîne ...
Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  7 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  8 / 20 
 Pointeurs et tableaux Pointeurs et tableaux

Pointeurs et tableaux unidimensionnels - Ex 3 - 1/2 Pointeurs et tableaux unidimensionnels - Ex 3 - 2/2

Avec l’utilisation de l’adresse du premier élément du
La recherche dans un sous-tableau (imin + nb < N ) :
sous-tableau dans lequel on recherche :
b o o l cherche_zero ( i n t t a b [ N ] , i n t imin , i n t nb ) {
f o r ( i n t i = i m i n ; i <=( i m i n +nb ) ; i ++) { b o o l cherche_zero ( i n t ∗ tab , i n t nb )
i f ( t a b [ i ] == 0 ) r e t u r n t r u e ; {
} f o r ( ; nb >0; nb−−, t a b ++ )
return f a l s e ; i f ( ∗ t a b == 0 ) r e t u r n t r u e ;
} return f a l s e ;
}

void f ( ) void f ( ) {
{ int a[100];
int a[100]; i f ( cherche_zero (&a [ 1 0 ] , 5 ) ) ...
i f ( cherche_zero ( a , 1 0 , 5 ) ) . . . }
}
Avantage : remplace un couple tableau + indice.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  9 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  10 / 20 
Pointeurs et tableaux Le cas particulier des chaînes de caractères

Limitations des tableaux statiques

1 Pointeurs et tableaux
Du fait qu’un tableau est un pointeur constant :
On ne peut créer de tableau dont la taille est une variable 2 Le cas particulier des chaînes de caractères
du programme
On ne peut créer de tableau bidimensionnel dont les lignes 3 Et encore ...
n’ont pas le même nombre d’éléments.
I Ces opérations deviennent possibles dès que l’on manipule
des pointeurs alloués dynamiquement (malloc, Semestre 6).

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  11 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  12 / 20 
 Le cas particulier des chaînes de caractères Le cas particulier des chaînes de caractères

Chaîne de caractères Bibliothèque string

Il est possible d’utiliser les fonctions de la bibliothèque

Maintenant nous savons qu’une chaîne de caractères (tableau)
string.h :
est en fait un char* :
i n t main ( ) man 3 fgets RET
{
int i ; char *fgets(char *s, int size, FILE *stream);
char ∗ chaine ;
chaine = " chaine de c a r a c t e r e s " ; fgets() reads in at most one less than size characters from stream and
f o r ( i = 0 ; ∗ chaine ! = ’ \ 0 ’ ; i ++) stores them into the buffer pointed to by s. Reading stops after an
EOF or a newline. If a newline is read, it is stored into the buffer.
chaine ++; A '\0' is stored after the last character in the buffer.
p r i n t f ( " nombre de c a r a c t e r e s = %d \ n " , i ) ; [...]
} fgets() return s on success, and NULL on error or when end
of file occurs while no characters have been read.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  13 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  14 / 20 
Le cas particulier des chaînes de caractères Le cas particulier des chaînes de caractères

Lire une chaîne sur l’entrée standard Fonctions utiles

# define N 1024

char ∗ monfgets ( i n t s i z e ) La librairie string fournit entre autres :

{ strlen(s) retourne la taille d’une chaîne :
a s s e r t ( s i z e <N ) ; calculates the length of the string s, not
char i n p u t [ N ] ; / / p r e p a r a t i o n d u b u f f e r including the terminating '\0' character.
f g e t s ( i n p u t , s i z e +2 , s t d i n ) ; / / g e t ! strncmp(ch1,ch2) compare deux chaînes :
char ∗ resu = s t r n d u p ( i n p u t , s t r l e n ( i n p u t ) − 1 ) ; compares the two strings s1 and s2. It returns
// enleve le saut de ligne an integer less than, equal to, or greater than
zero if s1 is found, respectively, to be less
r e t u r n resu ; than, to match, or be greater than s2.
}
char ∗ resu = monfgets ( 4 ) ; / / 4 premiers chars !
p r i n t f ( "%s \ n " , resu ) ;

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  15 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  16 / 20 
 Et encore ... Et encore ...

Priorité des opérateurs

Du plus prioritaire au moins prioritaire.

1 Pointeurs et tableaux [] accès dans un tableau

++ -- incrémentation et décrémentation
2 Le cas particulier des chaînes de caractères * déréférencement de pointeur
& prise d’adresse
* / % opérateurs multiplicatifs
3 Et encore ...
+ - opérateurs additifs
== < > . . . opérateurs de comparaison
&& || opérateurs booléens
= op = opérateurs d’affectation

Exemple : *p++ signifie *(p++), pas (*p)++;

I dans le doute : mettre des parenthèses.

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  17 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  18 / 20 
Et encore ... Et encore ...

Priorité dans les déclarations Pointeurs complexes

Exemples complexes :
int** x; pointeur sur un pointeur sur un int,
Attention à la priorité de * et , dans les déclarations. *x : pointeur sur un int,
int *a,b; **x : int.
b a pour type int, pas int*. int *x[10]; tableau de 10 pointeurs sur des int,
int *a,*b; x[1] : pointeur sur un int,
a et b ont le type int*. *(x[1]) : int.
int (*x)[10]; pointeur sur un tableau de 10 int.
(inutile : on préférera un pointeur sur un élément du
tableau)

Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  19 / 20  Laure Gonnord (Lille1/Polytech) AlgoProgIMA3 Cours 6b Pointeurs++ 2012  20 / 20 
Laure Gonnord Polycopié de Programmation Structurée IMA3  2012/2013

Autres documents utiles

Cette section comprend :
 les objectifs du cours : algorithmique et C
 un poly récapitulatif de syntaxe algorithmique
 un glossaire Algo/Chinois

80/85
Département IMA / 3A (S5) Programmation Structurée 2012/2013
[Link]

Objectifs du Cours
1 Compétences attendues en Algorithmique
 Connaître la syntaxe du pseudo langage algorithmique
 Connaître les notions suivantes : les variables, les constantes, les fonctions, les actions, les
boucles tant que, les boucles pour.
 Savoir écrire précisément la déclaration d'une action et l'appel de cette action (types,
syntaxe, . . . ). Pareil pour une fonction. Savoir décrire une exécution à l'aide de schémas
d'exécution. Savoir ce qu'est la signature d'une fonction.
 Connaître les principes des tris courants (insertion, sélection, fusion). Savoir retrouver les
algorithmes en pseudocode. Savoir très rapidement écrire le tri sélection.
 Les tableaux : déclaration, initialisation, savoir parcourir un tableau avec une boucle pour,
savoir parcourir avec une boucle tant que lorsque l'on veut s'arrêter avant.
 Les matrices ou tableaux 2d : idem
 Les chaînes de caractères codées avec marqueur de n : parcours, et les algorithmes courants
(longueur, concaténation, . . . )
 Les variables modiables : utilisation à bon escient, et déclaration à l'aide des variables D
et/ou R.
 Conception/Analyse : savoir analyser un problème et le découper en petits algorithmes.
Savoir choisir entre fonction et action, et déterminer les variables d'entrée nécessaires.
 Savoir analyser son algorithme en terme de coût. Connaître le coût en moyenne des
principaux tris.

2 Compétences attendues en Programmation C

 La même chose que la partie algorithmique : variables, types, constantes, fonctions,
procédures, appels de fonctions, tableaux et matrices, structures. . .
 Booléens : savoir qu'ils n'existent pas en C en tant que tels, mais que l'on peut (et l'on
doit) utiliser stdbool.
 Pointeurs : utiliser * et & à bon escient. Utilisation des pointeurs dans le cas où l'on utilise
des paramètres modiables en algorithmique. Le parcours de tableau avec des pointeurs
n'est pas demandé, ni l'allocation dynamique.
 Syntaxe des tableaux et matrices : déclaration, accès à une case, parcours dans tous les
sens.
 Les chaînes de caractères en C. La diérence entre "a" et 'a'.
 Entrées/sorties : printf, scanf, et utilisation pour demander des informations à l'utilisateur
du programme. Utilisation de getc et getline.
 Principes généraux de compilation pratique : ce que sont les .o, .h (savoir faire un .h), les
librairies, et comment compiler à la ligne de commande ou avec un Makele. Diérence
entre compilation et exécution.
 Utiliser les fonctions données dans les librairies, par exemple dans string.h.
3 Compétences TP
et plus spéciquement en ce qui concerne le C :
 Utiliser un éditeur ecace pour éditer du C et éventuellement compiler
 Compiler, exécuter à la ligne de commande.
 Savoir lire l'énoncé, répondre aux questions posées, papier, crayon, expliquer, faire des
tests pertinents.
 Commenter, documenter.
 Savoir un peu utiliser gdb.
Département IMA / 3A (S5) Programmation Structurée 2012/2013
[Link]

Syntaxe Algorithmique
Nom Syntaxe Exemple Commentaire
Aectation ← x ← 42 x doit être déclaré
Type entier Entier x :Entier déclaration de x entier
Type réel Réel x :Réel déclaration d'un réel, en machine ce sera un ottant
Type charactère Charactère c :Charactère déclaration d'un caractère ; les constantes sont 'a', 'b', . . .
Type booléen Booléen b :Booléen déclaration d'un booléen ; les constantes sont Vrai et Faux
Type chaîne Chaîne s ← ”toto” aectation d'une chaîne, s doit être déclarée.
Tableau Vecteur Vecteur[10] d'Entiers tableau de 10 entiers indexés de 0 à 9
constante Constante Constante N : 10 déclare une constante symbolique N qui vaut 10

Tests
Si condition alors
instructions si vrai Si condition alors
Sinon instructions si vrai
instructions si faux Fsi
Fsi

Boucles
Pour i de inf à sup Faire Tq condition faire
instructions instructions
Fpour Ftq

Programme/fonction/action : exemples
Fonction fonct(c) : Entier Action monact(a,b,c)
D: c :Charactère D: a : Entier
Programme Main
.... L: s :Entier D/R: b : Entier
.... .... R: c : Charactère
.... .... ...
Retourner 0 .... ...
FProgramme Retourner s ...
FFonction FAction
 ici fonct est une fonction Caractère -> Entier :
L'unique paramètre (la donnée ) est un caractère, nommé c dans la suite de la fonction. La
variable s est locale. L'appel : resu ← f onct(d) où d a une valeur et resu est déclaré de
bon type.
 ici monact est une action à trois arguments. Les modications apportées au premier
paramètre ne sont pas enregistrées (c'est une donnée ). Par contre les modications
apportées aux paramètres 2 et 3 sont enregistrées (donnée-résultat et résultat ). Appel :
monact(a,b,c) avec a, b ayant une valeur, et c étant déclaré.
 Termes informatiques en chinois --- Programmation Structurée --
Glossaire réalisé avec l'aimable collaboration de Quanquan WANG, IMA3 en 2010/2011

Exemple Traduction

algorithme 算法

implémentation (en C) 植入，实现

variable 变量

type 类型

booléen true,false 布尔函数（真，假）

entier 12,-7 整数

réel 42.67 实数

caractère a' 字符

chaîne de caractères “toto” 字符串

expression 表达式

expression numérique 2x+56 数字表达式

expression booléenne b ou true 布尔函数表达式

affectation X := 7 赋值

calculer 计算

stocker 储存

crochet [ , ] 方括号

accolade {, } 大括号

chevron <, > 角括号

action / procédure 程序

fonction 函数

retourner 返回

paramètre 参数

paramètre d'entrée 输入的参数

 Termes informatiques en chinois --- Programmation Structurée --
Glossaire réalisé avec l'aimable collaboration de Quanquan WANG, IMA3 en 2010/2011

paramètre de sortie 输出的参数

appel de fonction 函数的调用

passage de paramètres par valeur 按值传递参数

vecteur, tableau [1|2|-2| … ] 向量，数组

indice 下标，标号

case 案例，个案

accès en lecture 可读

accès en écriture 可写

pointeur 指针

mémoire 内存

Allocation / allouer 配置，给予（开辟空间）

adresse 地址

complexité, coût d'un programme 复杂程度，程序的成本

algorithme linéaire 线性算法

algorithme quadratique 二次算法

algorithme polynômial 多项式算法

algorithme exponentiel 指数算法

déboguer 调试

tester 测试

compiler 编译

éditer un fichier 编辑文件