Add latest implementation of tree algorithm in TP6 directory

[Algorithmic_C.git] / TP6 / tas / tas.c

diff --git a/TP6/tas/tas.c b/TP6/tas/tas.c
new file mode 100644 (file)
index 0000000..c3edbd3
--- /dev/null
+++ b/TP6/tas/tas.c
@@ -0,0 +1,112 @@
+/******************************************************************************/
+/*                                  tas                                       */
+/******************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#define MAX 11
+
+typedef int TAS[MAX]; /* la case d'indice 0 n'est pas utilisee */
+
+
+/* affichage du tas  */
+void affiche_tas(TAS t, int n, char *message)
+{
+  int i;
+  printf("%s \n",message);
+  for (i=1;i<=n;i++) printf("%5d ",t[i]);
+  printf("\n");   
+}            
+
+
+/* initialisation du tas la valeur val */
+void init_tas(TAS t, int n, int val)
+{
+ int i;
+ for (i=0;i<=n;i++) t[i] = val;
+}
+
+
+/* descente de l'element se trouvant au sommet du tas, a l'indice 1 et pas 0 */
+void descente(TAS t, int g, int d)
+{
+ int i, j, x; /* i indice du pere - j indice du fils */
+ x = t[g]; i =g ; j = 2*i;
+ while (j<= d)
+  {
+   if (j < d) if (t[j] < t[j+1]) j++; /* j indice du fils choisi */
+  
+   if (x < t[j]) {t[i] = t[j]; i = j; j*=2;}
+   else break;
+  }
+ t[i] = x;
+}
+
+
+/* montee de l'element d'indice m */
+void montee(TAS t,int m, int n)
+{
+ int i, j, x; /* i indice du pere - j indice du fils */
+ x = t[m]; j = m; i = j/2;
+ while (i>= 1)
+  {
+   if (x > t[i]) {t[j] = t[i]; j = i; i = j/2;}
+   else break;
+  }
+ t[j] = x;
+}
+
+
+/* remplacement de l'element d'indice m  par nouv_val et mise a jour du tas */
+void change(TAS t, int nouv_val, int m, int n)
+{
+ if (nouv_val < t[m]) {t[m] = nouv_val; descente(t,m,n); }
+ else  {t[m] = nouv_val; montee(t,m,n);}
+}
+
+
+/****************************************************************************/                 
+main()
+{int n = MAX-1;        
+ int i, g, d, x;
+ TAS t;
+ 
+ srand(time(NULL));
+ for (i=1;i<=n;i++) t[i] = rand()%MAX;
+ affiche_tas(t,n,"Le tableau initial");
+
+ g = (n / 2) + 1; d = n;
+ while (g > 1) descente(t,--g,d);
+ 
+ affiche_tas(t,n,"Apres contruction du tas");
+ change(t, 45, 7, 10);
+ affiche_tas(t,n,"Le tas apres change(t,45,7,10)");
+ change(t, -5, 3, 10);
+ affiche_tas(t,n,"Le tas apres change(t,-5,3,10)");
+ 
+ while (d > 1) {
+       x=t[1]; /* le max */
+       t[1]=t[d]; /* le dernier devient le premier du tableau */
+       t[d]=x; /* le max est place a la fin du tableau */
+        descente(t,g,--d); /* on fait descendre le nouveau premier elt a sa bonne place */
+               }       
+ affiche_tas(t,n,"Le tas apres le tri");
+
+  for (i=1;i<n;i++) if (t[i]>t[i+1]) {printf("Erreur tri\n");break;}
+} 
+
+
+/***************************************************************************   
+Le tableau initial 
+   10     7     1     9     4     7     3     2     4    10 
+Apres contruction du tas 
+   10    10     7     9     7     1     3     2     4     4 
+Le tas apres change(t,45,7,10) 
+   45    10    10     9     7     1     7     2     4     4 
+Le tas apres change(t,-5,3,10) 
+   45    10     7     9     7     1    -5     2     4     4 
+Le tas apres le tri 
+   -5     1     2     4     4     7     7     9    10    45 
+***************************************************************************/
+