Sommaire

Introduction
Programmation Présentation
Évaluation
et structures de données en C
Calendrier
cours 1: Introduction et rappels Biblio
Historique rapide

Jean-Lou Desbarbieux, Stéphane Doncieux

Rappels au travers d’exemples
et Mathilde Carpentier
LU2IN018 SU 2023/2024
Pointeurs et gestion de la mémoire

Structures

Listes chaı̂nées

Présentation du module Évaluation

▶ Module avancé (niveau 200) de 3 ECTS

▶ Objectifs principaux :
▶ 50% pour l’évaluation finale
▶ Consolidation des notions de gestion explicite de la
mémoire ▶ 25% pour l’évaluation intermédiaire
▶ Structure de données autoréférentielles : listes, arbres, ... ▶ 25% pour une évaluation des TME (participation et
▶ Bonnes habitudes de programmation (tests, structuration,
mini-soutenances)
débogage)
▶ Entrées/sorties et manipulation de fichiers Les annales des examens et partiels sont sur le site de l’UE.
▶ Introduction à la généricité Attention, l’UE a évolué au cours des dernières années et si le
▶ Itinéraire : programme est resté globalement le même, il y a tout de même
▶ Notions d’algorithmique eu quelques changements. Un de ces changements est que,
avant 2015, les documents étaient autorisés, depuis cette date,
Pensez à vous inscrire... seul le memento est autorisé.

... si ce n’est pas encore fait

Calendrier Calendrier (à titre indicatif)

▶ 6 semaines de cours, 6 semaines de TD, 6 semaine de

TME
▶ Cours une semaine sur 2
Séance 1. Rappels pointeurs/structures/listes chaı̂nées
▶ TME une semaine et TD l’autre, sur le même créneau
Séance 2. Débogage, compilation séparée et outils de
horaire
développement
▶ Les TME commencent cette semaine ! Séance 3. Chaı̂nes de caractères et entrées/sorties
▶ Les TD commencent la semaine du 18 septembre Séance 4. Arbres
▶ L’évaluation intermédiaire aura lieu la semaine du 6 Séance 5. LibC et introduction à la généricité
novembre Séance 6. Conclusion et Révisions
▶ L’examen aura lieu la semaine du 18 décembre ou du 8
janvier

Foum d’aide : à venir, surveiller sur Moodle.

Bibliographie et outils Le Langage C : historique

▶ Le langage C a été inventé en 1972 par Dennis Ritchie et
▶ Le langage C : norme ANSI. Brian W. Kernighan & Denis
Ken Thompson (AT&T Bell Laboratories) pour réécrire
M. Ritchie, Dunod Unix et développer des programmes sous Unix.
▶ Programmer en langage C. Claude Delannoy, Eyrolles ▶ En 1978, Brian Kernighan et Dennis Ritchie publient la
▶ C : a reference manual. Samuel P. Harbison & Guy L. définition classique du C dans le livre The C Programming
Steele Jr., Prentice Hall language .
▶ C : a software engineering approach. Peter A. Darnell & ▶ C est une norme ANSI (ANSI-C) depuis 1989 et un
Philip E. Margolis, Springer standard ISO depuis 1990, standard étendu en 1999
▶ ... (C99), 2011 (C11) et en 2018 (C17), future version à venir
Environnement : Linux. (C23 en 2024 ?).
Outils informatiques utilisés : ▶ Toutes les distributions Linux fournissent des compilateurs
▶ éditeurs : emacs/vi/gvim/gedit C.
▶ compilateur : gcc Caractéristiques du langage :
▶ débogueur : gdb, ddd ▶ impératif
▶ automatisation de la compilation : Makefile ▶ bas-niveau
▶ typé
Comparaison de différents langages

Rappels au travers
d’exemples

Pereira, R., Couto, M., Ribeiro, F., Rua, R., Cunha, J., Fernandes, J. P., & Saraiva, J. (2017). Energy efficiency
across programming languages : how do energy, time, and memory relate ?. In Proceedings of the 10th ACM
SIGPLAN International Conference on Software Language Engineering (pp. 256-267).

