Jean-Jacques BOURDIN

Université Paris 8
Labo IA, Dépt. Informatique
2, rue de la Liberté
93526 Saint-Denis Cedex
FRANCE

Tél : (+33/0) 1 49 40 64 03
Fax : (+33/0) 1 49 40 64 10
E-mail : Jean-Jacques.BourdinNOSPAM@ai.univ-paris8.fr (enlever le NO Spam)


Programmation Impérative 2

Septembre 2017 -- Janvier 2018


  1. Présentation
  2. Programmation structurée
  3. Indirections et Fonctions
  4. Exemples : images
  5. Énoncé de partiel (exemple)
  6. Bientôt, les énoncés de projets
  1. Présentation

    • Objectifs

    • Prérequis

    • Pratique

  2. Programmation strcuturée

    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. Sa 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.
      puissances:    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. Compilation

      1. 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)
      2. Exemples d'utilisation des bibliothèques
        On trouvera de la documentation précise sur les bibliothèques standard sur les liens suivants :
        • 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 
            */
            
          • 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\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>   
            
            int main(int argc, char **argv) {
                    void catch(int);
                    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.

            Exemples de solutions :
            #include <stdarg.h> 
            #include <stdio.h>
            #include <stdlib.h>
            #include <assert.h>
            /* typedef unsigned long int ulint;*/
            /* nombre arguments 1 ou 4*/
            #define NBARG 4
            
            int fib (int argl, ...) {
              va_list liste;
              int * t;
              int i, val;
            
              if (argl < 0) {
            	t = (int *) malloc ( NBARG * sizeof(int));
            	assert(t);
            
            	va_start(liste,argl);
            	val=argl;
            	for(i=0 ; i < NBARG; i++, val=va_arg(liste, int)) {
            	  t[i]=val;
            	  //	printf("%d avec %d et %d\n",__LINE__, i, val);
            	}
            	
            	va_end(liste);
            	//  printf("les t %d %d %d %d\n",t[0],t[1],t[2],t[3]);
            	if (i > 2) {
            	  if (t[0] < t[1])
            		return fib(t[0],t[1]-1,t[2]+t[3],t[2]);
            	  return t[2];
            	}
              }
              return fib(-argl, -2, 1, 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);
              }
            }
            
            
            #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
            */
            
          • Utilisez setjmp pour mettre en place une procédure de sauvegarde de données avant la fin d'exécution d'un programme.
            Complétez-la en récupérant les erreurs d'interaction et en faisant "finir proprement" votre processus dans ces cas-là.

          • É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 ?

          Librairie stdlib.h

          #include
          #include
          
          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
          		./fil $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
          
          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 ?).
        • 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 memset\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.

          Exemple 2 On essaie maintenant de gérer le temps entre la forme liste et la forme vecteur, pour un simple calcul de somme. Que pensez-vous des résultats.
          /* Rapport de temps entre l'utilisation d'une liste et celle d'un vecteur
             jj 30/X/2014*/
          #include<stdio.h>
          #include<stdlib.h>
          #include<time.h>
          typedef unsigned long long int ullint;
          typedef unsigned int Uint;
          struct cell {
            ullint val;
            struct cell * nxt;
          } ;
          typedef struct cell cell;
          typedef struct cell * liste;
          struct vecteur {
            Uint nb;
            ullint * v;
          } ;
          typedef struct vecteur vecteur;
          
          vecteur construitv (Uint nb) {
            int i;
            ullint a, b;
            vecteur w;
            w.nb = nb;
            w.v = NULL;
            if (nb < 2)
          	return w;
            w.v = (ullint *) malloc (nb * sizeof(ullint));
            w.v[0]= (ullint) 1;
            w.v[1]= (ullint) 1;
            a = b = (ullint) 1;
            for(i=2; i < nb; i++) {
          	w.v[i] = (a + b) % 17;
          	b = a;
          	a = w.v[i];
            }
            return w;
          }
          liste construitl (vecteur v) {
            liste crt, deb;
            int i;
            
            deb = NULL;
            for (i = v.nb; i--;  deb = crt) {
          	crt = (liste) malloc (sizeof(cell));
          	crt->val = v.v[i];
          	crt->nxt = deb;
            }
            return crt;
          }
          void voirv (vecteur w) {
            int i;
            for (i = 0; i < w.nb; i++)
          	printf("%3llu ", w.v[i]);
            printf("\n");
          }
          void voirl (liste l) {
            if (!l) {
          	printf("\n");
          	return;
            }
            printf("%3llu ", l->val);
            voirl (l->nxt);
          }
          void affl (liste l) {
            while (l) {
          	printf("%3llu ", l->val);
          	l = l->nxt;
            }
            printf("\n");
          }
          ullint somv (vecteur v) {
            int i;
            ullint s;
            s = (ullint) 0;
            for (i = 0; i < v.nb; i++)
          	s += v.v[i];
            return s;
          }
          ullint soml (liste l) {
            ullint s;
            s = 0;
            while (l) {
          	s += l->val;
          	l = l->nxt;
            }
            return s;
          }
          int main (int argc, char * * argv) {
            int n, i;
            vecteur t;
            liste new;
            ullint s1, s2;
            clock_t cp;
            int tps_init, tps_crt, dtps;
          
            if (argc != 2) {
          	n = 100;
          	t = construitv (n);
          	voirv(t);
          	new = construitl(t);
          	voirl(new);
          	affl(new);
          	printf("Les deux sommes %llu et %llu \n", somv(t), soml(new));
          	return 0;
            }
            n = (Uint) atoi (argv[1]);
            t = construitv (n);
            new = construitl(t);
          
            printf("Temps pour %u\n", n);
            tps_init = (int) clock ();
            s1 = somv(t);
            tps_crt =  (int) clock ();
            dtps = tps_crt - tps_init;
            printf("par vecteur \t%d\n", dtps);
            tps_init = (int) clock ();
            s2 = soml(new);
            tps_crt =  (int) clock ();
            dtps = tps_crt - tps_init;
            printf("par liste \t%d\n", dtps);
          }
          /*
          Mu.local: gcc tempsliste.c
          Mu.local: a.out 100
          Temps pour 100
          par vecteur 	3
          par liste 	1
          Mu.local: a.out 500
          Temps pour 500
          par vecteur 	5
          par liste 	4
          Mu.local: a.out 1000
          Temps pour 1000
          par vecteur 	7
          par liste 	8
          Mu.local: a.out 10000
          Temps pour 10000
          par vecteur 	45
          par liste 	64
          */
          
          Exercices

          Mettre en place quatre méthodes permettant de calculer une valeur (n,m) du triangle de Pascal (ou du binôme de Newton). Les évaluer en temps.
          les méthodes :

          1. Récursive classique où une valeur est la somme des deux de la ligne au-dessus.
          2. Itérative, faire le calcul de chaque ligne, une à une.
          3. Itérative incrémentale, où on conserve dans un fichier les valeurs déjà obtenues et où on complète le fichier chaque fois que nécessaire.
          4. Par les factorielles.
          Voici un exemple de fonction :
          struct vect {
            int nb;
            int * v;
          } ;
          typedef struct vect vect_t;
          
          vect_t remplir (int l, int c) {
            vect_t v;
            int i, j, *ptr;
          
            v.nb = 0;
            if (l < c)
          	return v;
            v.nb = c + 1;
            v.v = (int *) malloc ((c + 1) * sizeof(int));
            assert(v.v);
            memset (v.v, 0, (c + 1) << 2);
            v.v[0] = 1;
            for (j = 0; j < l; j++) {
          	ptr = v.v + c + 1;
          	while (ptr > v.v) {
          	  *ptr += *(ptr - 1);
          	  ptr--;
          	}
            }
            return v;
          }
          
          Comparer les temps obtenus.




  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. 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'occrurences 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.
    6. 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 à écrire la fonction qui répond à la question de savoir s'il y a un chemin entre un sommet départ un sommet arrivée.
        Puis de transformer cette structure pour faire un graphe à vecteur de successeurs
        puis liste de successeurs,
        enfin, par graphe à brins.
         

      2. 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.

      3. 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 :

        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.

        Dernière mise à jour : 14/11/17, 17h