Algo 1&2 Complet

Chapitre-2 Algorithmique et programmation C
Les Variables, les pointeurs, les constantes,

Fonctions Entrés/Sortie
Les algorithmes
 Un algorithme est un ensemble de règles logiques et
chronologiques qu’on doit suivre pour aboutir à la
résolution d’un problème particulier.
 Ces règles sont constituées d’un nombre fini d’opérations
élémentaires (Arithmétique & Logique).
 Ces opérations seront exécutées dans un ordre bien
déterminé.
 Un algorithme peut être assimilé à un raisonnement que
l’on peut traduire avec un langage que toute personne
peut comprendre :
o LDA : Langage de Description d’Algorithme

Les algorithmes
 Le LDA n’est pas un langage informatique.
 Le programme informatique est à la traduction du LDA à

un autre langage compréhensible pour la machine
(Pascal, Visual Basic, C, C++, C#, Java…)
Langage traduisant la pensée de
manière compréhensible pour toute
personne : Algorithme
LDA
……
……
……
Raisonnement logique Programme

et chronologique C, C++,…
Langage traduisant le LDA de

manière compréhensible pour
l’ordinateur : Programme
Programme C, C+
Langage Machine Compilateur
+
Exemple 1. Recherche d’un mot dans un dictionnaire
Méthode 1 : Recherche séquentielle

a. Début algorithme.
b. Retenir (saisir, lire) le mot à rechercher.
c. Ouvrir le dictionnaire à la première page.
d. Tant que le mot ne se trouve pas sur la page courante
et la page courante n'est pas la dernière exécuter
l'étape e) sinon passer à l'étape f).
e. Passer à la page suivante.
f. Si le mot s'y trouve lire la définition sinon ce mot ne
se trouve pas dans le dictionnaire.
g. Fin de l'algorithme.
Exemple 1. Recherche d’un mot dans un dictionnaire
Méthode 1 : Recherche dichotomique
a. Début algorithme.
b. Retenir (saisir, lire) le mot à rechercher.
c. Ouvrir le dictionnaire à la page du milieu.
d. Tant que le mot ne se trouve pas sur la page courante et
la page courante n'est pas la dernière exécuter l'étape e)
et f) sinon passer à l'étape g).
e. Si le mot se trouve dans la partie droite ouvre la page du
milieu de cette partie
f. Sinon ouvre la page du milieu de la partie gauche
g. Si le mot s'y trouve lire la définition sinon ce mot ne se
trouve pas dans le dictionnaire.
h. Fin de l'algorithme.
• Conclusion
– Plusieurs algorithme peuvent donner le

même résultats
– Evaluation des algorithmes en fonction du
temps d’exécution et de la mémoire utilisée
* Structure d’un
Algorithme
Déclaration du nom algorithme nom de l’algorithme
de l’algorithme
const
liste des constantes
Déclaration des var

constantes, des variables liste des variables
et des structures
struct
liste des structures
début algorithme
action 1 // commentaire 1
action 2 // commentaire 2
Le corps de l’algorithme .
.
.
action n // commentaire n
fin algorithme
* Structure d’un
Nom de l’algorithmeAlgorithme
:
o Il permet tout simplement d’identifier un algorithme
parmi d’autres.
Les déclarations :
o C’est une liste exhaustive de variables utilisées et
manipulées dans le corps de l’algorithme.
Le corps de l’algorithme :
o Dans cette partie de l’algorithme, sont placées les
tâches à exécuter (instructions, opérations, …).
Les commentaires :
o Pour permettre une lecture plus aisée et plus
compréhensive de l’algorithme
* Les
Déclarations
 Les Constantes :
o Elles représentent des chiffres, des nombres, des caractères, des
chaînes de caractères, … dont la valeur ne peut pas être modifiée au
cours de l’exécution de l’algorithme.
 Les Variables :
o Elles peuvent stocker des chiffres des nombres, des caractères, des
chaînes de caractères,… dont la valeur peut être modifiée au cours de
l’exécution de l’algorithme.
 Les Tableaux :
o Elles permettent de rassembler plusieurs valeurs ou constantes de
même type sous un même identificateur.
 Les Structures :
o Elles permettent de rassembler plusieurs valeurs ou constantes de
types différents sous un même identificateur, on parle également
d’entités ou d’objets.
* Les Déclarations des variables et des
constantes
Pour pouvoir accéder aux données, le programme (quel que soit le
langage dans lequel il est écrit) fait usage d’un grand nombre de
variables de différents types.
Une VARIABLE possède :
Un nom (identificateur) : Un variable apparaît en programmation sous

un nom de variable.
Un type : Pour distinguer les uns des autres les divers contenus possibles,
on utilise différents types de variables (entiers, réels, chaîne de
caractères..).
Une valeur : Une fois la variable définie, une valeur lui est assignée, ou
affectée.
Une adresse : C’est l’emplacement dans la mémoire de l’ordinateur, où
est stockée la valeur de la variable.
* Langage de programmation C
Le langage « C » est le plus utilisé dans la
programmation. Des langages informatiques plus modernes
comme C++, Java et PHP reprennent des aspects de C.
Structure générale d’un programme C

Un programme C comporte une série d’instructions structurées en bloc, il
peut être constitué de plusieurs sous-programmes ou fonctions.
* Structure générale d’un programme C
La fonction principale main()
Un programme C comporte toujours une fonction principale dans

laquelle on peut appeler les autres fonctions définies dans le fichier ou
bien prédéfinies dans la bibliothèque du langage.
La syntaxe de cette fonction principale est donnée par :
main(void)
{
……
}
C’est une fonction sans argument en général d’où le mot void (rien) entre
les parenthèses.
Les Inclusion de source #include<nonfichier.h>
Pendant l’exécution d’un programme C, Le compilateur a besoin d’être

informé sur :
 les structures de données et de variables externes
 l’aspect des fonctions prédéfinies utilisées dans le programme.
Ces informations sont contenues dans des fichiers d’extension « .h ».

Ces fichiers doivent être introduits dans le programme principal à travers la
directive « #include ».
Sa syntaxe est la suivante :
#include <nomfichier.h>
La directive #include permet d’incorporer dans le fichier source le code du

fichier <nomfichier.h>
Nom fichier Rôle

<math.h> pour utiliser les fonctions mathématiques usuelles
<stdio.h> pour utiliser les fonctions d’entrées/sortie « printf() »
<stdlib.h> Pour la gestion de la mémoire, conversions et les fonctions système
<string.h> Pour manipuler des chaines de caractère.
<conio.h> Pour utiliser les fonctions de contrôle l’affichage à l’écran : « getchar() »
<complex.h> Pour manipuler les nombres complexes
<ctype.h> pour utiliser les fonctions de manipulation des caractères (fonction test) :
« islower() » : test si un caractère est majuscule.
#include <stdio.h>
main(void)
{
printf("bonjour tout le monde\n");
}
Les variables et les constantes :
Les constantes et les variables sont définies dans la partie déclarative
par deux caractéristiques essentielles, à savoir :
 L’ identificateur :
o Il représente le nom de la variable, de la constante ou de la
structure. Il est composé généralement de lettres mais peut
également contenir et de chiffres.
 Il ne doit pas commencer par des chiffres
 Il ne doit pas contenir d’espaces, de caractères de
ponctuation ou de caractères accentués.
Le type :
o Il représente la nature de la variable ou de la constante (entier,
réel, booléen, chaîne de caractères…)
Les variables :
Une variable est caractérisée par :
 Un nom : Une variable apparait en programmation sous un nom de

variable.
 Un type : On utilise différents types de variables (entiers, réels, chaine

de caractères …).
 Une valeur : Une fois la variable définie, une valeur lui est assignée, ou
affectée.
 Une adresse : C’est l’emplacement dans la mémoire de l’ordinateur, ou

est stockée la valeur de la variable.
Les Types des variables :
Toute données, quelle que soit sa nature, devra être codée sous forme
binaire
Le type de donnée permet de donner un sens à une données qui est
stockée dans un emplacement mémoire d’adresse N.
Cette données peut représenter un entier

naturel, un entier signé, un caractère, un réel ou .
une instruction mémoire.
.
On doit connaitre la manière dont chaque N 10001101
donnée était codée c-a-d son type
C manipule deux types de nombres:
Les entiers et les nombres flottants
Les Types des variables : Les Entiers
Sont désigné par « int ». Ils peuvent être affectés de deux types
d’attributs : un attribut de précision et un attribut de représentation.
Les attributs de précision sont «short » et « long ».

L’attribut de représentation « unsigned »
Type de données Type de codage Mémoire occupée

int (entier signé) Complément à 2 4 octets
short int 2 octets
unsigned int (entier non signé) Binaire pur 4 octets
Les Types des variables : Les caractères
Sont désigné par « char ». Il contient le code de n’importe quel caractère

de l’ensemble des caractères utilisé sur la machine.
Le codage utilisé est le codage ASCII. À chaque caractère correspond un
codage binaire d’un entier.
Donc en « C » si a est « char » on peut effectuer l’opération a+1
main(){
Ce programme donnera le caractère
char x, y;
suivant de ‘a’
x=‘a';
y=x+1;}

char (caractère) ASCII 1 octets
Les Types des variables : Les flotants
Il existe trois types de flottants correspondants à trois précisions possibles.
En allant de la précision la plus faible vers la plus forte, on dispose des
types float, double et long double.

float (flottant réel) Normalisation IEEE 4 octets
Double (flottant double) 8 octets
long double (flottant double long) 12 octets
sizeof(type) : Fonction permettant de renvoyer la taille occupée dans

la mémoire d’un certain type de données.
* Les types de variables en langage C
Plage de valeurs
Type de donnée Signification Taille (en octets) acceptée
char Caractère 1 0 à 255

short int Entier court 2 -32 768 à 32 767
unsigned short int Entier court non signé 2 0 à 65 535
2 (sur processeur 16 bits) -32768 à 32767

int Entier 4 (sur processeur 32 bits) -2147483 648 à
2147483647
2 (sur processeur 16 bits) 0 à 65 535

unsigned int Entier non signé
4 (sur processeur 32 bits) 0 à 4 294 967 295
-2 147 483 648 à 2 147

long int Entier long 4 483 647
unsigned long int Entier long non signé 4 0 à 4 294 967 295
float Flottant (réel) 4 3.4*10-38 à 3.4*1038

double Flottant double 8 1.7*10-308 à 1.7*10308
long double Flottant double long 12 3.4*10-4932 à 3.4*104932
Les constantes :
Les constantes sont des variables qui vont prendre une valeur fixe
Variable déclarée avec le qualificateur «const »
Ce sont des variables dont la valeur n'est pas modifiable pendant
l’exécution du programme. Le qualificateur « const » permet de protéger
la valeur de la variable.
#include <stdio.h> #include <stdio.h>

main() main()
{ {
int b=8; const int b=8;
b=b+2; b=b+2;
printf("b= %d", b); printf("b= %d", b);
} }
Erreur b est protégé
Read only variable ‘b’
Les constantes entières
Elles peuvent s'exprimer
 en notation décimale: 123, -123, etc...
 en notation octale avec un 0 en première position: 0123
 en notation hexadécimale avec les caractères 0x ou 0X en première
position : 0x1b, 0X2c, 0X1B,
Différents types des constantes peuvent être définis en ajoutant des suffixes.
forme de la constante liste de types
pas de suffixe, décimal int, unsigned int, long int, unsigned long int
pas de suffixe, octal ou hexadécimal int, unsigned int, long int, unsigned long int
suffixé par u ou U unsigned int, unsigned long int
suffixé par l ou L long int, unsigned long int
suffixé par (u ou U) et (l ou L) unsigned long int
Les constantes flottant
Une constante flottante se présente sous la forme d'une partie entière, un

point qui joue le rôle de virgule, une partie fractionnaire, une des deux
lettres e ou E, le signe + ou - suivi de la valeur absolue de l'exposant
#include <stdio.h>
main()
{
double b=12.345e123;
b=b+2;
printf("b= %e", b);
}
Les constantes caractère
Les constantes de type caractère se note entre apostrophes: 'a' '2'
#include <stdio.h>
main(void)
{
char b='a';
b=b+5;
printf("b= %c\n", b);
}
Les constantes caractère
Les caractères non imprimables
\n nouvelle ligne
\t tabulation horizontale
\v tabulation verticale
\b retour d'un caractère en arrière
\f saut de page
\a beep
\' apostrophe
\" guillemet
Les pointeurs
Un pointeur est une variable qui stock une adresse mémoire. Cette
adresse peut être celle d’une autre variable d’un certain type ou celle d’un
espace mémoire alloué dynamiquement.
Un pointeur typé permet de pointer une adresse d’un espace
mémoire ou on peut stocké des valeurs d’un certain type.
Un pointeur générique permet de pointer une adresse d’un espace
mémoire ou on peut stocké des valeurs de n’importe quel type.
La syntaxe de déclaration d’un pointeur est :
char *p1
type *identificateur ; int *P2
Double *p3
Les pointeurs Opérateur « & »
L’opérateur « & » appliqué à une variable délivre l’adresse de celle-ci ; cette

adresse pourra être affectée à une variable de type pointeur. On peut écrire
par exemple :
Main{
int i;
int *pi; // pi pointeur vers un int /
pi = &i; / /le pointeur pi repère la variable i /
}
Les pointeurs (l’Opérateur d’indirection « * »)
« * » utilisé en opérateur préfixé est un opérateur d’indirection qui, appliqué
à une valeur de type pointeur, délivre la valeur stocké dans l’adresse
pointée.
main()
{
int i=3, j;
int *pi;
pi = &i; // on affecte l’adresse de i au pointeur « pi »/
*pi = 2; //on stocke la valeur 2 dans la zone mémoire dont l’adresse est
// donnée par pi
j = i + 1;/ on ajoute 1 à la valeur de i dont l’adresse est pointée par « pi ».}
L’opérateur * peut être opérateur de multiplication ou opérateur
d’indirection. (*x * *y)
Les pointeurs (l’Opérateur d’indirection « * »)
#include <stdio.h>
#include <stdlib.h>
main()
{
int i;
int *pi;
i=5;
pi = &i;
*pi = 2;
printf("i=%d", i);
system("pause");}
Les pointeurs
Type *nom_pointeur
Donc lorsqu’on déclare un pointeur on peut identifier trois objets
différents :
&nom_pointeur : contient l’adresse mémoire propre au pointeur
nom_pointeur : contient l’adresse mémoire pointée
*nom_pointeur : contient la valeur contenue dans l’adresse pointée
Les doubles pointeurs
Type **nom_pointeur
Un double pointeur est une variable qui stock une adresse mémoire d’un
pointeur. Donc le contenue de l’adresse pointée est une adresse mémoire.
Les doubles pointeurs
int i=3, j=9;
int *P, **G;
P=&i;
G=&P;
*G=&j;
**G=i+1;
printf("&i = %d &j = %d\n", &i, &j);
printf("P = %d\n", P);
printf("i = %d j = %d\n", i, j);
&j = 60FF04 j = 49
G = &P *G = P = &i = 60FF08 **G=*P= i = 3

Arithmétique sur les pointeurs
La valeur d'un pointeur étant un entier, on peut lui appliquer un certain nombre
d'opérateurs arithmétiques classiques
Toutes les opérations avec les pointeurs tiennent compte automatiquement du

type et de la grandeur des objets pointés.
 l'addition d'un entier à un pointeur. Le résultat est un pointeur de

même type que le pointeur de départ ;
 la soustraction d'un entier à un pointeur. Le résultat est un pointeur
