Programmation Impérative
Imperative Programming

Overview

Ch I) Let's try!

Ch II) Easy C

    II.A) Variables, Expressions, Types, Instructions

    II.B) Operators

    II.C) Control Flow

    II.D) Data Structures

    II.E) Compilation

Ch III) C Addresses

    III.A) Déjà vu

    III.B) Arrays

    III.D) Lists

    III.D) Trees

    III.C) Functions' Pointeers

Ch IV) C more than that

    III.A) Principles / Principes, Rappels

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 connaître l'emplacement, l'adresse, de la variable "a" en utilisant l'opérateur & :

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 spéciale qui contient des adresses, un pointeur. On peut aussi savoir ce qu'il y a à une certaine adresse avec l'opérateur unaire *.

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

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
a = 5	 v = 8
a = 8	 v = 5
*/

      nom  adresse contenus
main   a   400     5    puis 13        puis 8
main   v   404     8            puis 5
iv     pa  408     400    
iv     pb  416     404

/* une autre version */
#include <stdio.h>

void nrut (int * px, int * py) {
  * px = * px + * py;
  * py = * px - * py;
  * px = * px - * py;
}
void lookatit (int n) {
  int x, y;
  int * px, * py; /* adresses de int */

  x  = n; 
  y  = 3; 
  px  = & x; 
  py  = & y;
  printf("adresses de x %p et y %p\n",px, py);
  printf("Avant : valeurs de x %d et y %d\n",x, y);
  nrut(px,py);
  printf("Avant : valeurs de x %d et y %d\n",x, y);
}
int main () {
  lookatit(5);
}
/*
adresses de x 0x7ff7b32b7768 et y 0x7ff7b32b7764
Avant : valeurs de x 5 et y 3
Apres : valeurs de x 3 et y 5
*/

