Programmation Imprative
Imperative Programming

A table is only a vector of vectors.

exemple :
Example
Nous allons travailler avec des tableaux d'altitude. Sur une grande carte, carre, nous donnons l'altitude de chacune des cases, c'est--dire l'altitude moyenne pour toute la surface qu'elle reprsente sur le terrain.
Pour gnrer le tableau, il faut utiliser cette fonction en donnant comme paramtres, le tableau, le nombre de colonnes et le nombre de lignes :

/* exo sur les altitudes JJ'2012 */ typedef float table [100] [100]; /* desormais table est un synonyme de float [100][100]*/ void remplirt (table t, int sx, int sy) { int x, y, sxy; float v, eps, add, pas; pas = 0.5; v = pas; add = 5.0; sxy = sx * sx + sy * sy; eps = 1.0 / (float) (sxy); for (x = 0; x < sx; x += 1) { for (y = 0; y < x; y += 1) { t[x][y] = (float) (x * x - y * y + add) * eps; } for (y = x; y < sy; y += 1) { t[x][y] = (float) ( y * y - x * x + add) * eps; } add += v; if (add > 10.0) v = - pas; if (add < 0.1) v = pas; } }

Nous pouvons donc maintenant utiliser une fonction pour afficher ce tableau et la fonction main pour s'en servir.
Note : le dnivel entre deux points et la diffrence d'altitude entre ces deux points.
Un dnivel positif est un dnivel dont la valeur est positive.
Puis

1. Trouver le point culminant (la valeur la plus grande) d'une certaine ligne horizontale.
2. Trouver le point culminant d'une certaine colonne.
3. Trouver le point culminant de toute la surface.
4. Trouver le second point culminant de toute la surface.
5. Calculer le dnivel entre deux points donns.
6. Calculer la somme des dnivels entre deux points d'une ligne. Il faut donc que le numro de la ligne soit fourni en argument.
7. Calculer la somme des dnivels entre deux points d'une colonne. Il faut donc que le numro de la colonne soit fourni en argument.
8. Calculer la somme des dnivels positifs entre deux points le long d'une ligne.
9. Calculer la somme des dnivels ngatifs entre deux points le long d'une colonne.

Nous allons maintenant crer plusieurs fichiers et les compiler sparment.
Le premier fichier contient les prototypes des fonctions. Il s'agit du fichier "fac.h":

/* les prototypes des fonctions */ int fac (int); int fac_acc (int, int); void affiche (int, int);

Ensuite nous avons un fichier qui s'occupe des entres sorties, le fichier "io.c":

#include "fac.h" void affiche (int a, int b) { printf("Vous avez donne \t%d\n",a); printf("Sa factorielle est \t%d\n",b); }

Le fichier suivant contient la fonction du calcul de la factorielle, c'est le fichier "fac.c":

#include "fac.h" /* le calcul de la fonction factorielle */ int fac (int n) { return fac_acc (n, 1); } int fac_acc (int n, int acc) { if (n < 2) { return acc; } else { return fac_acc (n-1, n*acc); } }

Enfin, le fichier "main.c" contient le reste du code (ici la fonction main):

#include "fac.h" main () { int n, f; n = 5; f = fact(n); affiche(n,f); n = 6; f = fact(n); affiche(n,f); }

Il reste les compiler sparment. Ceci se gnralise grce au fichier "Makefile":

# Compilation generique par Bourdin CC=gcc fac: io.o main.o fac.o fac.h $(CC) io.o main.o fac.o -o fac main.o: main.c fac.h io.o: io.c fac.h fac.o: fac.c fac.h clean: @rm -f *.o @rm -f core @rm -f *~

Attention, il faut remettre des "tabulations" la main, sous emacs.

Dans ce fichier on trouve trois sortes de lignes : les affectations de variables (ici "CC=gcc") qui permettent d'utiliser des variables par la suite, les dclarations de dpendance (comme "io.o: io.o fac.h", qui annonce que la compilation de io.o dpend de l'existance des deux autres fichiers) et les ordres (comme " @rm -f *.o" ou
" $(CC) io.o main.o fac.o -o fac") qui sont des lignes commenant par une tabulation.
Prenons la ligne 5:
fac est nomm "cible".
io.o main.o fac.o fac.h sont les dpendances.

Sous shell, il ne reste plus qu' demander la compilation

alpha5: make fac predecessor cycle (io.o) gcc -O -c io.c predecessor cycle (main.o) gcc -O -c main.c predecessor cycle (fac.o) gcc -O -c fac.c gcc io.o main.o fac.o -o fac ld: ERROR 33: Unresolved text symbol "fact" -- 1st referenced by main.o. Use linker option -v to see when and which objects, archives and dsos are loaded. ld: INFO 152: Output file removed because of error. *** Error code 1 (bu21)

Aprs correction (la fonction est nomme "fac" et pas "fact"!):

alpha5: make fac predecessor cycle (io.o) predecessor cycle (main.o) gcc -O -c main.c predecessor cycle (fac.o) gcc io.o main.o fac.o -o fac alpha5: fac Vous avez donne 5 Sa factorielle est 120 Vous avez donne 6 Sa factorielle est 720 alpha5:

On peut amliorer ce fichier de make, en utilisant des variables et des rgles :

# Meilleure compilation par Bourdin # # Attention, les tabulations doivent tre refaites vous-mmes, la # main # OBJ=io.o main.o fac.o CC=gcc fac: $(OBJ) fac.h $(CC) $(OBJ) -o fac %.o : %.c $(CC) -c $< clean: @rm -f *.o @rm -f core @rm -f *~

Vous remarquerez que les fichiers qui finissent par ".o" sont obtenus par compilation avec l'option "-c" c'est l'objet des lignes 14 et 15.

Quelques variables par dfaut

