Programmation Impérative
 Imperative Programming

TP Listes


  1. Type definition
    Définition des types
    typedef struct cell * liste_t;
typedef struct cell {
  float obj;
  struct cell * suiv;
} cell_t;
  2. 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;
}
  3. La somme des éléments
    float soml (liste_t l) {
  if (estvide(l)) {
    return 0.0;
  }
  return (*l).obj + soml((*l).suiv);
}
  4. Le nombre d‘éléments
    int howmany (liste_t l) {
  if (estvide(l)) {
    return 0;
  }
  return 1 + howmany ((*l).suiv);
}
  5. 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;
}
  6. 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);
}
  7. 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 par une fonction itérative.
    6. Faire la somme des éléments plus petits que x (paramètre fourni) 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.
    Dernière mise à jour le 6/3/2024 9h00