INFO517 : Programmation C

Cours du semestre 5 de la licence STIC INFO.

Responsable pour 2008--2009: Lionel Vaux.

Pensez à consulter les indications pour compiler un petit programme sur une machine des salles de TP.

N'hésitez pas à contribuer au wiki, et en particulier à cette page: clarifications, compléments, exemples… Si vous n'avez pas compris un point particulier, vous pouvez signaler votre problème sur la page de discussion (onglet en haut de cette page) ou par les moyens habituels. Il sera ensuite très positif de revenir sur cette page et de consigner ce qui vous posait problème et ce qui vous a permis de mieux comprendre.

Fonctionnement

Cet enseignement comprendra 10 séances de cours/TD (1h30) et 3 séances de TP (4h).

La distinction entre cours et TD restera floue. Je vous demanderai généralement d'écrire quelques petits programmes d'une semaine sur l'autre. Autant que possible, envoyez-moi vos fichiers sources à l'adresse lionel.vaux@univ-savoie.fr, afin que je puisse évaluer le niveau de chacun et ajuster le contenu des séances suivantes.

Et dites-moi si ça ne va pas, ou je risque d'avancer trop vite.

Objectifs du cours

• Principes généraux et particularités du langage (programmation impérative, typage fort, adressage mémoire)
• Syntaxe
• Bibliothèque standard (pour les entrées-sorties et l'interaction avec le système d'exploitation)
• Gestion de la mémoire
• Bonnes pratiques
• Outils et concepts:
  • automatisation de la compilation (make),
  • analyse de l'exécution et déboguage (gdb, valgrind),
  • documentation (doxygen),
  • boîte à outils graphique (gtk+)

Séances

Cours/TD 1 : lundi 22 septembre 2008

Présentation tout-en-un.

Le but de ce cours est de fournir le minimum vital aux étudiants pour:

• écrire un programme simple et court utilisant les types de base
• le compiler et l'exécuter
• trouver de la documentation

Après cette première séance, les étudiants devraient être capable de s'amuser un peu avec le langage.

Les exemples vus en cours

bateau.c <source lang="c">

1. include <stdio.h>

int main () { /* Écrit une chaîne */ puts("Bateau !");

/* Renvoie la valeur de sortie en cas de succès */ return 0; } </source>

euros-francs-v1.c <source lang="c">

1. include<stdio.h>

/* Écrit une table de conversion euros/francs

*  pour euros = 0, 5, 10, ...,  100 :
*  version initiale */

main() {

 int euros, euros_max, pas ;
 float francs, un_euro ;

 un_euro = 6.55957 ;  /* taux de conversion */

 pas = 5 ;         /* pas d'itération */
 euros = 0 ;       /* valeur initiale */
 euros_max = 100 ; /* valeur maximale */
 
 while (euros <= euros_max) {
   francs = un_euro * euros ; 
   printf("%d\t%f\n", euros, francs) ; 
   euros = euros + pas ; 
 }

} </source>

euros-francs-v2.c <source lang="c">

1. include<stdio.h>

/* Écrit une table de conversion euros/francs

*  pour euros = 0, 5, 10, ...,  100 :
*  correction de l'alignement */

main() {

 int euros, euros_max, pas ;
 float francs, un_euro ;

 un_euro = 6.55957 ;  /* taux de conversion */

 pas = 5 ;         /* pas d'itération */
 euros = 0 ;       /* valeur initiale */
 euros_max = 100 ; /* valeur maximale */
 
 while (euros <= euros_max) {
   francs = un_euro * euros ; 
   printf("%3d\t%6.2f\n", euros, francs) ; 
   euros = euros + pas ; 
 }

} </source>

euros-francs-v3.c <source lang="c">

1. include<stdio.h>

/* Écrit une table de conversion euros/francs

* pour euros = 0, 5, 10, ...,  100 :
* avec un  `for' */

main() {

 int euros ;
 
 for (euros = 0 ; euros <= 100 ; euros = euros + 5) 
   printf("%3d\t%6.2f\n", euros, 6.55957*euros) ; 

} </source>

euros-francs-v4.c <source lang="c">

1. include<stdio.h>

1. define UN_EURO 6.55957 /* un euro en francs */

/* Écrit une table de conversion euros/francs

* pour euros = 0, 5, 10, ...,  100 :
* définition pour le préprocesseur */

main() {

 int euros ;
 
 for (euros = 0 ; euros <= 100 ; euros = euros + 5)
   printf("%3d\t%6.2f\n", euros, UN_EURO*euros) ; 

} </source>

arrondi.c <source lang="c">

1. include<stdio.h>

1. define INCR 0.00001 /* incrément pour le test de précision */
2. define NUM 100000 /* nombre de pas */

/* Calcule INCR*NUM en ajoutant NUM fois INCR à 0 */ main() {

 float accu ;
 int i ;
 
 accu = 0 ;
 for (i=0 ; i < NUM ; i=i+1) 
   accu = accu + INCR ;
 printf("%f=%f?\n",NUM*INCR,accu) ;

} </source>

arrondi-double.c (cette variante a été signalée pendant les rappels de la deuxième séance) <source lang="c">

1. include<stdio.h>

1. define INCR 0.00001 /* incrément pour le test de précision */
2. define NUM 100000 /* nombre de pas */

/* Calcule INCR*NUM en ajoutant NUM fois INCR à 0.

* Cette version utilise un accumulateur de type `double' 
* pour limiter les erreurs d'arrondi */

main() {

 double accu ;	// On calcule en double précision
 int i ;
 
 accu = 0 ;
 for (i=0 ; i < NUM ; i=i+1) 
   accu = accu + INCR ;
 printf("%f=%f?\n",NUM*INCR,accu) ;

} </source>

copie-v1.c <source lang="c">

1. include<stdio.h>

/* Copie l'entrée standard sur la sortie standard */ main() {

 int c;

 c = getchar();
 while (c != EOF) {
   putchar(c);
   c = getchar();
 }

} </source>

copie-v2.c <source lang="c">

1. include<stdio.h>

/* Copie l'entrée standard sur la sortie standard :

* assignation comme valeur */

main() {

 int c;

 while ((c = getchar()) != EOF) {
   putchar(c);
 }

} </source>

Exercices pour le 29 septembre

• Au choix:
  1. Sur la machine et le système de votre choix, écrire et compiler un programme C (par exemple bateau.c), puis envoyer le fichier source et le binaire obtenu à l'adresse lionel.vaux@univ-savoie.fr.
  2. Ne pas y parvenir et alors me contacter au plus tôt pour y remédier. Ensuite revenir au choix 1, évidemment.
• Modifier l'un des fichiers euros-francs-v?.c pour afficher une ligne d'en-tête alignée sur les résultats (et quelques fioritures). C'est-à-dire que la sortie doit ressembler à:

 Euros:    Francs:
    0   ->     0.00 
    5   ->    32.80 
   10   ->    65.60 
   15   ->    98.39 
   20   ->   131.19 
   ...

