Programmation

et structures de données en C
cours 1: Introduction et rappels

Jean-Lou Desbarbieux, Stéphane Doncieux

et Mathilde Carpentier
LU2IN018 SU 2021/2022
Sommaire

Introduction
Présentation
Évaluation
Calendrier
Biblio
Historique rapide

Rappels au travers d’exemples

Pointeurs et gestion de la mémoire

Structures

Listes chaı̂nées
Présentation du module

I Module avancé (niveau 200) de 3 ECTS

I Objectifs principaux :
I Consolidation des notions de gestion explicite de la
mémoire
I Structure de données autoréférentielles : listes, arbres, ...
I Bonnes habitudes de programmation (tests, structuration,
débogage)
I Entrées/sorties et manipulation de fichiers
I Introduction à la généricité
I Itinéraire :
I Notions d’algorithmique

Pensez à vous inscrire...

... si ce n’est pas encore fait
Évaluation

I 50% pour l’examen final

I 25% pour le partiel
I 20% pour une évaluation liée aux TME
I 5% de participation
Les annales des examens et partiels sont sur le site de l’UE.
Attention, l’UE a évolué au cours des dernières années et si le
programme est resté globalement le même, il y a tout de même
eu quelques changements. Un de ces changements est que,
avant 2015, les documents étaient autorisés, depuis cette date,
seul le memento est autorisé.
Calendrier

I 6 semaines de cours, 6 semaines de TD, 6 semaine de

TME
I Cours une semaine sur 2
I TME une semaine et TD l’autre, sur le même créneau
horaire
I Les TME commencent cette semaine !
I Les TD commencent la semaine du 27 septembre
I Le partiel aura lieu la semaine du 8 novembre
I L’examen aura lieu la semaine du 10 janvier

Tutorat : 1 séance de 2h par semaine et un forum, voir

annonces sur Moodle.
Calendrier (à titre indicatif)

Séance 1. Rappels pointeurs/structures/listes chaı̂nées

Séance 2. Débogage, compilation séparée et outils de
développement
Séance 3. Chaı̂nes de caractères et entrées/sorties
Séance 4. Arbres
Séance 5. LibC et introduction à la généricité
Séance 6. Conclusion et Révisions
Bibliographie et outils
I Le langage C : norme ANSI. Brian W. Kernighan & Denis
M. Ritchie, Dunod
I Programmer en langage C. Claude Delannoy, Eyrolles
I C : a reference manual. Samuel P. Harbison & Guy L.
Steele Jr., Prentice Hall
I C : a software engineering approach. Peter A. Darnell &
Philip E. Margolis, Springer
I ...
Environnement : Linux.
Outils informatiques utilisés :
I éditeurs : emacs/vi/gvim/gedit
I compilateur : gcc
I débogueur : gdb, ddd
I automatisation de la compilation : Makefile
Le Langage C : historique
I Le langage C a été inventé en 1972 par Dennis Ritchie et
Ken Thompson (AT&T Bell Laboratories) pour réécrire
Unix et développer des programmes sous Unix.
I En 1978, Brian Kernighan et Dennis Ritchie publient la
définition classique du C dans le livre The C Programming
language .
I C est une norme ANSI (ANSI-C) depuis 1989 et un
standard ISO depuis 1990, standard étendu en 1999
(C99), 2011 (C11) et en 2018 (C18).
I Toutes les distributions Linux fournissent des compilateurs
C.
Caractéristiques du langage :
I impératif
I bas-niveau
I typé
Rappels au travers
d’exemples
Exemple de programme (1)

Fichier ”HelloWorld.c” (éditeur de texte)

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

i n t main ( v o i d ) {
p r i n t f ( ” H e l l o Sorbonne ! \ n ” ) ;
return 0;
}

Compilation (dans un terminal)

gcc -o HelloWorld HelloWorld.c

Exécution (dans un terminal)

./HelloWorld
Exemple de programme (2)
# i n c l u d e <s t d i o . h>

# d e f i n e NBGROUPES 13