• $@ dsigne le nom de la cible
• $< le nom de la premire dpendance
• $^ la liste des dpendances
• $? la liste des dpendances plus rcentes que la cible
• $* le nom du fichier sans suffixe

• le fichier Makefile
• le fichier de dclarations de type
• le fichier main.c
• le fichier fonctions.c
• le fichier newton.c
• le fichier autres.c

• Reprendre un exemple prcdent, par exemple les chemins et dnivels, et le sparer en plusieurs parties.
• Mettre toutes les parties dans un rpertoire correspondant.
• Fabriquer le fichier makefile correpondant.
• Faire tourner le programme.

    III.A) Principles
Principes

A variable is a set of three things: a name, a type and a location.
It is in this location that one can find the value of the variable. The address is known by the operator &.

Une variable est un triplet < nom, type, emplacement>. C'est cet emplacement que, selon le type, on trouve la valeur. On peut connatre l'emplacement, l'adresse, de la variable "a" en utilisant l'oprateur & :

void voirou1 () { int i, j; printf("i est en %u, j est en %u\n", (int)&i, (int)&j); }

One may also set this adress into a new variable, a "pointer". The content of such a variable is available, and the content of the pointed variable can be found with the unary operator *.
On peut aussi mettre cette adresse dans une variable spciale qui contient des adresses, un pointeur. On peut aussi savoir ce qu'il y a une certaine adresse avec l'oprateur unaire *.

/* une petite question sur les allocations */ #include <stdio.h> void nrut (int * px, int * py) { * px = * px + * py; * py = * px - * py; * px = * px - * py; } void lookatit (int n) { int i, j, k, l; int * pi, * pj; i = 2; j = 3; k = 4; l = 5; pi = & i; pj = & j; printf("adresses de i %d et j %d\n",pi, pj); printf("adresses de i %p et j %p\n",pi, pj); nrut(pi,pj); printf("valeurs de i %d et j %d\n",i, j); pi = & k; pj = & l; printf("adresses contenues dans pi %d et pj %d\n",pi, pj); printf("adresses contenues dans pi %p et pj %p\n",pi, pj); } int main () { lookatit(5); } /* adresses de i -317351240 et j -317351244 adresses de i 0x7ffeed159ab8 et j 0x7ffeed159ab4 valeurs de i 3 et j 2 adresses contenues dans pi -317351248 et pj -317351252 adresses contenues dans pi 0x7ffeed159ab0 et pj 0x7ffeed159aac */

void voirou () { int *pi, *pj; int i, j; printf("i est en %d, j est en %u\n",(int) &i,(int) &j); pi = & i; pj = & j; i = 7; j = 9; printf("En %u il y a %d\n", (int) pi, * pi); printf("En %u il y a %d\n", (int) &j, j); }

On peut se servir des adresses pour modifier le contenu d'une variable extrieure.

void iv (int * pa, int * pb) { * pa = * pa + * pb; * pb = * pa - * pb; * pa = * pa - * pb; } int main () { int a, v; a = 5; v = 8; voirou1(); voirou(); printf("a = %d\t v = %d\n",a,v); iv (&a, &v); printf("a = %d\t v = %d\n",a,v); } /* dhcp13.ai.univ-paris8.fr: a.out i est en 1344117452, j est en 1344117448 i est en 1344117436, j est en 1344117432 En 1344117436 il y a 7 En 1344117432 il y a 9 a = 5 v = 8 a = 8 v = 5 */

Amusant, non ?
Voici un autre exemple, que vous reconnatrez aisment :

/* Fait par JJ B en 2010 */ typedef int * pint; void fct (int nb, int rg, pint a, pint b) { if (nb > rg) { *a = *a + *b; *b = *a - *b; fct (nb, rg + 1, a, b); } } main () { int i, n, a, b; n = 10; for (i = 0; i <= n; i++) { a = 1; b = 1; fct (i, 0, &a, &b); printf("%d => %d\n", i, b); } }

    III.B) Arrays and pointers
Vecteurs et Tableaux

