试实现贝努里队列类
【解】贝努里队列和其他的优先级队列的实现有些不同。它不是用一棵树来表示而是用一个森
林来表示。在贝努里队列的实现中,我们可以借助于第
5
章中实现的
tree
类。用
tree
类的对
象保存贝努里树。保存一个贝努里队列就是保存一个树根的数组。数组的
0
号单元存储
B0
的
根结点的地址,
1
号单元存储
B1
的根结点的地址,以此类推。贝努里队列的公有行为是优
先级队列的行为,再加上归并优先级队列。贝努里队列类的定义见代码清单
6-18
。
代码清单
6-18
贝努里队列类的定义
1. template <class T>
2. class Binomial {
3. tree<T>::node **forest; // 存放贝努里森林中的每棵树的树根的数组
4. int noOfTree; // 数组规模
5.
6. tree<T>::node *merge(tree<T>::node *t1,tree<T>::node *t2);//归并贝努里树
7. int findmin(); // 找出根结点值最小的树
8. void deleteTree(tree<T>::node *rt) { // 释放以 rt 为根的树的空间
9. tree<T>::node *son = rt->son, *t;
10. while (son != NULL) {
11. t = son;
12. son = son->brother;
13. deleteTree(t);
14. }
15. delete rt;
16. }
17.
18. public:
19. Binomial(int n = 100) // n 是队列中预计元素个数
20. { noOfTree = int (log(n) / log(2)) + 1; // 计算所需的贝努里树的阶数
21. forest = new tree<T>::node*[noOfTree];
22. for (int i = 0; i < noOfTree; ++i) forest[i] = NULL;
23. }
24.
25. ~Binomial()
26. { for (int i =0 ; i < noOfTree; ++i) // 删除每一棵树
27. if (forest[i] != NULL) deleteTree(forest[i]);
28. delete [] forest; // 删除存储树根的数组
29. }
30. void enQueue(T x);
31. T deQueue();
32. bool isEmpty();
33. T getHead();
34. void merge(Binomial &other);
35. };