From 3aff7aaa9de61a5f3430bd86960c4f9c4b958786 Mon Sep 17 00:00:00 2001 From: Pixel <> Date: Wed, 7 Mar 2001 00:41:50 +0000 Subject: Version finale pour les algos. --- doc/BHeap.doc.fr | 89 -------------------------------------------------------- 1 file changed, 89 deletions(-) delete mode 100644 doc/BHeap.doc.fr (limited to 'doc/BHeap.doc.fr') diff --git a/doc/BHeap.doc.fr b/doc/BHeap.doc.fr deleted file mode 100644 index 753ceee..0000000 --- a/doc/BHeap.doc.fr +++ /dev/null @@ -1,89 +0,0 @@ -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 . 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. -- cgit v1.2.3