/* Fait par JJ B en 2010 */
#include <stdio.h>
  
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);
  }
}
int 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 */ #include <stdio.h> #include <stdlib.h> typedef struct vecteur { int nbe; float tab [100]; } vecteur_t; typedef float * pfloat; float somv (vecteur_t v) { int i; float som; pfloat 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é défini 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 un vecteur de nombre complexes

   Nous complétons la structure de nombres complexes présentée sur les vecteurs de structures. Ceci serait bien placé dans un fichier Header (tel que comp.h.

   #include <stdio.h> #include <stdlib.h> typedef struct compl { float r; // représente la partie réelle float i; // représente la partie imaginaire } compl_t; typedef struct vecc { int nbc; compl_t vc [100]; float vm [100]; /* le module pour chacun */ } vecc_t; vecc_t creevec (int); vecc_t calculmodule (vecc_t); void affvec (vecc_t); int mini (vecc_t);

   Nous donnons trois des fonctions importantes : main, creevec et module (qui calcule le carré du module d'un nombre complexe).

   Les autres fonctions sont à écrire par vous-mêmes.

   #include "comp.h" int main () { vecc_t v, w; int n, i; float mod, modmoy; n = 20; v = creevec(n); printf("Avant le module \n"); affvec (v); v = calculmodulecarre(v); printf("Avant le module \n"); affvec (v); i = mini (v); printf("le plus petit est le numéro %2d \t %f i%f et son module %f\n", i, v.vc[i].r, v.vc[i].i, v.vm[i]); } vecc_t creevec (int nb) { float reel, imag, eps; int i; vecc_t v; v.nbc = nb; reel = 1.0; imag = 2.0; eps = 0.13; for (i = 0; i < nb; i++) { v.vc[i].r = reel; v.vc[i].i = imag; reel += eps; imag -= eps; if (reel > 2.0) eps = 0.05 - eps; } return v; } float lemodulecarre (compl_t c) { return c.r * c.r + c.i * c.i; }

   Qui donne à l‘exécution :

   White.local: a.out Avant le module 0 : 1.000000 + i 2.000000 module 0.000000 1 : 1.130000 + i 1.870000 module 0.000000 2 : 1.260000 + i 1.740000 module 0.000000 3 : 1.390000 + i 1.610000 module 0.000000 4 : 1.520000 + i 1.480000 module 0.000000 5 : 1.650000 + i 1.350000 module 0.000000 6 : 1.780000 + i 1.220000 module 0.000000 7 : 1.910000 + i 1.090000 module 0.000000 8 : 2.040000 + i 0.960000 module 0.000000 9 : 1.960000 + i 1.040000 module 0.000000 10 : 1.880000 + i 1.120000 module 0.000000 11 : 1.800000 + i 1.200000 module 0.000000 12 : 1.720000 + i 1.280000 module 0.000000 13 : 1.640000 + i 1.360000 module 0.000000 14 : 1.560000 + i 1.440000 module 0.000000 15 : 1.480000 + i 1.520000 module 0.000000 16 : 1.400000 + i 1.600000 module 0.000000 17 : 1.320000 + i 1.680000 module 0.000000 18 : 1.240000 + i 1.760000 module 0.000000 19 : 1.159999 + i 1.840001 module 0.000000 Avant le module 0 : 1.000000 + i 2.000000 module 5.000000 1 : 1.130000 + i 1.870000 module 4.773800 2 : 1.260000 + i 1.740000 module 4.615200 3 : 1.390000 + i 1.610000 module 4.524200 4 : 1.520000 + i 1.480000 module 4.500800 5 : 1.650000 + i 1.350000 module 4.545000 6 : 1.780000 + i 1.220000 module 4.656800 7 : 1.910000 + i 1.090000 module 4.836200 8 : 2.040000 + i 0.960000 module 5.083200 9 : 1.960000 + i 1.040000 module 4.923200 10 : 1.880000 + i 1.120000 module 4.788800 11 : 1.800000 + i 1.200000 module 4.680000 12 : 1.720000 + i 1.280000 module 4.596800 13 : 1.640000 + i 1.360000 module 4.539200 14 : 1.560000 + i 1.440000 module 4.507200 15 : 1.480000 + i 1.520000 module 4.500800 16 : 1.400000 + i 1.600000 module 4.520000 17 : 1.320000 + i 1.680000 module 4.564800 18 : 1.240000 + i 1.760000 module 4.635201 19 : 1.159999 + i 1.840001 module 4.731201 le plus petit est le numéro 4 1.520000 i1.480000 et son module 4.500800

   Bien évidemment il aura fallu créer la fonction qui calcule le module de tous les complexes du vecteur.

    

2. Dynamic arrays
   Tableaux dynamiques
   
We oversize our arrays, is it such a good idea?
Jusqu'à présent, vous avez un problème avec la taille des tableaux et vecteurs, ce n'est plus la peine grâce aux tableaux dynamiques.

#include<stdio.h> #include<stdlib.h> #include<assert.h> 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))); assert(pt); fcttab(n, pt); seetab(pt, nbele); free(pt); /* c'est plus joli, plus souple, plus dynamique */ }



3. Exercices

   Refaire toutes les fonctions déjà vues sur les tableaux mais avec des tableaux dynamiques.

 

 

 

Voici une modification de la création d‘un vecteur de nombres complexes :

vecc_t creevec (int nb) { float reel, imag, eps; int i; compl_t *ptr; vecc_t v; v.nbc = nb; v.vc = malloc( nb * sizeof(compl_t)); assert(v.vc); v.vm = malloc( nb * sizeof(float)); assert(v.vm); ptr = v.vc; reel = 1.0; imag = 2.0; eps = 0.13; for (i = 0; i < nb; i++) { ptr->r = reel; ptr->i = imag; ptr++; reel += eps; imag -= eps; if (reel > 2.0) eps = 0.05 - eps; } return v; }

et la modification du fichier comp.h :

#include <stdio.h> #include <stdlib.h> #include <assert.h> struct compl { float r; // représente la partie réelle float i; // représente la partie imaginaire } ; typedef struct compl compl_t; struct vecc { int nbc; compl_t * vc; float * vm; /* le module pour chacun */ } ; typedef struct vecc vecc_t; vecc_t creevec (int); vecc_t calculmodule (vecc_t); void affvec (vecc_t); int mini (vecc_t);

Voici un exemple pour des tableaux d'altitude. Pour une carte, ici, un tableau carré, chaque case (une petite surface du terrain) contient son altitude. Voici l'ensemble du programme qui crée un tableau d'altitudes (la topographie d'un terrain) et l'affiche.
Let's see some new types to work on the altitude field.
Créons d'abord les types qui vont nous servir :

typedef unsigned int uint; typedef float * tabalt ; typedef struct tableau { tabalt t; unsigned int nbc; unsigned int nbl; } 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 créer 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 récupérer 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 systématiquement le tableau avec les mêmes valeurs que dans l'exemple donné précédemment :

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 dénivelé entre les deux.
2. pour deux points de la même horizontale, donner la somme des dénivelés positifs entre eux.
3. pour deux points de la même verticale, donner la somme des dénivelés positifs entre eux.
4. pour deux points de la même verticale, donner la somme des dénivelés positifs et la somme des dénivelés négatifs entre eux. (utilisation d'une structure ad hoc).
5. pour deux points donnés, calculer les dénivelés positifs et négatifs entre eux, selon la droite qui les joint.

    III.D) Listes Chaînées

1. Lisp like lists
   Listes Lisp
   

   Hereafter is a function building a list of n numbers. It's written in scheme, you'll have to translate it.

   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
   Définition des types
   

   typedef struct cell * liste_t; typedef struct cell { float obj; struct cell * suiv; } cell_t;

   Here you see that a list is only the adress of a structure.

   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_t l) { if (l == (liste_t) 0) { return 1; } return 0; } int estnonvide (liste_t l) { if (l == (liste_t) 0) { return 0; } return 1; }