Exemple de programme (1) Exemple de programme (2)

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

# d e f i n e NBGROUPES 12
Fichier ”HelloWorld.c” (éditeur de texte)
i n t groupes [NBGROUPES] = { 2 7 , 24 , 30 , 25 , 28 , 29 , 30 , 29 , 30 ,
# i n c l u d e <s t d i o . h> 30 , 29 , 30};
void afficher groupes ( void ) {
int i ;
i n t main ( v o i d ) { f o r ( i =0; i <NBGROUPES; i ++) {
p r i n t f ( ” H e l l o Sorbonne ! \ n ” ) ; p r i n t f ( ” Groupe %d : %d e t u d i a n t s \n ” , i , groupes [ i ] ) ;
}
return 0; }
} 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 ++) {
Compilation (dans un terminal) nb+=groupes [ i ] ;
gcc -o HelloWorld HelloWorld.c }
r e t u r n nb ;
}
Exécution (dans un terminal) i n t main ( v o i d ) {
./HelloWorld 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) Exemple de programme (4)
# i n c l u d e <s t d i o . h> void a f f i c h e r f i l i e r e ( i n t n ) {
# d e f i n e NBGROUPES 12 p r i n t f ( ” Le groupe %d e s t dans l a f i l i e r e : ” , n ) ;
# d e f i n e MAXSIZE 34 switch ( n ) {
i n t groupes [NBGROUPES] = { 2 7 , 24 , 30 , 25 , 28 , 29 , 30 , 29 , 30 , case 3 : case 6 :
30 , 29 , 30}; p r i n t f ( ” mono\n ” ) ;
i n t a j o u t e r e t u d i a n t ( void ) { break ;
i n t i =0; case 2 : case 7 : case 8 :
w h i l e ( i <NBGROUPES) { p r i n t f ( ” majeure \n ” ) ;
i f ( groupes [ i ]<MAXSIZE ) { break ;
groupes [ i ] + + ; case 1 : case 4 : case 5 :
return i ;} p r i n t f ( ” mono + double majeure / cursus \n ” ) ;
i ++; break ;
} case 9 :
r e t u r n −1; p r i n t f ( ”DANT + double majeure \n ” ) ;
} break ;
i n t main ( v o i d ) { case 1 2 :
i n t g= a j o u t e r e t u d i a n t ( ) ; p r i n t f ( ” double majeure \n ” ) ;
i f ( g== −1) { break ;
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 ” ) ; default :
} p r i n t f ( ”< f i l i e r e inconnue !> ” ) ;
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 ) ; }
} i n t main ( v o i d ) {
return 0; afficher filiere (3);
} return 0;
}

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
Pointeurs et gestion de la int Entier 2 (16 b)
4(32 et 64 b)
-32768 à 32767
-2 147 483 648

mémoire unsigned int Entier non signé 2 (16 b)

à 2 147 483 647
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) Exemple
▶ Chaque variable correspond à un bloc mémoire d’une taille connue et à
un emplacement donné.
▶ Cet emplacement est l’adresse de la variable.
▶ Un pointeur est une variable dont le contenu est une valeur qui est
elle-même une adresse mémoire.
▶ Déclaration : on ajoute “*” au type de la donnée pointée. Exemples :
int *i; char *c; 0x1234 2 i
▶ L’adresse d’une variable est récupérée grâce à l’opérateur “&” : i n t i =2 , j =36 , k =124; 0x1238 36 j
i n t i =2; i n t * l =& i ; 0x123C 124 k
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 * / 0x1240 0x1234 l
▶ La valeur stockée en mémoire à l’adresse indiquée par un pointeur peut Dans cet exemple, l contient l’adresse de la variable i.
ê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 * /
▶ 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
initialisé).

Les pointeurs de pointeurs de ... Tableaux & Pointeurs

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

