tas.c

   1 /******************************************************************************/
   2 /*                                  tas                                       */
   3 /******************************************************************************/
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 #define MAX 11
   9
  10 typedef int TAS[MAX]; /* la case d'indice 0 n'est pas utilisee */
  11
  12
  13 /* affichage du tas  */
  14 void affiche_tas(TAS t, int n, char *message)
  15 {
  16   int i;
  17   printf("%s \n",message);
  18   for (i=1;i<=n;i++) printf("%5d ",t[i]);
  19   printf("\n");
  20 }
  21
  22
  23 /* initialisation du tas la valeur val */
  24 void init_tas(TAS t, int n, int val)
  25 {
  26  int i;
  27  for (i=0;i<=n;i++) t[i] = val;
  28 }
  29
  30
  31 /* descente de l'element se trouvant au sommet du tas, a l'indice 1 et pas 0 */
  32 void descente(TAS t, int g, int d)
  33 {
  34  int i, j, x; /* i indice du pere - j indice du fils */
  35  x = t[g]; i =g ; j = 2*i;
  36  while (j<= d)
  37   {
  38    if (j < d) if (t[j] < t[j+1]) j++; /* j indice du fils choisi */
  39
  40    if (x < t[j]) {t[i] = t[j]; i = j; j*=2;}
  41    else break;
  42   }
  43  t[i] = x;
  44 }
  45
  46
  47 /* montee de l'element d'indice m */
  48 void montee(TAS t,int m, int n)
  49 {
  50  int i, j, x; /* i indice du pere - j indice du fils */
  51  x = t[m]; j = m; i = j/2;
  52  while (i>= 1)
  53   {
  54    if (x > t[i]) {t[j] = t[i]; j = i; i = j/2;}
  55    else break;
  56   }
  57  t[j] = x;
  58 }
  59
  60
  61 /* remplacement de l'element d'indice m  par nouv_val et mise a jour du tas */
  62 void change(TAS t, int nouv_val, int m, int n)
  63 {
  64  if (nouv_val < t[m]) {t[m] = nouv_val; descente(t,m,n); }
  65  else  {t[m] = nouv_val; montee(t,m,n);}
  66 }
  67
  68
  69 /****************************************************************************/
  70 main()
  71 {int n = MAX-1;
  72  int i, g, d, x;
  73  TAS t;
  74
  75  srand(time(NULL));
  76  for (i=1;i<=n;i++) t[i] = rand()%MAX;
  77  affiche_tas(t,n,"Le tableau initial");
  78
  79  g = (n / 2) + 1; d = n;
  80  while (g > 1) descente(t,--g,d);
  81
  82  affiche_tas(t,n,"Apres contruction du tas");
  83  change(t, 45, 7, 10);
  84  affiche_tas(t,n,"Le tas apres change(t,45,7,10)");
  85  change(t, -5, 3, 10);
  86  affiche_tas(t,n,"Le tas apres change(t,-5,3,10)");
  87
  88  while (d > 1) {
  89         x=t[1]; /* le max */
  90         t[1]=t[d]; /* le dernier devient le premier du tableau */
  91         t[d]=x; /* le max est place a la fin du tableau */
  92         descente(t,g,--d); /* on fait descendre le nouveau premier elt a sa bonne place */
  93                }
  94  affiche_tas(t,n,"Le tas apres le tri");
  95
  96   for (i=1;i<n;i++) if (t[i]>t[i+1]) {printf("Erreur tri\n");break;}
  97 }
  98
  99
 100 /***************************************************************************
 101 Le tableau initial
 102    10     7     1     9     4     7     3     2     4    10
 103 Apres contruction du tas
 104    10    10     7     9     7     1     3     2     4     4
 105 Le tas apres change(t,45,7,10)
 106    45    10    10     9     7     1     7     2     4     4
 107 Le tas apres change(t,-5,3,10)
 108    45    10     7     9     7     1    -5     2     4     4
 109 Le tas apres le tri
 110    -5     1     2     4     4     7     7     9    10    45
 111 ***************************************************************************/
 112