#include #include #include "memoire.h" #include "abr.h" typedef int *couple; static couple creer_couple (int a, int b) { couple c = (int *) memoire_allouer (2 * sizeof (int)); c[0] = a; c[1] = b; return c; } int cmp_sur_1 (const couple a, const couple b) { return (a[0] > b[0]) - (a[0] < b[0]); } void afficher (couple c) { printf ("(%d, %d)\n", c[0], c[1]); } void afficher_elem (void *vide, void *cpl) { afficher ((couple) cpl); } /************************************************************************/ static void incremente (int *n, void *elt) { (*n)++; } static unsigned int cardinal (abr a) { unsigned int taille = 0; abr_appliquer (a, (appliquer) incremente, &taille); return taille; } /***************************************************************************/ /* voici une version un peu mysterieuse de abr2tableau */ /* exo: faire plus efficace à l'aide d'un type tableau dynamique */ static void ranger (void ***tab, void *elt) /* *tab contient l'adresse de la prochaine case à remplir */ { *(*tab)++ = elt; /* equivalent à **tab = elt; *tab = *tab + 1; */ } static couple * abr2vecteur (abr a) { couple *vecteur, *tmp; tmp = vecteur = (couple *) memoire_allouer (cardinal (a) * sizeof (couple)); abr_appliquer (a, (appliquer) ranger, &tmp); return vecteur; } /************************************************************************/ struct resultat { int compteur; couple valeur; }; static void valeur_ieme (struct resultat *r, void *elt) { r->compteur--; if (r->compteur == 0) r->valeur = elt; } static void * abr_ieme (abr a, int ieme) { struct resultat r = { ieme, NULL }; abr_appliquer (a, (appliquer) valeur_ieme, &r); return r.valeur; } /**************************************************************************/ int main (int argc, char *argv[]) { abr a = abr_creer ((comparer) cmp_sur_1); printf ("insertion de couples\n"); { /* Creation d'un abr un peu tordu */ int i; for (i = 0; i < 12; i += 4) { couple c; abr_inserer (a, c = creer_couple (i + 3, 20 - i)); afficher (c); abr_inserer (a, c = creer_couple (i, 40 - i)); afficher (c); abr_inserer (a, c = creer_couple (i + 2, 30 - i)); afficher (c); abr_inserer (a, c = creer_couple (i + 1, 100 - i)); afficher (c); } } printf ("appliquer afficher \n"); abr_appliquer (a, (appliquer) afficher_elem, NULL); printf ("abr2vecteur \n"); { /* test abr2vecteur et cardinal */ unsigned int i, taille; couple *vecteur = abr2vecteur (a); taille = cardinal (a); for (i = 0; i < taille; i++) afficher (vecteur[i]); } /* test ieme */ printf ("afficher le 10ieme\n"); afficher (abr_ieme (a, 10)); return EXIT_SUCCESS; }