constant sur son premier élément !
i n t i =3; 0x1234 3 i
i n t * j =& i ; 0x1238 0x1234 j int a[10];
i n t * * k=& j ; 0x123C 0x1238 k i n t * b=a ;

k est un pointeur de pointeur sur entier. Il contient donc a ⇐⇒ b ⇐⇒ &a[0] ⇐⇒ &b[0]

l’adresse d’une variable contenant l’adresse d’une variable de La notation avec [] est équivalente à l’addition de l’indice :
type int.
int a[10];
Il est également possible de définir des pointeurs de pointeurs
i n t * b=a ;
de pointeurs sur un type donné et ainsi de suite...
a[2] ⇐⇒ ∗(a + 2) ⇐⇒ b[2] ⇐⇒ ∗(b + 2)
Passage de paramètres à une fonction Passage de paramètres à une fonction

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

▶ Copie du contenu de la variable transmise ▶ Copie du contenu de la variable transmise

void f ( i n t n ) { void f ( i n t *p ) {
/ * 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 / * 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 . 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 . 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 . . .
*/
n =5; */
} * p =5;
}
i n t i =4;
f ( i ); i n t i =4;
/ * i vaut t o u j o u r s 4 * / f (& i ) ;
/ * i v a u t maintenant 5 * /

Passage de paramètres à une fonction Allouer dynamiquement la mémoire

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

▶ Copie du contenu de la variable transmise
#include <stdlib.h>
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 void *malloc(size t taille)
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 ▶ Argument : taille en octets
i l p o i n t e a un impact hors de f ▶ size t : entier non signé
*/ ▶ Valeur renvoyée de type void *
t [3]=42;
} ▶ Déclaré dans stdlib.h
▶ ATTENTION : la zone mémoire allouée n’est pas
i n t tab [10]={0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9}; initialisée...
f ( tab ) ;
/ * t a b [ 3 ] v a u t maintenant 42 * /
Autres fonctions d’allocation : realloc 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 * r e a l l o c ( v o i d * adr , s i z e t t a i l l e ) }
▶ Changement de taille d’un emplacement mémoire # i n c l u d e < s t d l i b . h>
précédemment alloué v o i d f r e e ( v o i d * adr ) ;
▶ La nouvelle taille est taille, elle peut être inférieure ou ▶ Libération de la mémoire
supérieure
▶ Libère, d’un coup, un bloc précédemment alloué par
▶ Les octets conservés de l’ancien tableau sont identiques
malloc, calloc ou realloc
▶ L’emplacement en mémoire peut changer
▶ Il n’est pas possible de ne libérer la mémoire que
▶ Exemple :
partiellement
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 * /
▶ free(NULL) ne fait rien
tab2= r e a l l o c ( tab ,m) ; ▶ Libérer deux fois de suite la mémoire conduit à un
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 ” ) ; comportement indéterminé : généralement un seg fault...
exit (1);
}
t a b =tab2 ;
...

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 ) ;
Structures
▶ Copie n octets à partir de l’adresse contenue dans le
pointeur s2 vers l’adresse stockée dans s1
▶ Remarque : s2 doit pointer vers une zone mémoire de
taille suffisante.
▶ la fonction renvoie la valeur de s1
 Déclaration :
Vous avez dit structures ?
s t r u c t <nom de type>
▶ Les structures sont des types composés définis par le {
type1 var1 ;
programmeur.
type2 var2 ;
▶ Les structures regroupent à l’intérieur d’une même variable ...
des variables sémantiquement liées. Exemple : une fiche typen varn ;
};
d’un répertoire contient le nom, le prénom, l’adresse, le
numéro de téléphone... Utilisation :
▶ Déclaration d’une variable du type défini
Exemple, point dans un espace 3D : struct <nom de type> <nom de variable>;
struct point { Exemple : struct point p1;
float x; struct point *pp1;
float y;
ATTENTION, il faut bien préciser le mot-clé struct
float z;
}; ▶ Récupération d’un champ :
struct p o i n t p1 ; var.<nom du champ>
p1 . x = 12.0;
Exemple :p1.x=44.20;
p1 . y = 24.2;
p1 . z = 42.0; pvar-><nom du champ>
Exemple :pp1->x=44.20;

