diff options
Diffstat (limited to 'lib/BHeap.cc')
| -rw-r--r-- | lib/BHeap.cc | 159 |
1 files changed, 153 insertions, 6 deletions
diff --git a/lib/BHeap.cc b/lib/BHeap.cc index 4d7cc9e..ef4bd04 100644 --- a/lib/BHeap.cc +++ b/lib/BHeap.cc @@ -3,8 +3,52 @@ #include "BHeap.h" #include "CList.h" +/**********************************\ +* * +* Tas binomial * +* * +\**********************************/ + +/* + * + * Le tas binomial implémenté suit exactement les algorithmes présentés dans + * le livre "Introduction à l'algorithmique". La structure est récursive et + * les données de l'entête sont réparties comme suit: + * - Degree = -1 (pour signaler que nous somme dans l'entête) + * - Key contient le nombre d'éléments enregistrés + * - Brother est le pointeur sur le premier élément du tas + * + */ + static int d, Depths[65536]; + +/* + * Cette fonction sert à afficher le contenu du tas binomial sur le stream + * passé en argument. L'affichage sera structuré de sorte à ressembler aux + * diagrammes présentés dans le livre "Introduction à l'algorithmique", à + * ceci près qu'ils sont présentés à la verticale. Exemple: + * + * * Head cell. + * | + * |__ 6 + * |_ 15 + * | |__ 18 + * |_ 5 + * | |_ 10 + * | | |__ 29 + * | |__ 9 + * |_ 2 + * |_ 3 + * | |_ 16 + * | | |__ 23 + * | |__ 17 + * |_ 11 + * | |__ 25 + * |__ 14 + * + */ + void BHeap::Dump(ostream & os) { int i; @@ -30,6 +74,12 @@ void BHeap::Dump(ostream & os) } } + + /* + * Cette fonction est utilisée dans les tests "paranoïaques" pour compter + * le nombre véritable de cellules lors d'un parcours récursif. + */ + int BHeap::rn(void) { int n = 0; @@ -46,6 +96,11 @@ int BHeap::rn(void) return n; } + + /* + * Implémentation directe de la primitive LIEN-BINOMIAL(y, z) avec y = this. + */ + void BHeap::Link(BHeap * z) { Father = z; @@ -54,6 +109,15 @@ void BHeap::Link(BHeap * z) z->Degree = z->Degree + 1; } + + /* + * Implémentation de la primitive FUSIONNER-TAS-BINOMIAUX(T1, T2) avec T1 = this. + * L'algorithme a du être inventer car il n'est pas présenté dans le livre. + * Par contre, il s'inspire fortement de l'algorithme "Fusion" pour le + * tri-fusion. De plus, contrairement aux indication du livre, T2 sera rajouté + * APRES T1, et aucun tas binaire nouveau ne sera créé. + */ + void BHeap::Merge(BHeap * H) { BHeap *P1, *P2, *T1, *T2; @@ -78,21 +142,38 @@ void BHeap::Merge(BHeap * H) H->Brother = NULL; } -BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL), -FP(new CList) + + /* + * Constructeur d'un tas binomial. + */ + +BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL), FP(new CList) { - type = T_BHEAP; + type = T_BHEAP; } + + /* + * Constructeur interne. La structure est récursive, donc nous implémentons + * un constructeur privé. + */ + BHeap::BHeap(Key_t IKey, Datas_t const &IDatas):PriorityList(IKey, IDatas), Degree(0), Father(NULL), Child(NULL), Brother(NULL) { - type = T_BHEAP; + type = T_BHEAP; #ifdef DEBUG nc++; #endif } + + /* + * Le destructeur. S'il est appelé sur l'entête, nous effacons récursivement + * la liste des pointeurs intermédiaires, ainsi que tout le tas + * récursivement (voir rapport). + */ + BHeap::~BHeap(void) { if (Degree == -1) @@ -109,6 +190,11 @@ BHeap::~BHeap(void) #endif } + + /* + * Implémentation directe de l'algorithme MINIMUM-TAS-BINOMIAL(T) avec T = this. + */ + Cell BHeap::Min(void) { BHeap *x = this, *y = NULL; @@ -124,6 +210,12 @@ Cell BHeap::Min(void) return y->FP; } + + /* + * Insertion d'une cellule déjà créé dans le tas. + * La routine fonctionne comme dans l'algorithme conseillé. + */ + Cell BHeap::Insert(BHeap * E) { BHeap *H; @@ -139,6 +231,11 @@ Cell BHeap::Insert(BHeap * E) return ((E->FP = ((CList *) (FP->Insert(Key, E))))); } + + /* + * Insertion d'un couple (Clef, Données) dans le tas. + */ + Cell BHeap::Insert(Key_t IKey, Datas_t const &IDatas) { BHeap *P; @@ -150,6 +247,15 @@ Cell BHeap::Insert(Key_t IKey, Datas_t const &IDatas) return (Insert(P)); } + + /* + * Implémentation de l'algorithme TAS-BINOMIAL-EXTRAIRE-MIN(T) avec T = this. + * La clef extraite sera renvoyée et les données satellites seront écrites dans + * la variable Datas. L'implémentation est beaucoup plus longue que + * l'algorithme de quatre lignes présenté dans le livre mais il s'agit de la + * traduction entre les phrases en français présentées et le langage C. + */ + Key_t BHeap::Extract_Min(Datas_t & Datas) { BHeap *x, *y = NULL, *P, *P2, *P3, *Before; @@ -163,6 +269,8 @@ Key_t BHeap::Extract_Min(Datas_t & Datas) Key--; + // 1. Trouver la racine x de clé minimum dans la liste des racines de T... + for (x = Brother; x; x = x->Brother) { if ((x->Key < min)) { min = x->Key; @@ -172,10 +280,14 @@ Key_t BHeap::Extract_Min(Datas_t & Datas) P = x; } + // ... et supprimer x. Before->Brother = y->Brother; + // 2. T' <- CREER-TAS-BINOMIAL Before = new BHeap; + // 3. inverser l'ordre de la liste chaînée des fils de x, + // et faire pointer tête[T'] sur la tête de la liste résultante. for (P = y->Child; P;) { P2 = Before->Brother; P3 = P->Brother; @@ -184,9 +296,11 @@ Key_t BHeap::Extract_Min(Datas_t & Datas) P = P3; } + // 4. T <- UNION-TAS-BINOMIAUX(T, T') Before->Key = 0; Union(Before); + // 5. retourner x (et l'effacer) k = y->Key; y->Brother = y->Child = NULL; FP->Delete(Datas, ((Cell) y->FP)); @@ -196,6 +310,11 @@ Key_t BHeap::Extract_Min(Datas_t & Datas) return k; } + + /* + * Implémentation directe de l'algorithme UNION-TAS-BINOMIAUX(T1, T2) avec T1 = this. + */ + PriorityList *BHeap::Union(PriorityList * P) { BHeap *x, *Before, *After; @@ -231,6 +350,13 @@ PriorityList *BHeap::Union(PriorityList * P) return this; } + + /* + * Implémentation de l'algorithme TAS-BINOMIAL-DIMINUER-CLE(T,x,k) avec T = this. + * L'implémentation de cette routine a nécessité le rajout d'une table de pointeurs + * pour conserver une structure correcte (voir rapport) + */ + bool BHeap::Lower_Key(Cell x, Key_t NKey) { BHeap *y, *z, *tx = ((BHeap *) ((CList *) x)->Datas); @@ -239,8 +365,7 @@ bool BHeap::Lower_Key(Cell x, Key_t NKey) return false; tx->Key = NKey; - for (y = tx, z = tx->Father; z && (y->Key < z->Key); - y = z, z = y->Father) { + for (y = tx, z = tx->Father; z && (y->Key < z->Key); y = z, z = y->Father) { SWAP(y->Datas, z->Datas); SWAP(y->Key, z->Key); SWAP(y->FP, z->FP); @@ -250,6 +375,13 @@ bool BHeap::Lower_Key(Cell x, Key_t NKey) return true; } + + /* + * Implémentation directe de l'algorithme TAS-BINOMIAL-SUPPRIMER(T,x) avec T = this. + * La valeur de la clef supprimée est renvoyée par la routine et les données satellites + * sont écrites dans la variable Datas. + */ + Key_t BHeap::Delete(Datas_t & Datas, Cell x) { Key_t K; @@ -262,16 +394,31 @@ Key_t BHeap::Delete(Datas_t & Datas, Cell x) return K; } + + /* + * Booléen qui détermine si le tas est vide ou pas. + */ + bool BHeap::IsEmpty(void) { return (!(Brother)); } + + /* + * Lit la clef d'une cellule d'un tas. + */ + Key_t BHeap::ReadKey(Cell C) { return ((BHeap *) ((CList *) C)->Datas)->Key; } + + /* + * Lit les données d'une cellule d'un tas. + */ + Datas_t BHeap::ReadDatas(Cell C) { return ((BHeap *) ((CList *) C)->Datas)->Datas; |