Attention

Programmation Impérative 2

Septembre -- Décembre 2019

1. Présentation
2. Programmation structurée
3. Indirections et Fonctions
4. Exemples : images
5. Les énoncés de projets

1. Présentation

   • Objectifs

   • Prérequis

   • Pratique

2. Programmation strcuturée

   1. Exemples
      1. Un exemple

         Voici un programme simple que nous voudrions structurer :

         #include <stdio.h> double puis (double x, int n) { double res = 1.0; while (n) { if (n & 0x01) res *= x; x *= x; n >>= 1; } return res; } main () { int n; double y; for (y=0.0; y < 3.1; y += 0.2) { for (n = 0; n < 10; n++) printf ("%3.5lf ^ %d == %6.8lf\n", y, n, puis(y,n)); } }

         
         

      2. Spécification

         D'abord, il faut spécifier pour la fonction puis. Elle renvoie un double et reçoit comme paramètre un double et un entier.

         double puis (double, int) ;

         
         Nous nommerons ceci, la "spécification" de la fonction. Vous avez sans doute déjà remarqué que si la fonction appelante est placée avant la fonction appelée, par défaut, le compilateur applique un type entier comme type de la valeur retournée. Ceci est à la base de nombreuses erreurs. Pour éviter cela, commencez, en tête de fichier, par spécifier toutes vos fonctions.
         

      3. Séparation

         Ensuite, séparez ce programme en trois parties :

         • l'entête, puis.h,
         • le fichier contenant la fonction, puis.c,
         • le fichier contenant la fonction main, main.c.
         Il suffit alors que les deux fichiers .c commencent par

         #include "puis.h"

         
         pour que cet entête soit inclus automatiquement dans votre programme. Nous arrivons alors à avoir trois fichiers, qui accompagnent la compilation suivante :

         $gcc main.c puis.c -o puissances

         
         Mais pour répartir le travail vaut mieux encore séparer aussi la compilation, en faisant faire d'abord le code objet (.o) de chaque fichier. L'utilisation d'un fichier Makefile de base fait ce travail.

         CC=gcc puissance: main.o puis.o puis.h $(CC) -o puissance main.o puis.o main.o: main.c puis.h $(CC) -c main.c puis.o: puis.c puis.h $(CC) -c puis.c clean: rm *.o *~ core

         
         À l'usage, si on veut compiler le programme on fait simplement :

         $make

         
         Toutes les compilations ont lieu alors avec vérification, par leur date, de l'antériorité des fichiers, de façon à ne compiler que ceux qui ont été modifiés depuis la dernière compilation.
         Premier fichier Makefile :

         # Compilation generique par Bourdin CC=gcc SRC=puis.c main.c OBJ=puis.o main.o CFLAGS=-Wall fil: $(OBJ) puis.h $(CC) -o $@ $(OBJ) main.o: main.c $(CC) -c main.c $(CFLAGS) puis.o: puis.c $(CC) -c puis.c $(CFLAGS)

         
         Mais on fera mieux ainsi :

         CC=gcc SRC=puis.c main.c OBJ=$(SRC:.c=.o) FLAGS=-Wall fil: $(OBJ) puis.h $(CC) -o $@ $(OBJ) %.o: %.c $(CC) -c $< $(CFLAGS) clean: rm *.o *~ core

         
         Vous trouverez dans sur ce support des précisions sur les variables prédéfinies dans un fichier Makefile.

      4. Second exemple
         Voici un petit programme qui fait, qui fait quoi, d'ailleurs ?
         Il s'agit, ici aussi de le séparer en plusieurs fichiers.

         #define MAX 100000 typedef unsigned short Shu; int suite (int n) { int a; a = n >> 1; if (n & 0x01) return 3 * (a + 1); return a; } int main (int argc, char * * argv) { int n, i, v, seed; Shu tab [MAX], *crt; if (argc > 1) n = atoi (argv[1]); else n = 7; for (seed = 1; seed < 900; seed++) { for (i = 0, crt = tab; i < MAX; i++) *crt++ = (Shu) 0; v = seed; tab [v] = 1; for (i = 1; i < n; i++) { v = suite (v); if (v > MAX) { printf("Depassement pour %d : %d\n", seed, v); exit (0); } if (tab[v]) break; tab[v] = 1; } if (n == i) printf("seed %d \t n %d i %d\n", seed, n, i); } }

      5. Exercices

         Implémenter les deux exemples ci-dessus.

         Prendre un programme déjà fait en C, le séparer en divers fichiers et créer le Makefile correspondant. Vérifier que la compilation se passe correctement.

   2. Compilation

      1. Détour par le printf
         

         Voir la page wikipedia la plus sérieuse sur le sujet.

      2. Les quatre étapes
         1. Précompilation (option -E)
            On peut supposer que vous savez utiliser les directives de précompilation, les pseudo fonctions, la compilation conditionnelle, sinon, posez des questions !
            
         2. Code assembleur (option -S)
            Voici un exemple d'utilisation. D'abord, le programme
            

            #include <stdio.h> int fct (int n) { int i, v1, v2; v1 = 1; v2 = 1; i = 2; while (i <= n) { v2 += v1; v1 = v2 - v1; i++; } return v2; } int ftc (int n) { if (n < 2) return 1; return ftc(n-1) + ftc (n-2); } main () { int n = 0; while (n < 20) { printf("f(%3d)\t== %d\n",n, fct(n)); printf("\t== %d\n", ftc(n)); n++; } }

            
            Une deuxième version, à peine différente :

            #include <stdio.h> int fct (int n) { int i, v1, v2; v1 = 1; v2 = 1; for (i = 2; i <= n; i++) { v2 += v1; v1 = v2 - v1; } return v2; } int ftc (int n) { if (n < 2) return 1; return ftc(n-1) + ftc (n-2); } main () { int n; for (n = 0; n < 20; n++) { printf("f(%3d)\t== %d\n",n, fct(n)); printf("\t== %d\n", ftc(n)); } }

            
            Voici le code assembleur généré par ces deux programmes, il est identitque :
            

            .text .globl _fct _fct: LFB3: pushq %rbp LCFI0: movq %rsp, %rbp LCFI1: movl %edi, -20(%rbp) movl $1, -8(%rbp) movl $1, -12(%rbp) movl $2, -4(%rbp) jmp L2 L3: movl -8(%rbp), %eax addl %eax, -12(%rbp) movl -8(%rbp), %edx movl -12(%rbp), %eax subl %edx, %eax movl %eax, -8(%rbp) incl -4(%rbp) L2: movl -4(%rbp), %eax cmpl -20(%rbp), %eax jle L3 movl -12(%rbp), %eax leave ret LFE3: .globl _ftc _ftc: LFB4: pushq %rbp LCFI2: movq %rsp, %rbp LCFI3: pushq %rbx LCFI4: subq $24, %rsp LCFI5: movl %edi, -20(%rbp) cmpl $1, -20(%rbp) jg L7 movl $1, -24(%rbp) jmp L9 L7: movl -20(%rbp), %edi decl %edi call _ftc movl %eax, %ebx movl -20(%rbp), %edi subl $2, %edi call _ftc addl %eax, %ebx movl %ebx, -24(%rbp) L9: movl -24(%rbp), %eax addq $24, %rsp popq %rbx leave ret LFE4: .cstring LC0: .ascii "f(%3d)\11== %d\12\0" LC1: .ascii "\11== %d\12\0" .text .globl _main _main: LFB5: pushq %rbp LCFI6: movq %rsp, %rbp LCFI7: subq $16, %rsp LCFI8: movl $0, -4(%rbp) jmp L12 L13: movl -4(%rbp), %edi call _fct movl -4(%rbp), %esi movl %eax, %edx leaq LC0(%rip), %rdi movl $0, %eax call _printf movl -4(%rbp), %edi call _ftc movl %eax, %esi leaq LC1(%rip), %rdi movl $0, %eax call _printf incl -4(%rbp) L12: cmpl $19, -4(%rbp) jle L13 leave ret LFE5: .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support EH_frame1: .set L$set$0,LECIE1-LSCIE1 .long L$set$0 LSCIE1: .long 0x0 .byte 0x1 .ascii "zR\0" .byte 0x1 .byte 0x78 .byte 0x10 .byte 0x1 .byte 0x10 .byte 0xc .byte 0x7 .byte 0x8 .byte 0x90 .byte 0x1 .align 3 LECIE1: .globl _fct.eh _fct.eh: LSFDE1: .set L$set$1,LEFDE1-LASFDE1 .long L$set$1 LASFDE1: .long LASFDE1-EH_frame1 .quad LFB3-. .set L$set$2,LFE3-LFB3 .quad L$set$2 .byte 0x0 .byte 0x4 .set L$set$3,LCFI0-LFB3 .long L$set$3 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$4,LCFI1-LCFI0 .long L$set$4 .byte 0xd .byte 0x6 .align 3 LEFDE1: .globl _ftc.eh _ftc.eh: LSFDE3: .set L$set$5,LEFDE3-LASFDE3 .long L$set$5 LASFDE3: .long LASFDE3-EH_frame1 .quad LFB4-. .set L$set$6,LFE4-LFB4 .quad L$set$6 .byte 0x0 .byte 0x4 .set L$set$7,LCFI2-LFB4 .long L$set$7 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$8,LCFI3-LCFI2 .long L$set$8 .byte 0xd .byte 0x6 .byte 0x4 .set L$set$9,LCFI5-LCFI3 .long L$set$9 .byte 0x83 .byte 0x3 .align 3 LEFDE3: .globl _main.eh _main.eh: LSFDE5: .set L$set$10,LEFDE5-LASFDE5 .long L$set$10 LASFDE5: .long LASFDE5-EH_frame1 .quad LFB5-. .set L$set$11,LFE5-LFB5 .quad L$set$11 .byte 0x0 .byte 0x4 .set L$set$12,LCFI6-LFB5 .long L$set$12 .byte 0xe .byte 0x10 .byte 0x86 .byte 0x2 .byte 0x4 .set L$set$13,LCFI7-LCFI6 .long L$set$13 .byte 0xd .byte 0x6 .align 3 LEFDE5: .subsections_via_symbols

            
            
         3. Code objet (option -c)
         4. Édition de liens (option -o)
      3. Exemples d utilisation des bibliothèques
         On trouvera de la documentation précise sur les bibliothèques standard sur les liens suivants :
         • Ici
         • ou ici et les pages suivantes
         • ou, moins bien : ici.
         • assert
           

           #include <assert.h> #include <stdio.h> /*Premiere version : main () { int i, j, n; n = 10; for (i=0, j=0; i <= n; i++){ j += 1 + (i << 1); assert(j==(i*i)); printf("%d carre == %d\n",i,j); } } /* Macintosh.local: gcc asser.c Macintosh.local: a.out Assertion failed: (j==(i*i)), function main, file asser.c, line 9. Abort trap */ /* Seconde version */ main () { int i, j, n; n = 10; for (i=0, j=0; i <= n; i++){ assert(j==(i*i)); printf("%d carre == %d\n",i,j); j += 1 + (i << 1); } } /* Macintosh.local: gcc asser.c Macintosh.local: a.out 0 carre == 0 1 carre == 1 2 carre == 4 3 carre == 9 4 carre == 16 5 carre == 25 6 carre == 36 7 carre == 49 8 carre == 64 9 carre == 81 10 carre == 100 */

           • setjmp
             Il s agit donc de "sauter" à un endroit prédéfini avec une valeur d environnement.
             

             #include <setjmp.h> #include <stdio.h> jmp_buf ebuf; /* ceci est une variable globale, mais comment l eviter ?*/ void f2(void); int main(void) { int i; printf("1 "); i = setjmp(ebuf); printf("\t ligne : %d\n", __LINE__); if(i == 0) { printf("\t ligne : %d\n", __LINE__); f2(); printf("This will not be printed."); } printf("%d \n", i); return 0; } void f2(void) { printf("2 "); printf("\t ligne : %d\n", __LINE__); longjmp(ebuf, 3); } /* 1 ligne : 13 ligne : 15 2 ligne : 27 ligne : 13 3 */

             #include <setjmp.h> #include <stdio.h> jmp_buf ebuf, env, env2; /* ce sont des variables globales, encore ! */ void f2(void); void f1(void); int main(void) { int i; printf("1 "); i = setjmp(ebuf); printf("\t ligne : %d\n", __LINE__); if(i == 0) { printf("\t ligne : %d\n", __LINE__); i = setjmp(env); if (i) { printf("i : %d\t ligne : %d\n", i, __LINE__); return 0; } f2(); printf("This will not be printed."); } printf("%d \n", i); f1(); return 0; } void f1(void) { printf("f1 "); printf("\t ligne : %d\n", __LINE__); longjmp(env, 35); } void f2(void) { printf("2 "); printf("\t ligne : %d\n", __LINE__); longjmp(ebuf, 3); } /* JJBook : a.out 1 ligne : 13 ligne : 15 2 ligne : 36 ligne : 13 3 f1 ligne : 31 i : 35 ligne : 18 */

           • signal.h : Petit exemple amusant :

             #include<stdio.h> #include<signal.h> #include<unistd.h> void sig_handler(int signo) { if (signo == SIGINT) printf("received SIGINT\n"); } int main(void) { if (signal(SIGINT, sig_handler) == SIG_ERR) printf("\ncan't catch SIGINT\nIf you get this message something is definitely wrong\n"); // A long long wait so that we can easily issue a signal to this process while(1) sleep(1); return 0; } dhcp8.ai.univ-paris8.fr: gcc sighandle.c dhcp8.ai.univ-paris8.fr: a.out ^Creceived SIGINT ^Creceived SIGINT ^Z [1]+ Stopped a.out dhcp8.ai.univ-paris8.fr: bg [1]+ a.out & dhcp8.ai.univ-paris8.fr: dhcp8.ai.univ-paris8.fr: jobs [1]+ Running a.out & dhcp8.ai.univ-paris8.fr: kill %1 dhcp8.ai.univ-paris8.fr: [1]+ Terminated: 15 a.out dhcp8.ai.univ-paris8.fr: jobs dhcp8.ai.univ-paris8.fr:

             Une fois le process lancé, je ne peux plus l'interrompre avec un contrôle C. Par contre, s'il est détaché, c'est le système qui lui envoie un (autre) message d'interruption et il s'arrête enfin.
             Deuxième exemple, pour sortir gentiment d'un seg fault.

             /* signal exemple : sortie douce de SegFault */ #include <stdio.h> #include <stdlib.h> #include <signal.h> void catch(int); int main(int argc, char **argv) { int a, *ptr; signal(SIGSEGV, catch); /* intercepte SIGSEGV - SegFault */ a = *ptr; /* Qu'y-a-til l'adresse 0 ? */ } void catch(int snum) { printf("Signal recu %d\n", snum); exit(0); } /* dhcp8.ai.univ-paris8.fr: gcc newsignal.c dhcp8.ai.univ-paris8.fr: a.out Signal recu 11 */

           • stdarg.h :

             #include <stdarg.h> /* Pour va_list */ #include <stdio.h> /* Pour printf */ void afficher (const char *format, const char *espace, ...) { /* Liste des arguments */ va_list args; /* Initialisation, à partir du dernier paramètre connu */ va_start (args,espace); /* Parcours de la chaîne de format et affichage des données */ int i; for (i=0; format[i]; i++) switch (format[i]) { case 'C' : case 'c' : printf ("%c%s",va_arg(args,int),espace); break; case 'D' : case 'd' : case 'i': printf ("%d%s",va_arg(args,int),espace); break; case 'E' : printf ("%E%s",va_arg(args,double),espace); break; case 'e' : printf ("%e%s",va_arg(args,double),espace); break; case 'F' : case 'f' : printf ("%f%s",va_arg(args,double),espace); break; case 'G' : printf ("%G%s",va_arg(args,double),espace); break; case 'g' : printf ("%g%s",va_arg(args,double),espace); break; case 'H' : printf ("%X%s",va_arg(args,int),espace); break; case 'h' : printf ("%x%s",va_arg(args,int),espace); break; case 'O' : case 'o' : printf ("%o%s",va_arg(args,int),espace); break; case 'P' : case 'p' : printf ("%p%s",va_arg(args,void*),espace); break; case 'S' : case 's' : printf ("%s%s",va_arg(args,char*),espace); break; default : ; } /* Fermeture */ va_end (args); printf("\n"); } /* Exemple d'utilisation */ int main () { afficher ("ioHefGcsp"," ",9572,9572,9572,6569.28,6569.28,6569.28,'$',"Exemple",NULL); }

             
             
           Exercices À faire dans l'ordre que vous préférez, plutôt du dernier au premier, non ?
           • Nous avons donc, ici, utilisé stdarg pour réinventer la fonction printf. Ce n est pas forcément le meilleur exemple. Faites une fonction qui calcule la suite de Fibonacci par récursivité terminale. On sait le faire avec une fonction "chapeau". Supprimez la fonction chapeau par l usage de stdarg. Il vous faut donc une seule fonction pour faire la fonction chapeau et la fonction récursive terminale.

           • Faites une procédure de sauvegarde de données.
             Arrangez-vous pour la lancer lorsque le programme s interrompt.
             Notez que, avec signal, les passages de paramètre vont être un peu complexe, l utilisation d un setjmp bien pensé permet d éviter cet écueil.

           • Écrivez un type permettant de lier deux entiers de taille "unsigned long long int". Écrivez une fonction qui prend deux entiers en paramètre et renvoie un objet de votre type contenant le reste et le résultat de la division entière du premier paramètre par le second.
             En quoi ce travail est-il différent de la fonction standard div ?

             Exemple de solutions :

             #include <stdio.h> #include <stdarg.h> int fib (int arg1, ...) { va_list liste; int v, w; if (arg1 < 0) { va_start(liste,arg1); v = va_arg(liste, int); w = va_arg(liste, int); va_end(liste); if (arg1 < -2) { return fib(arg1 + 1, v + w, v); } return v; } if (arg1) return fib(-arg1, 1, 1); return 1; } int main () { int i, n; i = 10; for (i = 0; i < 11; i++) { n = fib(i + 1); printf("Resultat de %d\t %d\n", i, n); } } /* Resultat de 0 1 Resultat de 1 1 Resultat de 2 2 Resultat de 3 3 Resultat de 4 5 Resultat de 5 8 Resultat de 6 13 Resultat de 7 21 Resultat de 8 34 Resultat de 9 55 Resultat de 10 89 */

         • Librairie stddef.h

         • Librairie stdlib.h

           #include <stdio.h> #include <stdlib.h> void sortie () { printf("This is the end\n"); } void finir () { printf("My only friend the end\n"); } void definir () { printf("Of everything that stands the end\n"); } void refinir () { printf("Of our elaborate plans the end\n"); } int main () { printf("Jim Morrisson\n\nThe end\n\n"); atexit(definir); atexit(refinir); atexit(finir); atexit(sortie); } /*Jim Morrisson The end This is the end My only friend the end Of our elaborate plans the end Of everything that stands the end */

         • Écriture sur fichiers

           Voici un programme qui permet de travailler. D abord son Makefile :
           

           # Compilation generique par Bourdin CC=gcc SRCDIRECT=miam.c fibiter.c direct.c OBJDIRECT=$(SRCDIRECT:.c=.o) FLAGS=-Wall fool: $(OBJDIRECT) direct.h $(CC) -o $@ $^ rm fib.dat %.o: %.c $(CC) -o $@ -c $< $(CFLAGS) clean: rm *.o *~ core hop: for i in 0 1 2 3 4 5 6 7 8 9 do ./fool $i ; done

           
           puis le fichier header :

           /*direct.h*/ #include <stdio.h> #include <stdlib.h> int fibiter (int); int lire (FILE *, int); int remplir (FILE *, int);

           Il vous faut la fonction main :

           /* miam.c */ #include "direct.h" #define NOM "fib.dat" #define NORMAL 43 int main (int argc, char * * argv) { FILE * fichier; int i, j, v, w; if (argc == 2) { i = atoi (argv [1]); if ((fichier = fopen(NOM,"r+"))!= NULL) { // printf("On cherche fib(%d)\n",i); v = lire (fichier, i); printf("fib(%d) = %d\n",i,v); } else { if ((fichier = fopen(NOM,"w+"))== NULL) { printf(" Rien a faire nous revenons a une fonction classique\n"); v = fibiter (i); printf("fib(%d) = %d\n",i,v); } else { v = remplir (fichier, i); printf("fib(%d) = %d \n",i,v); } } fclose(fichier); } else { /* Taille indefinie */ if ((fichier = fopen(NOM,"r+"))== NULL) { printf("il faut creer ce fichier \n\n"); fichier = fopen(NOM,"w+"); v = remplir (fichier, NORMAL); w = lire (fichier, NORMAL); printf("fib(%d) = %d == %d\n",NORMAL,v, w); fclose (fichier); } else { v = lire (fichier, NORMAL); printf("fib(%d) = %d \n",NORMAL,v); close(fichier); } } }

           Il vous faut le fichier où on écrit les données :

           /*direct.c*/ /* Il s agit de lire et d ecrire dans un fichier massif */ #include "direct.h" int lire (FILE * f, int nb) { int nf, i, v, w, * tf; /* on commence par savoir s il y a assez d elements dans f*/ fread(&nf, (size_t) 4, (size_t) 1, f); printf("Dans ce fichier il y a %d elements\n",nf); if (nf > nb) { tf = (int *) malloc ((nb+1) * sizeof (int)); fread(tf, (size_t) 4, (size_t) (1 + nb), f); for (i=0; i <= nb; i++) { printf("fib(%d) == %d\n",i, tf[i]); } return tf[nb]; } else { return remplir (f, nb); } } int remplir (FILE * f, int nb) { int nf, i, v, w, * tf; tf = (int *) malloc ((nb+1) * sizeof (int)); tf[0] = 1; tf[1] = 1; for (i=2, v=1, w=1; i <= nb; i++) { v += w; tf[i] = v; w = v - w; } for (i=0; i < nb; i++) { printf("fib(%d) = %d\n",i,tf[i]); } fseek (f,0,SEEK_SET); fwrite(&nb, (size_t) 4, (size_t) (1), f); fwrite(tf, (size_t) 4, (size_t) (1 + nb), f); return tf[nb]; }

           S il vous manque une fonction, comme celle qui calcule la suite de Fibonacci, je vous fais confiance.

           • Faites tourner ce programme.
           • Adaptez-le pour utiliser des entiers beaucoup plus grands (unsigned long long int ?).

           Second exemple

           Nous utilisons maintenant des fprintf et des fscanf, pour faire la même chose. Bien sûr le "programme" n est pas complet sans au moins le fichier main.c qui suit mais il manque d autres choses...

           #include <stdio.h> #include "mydef.h" #define NOM "num.dat" #define SIZE 45 void remplir (FILE * f) { int i,n,m,p; n=1, m=1; fprintf(f,"%9d %9d %9d ",SIZE,1,1); for (i=2;i < SIZE; i++ ) { p = n+m; fprintf(f,"%9d ",p); n=m; m=p; printf("%d ",p); } fprintf(f,"\n"); printf("\n"); } int remplirn (FILE * f, int nb) { int i,n,m,p; n=1; m=1; p=1; fprintf(f,"%9d %9d %9d ",nb,1,1); for (i=2;i < nb; i++ ) { p = n+m; fprintf(f,"%9d ",p); n=m, m=p; printf("%d ",p); } fprintf(f,"\n"); printf("\n"); return p; } void lire (FILE * f) { int i, j, taille, buf[SIZE]; fscanf(f,"%d ",&j); taille = j > SIZE ? SIZE : j; for (i=0;i < taille;i++) { fscanf(f,"%d ",&j); buf[i]=j; } for (i=0;i < taille;i++) { printf("%9d ",buf[i]); printf("%d |",buf[i]); } printf("\n"); } int liren (FILE * f, int nb) { int i, j, v0, v1, v; long posi; fseek(f, 0, SEEK_SET); fscanf(f,"%d ",&j); if (j > nb) { posi = (nb * 10); fseek(f, posi, SEEK_SET); fscanf(f,"%d ",&v); return v; } /* Il n y avait pas assez de valeurs */ fclose(f); if ((f = fopen(NOM,"r+"))== NULL) { printf("Ca ne va plus du tout\n\n"); return fib(nb); } fseek(f, -19L, 2); fscanf(f,"%d ",&v0); printf("%d => %d\n",j-2, v0); fseek(f, -10L, 2); fscanf(f,"%d ",&v1); printf("%d => %d\n",j-1, v1); for ( ; j < nb; j++ ) { v = v0 + v1; fprintf(f,"%9d ",v); printf("%d ",v); v0 = v1; v1 = v; } v1 = ftell(f); printf("on est maintenant en %d\n",v1); fseek(f,-v1,1); fscanf(f,"%d ",&v0); printf("On y trouve %d\n", v0); fseek(f,0L,SEEK_SET); fprintf(f,"%9d ",nb); printf("remis %d au debut\n", nb); v1 = ftell(f); printf("on est encore en %d\n",v1); fseek(f,-v1,1); fscanf(f,"%d ",&v0); printf("On y trouve %d\n", v0); return v; } int fib (int n) { int v0, v1, v; v0 = 1; v1 = 1; while (--n) { v = v0 + v1; v0 = v1; v1 = v; } return v1; } /* gcc truc.o main.o -o fil neige: fil il faut creer ce fichier 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 neige: fil 49 43 => 408733 44 => 34903170 35311903 70215073 105526976 175742049 281269025 on est maintenant en 512 On y trouve 45 remis 49 au debut on est encore en 522 On y trouve 45 fib(49) = 281269025 neige: cat num.dat 45 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 3 */

           et voici le main.c

           #include <stdio.h> #include "mydef.h" #define NOM "num.dat" int main (int argc, char * * argv) { FILE * fichier; int i, j, v, w; if (argc == 2) { i = atoi (argv [1]); if ((fichier = fopen(NOM,"r"))!= NULL) { v = liren (fichier, i); printf("fib(%d) = %d\n",i,v); } else { if ((fichier = fopen(NOM,"w+"))== NULL) { printf(" Rien a faire nous revenons a une fonction classique\n"); v = fib (i); printf("fib(%d) = %d\n",i,v); } else { v = remplirn (fichier, i); fseek (fichier, -10L, 2); fscanf(fichier,"%d",&w); printf("fib(%d) = %d ou %d\n",i,v, w); } } fclose(fichier); } else if (argc == 3) { i = atoi (argv [1]); j = atoi (argv [2]); // printf("les valeurs de %d a %d\n",i,j); if ((fichier = fopen(NOM,"r"))!= NULL) { for ( ; i <= j; i++) { v = liren (fichier, i); printf("fib(%3d) = %10d\n",i,v); } } else { if ((fichier = fopen(NOM,"w+"))== NULL) { printf(" Rien a faire nous revenons a une fonction classique\n"); for ( ; i <= j; i++) { v = fib (i); printf("fib(%d) = %d\n",i,v); } } else { v = remplirn (fichier, i); fseek (fichier, -10L, 2); fscanf(fichier,"%d",&w); printf("fib(%d) = %d ou %d\n",i,v, w); } } fclose(fichier); } else { /* Taille indefinie */ if ((fichier = fopen(NOM,"r"))== NULL) { printf("il faut creer ce fichier \n\n"); fichier = fopen(NOM,"w+"); remplir (fichier); lire (fichier); fclose (fichier); } else { lire (fichier); fclose(fichier); } } }

         • Times.h
           Exemple 1

           #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<time.h> #include<string.h> int main (int argc, char * * argv) { clock_t cp; int tps_init, tps_crt, dtps, n, i, j; int *veca, *vecb, *vecc, *ptr; if (argc != 2) { n = 100; } else n = (int) atoi (argv[1]); veca = (int *) malloc (n * sizeof(int)); vecb = (int *) malloc (n * sizeof(int)); vecc = (int *) malloc (n * sizeof(int)); assert(veca && vecb && vecc); printf("Temps pour %u avec bzero\t", n); tps_init = (int) clock (); for (i = 0; i < n; i++) { bzero(vecb, n << 2); vecb[i] = i - 2; } tps_crt = (int) clock (); dtps = tps_crt - tps_init; printf(" \t%d\n", dtps); printf("Temps pour %u avec memset\t", n); tps_init = (int) clock (); for (i = 0; i < n; i++) { memset(veca, 0, n << 2); veca[i] = i - 2; } tps_crt = (int) clock (); dtps = tps_crt - tps_init; printf(" \t%d\n", dtps); printf("Temps pour %u avec boucle\t", n); tps_init = (int) clock (); for (i = 0; i < n; i++) { for (j = 0, ptr = vecc; j < n; j++) *ptr++ = 0; } tps_crt = (int) clock (); dtps = tps_crt - tps_init; printf(" \t%d\n", dtps); }

           Vous connaissez plusieurs méthodes permettant de calculer la n-ième valeur de la suite de Fibonacci. Programmez-les et vérifiez laquelle est la plus rapide.

           Même chose avec la valeur n,m du triangle de Pascal.

   
   
   