1. Retour
   What is an array? Nothing else than a pointer.
   Qu'est-ce qu'un tableau ? Un pointeur ! On peut parcourir un tableau, case case, par un pointeur :

   /* Fait par JJ B en 2014 */ #include <stdio.h> #include <stdlib.h> struct vecteur { int nbe; float tab [100]; } ; typedef struct vecteur vecteur_t; typedef float * pfloat; float somv (vecteur_t v) { int i; float som, *p; p = v.tab; som = 0; for (i = 0; i < v.nbe; i++) { som = som + *p; p ++; } return som; }

   On suppose que le vecteur a t dfini par ailleurs. Voici une illustration du fonctionnement de cette fonction :

   Il vous reste reprendre quelques exercices faits avec des vecteurs, mais cette fois, en utilisant les pointeurs.

   Exemple avec les altitudes

   #include <stdio.h> typedef float table [100] [100]; void affichet (table t, int sx, int sy) { int x, y; printf("Tableau \n"); for (x = 0; x < sx; x += 1) { for (y = 0; y < sy; y += 1) { printf ("%3.3f ", t[x][y]); } printf("\n"); } } void afficheptr (table t, int sx, int sy) { int x, y; float * ptr; printf("Tableau pointeurs\n"); for (x = 0; x < sx; x += 1) { ptr = (float *) &(t[x]); /* mais pourquoi ? */ for (y = 0; y < sy; y += 1) { printf ("%3.3f ", *ptr++); } printf("\n"); } } void afficheadr (table t, int sx, int sy) { int x, y; float * ptr; printf("Adresses Tableau \n"); for (x = 0; x < sx; x += 1) { ptr = (float *) &(t[x]); for (y = 0; y < sy; y += 1) { printf ("%d ", (int) ptr++ % 10000); } printf("\n"); } } void remplirt (table t, int sx, int sy) { int x, y, sxy; float v, eps, add; v = 0.1; add = 0.0; sxy = sx * sx + sy * sy; eps = 1.0 / (float) (sxy); for (x = 0; x < sx; x += 1) { for (y = 0; y < x; y += 1) { t[x][y] = (float) (x * x - y * y + add) * eps; } for (y = x; y < sy; y += 1) { t[x][y] = (float) ( y * y - x * x + add) * eps; } add += v; if (add > 2.0) v = - 0.1; if (add < 0.1) v = 0.1; } } int main () { table t; int sizex, sizey; sizex = 10; sizey = 10; remplirt(t, sizex, sizey); affichet(t, sizex, sizey); afficheptr(t, sizex, sizey); afficheadr(t, sizex, sizey); }

   Qui donne l'excution :

   0.000 0.005 0.020 0.045 0.080 0.125 0.180 0.245 0.320 0.405 0.005 0.001 0.015 0.041 0.075 0.120 0.175 0.240 0.315 0.400 0.021 0.016 0.001 0.026 0.061 0.106 0.161 0.226 0.301 0.386 0.047 0.041 0.026 0.002 0.036 0.081 0.136 0.201 0.276 0.361 0.082 0.077 0.062 0.037 0.002 0.047 0.102 0.167 0.242 0.327 0.127 0.122 0.107 0.082 0.047 0.002 0.057 0.122 0.197 0.282 0.183 0.178 0.163 0.138 0.103 0.058 0.003 0.068 0.143 0.228 0.249 0.243 0.228 0.204 0.169 0.124 0.068 0.004 0.078 0.163 0.324 0.319 0.304 0.279 0.244 0.199 0.144 0.079 0.004 0.089 0.410 0.405 0.389 0.364 0.329 0.285 0.229 0.164 0.089 0.005 Tableau pointeurs 0.000 0.005 0.020 0.045 0.080 0.125 0.180 0.245 0.320 0.405 0.005 0.001 0.015 0.041 0.075 0.120 0.175 0.240 0.315 0.400 0.021 0.016 0.001 0.026 0.061 0.106 0.161 0.226 0.301 0.386 0.047 0.041 0.026 0.002 0.036 0.081 0.136 0.201 0.276 0.361 0.082 0.077 0.062 0.037 0.002 0.047 0.102 0.167 0.242 0.327 0.127 0.122 0.107 0.082 0.047 0.002 0.057 0.122 0.197 0.282 0.183 0.178 0.163 0.138 0.103 0.058 0.003 0.068 0.143 0.228 0.249 0.243 0.228 0.204 0.169 0.124 0.068 0.004 0.078 0.163 0.324 0.319 0.304 0.279 0.244 0.199 0.144 0.079 0.004 0.089 0.410 0.405 0.389 0.364 0.329 0.285 0.229 0.164 0.089 0.005 Adresses Tableau -7648 -7644 -7640 -7636 -7632 -7628 -7624 -7620 -7616 -7612 -7248 -7244 -7240 -7236 -7232 -7228 -7224 -7220 -7216 -7212 -6848 -6844 -6840 -6836 -6832 -6828 -6824 -6820 -6816 -6812 -6448 -6444 -6440 -6436 -6432 -6428 -6424 -6420 -6416 -6412 -6048 -6044 -6040 -6036 -6032 -6028 -6024 -6020 -6016 -6012 -5648 -5644 -5640 -5636 -5632 -5628 -5624 -5620 -5616 -5612 -5248 -5244 -5240 -5236 -5232 -5228 -5224 -5220 -5216 -5212 -4848 -4844 -4840 -4836 -4832 -4828 -4824 -4820 -4816 -4812 -4448 -4444 -4440 -4436 -4432 -4428 -4424 -4420 -4416 -4412 -4048 -4044 -4040 -4036 -4032 -4028 -4024 -4020 -4016 -4012

   Le "pourquoi" vient simplement du fait que, lorsque le tableau est cr, il contient 100x100 entiers. Donc, pour passer la ligne suivante, il faudrait avancer de 400 octets...

    

    

    

    

    

2. Dynamic arrays
   Tableaux dynamiques
   We oversize our arrays, is it such a good idea?
   Jusqu' prsent, vous avez un problme avec la taille des tableaux et vecteurs, ce n'est plus la peine grce aux tableaux dynamiques.

   typedef int * pint; typedef int table [100]; void fcttab (int nb, table t) { int i; pint p1, p2, p3; p3 = t; p2 = t + 1; p1 = t + 2; *p3 = 1; *p2 = 1; for (i = 2; i <= nb; i+=1) { *p1 = *p2 + *p3; p3 = p2; p2 = p1; p1+= 1; } } void seetab (table t, int nb) { pint p; p = t; while (nb > 0) { printf("%d\t", *p); p++; nb--; } printf("\n"); } main () { table tt; pint pt; int n, nbele; n = 18; nbele = n + 1; /* ici, la methode classique ou tt est un tableau */ fcttab(n, tt); seetab(tt, nbele); n = 10; nbele = n + 1; /* la, la methode dynamique de "creation" d'un tableau */ pt = (pint) malloc ((size_t) (nbele * sizeof(int))); fcttab(n, pt); seetab(pt, nbele); free(pt); /* c'est plus joli, plus souple, plus dynamique */ }

   
   
