diff options
Diffstat (limited to 'doc')
-rw-r--r-- | doc/BHeap.doc.fr | 89 | ||||
-rw-r--r-- | doc/Makefile.am | 1 |
2 files changed, 90 insertions, 0 deletions
diff --git a/doc/BHeap.doc.fr b/doc/BHeap.doc.fr new file mode 100644 index 0000000..753ceee --- /dev/null +++ b/doc/BHeap.doc.fr @@ -0,0 +1,89 @@ +BHeap: (tas binomial) +----- + + Impl�mentation: + ~~~~~~~~~~~~~~ +Ce code utilisant les classes, il ne peut marcher qu'en C++. +Le tas binomial est une classe d�riv�e de la classe 'PriorityList'. +Toutes les m�thodes �tant virtuelles, vous pouvez sans probl�me assigner +un BHeap � une PriorityList et appeler les m�thodes classiques de la liste +de priorit�. + + + Utilisation: + ~~~~~~~~~~~ +Pour creer un tas binomial vide, il suffit de faire: + +BHeap * Tas = new BHeap; + +Il n'y a aucune variable de la structure BHeap lisible directement. Tout +s'effectue par des appels aux m�thodes de la classe. + +Les donn�es satellites sont dispos�es dans la structure sous la forme d'un +pointeur du type void. Le type des donn�es est d�finit par le typedef 'Datas_t'. +Le type des clefs est d�finit par le typedef 'Key_t'. Par d�faut, ceux-ci sont: + +typedef Datas_t void * +typedef Key_t int + +Vous pouvez changer ces typedefs avant de faire un #include <PCommon.h>. Le type +changera alors automatiquement dans la compilation de la librairie. Attention: +cela ne marchera bien �videmment qu'en compilation statique (c'est � dire avec +le package PriorityList dans votre arbre de d�veloppement) et le type Key_t doit +�tre un type 'comparable' (afin de faire les tests sur les clefs). Il est n�anmoins +vivement conseill� de conserver les types de bases. + +Il n'y a aucun moyen direct de 'renverser' l'ordre de la liste (c'est � dire +faire du plus grand au plus petit). Il vous suffit de faire des insertions sur +les valeurs n�gatives des clefs r�elles � ins�rer. + +Voici les m�thodes disponibles: + + BHeap::BHeap(void); + BHeap::~BHeap(void); + + Key_t PriorityList::ReadKey(void); + Datas_t PriorityList::ReadDatas(void); + + void BHeap::Dump(void); + + BHeap * BHeap::Min(void); + BHeap * BHeap::Insert(Key_t IKey, Datas_t IDatas); + Key_t BHeap::Extract_Min(Datas_t & Datas); + BHeap * BHeap::Union(PriorityList * H); + int BHeap::Lower_Key(Key_t NKey); + Key_t BHeap::Delete(Datas_t & Datas, PriorityList * x); + +Le constructeur est le constructeur 'tas vide'. Le +destructeur ne peut que servir a d�truire un tas complet. + +Les deux m�thodes PriorityList::ReadKey et PriorityList::ReadDatas servent a lire +les donn�es de la structure. Elles sont directement d�riv�es de PriorityList. + +La m�thode BHeap::Min recherche la clef minimum de la structure et en renvoie +le pointeur correspondant. Elle s'utilise sur le tas dans lequel on recherche. + +La m�thode BHeap::Insert va inserer une nouvelle clef dans le tas sur lequel +on a appel� la m�thode. + +La m�thode BHeap:Extract_Min va rechercher et supprimer le minimum dans le tas +sur lequel elle a �t� appel�e. Elle renvoie la clef minimum. Les +donn�es satellite sont �crites dans la variable Datas pass�e en param�tre. + +La m�thode BHeap::Union va vider compl�tement le tas pass� en param�tre pour +effectuer l'op�ration Union avec le tas sur lequel la m�thode a �t� appel�e. + +La m�thode BHeap::Lower_Key va diminuer la valeur de la clef de la cellule sur +laquelle la m�thode a �t� appel�e. + +Enfin la m�thode BHeap::Delete va effacer la clef pass�e en param�tre depuis le +tas sur lequel la m�thode a �t� appel�e. Elle va renvoyer la valeur de la clef +supprim�e et les donn�es satellites sont �crites dans la variable Datas. + + + Pr�cautions: + ~~~~~~~~~~~ +Il ne faut *jamais* supprimer une clef directement avec la fonction C++ +delete. Il faut toujours utiliser la m�thode BHeap::Delete(). Par contre +pour effacer l'int�gralit� d'un tas, il suffit de faire delete Tas, et +l'ensemble des clefs seront effac�es tr�s rapidement. diff --git a/doc/Makefile.am b/doc/Makefile.am new file mode 100644 index 0000000..2ddd071 --- /dev/null +++ b/doc/Makefile.am @@ -0,0 +1 @@ +EXTRA_DIST = BHeap.doc.fr
\ No newline at end of file |