3. Indirections
   1. Principe général
      Toute déclaration de variable consiste à la création d un triplet (nom, type, emplacement mémoire). Oublier de tenir compte de la mémoire quand on veut gérer les variables est une garantie d insuccès.
   2. Premières fonctions
      

      void intervertir (float * pa, float *pb) { *pa += *pb; *pb = *pa - *pb; *pa = *pa - *pb; }

      
      
      puis une fonction de parcours d un vecteur.

      float somtf (float t[100], int nb) { /* ou t est le vecteur (surdimensionne) et nb le nombre d elements presents */ float s, *ptr; ptr = t; for (s = 0.0; nb--;) s += *ptr++; return s; }

      
      
      
   3. Tableaux dynamiques
      Déclaration :

      typedef unsigned int Uint; struct tabf { Uint nb; float * t; } ; typedef struct tabf tabf;

      
      
      Et maintenant la fonction qui permet de remplir un tel vecteur :

      tabf remplir (Uint nb) { float v, w, * ptr; int i; tabf t; t.t = (float *) malloc (nb * sizeof (float)); assert(t.t); t.nb = nb; v = 1.0; w = 0.215; ptr = t.t; for (i=0; i < nb; i++) { *ptr++ = v; v += w; if (v > 2.0) w -= 0.3; if (v < 1.0) w += 0.3; } return t; }

      
      
      À faire avec un tel tableau, sans jamais utiliser les crochets :
      • Somme des valeurs,
      • moyenne des valeurs,
      • plus grande des valeurs,
      • seconde plus grande des valeurs,
      • concaténer deux vecteurs de ce type,
      • miroir d un tel vecteur,
      • tris d un tel vecteur (quicksort, heapsort, insertion, ...)
      • suppression des doublons.
      
      
   4. Listes

      Une liste est, soit la liste vide (notée NULL ou (liste) 0), soit la construction d un objet et d une liste.

      Voir l exemple de liste donné dans la partie sur la gestion du temps.

      Deuxième exemple, une structure de liste et une fonction pour créer la dite liste.

      struct cell { int n; float val; struct cell * nxt; }; typedef struct cell cell_t; typedef struct cell * liste; liste cons (liste l, int v, float x) { liste new; new = (liste) malloc (sizeof(cell_t)); new->n = v; new->val = x; new->nxt = l; return new; } /* creer la liste avec des valeurs fibonacciennes */ liste creerliste (int nb) { int v, w, x; int * pt; float a, b; liste l, crt; l = (liste) 0; v = 1; a = 1.0; w = 1; b = (float) w / v;; l = cons (l, v, a); l = cons (l, w, b); nb -= 2; while (nb--) { x = (v + w); v = w; w = x; l = cons(l, x, (float) x / v); } return l; }

   5. Exercice amusant
      Faites tourner cette fonction avec 0.0 comme paramètre.

      Comment la corriger ?

      double newton (double x) { double xi; if (x < 0.0) return DBL_MIN; if (x > 0.0) xi = x / 2.0; else xi = 0.005; while (x != xi * xi) { xi = xi / 2.0 + x / (xi * 2.0); printf("%f %f\n", x, xi); } return xi; }

   6. Arbres

      Nous donnons maintenant une structure et une fonction de remplissage d un arbre. Pour cela, il faut utiliser le tableau tel que vu précédemment, nous ne redonnons pas les structures et fonctions correspondantes.
      Commençons par un type et une fonction qui construit un vecteur.

      typedef unsigned int Uint; struct tabf { Uint nb; float * t; } ; typedef struct tabf tabf;

      
      

      tabf remplir (Uint nb) { float v, w, * ptr; int i; tabf t; t.t = (float *) malloc (nb * sizeof (float)); t.nb = nb; v = 1.0; w = 0.215; ptr = t.t; for (i=0; i < nb; i++) { *ptr++ = v; v += w; if (v > 2.0) w -= 0.3; if (v < 1.0) w += 0.3; } return t; }

      
      Ensuite et à partir de là, construire l arbre.

      #define NBF 5 struct noeud { int nb; float val; struct noeud * nxt [NBF]; } ; typedef struct noeud noeud; typedef struct noeud * arbre;

      
      D abord la fonction qui parcourt le vecteur de type tabf pour fabriquer l arbre :

      arbre faitarbre(tabf t) { int i, num; float * ptr; arbre a; a = NULL; num = 0; ptr = t.t + t.nb - 1; while (ptr >= t.t) { a = inserenoeud(a, num, *ptr); num++; ptr--; } return a; }

      
      Puis la fonction qui insère un a un les éléments :

      arbre inserenoeud (arbre a, int num, float v) { int i, j; arbre b; if (! a) { a = malloc (sizeof (noeud)); for (i = 0; i < NBF; i++) a->nxt[i] = NULL; a->nb = num; a->val = v; return a; } for (i = 0; i < NBF; i++) { if (! (a->nxt[i])) { b = malloc (sizeof (noeud)); for (j = 0; j < NBF; j++) b->nxt[j] = NULL; b->nb = num; b->val = v; a->nxt[i] = b; return a; } } i = rand() % NBF; a->nxt[i] = inserenoeud(a->nxt[i], num, v); return a; }

      
      Il reste, comme on peut s en douter à

      • Afficher le contenu d un tel arbre.
      • Trouver si une valeur appartient à l arbre.
      • Trouver combien de fois une valeur apparaît dans l arbre.
      • Parcours en profondeur.
      • Parcours par génération, en largeur d abord.
      Nous avons vu une fonction qui cherche si une valeur apparaît dans cet arbre :

      uint yest (int n, arbre a) { uint nbf, i, k; if (! a) return (uint) 0; if (n == a->nb) return (uint) 1; for (i = 0; i < NBN ; i++) if (yest (n, a->fils[i])) return (uint) 1; return (uint) 0; }

      
      Il vous reste à écrire  :
      • Une fonction qui compte le nombre d'occurrences de la valeur dans l arbre.
      • Une fonction qui calcule le nombre de feuilles de l arbre (ce sont les noeuds qui n ont aucun descendant).
      • Une fonction qui calcule la profondeur de l arbre.
      • Une fonction qui mémorise et renvoie, sous la forme d un tableau, le chemin entre la racine et un sommet que l on a trouvé.
      • Une fonction qui mémorise et renvoie, sous la forme d un tableau, le chemin entre la racine et le somet de valeur n le plus proche.

   7. Graphes
      1. Première structure

         D abord les structures les plus simples possibles : la matrice.

         #include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> typedef short unsigned Shu; struct graphe { int nbs; Shu * tab; } ; typedef struct graphe graphe;

         Ensuite une fonction de création d un graphe

         graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? 1 : 0; } return g; }

         
         Il vous faut aussi une fonction d affichage :

         void voirgraf (graphe g) { Shu i, j, nb, num; nb = g.nbs; printf("Graphe\n"); for (i = 0, num = 0; i < nb; i++) { for (j = 0; j < nb; j++) printf("%c ", g.tab[num++]? 1 : ); printf("\n"); } }

         
         et le main par-dessus, il ne vous manque rien n est-ce pas ?

         Shu nbnonnuls (graphe g) { Shu i, j, nb, num, total; nb = g.nbs; total = 0; printf("Graphe\n"); for (i = 0, num = 0; i < nb; i++) { for (j = 0; j < nb; j++) total += g.tab[num++]; } return total; } int main () { graphe g; int nb; Shu to; nb = 10; g = creegraphe (nb); voirgraf(g); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); nb = 50; g = creegraphe (nb); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); nb = 500; g = creegraphe (nb); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); } /*taux 0.25 Graphe 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Graphe Pour 10 il y a 25 cases non vides soit 25.000000 % taux 0.0833333 Graphe Pour 50 il y a 212 cases non vides soit 8.480000 % taux 0.00925926 Graphe Pour 500 il y a 2333 cases non vides soit 0.933200 % */

         
         Il vous reste à :

         1. Écrire les structures correspondant aux types :
            1. Matrice compacte
            2. vecteur de triplets
            3. arbre n-aire
            4. arbre avec vecteur de successeurs (et nombre de successeurs)
            5. arbre avec liste successeurs
            6. brins.
         2. écrire la(les) fonction(s) de transition entre la structure matrice et la(les) structure(s) choisie(s).
         3. Écrire la fonction qui, avec cette structure, trouve un chemin entre deux sommets.
         Voici donc, telle que donnée en cours, une fonction d existance de chemin entre deux sommets.

         int chemin (Shu dep, Shu arr, graphe g, Shu flag[]) { Shu new; ligne l; if (dep == arr) return 1; if (flag[dep]) return 0; l = g.tab[dep]; flag[dep] = 1; while (l) { new = l->y; if (! flag[new]) if (chemin(new, arr, g, flag)) return 1; l = l->nxt; } return 0; } int existe_chemin (Shu dep, Shu arr, graphe g) { Shu * flag; flag = (Shu *) malloc (g.nbs * sizeof(Shu)); memset(flag, 0, (size_t) (g.nbs << 1)); return chemin (dep, arr, g, flag); }

         Vous pouvez maintenant transformer cette fonction pour trouver le chemin, puisqu on sait le trouver !
      2. Structure à brins

         Un brin est l extrémité d une arête, avec le signe moins au départ et le signe plus à l arrivée. L arête 5 qui va du sommet 3 au sommet 7 est donc composée de deux brins, le -5 lié au sommet 3 et le +5 lié au sommet 7.
         Il faut, pour concentrer davantage les données, mettre en place une structure avec trois vecteurs :

         • par sommet, le numéro d un des brins qui le joignent, ou 0 s il n y en a pas.
         • par brin, le numéro du sommet associé,
         • par brin, le numéro du "prochain brin" en tournant autour du sommet associé.
         Fabriquez cette structure, les fonctions pour transformer le graphe ci-dessus selon cette présentation, puis les fonctions usuelles de parcours de graphe.
   8. Pointeurs de fonctions

      Puisque nous pouvons travailler avec des pointeurs que ne travaillons-nous avec des pointeurs de fonction ?

      Voici d abord un exemple de définition :

      typedef void (* ptrfct) (); extern void fcta (); extern void fctb (); extern void g (void (*) ());

      
      Il est assez facile d utiliser ces fonction, c est fait dans le fichier menu.c ci-joint. Voyons un peu le détail :

      #include "ptr.h" void fcta () { printf(" a "); } void fctb () { printf(" b "); } void g (void (* fct) ()) { printf("g appelle :"); fct(); printf("\n"); } void fcttest () { g(fcta); g(fctb); } int menu () { int n; n = 0; while (!n) { printf("Choisissez entre la fonction a (tapez 1)\n"); printf("et la fonction b (tapez 2) :\n"); scanf("%d",&n); if (n==1 || n==2) break; } return n-1; } void faire () { int n; ptrfct tf [] = {fcta, fctb}; n = menu(); tf[n](); }

      
      Dans les deux cas vous voyez qu un pointeur de fonctions n est rien d autre qu un pointeur comme tous les autres, il contient simplement l adresse du début de la fonction.

   9. Pointeurs de fonctions, illustration

      Sous OpenGL, on doit utiliser des pointeurs de fonctions. Par exemple la fonction définie par :

      void Mouse(int button, int state, int x, int y){ switch(button){ case GLUT_LEFT_BUTTON: break; case GLUT_MIDDLE_BUTTON: break; case GLUT_RIGHT_BUTTON: break; } glutPostRedisplay(); }

      
      sera mémorisée dans le main comme fonction de gestion de souris. D un côté c est logique, de l autre cette affectation n est possible que parce que la fonction est correctement définie dans glut.

      int main(int argc, char **argv) { if (argc<2) { fprintf(stderr, "Usage : palette nom_de_fichier\n"); exit(0); } glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE); glutInitWindowSize(640,480); glutInitWindowPosition(0, 0); glutCreateWindow("VPUP8"); Init(argv[1]); glutCreateMenu(menuFunc); glutAddMenuEntry("Informations", 0); glutAddMenuEntry("Ouvrir", 3); glutAddMenuEntry("Sauver", 4); glutAddMenuEntry("Noir et Blanc", 6); glutAddMenuEntry("Quit", 5); glutAttachMenu(GLUT_LEFT_BUTTON); glutDisplayFunc(Display); glutReshapeFunc(Reshape); glutKeyboardFunc(Keyboard); glutMouseFunc(Mouse); glutMainLoop(); return 1; }

      
      Voici des fichiers utiles pour travailler :

      • main.c
        
      • ppm.c pour lire les fichiers image ppm.
      • ima.h
        
      • modif.c
        
      • le makefile, qui devrait fonctionner au Bocal.
        Vous trouverez également sur la page de M. Belhadj des exemples simples d utilisation de la SDL en particulier dans cette page les sources des exemples. Je vous conseille de travailler l exemple 4.
        Il vous faut également des images en ppm, en voici quelques unes.
      • une image des Andes
        
      • une image une peinture classique
        
      • une image du Kilimanjaro
        
      • une image de requin
        
      • une image d altitude
        
      • une image d altitude revisitée.
        
      Vous trouverez également sur la page de M. Belhadj des exemples simples d utilisation de la SDL en particulier dans cette page les sources des exemples. Je vous conseille de travailler l exemple 4.
      Une fois que tout ceci fonctionne, compilation et exécution comprises, il vous reste à écrire quelques fonctions comme :
      1. refaire la fonction gris pour passer à une image en niveaux de gris.
      2. modifier la fonction gris pour qu elle tienne davantage compte de la luminosité. On considère que l oeil est surtout sensible au vert (coefficient 1.5), puis au rouge (coefficient 1) et enfin au bleu (coefficient 0.5). Modifier en conséquence le calcul du gris à afficher.
      3. faire une fonction vert pour, à la fois, diminuer l importance des nuances rouge et bleues et ajouter de l intensité au vert.
      4. modifier la fonction vert pour faire un "négatif" de l image, c est-à-dire que chaque valeur prendra son complémentaire (sur 8 bits).
      5. modifier la fonction vert pour, cette fois, diminuer l écart entre les trois valeurs de chaque pixel.

      6. modifier les fonctions précédentes de façon à réduire la saturation (augmenter la composante la plus faible en direction de la seconde).
      7. Color Look-Up-Table
         Le principe de la LUT est de disposer d'une table où toutes les couleurs utilisées au moins une fois dans l'image ont un numéro d'entrée. Par exemple le premier pixel rencontré est bleu (0,20,200) il aura le numéro 0 dans la LUT. Ensuite on crée une seconde version de l'image dans laquelle le pixel n'est plus associé à sa couleur mais à son numéro d'entrée dans la C-LUT.

         On crée la C-LUT en s'arrangeant pour que toute couleur déjà rencontrée ne soit pas une nouvelle entrée.

         Il ne reste plus, alors, qu'à être capables d'afficher une image à partir de : sa C-LUT et son vecteur.

         Pour améliorer le procédé, on peut considérer que si une couleur proche d'une couleur déjà présente dans la C-LUT c'est celle-ci qui sera utilisée pour ce pixel.

         Dernière mise à jour : 11/1/2020, 13h