i n t groupes [NBGROUPES] = { 2 7 , 24 , 30 , 25 , 28 , 29 , 30 , 29 , 30 ,
30 , 29 , 30 , 28};
void afficher groupes ( void ) {
int i ;
f o r ( i =0; i <NBGROUPES; i ++) {
p r i n t f ( ” Groupe %d : %d e t u d i a n t s \n ” , i , groupes [ i ] ) ;
}
}
i n t t o t a l e t u d i a n t s ( void ) {
int i ;
i n t nb =0;
f o r ( i =0; i <NBGROUPES; i ++) {
nb+=groupes [ i ] ;
}
r e t u r n nb ;
}
i n t main ( v o i d ) {
afficher groupes ( ) ;
p r i n t f ( ” Nombre t o t a l d ’ e t u d i a n t s : %d\n ” , t o t a l e t u d i a n t s ( ) ) ;
return 0;
}
Exemple de programme (3)
# i n c l u d e <s t d i o . h>
# d e f i n e NBGROUPES 13
# d e f i n e MAXSIZE 30
i n t groupes [NBGROUPES] = { 2 7 , 24 , 30 , 25 , 28 , 29 , 30 , 29 , 30 ,
30 , 29 , 30 , 28};
i n t a j o u t e r e t u d i a n t ( void ) {
i n t i =0;
w h i l e ( i <NBGROUPES) {
i f ( groupes [ i ]<MAXSIZE ) {
groupes [ i ] + + ;
return i ;}
i ++;
}
r e t u r n −1;
}
i n t main ( v o i d ) {
i n t g= a j o u t e r e t u d i a n t ( ) ;
i f ( g==−1) {
p r i n t f ( ” Tous l e s groupes s o n t p l e i n s , l ’ a j o u t a echoue\n ” ) ;
}
else {
p r i n t f ( ” L ’ e t u d i a n t . e a e t e a j o u t e . e dans l e groupe %d\n ” , g ) ;
}
return 0;
}
Exemple de programme (4)
void a f f i c h e r f i l i e r e ( i n t n ) {
p r i n t f ( ” Le groupe %d e s t ( m a j o r i t a i r e m e n t ) dans l a f i l i e r e : ” , n ) ;
switch ( n ) {
case 1 : case 3 : case 4 : case 5 : case 6 : case 9 :
p r i n t f ( ” mono\n ” ) ;
break ;
case 2 :
p r i n t f ( ” majeure \n ” ) ;
break ;
case 7 :
case 1 0 :
case 1 3 :
p r i n t f ( ” double majeure \n ” ) ;
break ;
case 8 :
p r i n t f ( ” double cursus \n ” ) ;
break ;
case 1 1 :
p r i n t f ( ” mineur \n ” ) ;
break ;
case 1 2 :
p r i n t f ( ”DANT\n ” ) ;
break ;
default :
p r i n t f ( ”< f i l i e r e inconnue !> ” ) ;
}
Pointeurs et gestion de la
mémoire
Pointeurs et gestion dynamique de la mémoire
Chaque variable occupe un certain espace en mémoire (en
couleur ce qu’il faut retenir)
Type Signification Taille (o) Plage de valeurs
char Caractère 1 -128 à 127
unsigned char Caractère 1 0 à 255
short int Entier court 2 -32768 à 32767
uns. short int Entier court non s. 2 0 à 65535
int Entier 2 (16 b) -32768 à 32767
4(32 et 64 b) -2 147 483 648
à 2 147 483 647
unsigned int Entier non signé 2 (16 b) 0 à 65 535
4 (32 et 64 b) 0 à 4 294 967 295
long int Entier long 4 -2 147 483 648
à 2 147 483 647
8 (64 b) -9 223 372 036 854 775 080
à 9 223 372 036 854 775 807
uns. long int Entier long non s. 4 0 à 4 294 967 295

Type Signification Taille (o) Plage de valeurs

float Simple précision 4 +/- 1.175494e-38 à 3.402823e+38
double Double précision 8 +/- 2.225074e-308 à 1.797693e+308
long double Double préc. long 12 +/- 3.362103e-4932 à 1.189731e+4932
Notion de pointeur (rappel)
I Chaque variable correspond à un bloc mémoire d’une taille connue et à
un emplacement donné.
I Cet emplacement est l’adresse de la variable.
I Un pointeur est une variable dont le contenu est une valeur qui est
elle-même une adresse mémoire.
I Déclaration : on ajoute “*” au type de la donnée pointée. Exemples :
int *i; char *c;
I L’adresse d’une variable est récupérée grâce à l’opérateur “&” :
i n t i =2;
i n t ∗ l ; / ∗ l e s t un p o i n t e u r s u r e n t i e r ∗ /
l =& i ; / ∗ l p o i n t e s u r i ∗ /

I La valeur stockée en mémoire à l’adresse indiquée par un pointeur peut

être récupérée grâce à l’opérateur “*” (on parle de déréférenciation).
Ex :
i n t i =2;
i n t ∗ l =& i ; / ∗ l e s t un p o i n t e u r s u r i ∗ /
∗ l =3; / ∗ l a v a l e u r de i passe a 3 ∗ /

I NULL (ou 0) est une valeur spéciale qui ne pointe pas sur une zone
mémoire valide (utilisé pour indiquer qu’un pointeur n’est pas encore
Exemple

0x1234 2 i
i n t i =2 , j =36 , k =124; 0x1238 36 j
i n t ∗ l =& i ; 0x123C 124 k
0x1240 0x1234 l
Dans cet exemple, l contient l’adresse de la variable i.
Les pointeurs de pointeurs de ...

i n t i =3; 0x1234 3 i
i n t ∗ j =& i ; 0x1238 0x1234 j
i n t ∗∗ k=& j ; 0x123C 0x1238 k
k est un pointeur de pointeur sur entier. Il contient donc
l’adresse d’une variable contenant l’adresse d’une variable de
type int.
Il est également possible de définir des pointeurs de pointeurs
de pointeurs sur un type donné et ainsi de suite...
Tableaux & Pointeurs

Une référence à un tableau est équivalente à un pointeur

constant sur son premier élément !
int a[10];
i n t ∗b=a ;

a ⇐⇒ b ⇐⇒ &a[0] ⇐⇒ &b[0]
La notation avec [] est équivalente à l’addition de l’indice :
int a[10];
i n t ∗b=a ;

a[2] ⇐⇒ ∗(a + 2) ⇐⇒ b[2] ⇐⇒ ∗(b + 2)

Passage de paramètres à une fonction

I Toujours par copie ... mais copie de quoi ?

I Copie du contenu de la variable transmise

void f ( i n t n ) {
/ ∗ n e s t une v a r i a b l e i n t e r n e a f i n i t i a l i s e e
avec l a v a l e u r t r a n s m i s e a l a f o n c t i o n .
M o d i f i e r n n ’ a aucun impact en dehors de f .
∗/
n =5;
}

i n t i =4;
f ( i );
/ ∗ i vaut t o u j o u r s 4 ∗ /
Passage de paramètres à une fonction
I Toujours par copie ... mais copie de quoi ?
I Copie du contenu de la variable transmise

v o i d f ( i n t ∗p ) {
/ ∗ p e s t une v a r i a b l e i n t e r n e a f i n i t i a l i s e e
avec l a v a l e u r t r a n s m i s e a l a f o n c t i o n
M o d i f i e r p n ’ a aucun impact en dehors de f . . .
mais m o d i f i e r ∗p a un impact . . .
∗/
∗p =5;
}

i n t i =4;
f (& i ) ;
/ ∗ i v a u t maintenant 5 ∗ /
Passage de paramètres à une fonction

I Toujours par copie ... mais copie de quoi ?

I Copie du contenu de la variable transmise

void f ( i n t t [ 1 0 ] ) {
/ ∗ t e s t un t a b l e a u , i l e s t donc e q u i v a l e n t
a un p o i n t e u r . . . donc m o d i f i e r ce s u r q u o i
i l p o i n t e a un impact hors de f
∗/
t [3]=42;
}

i n t tab [10]={0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9};

f ( tab ) ;
/ ∗ t a b [ 3 ] v a u t maintenant 42 ∗ /
Allouer dynamiquement la mémoire

#include <stdlib.h>

void *malloc(size t taille)

I Argument : taille en octets
I size t : entier non signé
I Valeur renvoyée de type void *
I Déclaré dans stdlib.h
I ATTENTION : la zone mémoire allouée n’est pas
initialisée...
Autres fonctions d’allocation : realloc
# i n c l u d e < s t d l i b . h>
v o i d ∗ r e a l l o c ( v o i d ∗ adr , s i z e t t a i l l e ) }
I Changement de taille d’un emplacement mémoire
précédemment alloué
I La nouvelle taille est taille, elle peut être inférieure ou
supérieure
I Les octets conservés de l’ancien tableau sont identiques
I L’emplacement en mémoire peut changer
I Exemple :
i n t n=10 ,m, ∗ t a b = m a l l o c ( n∗ s i z e o f ( i n t ) ) , ∗ tab2 ;
. . . / ∗ code i n i t i a l i s a n t m ∗ /
tab2= r e a l l o c ( tab ,m) ;
i f ( ! tab2 ) {
p r i n t f ( ” E r r e u r de r e a l l o c a t i o n \n ” ) ;
exit (1);
}
t a b =tab2 ;
...
Libération de la mémoire : free

# i n c l u d e < s t d l i b . h>
v o i d f r e e ( v o i d ∗ adr ) ;
I Libération de la mémoire
I Libère, d’un coup, un bloc précédemment alloué par
malloc, calloc ou realloc
I Il n’est pas possible de ne libérer la mémoire que
partiellement
I free(NULL) ne fait rien
I Libérer deux fois de suite la mémoire conduit à un
comportement indéterminé : généralement un seg fault...
Copie de blocs mémoire : memcpy

# i n c l u d e < s t r i n g . h>
v o i d ∗memcpy ( v o i d ∗s1 ,
c o n s t v o i d ∗s2 , s i z e t n ) ;
I Copie n octets à partir de l’adresse contenue dans le
pointeur s2 vers l’adresse stockée dans s1
I Remarque : s2 doit pointer vers une zone mémoire de
taille suffisante.
I la fonction renvoie la valeur de s1
Structures
Vous avez dit structures ?
I Les structures sont des types composés définis par le
programmeur.
I Les structures regroupent à l’intérieur d’une même variable
des variables sémantiquement liées. Exemple : une fiche
d’un répertoire contient le nom, le prénom, l’adresse, le
numéro de téléphone...

Exemple, point dans un espace 3D :

struct point {
float x;
float y;
float z;
};
struct p o i n t p1 ;
p1 . x = 12.0;
p1 . y = 24.2;
p1 . z = 42.0;
Déclaration :
s t r u c t <nom de type>
{
type1 var1 ;
type2 var2 ;
...
typen varn ;
};

Utilisation :
I Déclaration d’une variable du type défini
struct <nom de type> <nom de variable>;
Exemple : struct point p1;
struct point *pp1;
ATTENTION, il faut bien préciser le mot-clé struct
I Récupération d’un champ :
var.<nom du champ>
Exemple :p1.x=44.20;
pvar-><nom du champ>
Exemple :pp1->x=44.20;
typedef

I Définition de types synonymes. Exemple :

typedef i n t e n t i e r ;
e n t i e r i =3;
I cas des tableaux :
typedef i n t vect [ 3 ] ;
v e c t v1 , v2 ;
I cas des struct
typedef s t r u c t point { i n t x ; i n t y ;} point ;
point A;
Initialisation & affectation

Initialisation semblable à celle de tableaux :

typedef s t r u c t ma struct {
float x;
char c ;
} ma struct ;
m a s t r u c t s={ 1 . 1 2 , ’ a ’ } ;

Possibilité de copier directement une structure par affectation :

m a s t r u c t s1 ={1.12 , ’ a ’ } , s2 ;

équivalent à s2 . x=s1 . x ;
s2=s1 ;
s2 . c=s1 . c ;
ATTENTION aux pointeurs ...
Tableaux et structures

Tableaux dans une structure

s t r u c t personne {
char nom [ 3 0 ] ;
char prenom [ 3 0 ] ;
unsigned i n t nb commande ;
unsigned i n t n commande [ 1 0 ] ;
};
...
s t r u c t personne c l i e n t 1 ={ ” Dupond ” , ” A l b e r t ” , 0 ,
{0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0}};
...
c l i e n t 1 . n commande [ c l i e n t 1 . nb commande ] = 3406;
c l i e n t 1 . nb commande ++;

Tableaux de structure
s t r u c t personne c l i e n t s [ 1 0 0 ] ;
...
c l i e n t s [ 2 0 ] . n commande [ c l i e n t s [ 2 0 ] . nb commande ] = 4807;
c l i e n t s [ 2 0 ] . nb commande ++;
Structures dans une structure

s t r u c t date {
unsigned char j o u r ;
unsigned char mois ;
unsigned i n t annee ;
};

s t r u c t personne {
char nom [ 3 0 ] ;
char prenom [ 3 0 ] ;
s t r u c t date d a t e n a i s s a n c e ;
};
...
s t r u c t personne c l i e n t ={ ” Dupond ” , ” A l b e r t ” ,
{24 ,5 ,1950}};
i f ( c l i e n t . d a t e n a i s s a n c e . annee>1940) {
...
}
Structure et pointeurs
t y p e d e f s t r u c t personne {
char ∗ nom ;
char ∗ prenom ;
} personne ;

personne p1 , p2 ;

p1 . nom = ( char ∗ ) m a l l o c ( 7 + 1 ) ;
s t r c p y ( p1 . nom , ” Deckard ” ) ;

p1 . prenom = ( char ∗ ) m a l l o c ( 4 + 1 ) ;
s t r c p y ( p1 . prenom , ” Rick ” ) ;

p2=p1 ; / / c e l a f a i t q u o i ?

p r i n t f ( ” p2 . nom=%s p2 . prenom=%s\n ” , p2 . nom , p2 . prenom ) ;

f r e e ( p1 . nom ) ;
f r e e ( p1 . prenom ) ;

/ / Quel e s t l e r e s u l t a t de c e t appel ?
p r i n t f ( ” p2 . nom=%s p2 . prenom=%s\n ” , p2 . nom , p2 . prenom ) ;
Listes chaı̂nées
Listes chaı̂nées : introduction
Principe :
I stockage d’un ensemble d’éléments
I chaque élément contient l’emplacement du suivant

Avantages par rapport aux tableaux :

I insérer un élément sans avoir avoir à recopier la suite du
tableau,
I retirer un élément sans avoir avoir à recopier la suite du
tableau,
I ne pas nécessiter l’utilisation de mémoire contiguë,
I permet de faire varier dynamiquement la taille,

Inconvénients :
I prend plus de place qu’un tableau
I pas d’accès immédiat à un élément
Structure de liste

typedef s t r u c t un element
{
i n t data ;
s t r u c t un element ∗ suivant ;
} Un element ;

ou bien :
typedef s t r u c t u n e l e m e n t ∗ P un element ;

typedef s t r u c t un element
{
i n t data ;
P un element s u i v a n t ;
} Un element ;
Création d’un élément

P un element c r e e r e l e m e n t ( i n t v )
{
P un element e l ;

e l = ( P un element ) m a l l o c ( s i z e o f ( Un element ) ) ;
i f ( e l == NULL ) r e t u r n NULL ;
e l−>data=v ;
e l−>s u i v a n t = NULL ;
return el ;
}
Déclaration d’une liste :
P un element m a l i s t e = NULL ;

Insertion en début de liste

P un element i n s e r e r e l e m e n t d e b u t ( P un element p l i s t e ,
P un element e l )
{
e l−>s u i v a n t = p l i s t e ;
return el ;
}
Insertion en fin de liste

P un element i n s e r e r e l e m e n t f i n ( P un element p l i s t e ,
P un element e l )
{
P un element p l = p l i s t e ;

i f ( p l i s t e == NULL )
return el ;

w h i l e ( p l−>s u i v a n t )
{
p l = p l−>s u i v a n t ;
}
p l−>s u i v a n t = e l ;

return pliste ;
}
Suppression d’un élément dans une liste
P un element s u p p r i m e r e l e m e n t ( P un element l i s t e ,
P un element ∗ e l ) {
i f ( ( ∗ e l )== l i s t e ) {
P un element n l =(∗ e l )−>s u i v a n t ;
free (∗ el ) ;
∗ e l =NULL ;
return nl ;
}
P un element tmp= l i s t e ;
w h i l e ( ( tmp ) && ( tmp−>s u i v a n t ! = ∗ e l ) ) {
tmp=tmp−>s u i v a n t ;
}
i f ( tmp−>s u i v a n t ==∗ e l ) {
tmp−>s u i v a n t = ( ∗ e l )−>s u i v a n t ;
free (∗ el ) ;
∗ e l =NULL ;
}
else {
p r i n t f ( ” A t t e n t i o n , e l n ’ e s t pas dans l a l i s t e ! \ n ” ) ;
}
return l i s t e ;
}