Refine .gitignore some more.

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

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