Projet ZZ1 : Labyrinthe

Partition

Implémentation

Nous avons implémenter une partition pour pouvoir regrouper des éléments dans des paquets :

  • L'Implémentation sera sous forme arborescente, stocké dans un tableau
  • L'arbre devra permettre de remonter d'un nœud vers la racine
  • La hauteur d'un arbre devra être minimale
  • Le parent d'une racine est elle même

    • Structure de données

    Pour limiter les temps de traitement, on choisit d'implémenter la partition comme ceci :


    typedef struct partition {
        int size;
        element_t *data;
        bool *class;
        int *heights;
    } partition_t;

        int size;
    La taille de la partition
         element_t *data;
    Le taleau contenant le numéro du parent de i
         bool *class;
    Le tableau de booléen disant si i est une racine
         int *heights;
    Le tableau des tailles des arbres, pertinant pour les racines uniquement

    Fonctions

  • En premier lieu, la fonction de création de tas :

    •     partition_t partitionCreer(int size);

    Cette fonction initialise la partition avec N racines de hauteur 1. Nous sommes obligés de partir de cette configuration pour pouvoir obtenir toutes les partitions possible. En effet, nous ne disposons que de l'opération fusion.


  • Puis la fonction pour récupérer le numéro de la classe d'un élément

    •     identifier_t partitionRecupererClasse(partition_t *p, element_t x);

    Cette fonction remonte l'arbre depuis l'élément cherché jusqu'à arriver à la racine, puis il renvoit son identifiant.

    Compléxité : Θ(log(N))


  • La fonction pour fusionner 2 éléments entre eux

    •     void partitionFusion(partition_t *p, element_t x, element_t y);

    Cette fonction fusionne 2 éléments de la partition entre s'ils ne sont pas déjà dans la même partition. La fusion se fait de manière à garder la hauteur de l'arbre la plus petite possible. La hauteur de l'arbre résultant de la fusion est au pire de hauteur MAX(taille arbre premier élément + 1, taille arbre deuxième élément).

    Compléxité : Θ(log(N))


  • La fonction pour lister tous les éléments d'une classe de la partition

    •     element_t *partitionListerClasse(partition_t *p, identifier_t id);

    Pour chaque élément de la partition, on regarde s'il appartient à la classe.

    Compléxité : Θ(N x log(N))


  • La fonction pour lister toutes les classes de la partition

    •     bool *partitionListerPartition(partition_t *p);

    Retourne simplement le tableau class de la partition.

    Compléxité : Θ(1)


    Affichage avec graphviz

    Petit exemple d'une partition avec 10 éléments :


    Fusion de : 3 6

    Fusion de : 5 3

    Fusion de : 6 2

    Fusion de : 1 2

    Fusion de : 0 9

    Fusion de : 6 0

    Fusion de : 8 7

    Fusion de : 3 7