【3】 source code and printing results3.1）source code at a glance Attention）二项队列的实现源代码用到了 儿子兄弟表示法；
[url=][/url]
#include "binominal_queue.h" #define MINIMAL 10000int minimal(BinominalQueue bq){ int capacity; int i; int minimal; int miniIndex; minimal = MINIMAL; capacity = bq->capacity; for(i=0; i<capacity; i++) { if(bq->trees && bq->trees->value < minimal) { minimal = bq->trees->value; miniIndex = i; } } return miniIndex;}// initialize the BinominalQueue with given capacity.BinominalQueue init(int capacity){ BinominalQueue queue; BinominalTree* trees; int i; queue = (BinominalQueue)malloc(sizeof(struct BinominalQueue)); if(!queue) { Error("failed init, for out of space !"); return queue; } queue->capacity = capacity; trees = (BinominalTree*)malloc(capacity * sizeof(BinominalTree)); if(!trees) { Error("failed init, for out of space !"); return NULL; } queue->trees = trees; for(i=0; i<capacity; i++) { queue->trees = NULL; } return queue;} // attention: the root must be the left child of the binominal tree.int getHeight(BinominalTree root){ int height; if(root == NULL) { return 0; } height = 1; while(root->nextSibling) { height++; root = root->nextSibling; } return height;}// merge BinominalQueue bq2 into bq1.void outerMerge(BinominalQueue bq1, BinominalQueue bq2){ int height; int i; for(i=0; i<bq2->capacity; i++) { height = -1; if(bq2->trees) { height = getHeight(bq2->trees->leftChild); // attention for the line above // height = height(bq2->trees->leftChild); not height = height(bq2->trees); merge(bq2->trees, height, bq1); } } }// merge tree h1 and h2 = bq->trees[height], // who represents the new tree and old one respectively.BinominalTree merge(BinominalTree h1, int height, BinominalQueue bq){ if(h1 == NULL) { return h1; } if(bq->trees[height] == NULL) // if the queue don't has the B0 tree. { bq->trees[height] = h1; return bq->trees[height]; } else // otherwise, compare the new tree's height with that of old one. { if(h1->value > bq->trees[height]->value) // the new should be treated as the parent of the old. { innerMerge(bq->trees[height], height, h1, bq); } else // the old should be treated as the parent of the new. { innerMerge(h1, height, bq->trees[height], bq); } } return h1;} BinominalTree lastChild(BinominalTree root){ while(root->nextSibling) { root = root->nextSibling; } return root; }
[/url]