4. La somme des éléments
   

   float soml (liste_t l) { if (estvide(l)) { return 0.0; } return (*l).obj + soml((*l).suiv); }

5. Le nombre d‘éléments
   

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

6. La construction
   

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

7. Trois fonctions d‘affichage
   

   void affl (liste_t l) { if (estvide (l)) { printf("\n"); } else { printf("%5.2f ", (*l).obj); affl ((*l).suiv); } }

   Notons que (*l).nxt s‘écrit aussi l->nxt, la flèche, ici "-" et ">", est un nouvel opérateur qui remplace une écriture un peu longue.

   void affll (liste_t l) { if (estvide (l)) { printf("\n"); } else { printf("%5.2f ", l->obj); affll (l->suiv); } } void affw (liste_t l) { while (estnonvide (l)) { printf("%5.2f ", l->obj); l = l->suiv; } printf("\n"); }

   Des entêtes à inclure :

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

   La fonction main :

   int main () { liste_t 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 élément.
   2. Afficher les éléments dans l‘ordre inverse.
   3. Mettre les éléments 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 décroissant).
   5. Faire la somme des éléments d‘une liste.
   6. Faire la somme des éléments plus petits que 50 d‘une liste.
   7. Faire la moyenne des éléments d‘une liste.
   8. Enlever le premier élément d‘une liste.
   9. Enlever le dernier élément d‘une liste.
   10. Intervertir le premier et le second éléments d‘une liste.
   11. Fonction de concaténation de deux listes.
   12. Dans une liste rangée, insérer une cellule à sa place.
   13. Faire le tri d‘une liste, par insertion.
   14. Faire le tri d‘une liste, avec Quicksort.
   15. Trouver le médian des éléments d‘une liste.
   16. Fabriquer une liste des carrés de tous les éléments d‘une autre liste passée en paramètre.
   Exemple de solution

   int plusgrandliste (liste_t 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_t l) { if (l) return plusgrandliste (l->next, l->nb); return INT_MIN; /* impose d‘avoir inclus limits.h */ }

   Ou encore

   int plusgrandliter (liste_t l) { int plgd; liste_t crt, ptrplgd; if (! l) return INT_MIN; /* il faut avoir inclus limits.h */ ptrplgd = l; plgd = ptrplgd->nb; crt = l->nxt; while (crt) { if (crt->nb > plgd) { plgd = crt->nb; ptrplgd = crt; } crt = crt->nxt; } return plgd; }

    

9. Inversion d‘une liste.
10. Inversion par la méthode PG/DG.

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

    
    

    III.D) Arbres

"La beauté des arbres est de croître." (qui ?)

Nous présentons 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>

typedef struct noeud {
  int num;
  float val;
  struct noeud * sg;
  struct noeud * sd;
} noeud_t;

typedef struct noeud * arbre_t;

