Jean-Jacques BOURDIN

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

Programmation Impérative
 Imperative Programming

Spring 2023

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 2023)

    V.A) Example: a report in LaTeX

 

 

 

 

Ch III) Adresses C

    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
    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).obj  = (float) nb;
  (*new).suiv = 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;
  float s;
  nb = 10;
  l = creer(nb);
  affw(l);
  s = soml(l);
  printf("Total : %f\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_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 
    float plusgrandliter (liste_t l) {
   float plgd;
   liste_t crt, ptrplgd;
   if (! l)
      return INT_MIN; /* il faut avoir inclus limits.h */
   ptrplgd = l;
   plgd = ptrplgd->obj;
   crt = l->suiv;
   while (crt) {
      if (crt->obj > plgd) {
         plgd = crt->obj;
         ptrplgd = suiv;
      }
      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