File de priorité dynamique

Soyez le premier à donner votre avis sur cette source.

Snippet vu 30 941 fois - Téléchargée 19 fois

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

Ajouter un commentaire Commentaire
Messages postés
13
Date d'inscription
lundi 10 octobre 2005
Statut
Membre
Dernière intervention
11 août 2008

Ben, c'est juste que j'ai regardé en vitesse le code et j'ai trouvé des trucs bizarres...

1) Dans ajouter(), tu incrémentes le compteur avant d'ajouter l'élément. C'est bizarre :
On imagine qu'il y ait n éléments, on a donc des objets aux indices compris entre 0 et n-1.
Tu incrémentes d'abord longeur (qui est alors égal à n+1) et tu ajoutes l'objet à cet indice.
Il n'y a donc rien entre (n-1) et (n+1).

2) Dans retirer(), si la file est vide, tu renvoies une valeur qui n'a pas été initialisée (sauf cas de constructeur par défaut)...

3) Dans tamiser() et percoler(), tu utilises une variable j qui n'a pas été initialisée non plus.

4) A aucun moment, tu n'initialises la variable vide...

5) Dans afficher(), tu n'incrémentes jamais le compteur i. On a une boucle infinie...

Je ne sais pas pour quel langage c'est écrit mais en C++, les variables non initialisées, ça ne pardonne pas...

Voilà.
C'est pour être constructif que je dis ça.
J'espère avoir pu aider.

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.