arbre_t ajout (arbre_t a, int v, float x) {
  arbre_t new;
  int rande;
  if (! a) {
	new = (arbre_t) malloc (sizeof (noeud_t));
	new->num = v;
	new->val = x;
	new->sg = (arbre_t) 0;
	new->sd = (arbre_t) 0;
	return new;
  }
  rande = rand ();
  if (rande & 0x01) {
	/* on le met à gauche*/
	if (! (a->sg)) {
	  /* s'il ny a pas de fils gauche */
	  a->sg = (arbre_t) malloc (sizeof (noeud_t));
	  a->sg->num = v;
	  a->sg->val = x;
	  a->sg->sg = (arbre_t) 0;
	  a->sg->sd = (arbre_t) 0;
	  return a;
	}
	a->sg = ajout(a->sg, v, x);
	return a;
  }
  /* on le met donc a droite*/
  if (! (a->sd)) {
	/* s'il ny a pas de fils droit */
	a->sd = (arbre_t) malloc (sizeof (noeud_t));
	a->sd->num = v;
	a->sd->val = x;
	a->sd->sg = (arbre_t) 0;
	a->sd->sd = (arbre_t) 0;
	return a;
  }
  a->sd = ajout(a->sd, v, x);
  return a;
}
/*
  To create the tree, you add, one after the other, the values in the
  tree.
*/
arbre_t creation (int n) {
  arbre_t a;
  float x, y;
  x = 1.5;
  y = 0.21;
  a = (arbre_t) 0;
  while (n--) {
	a = ajout (a, n, x);
	x += y;
	y += 0.06;
	if (x > 3.0 || x < -2.0)
	  y = - y;
  }
  return a;
}

void afficharbre (arbre_t a) {
  if (a) {
	afficharbre (a->sg);
	printf("%d %3.2f ", a->num, a->val);
	afficharbre (a->sd);
  }
}

int appartient (arbre_t a, float x) {
  if (! a)
    return 0;
  if (a->val ==  x)
    return 1;
  return appartient(a->sg, x) || appartient (a->sd, x);
}

• 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 supérieur à une valeur donnée.
• 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 générations entre la racine de l‘arbre et la cellule cherchée. 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->sg, x) || fappartient (a->sd, 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("methode 1\t %f dedans %s\n", x, appartient(a,x) ? "Oui" : "Non"); printf("methode 2\t%f dedans %s\n", x, fappartient(a,x) ? "OUI" : "NON"); }

Cette fois :


methode 1 0.720000 dedans Non methode 2 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 is lower than n
and every value in its right part is greater or equal than n.
Here after is a function that build a BST.
C‘est la même structure mais elle respecte deux conditions : pour tout sommet de valeur n, tous ses descendants à gauche ont une valeur inférieure à n et tous ses descendants à droite one une valeur supérieure ou égale à n.
Voici la fonction de création d'un tel arbre :

arbre ajout (arbre a, int v, float x) { arbre new; if (! a) { new = (arbre) malloc (sizeof (noeud)); new->num = v; new->val = x; new->sg = (arbre) 0; new->sd = (arbre) 0; return new; } if (x < a->val) { /* on le met à gauche*/ if (! (a->sg)) { /* s‘il ny a pas de fils gauche */ a->sg = (arbre) malloc (sizeof (noeud)); a->sg->num = v; a->sg->val = x; a->sg->sg = (arbre) 0; a->sg->sd = (arbre) 0; return a; } a->sg = ajout(a->sg, v, x); return a; } /* on le met donc a droite*/ if (! (a->sd)) { /* s‘il ny a pas de fils droit */ a->sd = (arbre) malloc (sizeof (noeud)); a->sd->num = v; a->sd->val = x; a->sd->sg = (arbre) 0; a->sd->sd = (arbre) 0; return a; } a->sd = ajout(a->sd, 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); }

Voici une fonction présentée en cours pour améliorer l‘affichage :

void blancs (int n) { while (n--) printf(" "); } void voisarbre (arbre a, int nbb) { if (a) { voisarbre (a->sg, nbb + 1); blancs (nbb); printf("%2d %d %3.3f\n", nbb, a->num, a->val); voisarbre (a->sd, nbb + 1); } else printf("\n"); }

Puis une fonction qui compte le nombre d‘occurences d‘une certaine valeur non entière x 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 décroissant.
Puis une fonction qui renvoie le nombre de sommets de l‘arbre.
Puis une fonction qui renvoie le nombre de feuilles de l‘arbre.
Puis une fonction qui renvoie le nombre de sommets de l‘arbre ayant effectivement deux successeurs.
Puis une fonction qui renvoie le nombre de sommets de l‘arbre ayant effectivement un successeur.


    III.C) Graphes

Le fichier header :

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #include<assert.h> #define MAXSUCC 10 typedef unsigned short Shu; /* pour le vecteur de successeurs */ typedef struct neuvec { Shu val; Shu num; /* son numero dans le vecteur */ int nbs; struct neuvec * succ [MAXSUCC]; } neuvec_t; typedef struct neuvec * ptvec_t; typedef struct graphevec { int nbn; Shu * vu; ptvec_t * noeud; } gravec_t; void voirgraf (gravec_t); gravec_t creegraphevec(int); /* l'argument est le nombre de noueds */

