repositories / Algorithmic_C.git / blame
| Commit | Line | Data |
|---|---|---|
| 249ff697 JB |
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 |