blob: 753ceeeec3c37bdf41593bec136d46eb6ed82bac (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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.
|
