TD-4, pointeurs

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-4/enonce.html

Programmes Prenom.Nom.c à déposer par ftp sur poly en /users/profs/maranget/TD-4.

1 Tour de chauffe

Soit le programme suivant :

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

typedef struct coucou {
  int val;
} coucou;

coucou *consCoucou(int v)
{
  coucou *r;

  r = (coucou *)malloc(sizeof(coucou));
  if (r == NULL) {
    fprintf(stderr,"Plus de memoire !!!\n");
    exit(-1);
  }
  r->val = v;
  return r;
}

void main(void)
{
  coucou *p,*q;

  p = consCoucou(1);
  q = p;
  q->val = q->val + 1;
  printf("%d %d\n",p->val,q->val);
}

Deviner ce qu'affiche le programme, en cas de doute, le compiler et l'exécuter.

Quel est l'affichage, si on remplace la ligne q = p; dans main par la ligne q = consCoucou(p->val) ?

2 Ensembles

On considère le type Set des ensembles d'entiers, les ensembles étant implantés en machine pas des listes d'entiers.

typedef struct cell {
  int val;
  struct cell *next;
} Cell;

typedef Cell *Set;

Le fait que les listes d'entiers encodent les ensembles d'entiers se traduira par une contrainte supplémentaire : les entiers contenus dans les listes doivent être deux à deux distincts.

2.1 Fonction de construction

On commence par créer une fonction très utile, la fonction cons de construction des listes.

Set cons(int v,Set s)

Étant donnés un entier v et une liste d'entiers s la fonction cons alloue une nouvelle cellule de liste contenant v, l'ajoute en tête de s et renvoie un pointeur sur la nouvelle liste ainsi construite. La fonction cons est la seule fonction de votre programme à venir qui fait appel à l'allocateur système malloc.

2.2 Fonctions de base

Écrire les trois fonctions suivantes :

La fonction afficher affiche un ensemble à l'écran, par exemple {} ou {1, 3, 2}.
La fonction dedans teste l'appartenance d'un entier à un ensemble.
La fonction ajouter ajoute un élément à un ensemble. Attention, une liste qui représente un ensemble ne peut pas contenir deux fois le même élément.

Voici des signatures possibles pour ces trois fonctions :

void afficher(Set s)
int dedans(int i,Set s)
Set ajouter(int i,Set s)

2.3 Réunion, intersection, ...

Programmer la réunion, l'intersection, l'inclusion et l'égalité des ensembles.

2.4 Calcul de point fixe

On demande de fermer un ensemble par la soustraction. C'est à dire que, étant donné un ensemble S, on définit la fermeture de S par soustraction S^- comme le plus petit ensemble qui obéit aux deux propriétés suivantes :

S^- contient S.
Si x appartient à S^- et y appartient à S^-, alors la valeur absolue de x-y appartient à S^-

On calcule S^- comme la limite d'une suite d'ensembles que l'on va définir. On commence par généraliser la soustraction aux ensembles d'entiers. Soit moins une nouvelle fonction :

Set moins(Set s)

Étant donné un ensemble S, moins(S) est l'ensemble des valeurs absolues des différences des éléments de S. On montre que S^- est la limite de la suite S_i, avec :

S₀ = S, S_i+1 est la réunion de S_i et de moins(S_i).

On montre aussi que la suite S_i finit par être stationnaire.

En déduire une manière de calculer S^- et l'écrire en C. On affichera les étapes intermédiaires du calcul pour, par exemple, obtenir l'affichage suivant :

Fermeture par soustraction de {9 24}
s0 = {9 24}
s1 = {24 9 15 0}
s2 = {24 9 6 15 0}
s3 = {24 9 3 18 6 15 0}
s4 = {24 18 12 3 21 6 9 15 0}
limite = {24 18 15 21 9 12 3 6 0}

Vous trouverez la solution de cet exercice en set.txt.

3 Calcul de factorielle

Nous connaissons tous l'écriture décimale des entiers, 0, 123, etc. Lorsque l'on ne veut pas borner à priori la taille des entiers manipulés, il devient intéressant de les représenter comme la liste de leurs chiffres en représentation décimale.

3.1 Définitions de base

Les grands entiers seront représentés par la liste de leurs chiffres en ordre inverse (afin de faciliter l'arithmétique). Zéro pourra être représenté par le pointeur nul (NULL).

Écrire le type Entier des grands entiers, ainsi que la fonction de construction nouveau_chiffre. La signature de nouveau_chiffre est la suivante :

Entier nouveau_chiffre(unsigned int valeur,Entier suivant)

La fonction nouveau_chiffre prend un entier val entre zéro et neuf en argument, ainsi qu'un grand entier suivant et renvoie un nouveau grand entier qui est obtenu en mettant le nouveau chiffre val en tête de la représentation de suivant.

Attention, puisque les grands entiers sont représentés par la liste en ordre inverse de leurs chiffres, de sorte que si suivant représente n, alors le nouveau grand entier représente val+10 * n.

Toutes les fonctions suivantes ne devront jamais utiliser malloc directement, mais mais toujours nouveau_chiffre.

3.2 Lecture et écriture

Écrire une fonction grandir qui prend un entier non signé en argument unsigned int et renvoie un grand entier qui le représente. Écrire une fonction affiche qui prend un grand entier en argument et l'affiche. Voici des signatures possibles pour ces fonctions :

Entier grandir(unsigned int i)
void affiche(Entier i)

3.3 Factorielle

Écrire une fonction mult de multiplication par un scalaire avec retenue. Voici une signature pour mult :

Entier mult(unsigned int n, Entier p,unsigned int retenue)

Donc, mult renvoie un grand entier qui représente n que multiple p plus la retenue. On aura intérêt à écrire mult de façon récursive après avoir un peu réfléchi à l'algorithme de multiplication de l'école primaire.

Programmer la factorielle, en utilisant mult. On obtiendra par exemple :

32! = 263130836933693530167218012160000000

Vous trouverez la solution de cet exercice en grand.txt.

Ce document a été traduit de L^AT_EX par H^EV^EA.