typedef Initialisation & affectation

Initialisation semblable à celle de tableaux :

▶ Définition de types synonymes. Exemple : typedef s t r u c t ma struct {
typedef i n t e n t i e r ; float x;
e n t i e r i =3; char c ;
} ma struct ;
▶ cas des tableaux : m a s t r u c t s={ 1 . 1 2 , ’ a ’ } ;
typedef i n t vect [ 3 ] ;
v e c t v1 , v2 ; Possibilité de copier directement une structure par affectation :
▶ cas des struct m a s t r u c t s1 ={1.12 , ’ a ’ } , s2 ;
typedef s t r u c t point { i n t x ; i n t y ;} point ;
point A; équivalent à s2 . x=s1 . x ;
s2=s1 ;
s2 . c=s1 . c ;
ATTENTION aux pointeurs ...
Tableaux et structures Structures dans une structure

Tableaux dans une structure

s t r u c t personne { s t r u c t date {
char nom [ 3 0 ] ; unsigned char j o u r ;
char prenom [ 3 0 ] ; unsigned char mois ;
unsigned i n t nb commande ; unsigned i n t annee ;
unsigned i n t n commande [ 1 0 ] ; };
};
... s t r u c t personne {
s t r u c t personne c l i e n t 1 ={ ” Dupond ” , ” A l b e r t ” , 0 , char nom [ 3 0 ] ;
{0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,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 ;
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 ++; ...
s t r u c t personne c l i e n t ={ ” Dupond ” , ” A l b e r t ” ,
{24 ,5 ,1950}};
Tableaux de structure i f ( c l i e n t . d a t e n a i s s a n c e . annee>1940) {
...
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 ++;

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 ” ) ;
Listes chaı̂nées
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 : introduction Structure de liste
Principe :
▶ stockage d’un ensemble d’éléments typedef s t r u c t un element
▶ chaque élément contient l’emplacement du suivant {
i n t data ;
s t r u c t un element * suivant ;
Avantages par rapport aux tableaux :
} Un element ;
▶ insérer un élément sans avoir avoir à recopier la suite du
tableau, ou bien :
▶ retirer un élément sans avoir avoir à recopier la suite du
typedef s t r u c t u n e l e m e n t * P un element ;
tableau,
▶ ne pas nécessiter l’utilisation de mémoire contiguë, typedef s t r u c t un element
▶ permet de faire varier dynamiquement la taille, {
i n t data ;
Inconvénients : P un element s u i v a n t ;
} Un element ;
▶ prend plus de place qu’un tableau
▶ pas d’accès immédiat à un élément

Création d’un élément

Déclaration d’une liste :

P un element c r e e r e l e m e n t ( i n t v ) P un element m a l i s t e = NULL ;

{
P un element e l ; Insertion en début de liste
e l = ( P un element ) m a l l o c ( s i z e o f ( Un element ) ) ; 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 ,
i f ( e l == NULL ) r e t u r n NULL ; P un element e l )
e l −>data=v ; {
e l −>s u i v a n t = NULL ; e l −>s u i v a n t = p l i s t e ;
return el ; return el ;
} }
Insertion en fin de liste 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 ) {
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 , i f ( ( * e l )== l i s t e ) {
P un element e l ) P un element n l = ( * e l )−> s u i v a n t ;
{ free (* el ) ;
P un element p l = p l i s t e ; * e l =NULL ;
return nl ;
i f ( p l i s t e == NULL ) }
return el ; 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 ) ) {
w h i l e ( p l −>s u i v a n t ) tmp=tmp−>s u i v a n t ;
{ }
p l = p l −>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 ;
p l −>s u i v a n t = e l ; free (* el ) ;
* e l =NULL ;
return pliste ; }
} 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 ;
}