3. Exercices

   Refaire toutes les fonctions dj vues sur les tableaux mais avec des tableaux dynamiques.

   Voici un exemple de corrig, l'ensemble du programme qui cre un tableau d'altitudes (la topographie d'un terrain) et l'affiche (on trouve le mme, " l'ancienne" un peu plus haut sur cette page).

   Let's see some new types to work on the altitude field.
   Crons d'abord les types qui vont nous servir :

   typedef unsigned int uint; typedef float * tabalt ; struct tableau { tabalt t; unsigned int nbc; unsigned int nbl; } ; typedef struct tableau tableau;

   
   This type includes the length in columns and lines of the array and the adress of the values.
   Comme vous le voyez, la structure tableau contient maintenant aussi ses dimensions. On peut maintenant crer un tel tableau :

   tableau creetableau (uint nbc, uint nbl) { tableau t; t.nbc = nbc; t.nbl = nbl; t.t = (tabalt) malloc ((size_t) (nbc * nbl * sizeof(float))); return t; }

   
   Once it's created, it is easy to fill the array with values.
   Une fois qu'il sera cr, on peut mettre une valeur dans une des cases, ou rcuprer le contenu de l'une des cases :

   void puttab (tableau t, uint i, uint j, float amettre) { if (i < t.nbc && j < t.nbl) { *(t.t + i + j * t.nbc) = amettre; } } float valtab (tableau t, uint i, uint j) { if (i < t.nbc && j < t.nbl) { return *(t.t + i + j * t.nbc); } return -1.0; }

   
   Il ne reste plus qu' remplir systmatiquement le tableau avec les mmes valeurs que dans l'exemple donn prcdemment :

   void remplirtab (tableau t) { uint i, j; float val; for (i = 0; i < t.nbc; i++) for (j = 0; j < t.nbl; j++) { val = (float) (30 * i + 20 * i * j + 15 * j); while (val > 2000.0) val = val - 2000.0; if (val > 1000.0) val = 2000.0 - val; puttab(t, i, j, val); } }

   
   Puis tre en mesure d'afficher toutes les cases du tableau :

   void voirtab (tableau t) { uint i, j; for (j = 0; j < t.nbl; j++) { printf ("%6d", j); } printf("\n"); for (i = 0; i < t.nbc; i++) { printf ("%4d |", i); for (j = 0; j < t.nbl; j++) { printf ("%6.2f ", valtab(t, i, j)); } printf("\n"); } }

   
   Une fonction main pour faire fonctionner tout cela et le tour est jou.

   int main () { uint sx, sy; tableau t; sx = 10; sy = 10; t = creetableau (sx, sy); remplirtab (t); voirtab(t); }

   Voici un jeu d'essais :

   0 1 2 3 4 5 6 7 8 9 0 | 0.00 15.00 30.00 45.00 60.00 75.00 90.00 105.00 120.00 135.00 1 | 30.00 65.00 100.00 135.00 170.00 205.00 240.00 275.00 310.00 345.00 2 | 60.00 115.00 170.00 225.00 280.00 335.00 390.00 445.00 500.00 555.00 3 | 90.00 165.00 240.00 315.00 390.00 465.00 540.00 615.00 690.00 765.00 4 |120.00 215.00 310.00 405.00 500.00 595.00 690.00 785.00 880.00 975.00 5 |150.00 265.00 380.00 495.00 610.00 725.00 840.00 955.00 930.00 815.00 6 |180.00 315.00 450.00 585.00 720.00 855.00 990.00 875.00 740.00 605.00 7 |210.00 365.00 520.00 675.00 830.00 985.00 860.00 705.00 550.00 395.00 8 |240.00 415.00 590.00 765.00 940.00 885.00 710.00 535.00 360.00 185.00 9 |270.00 465.00 660.00 855.00 950.00 755.00 560.00 365.00 170.00 25.00

   
   Avec ce tableau, il faut faire quelques fonctions.
   1. pour deux points voisins, (i1,j1) et (i2,j2) donner le dnivel entre les deux.
   2. pour deux points de la mme horizontale, donner la somme des dnivels positifs entre eux.
   3. pour deux points de la mme verticale, donner la somme des dnivels positifs entre eux.
   4. pour deux points de la mme verticale, donner la somme des dnivels positifs et la somme des dnivels ngatifs entre eux. (utilisation d'une structure ad hoc).
   5. pour deux points donns, calculer les dnivels positifs et ngatifs entre eux, selon la droite qui les joint.

    III.D) Listes Chanes

1. Lisp like lists
   Liste Lisp
   

   Voici une fonction qui construit une liste de n nombres entiers. Elle est en Lisp, il faut donc la transcrire.

   (define (creerl n) (if (< n 1) '(0) (cons n (creerl (- n 1)))))

   
   

2. Type definition
   Dfinition des types
   

   struct cell { int nb; struct cell * nxt; } ; typedef struct cell cell_t; typedef struct cell * liste;

   O on voit que la liste est en fait uniquement l'adresse d'une structure qui contient une valeur et une liste.
3. fonctions simples
   

   int estvide (liste l) { if (l == (liste) 0) { return 1; } return 0; } int estnonvide (liste l) { if (l == (liste) 0) { return 0; } return 1; }

4. La somme des lments
   

   int soml (liste l) { if (estvide(l)) { return 0; } return (*l).nb + soml((*l).nxt); }

5. Le nombre d'lments
   

   int howmany (liste l) { if (estvide(l)) { return 0; } return 1 + howmany ((*l).nxt); }

6. La construction
   

   liste cons (int nb, liste l) { liste new; new = (liste) malloc (sizeof(cell_t)); assert(new); (*new).nb = nb; (*new).nxt = l; return new; } liste creer (int nb) { liste debut; int i, j, k, t; j = 13; k = 21; debut = (liste) 0; for (i = 0; i < nb; i++) { debut = cons (j, debut); t = (j + k) % 33; k = j; j = t; } return debut; }

7. Trois fonctions d'affichage
   

   void affl (liste l) { if (estvide (l)) { printf("\n"); } else { printf("%3d ", (*l).nb); affl ((*l).nxt); } }

   void affll (liste l) { if (estvide (l)) { printf("\n"); } else { printf("%3d ", l->nb); affll (l->nxt); } } void affw (liste l) { while (estnonvide (l)) { printf("%3d ", l->nb); l = l->nxt; } printf("\n"); }

   Des enttes inclure :

   #include<stdio.h> #include<stdlib.h> #include<assert.h>

   La fonction main :

   int main () { liste l; int nb, s; nb = 10; l = creer(nb); affw(l); s = soml(l); printf("Total : %d\n", s); s = howmany(l); printf("Il y a %d elements\n", s); }

8. Liste d'exercices faire.
   
   1. Trouver le plus grand lment.
   2. Afficher les lments dans l'ordre inverse.
   3. Mettre les lments de la liste en ordre inverse. (Attention, il n'y a pas besoin de malloc pour faire cette fonction).
   4. Fabriquer une liste avec les n premiers entiers (dans l'ordre dcroissant).
   5. Faire la somme des lments d'une liste.
   6. Faire la somme des lments plus petits que 50 d'une liste.
   7. Faire la moyenne des lments d'une liste.
   8. Enlever le premier lment d'une liste.
   9. Enlever le dernier lment d'une liste.
   10. Fonction de concatnation de deux listes.
   11. Dans une liste range, insrer une cellule sa place.
   12. Faire le tri d'une liste, par insertion.
   13. Trouver le mdian des lments d'une liste.
   14. Fabriquer une liste des carrs de tous les lments d'une autre liste passe en paramtre.
   Exemple de solution

   int plusgrandliste (liste l, int candidat) { if (l) { if (l->nb > candidat) return plusgrandliste (l->next, l->nb); return plusgrandliste (l->next, candidat); } return candidat; /* il n'y a plus d'autre possible*/ } int plusgrandl (liste l) { if (l) return plusgrandliste (l->next, l->nb); return INT_MIN; /* impose d'avoir inclus limits.h */ }

    

    

    

    

    

9. Quicksort sur une liste

   Pour faire Quicksort, nous avons besoin de faire une fonction qui trie les toutes petites listes.

   liste tril2(liste l) { liste crt ; if (!l) return l; if (! l->nxt) return l; crt = l->nxt; if (l->nb < crt->nb) return l; crt->nxt = l; l->nxt = NULL; return crt; }

   Il ne reste plus qu' faire quicksort :
   1. sparer la liste en trois parties, le pivot, les petits et les grands,
   2. utiliser qs pour ranger les petits,
   3. utiliser qs pour ranger les grands,
   4. remettre bout bout les trois ensembles.

   liste qs (liste l) { liste petits, grands, pivot, crt; if (!l) return l; if (! l->nxt) return l; if (! l->nxt->nxt) return tril2(l); pivot = l; l = l->nxt; pivot->nxt = NULL; petits = NULL; grands = NULL; while (l) { crt = l->nxt; if (l->nb < pivot->nb) { /* il est petit */ l->nxt = petits; petits = l; } else { /* il est grand */ l->nxt = grands; grands = l; } l = crt; } grands = qs(grands); petits = qs(petits); pivot->nxt = grands; if (! petits) return pivot; crt = petits; while (crt->nxt) crt = crt->nxt; crt->nxt = pivot; return petits; }

10. Inversion d'une liste.
11. Inversion par la mthode PG/DG.

    (define (re l) (ifn (cdr l) l (cons (car (re (cdr l))) (re (cons (car l) (re (cdr (re (cdr l)))))))))

    
    

Quelques solutions vues en cours

• Moyenne des lments de la liste
  C'est pourtant simple : d'une part on compte le nombre d'lments d'autre part on fait la somme des lments. Ensuite on divise.
  Attention, il faut traiter, au dbut, le cas o la liste est vide.
  

  int moyl (liste l) { int val, nb; liste crt; if (! l) return 0; val = 0; nb = 0; crt = l; while (crt) { val += car(crt); crt = cdr(crt); nb++; } return val/nb; }

• Cration d'une liste de nombres dcroissants
  

   

   

   

   

   

      III.D) Arbres

  "La beaut des arbres est de crotre." (qui ?)

  Nous prsentons une structure pour des arbres binaires. We start by defining some structures.

  /* Arbres binaires tout simplement */ #include <stdio.h> #include <stdlib.h> #include <time.h> struct noeud { int num; float val; struct noeud * fg; struct noeud * fd; } ; typedef struct noeud noeud; typedef struct noeud * arbre;

  We'll add a new set of values in the tree.

  arbre ajout (arbre a, int v, float x) { arbre new; int rande; if (! a) { new = (arbre) malloc (sizeof (noeud)); new->num = v; new->val = x; new->fg = (arbre) 0; new->fd = (arbre) 0; return new; } rande = rand (); /* printf(" insere %d en %d avec %2d\n", v, a->num, rande %10); */ if (rande % 2) { /* on le met gauche*/ if (! (a->fg)) { /* s'il ny a pas de fils gauche */ a->fg = (arbre) malloc (sizeof (noeud)); a->fg->num = v; a->fg->val = x; a->fg->fg = (arbre) 0; a->fg->fd = (arbre) 0; return a; } a->fg = ajout(a->fg, v, x); return a; } /* on le met donc a droite*/ if (! (a->fd)) { /* s'il ny a pas de fils droit */ a->fd = (arbre) malloc (sizeof (noeud)); a->fd->num = v; a->fd->val = x; a->fd->fg = (arbre) 0; a->fd->fd = (arbre) 0; return a; } a->fd = ajout(a->fd, v, x); return a; } /* To create the tree, you add, one after the other, the values in the tree.*/ arbre creation (int n) { arbre a; float x, y; x = 1.5; y = 0.21; a = (arbre) 0; srand(time(NULL)); while (n--) { a = ajout (a, n, x); printf("\n"); x += y; y += 0.06; if (x > 3.0 || x < -2.0) { y = - y; } } return a; }

  It is also possible to show the tree created:

  void afficharbre (arbre a) { if (a) { afficharbre (a->fg); printf("%d %3.2f ", a->num, a->val); afficharbre (a->fd); } }

  int appartient (int nu, arbre a) { if (! a) return 0; if (a->num == nu) return 1; if (appartient (nu, a->fd)) return 1; return appartient (nu, a->fg); }

  Vous pouvez aussi :

  • Trouver le plus grand val dans un arbre.
  • Trouver le second plus petit val dans un arbre.
  • Compter le nombre de noeuds de l'arbre.
  • Compter le nombre de noeuds dont le champ val est suprieur une valeur donne.
  • Compter le nombre de feuilles de l'arbre (une feuille est un noeud qui n'a aucun successeur).
  • Renvoyer la profondeur d'un noeud de l'arbre. La profondeur est le nombre de gnrations entre la racine de l'arbre et la cellule cherche. La racine est la profondeur 0, ses successeurs directs la profondeur 1, etc.
  • Renvoyer la profondeur maximale de l'arbre.

  int main () { int n; arbre a, b; float x; /* srand(time(NULL)); */ n = 20; a = creation (n); printf("\n Vois \n"); voisarbre (a,0); x = 0.72; printf("%f dedans %s\n", x, appartient(a,x) ? "Oui" : "Non"); }

  Oh, il ne le trouve pas :

  0.720000 dedans Non

  Il faut donc faire une approximation :

  int fappartient (arbre a, float x) { if (! a) return 0; if (fabs(a->val - x) < 0.0001) return 1; return fappartient(a->fg, x) || fappartient (a->fd, x); }

  int main () { int n; arbre a, b; float x; /* srand(time(NULL)); */ n = 20; a = creation (n); printf("\n Vois \n"); voisarbre (a,0); x = 0.72; printf("%f dedans %s\n", x, appartient(a,x) ? "Oui" : "Non"); printf("%f dedans %s\n", x, fappartient(a,x) ? "OUI" : "NON"); }

  Cette fois :
  

  0.720000 dedans Non 0.720000 dedans OUI

  Arbres binaires de recherche
  Binary search tree
  The structure is the same but two conditions are respected:
  for a node with value n, every value in its left part are lower than n
  and every value in its right part are greater or equal than n.
  Here after is a function that build a BST.
  C'est la mme structure mais elle respecte deux conditions : pour tout sommet de valeur n, tous ses descendants gauche ont une valeur infrieure n et tous ses descendants droite one une valeur suprieure ou gale n.
  Hereafter is the adequate construct function:

  arbre ajout (arbre a, int v, float x) { arbre new; if (! a) { new = (arbre) malloc (sizeof (noeud)); new->num = v; new->val = x; new->fg = (arbre) 0; new->fd = (arbre) 0; return new; } if (x < a->val) { /* on le met gauche*/ if (! (a->fg)) { /* s'il ny a pas de fils gauche */ a->fg = (arbre) malloc (sizeof (noeud)); a->fg->num = v; a->fg->val = x; a->fg->fg = (arbre) 0; a->fg->fd = (arbre) 0; return a; } a->fg = ajout(a->fg, v, x); return a; } /* on le met donc a droite*/ if (! (a->fd)) { /* s'il ny a pas de fils droit */ a->fd = (arbre) malloc (sizeof (noeud)); a->fd->num = v; a->fd->val = x; a->fd->fg = (arbre) 0; a->fd->fd = (arbre) 0; return a; } a->fd = ajout(a->fd, v, x); return a; } arbre creation (int n) { arbre a; float x, y; x = 1.5; y = 0.21; a = (arbre) 0; while (n--) { a = ajout (a, n, x); x += y; y += 0.06; if (x > 3.0 || x < -2.0) { y = - y; } } return a; }

  Il vous reste faire la nouvelle fonction d'appartenance d'une valeur ( virgule) dans cet arbre.
  

  int appartient (arbre a, float x) { if (! a) return 0; if (a->val == x) return 1; if (a->val > x) return appartient (a->sg, x); return appartient (a->sd, x); } int appartientf (arbre a, float x) { if (! a) return 0; if (fabsf(a->val - x) < 0.0001) return 1; if (a->val > x) return appartientf (a->sg, x); return appartientf (a->sd, x); }

  Puis une fonction qui compte le nombre d'occurences d'une valeur virgule dans cet arbre.
  Puis une fonction qui affiche toutes les valeurs (val) dans l'ordre croissant.
  Puis une fonction qui affiche toutes les valeurs (val) dans l'ordre dcroissant.
  Puis une fonction qui renvoie le nombre de sommets de l'arbre.
  

   

   

   

   

   

   

   

   

   

   

  ---

  Ch IV) What else?

      IV.A) Compiler
  Rgles de Compilation

  • The four steps for compiling
    Les quatre tapes de la compilation
    • The preprocessor. La prcompilation (on obtient le rsultat en utilisant l'option -E)
    • Assembly code. le code assembleur (option -S)
    • Building of the object code. le code objet (option -c)
    • The linker. l'dition de liens (option -o et le nom de l'excutable).
    
    
  • The preprocessor

    It obeys to orders starting with #. Examples:
    Les directives qui commencent par # et elles seules sont vallues par le prcompilateur. Il les excute. Parmi ces directives nous verrons essentiellement les :

    • #define
    • #include
    • #if then else
    Pseudo-constants and pseudo-functions
    pseudo-constantes et pseudo-fonctions
    Il s'agit de remplacer dans le texte, dans le corps du programme, toute occurence du mot dfini par sa dfinition. Exemple :
    #define MAXI 100
    every occurence of MAXI will be replaced by 100.

    #include <stdio.h> #define GT(a, b) a < b ? b : a #define CARRE(a) a * a main () { int i, s; i = 10; s = 12; printf("Le MAX de %3d et %3D est %d\n",i,s,GT(i,s)); printf("Le MAX de %3d et %3D est %d\n",i,s, GT(i++,s++)); printf("Le MAX de %3d et %3D est %d\n",i,s, GT(i+1,s+1)); printf("Le carre de %3d est %d\n",i + 1,CARRE(i + 1)); printf("Le carre de %3d est %d\n",i,CARRE(i++)); printf("Le carre de %3d est %d\n",i,CARRE(--i)); }

    
    After preprocessoring, this part of the program becomes:
    aprs compilation partielle, devient

    main () { int i, s; i = 10; s = 12; printf("Le MAX de %3d et %3D est %d\n",i,s,i < s ? s : i); printf("Le MAX de %3d et %3D est %d\n",i,s, i++ < s++ ? s++ : i++); printf("Le MAX de %3d et %3D est %d\n",i,s, i+1 < s+1 ? s+1 : i+1); printf("Le carre de %3d est %d\n",i + 1,i + 1 * i + 1); printf("Le carre de %3d est %d\n",i,i++ * i++); printf("Le carre de %3d est %d\n",i,--i * --i); }

    
    The program does:

    dhcp2.ai.univ-paris8.fr: a.out Le MAX de 10 et 12 est 12 Le MAX de 10 et 12 est 13 Le MAX de 11 et 14 est 15 Le carre de 12 est 23 Le carre de 11 est 132 Le carre de 13 est 132

    Et que diriez-vous de ce rsultat paradoxal ?

    #define MAX(s,t) s < t ? t : s main () { int i, j, k, m, n; i = 2; j = 5; k = 6; n = MAX(i,j); m = MAX(n, k); printf("MAX(%3d,%3d,%3d) == %3d\n",i,j, k, m); printf("MAX(%3d,%3d,%3d) == %3d\n",i,j, k, MAX(MAX(i,j),k)); }

    
    a a l'air tout simple et, presque, normal, non ? Essayons.

    jj@mu $ a.out MAX( 2, 5, 6) == 6 MAX( 2, 5, 6) == 5 jj@mu $

    
    ... qui n'est pas tout fait normal.
    Let's look at the preprocessed code:

    jj@mu $ gcc -E ex.c # 1 "ex.c" # 1 "" # 1 "" # 1 "ex.c" main () { int i, j, k, m, n; i = 2; j = 5; k = 6; n = i < j ? j : i; m = n < k ? k : n; printf("MAX(%3d,%3d,%3d) == %3d\n",i,j, k, m); printf("MAX(%3d,%3d,%3d) == %3d\n",i,j, k, i < j ? j : i < k ? k : i < j ? j : i); }

    
    Just look at it and the error seems ovious.
    Cette fois je vois bien o est l'erreur, dans ce cas on regarde, si i est plus petit que j on revoie j, sinon on fait l'valuation de i plus petit que k. C'est idiot, on voudrait justement le contraire !
    
  • Libraries
    Bibliothques
    There are some very well documented standard libraries, you should check them on:
    On trouvera de la documentation prcise sur les bibliothques standard sur
    le lien suivant. Vous devriez en prendre connaissance.
    
    

        IV.A) Arithmtique

    
    
    1. Dcalages
    Remarquons :
    

      Dcimal       Binaire
          3              11
          6             110
         12            1100
         24           11000
         48          110000
         96         1100000
        192        11000000
          4             100
          8            1000
         16           10000
         13            1101
         26           11010
    

    Remarquons que, en dcimal, 1230 et dix fois plus grand que 123. Donc, en binaire, 101010 et deux fois plus grand que 10101. L'oprateur de dcalage gauche

     << 

    permet donc de dcaler un nombre binaire de n cases donc de le multiplier par 2 puissance n.

    void puiss2 (int pmax) { int i, p; p = 1; for (i=0; i < pmax; i++) { printf("%d\t",p); p = p << 1; } printf("\n"); }

    
    Bien sr le dcalage droite fait exactement le contraire.
    Attention, pour les nombres ngatifs, comme vous le savez, pour que le nombre reste ngatif, si le premier chiffre est un 1, au cours du dclage droite, ce sont des 1 qui sont mis gauche !
    2. Et binaire

        01011010
    &   00011100
    ------------
        00011000
    
        01011010
    &   00000001
    ------------
        00000000
    

    S'crit avec &.

    int imper (int i) { return i & 0x01; }

    
    

    3. Ou binaire

    int nonul (int i) { while (i) { if (i | 0x01) return 1; i = i << 1; } return 0; } /* completement inutile, non */

    
    

    4. Ou bien binaire

    int differ (int i, int j) { if (i ^ j) return 1; return 0; }

    
    

    5. Non binaire

    Essayez donc ceci :

    int inver (int i) { return 1 + ~i; } int main () { int n; for (n = -10; n < 11; n++) printf("%d == - %d\n", n, inver(n)); }

    
    

        IV.B) Input/output
    Entres/Sorties

    
    
    1. First example see in class on March the 25th 2020
       To write on a file one needs to open it and... to write on it.
       We start by the vector definition.

       #include <stdio.h> #include <stdlib.h> #include <assert.h> struct vect { int nbele; int * v; } ; typedef struct vect vect_t;

       Print such a vector is easy :

       void afficv(vect_t v) { int i; for (i = 0; i < v.nbele; i++) printf("%d ",v.v[i]); printf("\n"); }

       Read from a file, first the number of elements then the elements is easy too, as soon as we have a file descriptor :

       vect_t lire (FILE * fd, int nbele) { vect_t v; int i, nbelefic, tmp; v.nbele = nbele; fscanf(fd, "%d ", &nbelefic); if (nbelefic < nbele) { nbele = nbelefic; } v.v = (int *) malloc (nbele* sizeof(int)); assert(v.v); for(i=0; i < nbele; i++) { fscanf(fd, "%d", &tmp); v.v[i] = tmp; } return v; }

       Write such a file should not worry you :

       void ecrire (FILE * fd, vect_t w) { int i; fprintf(fd,"%9d ",w.nbele); printf(" on met %d\n",w.nbele); for (i = 0; i < w.nbele; i++) fprintf(fd,"%9d ",w.v[i]); fprintf(fd,"\n"); }

       All that remain are two simple functions.

       vect_t creervect(nb) { int i, a, b, c; vect_t w; w.nbele = nb; w.v = (int *) malloc (nb * sizeof(int)); assert(w.v); a = 1; b = 1; w.v[0]=1; w.v[1]=1; for (i = 2; i < nb; i++) { c = a + b; w.v[i] = c; b = a; a = c; } return w; } int main (int argc, char * * argv) { int nb, lireou; FILE * fd; vect_t w; if (argc != 3) { printf(" Mode : a.out nb nmfic\rn nb est un entier et nmfic un nom de fichier\n"); exit (0); } nb = atoi (argv[1]); printf("argv[1] valait %d\n", nb); printf("Pour lire (1) ou ecrire (2) ?\n"); scanf("%d",&lireou); if (lireou == 1) { fd = fopen(argv[2],"r+");/* open the file to read it*/ assert(fd); w = lire(fd,nb); afficv(w); printf("Ou suis-je ? %ld\n",ftell(fd)); fseek(fd, 0L, 0); printf("Ou suis-je ? %ld\n",ftell(fd)); fseek(fd, -10L, SEEK_END); printf("Ou suis-je ? %ld\n",ftell(fd)); fclose(fd); exit (0); } printf("On va ecrire \n"); fd = fopen(argv[2],"w");/* open the file to write it*/ assert(fd); w = creervect(nb); afficv(w); ecrire(fd,w); fclose(fd); exit (0); } /* r r+ w w+ a a+ O debut debut dbut dbut fin fin non err err creation ftell(fd) -> le numro de la case du fichier (0 c'est le dbut, 1 le second octet...) fseed(fd,ecart,point) permet d'avancer de "ecart" octets partir du "point" SEEK_SET 0 SEEK_CUR 1 SEEK_END 2 */

    2. Second example
       

       #include <stdio.h> #include <stdlib.h> struct vectd { int nb; double * v; } ; typedef struct vectd vectd_t;

       Then we are able to write such a vector on the terminal:

       void afficher (vectd_t v){ int i; printf("%d ",v.nb); for (i = 0; i < v.nb; i++) printf("%lf ",v.v[i]); printf("\n"); }

       ... or on the file:

       void ecrire (vectd_t v, char * nomfichier) { int i; FILE * fd; fd = fopen (nomfichier, "w"); if (! fd) { /* good old ways */ printf("Impossible d ouvrir le fichier %s !\n\n", nomfichier); exit (1); } fprintf(fd,"%d ",v.nb); for (i = 0; i < v.nb; i++) fprintf(fd,"%lf ",v.v[i]); fclose(fd); }

       we need to create it:

       vectd_t creer (int nb) { vectd_t v; int i; double x, eps; v.nb = nb; v.v = (double *) malloc (nb * sizeof(double)); if (! v.v) { printf("Impossible d allouer la memoire de taille %d !\n\n", nb); exit (1); } eps = - 0.07; for (i = 0, x=1.3; i < v.nb; i++) { v.v[i] = x; x += eps; if (x < 1.0) eps = 0.145 + eps; if (x > 1.7) eps = - 0.145 + eps; } return v; }

       or to read it from the file:

       vectd_t lire (char * nomfichier) { vectd_t v; int i, nb; FILE * fd; double x; fd = fopen (nomfichier, "r"); if (! fd) { printf("Impossible d ouvrir le fichier %s !\n\n", nomfichier); exit (1); } fscanf(fd,"%d ",&nb); v.nb = nb; v.v = (double *) malloc (nb * sizeof(double)); if (! v.v) { printf("Impossible d allouer la memoire de taille %d !\n\n", nb); exit (1); } for (i = 0; i < v.nb; i++) { fscanf(fd,"%lf ",&x); v.v[i] = x; } fclose(fd); return v; }

       Here is a main function to use all the functions above.

       int main (int argc, char * * argv) { int nb, choix; vectd_t w; char * nf = "donnees.txt"; choix = 0; if (argc == 3) { choix = atoi (argv[1]); nb = atoi (argv[2]); printf("creation du fichier avec %d valeurs\n", nb); w = creer(nb); afficher(w); ecrire(w,nf); return 0; } if (argc == 2) { choix = atoi (argv[1]); } if (choix < 0 || choix > 1) choix = 0; switch(choix) { case 0: printf("creation du fichier\n"); nb = 21; w = creer(nb); afficher(w); ecrire(w,nf); break; case 1: printf("lecture du fichier\n"); w = lire(nf); afficher(w); break; } }

    3. Second example
       

       We need to read and write files. Let's start with some definitions.

       Nous allons voir maintenant comment on crit et comment on peut lire les contenus de fichiers. D'abord, il nous faut quelques dfinitions, c'est le fichier mydef.h :
    4. Third example
       

    5. A quicker version

       Version plus rapide

       The prototypes and definitions are given at first:
       Nous donnons ici simplement les fichiers direct.h, qui contient les dcalrations et prototypes,

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

       the file with the main function
       

       puis le fichier contenant 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); } } }

       then the two functions of file direct.c
       

       puis les deux fonctions qui composent le fichier direct.c, lire

       /*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); } }

       then remplir(fill it)
       puis remplir

       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]; }

       All that is to do now is compile and run the program.
       Il ne reste plus qu' copiler.

           V.A) Projets : un exemple de rapport

       Vous pouvez utiliser LaTeX pour rdiger votre projet. Pour cela vous trouverez ici plusieurs fichiers :
       • un exemple de rapport tabli grce LaTeX, ici en fichier pdf,
       • le rapport susmention en LaTeX,
       • le fichier de bibliographie utilise.

       ---

       Dernire mise jour le 19/4/2021 14h00

       ---