| 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 | ***************************************************************************/ |