de même type que le pointeur de départ ;
Arithmétique sur les pointeurs
#include <stdio.h>
#include <stdlib.h>
main()
{
int *p1, *p2, a;
p1=&a;
p2=p1+2; // Equivalent à P2 = P1 + 2*sizeof(int)
printf("p1=%x\n", p1);
printf("p2=%x\n", p2);
}
Allocation Dynamique de la mémoire
Lorsqu’on déclare un pointeur il est initié par NULL :
Type *P = NULL (Si P==0 Alors Ecrire(« p ne pointe vers aucun objet »)
Après on peut lui affecter :

 l’adresse d’une autre variable déjà déclarée
 l’adresse du premier octet d’une zone mémoire réservée au cours de

l’exécution du programme afin de stocker une valeur d’un certain type.
Allocation Mémoire (Memory ALLOCation malloc())

Allocation Dynamique de la mémoire: Fonction malloc()
Appartient à la librairie standard stdlib.h
La syntaxe :
(Type*)malloc(sizeof(Type))
Cette fonction retourne un pointeur d’un certain type (Type *) pointant vers
un objet de taille sizeof(Type) octets.
#include <stdlib.h> On peut donc affecter directement

une valeur entière à *p puisqu’on a
int *p;
réservé 4 octets à l’aide de la
p = (int*)malloc(sizeof(int)); fonction malloc().
#include <stdlib.h>
main()
{
int i = 3;
int *p=NULL;
p = (int*)malloc(sizeof(int));
*p = 6;}
#include <stdlib.h>
main()
{
int i = 3;
int *p=NULL;
p = &i;
*p = 6
}
Allocation dynamique d’un espace pour plusieurs objets contigus en
mémoire
#include <stdio.h>
#include <stdlib.h>
=i
main()
{
p+1
int i = 3; =j
int j = 6;
int *p;
p = (int*)malloc(2 * sizeof(int));
*p = i;
*(p + 1) = j;
}
Les opérateurs et les expressions
L'opération par laquelle on attribue une valeur à une variable s'appelle

affectation. Dans un algorithme (pseudo-code) "←".
Dans le langage C par le signe " = ".
#include <stdio.h>
main()
{ i : variable (Adresse, type , valeur)
int i;
i = i*2+5; i*2+5 : expression (type, valeur)
printf("b= %d", i);
}
Les opérateurs Arithmétique, de comparaison & logique
Arithmétique Comparaison
Opérateur C Opérateur C
Addition + Supérieur stricte >
Soustraction - Inférieur stricte <
Multiplication * Supérieur ou égal >=
Division / Inférieur ou égal <=
Modulo (reste de la Egal ==
%
division entière) Différent !=
Logique
Opérateur C
ET Logique &&
OU Logique ||
Négation Logique !
*Structure générale d’un programme C
Les opérateurs Arithmétique, de comparaison & logique
Priorité croissante de bas vers le haut
Opérateur C
Opérateur de multiplication *
Opérateur de division /
Opérateur d'addition +
Opérateur de soustraction -
Opérateur d'infériorité stricte <
Opérateur de supériorité stricte >
Opérateur d'infériorité ou d'égalité <=
Opérateur de supériorité ou
>=
d'égalité
Opérateur d'égalité ==
Opérateur d'inégalité !=
Opérateur et logique ET &&
Les Opérateurs d’incrémentations & de décrémentation
++ incrémentation
-- décrémentation
On dit que ++ est :
- un opérateur de pré incrémentation lorsqu'il est placé à gauche de la variable
- un opérateur de post incrémentation lorsqu'il est placé à droite de la variable
a++; a = a+1;
b = a++; b = a;
a = a+1;
b = ++a; a = a+1;
b = a;
Les Opérateurs d’incrémentations & de décrémentation
#include <stdio.h> #include <stdio.h>

int main() int main()
{ {
int a, b, c; int a, b, c;
a = 5; a = 5;
b = a + 4; b = a + 4;
b = a++ - 7; b = ++a - 7;
b = a - b - 7; b = a - b - 7;
printf("a= %d\n", a); printf("a= %d\n", a);
printf("b= %d\n", b); printf("b= %d\n", b);
return(0); return(0);
} }
a=6 b=1 a=6 b=0

Les opérateurs d’affectation élargie
C dispose d'opérateurs encore plus puissants.
i += k (i = i + k ) #include <stdio.h>
i -= k (i = i – k) main()
a *= b (a = a*b ) {
a /= b (a = a/b ) int a, b, c;
a %= b (a = a%b ) a = 5;
b = 2;
a += 4;
b *= a;
b = a++ - 7;
b += a - 7;
a %= b;
printf("a= %d\n", a);
a=0 b=5 printf("b= %d\n", b);
system("pause");
}
Les fonctions d’entrée et sortie (printf() et scanf())
représentation à partir Scanf() représentation

d’une chaîne de caractères manipulable par la
(vision humaine) Printf() machine (vision machine),
Pour réaliser ces transformations ces fonctions sont guidées par des

formats qui décrivent le type des objets manipulés et la
représentation en chaîne de caractères cible.
Par exemple, un format du type %x signifie d’une part que la variable

manipulé ou représenté est de type entier et d’autre part que la chaîne
de caractères qui la représente est exprimée en base 16 (hexadécimal).
Les fonctions d’entrée et sortie (printf()
Le premier argument une chaîne de caractères qui spécifie à la fois

 des caractères à afficher tels quels
 des "codes de format" repérés par % (tel que %c, %d ou %f) et qui
précisent le type de l'information à afficher.
L'appel de printf se présente comme ceci :
printf (‘’format’’, liste_d'expressions )
%d entier décimal
%f réel
%e Réel flottant
%c caractère (1 seul)
%s chaîne de caractères
Les fonctions d’entrée et sortie scanf()
D'une manière générale, l'appel de scanf se présente ainsi :

scanf(« format », liste d’adresses)
Les fonctions d’entrée et sortie scanf()
Les fonctions d’entrée et sortie getchar() et putchar()
"getchar()" fonction sans paramètre qui « capte » la valeur d’un seul caractère
x=getchar() joue le même rôle que : scanf(« %c », &x).
"putchar()" fonction écrit le caractère passé en argument sur la sortie standard

(l'écran). Le paramètre à placer entre les () doit être de type caractère.
putchar(x) joue le même rôle que : printf(« %c », x)

Occupation mémoire
Chaque octet dans la mémoire

est repéré par un numéro écrit
en hexadécimal.
Chaque donnée va être repérée

par son adresse qui représente
le numéro de son premier
octet.
Occupation mémoire : Alignement des données
Pour augmenter leurs performances, les processeurs sont souvent reliés à
la mémoire vive par un bus de données plus large que la granularité de
leur adressage (ensemble des bits adressable).
Données de même type
Dans ce cas les données seront bien aligner sur chaque emplacement.
#include <stdio.h> Après exécution on trouve :

main()
{int a, b, c, d; &a=28FF44
printf("adresse de a = %X\n",&a); &b=28FF40
printf("adresse de b = %X\n",&b); &c=28FF3C
printf("adresse de c = %X\n",&c); &d=28FF38.
printf("adresse de d = %X\n",&d);
system("pause");}
L’alignement de ces données dans une mémoire de 64 bits est la

suivante :
Octet 0 Octet 1 Octet 2 Octet 4 Octet 5 Octet 6 Octet 7 Octet 8

28FF38 d c
28FF40 b a
Cas des données de différents types
nécessaire, de laisser des trous entre elles afin qu'elles soient toutes bien
alignées.
L’ordre appliqué dans la séquence de déclaration des variables va
influencer sur la quantité totale de mémoire utilisée.
main()
{int a, b;
double x, y, z;
}
28FF28 z
28FF30 y
28FF38 x
28FF40 b a
Cas des données de différents types main()
{double x;
int a;
double y;
int b;
double z;

28FF20 z
28FF28 b
28FF30 y
28FF38 a
28FF40 x
Structures de contrôles
 La structure linéaire Traitement 1
Traitement 2
 se caractérise par une suite d’actions
à exécuter dans l’ordre où elles sont énoncées Traitement 3
Traitement 4
 Les structures de contrôle
 Permettent de contrôler l’exécution d’une suite

d’instructions
o Structures de contrôle alternatives
o Structures de contrôle répétitives

* Les structures
Alternatives
 Une structure alternative offre la possibilité de donner des

issues différentes à la poursuite d’un algorithme.
 Ces issues s’excluent mutuellement.
 On peut rencontrer plusieurs formes de structures
alternatives :
* Les structures
Alternatives
 Forme alternative réduite :
 Contrôle d’un seul bloc d’instruction
 Dans cette structure, l’exécution du traitement T2 ne dépend
que la réalisation de la condition qui le précède :
Traitement 1
si la condition est si la condition n’est pas
Si Vrai vérifiée les traitements
vérifiée les traitements Condition
se font dans cet ordre : se font dans cet ordre :
(T1 T2  T3). Si Faux (T1 T3).
Traitement 2
Traitement 3
* Les structures
Alternatives
 Forme alternative complète :
 Contrôle de plusieurs bloc d’instruction
 Dans cette structure, l’exécution de l’un des deux
traitements distincts possibles T2 et T3 ne dépend
que la réalisation de la condition qui les précède :
Traitement 1
Si Vrai Si Faux
si la condition est Condition si la condition

vérifiée les n’est pas vérifiée
traitements se les traitements se
font dans cet Traitement 2 Traitement 3 font dans cet
ordre : ordre :
(T1 T2  T4). (T1 T3  T4).
Traitement 4
* Les structures
Alternatives
Forme réduite
La structure SI ... ALORS….FIN SI

Langage C
IF ( <condition> )
{
[<bloc d'actions-1>]
}
[<bloc d'actions-2>]
 Le bloc d’actions 1 est exécuté seulement au cas où la condition

prend la valeur Vrai. Dans le cas contraire le programme passe
directement le bloc 2 .
 Avec cette structure on ne peut contrôler qu’un seul bloc d’action
* Les structures
Alternatives
Forme complète
La structure SI ... ALORS…SINON….FIN SI
IF ( <condition> )
{
[<bloc d'actions 1>]
}
ELSE
{
[<bloc d'actions 2>]
}
 Au cas où la condition est vraie seul le bloc d'instruction-1 est

exécuté. Dans le cas contraire seul le bloc d'instructions-2 est
exécuté.
 Avec cette structure on peut contrôler plusieurs bloc d’action
* Les structures
Alternatives
Forme complète
Lorsqu’il y a ambiguïté sur la structure « if » dont dépend une partie

else, l’ambiguïté est levée en faisant dépendre le « else » de l’instruction
« if » la plus proche.
if (a > b)
if (a > b) {
if (c < d) if (c < d)
u = v; u = v;
else }
i = j; else
i = j;
* Les structures
Alternatives

* Les structures
Alternatives Vrai
Si Cond 1
TA Faux TAT1TB
T1
Vrai
Si Cond 2
Faux TAT2TB
T2
Vrai
Si Cond n
Faux TATnTB
Tn
Aucune Cond
TATn+1TB
T n+1
TB
* Les structures
Alternatives
if <condition1>
{Traitement 1;}
else { if <condition1>
if <condition2> {Traitement 1;}
{Traitement 2;} else if <condition2>
else { {Traitement 2;}
if <condition3> else if <condition3>
{Traitement 3;} {Traitement 3;}
else { else if <condition4>
if <condition4> {Traitement 4;}
{Traitement 4;} else
else { {Traitement 5;}
Traitement 5;
}
}
}
}
* Les structures
Alternatives
Structure de choix multiple (selon que)
Au lieu de faire des « Si » imbriqués ou des Sinon Si, il suffit d’indiquer
quoi faire quand telle ou telle valeur d’une expression est rencontrée. En
algorithmique
switch(variable)
Le mot clé « break » indique la
{
sortie de la structure
case valeur 1 : liste intruction; break;
conditionnelle.
Le mot clé « default » précède
la liste d'instructions qui sera
.
exécutée si l'expression n'est
.
jamais égale à aucunes valeurs
.
des « case ».
case valeur n : liste intruction;break;
default: liste intruction;
}
* Les structures
Alternatives
Forme alternative : (Cas des conditions non disjointes)
contrôle deux traitements (T et T’)
 dans ce cas on va combiner les conditions Ci avec les
opérateurs logiques (AND, OR, XOR).
 Exemple :
If (Cond1 && Cond2 && Cond3 && ……&& Condn)

{trairement 1;}
Else
{trairement 2;}
* Les structures
Alternatives
Forme alternative multiple : (Cas des conditions non disjointes)
Contrôle de plusieurs traitements
 dans ce cas on va imbriquer les structures alternatives.
 Exemple :
* Les structures
Alternatives
Vrai
Si C1
TA Si Cond 2 Vrai
Si C2
Vrai
Faux
Si C3
Faux
Faux
Vrai
Si Cn
Aucune Cond Faux

Tn
T n+1
T’n
T’3
T’2
TB T’1
* Les structures
if <condition1> Alternatives
if<condition2>
if <condition3> Tn : Si C1 AND C2 AND …… AND Cn
.
.
if <condition(n)>

{Traitement n}
else
{Traitement n’}

.
.

else
{Traitement 3’}
else
{Traitement 2’}
else
{Traitement 1’}

Si (a=0) AND (b=0) AND (c=0) alors «la solution est IR »
Si (a=0) AND (b=0) AND (c#0) alors «impossible»
Si (a=0) AND (b#0) alors x1  -c/b
Si (a#0) alors calcul de Delta

#include <math.h>
main(){ {
float a, b,c; delta=b*b-4*a*c;
float delta; printf("DELTA=%f\n", delta);
printf("resolution de l'eq if (delta>0)
ax²+bx+c=0\n"); {
printf("a="); printf("la solution est:%f\n", (-b-
scanf("%f", &a); sqrt(delta))/2*a);
printf("b="); printf("la solution est:%f\n", (-
scanf("%f", &b); b+sqrt(delta))/2*a);
printf("c="); }
scanf("%f", &c); else if (delta == 0)
if (a==0) printf("la solution est:%f\n",
if (b==0) -b/(2*a));
if (c==0) else
printf("la solution est : IR"); printf("pas de solution dans IR");
else }
printf("résolution impossible");
else
printf("la solution est : %f", -c/b);
else
Structures de contrôle itératives
Les structures itératives permettent de répéter l’exécution d’un

ensemble d’instructions une ou plusieurs fois.
Ces structures sont regroupées sous deux grandes familles

selon si : le nombre de répétitions est connu ou pas.
Nombre Nombre
connu de inconnu de
répétitions répétitions
Cas ou le nombre de répétition est connu :
Dans cette structure, la sortie de la boucle d’itération

s’effectue lorsque le nombre souhaité de répétition est
atteint.
On utilise donc une variable d’itérations caractérisée par :
• sa valeur initiale,
• sa valeur finale,
• son pas de variation.
Cas ou le nombre de répétition est connu :
Faire la somme de N valeurs

int V, S, N,i;
Var V, S entiers S = 0;
S0 Scanf(« %d », &N);
Lire (V) for (i=1; i<=N; i++)
SS+V {
Lire (V) Scanf(« %d », &V);
SS+V S=S+V
Lire (V) }
SS+V Printf(‘’S= %d’’, S)
Lire (V)
SS+V
.
.
.
Afficher (S)
Pour….allant….suivant
 Si la valeur finale de l’indice est inférieure à sa valeur

initiale le pas de variation est négatif, la structure est
dite «décroissant »
 dans le cas contraire, le pas est positif et la
structure est dite «croissant »
i0 < i f
For(i=i0; i<=if; i++) For(i=if; i>=i0; i--)
{ {
. .
. .
} }
Pseudo - code Language C

Pour i Vi à Vf [pas p] for(i = Vi ; i <= Vf ; i = i + 1)
[<bloc d’actions >] {
Suivant i [<bloc d’actions >]
}
Le bloc d'instructions est exécuté un nombre de fois connu à

l’avance contrôlé par un compteur allant de la valeur Vi
(valeur initiale) à la valeur Vf(valeur finale).
Attention :
le traitement ne doit pas modifier la variable itérative (compteur)
Exemples Pour….allant….suivant
Cet algorithme fait la somme d’un certain nbre de valeurs saisies)
Pseudo - code Language C
Var i, S, var : entiers int i, S, var;
S0 S = 0;
Pour i allant de 0 à 3 for (i=0; i<=3; i++)
Afficher ("var =" ) {
Lire (var) printf("var =");
S  S + var scanf("%d« , &var);
Suivant i S = S + var;
Afficher("La somme est :", S) }
Afficher(i) printf("la somme est :%d", S);
int i, S, var; SIMULATION

S = 0;
for (i=0; i<=3; i++) i=0 var=2 S=0+2 2
{ i=1 var=-3 S=2-3 -1
printf("var ="); i=2 Var=4 S=-1+4 3
scanf("%d",&var);
S = S + var; i=3 Var=-8 S=3-8 -5
} i=4 Arrêt des itérations
printf("la somme est :%d", S);
EN MEMOIRE
i=4 S = -5
int A,B,C ; A=6; B=4; C=-2

A=6; itération Test logique A=6 B=4 C=-2
B=4; (A>B)
C = -2; i=1 Vrai 6-2= 4 -2 -2
for(i=1; i<= 5; i++)
i=2 Vrai 4-2 = 2 -2 -2
if (A > B){
A = A + C; i=3 Vrai 2-2 = 0 -2 -2
B = C;} i=4 Vrai 0-2 = -2 -2 -2
Else{ i=5 Faux -2 -2+2 = 0 0
B = B – C;
i=6 Arrêt des itérations
C = B;
}
printf(‘’A=%d’’, A); En mémoire
printf (‘’B=%d’’, B); i=6 A=-2 B=0 C=0
printf (‘’C=%d’’, C);
Pour….allant….suivant
Cas des boucles imbriquées
Pseudo - code Visual Basic

Pour i allant de Vi à Vf [pas p] for(i = Vi ; i <= Vf ; i = i + 1)
{
Pour j allant de Wi à Wf [pas p] for(j = Vi ; j <= Vf ; j = j + 1)
Suivant j [<bloc d’actions >]
}
}
Suivant i
Int S, i; j;
j=1 j=2 j=3
S  0; i=1 S=0+1+1=2 S=2+1+2=5
i=2 S=5+2+1=8 S=8+2+2=12
for(i=1; i<=3; i++)
i=3 S=12+3+1=16 S=16+3+2=21
{
for(j=1; j<=2; j++) i=4 Arrêt des itérations
{S = S + i + j}
}
EN MEMOIRE
printf (“la somme est %d”, S)
i=4 S = 21
j=3
Cas ou le nombre de répétition est inconnu :
While
 Dans cette structure, la sortie de la boucle d’itération

s’effectue lorsqu’une condition n’est plus vérifiée.
 Tant que la condition est vérifiée on répète l’exécution du
bloc d’instruction contrôlé
 Le nombre des itérations est donné après la sortie de la
boucle
Tant que …. faire
Pseudo - code Langage C

i  Vi i = i0
Tant que <condition> faire While <condition>
i  i+1 [<bloc d’actions >]
Fin tant que i++;
}
 Dans ce cas la vérification de la condition se fait avant

l’exécution du bloc d’instruction
 Le bloc d’instruction peut ne jamais être exécuté

Exemples Tant que …. faire
Cet algorithme fait la somme des valeurs saisies, arrêt lorsque var = -1)
Language C
int S, var;
i = 1;
S = 0;
printf("saisir la valeur", i);
scanf("%d",&var);
while (var!=-1)
{
S = S + var;
i = i + 1;
printf("saisir la valeur %d", i);
scanf("%d",&var);
}
printf("la somme est :%d",S);
printf("le nbre de valeur est :%d",i-1);
Tant que …. faire
int S, var; SIMULATION

i = 0; var=2 i=1 S=0+2 2
S = 0;
printf("saisir la valeur", i); var=-3 i=2 S=2-3 -1
scanf("%d",&var); Var=4 i=3 S=-1+4 3
while (var!=-1) Var=-8 i=4 S=3-8 -5
{
Var=-1 Arrêt des itérations
S = S + var;
i = i + 1;
printf("saisir la valeur", i); EN MEMOIRE
scanf("%d",&var); i=4 S = -5
}
printf("le nbre de valeur est :%d",S);
Comparaison boucles pour et tant que
• Implicitement, l’instruction for:

 initialise un compteur
 incrémente le compteur à chaque pas
 vérifie que le compteur ne dépasse pas la borne
supérieure
• Explicitement, l’instruction While il faut
 initialiser un compteur {amorçage}
 incrémenter le compteur à chaque pas {relance}
 vérifier que le compteur ne dépasse pas la borne
supérieure ou une condition est vérifiée{test de
boucle}
Cas ou le nombre de répétition est inconnu :
Do …..While
 Dans cette structure, la sortie de la boucle d’itération

s’effectue lorsqu’une condition n’est plus vérifiée.
 Tant que la condition est vérifiée on répète l’exécution du
bloc d’instruction contrôlé
 Le nombre des itérations est donné après la sortie de la
boucle
Répéter …….tant que
Pseudo - code Visual Basic

i  Vi i=i0
Répéter do
i  i+1 [<bloc d’actions >]
Tant que <condition> i=i+1
}
while ([condition]);
 Dans ce cas la vérification de la condition se fait après

l’exécution du bloc d’instruction
 Le bloc d’instruction s’exécute au moins une fois

Exemples Répéter …….tant que
Cet algorithme fait la somme des valeurs saisies, arrêt lorsque S>=1000)
Language C
int S, i, var;
i = 1;
S = 0;
do
{
printf("Saisir la valeur" , i);
scanf("%d",&var);
S = S + var;
i = i + 1;
}
while (S<1000);
printf("le nbre de valeur est :%d", i);
Comparaison boucles répéter et tant que
• boucle While
 condition vérifiée avant chaque exécution du traitement
 le traitement peut donc ne pas être exécuté
 la condition porte surtout sur la saisie de nouvelles
variables (relance)
• boucle Do While
 condition vérifiée après chaque exécution du traitement
 le traitement est exécuté au moins une fois
 la condition porte surtout sur le résultat du traitement
Remarque: la boucle répéter est typique pour les saisies

avec vérification.
Choisir pour... tant que… répéter…
Boucle Tant que

n
No
Traitement
exécuté au
moins une
Non fois
Oui
Nombre
d’itération
connu ? Boucle Répéter
Oui
Boucle Pour
L’algorithme du Max et du Min
Trouver la max et le nombre de max d’un certain nombre connu de valeur
int x, Max, Nmax;

printf(« saisir la valeur 1 »);
Scanf(«%d», &x);
Max = X
Nmax = 1
for (i=2; i<=10 ; i++){
printf(« saisir la valeur 1 »);
Scanf(«%d», &x);}
if (x>Max){
Max = x
Nmax = 0
}
if Max == X {
Nmax=Nmax+1}
}
printf(« la valeur Max est : %d», Max)
printf(« le nbre des Max est : %d», Nmax)
main()
{
int v, i, S=0, Max, nmax;
L’algorithme du Max
Trouver la max et le min d’un certain nombre inconnu de valeur. La
i=1;
saisie s’arrête
printf("donner lorsqu’on
la valeur %d ", i);saisie une valeur égale à zéro
scanf("%d", &v);
if(v==0)
{printf("saisie terminee");
printf("le nbre de valeur saisie est %d \n ", i-1);}
else{
Max=v;
nmax=0;
while (v!=0){
if(v>Max){
Max=v;
nmax=0;}
if(v==Max)
nmax++;
i++;
printf("donner la valeur %d ", i);
scanf("%d", &v);}
printf("saisie terminee\n ");
printf("le nbre de valeur saisie est %d \n ", i-1);
printf("le max est : %d\n", Max);
printf("le nbre de max est : %d\n", nmax);}
}
Les tableaux
Exemple de problème :
Saisir une suite de nombres, puis afficher cette suite après
avoir divisé tous les nombres par la valeur maximale de la
suite.
Nécessité de conserver les nombres en mémoire
Variable contenant une valeur Variable contenant plusieurs valeurs
var 132
var 23 -12 -11 2 23 23 21 12 123 132

Les tableaux
Un tableau est une variable qui peut contenir plusieurs données de même type:
 Tableau d’entiers
 Tableau de réels
 Tableau de caractère
Un tableau possède des dimensions

 Tableau à une dimension (ligne) (liste de données)
 Tableau à deux dimensions (ligne colonne) (traitement d’image)
 Tableau à trois dimensions (ligne, colonne profondeur) (données spatiales)
 Tableau à quatre dimensions (ligne, colonne, profondeur, temps) (données
spatiales qui évolue dans le temps)
 …..
 L’espace mémoire réservé pour un tableau augmente fortement avec le nombre
de dimension. Problème de la taille limité de la mémoire
Les tableaux Accès aux données
L’accès à une donnée (case) dans un tableau nécessite un ou plusieurs
indices:
- Tableau à une dimension : un seul indice utilisé
- Tableau à deux dimensions : deux indices utilisés (indice ligne et indice
colonne)
- Tableau à trois dimensions : trois indices utilisés.
 les "cases" sont numérotées à partir de zéro, autrement dit que le plus
petit indice est zéro.
 Lors de la déclaration d'un tableau, on précise le nombre cases du

tableau c-a-d le nombre de valeur stockées.
Nom du tableau indice
0 1 2 3 4
Tab1 12 3 4 -56 -8
valeurs
Indice ligne
Indice colonne
0 1 2 3 4
1 3 4 -56 -8
2 3 4 6 7 valeurs
3 2 12 32 43
4 2 6 7 9
Nom du tableau Tab2
Tab1(3)=-56 Tab2(3)(2)=12
0 1 2 ….. 499
12 1 2 …… 5
0 0 0 0 1 1 0 0
P
0 0 0 0 0 0 0 1
P+1
P+2 0 0 0 0 0 0 1 0
……. ... … … … … … … …
P+499 0 0 0 0 0 1 0 1
T un pointeur qui pointe l’adresse mémoire où on stock la première

valeur
T+0=&T[0]
*(T+0)=T[0]
T+1=&T[1]
*(T+1)=T[1]
T+2=&T[2]
*(T+2)=T[2]
…
..
T+499=&T[499]
*(T+499)=T[499]
main()
main() {
main() { int *T, i=0, n, k;
{ int *T, i, n;
int T[10], i; T=(int*)malloc(sizeof(int));
printf("n= "); printf("T[%d]= ", i);
for(i=0; i<10; i++) scanf("%d", &n);
{ scanf("%d", T+i);
T=(int*)malloc(n*sizeof(int)); while(T[i]!=0)
printf("T[%d]= ", i); for(i=0; i<=n-1; i++) {
scanf("%d", &T[i]); {
} i++;
printf("T[%d]= ", i); T=(int*)realloc(T,
} scanf("%d", T+i); (i+1)*sizeof(int));
} printf("T[%d]= ", i);
} scanf("%d", T+i);
}
}
malloc() & realloc()
La syntaxe de la fonction malloc() est :
(Type*)malloc(Nbre_case*sizeof(Type))

Cette fonction retourne un pointeur d’un certain type (Type*) pointant vers un
objet de taille (Nbre_case)*sizeof(Type) octets.
La syntaxe de la fonction remalloc() est :
(Type*)realloc(pointeur, Nbre_case*sizeof(Type))

Cette fonction permet de :
- faire une extension de la zone mémoire allouée par malloc et pointé par
« pointeur », Si l'espace mémoire libre qui suit le bloc initial est suffisant
- Allouer un nouveau bloc de mémoire (bloc d’origine plus l’extension), le
contenu de la zone d'origine recopié dans la nouvelle zone et le bloc
mémoire d'origine sera libéré automatiquement. Si l'espace mémoire libre
qui suit le bloc initial est insuffisant
malloc() & realloc()
*P
*(P+1)
*(P+2)
(type*)Malloc(6*sizeof(type)
*(P+3)
*(P+4)
*(P+5)
P *P P *P
*(P+1) *(P+1)
*(P+2) (type*)Realloc(P, 8*sizeof(type) *(P+2)
*(P+3) *(P+3)
*(P+4) *(P+4)
*(P+5) *(P+5)
*(P+6)
*(P+7)
Les Tableaux
Insertion d’un élément :
Ecrire un programme qui saisit la dimension N d’un tableau de int
remplit le tableau par des valeurs entrées au clavier. Insérer ensuite
une valeur « e » à une position « pos » du même tableau. Afficher
enfin le tableau avec la valeur insérée.
Insérer un élément dans la case 2
0 1 2 3 4 5
12 4 11 78 15
Les Tableaux
suppression d’un élément :
Ecrire un programme qui saisit la dimension N d’un tableau de int
remplit le tableau par des valeurs entrées au clavier. Supprimer
ensuite la valeur d’une position « pos » du même tableau. Afficher
enfin le tableau de N-1 éléments.
Suppression de l’élément de la case 2
0 1 2 3 4
12 4 11 78 15
Suppression d’une valeur dans un tableau
0 1 2 3 4 5 6 7
2 12
14 14
12
45 12 45 12 12 12
j=0;
for(i=0; i<n; i++)
{
T[j]=T[i];
if(T[i]!=x)
j++;
}
Suppression de doublons
Suppression sur place
2 12 2 12 24 2 24
2 12 12 24 24 2 24
2 12 24 24 24
2 12 24 24
for(k=0; k<n; k++)
{
j=k+1;
for(i=k+1;i<n; i++)
{
T[j]=T[i];
if(T[i]!=T[k])
j++;
}
for(i=j; i<n; i++)
n=j;
}
Suppression de doublant
Suppression des doublant avec stockage dans une autre zone

mémoire
T 2 12 2 12 24 2 24
G 2 12 24
G=(int*)malloc(sizeof(int));
k=0;
for(i=0; i<n; i++)
{
for(j=0; j<i && T[i]!=T[j]; j++)
{}
if(i==j)
{G=(int*)realloc(G, (k+1)*sizeof(int));
G[k]=T[k];
k++;}
}
Les Tableaux
Union de tableau:
Ecrire un programme qui saisit deux tableaux de dimension # et de
créer un troisième dont les éléments représentent l’union sans
doublons des deux tableaux.
i= 0 1 2 3 i= 0 1 2
T1[i]= 12 4 13 12 T2[i]= 45 4 32
k= 0 1 2 3 4
T[k]= 12 4 13 45 32
Les Tableaux
Intersection de tableaux:
Ecrire un programme qui saisit deux tableaux de dimension # et de
créer un troisième dont les éléments représentent l’intersection des
deux premiers tableaux.
i 0 1 2 3 4 5 6 j 0 1 2 3
T1[i]= 12 4 13 6 12 45 23 T2[j]= 12 4 23 45
k 0 1 2 3
T[k]= 12 4 45 23
Exercice:
Donner un algorithme qui stocke un certain nombre inconnu de notes dans un tableau
de valeur et calcule et affiche la moyenne. L’utilisateur peut arrêter la saisie en
entrant (-1).
Les tableaux multidimensionnels
12
 En mémoire un tableau statique, quelque soit sa
dimension, (T[n1][n2]…[np]) occupe un seul bloc. 9
Ligne 1
 Ce bloc est linéaire. 34
 Dans un tableau à plusieurs dimensions, l’accès à une 11
données (case) provoque un déplacement en mémoire
à partir du début. 18
-11
Ligne 2
0 1 2 3 9
0 12 9 34 11 -34
1 18 -11 9 -34 -1
2 -1 0 13 15 0
Ligne 3
3 78 22 88 23 13
15
78
22
Ligne 4
88
23
Donc on peut considérer un tableau de n dimension comme un tableau
unidimensionnel. On repère un élément du tableau par un seul indice
T *T
T+1 *(T+1)
0 1 ….. n T+2 *(T+2)
0 T+3 *(T+3)
1 … ..
….. ..
…..
m ..
….. ..
..
…..
Le temps d’accès à une donnée du tableau est ..
long. Pour accéder à un élément T(p, q) on ..
……
doit parcourir p*n+q+1 éléments.
T+n*m-1 *(T+n*m-1)
Les tableaux multidimensionnels (2D)
Tableau de valeurs
Simple Pointeur P *(*(T+0) + 0)
*(*(T+0) + 1)
Double Tableau de pointeurs ….
Pointeur *(*(T+0) + m-1)
T *(T+0) *(*(T+1) + 0)
*(T+1) *(*(T+1) + 1)
*(T+2) ….
….. *(*(T+1) + m-1)
*(*(T+2) + 0)
…..
*(*(T+2) + 1)
*(T+n-1) ……
*(*(T+2) + m-1)
……
*(*(T+n-1) + 0)
Chaque élément est repérer par deux indices : numéro de ligne et
numéro de colonne:
&T[i][j] = *(T+i) + j = T[i] + j
T[i][j] = *(*(T+i) + j)
Le temps d’accès à une donnée du tableau est plus rapide. Pour accéder
à un élément T(p, q) on va aller directement vers l’adresse
pointée par T[p] puis à l’adresse T[p]+q.
T[0][0][0]
Les tableaux multidimensionnels 3D T[0][0][1]
…..
T[0][0] T[0][0][k-1]
T[0]T[1] T[0][1][0]
…. T[0][1][1]
T[0]T[m-1]
…..
T T[0] T[1]T[0]
T[0][1][k-1]
T[1] T[1]T[1]
…. ….
T[2]
T[1]T[m-1] T[0]T[m-1][0]
…..
T[2]T[0] T[0]T[m-1][0]
….. T[2]T[1] ….
T[n-1] …… T[0]T[m-1][k-1]
T[2]T[m-1]
……
T[n-1]T[0]
Chaque élément est repérer par trois indices : numéro de ligne, numéro
de colonne et numéro de la profodeur:
&T[i][j][k]= *(*(T+i) + j) + k = T[i][j] + k
T[i][j][k] = *(*(*(T+i) + j) + k)
Pour accéder à un élément T(p, q, s) on va aller directement vers

l’adresse pointée par T[p] puis vers l’adresse pointée par T[p][q]
puis vers l’adresse T[p][q] + s
Repérer les données par un ou plusieurs indices ???

Les tableaux
main()
{
main() int **T, i, j, n, m;
{ printf("n= ");
int T[3][3], i, j; scanf("%d", &n);
for(i=0; i<=2; i++) printf("m= ");
{ scanf("%d", &m);
for(j=0; j<=2; j++) T=(int**)malloc(n*sizeof(int*));
{ for(i=0; i<=n-1; i++)
printf("T[%d][%d]= ", i, j); {
scanf("%d", &T[i][j]); *(T+i)=(int*)malloc(m*sizeof(int));
} for(j=0; j<=m-1; j++)
} {
} printf("T[%d][%d]= ", i, j);
scanf("%d", *(T+i)+j);
}
}
printf("T[2][1]= %d", *(*(T+2)+1));
}
les valeurs d’un tableau multidimensionnel alloué dynamiquement ne
sont pas forcément stockées dans un seul bloc. En effet l’initiation des
pointeurs T[i] avec la fonction malloc() permet au système d’exploitation
de chercher n zones mémoire composées chacune par m case mémoire.
Chaque zone sera pointée par T[i].
Les Algorithmes de tri
 Les tableaux permettent de stocker plusieurs éléments de
même type au sein d'une seule entité,
 Trier un tableau c'est donc ranger les éléments d'un
tableau en ordre croissant ou décroissant
 Il existe plusieurs méthodes de tri qui se différencient par
leur complexité d'exécution et leur complexité de
compréhension pour le programmeur.
 Nous exposons deux méthodes :
 le tri par sélection (minimum (maximum) successif )
 Le tri à bulles (permutation successive)
 Le tri par insertion
Le tri par insertion
Ce tri s’inspire d’un processus naturel utilisé dans le tri des cartes qu’un
possédé dans sa main, le joueur prend chaque carte et l’insère à sa place
en décalant les autres.
Ce tri utilise le processus élémentaire d’insertion d’une valeur dans sa

position dans une liste des valeurs triée.
4
50
0 1 2 3 4 5 6 7 8
12 23 35 45 55
55 63
63 78
78 89
89
Lire (e) // valeur à inserer
Redim(T(n+1))
Pour(i=n; i>=1 && e<T[i -1]; i--)
T[i]=T[i-1];
FinPour
T[i]=e;
pour(i=0; i<=n; i++)
Afficher(T[i])
FinPour
Pour(k=1; k<n; k++)
e=T[k];
Pour(i=k; i>=1 && e<T[i-1]; i--)
T[i]=T[i-1];
suivant i
T[i]=e
Suivant k
Tri par sélection
Tri par Min ou Max successif
Consiste à chercher le minimum (ou maximum) et à la
permuter avec la valeur de la première position, puis
rechercher le deuxième min et la permuter avec la deuxième
position, et ainsi de suite. Cette algorithme utilise donc le
traitement élémentaire de permutation de deux valeurs de
deux variables.
Tri par maximum successif
r=0 r=1 r=2 r=3 r=4 r=5

i=0; 12 14 11 3 34 10
i=1; 34 14 11 3 12 10
i=2; 34 14 12 3 11 10
i=3; 34 14 12 11 3 10
i=4; 34 14 12 11 10 3
Tri par max successif
Pour(k=0; à n-2; k++)
Max=T[k];
pmax=k;
Pour(i=k+1; à n-1 ; i++)
Si(T[i]>Max)
Max=T[i];
pmax=i;
FinSi
Suivant i
Si(T[k]!=T[pmax]) Alors
e=T[k];
T[k]=T[pmax];
T[pmax]=e;
FinSi
Suivant k
Le tri à bulles
Principe de la méthode :
On parcoure le tableau du début à la fin et en échangeant tout

couple d'éléments consécutifs non ordonnés:
si(T[i]<T[i+1]) on permute.
La plus petite valeur se case à droite du tableau (dans T[n-1]).
On reprend la même opération pour le tableau T[0]..T[n-2] et
ainsi de suite.
Le tri à bulles
Par exemple, pour trier [130, 156, 213, 230, 300] suivant un
ordre décroissant, on va avoir les boucles suivantes :
i=0; 130 156 213 230 300
k=0; 156 130 213 230 300

k=1; 156 213 130 230 300
k=2; 156 213 230 130 300
k=3; 156 213 230 300 130
i=1; 156 213 230 300 130
k=0; 213 156 230 300 130

k=1; 213 230 156 300 130
k=2; 213 230 300 156 130
Le tri à bulles
Pour(i=1 à n-1 ; i++)

Pour(k=0 à n-i; k++)
Si(T[k]<T[k+1]) Alors
e=T[k];
T[k]=T[k+1];
T[k+1]=e;
FinSi
Suivant k
Suivant i
Algo & Prog C-2
Fonctions et Procédures
Chaines de caractère
Les Structures
Les Fichiers
Les fonctions & les procédures
On peut, dans une application, procéder aux mêmes
traitements, ou à des traitements similaires, à plusieurs
endroits de son déroulement.
Ces traitements vont être écrites dans des algorithmes à
part
 Fonctions
 procédures
Dans l’algorithme principale on peut appeler plusieurs fois

une fonction ou une procédure
Une fonction ou une procédure peut elle-même appeler
une ou plusieurs fonctions et procédures.
Structuration Diviser pour

mieux régner
Les fonctions et les procédures permettent de décomposer
un programme complexe en une série de sous-programmes
plus simples, lesquels peuvent à leur tour être décomposés
eux-mêmes en fragments plus petits, et ainsi de suite.
Intérêts Les fonctions & les
procédures
 Regrouper un ensemble d’instruction dans le même
algorithme afin de pouvoir y faire appel autant de fois que
nécessaire.
 Lisibilité et identification des erreurs, réutilisation
 On peut ne pas connaître comment est définie une
fonction ou une procédure pour y faire appel. Par contre il
est nécessaire de connaître sa déclaration (son manuel
d’utilisation):
 Quel est son rôle?
 Quels sont les arguments à fournir?
 Quelles est la valeur retournée?
-Les paramètres-
Les procédures et fonctions peuvent nécessiter éventuellement zéro un
ou plusieurs paramètres d’entrée ou de sortie.
Un paramètre d’entrée est la référence à une variable manipulée par

la procédure ou la fonction. Dans ce cas la valeur d’une variable du
programme principal est copiée dans ce paramètre.
Un paramètre de sortie est une variable dont la valeur est affectée par
les instructions du sous-programme
Un paramètre d’entrée-sortie Un paramètre peut jouer à la fois le

rôle de paramètre d’entrée et de sortie.
On peut avoir des fonctions qui nécessite pas de paramètres pour qu’ils
soient exécutées. On parle de fonction sans argument
Les fonctions
 Les fonctions sont des sous-programmes admettant des paramètres et
retournant un seul résultat (comme les fonctions mathématiques
z=f(x,y,. . .)). les fonctions possédent:
 Un nom
 des paramètres en nombre fixe (n>=0)
 Un seul type, qui est le type de la valeur retournée. la valeur de
retour est spécifiée par l'instruction Return
 Généralement le nom d’une fonction doit être explicite:

 Maximum()
 Minimum()
Syntaxe: Exemple
type NomFonction (type a, type b, type c, …){

Type res ;
…
Return res }
type NomFonction (type *a, type *b, type c, …){

Type res ;
…
Return res }
type * NomFonction (type a, type b, type c, …){

Type *res ;
…
Return res }
Syntaxe: Exemple
type NomFonction (type a, type b, type c, …){

Type res ;
…
Return res } Paramètres Formels
Main()
{ type P, x, y, z ……;
………
P = NomFonction (x, y, z, …)
……}
Paramètres effectifs
Les fonctions
Exemple : fonction qui renvoi le maximum de deux variables a et b
(paramètres d’entrés).
#include <stdio.h>
int Max(int a, int b) main()
{ { int M, x, y;
int res; printf("x = ");
res=a; scanf("%d", &x);
if(b>res) printf("y = ");
res=b; scanf("%d", &y);
return(res); M=Max(x, y);
} printf("Max = %d", M);
}
Les fonctions
Exercice : Ecrire une fonction int FMax(int *T, int n) qui permet de trouver le
maximum d’un tableau d’un certain nombre de valeurs. Ecrire un algorithme test
qui appelle cette fonction.
#include <stdio.h> main(){

#include <stdlib.h> int i, n, *tab, M;
int Fmax(int *T, int n) printf("donner le nombre de valeur n =
{int Max, i; ") ;
Max=T[0]; scanf("%d",&n);
for(i=0; i<n; i++) tab=(int*)malloc(n*sizeof(int));
{if(T[i]>Max) for (i=0; i<n; i++)
Max=T[i];} {printf("tab(%d) = ", i);
return(Max);} scanf("%d", tab+i);}
M=Fmax(tab, n);
printf("maximum est : %d", M;}
Les Procédures
 Les procédures sont des sous-programmes qui ne retournent aucun
résultat
 Par contre elles admettent des paramètres d’entrés, de sorties ou

d’entrés/sorties:
Syntaxe: Exemple
void NomProcédure (type a, type b, type c, …. )

{ Type variablesLocals;
…
…}
void: vide ou Null (ne retourne rien)

Syntaxe: Exemple
void NomProcédure (type a, type b, type c, …){

Type res ;
…}
Paramètres Formels
Main()
{ type P, x, y, z ……;
………
NomProcédure (x, y, z, …)
……}
Paramètres effectifs
Exercices: Ecrire une procédure qui permet d’afficher le Max et le Min d’un
tableau d’entier. void MaxMin(int *V, int n)
int Fmax(int *T, int n) int Fmin(int *T, int n)

{int Max, i; {int Min, i;
Max=T[0]; Min=T[0];
for(i=0; i<n; i++) for(i=0; i<n; i++)
{if(T[i]>Max) {if(T[i]<Min)
Max=T[i];} Min=T[i];}
return(Max);} return(Min);}
void MaxMin(int *V, int n)

{
printf("max = %d\n", Fmax(V, n));
printf("min = %d\n", Fmin(V, n));
}
Exercice
 Ecrire une procédure permute(a, b) qui permute les

valeurs de ceux variables entiers.
 Ecrire un algorithme d’essai. Transmission de valeurs
#include <stdio.h> Pas de
void permute(int a, int b) permutation
{int k;
main(){
k = a;
int x, y;
a = b;
printf("x = ");
b = k;}
scanf("%d", &x);
&a a printf("y = ");
scanf("%d", &y);
&b b
permute(x, y);
&x x printf("x = %d\n", x);
printf("y = %d", y);}
&y y
Exercice
 Ecrire une procédure permute(a, b) qui permute les

valeurs de ceux variables entiers.
 Ecrire un algorithme d’essai. Transmission d’adresse
#include <stdio.h>
void permute(int *a, int *b)
{int k;
main(){
k = *a;
int x, y;
*a = *b;
printf("x = ");
*b = k;}
scanf("%d", &x);
printf("y = ");
a=&x a scanf("%d", &y);
permute(&x, &y);
b=&y b
printf("x = %d\n", x);
printf("y = %d", y);}
Exercice
Ecrire une procédure permute(a, b) qui permute les valeurs de ceux
variables entiers. Ecrire une autre procédure Tri (x, y, z) qui tri dans
l’ordre décroissant en appelant la procédure permute(a, b).
#include <stdio.h>
void permute(int *a, int *b){
int k; main(){
k=*a; int z1,z2,z3;
*a=*b; printf("donner trois
*b=k;} valeurs\n");
void tri(int *x, int *y, int *z){ scanf("%d", &z1);
if (*x<*y) scanf("%d", &z2);
permute(x,y); scanf("%d", &z3);
if (*y<*z) tri(&z1, &z2, &z3);
permute(y,z); printf("%d%d%d", z1,
if (*x<*y) z2, z3)}
permute(x,y);}
Exercice
Créer une fonction
#include max(a, b) qui renvoi le maximum de deux
<stdio.h>
variables:
int Max(int a, int b){
Créer une fonction VMAX(T) qui permet trouver le maximum des
int res;d’un vecteur de 4 valeurs et ceci en appelant la fonction
éléments
res=a; main(){
max(). Créer un algorithme d’essai.
if(b>a) int V[5], i;
{res=b;} for (i=0; i<=4; i++){
return (res);} printf("V[%d]=", i);
scanf("%d", &V[i]);}
printf("le maximum est: %d\n", VMAX(V));}
int VMAX(int *V){

int i, M;
for (i=0; i<=4; i++)
M = Max(Max(Max(Max(V[0], V[1]),V[2]),V[3]),V[4]);
return (M);}
Processus d’analyse
La décomposition en sous traitement
Le processus d’analyse permet de décomposer un traitement complexe en

sous traitement « plus simples » mais différent du précédent. ces sous
problèmes seront à leur tour décomposés jusqu’à un niveau d’opération
« élémentaires » faciles à réaliser.
Processus d’analyse
La décomposition récursive
Dans certain cas, le sous traitement est une illustration du problème initial,
mais pour un cas « plus simple ». Par conséquent, la solution du problème
s’exprime par rapport à elle-même! On appelle ce phénomène récursivité.
Dans un raisonnement par récurrences : pour résoudre un problème

complexe on appelle le même traitement initial mais avec un cas plus simple.
Traitement complexe
Sous Traitement 1
Sous traitement 2
Traitement élémentaire
Méthode itérative et récursive
Méthode itérative : un traitement élémentaire qui progresse grâce à

une boucle. Le dernier traitement donne le résultat final.
Méthode récursif: le calcul final est exprimé en fonction du calcul

précédent. Donc pour faire un traitement revient à faire le même traitement
mais pour un cas plus simple jusqu’a arrivé au traitement élémentaire.
X0 *X X4 =
X1 *X X* X3
X2 *X X* X2
X3 *X X* X1
X4 *X X* X0
= X4
Raisonnement par récurrence
Exemple de Récursivité
la factoriel de n est :
n! = 1*2*3…..*n : traitement itératif
n! = n*(n-1)*(n-2)*(n-3)*…..*1
n! = n*(n-1)! : traitement récursif
Pour calculer la valeur de n!, il suffit donc de savoir calculer

(n-1)! Et ensuite de multiplier cette valeur par n.
Le sous problème du calcul (n-1)! Est le même problème
initial, mais pour un cas « plus simple » car (n-1 < n)
Fonction récursive
Dans les algorithmes
 Pendant le traitement d’une fonction nous pouvons appeler

d’autres fonctions déjà déclarées (décomposition en sous
problèmes)
 Nous pouvons aussi, Pendant le traitement d’une fonction,
appeler la même fonction initiale mais avec des arguments
plus simples (décomposition récursive)
 Une fonction récursive est une fonction qui s’appelle elle-
même dans son traitement.
 Si la fonction appelée n’est autre que la fonction qui
appelle, on déclenche une boucle infinie. Donc nécessité
d’une condition de sortie de la fonction.
Fonction récursive
Type F(type a, type b){ Type RF(type z){
float res; Type Var x, res
….. if(<test logique>)
Return res } ....
else
Type NF(type z ){ Res = RF(x)
Type x, y, res2 Return res
…..
res2 = F(x, y)
return res2 }
 Récursivité simple
 Récursivité terminale
Fonctions Récursives simple
 Des fonctions s'appelant elles-mêmes, elles sont également
un moyen rapide pour poser certains problèmes
algorithmique.
 il faut une condition valide de sortie pour la fonction.
 Les appels des fonctions récursives sont empilées puis

dépilées à partir du dernier appel (LIFO)
 Une fonction de ce type possède donc deux parcours: la

phase de descente et la phase de remontée.
 Une descente jusqu’à ce que la fonction rencontre la

condition de sortie, puis elle remonte dans tous les appels
précédents
Neme appel récursive
2 Traitement
13erer appel récursive
Elémentaire
, Soit un traitement récursive

,
,
,
LIFO
Exemple Fonction – Factorielle
 On peut écrire la factorielle de N par une suite:

Avec Un = n!. Sous cette forme Un dépend de n et Un-1.

Ecrire l'algorithme de la fonction factorielle en employant
Un traitement récursive simple.
Un traitement itératif.
Fonction itérative et récursive – Factorielle
Résonnement itérative Résonnement récursive
long fact(int n){ long fact_rec(int n){
long res; long res;
int i; if(n==0 || n==1)
res=1; res=1;
for(i=1; i<=n; i++) else
res=res*i; res=n*fact_rec(n-1);
return(res);} return(res);}
main(){
int x;
printf("x = ");
scanf("%d", &x);
printf("%d! = %d", x, fact(x));}
Phase descente
Fact(6) = 6 * fact(5)
Fact(5) = 5 * fact(4)
Fact(4) = 4 * fact(3)
Fact(3) = 3 * fact(2)
Empilements des appels de la fonction Fact(2) = 2 * fact(1)

récursive puis dépilement des appels
enregistrées. 2*1
3*2*1
4*3*2*1
5*4*3*2*1
6*5*4*3*2*1
Phase de remontée
Fonction récursive terminale
La récursivité simple reste valable pour des petits calculs.
Pour des récursivités plus profondes, un autre type de fonction récursive
existe, c'est la récursivité terminale.
c'est une récursivité avec uniquement une phase de descente, sans

remontée.
Cela est possible en évitant de faire d’autre opérations sur les appelles
empilés la fonction récursive.
Nous allons donc éviter la multiplication par n pendant les appelles de la

FR. on a pas besoin de les stocker (empilé).
Fonction récursive terminale
long fact_rec_term(int n, long res){
int z;
if(n==0)
z=1;
else if(n==1)
z=res;
else
Fact(6,1) z=fact_rec_term(n-1, n*res);
return(z);}
Fact(5, 6*1)
Fact(4, 5*6*1)
Fact(3, 4*5*6*1)
Fact(2, 3*4*5*6*1)
Fact(1, 2*3*4*5*6*1)
Si n==1; renvoyer res=720
Fonction– Racine carrée
 La valeur de la racine carrée d'un nombre A peut être
approximée en employant la suite récurrente d'ordre 1
suivante:

*Fonction Racine carrée (2)
 Version itérative  Version récursive
float racine(floatA,floate){
float X;
X=A;
while(abs(X*X-A)>e)
X=(X+A/X)/2; float racine(float A,float e,
return(X);} float X){
float res;
if(abs(X*X-A)<=e)
res = X;
else
res = racine(A,e,(X+A/X)/2);}
return (res);}
float racine(float A,float e,
float X){
float res;
if(abs(X*X-A)<=e)
res = X;
else
res = racine(A,e,(X+A/X)/2);}
return (res);}
|X*X-A|=1
Racine(2, 1.500) 0.25 Récursivité terminale

Racine(2, 1.4166) 6.75 10-3
Racine(2, 1.414215) 3.83 10-5
Racine(2, 1.414213) 1 10-6
X=1,414213
le Maximum de V avec une fonction récursive
Soit la fonction Max(a, b).
Ecrire une fonction récursive qui renvoi le maximum des valeurs d’un
tableau V de dimension n. cette fonction aura pour argument les
éléments du vecteur V et la dimension n « RecMax(V, n) »
Cette fonction récursive doit renvoyer la valeur suivante:

Pour n=5 on doit renvoyer

Donc trouver le max des éléments d’un vecteur V de dimension N revient à

trouver le Max des éléments d’un vecteur V de dimension N-1 et V(N-1)
int Max(int a, int b){
int res;
res = a;
if(b>res)
res=b;
return(res);}
int Fmax(int *T, int n){

int M, i;
if (n==1)
M=T[0];
else
if(n==2)
M=Max(T[0], T[1]);
else
M=Max(Fmax(T, n-1), T[n-1]);
return(M);}
123 56 2378 33 21
MAX(T[4], FMax(T, 4))
(
MAX T[4], MAX(T[3], FMax(T, 3)) )
2378
(
MAX T[4], MAX(T[3], MAX(T[2], FMax(T, 2))) )
(
MAX T[4],2378 )
(
MAX T[4], MAX(T[3], MAX(T[2],MAX(T[1], T[0]))) )
(
MAX T[4], MAX(T[3],2378) )
(
MAX T[4], MAX(T[3], MAX(T[2],123)) )
Recherche du Max Méthode de
diviser pour régner
Etape-1 : diviser le tableau en deux sous-tableaux.
Etape-2: trouver récursivement le maximum dans chaque demi-tableau

Max1 et Max2. Si la taille du demi-tableau est réduite à deux éléments, on
appelle la fonction Max(a,b).
Etape-3: retourner le maximum des deux maximums trouvés.

int FMax(int *T, int deb, int fin)
{
int res, Max1, Max2, mid;
if((fin-deb)<=1)
res=MAX(T[deb], T[fin]);
else{
mid=(fin+deb)/2;
Max1=FMax(T, deb, mid);
Max2=FMax(T, mid+1, fin);
res=MAX(Max1, Max2);}
return(res);
}
0 1 2 3 4 5 6 7 8 9
5 6 9 8 -4 12 -13 1 2 7
Deb=0 =Max(v(1),v(0))=6
Fin = 2
(2-0=2)
Mid=2/2=1
Max1=Fmax(v, 0, 1)
Deb=0 Max2 = Fmax(v, 2, 2)
= Max(v(2),v(2))=9
Fin = 4 Max(6,9)=9
Deb=0
(4-0=4)
Fin = 9
Mid=4/2=2
(9-0=9)
Max1=Fmax(v, 0, 2)
Mid=9/2=4,5
Max2 = Fmax(v, 3, 4)
Max1=Fmax(v, 0, 4) Max(v(4),v(3))=8
Max2 = Fmax(v, 5, 9) Max(9,8)=9
Max(12,9)=12 Deb=5 Deb=5

Fin = 9 Fin = 7
(9-5=4) (7-5=2)
= Max(v(5),v(6))=12
Mid=14/2=7 Mid=12/2=6
Max1=Fmax(v, 5, 7) Max1=Fmax(v, 5, 6)
Max2 = Fmax(v, 8, 9) Max2 = Fmax(v, 7, 7) = Max(v(7),v(7))=1
Max(12,7)=12 Max(12,1)=12
Max(v(8),v(9))=7
Calcul récursif de la puissance Méthode-1
PUISS(2, 6)
2*PUISS(2, 5) 2*32=64
2*PUISS(2, 4) 2*16=32
2*PUISS(2, 3) 2*8=16
2*PUISS(2, 2) 2*4=8
2*PUISS(2, 1) 2*2=4
2*PUISS(2, 0) 2*1=2
Calcul récursif de la puissance Méthode-1
int PUISS(int X, int n)

{
int res;
if(n==0)
res=1;
else
res=X*PUISS(X, n-1);
return(res);
}


{
int res;
if(n==0)
res=1;
else if(n%2==0)
res=PUISS(X*X, n/2);
else
res=X*PUISS(X*X, (n-1)/2);
return(res);
}
{
int res;
if(n==0)
res=1; PUISS(2, 6) 64
else if(n%2==0)
res=PUISS(X*X, n/2); PUISS(4, 3) 64
else
res=X*PUISS(X*X, (n-1)/2);
return(res); 4*PUISS(16, 1) 4*16*1
}
16*PUISS(16*16, 0) 16*1
Récursivité croisée
Deux fonctions récursive qui s’appelle mutuellement:
Calcul de la racine carré en utilisant deux suites adjacentes.

float U(int n, float A)

float V(int n, float A)
{
{
float V(int, float);
float z;
float z;
if (n==0)
if (n==0)
z=A;
z=1;
else
else
z=(U(n-1, A)+V(n-1, A))/2;
z=2/(1/U(n-1, A)+1/V(n-1, A));
return(z);
return(z);
}
Algorithmes de tri
 Les tableaux permettent de stocker plusieurs éléments de
même type au sein d'une seule entité,
 Trier un tableau c'est donc ranger les éléments d'un
tableau en ordre croissant ou décroissant
 Il existe plusieurs méthodes de tri qui se différencient par
leur complexité d'exécution et leur complexité de
compréhension pour le programmeur.
 Nous exposons deux méthodes :
 le tri par sélection (minimum (maximum) successif )
 Le tri à bulles
 Le tri par insertion
Algorithmes de tri
Dans les deux premières méthodes de tri, on doit utiliser
une procédure qui permet d'échanger (de permuter) la
valeur de deux variables.

{
int k;
k=*a;
*a=*b;
*b=k;
}
Tri par sélection
Tri par Min ou Max successif
on parcourt le tableau de gauche à droite, on cherche le plus
petit élément puis on le positionne dans l’indice i du tableau.
On recommence la même opération pour le sous-tableau de
droite qui commence par l’indice i+1.
plus généralement : Pour trier le sous-tableau

t[i..nbElements] il suffit de positionner au rang i le plus
petit élément de ce sous-tableau et de trier le sous-tableau
t[i+1..nbElements]
Tri par maximum successif
r=0 r=1 r=2 r=3 r=4 r=5

i=0; 12 14 11 3 34 10
i=1; 34 14 11 3 12 10
i=2; 34 14 12 3 11 10
i=3; 34 14 12 11 3 10
i=4; 34 14 12 11 10 3
Tri par max successif
int posmax(int *T, int n, int r)
void Tri(int *V, int n)

Le tri à bulles
Principe de la méthode :
Sélectionner le minimum du tableau en parcourant le tableau

du début à la fin et en échangeant tout couple d'éléments
consécutifs non ordonnés.
Le tri à bulles
Par exemple, pour trier [130, 156, 213, 230, 300] suivant un
ordre décroissant, on va avoir les boucles suivantes :
i=0; 130 156 213 230 300
k=0; 156 130 213 230 300

k=1; 156 213 130 230 300
k=2; 156 213 230 130 300
k=3; 156 213 230 300 130
i=1; 156 213 230 300 130
k=0; 213 156 230 300 130

k=1; 213 230 156 300 130
k=2; 213 230 300 156 130
Le tri à bulles
void Tri(int *T, int n)

Ce tri s’inspire d’un processus naturel utilisé dans le tri des cartes qu’un
possédé dans sa main, le joueur prend chaque carte et l’insère à sa place
en décalant les autres.
void Tri_Insert(int *T, int n)

LE TRI Rapide (TRI PIVOT)
C'est l’un des tris les plus rapides, et les plus utilisés. La méthode est
constituée de deux méthodes.
Placer un élément du tableau (appelé pivot) à sa place définitive, en

permutant tous les éléments de telle sorte de placer toutes les valeurs
inférieures au pivot à sa gauche et placer ceux qui sont supérieurs
à sa droite. Cette opération s'appelle le partitionnement.
Pour chacun des sous-tableaux de gauche et de droite, on applique par

récurrence le même traitement avec un nouveau pivot, jusqu'à
ce que l'ensemble des éléments soit trié.
Première partitionnement avec le pivot V[0]
int pivot(int *T, int deb, int fin)
{ void tri(int *T, int deb, int fin)
int pv=deb; {
int j=deb, i; int pv;
for(i=deb+1; i<=fin;i++){ {
if(T[i]<T[pv]) if(deb<fin)
{ {
j++; pv=pivot(T, deb, fin);
perm(T+i, T+j); tri(T, deb, pv-1);
} tri(T, pv+1, fin);
} }
perm(T+j, T+deb); }
return j; }
}
Les algorithmes de Recherche
Recherche linéaire dans un ensemble non trié
 On procède par une recherche linéaire: on parcoure le

tableau et lorsque qu’on trouve le nombre recherché (t(i)=X)
on renvoi l’indice correspondant.
 Si on parcourt tous le tableau sans trouver la valeur
recherchée on déclare que le nombre n’existe pas.
Recherche dans un ensemble non trié
Fonction Recherche (T(), X, Nb)
Var i, R : entier
i0
Tant que (i<=Nb-1 ET T(i) # X) Alors
i  i+1
Fin tant que
Si (i = Nb) alors
Ecrire (« le nombre est introuvable »)
Sinon
Ecrire (« le nombre de trouve dans l’indice »)
Renvoyer (i)
Fin
Recherche Dichotomique dans un ensemble trié
La recherche séquentielle demande plus de temps d’exécution.
L’algorithme de Dichotomie est basé sur le principe de « diviser pour

résoudre ».
On divise l’ensemble de recherche en deux sous-ensembles égaux. On

détermine ensuite dans quel sous-ensemble doit se trouver la valeur
recherchée. Puis on poursuit la recherche d’une manière récursive dans
les sous-ensembles jusqu’à ce qu’on trouve la valeur recherché ou on
arrive à un sous-intervalle où la borne inférieure coïncide avec la borne
supérieure et donc on conclut que la valeur n’existe pas dans cette
ensemble.
Recherche par Dichotomie (fonction récursive)
void Rech_Dico(int *T, int deb, int fin, int x) {

int i, mid, z;
if(deb>fin)
printf("valeur introuvable");
else {
mid=(deb+fin)/2;
if(T[mid]==x)
printf("valeur trouvee a %d", mid);
else {
if(x<T[mid])
fin=mid-1;
else
deb=mid+1;
Rech_Dico(T, deb, fin, x); } }
}
Recherche par Dichotomie (fonction itérrative)
void Rech_Iterra(int *T, int deb, int fin, int x) {
int mid;
mid=(deb+fin)/2;
while(T[mid]!=x && deb<fin)
{
if(x<T[mid])
fin=mid-1;
else
deb=mid+1;
mid=(deb+fin)/2;
}
if(T[mid]==x)
printf("la valeur est trouvee a i = %d", mid);
else
printf("la valeur non trouvable");
}
Utilisation de la dichotomie
résolution de f(x)=0
f est une fonction définie sur l’intervalle [a, b] et strictement
monotone sur [a, b]. On cherche à résoudre numériquement
l’équation f(x) = 0.
l’existante d’une racine sur [a, b] se traduit par le fait que
f(a) et f(b) sont de signe contraires, c-a-d f(a)*f(b)<0, et
que f est continue sur [a, b].
Si p est un réel sur [a, b], la racine x0 par rapport à p peut
être testée par l’algo suivant:
Si f(a)*f(p)<=0 alors
Rechercher x0 dans [a,p]
Sinon
Rechercher x0 dans [p,b]
FinSi
Utilisation de la dichotomie
résolution de f(x)=0

double
doublezerof(double
zerof2(double a, a,
double b, b,
double double e){e){
double
double
doublemid,
mid,res;
res;
mid=(a+b)/2;
int n=1; P2 P3 P1
if(fabs(f(mid))<e)
mid=(a+b)/2; Min Min
res=mid;
while(fabs(f(mid))>=e){
else{if(f(a)*f(mid)<0)
if(f(a)*f(mid)<0)
b=mid;
b=mid;
else f(Min)
else
a=mid;
a=mid;
mid=(a+b)/2;
res=zerof(a,
n++; b, e);}
return res;}
printf("%d\n", n);}
return mid;} f(P2)
main(){ P2 P3 P1
double a, b, e=1e-6; f(P3) Min Max
printf("a = "); f(P1)
scanf("%f", &a);
printf("b = "); f(Max)
scanf("%f", &b);
if(f(a)*f(b)>0)
printf("pas de solution");
else
printf("%f", zerof(a, b, e));}
Chapitre – 2 Les chaines de caractère
 Dans un programme informatique, les chaînes de caractères servent à

stocker les informations non numériques comme par exemple une liste
de nom de personne ou des adresses.
 En langage C Il n'existe pas de type spécial chaîne ou string. Une

chaîne de caractères est traitée comme un tableau à une
dimension de caractères (vecteur de caractères).
 Pour marquer la fin de la chaine de caractère le symbole ‘\0’ doit être

saisi et stocké dans la dernière case du tableau.
Déclaration d’une chaîne
char <nom_chaine>[<dimension>]
Initialiser un tableau d’entier
int tab[5] = {12, 23, 5, 0, 123};
Initialiser d’un tableau de char
char T[7]={'b', 'o', 'n', 'j', 'o', 'u', 'r'};
Initialiser d’une chaine char
char T[8]={'b', 'o', 'n', 'j', 'o', 'u', 'r', '\0'};

Pour le cas spécial des chaines de caractères, nous pouvons utiliser

une initialisation plus confortable
char T[8]="bonjour";
char CH[ ] = "bonjour";
Lors de l'initialisation par [], l'ordinateur réserve automatiquement

le nombre d'octets nécessaires pour la chaîne, c.-à-d.: le nombre
de caractères + 1 (ici: 8 octets).
main()
{int i; main(){
CH[]="bonjour"; char CH[]="bonjour";
for(i=0; i<=7; i++) printf("%s", CH);}
printf("%c", CH[i]);
}
le code format %s permet d’afficher toute la chaine de caractère.

Ci-dessous un programme C qui permet de visualiser la mémorisation

d’une chaine de caractère :
# include <stdio.h>
main(){
char CH[8]="bonjour";
int i;
printf("\tCaractere | ASCII | Adresse\n");
printf("-----------------------------------\n");
for(i=0; i<8; i++)
printf("CH[%d] = %5c | %4d | %6x\n", i, CH[i], CH[i], &CH[i]);}
Initialiser une chaine char
char A[ ] = "Bonjour !"; /* déclaration par un tableau */

char *B = "Bonjour !"; /* déclaration par un pointeur */
A est un tableau Les caractères de la chaîne peuvent être changés,

mais le nom A va toujours pointer sur la même adresse en mémoire.
B est un pointeur pointé sur une chaîne de caractères constante
stockée quelque part en mémoire. Elle peut être lue, copiée ou
affichée, mais pas modifiée. Le pointeur peut être modifié et pointer
sur autre chose.
char *A = "Petite chaîne";

char *B = "Deuxième chaîne un peu plus longue";
A = B;
A et B pointent sur la même chaîne; la "Petite chaîne" est perdue:
char A[45] = "Petite chaîne";

char B[45] = "Deuxième chaîne un peu plus longue";
A = B; /* IMPOSSIBLE -> ERREUR !!! */
Donc dans le cas d’une initiation d’une chaine par un tableau on pourra
modifier (réinitialiser) cette chaine.
# include <stdio.h>
main(){
char CH[]= "bonjour", t='B';
*CH=t;
printf("%s\n", CH);}
Par contre cette dernière sera constante (non modifiable) dans le cas
d’une initiation par pointeur.
# include <stdio.h>
main()
{ char t;
char *CH= "bonjour", t='B'; // Impossible: Erreur //
*CH=t;
printf("%s\n", CH);}
Dans les chaînes de caractères, nous pouvons utiliser toutes les

séquences d'échappement définies comme caractères constants:
# include <stdio.h>
main(){
char CH[9]="bon\njour";
printf("%s", CH);}
Remarque
'c' est un caractère contant qui a une valeur numérique qui correspond
au code ASCII
''c'' est un tableau de caractères qui contient deux caractères la lettre

'c' et le caractère NULL: '\0'
Saisie d’une chaîne de caractères
Saisie dans un tableau statique
Utilisation de scanf("%s", CH)
# include <stdio.h>
main() !!!!!!!! Utilisation facile mais
{ avec beaucoup de précaution
char CH[20];
scanf("%s", CH);
printf("%s\n", CH);
}
Utilisation de scanf("%s", CH)

 cette fonction s'arrête si elle tombe au cours de sa lecture sur un
espace, une tabulation ou une entrée. il sera impossible de récupérer
toute la chaine de caractère.
 cette fonction ne contrôle pas la taille de la mémoire initialement
réservée pour le stockage de la chaine. Dépassement de la mémoire.
# include <stdio.h>
main(){
char CH[20];
printf("donner votre nom et prenom ");
scanf("%s", CH);
printf("votre nom et prenom est : %s\n", CH);}
Utilisation de scanf("%c", CH+i)

main()
 {
Ici la saisie se fait caractère par caractère dans une boucle « while ».
 char CH[20];
Tant que l’utilisateur n’a pas tapé « Return » (\n) la saisie des caractères
continue. int p=0;
 Le caractère printf("donner
« Null » est votre
stockénom
à laetfin
prenom ");
de la chaine pour marquer la fin
scanf("%c",
de cette dernière. CH+p); « Null » va remplacé ‘\n’.
Le caractère
 while(CH[p]!='\n')
La récupération de la chaine sera complète même si on introduit un
espace dans {p++;
la chaine initiale.
scanf("%c", CH+p);}
CH[p]='\0';
Saisie dans un tableau dynamique
La réservation de <stdio.h>
# include la mémoire sera dynamique en utilisant les fonctions
malloc() main(){
et realloc().
char *CH, c;
int p=0, i;
printf("donner votre nom et prenom ");
CH=(char*)malloc(sizeof(char));
scanf("%c", CH+p);
while(CH[p]!='\n')
{ p++;
CH=(char*)realloc(CH,(p+1)*sizeof(char));
scanf("%c", CH+p);
}
CH[p]='\0';
Parcourir une chaîne de caractères :

On peut utiliser un pointeur pour parcourir une chaine de caractère.
int main(void) int main(void){ int main(void){

{ int i=0; char *ptr;
char *ptr; char CH[] = "Bonjour"; char CH[] = "Bonjour";
char CH[] = "Bonjour"; while (CH[i]!='\0'){ ptr=CH;
printf("%s\n",CH);} printf("%c",CH[i++]);}} while (*ptr!='\0')
printf("%c",*ptr++);}
Manipulations de chaînes de caractères

Fonction de lecture getchar() et d’écriture putchar()
getchar() est une fonction sans paramètre qui « capte » la valeur du

caractère lu à la position courante de l'entrée standard (le clavier) et
le retourne. scanf(« %c », &x).
putchar() écrit le caractère passé en argument sur la sortie standard

(l'écran). printf(« %c », x)
#include <stdio.h>
int main(){
char c;
c = getchar();
// le programme suspend son fonctionnement jusqu'à ce que l'utilisateur tape
// au moins un caractère puis la touche <return>
putchar(c);}

Fonction de lecture gets() et d’écriture puts()
Gets(Chaine) lit une ligne de de caractères de stdin (clavier ou fichier) jusqu’à

ce qu’elle rencontre ‘\n’ et la copie à l'adresse indiquée par <Chaîne>. Le retour
à la ligne final ‘\n’ est remplacé par le symbole de fin de chaîne '\0'.
Char * gets(char *chaine)
Elle va nous permettre de lire une ou plusieurs lignes de texte (p.ex. des
phrases) terminées par un retour à la ligne.
#include <stdio.h>
main(){
char CH[100], *P;
P=gets(CH);
printf("%s", p);}

Fonction de lecture gets() et d’écriture puts()
puts écrit la chaîne de caractères désignée par <Chaîne>

sur stdout (Ecran ou fichier) et provoque un retour à la ligne.
puts(CH); est équivalent à printf("%s",CH).
#include <stdio.h>
main(){
char CH[100];
printf("saisir une chaine ");
gets(CH);
printf("votre chaine est: ");
puts(CH);}

fonction de saisie d'une chaîne de caractères fgets()
C’est une fonction qui appartient au fichier « stdio.h ». Elle a besoin de

trois paramètres et revoie une chaine de caractère.
char * fgets ( char * CH, int num, FILE * strdin );

CH : de type pointeur vers un tableau de caractères.
num : taille en octets du tableau de caractères pointé par chaîne.
Stdin : flux d’entrée. Il pointe vers le fichier à partir duquel se fait la lecture.
Cette fonction lit les caractères stdin et les place dans la chaîne CH tant
que le caractère lu est différent du caractère de saut de ligne ('\n') (ce
caractère est copié en fin de chaîne). La fin de la chaîne de caractères est
marquée par l'ajout d'un caractère nul (\0).
Cette fonction retourne le pointeur chaîne CH en cas de succès, et un

pointeur NULL en cas de fin de flux.

Recopie d'une chaîne de caractères strcpy, strncpy
C’est une fonction qui appartient au fichier « string.h ».
char * strcpy ( char * destination, char * source );
Copie la chaîne pointée par source vers la chaîne pointée par

destination. Attention au débordements de mémoire
char * strncpy ( char * destination, char * source, num );
Copie les num premiers caractères de source vers destination.


Concaténation de chaînes strcat(), strncat()

char * strcat ( char * destination, const char * source );

Ajoute une copie de la chaîne source à la chaîne destination. Le caractère de
fin de chaîne de destination est remplacé par le premier caractère de source,
et un nouveau caractère de fin de chaîne est ajouté à la fin de la nouvelle
chaîne résultante destination.
char * strncat ( char * destination, char * source, size_t num );

Ajoute les num premiers caractères de source à destination, plus un
caractère fin de chaîne.
Comparaison de chaînes strcmp(), strncmp()

int strcmp ( const char * str1, const char * str2 );
Compare les chaînes str1 et str2.

 Un zéro signifie que les deux chaînes sont égales
 Une valeur positive indique que le premier caractère différent a une
plus grande valeur dans str1 que dans str2
 Une valeur négative indique l'inverse.
int strncmp ( const char * str1, const char * str2, size_t num );
 Un zéro signifie que les num premiers caractères des deux chaînes
sont égaux.
 Une valeur positive indique que le premier caractère différent a une
plus grande valeur dans str1 que dans str2
 Une valeur négative indique l'inverse.
Nombre de caractère d’unr chaine strslen()
Retourne le nombre de caractères de CH sans tenir compte du caractère

de fin de chaîne.

int strlen (char *CH);
main()
{
char CH[]="bonjour";
printf("%d", strlen(CH));
}
Recherche d'un char dans une autre strchr()

char *strchr (const char *CH, int c)
Retourne l'adresse de la première occurrence du caractère c dans la

chaîne CH en partant du début de la chaîne. ou un pointeur NULL si c
n'est pas trouvée de CH
main(){
char CH1[]="abcdefr";
char *p;
p=strchr(CH1, 'c');
if(p!=NULL)
printf("trouvee");
else
printf("non trouvee");}
Recherche d'une chaîne dans une autre strstr()

char * strstr ( const char * CH1, const char * CH2);

Cette fonction retourne un pointeur sur la première occurrence de la
chaîne CH2 dans la chaine CH1, ou un pointeur NULL si CH2 n'est pas
une partie de CH1. La comparaison ne porte pas sur le caractère fin de
chaîne.
main(){
char CH1[]="abcdefr", CH2[]="cde";
char *p;
p=strstr(CH1, CH2);
if(p!=NULL)
printf("trouvee");
else
printf("non trouvee");}
Tableau de chaine de caractère

main(){
char **T, c;
int i, k, n;
n=0;
printf("saisir le nombre d'enregitrement");
scanf("%d", &n);
getchar();
T=(char**)malloc(n*sizeof(char*));
for (i=0; i<n; i++)
{
k=0;
printf("donner la chaine %d ", i);
T[i]=(char*)malloc(sizeof(char));
scanf("%c",T[i]+k);
while(*(T[i]+k)!='\n')
{
k++;
*(T+i)=(char*)realloc(*(T+i), (k+1)*sizeof(char));
scanf("%c",T[i]+k);
}
T[i][k]='\0';
}
for (i=0; i<n; i++)
printf("%s\n", T[i]);
Les Structures
besoin d’un mécanisme permettant de grouper un certain nombre de
variables de types différents au sein d’une même entité.
Champs ou membre ou élément
Référence Désignation Prix Stock
Une structure un ensemble d’éléments de types différents repérés par

un nom. Les éléments sont appelés des champs ou membre d’une
structure.
Déclarer une structure c’est créer un certain type de variable qui

va nous permettre de sélectionner plusieurs d’autre variables
conventionnel de différents types
Structure test
Type1 V1 Type3 V3
P1
P2
Type2 V2
struct test{
Type1 V1
Type2 V2
Type3 V3};
typedef struct test str;
Str P1, P2;
Les Structures
Déclaration de structure
Elle se fait en deux étapes :
Définir le type structure avec les membres
struct personne
{ On préfère utiliser l’instruction « deftype »
char nom[20];
char prenom[20]; Typedef struct personne str
int no_employe;
};
Déclarer des variables de ce type
struct personne p1, p2;

Ou bien
str p1, p2;

Les Structures
struct Produit
char nom1[20]; {
char nom2[20]; char nom[20];
float Prix1; float Prix;
float Prix2; int Stock;
int Stock1; };
int Stock2; Deftype struct Produit Prod
Prod p1, p2;
Nom1[20] Produit1
Nom2[20] Produit2
p1
Prix1 25,50
Prix2 21,20
p2
Stock1 500
Stock2 100
Les Structures
Initiation d’une structure et
Accès aux membres de structure avec l’opérateur (.)
struct personne
{
char nom[20];
char prenom[20];
int no_employe;
};
struct personne p1={"ALAOUI", "Ahmed", 23}, p2;
main()
{
printf("%s ", p1.nom);
printf("%s ", p1.prenom);
printf("%d", p1.no_employe);
}
Les Structures
simplifier la déclaration de types : définir des synonymes avec
typedef
typedef permet de définir type un synonyme à ce que l’on nomme en

langage C
typedef int entier; typedef int * ptr; typedef struct test Str;
struct test
main() main() {
{ { float x;
entier a, b; ptr P1, P2; char c;
} } int a;
};
main()
{
Str S1, S2;
}
Les Structures
Saisie des membres d’une structure
typedef
La saisie des champs d’unestruct personne
structure str; avec les méthode déjà vu de
se fait
struct
saisie des variables personne{
classiques.
chacun des champschar d’unenom[20];
structure peut être d’un type absolument
chartableau,
quelconque : pointeur, prenom[20];
structure, pointeur ... Il peut
int no_employe;};
même s’agir de pointeurs sur des structures du type de la structure dans
main(){
laquelle ils apparaissent.
//saisie des champs
 Données simplestr(int,
p1; float, char, ….);
 Tables de donnée;gets(p1.nom);
gets(p1.prenom);
scanf("%d", &p1.no_employe);
//Affichage des données
printf("%s ", p1.nom);
printf("%s ", p1.prenom);
printf("%d", p1.no_employe);
}
Saisie des membres d’une Structure comportant des pointeurs
vers une zone allouer dynamiquement : Chaine de caractère
Ecrire un programme qui permet de saisir puis afficher les champs de la

structure suivante:
struct employe
{
char *nom;
char *prenom;
int num;
};
Les Structures
Affectation de structures
Il est possible d’affecter à une structure le contenu d’une structure
définie à partir du même modèle.
typedef struct personne str; Une telle affectation globale

struct personne{ remplace :
char nom[20];
char prenom[20]; i=0;
int no_employe;}; while(P1.nom[i]!=‘\0’)
{
str p1, p2; P2.nom[i]=p1.nom[i];
…… P2.prenom[i]=p1.prenom[i];
p2=p1; i++;
}
P2.no_employe=p1.no_employe
Les Structures
Pointeurs vers une structure
On peut déclarer un pointeur de type structure de la manière suivante :
typedef struct personne Str;

struct personne{
char nom[20];
char prenom[20];
int no_employe;};
Str S1, *P1, *P2;

……
P1 = &S1;
P2=(Str *) malloc(sizeof(Str));
Les Structures
Pointeurs vers une structure
Si nous voulons écrire une référence à un membre de la structure
pointée par un pointeur P on doit écrire :
(*P).nom ou P  nom
l’indirection (*) a une priorité inférieure à celle de la sélection (.).
(*P).x est différent à *P.x
(*P).x signifie que P est un pointeur vers une structure qui possède
un élément X d’un certain type.
*P.x signifie que P est une variable de type structure. La structure

posséde un élément pointeur vers une valeur d’un certain type.
Les Structures
Pointeurs vers une structure et/ou des pointeurs
vers des éléments.
typedef struct personne Str; struct personne
struct personne
struct personne {
{
{ char c;
char c;
char c; int *x;
int *x;
int x; float y;
float y;
float y; };
};
};
main()
main()
main() {
{
{ Str *P, S1, S2;
Str S;
Str *P; P=(Str*)malloc(sizeof(Str));
S.x=(int*)malloc(sizeof(int));
P=(Str*)malloc(sizeof(Str)); P->x=(int*)malloc(sizeof(int));
S.c='A';
P->c='A'; P->c='A';
*S.x=23;
P->x=23; *P->x=23;
S.y=4.8;
P->y=4.8; P->y=4.8;
}
} }
Les Structures
Structure et les pointeurs
struc test struc test struc test
{ { {
type1 champ1 type1 champ1 type1 champ1
type2 champ2 type2 champ2 type2 champ2
…. struc test *P type3 *P
} …. ….
struc test var1, var2, *P } }
struc test var1, var2 struc test var1, var2
Pointeurs vers une
structure un des membres est un des membres est
Pointeurs vers une Pointeurs vers une
structure du même Variable de type
type différent
Les Structures
• Structure dont l’un des membre est un pointeur vers
une structure du même type
 Permet de pointer sur une autre structure de même struc test

type qui est stocker dans la mémoire. {
 On peut donc stocker plusieurs valeurs d’une type1 champ1
structure en mémoire. type2 champ2
 Stockage de ces valeurs dans des zones mémoires struc test *P
non contiguës. ….
 Chainage de valeurs et Création des listes chainée. }
struc test var1, var2
C’est une autre manière pour stocker un ensemble de valeur de même

type en mémoire.
Ce stockage va se faire dans différentes zones mémoire ne constituant
pas un bloc (non contiguës).
ces zone mémoire seront liées et constituent une liste chainée.
Deb = NULL typedef struct Insert_Note Str;
struct Insert_Note
{
Fin = NULL
Str *Next;
float note;
Str *Last;
Deb = Fin = New };
Next = NULL
New
Note = 12 Fin = New
Last = NULL Next = New
NULL
Note = 15
Last = Fin
NULL
Fin = New
Next = NULL
Note = 13,50
Last = NULL
Fin
Chainage de la chaine
if(Deb==NULL)
Deb=Fin=New
{
Deb=New;
Fin=New;
}
else
{
Fin->Next=New;
New->Last=Fin;
Fin=New;
}
Deb
Next
12,00
Last=NULL Next
18,00
Last
Next
14,00
Last
Parcourir une LC
Str *P
Int i=1
P=Deb; Fin
While(P!=NULL)
{ Next=NULL
P=P->Next; 10,00
i++; Last
}
Deb Insertion à une position pos
Next
P1
12,00
Next
Last=NULL
18,00
Last Next
18,00
Last
P2
Next
14,00
Last
Fin
Next=NULL
10,00
Last
Insertion à une position pos
else
if(pos==1) {
{ P=Deb;
New->Next=Deb; for(i=1; i<pos; i++)
Deb->Last=New; {
Deb=New; P=P->Next;
} }
else if(pos==n) P1=P->Last;
{ P2=P;
Fin->Next=New; P1->Next=New;
New->Last=Fin; New->Last=P1;
Fin=New; New->Next=P2;
} P2->Last=New;
}
Deb Suppression à une position pos
Next
P1
12,00
Next
Last=NULL
18,00
Last Next
18,00
Last
P2
Next
14,00
Last
Fin
Next=NULL
10,00
Last
Suppression à une position pos
else
if(pos==1) {
{ P=Deb;
Deb=Deb->Next; for(i=1; i<pos; i++)
} {
else if(pos==n) P=P->Next;
{ }
Fin->Last->Next=NULL; P1=P->Last;
P2=P->Next;
}
P1->Next=P2;
P2->Last=P1;
P1->Next=P2;
P2->Last=P1;
Deb->Next : pointe la deuxième
structure de la liste }
Fin->Last: pointe l’avant dernière

structure
Les Files et Les Piles
La File est une structure de données qui permet de stocker les

données dans l’ordre FIFO. L’insertion des données se fait donc
toujours à la fin de la liste (i.e. par le haut de la pile), la sortie se fait
par le bas.
Fin->Next=New
New->Last=Fin
Fin=New
La Pile est une structure de données, qui permet de stocker les

données dans l’ordre LIFO. L’insertion des données se fait donc
toujours au début de la liste (i.e. par le haut de la pile), donc le
premier élément de la liste est le dernier élément inséré, sa position
est donc en haut de la New->Next=Deb
pile.
Deb->Last=New
Deb=New;
Deb Fin
Next=NULL Next=NULL
Last Last
Les Piles
Next LIFO Next
Last Last
Next Next
Last Les Files Last

FIFO
Deb= Fin Deb =Fin
Next Next
Last=NULL Last=NULL
if(Deb==NULL){
typedef struct Insert_Note Str; Deb=New;
struct Insert_Note{ Fin=New;}
Str *Next; else{
float note; (*Fin).Next=New;
Str *Last;}; (*New).Last=Fin;
Fin=New;}
main(){
Str *Deb=NULL, *Fin=NULL, Cour=Deb;
*New, *Cour=NULL; while(Cour!=NULL){
float x; printf("%f\n", (*Cour).note);
int n; Cour=(*Cour).Next;}}
int i;
printf("donner le nombre de note; ")
scanf("%d", &n);
for(i=0; i<n; i++){
printf("donner la note %d ", i);
scanf("%f", &x);
New=(Str *)malloc(Str)); Enfilement
(*New).Next=NULL;
(*New).note=x;
(*New).Last=NULL;
Les Structures
Les Tableaux de structure
Nous allons développé dans ce cours le cas du stockage de plusieurs
valeurs d’une variable de type structure dans un tableau de structure.
Les données sont stockées dans un bloc de mémoire.
struct personne
{
char nom[20];
char prenom[20];
int no_employe;
};
struct personne tab_personne[100];
tab_ensemble[i].nom représente le nom de la personne de rang i du

tableau « tab_personne »
tab_ensemble [i].nom[k] représente le kème caractère du nom de la

ième personne.
Les Structures
Ecrire un prog C qui permet de saisir et de stocker le nom, le prénom ainsi
que le code des employés dans un tableau de structure « employé ».
Utiliser une allocation statique.
struct employe
{
char *nom;
char *prenom;
int num;
};
struct client
{
char *nom;
char *prenom;
int code;
};
typedef struct client client;
main()
{
int i, n;
client Tabclient[20];
printf("donner le nombre de client a saisir ");
scanf("%d", &n);
getchar();
for(i=0; i<n; i++)
{
printf("saisir le client %d\n", i+1);
Tabclient[i].nom = saisirChaine();
Tabclient[i].prenom=saisirChaine();
scanf("%d", &Tabclient[i].code);
getchar();
}
Les Structures
Allocation dynamique d’un tableau de structure
struct NomStruct
{
…….
};
typedef NomStruct Struct;
main()
{
int n ;
Struct *Tab ;
scanf("%d », &n) ;
Tab=(Struct*)malloc(n*sizeof(Struct)) ;
…….
}
Les Structures
Ecrire un prog C qui permet de saisir et de stocker les noms, les prénoms
ainsi que les codes des employés dans un Tableau de structure
« employé ». La saisie s’arrête lorsqu’on saisie un nom égal à la liste
constante « FIN ».
Les Listes Chainées

Ecrire un prog C qui permet de saisir et de stocker les noms, les prénoms
ainsi que les codes des employés dans une Liste Chainée de structure
« employé ». La saisie s’arrête lorsqu’on saisie un nom égal à la liste
constante « FIN ».
Les Structures
Les Tableaux et les Listes Chainées
Permettent de mettre en mémoire un ensemble de données de
même type sous un même identificateur:
Les Listes Chainées: stockage des données dans des cases

mémoires non contigües.
Avantage: Structuration plus flexible de données. possibilité d'ajouter

ou de supprimer des cases à tout moment sans déplacer les autres
éléments de la liste.
Inconvénient: temps de recherche d’un élément plus long. iI faut

parcourir la LC depuis le début jusqu'à ce qu'on le retrouve.
Les Structures
Les Tableaux et les Listes Chainées
Les Tableaux: stockage des données dans des cases mémoires

contigües.
Avantage: temps de recherche plus rapide. Pour accéder au i ème

élément il suffit d’écrire Table[i].
Inconvénient: c’est une structure figée. Le temps d’insertion et de

suppression est plus long.
Les Tables de hachage
Dans un tableau, la recherche de donnes se fait travers un indice T[i]

Les tables de hachage permettent de faire une recherche à travers un
élément de la structure.
par exemple, chercher les données concernant un client on précisant

son code (Table[« code »].
il faut pouvoir transformer son code en indice du tableau
Il faut écrire une fonction qui prend en entrée une chaîne de

caractères (code), fait des calculs avec, puis retourne en sortie un
numéro correspondant à cette chaîne. Ce numéro sera l'indice de la case
dans notre tableau
BY45
Les Structures
• Transmission d’une structure en argument d’une
fonction : transmission de valeur ou d’adresse.
typedef struct Test Str; typedef struct Test Str;
struct Test struct Test
{ {
float x; float x;
int a; int a;
}; };
void f(Str E) void f(Str *E)
{ {
E.x+=2; E->x+=2;
E.a++; E->a++;
} }
main() main()
{ {
Str E; Str E;
E.x=3.5; E.x=3.5;
E.a=6; E.a=6;
f(E); f(&E);
printf("%f, %d", E.x, E.a);} printf("%f, %d", E.x, E.a);}
Les Structures
• Fonction pointeur vers une structure.
struct employe
{
char *nom;
char *prenom;
int num;
};
Créer la procédure void saisir_employe(Str *E) qui permet de saisir

une structure.
Créer une fonction Str *saisirTable(int n) qui permet de saisir un

tableau de structure.
Les Fonctions d’entrées-Sorties
Dans un programme C on stock dans des adresses mémoire (mémoire

centrale) des valeurs qui proviennent d’une flot de données (stream):
- Saisie à partir du clavier scanf()
- Lecture à partir d’un fichier fscanf()
Dans un programme C on récupère les résultats d’un traitement par:

- Un affichage sur Ecran (les données sont dans la RAM. Perdue après
fermeture du programme. printf()
- Une Ecriture dans un fichier fprintf() (les données sont dans le HD)
Les fichiers permettent de stocker (ou lire) des données sur (à partir d’)
un support permanent tel que le disque dur. Les données sont
mémorisées sous forme d'une suite d'octets.
deux types de fichiers : binaire ou texte.
fichier rempli en mode binaire : chaque donnée est stockée selon la

méthode de codage binaire imposées par son type.
Les données ne peuvent être lues/écrites que par programme.
Avantage : La taille du fichier est optimale et les données sont facilement
lues/écrites avec des instructions réduites.
Inconvénient : on ne peut pas éditer le fichier pour en vérifier ou en modifier
le contenu.
Ce type de fichier peut être utiliser pour faire des sauvegardes de

données entre deux appels d'un programme.
Pour lire/écrire dans un fichier binaire, on utilise deux fonctions rapides à

utiliser (fread(), fwrite()).
Pour se positionner n'importe où dans le fichier (fseek()).
fichier rempli en mode Texte : chaque information est stockée sous la

forme d’une succession de codes ASCII.
Avantage : en plus de leur accès par programme, les données du fichier
peuvent être créées ou consultées par l'utilisateur à l'aide d'un
éditeur de texte,
Inconvénient : ils occupent souvent plus de place et sont plus difficiles à
manipuler par programme.
Un fichier texte est donc un cas particulier de fichier binaire : on peut donc
le manipuler en accès binaire, avec les fonctions (fread, fwrite).
On utilise surtout des fonctions "formatées" (fprintf, fgets, fscanf,...),
qui ressemblent à celles dont on dispose pour écrire à l'écran ou lire au
clavier.
Pour traiter les deux types de fichiers, binaire ou texte, on suit la même
procédure :
1. ouvrir le fichier (fonction fopen) ; on indique le nom du fichier et le
mode d’accès.
2. lire ou écrire dans le fichier en utilisant les fonctions compatibles
avec le type de fichier (binaire ou texte).
a. fread()//fscanf()
b. fwrite()//fprintf()
3. fermer le fichier (fonction fclose).
Contenu d’un fichier binaire et de son équivalent texte
On veut stocker dans un fichier la structure suivante :
Str S={-1.345e-5, -54, "abc"};
fichier en accès binaire avec la fonction fwrite()

-1.345e-6 -54 abc
BF 02 16 82 F9 44 24 1C FF CA 61 62 63 00
Codage IEEE Codage en comp2 Codage ASCII des lettres
8 octets 2 octets 4octers
fichier en accès Texte avec la fonction fprintf()

- 1 . 3 4 5 e - 5 - 5 4 a b c
2D 31 2E 33 34 35 65 2D 35 1B 2D 35 34 1B 61 62 63
17 octets
fputc()
fputs()
fprintf()//fwrite()
Ecriture dans un fichier
Programme C Fichier
Main Texte
{ 2334
……… 12/12/2015
}
HD
RAM
Lecture à partir d’un fichier
fgetc()
fgets()
fscanf()//fread()
Pour manipuler un fichier, un programme a besoin d'un certain nombre

d'informations :
 l'adresse de l'endroit de la mémoire-tampon où se trouve le fichier

 le mode d'accès au fichier (lecture ou écriture) ...
Ces informations sont rassemblées dans une structure dont le type, FILE*,
définie dans stdio.h.
Un objet de type FILE * est appelé flot de données (en anglais, stream).
Ouverture et fermeture de fichiers : fopen(), fclose()
FILE *fopen (char *nom-de-fichier , char *mode)

Paramètres
nom-de-fichier :if(fopen(nom-de-fichier
le nom du fichier auquel on ,veut
mode)==NULL)
accéder.
Mode : est uneprintf(‘’Ouverture
chaîne de caractères quiimpossible’’) ;
spécifie le mode d'accès au fichier. Les
modes d'accès else
diffèrent suivant le type de fichier considéré. On distingue : les
fichiers textes,{les fichiers binaires (caractères de contrôle sont interprétés ou pas.
//…Utilisation du contenu du fichier…//
Valeur rendue}
Si l’ouverture a réussi, la valeur retournée permet de repérer le fichier
Si l’ouverture est impossible, fopen rend la valeur NULL.
Ouverture et fermeture de fichiers
"r" ouverture d’un fichier texte en lecture.

"w" ouverture d’un fichier texte en écriture.
"a" ouverture d’un fichier texte en écriture à la fin.
"rb"ouverture d’un fichier binaire en lecture.
"wb" ouverture d’un fichier binaire en écriture.
"ab" ouverture d’un fichier binaire en écriture à la fin.
"r+" ouverture d’un fichier texte en lecture/écriture.
"w+" ouverture d’un fichier texte en lecture/écriture.
"a+" ouverture d’un fichier texte en lecture/écriture à la fin.
"rb+ ouverture d’un fichier binaire en lecture/écriture.
"wb+ ouverture d’un fichier binaire en lecture/écriture.
Ouverture et fermeture de fichiers
int fclose ( FILE * stream );
Paramètres
stream est le flot de type FILE* retourné par la fonction fopen() correspondant.
Valeur rendue
La fonction fclose() retourne un entier qui vaut zéro si l'opération s'est déroulée
normalement (et une valeur non nulle en cas d'erreur).
FILE *fi;
fi=fopen(nomfichier, mode)
fclose(fi);
Lecture et écriture par caractère sur fichier
Lecture par caractère sur fichier
int fgetc (FILE * stream)
Paramètres
#include
Stream ou flot-de-données : <stdio.h>
est de type pointeur vers FILE. Il pointe vers le fichier à
partir duquel se fait laint c;
lecture.
FILE *fi;
Valeur rendue
while ((c = fgetc(fi)) != EOF)
rend le caractère lu.
{ y a erreur d’entrée-sortie, ou rencontre de fin de fichier.
rend la valeur EOF S’il
... /* utilisation de c */
}
Lecture et écriture par caractère sur fichier
Ecriture par caractère sur fichier
int fputc (int carac , FILE *flot-de-données)
Paramètres
– carac est de type int,FILE
c’est*fo;
le caractère à écrire.
– flot-de-données est char
de typec; pointeur vers FILE. Il pointe vers le fichier sur lequel se
fait l’écriture.. fo=fopen("testecrire", "w");
do
Valeur rendue {c=getchar();
La fonction fputc() rend le caractère écrit si l’écriture s’est faite sans erreur, ou EOF
fputc(c, fo);}
en cas d’erreur.
while(c!='\n');
EXERCICE
Ecrire une fonction qui permet de saisir puis stocker caractère par caractère une
chaine de char dans un fichier.
Ecrire une fonction qui permet de mettre en mémoire le contenue d’un fichier en
stockant dans une chaine caractère par caractère.
Lecture et écriture par lignes sur fichier
Lecture par lignes sur fichier
char *fgets(char *chaine, int max, FILE *stream)

lit max #include <stdio.h>
- 1 caractères d’une chaînes sur le fichier les stocke dans la chaîne
« chaine ».#define LONG
elle s'arrête dès ...
qu'elle rencontre un caractère de passage à la ligne et
place unchar \0 à ligne[LONG];
la fin de la chaîne. Lorsqu'elle rencontre la fin de fichier, elle
retourne FILE
la chaîne
*fi; NULL.
while (fgets(ligne,LONG,fi) != NULL) //stop sur fin
Paramètres
de fichier ou erreur//
– chaîne : est de type pointeur vers char et doit pointer vers un tableau de caractères.
{ la taille en octets du tableau de caractères pointé par chaîne.
– taille : est
... // utilisation
– flot-de-données de pointeur
: est de type ligne //vers FILE. Il pointe vers le fichier à partir
duquel se} fait la lecture.
Valeur rendue
La fonction fgets rend le pointeur chaîne en cas de lecture sans erreur, ou NULL
dans le cas de fin de fichier ou d’erreur.
Lecture et écriture par lignes sur fichier
Écriture par chaîne : fputs()
int fputs (char *chaîne , FILE *flot-de-données)

Fputs() écrit sur le fichier le contenu du tableau dont la fin est indiquée par un
caractère null. C-a-d écrire une ligne ou une chaîne quelconque
Paramètres
FILE *fo;
– chaîne est de type pointeur vers char. Pointe vers un tableau de caractères contenant
char
une chaîne se terminant parc,unT[20];
null.
– flot-de-données estfo=fopen("testecrire",
de type pointeur vers FILE."w");
Il pointe vers le fichier sur lequel se
fait l’écriture.
gets(T);
Valeur rendue
fputs(T, fo);
La fonction fputs rend une valeur non négative si l’écriture se passe sans erreur, et
EOF en cas d’erreur.
Ecrire un programme qui permet d’écrire dans un fichier une chaine de
char en utilisant une allocation statique.
Ecrire un programme qui lire à partir d’un fichier une chaine de char
puis la stocker dans la RAN dans un tableau statique.
Ecrire une procédure permettant de saisir n chaines de caractères char
par char puis les stocke sur n ligne sur un fichier.
void FStock(FILE *fi, int n)
Programme qui permet de stocker les lignes d’un fichier dans une tableau de
chaine avec une allocation dynamique.
char** MStock(FILE *f)

Lecture et Ecriture formatées sur fichiers
Écriture formatée : fprintf()
int fprintf (FILE *stream , chaineformat , param1 , param2 , ... , paramn )
Paramètres
– flot-de-données : est de type pointeur vers FILE. Il pointe vers le fichier sur lequel
se fait l’écriture.
– chaineformat : Elle contient des caractères ordinaires qui doivent être copiés tels
for(i=0;
quels, i<n;séquences
et des i++) d’échappement (introduites par le caractère %), décrivant la
{ dont doivent être écrits les paramètres param1, param2,... paramn.
manière
– param : est une expression délivrant
printf("%d\n",fprintf(fo, "%s %sune%d\n",
valeur à écrire.
Tabclient[i].nom,
Tabclient[i].prenom, Tabclient[i].code));
} rendue
Valeur
La fonction fprintf retourne le nombre de caractères écrits, ou une valeur négative
s’il y a eu une erreur d’entrée-sortie.
Lecture et Ecriture formatées sur fichiers
Lecture formatée : fscanf()
fscanf (FILE *stream , chaineformat , param1 , param2 , ... , paramn )
Paramètres
–FILE *fo;
flot-de-données : est de type pointeur vers FILE. Il pointe vers le fichier à partir
duquel
int se faitn=4;
i=0, la lecture.
– chaineformat : est une chaîne de caractères qui spécifie la forme de l’entrée
client Tabclient[20];
admissible dans flot-de-données.
– lesfo=fopen("testecrire",
parami : sont des pointeurs. "r");Ils pointent des variables dans lesquelles fscanf
while(fscanf(fo,
dépose les valeurs lues"%s
dans %s %d\n", Tabclient[i].nom,
flot-de-données, après les avoir converties en binaire.
Tabclient[i].prenom,
s'arrête &Tabclient[i].code)!=EOF)
si elle tombe au cours de sa lecture sur un espace, une tabulation ou une
entrée
i++;
Valeur rendue
fscanf retourne le nombre de param_i affectés. S’il y a eu rencontre de fin de
fichier ou erreur d’entrée-sortie avant toute affectation à un param_i, fscanf retourne
EOF.
Ecrire un programme C qui permet de stocker dans un fichier Texte les
valeurs d’un tableau de structure
Ecrire un programme C qui permet de lire à partir d’un fichier Texte les
valeurs d’un tableau de structure
struct test
{
char CH[20];
float PU;
int STK;
};
Même exercice avec une allocation dynamique:

Char *CH
Lecture et Ecriture sur fichiers binaire
Lecture/Ecriture binaire : fread()/fwrite()
int fwrite( void* C, int taille_element, int nb_elements, FILE* fic);
int fread( void* C, int taille_element, int nb_elements, FILE* fic);
Paramètres
– l’adresse de la zone mémoire où on veut (on a) stocké la valeur.
– la taille en octet d'un élément .
– le nombre d'éléments à Lire/Ecrire.
– le pointeur du fichier
Valeur rendue
renvoient le nombre d'éléments effectivement lus/écrits..
Accès non séquentiel binaire : fseek()/ftell()
La fonction ftell() : renvoie la position actuelle du curseur sous la forme d'un long :
long ftell(FILE *stream );
Paramètres
– le pointeur du fichier
Valeur rendue
Valeur de type long qui représente la position actuelle du curseur.
la fonction fseek() : permet de déplacer le curseur d'un certain

nombre de caractères (octets) indiqué par «deplacement » à partir de la
position indiquée par «origine ».:
int fseek(FILE* pointeurSurFichier, long deplacement, int origine);
Paramètres
 le pointeur du fichier
 nombre de déplacement du curseur (nbre d’octet). Peut être > = < à 0
 l’origine à partir duquel on effectue le déplacement.
o SEEK_SET : indique le début du fichier ;
o SEEK_CUR : indique la position actuelle du curseur ;
o SEEK_END : indique la fin du fichier.
Valeur rendue
0 si l’utilisation est réussie.
la fonction rewind() : renvoie le curseur au début de fichier. Cette

fonction est équivalente à utiliser fseek pour nous renvoyer à la position
0 dans le fichier.
void rewind(FILE* pointeurSurFichier);
Paramètres
 le pointeur du fichier
Ecrire un programme C qui permet de stocker dans un fichier binaire
les valeurs d’un tableau de structure
Ecrire un programme C qui permet de lire à partir d’un fichier binaire

les valeurs d’un tableau de structure
struct test
{
char CH[20];
float PU;
int STK;
};
Lecture et Ecriture formatées sur une chaine
Ecriture formatée : sprintf()
main()
int sprintf (char
{ *chaine , format , param1 , param2 , ... , paramn )
char CH[20], T[20], x;
La fonction sprintf() réalise le même traitement que la fonction fprintf(), avec
int y;
la différence que les caractères émis par sprintf() sont écrits dans le tableau
printf("saisir
de caractères chaîne. Un nullun
estchar
écrit :dans
"); chaîne en fin de traitement.
scanf("%c", &x);
getchar();
printf("saisir une chaine : ");
gets(T);
printf("saisir entier : ");
scanf("%d", &y);
printf("la chaine formatee est : ");
sprintf(CH, "%c/%d/%s", x, y, T);
puts(CH);
}
Lecture formatée : sscanf()
sscanf (char *chaine , chaineformat , param1 , param2 , ... , paramn )
La fonction sscanf réalise le même traitement que la fonction fscanf, avec la

différence que les caractères lus par sscanf ne sont pas lus depuis un fichier,
mais du tableau de caractères chaîne.
Valeur renvoyée
Scanf() retourne le nombre de param-i affectés c-a-d le nombre de
paramètre qui sont conforme à la chaine format.
Les directives pour les lectures formatées
Caractères blancs :il s’agit des six caractères suivants : espace, tab, line
feed, new line, vertical tab et form feed. Ce sont des caractères très utilisés
dans les lectures formatées.
Les Directives (format) :

une suite de caractères blancs qui est un modèle d’un nombre
quelconque de caractères blancs.
une suite de caractères ordinaires qui est un modèle pour elle-même.

Exemple : la chaîne « -/- » est un modèle de la seule chaîne « -/- ».
des séquences d’échappement introduites par le caractère %. Exemple

« %d\n »
Les directives pour les lectures formatées
main()
{
FILE *fi;
char x[20], y[20], *z="ABCD xyz";
sscanf(z, "%s %s", x,y); // ou sscanf(z, "%s%s", x,y);
printf("%s\n", x);
printf("%s", y); main()
} {
FILE *fi;
char x[20], y[20], *z="ABCD */* xyz";
sscanf(z, "%s */* %s", x,y); // ou sscanf(z, "%s%s", x,y);
printf("%s\n", x);
printf("%s", y);
}
Lecture et Ecriture formatées sur une clavier
Affichage formatée sur Ecran : printf()
int printf (chaineformat , param1 , param2 , ... , paramn )
Lecture formatée à partir du clavier scanf()
Int scanf (chaineformat , param1 , param2 , ... , paramn )
Valeur renvoyée
Scanf() retourne le nombre de param-i affectés c-a-d le nombre de
paramètre qui sont conforme avec la chaine format.
On dira qu’une chaîne format est conforme à un modèle quand elle
appartient à l’ensemble des chaînes décrites par le modèle. Exemple :
123 est conforme au modèle %d.
printf() retourne le nombre de caractère écrit.

Fin Programme
Les constantes nommées
les énumérations
Les #define
On peut définir une constante nommée avec l’instruction #define.
Si par exemple on veut remplacer dans toute la suite du programme, toute
nouvelle occurrence de Pi par 3.14159 on peut écrire :

#define PI 3.14159
Les énumérations
On peut aussi définir des constantes nommées de la manière suivante :
enum { liste-d’identificateurs }
liste-d’identificateurs : des constantes de type « int »

les énumérations
Les #define
On peut définir une constante nommée avec l’instruction #define.
Si par exemple on veut remplacer dans toute la suite du programme, toute
nouvelle occurrence de Pi par 3.14159 on peut écrire :

#define PI 3.14159
Les énumérations
On peut aussi définir des constantes nommées de la manière suivante :
enum { liste-d’identificateurs }
liste-d’identificateurs : des constantes de type « int »

les énumérations
Déclaration de variable de type énumérations
enum test {a=2, b=4, c=6};

main()
{
enum test x1, x2, x3;
int y;
x1=a;
x2=b;
x3=c;
y=x1+x2+x3;
printf("y= %d", y);}
Les Unions
Il est parfois nécessaire de manipuler des variables auxquelles on désire
affecter des valeurs de type différents.
union nombre
{
int i;
float f;
}
union nombre N;
N . a = 10;
N . F = 3.14;
Complexité
 Comment évaluer les performances d'un algorithme ?
 différents algorithmes ont des couts différents en

termes de temps d'exécution (nombre d'opérations
effectuées par l'algorithme), taille mémoire (taille
nécessaire pour stocker les différentes structures de
données pour l'exécution).
 Ces deux concepts sont appelés la complexité en

temps et en espace de l'algorithme.
Complexité
 La complexité algorithmique permet de mesurer les
performances d'un algorithme et de le comparer avec
d'autres algorithmes réalisant les mêmes
fonctionnalités.
 La complexité algorithmique est un concept fondamental

pour tout programmeur, elle permet de déterminer si un
algorithme a et meilleur qu’un algorithme b et s’il est
optimal ou bien il ne doit pas être utilisé
*Complexité
Le temps d'exécution d'un programme dépend :
1. du nombre de données,
2. de la taille du code,
3. du type d'ordinateur utilisé (processeur, mémoire),
4. de la complexité en temps de l'algorithme.
 Soit n la taille des données du problème et T(n) le temps

d'exécution de l'algorithme. On distingue :
o Le temps du plus mauvais cas Tmax(n) qui correspond
au temps maximum pris par l'algorithme pour un
problème de taille n
o Comportement de T(n) pour un n est grand.
*Complexité
Règles générales :
1. le temps d'exécution TE d'une affectation, d’une

incrémentation, d’une opération élémentaire ou d'un test
est considéré comme constant c.
2. Le temps d'une séquence d'instructions est la somme
des TE des instructions qui la composent.
3. le temps d'un branchement conditionnel est égal au TE
du test plus le max des deux TE correspondant aux
deux alternatives (dans le cas d'un temps max).
4. Le temps d'une boucle est égal au coût du test de
sortie de boucle plus le corps de la boucle.
Exemple-1: Calcul d'une somme
{début}
R <-- 0 aff : temps d’affectation
i <-- 1 test : temps du test logique
TantQue i <= n Faire som : tems de la somme
R <-- R+T[i] inc : temps d’incrémentation
i <-- i+1
FinTantQue
{fin}

L’algorithme est donc asymptotiquement linéaire en n.

Notion de landau O(…)
Définition
Soient f et g deux fonctions dans IR+*

Exemple-2: Calcul d'une somme
R <-- 0
i <-- 1 aff : affectation
TantQue i <= N Faire test : test
R <-- R+T[i] som : somme
Si R>1000 Alors inc : incrémentation
R<-- 2*R mult : multiplication
FinSi
i <-- i+1
FinTantQue

Exemple-3 : calcul du factorielle (fonction récursive)
Fonction factorielle(n :naturel) : naturel

Début
Si n  0 alors
res  1 test: temps test
Sinon mult: multiplication
res  n*factorielle(n-1)
Finsi
Renvoyer (res)
Fin
Dans le cas d’un traitement récursif les deux branchements vont être
exécutés
T(n) = test + aff + mult + T(n-1)
T(n) = (n+1)*test+ n*aff + n*mult = (test + aff + mult)*n + test

Complexité linéaire O(n)

Exemple-4 (deux boucles imbriquées).
B<--0 aff: affectation
i <--1 som: somme
Pour i <-- 1 à n Faire test: test
B<--B+2 mult: multiplication
Pour j <-- 1 à m Faire inc: incrémentation
T[i,j] <-- (1+T[i,j])*B
Suivant j
Suivant i

Cette algorithme à une complexité O(n2).
Exemple-5 algorithme de Recherche du Max
Var : X, i, Max : entiers
Ecrire(« donner la valeur », 0)
Lire X c1:affectation
Max  X c2: incrémentation
i1 c3: test
Tant que (X <> -1) faire
si(X > Max) alors
Max  X
FinSi
Ecrire(« donner la valeur », i)
lire X
ii+1 La complexité est en O(n)
Fin tant que
Ecrire(‘’Max=‘’, Max)

Exemple-7 Fonction Echange
1. Fonction échanger (E/S a, b : Entier)

2. Déclaration T : Entier
3. Début
4. T a
5. ab
6. bT
7. fin
T(n) = 3*aff (aff : affectation)
Complexité constante en O(1)

*Comparaison entre les
algorithmes
Algorithmes de recherche linéaire
Fonction Recherche (T(), X, Nb)
Pire des cas, élément
Var i, R : entier
cherché absent du tableau
i0
On va effectuer n tests:
Tant que (i<=Nb-1 ET T(i) <> X) Alors
T(n)=n*C
i  i+1
complexité linéaire : O(n)
Fin tant que
Si (i = Nb) alors
Ecrire (« le nombre est introuvable ») Le temps d’exécution est
Sinon proportionnel aux
Ecrire (« le nombre de trouve dans l’indice ») nombres de données.
Renvoyer (i) Naïf il existe un
Fin algorithme plus efficace
*Comparaison entre les
algorithmes
Fonction Recherchedico(T() : entier, Nb : T(n) = 3*aff + test +T(n/2)
entier, X : entier): entier T(n) = C+T(n/2)
Var m : entier On pose n=2k  log(n)=k*log(2)
Min  0; T(2k) = C+T(2k-1)
Max  Nb-1; T(2k) = C+C+T(2k-2)
m  (Max+Min)/2; T(2k) = C+C+C+T(2k-3)
Tant que (T(m) <> X) faire T(2k) = C+C+C+…..+C+T(2k-k)
Si (T(m) > X) Alors T(2k) = k*C+T(1)
Max  m-1 T(n) = C*log(n)/log(2)+T(1)
Sinon T(n) ~ C’*log(n)
Min  m+1
Fin Si La complexité de l’algorithme est
P=(Max+Min)/2; logarithmique
Fin tant que La complexité est en O(log(n))
Renvoyer (m);
Complexité en O(log(n))
2.5
1.5
T(n)
0.5
0
1 9 17 25 33 41 49 57 65 73 81 89 97 105 113
Complexité en O(n)
140
Complexité en O(n2)) 120

100
16000
80
14000
T(n)
12000 60
10000 40
T(n)
8000 20
6000 0
4000 1 17 33 49 65 81 97 113 129 145 161 177 193 209 225
2000 n
0
1 17 33 49 65 81 97 113129145161177193209225
n
Les algorithmes usuels peuvent être classés en un certain nombre de
grandes classes de complexité.
 Les algorithmes sous-linéaires, dont la complexité est en général en

O(logn). sont considérés comme les plus rapides. C'est le cas de la
recherche d'un élément dans un ensemble ordonné fini de cardinal n.
 Les algorithmes linéaires en complexité O(n) ou en O(nlogn) sont

considérés comme rapides, comme l'évaluation de la valeur d'une
expression composée de n symboles ou les algorithmes optimaux de tri.
 Plus lents sont les algorithmes de complexité située entre O(n2) et O(n3),
c'est le cas de la multiplication des matrices et du parcours dans les
graphes.
 Au delà, les algorithmes polynomiaux en O(nk) pour k > 3 sont

considérés comme lents, sans parler des algorithmes exponentiels (dont
la complexité est supérieure à tout polynôme en n) que l'on s'accorde à
dire impraticables dès que la taille des données est supérieure à quelques
dizaines d'unités.
Ordre de grandeur du temps nécessaire à l'exécution
d'un algorithme d'un type de complexité
Conclusion
Qualités d'un algorithme :
1. Maintenable (facile à comprendre, coder, déboguer),

2. Rapide
Conseils :
1. Privilégier le point 2 sur le point 1 uniquement si on
gagne en complexité.
2. «ce que fait» l'algorithme doit se lire lors d'une lecture
rapide : Une idée par ligne.
3. Faire également attention à la précision, la stabilité et la
sécurité.
La rapidité d'un algorithme est un élément essentiel pour
définir les qualités de celui-ci.
Méthodologie
Comment trouver un algorithme?
 Prenez un exemple
 tentez de voir intuitivement comment résoudre le problème.
 Tentez alors de généraliser ces opérations pour obtenir les

principes généraux de votre algorithme.
 traduisez ces principes en pseudo-code.
 Si besoin, décomposez le problème en sous problèmes que

vous traitez indépendamment,
Deb
Next
Next
Note Next
Note
Last Note
Last
Last
Fin
Next
Note
Last

Algo 1&2 Complet

Transféré par

Droits d'auteur :

Formats disponibles

Algo 1&2 Complet

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Algo 1&2 Complet

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre-2 Algorithmique et programmation C

Les Variables, les pointeurs, les constantes,

o LDA : Langage de Description d’Algorithme

 Le programme informatique est à la traduction du LDA à

Raisonnement logique Programme

Langage traduisant le LDA de

Méthode 1 : Recherche séquentielle

– Plusieurs algorithme peuvent donner le

Déclaration des var

Une VARIABLE possède :

Un nom (identificateur) : Un variable apparaît en programmation sous

Structure générale d’un programme C

Un programme C comporte toujours une fonction principale dans

La syntaxe de cette fonction principale est donnée par :

Pendant l’exécution d’un programme C, Le compilateur a besoin d’être

Ces informations sont contenues dans des fichiers d’extension « .h ».

Sa syntaxe est la suivante :

La directive #include permet d’incorporer dans le fichier source le code du

Nom fichier Rôle

Une variable est caractérisée par :

 Un nom : Une variable apparait en programmation sous un nom de

 Un type : On utilise différents types de variables (entiers, réels, chaine

 Une adresse : C’est l’emplacement dans la mémoire de l’ordinateur, ou

Cette données peut représenter un entier

Les attributs de précision sont «short » et « long ».

Type de données Type de codage Mémoire occupée

Sont désigné par « char ». Il contient le code de n’importe quel caractère

Type de données Type de codage Mémoire occupée

Type de données Type de codage Mémoire occupée

sizeof(type) : Fonction permettant de renvoyer la taille occupée dans

char Caractère 1 0 à 255

unsigned short int Entier court non signé 2 0 à 65 535

2 (sur processeur 16 bits) -32768 à 32767

2 (sur processeur 16 bits) 0 à 65 535

-2 147 483 648 à 2 147

float Flottant (réel) 4 3.4*10-38 à 3.4*1038

#include <stdio.h> #include <stdio.h>

Une constante flottante se présente sous la forme d'une partie entière, un

Les constantes de type caractère se note entre apostrophes: 'a' '2'

Les caractères non imprimables

L’opérateur « & » appliqué à une variable délivre l’adresse de celle-ci ; cette

G = &P *G = P = &i = 60FF08 **G=*P= i = 3

Toutes les opérations avec les pointeurs tiennent compte automatiquement du

 l'addition d'un entier à un pointeur. Le résultat est un pointeur de

Après on peut lui affecter :

 l’adresse du premier octet d’une zone mémoire réservée au cours de

Allocation Mémoire (Memory ALLOCation malloc())

#include <stdlib.h> On peut donc affecter directement

L'opération par laquelle on attribue une valeur à une variable s'appelle

#include <stdio.h> #include <stdio.h>

a=6 b=1 a=6 b=0

représentation à partir Scanf() représentation

Pour réaliser ces transformations ces fonctions sont guidées par des

Par exemple, un format du type %x signifie d’une part que la variable

Le premier argument une chaîne de caractères qui spécifie à la fois

L'appel de printf se présente comme ceci :

printf (‘’format’’, liste_d'expressions )

D'une manière générale, l'appel de scanf se présente ainsi :

x=getchar() joue le même rôle que : scanf(« %c », &x).

"putchar()" fonction écrit le caractère passé en argument sur la sortie standard

float Flottant (réel) 4 3.410-38 à 3.41038

&T[i][j][k]= ((T+i) + j) + k = T[i][j] + k