TP6: More K&R coding style
[Algorithmic_C.git] / TP6 / tas / tas.c
CommitLineData
249ff697
JB
1/******************************************************************************/
2/* tas */
3/******************************************************************************/
4
5#include <stdio.h>
6#include <stdlib.h>
7
8#define MAX 11
9
10typedef int TAS[MAX]; /* la case d'indice 0 n'est pas utilisee */
11
12
13/* affichage du tas */
14void 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 */
24void 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 */
32void 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 */
48void 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 */
62void 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/****************************************************************************/
70main()
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/***************************************************************************
101Le tableau initial
102 10 7 1 9 4 7 3 2 4 10
103Apres contruction du tas
104 10 10 7 9 7 1 3 2 4 4
105Le tas apres change(t,45,7,10)
106 45 10 10 9 7 1 7 2 4 4
107Le tas apres change(t,-5,3,10)
108 45 10 7 9 7 1 -5 2 4 4
109Le tas apres le tri
110 -5 1 2 4 4 7 7 9 10 45
111***************************************************************************/
112