Sven De Félice et Jean-Jacques BOURDIN

Université Paris 8

Labo IA, Dépt. Programmation et Informatique Fondamentale

2, rue de la Liberté

93526 Saint-Denis Cedex

FRANCE

Overview

Ch I) Let's try!

Ch II) Easy C

    II.A) Variables, Expressions, Types, Instructions

    II.A) Operators

    II.B) Control Flow

    II.C) Data Structures

    II.D) 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

Ch V) Just for you (Projects 2022)

    V.A) Example: a report in LaTeX

    III.D) Listes Chaînées

1. Lisp like lists
   Liste 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
   

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

   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 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 éléments
   

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

5. Le nombre d‘éléments
   

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

   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 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 entêtes à 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 é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. Fonction de concaténation de deux listes.
   11. Dans une liste rangée, insérer une cellule à sa place.
   12. Faire le tri d‘une liste, par insertion.
   13. Trouver le médian des éléments d‘une liste.
   14. 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 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 */ }

   Ou encore

   int plusgrandliter (liste l) { int plgd; liste crt, ptrplgd; if (! l) return INT_MAX; 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)))))))))

    
    

Quelques solutions vues en cours

• Moyenne des éléments de la liste
  C‘est pourtant simple : d‘une part on compte le nombre d‘éléments d‘autre part on fait la somme des éléments. Ensuite on divise.
  Attention, il faut traiter, au début, 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; }

• Création d‘une liste de nombres décroissants
  Il "suffit" de rajouter à gauche un nouvel élément :

  liste creel (int v) { int n; liste crt; n = 0; crt = (liste) 0; while(v--) { crt = cons(n++, crt); } return crt; }

   

      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> 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); 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 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->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("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->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 décroissant.
  Puis une fonction qui renvoie le nombre de sommets de l‘arbre.
  

      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 16/3/2022 10h00

  ---