File de priorité dynamique

Commenter

Contenu du snippet

File de priorité dynamique , avec les opérations de base.
FilePrioDyn(TYPE[],int); // le constructeur vide est désactivé
void ajouter(TYPE); // ajouter un element
bool fileVide(); // etat de la file, vide ou non
TYPE premier(); // retourne la valeur de la racine
TYPE reduire(); // enlève la racine, puis tamise
void tamiser(int); //organiser les élémeent du haut vers le bas
void percoler(int); // organiser les éléments du bas vers le haut
void construire(TYPE[],int); // construction de la file dynamique de priorité
bool getVide(); // accesseur en lecture de (bool vide)
void afficher(); // afficher la liste

Source / Exemple : 


#define TAILLE_MAX 524288
/**


  •  @author Mehdi El Masaodui

*


  • /

template <typename TYPE>
class FilePrioDyn{

    private:
    bool vide;
    int longueur;
    TYPE sommet;
    TYPE elements[TAILLE_MAX]; // éléments de la liste

    public:
    FilePrioDyn(TYPE[],int); // le constructeur vide est désactivé
    void ajouter(TYPE); // ajouter un element
    bool fileVide(); // etat de la file, vide ou non
    TYPE premier(); // retourne la valeur de la racine
    TYPE reduire(); // enlève la racine, puis tamise
    void tamiser(int); //organiser les élémeent du haut vers le bas
    void percoler(int); // organiser les éléments du bas vers le haut
    void construire(TYPE[],int); // construction de la file dynamique de priorité
    bool getVide(); // accesseur en lecture de (bool vide)
    void afficher(); // afficher la liste
};
/**


  •  @param TYPE temp : tableau à base duquel on va construire la file de priorité

  •  @param int taille : la taille du tableau, on la passe explicitement parceque on ne peut pas récuperer la taille du tableau sur l'objet tableau en C++

*


  • /

template <typename TYPE>
FilePrioDyn<TYPE>::FilePrioDyn(TYPE temp[],int taille){
    construire(temp,taille);
}
/**


  •  @return L'état de la liste , true : vide , false : non-vide

*


  • /


template <typename TYPE>
bool FilePrioDyn<TYPE>::fileVide(){
    return getVide();
}
/**


  •  @return L'état de la variable vide

*


  • /

template <typename TYPE>
bool FilePrioDyn<TYPE>::getVide(){
    return vide;
}

/**


  •  @return Le sommet de la file de priorité

  • /

template <typename TYPE>
TYPE FilePrioDyn<TYPE>::premier(){
    return elements[0];
}
/**


  •  @return l'élément qui a été supprimé

  •  @description retire un élément du sommet, réduit la taille de un et tamise

  • /


template <typename TYPE>
TYPE FilePrioDyn<TYPE>::reduire(){
    TYPE temp;
    if(!fileVide()){
        elements[0]=elements[longueur];
        longueur=longueur--;
        tamiser(0);
    }else{
        /* la file est vide, aucun élément à retirer*/
    }
    return temp;
}

/**


  •  @param val élément à ajouter à la fin

  •         percoler à partir de l'élement ajouté

  • /


template <typename TYPE>
void FilePrioDyn<TYPE>::ajouter(TYPE val){
    longueur++;
    elements[longueur]=val;
    percoler(val);
}

/**


  •  @param temp tableau à partir duquel on construit la file de priorité

  •  @param int taille taille du tableau

  •         on ajoute un élément à la fin à chaque itération, on percole après chaque élément ajouté

*


  • /

template <typename TYPE>
void FilePrioDyn<TYPE>::construire(TYPE temp[],int taille){
    longueur=taille;
    int i;
    if(longueur>0){
        i=0;
        while(i<longueur){
            elements[i]=temp[i];
            percoler(i);
            i++;
        }
    }

}

/**


  •  @param i , l'élémentt ajouté à partir duquel tamiser,

  •            on tamise vers la bas de la structure

*


  • /

template <typename TYPE>
void FilePrioDyn<TYPE>::tamiser(int i){

    int k=i;
    int j=0; /* correction */
    while(j!=k){
        j=k;
        if(2*j<longueur && elements[2*j]>elements[k]){
            k=2*j;
        }
        if(2*j<longueur && elements[2*j+1]>elements[k]){
            k=2*j+1;
        }
        elements[j]=elements[k];
    }
}

/**


  •  @int i element à partir duquel percoler

  •  percoler est le fait de parcourir la structure à partir du dernier élément ajouté

  •  pour verifier le principe de priorité ( ordre )

*


  • /

template <typename TYPE>
void FilePrioDyn<TYPE>::percoler(int i){
   int k=i;
   int j=0;
   while(j!=k){
       j=k;
       if(j>1 && elements[j/2]<elements[k]){
           k=j/2;
       }
       elements[j]=elements[k];
   }
}

/**


  •  Affichage de la liste sous forme d'un arbre

  • /

template <typename TYPE>
void FilePrioDyn<TYPE>::afficher(){
    int i=0;
    while(elements[i]){
    std::cout<<"|Element "<<i<<" : "<<elements[i]<<"";
    i++;
    }
}

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (mehdi7604)