Fonctions de création et d‘affichage :

gravec_t creegraphe (int nbn) { Shu i, j, max, nbaretes, num, nba; float v, taux; gravec_t g; ptvec_t ptr; g.nbn = nbn; max = nbn * nbn; taux = 25.0; num = nbn / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.vu = (Shu *) malloc (nbn * sizeof(Shu)); assert(g.vu); bzero(g.vu, nbn << 2); g.noeud = (ptvec_t *) malloc (nbn * sizeof(ptvec_t)); assert(g.noeud); for (i = 0; i < nbn; i++) { g.noeud[i] = (ptvec_t) malloc (sizeof(neuvec_t)); assert(g.noeud[i]); g.noeud[i]->num = i; g.noeud[i]->nbs = 0; for (j = 0; j < MAXSUCC; j++) g.noeud[i]->succ[j] = NULL; } /* srand(time(NULL)); */ nbaretes = 0; for (i = 0; i < nbn; i++) { ptr = g.noeud[i]; nba = 0; j = i + 1; while (j < nbn && nba < MAXSUCC) { v = (float) rand () / RAND_MAX; printf(" v %f\t", v); if (v < taux) { ptr->succ[nba] = g.noeud[j]; nba++; nbaretes++; } j++; } ptr->nbs = nba; } printf("au total il y a %d aretes\n", nbaretes); return g; } void voirgraph(gravec_t gv) { int i, j; ptvec_t ptr; for (i = 0; i < gv.nbn; i++) { ptr = gv.noeud[i]; printf ("noeud %3d\t", i); printf ("%3d %3d \t %3d successeurs\t", ptr->num, ptr->val, ptr->nbs); for (j = 0; j < ptr->nbs; j++) { printf("%d, ", ptr->succ[j]->num); } printf("\n"); } }

Et un exemple de fonction main (mais il faut rajouter les fonctions qui manquent).

int main (int argc, char ** argv) { gravec_t gv; int nb, res; Shu from, to; if (argc == 2) nb = atoi(argv[1]); else nb = 50; /* ainsi, si je ne donne pas d‘argument à la commande, par défaut, on crée 50 sommets */ gv = creegraphe (nb); voirgraph(gv); from = 2; to = 5; res = cheminvec_init (&gv, from, to); if (!res) printf("pas de chemin de %d a %d\n", from, to); else { printf("Chemin de %d a %d\n", from, to); voircheminvec(gv); } printf("Il y a %d aretes\n", compternonzerovec(gv)); res = cheminvec_init (&gv, from, to); if (!res) printf("pas de chemin de %d a %d\n", from, to); else { printf("Chemin de %d a %d\n", from, to); voircheminvec(gv); } }

    III.C) Pointeurs de fonctions

D‘abord une déclaration de type.

typedef void (* ptrfct) ();


Ensuite les fonctions

void fcta () { printf(" a "); } void fctb () { printf(" b "); }




void g (void (* fct) ()) { printf("g appelle :"); fct(); printf("\n"); } void gg (ptrfct f) { printf("gg appelle :"); f(); printf("\n"); } void fcttest () { g(fcta); g(fctb); gg(fcta); gg(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; n = 0; } return n-1; /* Notons le n - 1 */ }




void main () { int n; ptrfct tf [] = {fcta, fctb}; fcttest (); n = menu(); tf[n](); for (n=0; n < 2; n++) gg(tf[n]); }


Voici ce travail à peine modifié pour que les fonctions fcta et fctb reçoivent un argument qui sera affiché aussi.

typedef void (* ptrfct) (int); void fcta (int a) { printf("Fonction 1: "); printf("%d\n",a); } void fctb (int a) { printf("Fonction 2: "); printf("%d\n",a); } void g (void (* fct) (), int n) { printf("g appelle :"); fct(n); printf("\n"); } void gg (ptrfct f, int n) { printf("gg appelle :"); f(n); printf("\n"); } 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; n = 0; } return n-1; } int main () { int n, m; ptrfct tf [] = {fcta, fctb}; m = 10; n = menu(); g(tf[n], m); gg(tf[n], m); }




---

Dernière mise à jour le 15/3/2024 19h00

---