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