• Écrire un programme francs-euros.c qui affiche une table de conversion dans le sens contraire (les comptes ronds sont en francs).
• Écrire un programme qui affiche la valeur entière, de type int, de EOF (vérifier qu'elle n'est pas dans l'intervalle entier [0..255]).
• Écrire un programme qui affiche la valeur entière du « caractère » € (il est possible que vous ne compreniez pas très bien ce qui vous arrive: on en parlera).
• Écrire un programme qui compte le nombre de caractères (au sens de getchar()) dans un fichier.

Solutions possibles pour les exercices

Pour les variations sur euros-francs-v?.c, voilà un programme qui rassemble un peu tout:

conversion.c <source lang="c">

1. include<stdio.h>

1. define UN_EURO 6.55957 /* un euro en francs */

/* Écrit une table de conversion euros/francs

* pour euros = 0, 5, 10, ...,  100 :
* définition pour le préprocesseur */

main() {

 int euros ;
 int francs ;
 
 printf("Euros:\t\tFrancs:\n") ; 
 for (euros = 0 ; euros <= 100 ; euros = euros + 5)
   printf("   %3d\t\t    %6.2f\n", euros, UN_EURO*euros) ; 

 printf("\nFrancs:\t\tEuros:\n") ; 
 for (francs = 0 ; francs <= 100 ; francs = francs + 5)
   printf("    %3d\t\t   %6.2f\n", francs, francs/UN_EURO) ; 

} </source>

Un programme qui affiche la valeur entière (type int) de EOF: <source lang="c">

1. include<stdio.h>

/* Écrit la valeur entière de EOF */ main() { printf("%d\n",EOF) ; } </source> On sauve ça dans EOF.c, puis on compile avec

$ gcc -Wall -o EOF EOF.c

Les erreurs produites sont standard (mauvais prototype pour main). L'exécution sur ma machine donne:

$ ./EOF
-1

La valeur entière de €, sur le même modèle: <source lang="c">

1. include <stdio.h>

main () { int euro = '€' ;

printf("%d\n",euro) ; } </source> On sauve ça dans euro.c, puis on compile avec:

$ gcc -Wall -o euro euro.c

ce qui produit les avertissements:

euro.c:3: attention : return type defaults to «int»
euro.c:4:13: attention : constante caractère multi-caractères
euro.c: Dans la fonction «main» :
euro.c:7: attention : control reaches end of non-void function

La deuxième ligne est le premier signe que quelque chose de bizarre est à l'œuvre. À l'exécution, on obtient:

$ ./euro 
14844588

Savez-vous expliquer ce qui se passe ?

Pour compter le nombre de caractères: ce qu'on a vu en cours fait mieux.

Cours/TD 2 : lundi 29 septembre 2008

Rappels et précisions; fonctions; tableaux.

Les exemples vus en cours

puissance-v1.c <source lang="c">

1. include<stdio.h>
2. define MAXEXP 16

/* Fonction puissance(a: int, b: int) : int

* renvoie a à la puissance b, si b positif, 1 sinon */ 

int puissance (int a, int b) { int i, ret ; ret = 1 ; for (i=0; i<b; ++i) /* ++i incrémente i */ ret = a * ret ; return ret ; }

/* Procédure affiche(a: int, b: int)

* formatte le résultat de puissance(a,b) */ 

void affiche(int a, int b) { printf("%2d^%2d = %10d\n",a,b,puissance(a,b)) ; }

/* Fonction principale: affiche les puissances de 2, de 1 à 2^MAXEXP */ void main () { int i ; for (i=0; i<=MAXEXP; ++i) affiche(2,i) ; } </source>

puissance-v2.c <source lang="c">

1. include<stdio.h>
2. define MAXEXP 16

/* Prototype de la fonction puissance(a: int, b: int) : int

*/

int puissance (int a, int b) ;

/* Procédure affiche(a: int, b: int)

* formatte le résultat de puissance(a,b) */ 

void affiche(int a, int b) { printf("%2d^%2d = %10d\n",a,b,puissance(a,b)) ; }

/* Fonction principale: affiche les puissances de 2, de 1 à 2^MAXEXP */ void main () { int i ; for (i=0; i<=MAXEXP; ++i) affiche(2,i) ; }

/* Code de la fonction puissance :

* puissance(a,b) renvoie a à la puissance b, si b positif, 1 sinon */ 

int puissance (int a, int b) { int ret ; ret = 1 ; /* On utilise l'argument b comme une variable locale */ for (/* pas d'initialisation nécessaire */; b>0; --b) ret = a * ret ; return ret ; } </source>

fibonacci.c <source lang="c">

1. include<stdio.h>
2. define MAX 30

/* calcule u[n], où u[0]=u[1]=1 et u[n+2]=u[n+1]+u[n] */ int fibo (int n, int rec) { if (n<=1) return 1 ; else return (fibo(n-1,rec+1)+fibo(n-2,rec+1)) ; }

/* affiche fibo(n) pour n de 0 à MAX */ int main () { int i ; for (i=0;i<=MAX;++i) printf("fibo(%2d)=%8d\n",i,fibo(i,0)) ; return 0 ; } </source>

tracerec.c <source lang="c">

1. include<stdio.h>
2. define N 15

/* Procédure blanks(n: int)

* insère n espaces. */

void blanks (int n) {

       for(;n>0;--n) putchar(' ') ;

}

/* Calcule fibo(n) (voir fibo.c) et affiche le résultat.

* Cet affichage dans la fonction permet de tracer le
* flot de récursion (l'ordre dans lequel les appels se font).
*
* On représente la profondeur de récursion par l'indentation,
* au moyen du second argument : tous les affichages sont décalés
* de rec espaces. L'entier rec est incrémenté dans l'appel récursif,
* et on démarre avec rec=0 dans main()
* */

int fibo_rec (int n, int rec) {

       blanks(rec) ; printf("fibo(%2d)=?\n",n) ;
       if (n<=1) {
               blanks(rec) ; printf("fibo(%2d)=1\n",n) ;
               return 1 ;
       } else {

/* On peut déclarer des variables locales à un bloc */

               int ret=fibo_rec(n-1,rec+1)+fibo_rec(n-2,rec+1) ;
               blanks(rec) ; printf("fibo(%2d)=%d\n",n,ret) ;

return ret ;

       }

}

/* Calcule fibo(N) avec affichage des étapes de récursion */ int main () {

       fibo_rec(N,0) ;
       return 0 ;

} </source>

segfault.c <source lang="c">

/* CE CODE EST VOLONTAIREMENT FAUTIF ! */

/* Notre première erreur de segmentation:

* les appels récursifs s'empilent sans limite et on sort de la mémoire
* disponible. */

1. include<stdio.h>
2. define MAX 30

/* calcule u[n], où u[0]=u[1]=1 et u[n+2]=u[n+1]+u[n] */ int fibo (int n, int rec) { return (fibo(n-1,rec+1)+fibo(n-2,rec+1)) ; }

/* affiche fibo(n) pour n de 0 à MAX */ int main () { int i ; for (i=0;i<=MAX;++i) printf("fibo(%2d)=%8d\n",i,fibo(i,0)) ; return 0 ; } </source>

textstat.c <source lang="c">

1. include<stdio.h>

/* En théorie, les valeurs entières des caractères

* sont dans un intervalle non précisé par la norme.
*
* Dans cet exemple, on considère que les caractères sont des entiers sur 8
* bits non signés (cf. CHAR_MIN, CHAR_MAX).
*
* Ceci était passé sous silence lors du cours.
*
*/

1. define CHAR_MIN 0
2. define CHAR_MAX 255

/* CHAR_NUM = CHAR_MAX - CHAR_MIN + 1 */

1. define CHAR_NUM 256

/* Une macro évidente */ void aff (char c, int n) { printf("%c:%2d ",c,n) ; }

/* Compte le nombre d'occurrences de chaque caractère

* et affiche certains résultats */ 

int main() { int c, i ; int nb [CHAR_NUM] ;

/* Mise à zéro */ for (i=0;i<CHAR_NUM;++i) nb[i]=0 ;

/* Calcul */ while((c=getchar()) != EOF) ++nb[CHAR_MIN+c] ;

/* Affichage */

/* Les lettres minuscules sont consécutives de 'a' à 'z'. */

printf("Minuscules:\n") ; for (c='a'; c<='z' ; ++c) aff(c,nb[CHAR_MIN+c]) ;

/* De même pour les majuscules de 'A' à 'Z'. */

printf("\nMajuscules:\n") ; for (c='A'; c<='Z' ; ++c) aff(c,nb[CHAR_MIN+c]) ;

/* Et les chiffres de '0' à '9'. */

printf("\nChiffres:\n") ; for (c='0'; c<='9' ; ++c) aff(c,nb[CHAR_MIN+c]) ;

printf("\nSauts de lignes: %d\n",nb[CHAR_MIN+'\n']) ;

return 0 ; }

</source>

Exercices pour le 6 octobre

Sur les fonctions

• Réécrire le programme conversion.c en utilisant une fonction pour l'affichage. Rendre ce programme plus modulaire en écrivant une procédure avec le prototype void francs_euros (int min, int max, int pas) qui afffiche la conversion de n francs en euros pour n variant de min à max par pas de pas et une procédure void euros_francs (int min, int max, int pas) qui affiche la même chose mais dans l'autre sens de conversion.

• Écrire une fonction int fact (int n) qui calcule la factorielle de n de deux manières différentes: une par récursion, une en utilisant une boucle. Essayer ces fonctions sur des valeurs pas trop petites et détecter quand ça dégénère.

Sur les tableaux et les chaînes

• Écrire une procédure void aff (int t[], int n) qui affiche les n premiers éléments du tableau t.

• On donne le programme:

<source lang="c">

1. include <stdio.h>

void incr (int n) { ++n ; }

void incr_t0 (int t[]) { ++t[0] ; }

int main () { int n = 0 ; int t[1] = { 0 } ; incr(n) ; incr_t0(t) ; printf("n: %d\n",n) ; printf("t[0]: %d\n",t[0]) ; return 0 ; } </source> Compiler et exécuter ce programme. Que remarque-t-on ? Qu'en déduire sur les tableaux comme arguments de fonctions.

• Que fait le programme fin_chaine.c suivant ? Expliquer.

<source lang="c">

1. include <stdio.h>

int main () { printf("Bateau.\n\0Et puis aussi...") ; return 0 ; } </source>

• Écrire un programme qui affiche les lignes données en entrée seulement si elles comportent plus de 20 caractères. Penser à structurer intelligemment.
• Écrire une fonction void pal(char s[]) qui renvoie 1 si la chaîne s est un palindrome et 0 sinon.

• Écrire une procédure void renverse(char s[]) qui renverse la chaîne s.

Solutions possibles

Un exemple complet de programme utilisant les fonctions (on n'hésite pas à en rajouter):

 #include <stdio.h>
 
 #define UN_EURO 6.55957 /* un euro en francs */ 
 
 void aff_col (int a, float b)
 {
     printf("   %3d\t\t    %6.2f\n", a, b ) ;
 }
 
 void aff_en_tete (const char a[], const char b[])
 {
     printf("%s\t\t%s\n", a, b ) ;
 }
 
 void table_conv (float taux, int min, int max, int pas)
 {
         int i ;
         if (pas > 0)
                 /* si le pas est positif on va du min au max */
                 for (i=min; i<=max; i=i+pas)
                         aff_col(i,taux*i) ;
         else if (pas < 0)
                 /* si le pas est négatif on va du max au min */
                 for (i=max; i>=min; i=i+pas)
                         aff_col(i,taux*i) ;
 }
 
 void francs_euros (int min, int max, int pas)
 {
         aff_en_tete("Francs","Euros") ;
         table_conv (1/UN_EURO,min,max,pas) ;
 }
 
 void euros_francs (int min, int max, int pas)
 {
         aff_en_tete("Euros","Francs") ;
         table_conv (UN_EURO,min,max,pas) ;
 }
 
 int main()
 {
         francs_euros(10,100,10) ;
         euros_francs(1,10,-1) ;
         return 0 ;
 }

Sur les factorielles:

 #include <stdio.h>
 #define MAX 30
 
 /* calcule n! par récurrence sur n  */
 unsigned long int fact_rec (unsigned int n) {
         if (n<=1) return 1 ;
         else return n*fact_rec(n-1) ; 
 }
 
 /* calcule n! par comme un produit itéré */
 unsigned long int fact_it (unsigned int n) {
 	unsigned int i ; 
 	unsigned long int acc = 1; 
 	for (i=2;i<=n;++i)
 		acc=i*acc ;
 	return acc ;
 }
 
 
 /* fonctions d'affichage */
 void aff (unsigned int n, unsigned long int res, const char nom[]) {
 	printf("On calcule %u!=%lu par %s\n", n, res, nom) ;
 }
 
 void aff_fact_rec (unsigned int n) {
 	aff(n,fact_rec(n),"fact_rec") ;
 }
 
 void aff_fact_it (unsigned int n) {
 	aff(n,fact_it(n),"fact_it") ;
 }
 
 /* affiche fact_rec(n) et fact_it(n) pour n de 0 à MAX */
 /* noter que malgré toutes nos précautions, ça dégénère vite, 
  * car n! croit vite */
 int main () {
 	unsigned int i ;
 	for (i=1; i<MAX; ++i) {
 		aff_fact_rec(i) ;
 		aff_fact_it(i) ;
 	}
         return 0 ;
 }

Afficher un tableau d'entiers:

 /* Affiche les n premiers éléments du tableau t sous la forme 
  * {t[0],t[1],...,t[n-1]} 
  * */
 void aff (int t[], int n) {
 	int i ; 
 	putchar('{') ;
 	for (i=0;i<n;++i) {
 		printf("%d",t[i]) ; 
 		if (i!=n-1)
 			putchar(',') ;
 	}
 	putchar('}') ;
 	putchar('\n') ;
 }

Afficher uniquement les lignes avec au moins 20 caractères (ici, une version plus générique):

 void ligne_au_moins (int n) {
         char s[n] ;
         int c = getchar() ;
         while (c != EOF) {
                 // Dans cette boucle, on traite une ligne, qui commence par c.
                 int i = 0 ;
                 // On commence par essayer de stocker les n premiers caractères :
                 while (c != '\n' && c != EOF && i<n) {
                         s[i] = c ;
                         ++ i ;
                         c = getchar() ;
                 }
                 // Si on a lu n caractères sans rencontrer de retour à la ligne
                 // ni de fin de fichier, on recopie et on vide la ligne.
                 if (i==n) {
                         // On recopie s
                         for (i=0; i<n; ++i)
                                 putchar(s[i]) ;
                         // On recopie la fin de la ligne
                         while (c != '\n' && c != EOF) {
                                 putchar(c) ;
                                 c = getchar() ;
                         }
                         // Retour à la ligne, si besoin
                         if (c == '\n') {
                                 putchar(c) ;
                                 c = getchar () ;
                         }
                 } else if (c == '\n') {
                         // Si la ligne se termine avant le n-ième caractère, 
                         // on passe à la suivante.
                         c = getchar() ;
                 }
         }
 }

Pour le test de palindrome et le renversement, on a d'abord besoin de connaître la longueur de la chaîne:

 unsigned int longueur (char s[]) {
 	unsigned int l ;
 	for (l=0; s[l]!='\0'; ++l) ; 
 	return l ;
 }
 
 int pal (char s[]) {
 	unsigned int l = longueur(s) ;
 	int i ; 
 	int ret = 1 ; 
 	// On parcourt la moitié du tableau (au plus) et on s'arrête si jamais
 	// on trouve des valeurs différentes dans des cases symétriques.
 	for (i=0; i<l/2 && ret ; ++i)
 		ret = (s[i]==s[l-i-1]) ;
 	return ret ;
 }
 	
 void renverse (char s[]) {
 	unsigned int l = longueur(s) ;
 	int i ; 
 	char c ; 
 	// On parcourt la moitié du tableau (au plus).
 	for (i=0; i<l/2 ; ++i) {
 		c = s[i] ; 
 		s[i] = s[l-i-1] ; 
 		s[l-i-1] = c ; 
 	}
 }

Cours/TD 3 : lundi 6 octobre 2008

Exercices en TD

Feuille 1.

Devoir à la maison pour le 13 octobre

Le sujet: INFO517-DM1.pdf et les fichiers sources dm1.c et mat.c.

Cours/TD 4 : lundi 13 octobre 2008

Représentation de la mémoire: pointeurs.

Les exemples vus en cours

Appel par adresse: <source lang="c">

1. include <stdio.h>

void inc (int *i) { ++(*i) ; }

int main () { int n = 0 ; printf("%d\n",n) ; inc(&n) ; printf("%d\n",n) ; return n ; } </source>

Rappel (tableaux): <source lang="c">

1. include <stdio.h>

void inc (int t[]) { t[0]++ ; }

int main () { int t[] = { 0 } ; printf("%d\n",t[0]) ; inc(t) ; printf("%d\n",t[0]) ; return t[0] ; } </source>

Les tableaux sont des pointeurs particuliers: <source lang="c">

1. include <stdio.h>

void aff (char *s) { while (*s != '\0') { putchar(*s) ; s++ ; } }

int main () { aff("bateau\n") ; return 0 ; } </source>

Affichage des éléments d'un tableau d'entiers (c'est pareil): <source lang="c">

1. include <stdio.h>

/* affiche les n premiers éléments de t */ void aff (int *t, int n) { putchar('{') ; for (;n>0;n--) { printf("%d",*t) ; if (n>1) putchar(',') ; t++ ; } putchar('}') ; putchar('\n') ; }

int main () { int t[] = {1,7,3,4,0,-1} ; aff(t,3) ; return 0 ; } </source>

Attention: rien ne contrôle le fait qu'on est bien dans le tableau. C'est-à-dire que ce qui suit est un programme C valide, qui compile et s'exécute: <source lang="c">

1. include <stdio.h>

/* affiche les n premiers éléments de t */ void aff (int *t, int n) { putchar('{') ; for (;n>0;n--) { printf("%d",*t) ; if (n>1) putchar(',') ; t++ ; } putchar('}') ; putchar('\n') ; }

int main () { int t[] = {1,7,3,4,0,-1} ; aff(t,7) ; // PROBLÈME ! return 0 ; } </source> On obtient par exemple:

 {1,7,3,4,0,-1,-1077769696}

Toutefois, il ne faut pas pousser le bouchon trop loin: on finit par écrire dans des zones qui ne sont pas allouées en mémoire. Ce programme, bien que valide en C, plante: <source lang="c">

1. include <stdio.h>

/* affiche les n premiers éléments de t */ void aff (int *t, int n) { putchar('{') ; for (;n>0;n--) { printf("%d",*t) ; if (n>1) putchar(',') ; t++ ; } putchar('}') ; putchar('\n') ; }

int main () { int t[] = {1,7,3,4,0,-1} ; aff(t,32000) ; // PROBLÈME ! return 0 ; } </source> C'est notre deuxième erreur de segmentation: on y reviendra, en précisant où sont les choses en mémoire.

On peut afficher les adresses d'un peu tout. Ici, par exemple, celles des arguments des fonctions qui se retrouvent sur la pile. <source lang="c">

1. include <stdio.h>

void f (char a, char b) { printf("char:\n") ; printf("&a: %u\n&b: %u\n", &a,&b) ; printf("a: %u\nb: %u\n", a,b) ; }

void g (int a, int b) { printf("int:\n") ; printf("&a: %u\n&b: %u\n", &a,&b) ; printf("a: %u\nb: %u\n", a,b) ; }

void h (long double a, long double b) { printf("long double:\n") ; printf("&a: %u\n&b: %u\n", &a,&b) ; printf("a: %Lf\nb: %Lf\n", a,b) ; }

int main () { f(0,1) ; g(0,1) ; h(0,1) ; return 0 ; } </source> À l'exécution, on remarque que l'écart entre ces adresses change (et aussi, qu'elles ne sont pas forcément dans l'ordre attendu):

 char:
 &a: 3216755060
 &b: 3216755056
 a: a
 b: b
 int:
 &a: 3216755072
 &b: 3216755076
 a: 97
 b: 98
 long double:
 &a: 3216755072
 &b: 3216755084
 a: 97.000000
 b: 98.000000

En effet, les types considérés ont des tailles différentes. La primitive sizeof donne (en octets) l'espace mémoire nécessaire pour stocker une donnée du type considéré: <source lang="c">

1. include <stdio.h>

void aff_taille (const char nom[], size_t taille) { printf("%16s : %2u\n",nom,taille) ; }

/* Affiche les tailles de types à taille fixe les plus courants */ int main () {

printf("Liste de tailles :\n") ; aff_taille("void",sizeof(void)) ; aff_taille("char",sizeof(char)) ; aff_taille("short int",sizeof(short int)) ; aff_taille("int",sizeof(int)) ; aff_taille("long int",sizeof(long int)) ; aff_taille("float",sizeof(float)) ; aff_taille("double",sizeof(double)) ; aff_taille("long double",sizeof(long double)) ; aff_taille("void*",sizeof(void*)) ; aff_taille("int*",sizeof(int*)) ; aff_taille("long double*",sizeof(long double*)) ;

return 0 ; } </source> Sur ma machine, on obtient la sortie:

 Liste de tailles :
             void :  1
             char :  1
        short int :  2
              int :  4
         long int :  4
            float :  4
           double :  8
      long double : 12
            void* :  4
             int* :  4
     long double* :  4

Noter que la taille des pointeurs est toujours la même (et c'est celle du type int).

Le type du pointeur renseigne le compilateur sur le décalage d'adresse à produire lors d'opérations arithmétiques: <source lang="c">

1. include <stdio.h>

int main () { char *s ; int *p ; long double *q ;

int i ;

for (i=0;i<4;++i) { ++s ; printf("s+%d : %u\n",i,s) ; }

for (i=0;i<4;++i) { ++p ; printf("p+%d : %u\n",i,p) ; }

for (i=0;i<4;++i) { ++q ; printf("q+%d : %u\n",i,q) ; }

return 0 ;

} </source> On observe que les écarts reflètent bien la taille du type annoncé (1, 4 et 12 ici):

 s+0 : 3086073265
 s+1 : 3086073266
 s+2 : 3086073267
 s+3 : 3086073268
 p+0 : 134513757
 p+1 : 134513761
 p+2 : 134513765
 p+3 : 134513769
 q+0 : 3216681396
 q+1 : 3216681408
 q+2 : 3216681420
 q+3 : 3216681432

Revenons sur l'allocation des tableaux avec le code suivant: <source lang="c">

1. include <stdio.h>

1. define TAILLE 1024

int t1 [TAILLE] ; int t2 [1] ; int t3 [TAILLE] ; int t4 [1] ;

void aff_point (int *p) { printf("%u = %x -> %i\n",p,p,*p) ; }

int * tab_nouv (int n) { int t[TAILLE] ; int i ; for (i=0; i<TAILLE; ++i) t[i]=n ; return t ; }

/* Affiche les adresses des tableaux statiques et de deux "tableaux" créés par

* tab_nouv() */

int main () { int *t5 = tab_nouv(4) ; int *t6 = tab_nouv(2) ; printf("Tableaux statiques:\n") ; aff_point(t1) ; aff_point(t2) ; aff_point(t3) ; aff_point(t4) ; printf("Tableaux dynamiques (?):\n") ; aff_point(t5) ; aff_point(t6) ; return 0 ; } </source> L'intention de l'auteur est visiblement de retourner un tableau « frais » à chaque appel de tab_nouv. C'est un peu raté, car la sortie de ce programme ressemble à:

 Tableaux statiques:
 134522656 = 804a720 -> 0
 134518496 = 80496e0 -> 0
 134518528 = 8049700 -> 0
 134522624 = 804a700 -> 0
 Tableaux dynamiques (?):
 3219749988 = bfe97c64 -> 2
 3219749988 = bfe97c64 -> 2

Les adresses renvoyées par tab_nouv sont les mêmes et le contenu est écrasé. C'est bien normal: ces tableaux sont alloués sur la pile, puis immédiatement oubliés à la sortie de la fonction.

On souhaite donc faire de l'allocation dynamique: c'est le rôle de la fonction void *malloc(size_t taille) qui renvoie l'adresse de début d'une zone de mémoire allouée, d'une taille au moins égale à taille. On pourra donc réécrire: <source lang="c"> int * tab_nouv (int n) { int *t = malloc(TAILLE*sizeof(int)) ; // la taille est donnée en octets !

       int i ;
       for (i=0; i<TAILLE; ++i)
               t[i]=n ;
       return t ;

} </source> On peut vérifier que la nouvelle version fonctionne bien sur la sortie:

 Tableaux statiques:
 134522720 = 804a760 -> 0
 134518560 = 8049720 -> 0
 134518592 = 8049740 -> 0
 134522688 = 804a740 -> 0
 Tableaux dynamiques:
 134529032 = 804c008 -> 4
 134533136 = 804d010 -> 2

Notez que les adresses rendues par malloc sont proches de celles des variables statiques.

Application à la lecture de lignes de longueur non bornée: <source lang="c">

 #include <stdlib.h>

1. include <stdio.h>

// On alloue par blocs de talle MORCEAU.

1. define MORCEAU 1024

/* Lit une ligne en entrée _quelle que soit sa taille_

* et la stocke dans *p (p est un pointeur sur une chaîne).
* Renvoie le nombre de caractère lus (-1 en cas d'erreur). */

int lit_ligne (char **p) { char c ; char *s ; int pos, blocs, i ;

// La position courante dans la chaîne est i+MORCEAU*blocs. pos = blocs = i = 0 ;

// On alloue le premier morceau. s = malloc ((++blocs)*MORCEAU*sizeof(char)) ; if (s == NULL) return -1 ;

while ((c=getchar())!=EOF && c!='\n') { s[pos] = c ; if (i==MORCEAU-1) { // on déborderait en faisant ++i if ((s=realloc(s,(++blocs)*MORCEAU*sizeof(char))) == NULL) { return -1 ; // plus de mémoire : on quitte } i=0 ; } else { ++i; } ++pos ; }

// si c == '\n' il faut l'ajouter

if (c=='\n') { s[pos] = c ; // on pourrait déborder en ajoutant le '\0': on gère ça if (i==MORCEAU-1) { if ((s=realloc(s,(pos+1)*sizeof(char))) == NULL) return -1 ; // plus de mémoire : on quitte } ++pos ; }

s[pos]='\0' ; *p=s ; return pos ;

}

/* Lit des lignes sur l'entrée et les affiche à l'envers. */ int main () { char *s ; int ret ; while ((ret=lit_ligne(&s))>0) { if (s[ret-1]=='\n') ret--; for (;ret>0;--ret) putchar(s[ret-1]) ; putchar('\n') ; free(s) ; } return ret ; } </source> La fonction void *realloc(void *p, size_t taille) demande de changer la taille de la zone allouée par malloc pointée par p, en en conservant le contenu.

La fonction void free(void *p) libère la zone de mémoire allouée par malloc ou realloc et la rend au système: on a fini de s'en servir. C'est essentiel, car on alloue autant de zones que de lignes lues: sans l'appel à free en fin de boucle, on conserverait en mémoire toutes les lignes alors que seule la dernière nous intéresse.

TP 1 : mercredi 15 octobre 2008

Les sujets de TP se trouvent sur cette page. Pour le premier TP, vous devez traiter le sujet TP0 — Préliminaires.

Note à l'usage de l'enseignant

Il faudra demander à la DSI l'installation des paquets: vim-full, gcc-doc, ddd.

Cours/TD 5 : lundi 20 octobre 2008

Modèle mémoire: pile, tas, segment de code, allocation dynamique.

Les exemples vus en cours

Le code suivant affiche la chaîne abcdef en minuscules puis en majuscules: <source lang="c">

1. include <stdio.h>

void maj (char s[]) { int i ; for (i=0 ; s[i]!='\0' ; i++) { char c = s[i] ; if (c>='a' && c<='z') s[i] = c+'A'-'a' ; } }

int main () { char s[] = "abcdef" ; /* tableau = pointeur ? */

puts(s) ; maj(s) ; puts(s) ; return 0 ; } </source>

Si on change la déclaration de s en <source lang="c"> char s* = "abcdef" ; </source> on obtient une erreur de segmentation. Pourquoi ?

Les tableaux ne sont pas des variables comme les autres: un tableau t doit être considéré comme un alias pour &t[0], qui n'est pas une valeur gauche (quelque chose qui va à gauche du signe =): c'est de la même nature que n+1 par exemple. Lors de la déclaration d'un tableau, son contenu (dont la taille est connue à la compilation) est alloué sur la pile. Par contraste, un pointeur est une variable entière qui contient une adresse. Lors de la déclaration <source lang="c"> char s* = "abcdef" ; </source> le tableau constant "abcdef" est alloué dans le segment de code en lecture seule et s pointe sur le premier caractère: c'est très différent.

On va mettre en évidence ce phénomène dans la suite en précisant l'emplacement mémoire des divers éléments d'un programme.

Voilà d'abord une petite bibliothèque pour afficher des adresses.

mem.h <source lang="c">

1. ifndef MEM_H
2. define MEM_H
3. include <stdio.h>

void mem_indent (int n) ;

/********** Affichage de pointeurs **********/

void mem_addr (void *p) ; void mem_addr_ptr (void **p) ; void mem_addr_ch (char **p) ; void mem_ch (char *p) ; void mem_addr_int (int *p) ;

/********** Affichage de la pile **********/

int * mem_debut_pile ; void mem_aff_pile (int *haut) ; void mem_aff_pile_chars (int *haut) ;

1. endif

</source> mem.c <source lang="c">

1. include <stdio.h>
2. include "mem.h"

/********** Fonctions utiles **********/

/* Affiche un caractère s'il est directement imprimable,

* un code standard s'il est connu et le code octal sinon. */

void mem_print_char (char c) { if ((c>='a' && c<='z') || (c>='A' && c<='Z') || (c>='0' && c<='9')) printf("%4c",c) ; else switch (c) { case '.': case ',': case ';': case '!': case '?': case ':': printf("%4c",c) ; break ; case ' ': printf(" ' '") ; break ; case '\n': printf(" \\n") ; break ; case '\t': printf(" \\t") ; break ; default: printf("\\%03o",(unsigned char)c) ; } }

/* Indente avec `n' tabulations */ void mem_indent (int n) { int i ; for (i=1;i<=n;i++) putchar('\t') ; }

/********** Affichage de pointeurs **********/

/* Affiche la valeur d'un pointeur (c'est-à-dire l'adresse de la case vers

* laquelle il pointe. */

void mem_addr (void *p) { printf("%10u == %8x\n", (unsigned int) p, (unsigned int) p) ; }

/* Affiche l'adresse et la valeur d'un pointeur. */ void mem_addr_ptr (void **p) { printf("%10u == %8x -> %10u == %8x\n", (unsigned int) p, (unsigned int) p, (unsigned int) *p, (unsigned int) *p); }

/* Affiche l'adresse et la valeur d'un pointeur sur `char',

* puis l'affiche comme une chaîne. */

void mem_addr_ch (char **p) { printf("%10u == %8x -> %10u == %8x -> %s\n", (unsigned int) p, (unsigned int) p, (unsigned int) *p, (unsigned int) *p, *p) ; }

/* Affiche la valeur d'un pointeur sur `char',

* puis l'affiche comme une chaîne.  */

void mem_ch (char *p) { printf("%10u == %8x -> %s\n", (unsigned int) p, (unsigned int) p, p) ; }

/* Affiche l'adresse et la valeur d'un `int' */ void mem_addr_int (int *p) { printf("%10u == %8x -> %11d\n", (unsigned int) p, (unsigned int) p, *p) ; }

/* Affiche l'adresse et la valeur d'un `int',

* avec les conversions non-signée et hexa. */

void mem_addr_ints (int *p) { printf("%10u == %8x -> %11d == %10u == %8x\n", (unsigned int) p, (unsigned int) p, *p, (unsigned int) *p, (unsigned int) *p) ; }

/* Variante de la précédente avec la conversion en caractères. */ void mem_addr_chars (int *p) { char *s ; int i ; printf("%10u == %8x -> %11d == %8x == {", (unsigned int) p, (unsigned int) p, *p, (unsigned int) *p) ; s=(char *)p ; mem_print_char(s[0]) ; for (i=1;i<sizeof(int);++i) { printf(","); mem_print_char(s[i]) ; } printf("}\n") ; }

/********** Affichage de la pile **********/

/* Le pointeur mem_debut_pile doit être initialisé à l'adresse d'une variable

* de pile */

void mem_aff_pile (int *haut) { int *p ; for (p=haut ; p<= mem_debut_pile ; p++) mem_addr_ints(p) ; }

void mem_aff_pile_chars (int *haut) { int *p ; for (p=haut ; p<= mem_debut_pile ; p++) mem_addr_chars(p) ; } </source>

Le programme suivant met en évidence l'allocation des chaînes constantes dans le segment de code, des tableaux locaux dans la pile, et l'allocation dynamique dans le tas. Le code a les adresses les plus basses. Le tas a des adresses petites et croissantes. La pile a des adresses grandes et décroissantes. <source lang="c">

1. include <stdio.h>
2. include <stdlib.h>
3. include "mem.h"

1. define TAILLE 40
2. define REC 5

char tab_ext [] = "tableau externe"; char *ptr_ext = "pointeur externe";

void f (int n) { char tab_f [] = "f: tableau"; char *ptr_f = "f: pointeur"; char *ptr_all_f = malloc(TAILLE) ; snprintf(ptr_all_f,TAILLE,"f: pointeur alloué %d", n) ;

if (n<REC) { mem_indent(n), mem_addr_int(&n) ; mem_indent(n), mem_ch(tab_f) ; mem_indent(n), mem_addr_ch(&ptr_f) ; mem_indent(n), mem_addr_ch(&ptr_all_f) ; f(n+1) ; } }

int main () { char tab_main [] = "main: tableau"; char *ptr_main = "main: pointeur"; char *ptr_all_main = malloc(TAILLE) ; snprintf(ptr_all_main,TAILLE,"main: pointeur alloué") ;

mem_ch(tab_ext) ; mem_addr_ch(&ptr_ext) ; mem_ch(tab_main) ; mem_addr_ch(&ptr_main) ; mem_addr_ch(&ptr_all_main) ;

f(0) ; return 0 ; } </source>

À l'exécution du programme suivant, on remarque que les adresses de la pile décroissent plus vite que ce qu'on aurait en n'empilant que les arguments. <source lang="c">

1. include <stdio.h>
2. include <stdlib.h>
3. include "mem.h"

1. define REC 8

void g (int n) ;

void f (int n) { if (n<REC) { mem_addr_int(&n) ; g(n) ; } }

void g (int n) { if (n<REC) { mem_addr_int(&n) ; f(n+1) ; } }

int main () { int n = 0 ; mem_addr_int(&n) ; f(1) ;

return 0 ;

} </source> C'est donc qu'il y a autre chose sur la pile.

Le programme suivant affiche l'intégralité de la pile: <source lang="c">

1. include <stdio.h>
2. include <stdlib.h>
3. include "mem.h"

1. define REC 8

void g (int n) ;

void f (int n) { if (n<REC) { mem_addr_int(&n) ; g(n) ; } else { printf("Affichage de la pile :\n") ; mem_aff_pile(&n) ; } }

void g (int n) { if (n<REC) { mem_addr_int(&n) ; f(n+1) ; } }

int main () { int n = 0 ; mem_debut_pile = &n ;

mem_addr_int(&n) ; f(1) ; return 0 ;

} </source> On remarque la pile contient des pointeurs vers des emplacements dans le segment de code. Il s'agit en fait d'adresses de retour vers le code de f et g, comme mis en évidence par l'exécution du programme suivant: <source lang="c">

1. include <stdio.h>
2. include <stdlib.h>
3. include "mem.h"

1. define REC 8

void g (int n) ;

void f (int n) { if (n<REC) { g(n) ; } else { printf("Affichage de la pile :\n") ; mem_aff_pile(&n) ; } }

void g (int n) { if (n<REC) { f(n+1) ; } }

int main () { int n = 0 ; mem_debut_pile = &n ;

printf("Adresse de f : "), mem_addr((void *)f) ; printf("Adresse de g : "), mem_addr((void *)g) ; f(1) ; return 0 ; } </source> À noter que les noms de fonctions peuvent être considérés comme des pointeurs dans le segment de code. Les adresses de retour mises en évidence dans la pile correspondent à des adresses dans le code de f et g.

On revient sur le deuxième exemple en affichant la pile, et en convertissant les entiers en blocs de caractères: on retrouve les tableaux de caractères alloués sur la pile. <source lang="c">

1. include <stdio.h>
2. include <stdlib.h>
3. include "mem.h"

1. define TAILLE 40
2. define REC 5

char tab_ext [] = "tableau externe"; char *ptr_ext = "pointeur externe";

void f (int n) { char tab_f [] = "f: tableau"; char *ptr_f = "f: pointeur"; char *ptr_all_f = malloc(TAILLE) ; snprintf(ptr_all_f,TAILLE,"f: pointeur alloué %d", n) ;

if (n<REC) { mem_indent(n), mem_addr_int(&n) ; mem_indent(n), mem_ch(tab_f) ; mem_indent(n), mem_addr_ch(&ptr_f) ; mem_indent(n), mem_addr_ch(&ptr_all_f) ; f(n+1) ; } else mem_aff_pile_chars(&n) ; }

int main () { int n = 0 ; char tab_main [] = "main: tableau"; char *ptr_main = "main: pointeur"; char *ptr_all_main = malloc(TAILLE) ; snprintf(ptr_all_main,TAILLE,"main: pointeur alloué") ;

mem_ch(tab_ext) ; mem_addr_ch(&ptr_ext) ; mem_ch(tab_main) ; mem_addr_ch(&ptr_main) ; mem_addr_ch(&ptr_all_main) ;

mem_debut_pile = &n ; f(0) ;

return 0 ;

} </source>

Cours/TD 6 : lundi 3 novembre 2008

Structures

Une petite bibliothèque de vecteurs en deux dimensions:

Les en-têtes vect.h: <source lang="C">

1. ifndef VECT_H
2. define VECT_H

/* On a besoin de la fonction `double sqrt(double d)' qui

* est déclarée dans `math.h' :
* penser à compiler avec l'option `-lm' de gcc.
*/

1. include <math.h>

/************************/ /* Définitions de types */ /************************/

/* type des scalaires (fixe la précision des calculs) */ typedef double scal_t ;

/* type des vecteurs */ typedef struct { scal_t x ; scal_t y ; } vect_t ;

/*******************************/ /* Opérations sur les vecteurs */ /*******************************/

/* création */ vect_t vect_nouv (scal_t x, scal_t y) ;

/* addition */ vect_t vect_add (vect_t u, vect_t v) ;

/* différence */ vect_t vect_diff (vect_t u, vect_t v) ;

/* produit scalaire */ scal_t vect_scal (vect_t u, vect_t v) ;

/* déterminant */ scal_t vect_det (vect_t u, vect_t v) ;

/* norme */ scal_t vect_norm (vect_t u) ;

/* distance */ scal_t vect_dist (vect_t u, vect_t v) ;

1. endif /* #ifndef VECT_H */

</source> Le code vect.c: <source lang="C">

1. include "vect.h"

/*******************************/ /* Opérations sur les vecteurs */ /*******************************/

/* création */ vect_t vect_nouv (scal_t x, scal_t y) { vect_t u ; u.x=x ; u.y=y ; return u ; }

/* addition */ vect_t vect_add (vect_t u, vect_t v) { vect_t w ; w.x = u.x + v.x ; w.y = u.y + v.y ; return w ; }

/* différence */ vect_t vect_diff (vect_t u, vect_t v) { vect_t w ; w.x = u.x - v.x ; w.y = u.y - v.y ; return w ; }

/* produit scalaire */ scal_t vect_scal (vect_t u, vect_t v) { return u.x * v.x + u.y * v.y ; }

/* déterminant */ scal_t vect_det (vect_t u, vect_t v) { return u.x * v.y - u.y * v.x ; }

/* norme */ scal_t vect_norm (vect_t u) { return sqrt(vect_scal(u,u)) ; }

/* distance */ scal_t vect_dist (vect_t u, vect_t v) { return vect_norm(vect_diff(u,v)) ; }

/* ... on pourrait continuer ... */ </source> Et un programme benêt qui l'utilise test_vect.c: <source lang="C">

1. include <stdio.h>
2. include "vect.h"

/***********************/ /* Programme principal */ /***********************/

void aff_calcul (const char calcul[], scal_t valeur) { printf("%20s = %5.2f\n",calcul, valeur) ; }

int main () {

vect_t u = vect_nouv(1,1) ; vect_t v = vect_nouv(-1,2) ;

/* Affichage des vecteurs choisis */

printf("Avec u=(%5.2f,%5.2f) et v=(%5.2f,%5.2f), on a :\n\n",u.x,u.y,v.x,v.y) ;

/* Calculs */ aff_calcul("|u|",vect_norm(u)) ; aff_calcul("|v|",vect_norm(v)) ; aff_calcul("u.v",vect_scal(u,v)) ; aff_calcul("det(u,v)",vect_det(u,v)) ; aff_calcul("dist(u,v)",vect_dist(u,v)) ;

printf("\n") ;

return 0 ;

} </source>

Pointeurs dans les structures

Une bibliothèque de buffers.

En-têtes char_buf.h: <source lang="C">

1. ifndef CHAR_BUF_H
2. define CHAR_BUF_H

1. include <stdio.h>

typedef char elem_t ;

typedef struct { size_t nb ; /* Nombre d'éléments du buffer */ elem_t *buf ; /* Pointeur vers le premier élément */ } buf_t ;

buf_t buff_new (size_t nb) ;

void buff_free (buf_t b) ;

size_t buff_size (buf_t b) ;

buf_t buff_resize (buf_t b, size_t nb) ;

1. endif /* #ifndef CHAR_BUF_H */

</source>

Code char_buf.c: <source lang="C">

1. include <stdlib.h>
2. include "char_buf.h"

buf_t buff_new (size_t nb) { buf_t b ; elem_t *buf = (elem_t *) malloc(sizeof(elem_t) * nb) ; if (buf != NULL) { b.nb = nb ; b.buf = buf ; } else { b.nb = 0 ; } return b ; }

void buff_free (buf_t b) { if (b.buf != NULL) free(b.buf) ; }

size_t buff_size (buf_t b) { return b.nb ; }

buf_t buff_resize (buf_t b, size_t nb) { char *buf = realloc(b.buf,nb) ; if (buf != NULL) { b.nb = nb ; b.buf = buf ; } else { b.nb = 0 ; } return b ; } </source>

Un exemple complet avec: struct, union, enum

Un exemple un peu arbitraire pour fabriquer un type composé. On abstrait au maximum.

D'abord les valeurs (données dans une union): En-têtes val.h: <source lang="C">

1. ifndef VAL_H
2. define VAL_H

typedef union { char c ; unsigned long int u ; long int i ; long double f ; const char *s ; } val_t ;

/* Constructeurs pour le type val_t */

val_t val_char (char c) ; val_t val_uint (unsigned long int u) ; val_t val_int (long int i) ; val_t val_float (long double f) ; val_t val_chaine (const char s[]) ;

1. endif /* #ifndef VAL_H */

</source>

Code val.c: <source lang="C">

1. include "val.h"

/* Constructeurs pour le type val_t */

val_t val_char (char c) { val_t v ; v.c = c ; return v ; }

val_t val_uint (unsigned long int u) { val_t v ; v.u = u ; return v ; }

val_t val_int (long int i) { val_t v ; v.i = i ; return v ; }

val_t val_float (long double f) { val_t v ; v.f = f ; return v ; }

val_t val_chaine (const char s[]) { val_t v ; v.s = s ; return v ; } </source>

Ensuite le type comp_t construit comme une somme disjointe.

En-têtes comp.h: <source lang="C">

1. ifndef COMP_H
2. define COMP_H

1. include <stdio.h>
2. include "val.h"

/* On définit un type composé comp_t, qui peut contenir des données de types

* divers :
*  - le type union val_t défini dans val.h est assez grand pour contenir une donnée ;
*  - le champ de type cas_t est une clé qui renseigne sur le type de la donnée.
**/

typedef enum { CHAR, UINT, INT, FLOAT, CHAINE, FIN } cas_t ;

typedef struct { cas_t cas ; val_t val ; } comp_t ;

/* Constructeurs pour le type comp_t */

comp_t comp_char (char c) ; comp_t comp_uint (unsigned long int u) ; comp_t comp_int (long int i) ; comp_t comp_float (long double f) ; comp_t comp_chaine (const char s[]) ; comp_t comp_fin () ;

/* Affiche un comp_t */ int comp_aff (comp_t x) ;

/* Formate une chaîne de comp_t :

* les éléments sont affichés entre crochets et on s'arrête sur FIN 
* */

int comp_aff_s (comp_t t[]) ;

1. endif /* #ifndef COMP_H */

</source>

Code comp.c: <source lang="C">

1. include "val.h"
2. include "comp.h"

/* Constructeurs pour le type comp_t */

comp_t compose (cas_t cas, val_t val) { comp_t x ; x.cas = cas ; x.val = val ; return x ; }

comp_t comp_char (char c) { return compose(CHAR,val_char(c)) ; }

comp_t comp_uint (unsigned long int u) { return compose(UINT,val_uint(u)) ; }

comp_t comp_int (long int i) { return compose(INT,val_int(i)) ; }

comp_t comp_float (long double f) { return compose(FLOAT,val_float(f)) ; }

comp_t comp_chaine (const char s[]) { return compose(CHAINE,val_chaine(s)) ; }

comp_t comp_fin () { comp_t x ; x.cas = FIN ; return x ; }

/* Affiche un comp_t */ int comp_aff (comp_t x) { cas_t cas = x.cas ; if (cas == CHAR) printf("%c",x.val.c) ; else if (cas == UINT) printf("%lx",x.val.u) ; else if (cas == INT) printf("%ld",x.val.i) ; else if (cas == FLOAT) printf("%Lf",x.val.f) ; else if (cas == CHAINE) printf("%s",x.val.s) ; else return 1 ; return 0 ; }

/* Formate une chaîne de comp_t :

* les éléments sont affichés entre crochets et on s'arrête sur FIN 
* */

int comp_aff_s (comp_t t[]) { comp_t x ; cas_t cas ; int i ; /* nombre de comp_t lus sauf FIN */ x = t[0] ; i = 0 ; cas = x.cas ; while (cas != FIN) { putchar('[') ; comp_aff(x) ; putchar(']') ; ++i ; x = t[i] ; cas = x.cas ; } putchar('\n') ; return i ; }

</source>

En un programme d'exemple test_comp.c: <source lang="C">

1. include <stdio.h>

1. include "val.h"
2. include "comp.h"

int main () { comp_t t[6] ; t[0]=comp_int(127) ; t[1]=comp_uint(127) ; t[2]=comp_char('a') ; t[3]=comp_chaine("un test") ; t[4]=comp_float(3.14159) ; t[5]=comp_fin() ; comp_aff_s(t) ; return 0 ; } </source>

Premier partiel

Le sujet de l'épreuve de 30 minutes: INFO517-Partiel1.pdf.

Cours/TD 6 : lundi 3 novembre 2008

Structures récursives

Quand on veut déclarer un type récursif (ou auto-référentiel), la syntaxe suivante est rejetée: <source lang="C"> typedef struct { int data ; bloc_t *suivant ; } bloc_t ; </source> Le problème est que le type bloc_t n'est pas encore défini au moment où on écrit la structure.

Il faut utiliser la syntaxe plus précise: <source lang="C"> typedef struct bloc_rec_t { int data ; struct bloc_rec_t *suivant ; } bloc_t ; </source>

L'idée est que <source lang="C"> struct bloc_rec_t { int data ; struct bloc_rec_t *suivant ; } </source> Déclare un nouveau nom de structure bloc_rec_t. Et alors struct bloc_rec_t est un type.

La version précédente revient à: <source lang="C"> struct bloc_rec_t { int data ; struct bloc_rec_t *suivant ; } typedef struct bloc_rec_t bloc_t ; </source>

Pour fixer les idées, on peut revenir au type des vecteurs vu plus haut, en utilisant la syntaxe de déclaration des structures: <source lang="C">

1. include <stdio.h>

struct vect_t { double x ; double y ; } ;

int main () { struct vect_t v = { 1, 2 } ; printf("(%4.2f,%4.2f)\n",v.x,v.y) ; return 0 ; } </source>

La déclaration struct vect_t v dit que v est une variable de type struct vect_t.

La définition struct vect_t v = { 1, 2 } ; initialise v avec 1 dans le premier champ (x) et 2 dans le second (y).

On utilisera souvent des pointeurs vers des structures. Si type_t est le type d'une structure qui comporte un champ x, alors on voudra souvent considérer un pointeur <source lang="C"> type_t *p; </source> et faire référence au champ x de la structure pointée par p: (*p).x. C'est tellement courant qu'il existe une notation abrégée pour cette opération: p->x. On pourra ainsi écrire le programme suivant: <source lang="C">

1. include <stdio.h>

struct vect_t { double x ; double y ; } ;

int main () { struct vect_t v = { 1, 2 } ; struct vect_t *p = &v ; printf("(%4.2f,%4.2f)\n",p->x,p->y) ; return 0 ; } </source> qui fait la même chose que le précédent.

Un exemple complet avec une pile

On construit un programme qui lit des lignes sur son entrée, et les affiches de la dernière à la première.

D'abord, on rappelle la fonction lit_ligne déjà vu plus haut, qu'on met dans une bibliothèque minimaliste:

En-têtes liste.h: <source lang="C">

1. ifndef LIGNE_H
2. define LIGNE_H

/* On alloue par blocs de taille LIGNE_MORCEAU. */

1. define LIGNE_MORCEAU 1024

/* Lit une ligne en entrée _quelle que soit sa taille_

* et la stocke dans *p (p est un pointeur sur une chaîne).
* Renvoie le nombre de caractère lus (-1 en cas d'erreur). */

int lit_ligne (char **p) ;

1. endif /* #ifndef LIGNE_H */

</source>

Code ligne.c: <source lang="C">

1. include <stdlib.h>
2. include <stdio.h>
3. include "ligne.h"

int lit_ligne (char **p) { char c ; char *s ; int pos, blocs, i ;

/* La position courante dans la chaîne est i+LIGNE_MORCEAU*blocs. */ pos = blocs = i = 0 ;

/* On alloue le premier morceau. */ s = malloc ((++blocs)*LIGNE_MORCEAU*sizeof(char)) ; if (s == NULL) return -1 ;

while ((c=getchar())!=EOF && c!='\n') { s[pos] = c ; if (i==LIGNE_MORCEAU-1) { /* on déborderait en faisant ++i, donc on alloue plus de mémoire */ if ((s=realloc(s,(++blocs)*LIGNE_MORCEAU*sizeof(char))) == NULL) { return -1 ; /* plus de mémoire disponible: on quitte */ } i=0 ; } else { ++i; } ++pos ; }

/* si c == '\n' il faut l'ajouter */

if (c=='\n') { s[pos] = c ; /* on pourrait déborder en ajoutant le '\0': on gère ça */ if (i==LIGNE_MORCEAU-1) { if ((s=realloc(s,(pos+1)*sizeof(char))) == NULL) return -1 ; /* plus de mémoire disponible: on quitte */ } ++pos ; }

s[pos]='\0' ; *p=s ; return pos ;

} </source>

Ensuite, on donne un type pour les piles de chaînes de caractères, et les fonctions usuelles.

En-têtes pile.h: <source lang="C">

1. ifndef PILE_H
2. define PILE_H

typedef char data_t ;

typedef struct bloc_rec_t { data_t *data ; struct bloc_rec_t *suivant ; } bloc_t ;

typedef bloc_t *pile_t ;

/* Renvoie une pile vide */ pile_t pile_cree () ;

/* Teste si une pile est vide (1 si vide, 0 sinon) */ int pile_vide (pile_t p) ;

/* Empile la donnée d sur la pile *p.

* En cas de succès, renvoie la nouvelle valeur de *p. 
* Sinon, renvoie NULL (et alors *p est inchangé). */

pile_t pile_empile (pile_t *p, data_t *d) ;

/* Dépile la donnée au sommet de la pile.

* Renvoie NULL en cas d'échec (pile vide). */

data_t *pile_depile (pile_t *p) ;

1. endif

</source>

Code pile.c: <source lang="C">

1. include <stdlib.h>
2. include "pile.h"

pile_t pile_cree () { return NULL ; }

int pile_vide (pile_t p) { return (p == NULL) ; }

pile_t pile_empile (pile_t *p, data_t *d) { pile_t q = malloc (sizeof(bloc_t)) ; if (q != NULL) { q->data = d ; q->suivant = *p ; *p = q ; } return q ; }

data_t *pile_depile (pile_t *p) { pile_t q = *p ; data_t *d = NULL ; if (!pile_vide(q)) { d=q->data ; *p=q->suivant ; free(q) ; } return d ; } </source>

Le programme principal test_pile.c: <source lang="C">

1. include <stdio.h>
2. include <stdlib.h>
3. include "ligne.h"
4. include "pile.h"

/* Lit des lignes, puis les affiche de la dernière à la première */ int main () { char *l ; pile_t p = pile_cree() ; int ret ;

printf("Tapez des lignes\n") ; while ((ret=lit_ligne(&l))>0) { pile_empile(&p,l) ; } if (ret<0) return -1 ; while(!pile_vide(p)) { l=pile_depile(&p) ; printf("%s",l) ; free(l) ; } return 0 ; } </source>

Makefile

Pour compiler le tout (avec les options usuelles), il faudrait écrire

 $ gcc -Wall -pedantic -o test_pile test_pile.c pile.c ligne.c 

et même, de manière plus modulaire:

 $ gcc -Wall -pedantic -o pile.o -c pile.c
 $ gcc -Wall -pedantic -o ligne.o -c ligne.c
 $ gcc -Wall -pedantic -o test_pile.o -c test_pile.c
 $ gcc -Wall -pedantic -o test_pile test_pile.o pile.o ligne.o

Ça devient fastidieux. L'outil make a été conçu pour ce genre de situation.

On peut écrire le fichier Makefile:

 CC=gcc
 CFLAGS=-Wall -pedantic

 all: test_pile

 test_pile: pile.o ligne.o test_pile.o
 	$(CC) $(CFLAGS) -o test_pile $^

 clean:
 	rm -f pile.o ligne.o test_pile.o test_pile 

et alors la commande make fait le nécessaire:

 $ make
 gcc -Wall -pedantic   -c -o pile.o pile.c
 gcc -Wall -pedantic   -c -o ligne.o ligne.c
 gcc -Wall -pedantic   -c -o test_pile.o test_pile.c
 gcc -Wall -pedantic -o test_pile test_pile.o pile.o ligne.o

La syntaxe des Makefile décrit des dépendances sous la forme:

 cible: dependance_1 dependance_2 ... dependance_n
   commande

c'est-à-dire: pour fabriquer cible j'ai besoin des fichiers dependance_? et j'appelle la commande commande.

On peut définir des variables (première ligne) et il existe des cibles spéciales (all et clean) qui ne produisent pas de fichier au nom de la cible.

Notez que la conversion des *.o aux *.c est faite automatiquement (et utilise les variables CC et CFLAGS): ceci correspond à des règles par défaut de make.

La syntaxe des Makefiles est assez riche et puissance: la lecture de la documentation est conseillée. On utilisera tout ça en TP.

Exercices en TD

Feuille 2.

Références

• The C programming language, de Kernighan et Ritchie;
• Le langage C, version française du précédent;
• Le polycopié de Bernard Cassagne, disponible ici, au format html (consultable en ligne) ou pdf;
• Le wikilivre Programmation C: un livre de cours sur le mode wikipedia.