Peut-on faire mieux ?

Cette incorporation du tableau dans une structure nous permet un passage par valeur de ce tableau. Ainsi, la copie évite la perturbation du fonctionnement de l'algorithme par la remontée non désirée des modifications faites dans les appels plus profonds. Nous avons le résultat souhaité, mais :

  • Si le tableau de la structure est très grand, les copies successives mobilisent une taille mémoire importante et un temps important pour copier des éléments peut-être inutiles,

  • La taille du tableau est limitée par la déclaration du type tstab.

Question

Pour éviter les deux inconvénients cités plus avant, il faut :

  • Supprimer toutes limites explicites de la taille des tableaux à traiter,

  • Éliminer les changements de tableau non souhaités.

En partant de la version initiale, écrivez une fonction void proc2(...) sans limites explicites de taille dans le prototype, restituant en fin de fonction la configuration du tableau telle qu'elle était à l'entrée de la fonction.

Indice

La taille ne peut être connue à la compilation. Ceci écarte l'utilisation d'une structure contenant un tableau.

La restitution du tableau à son état initial se fait à chaque niveau de la récursion. Chaque niveau est responsable de l'élimination de la perturbation apportée dans l'organisation du tableau.

Solution

1
void proc2(int ttab[], int n, int t) {
2
  int i, j;
3
  if (n==t) {
4
    for (i=0 ; i<=t ; ++i) printf("%d ",ttab[i]);
5
    printf("\n");
6
  }
7
  else
8
    for(j=n; j<=t; ++j) {
9
      /* modification inhérente à l'algorithme */
10
      echange(&ttab[n], &ttab[j]);
11
      proc2(ttab, n+1, t);
12
      /* annulation de la modification */
13
      echange(&ttab[n], &ttab[j]);
14
    }
15
}

Il suffit, à chaque niveau, de rétablir la modification faite. À la sortie de l'appel récursif, le sous-tableau retrouve sa configuration initiale.