《数据结构与算法分析——c语言描述》 练习6.32 答案
避免merge(H,H)
H2中没有树留下且Carry树为NULL，修改merge例程以终止合并
修改merge使得较少的树总被合并到较大的树中
.h
#ifndef _BinomialQueue_H
#define _BinomialQueue_H
typedef int ElementType;
struct BinNode;
typedef struct BinNode *BinTree;
typedef struct Collection *BinQueue;
BinQueue initialize(void);
ElementType findMin(BinQueue h);
int isEmpty(BinQueue h);
BinQueue merge(BinQueue &h1, BinQueue &h2);
void insert(ElementType X, BinQueue h);
BinQueue deleteMin(BinQueue h);
.cpp
#include"binomialqueue.h"
#include"fatal.h"
#define MAXTREES 25
#define CAPACITY ((1currentSize = 0;
<p>
return h;
}
ElementType findMin(BinQueue h) {
if (isEmpty(h))
Error("EMPTY HEAP");
ElementType minElem;
int i, j;
for (i = 0, j = 1; j currentSize; i++, j *= 2) {//找到第一个的二项树的根,j代表i二项树结点的个数，最大的二项树的下一个二项树的结点的个数比currentSize的最大值大1
if (h->theTrees[i] != NULL) {
minElem = h->theTrees[i]->element;
break;
}
}
for (; j currentSize; i++, j *= 2) {//再和剩下的比较
if (h->theTrees[i] && h->theTrees[i]->element < minElem) {
minElem = h->theTrees[i]->element;
}
}
return minElem;
}
int isEmpty(BinQueue h) {
return h->currentSize == 0;
}
static BinTree combineTrees(BinTree t1, BinTree t2) {
if (t1->element > t2->element)
return combineTrees(t2, t1);
else {
t2->nextSibling = t1->leftChild;//leftchild指向高度高的二项树，高度依次从nextSibling减少
t1->leftChild = t2;
return t1;
}
}
BinQueue merge(BinQueue &h1, BinQueue &h2) {//h2合并到h1当中
if (h1 == h2)
return h1;
BinTree t1, t2;
BinTree carry = NULL;
int carrt_tag;
if (h1->currentSize + h2->currentSize > CAPACITY)
Error("TOO MUCH ELEM");
if (h1->currentSize < h2->currentSize) {
//互换
BinQueue temp;
temp = h1;
h1 = h2;
h2 = temp;
}
h1->currentSize += h2->currentSize;
int h2Size = 0;
for (int i = 0, j = 1; j currentSize; i++, j *= 2) {//统计h2中树的数量
if (h2->theTrees[i] != NULL)
h2Size++;
}
for (int i = 0, j = 1; (carry || h2Size) && j currentSize; i++, j *= 2) {
t1 = h1->theTrees[i];
t2 = h2->theTrees[i];
if (carry)
carrt_tag = 1;
else
carrt_tag = 0;
switch (!!t1 + 2 * !!t2 + 4 * carrt_tag) {
case 0://t1,t2,carry空
break;
case 1://t1非空
break;
case 2://t2非空
h1->theTrees[i] = t2;
h2->theTrees[i] = NULL;
h2Size--;
break;
case 3://t1,t2非空
carry = combineTrees(t1, t2);
h1->theTrees[i] = NULL;
h2->theTrees[i] = NULL;
h2Size--;
break;
case 4://carry非空
h1->theTrees[i] = carry;
carry = NULL;
break;
case 5://t1,carry非空
carry = combineTrees(t1, carry);
h1->theTrees[i] = NULL;
break;
case 6://t2, carry非空
carry = combineTrees(t2, carry);
h2->theTrees[i] = NULL;
h2Size--;
break;
case 7:
h1->theTrees[i] = carry;
carry = combineTrees(t1, t2);
h2->theTrees[i] = NULL;
h2Size--;
break;
default:
Error("error");
break;
}
}
return h1;
}
void insert(ElementType X, BinQueue h) {
BinTree t1;
BinTree carry = (BinTree)malloc(sizeof(struct BinNode));
if (carry == NULL)
Error("EMPTY MEOERY");
carry->element = X;
carry->leftChild = carry->nextSibling = NULL;
int carrt_tag;
if (h->currentSize + 1 > CAPACITY)
Error("TOO MUCH ELEM");
h->currentSize += 1;
int i = 0;
while (carry != NULL) {
t1 = h->theTrees[i];
if (carry)
carrt_tag = 1;
else
carrt_tag = 0;
switch (!!t1 + 2 * !!carrt_tag) {
case 0://t1,t2,carry空
break;
case 1://t1非空
break;
case 2://carry非空
h->theTrees[i] = carry;
carry = NULL;
break;
case 3://t1,carry非空
carry = combineTrees(t1, carry);
h->theTrees[i] = NULL;
break;
default:
Error("error");
break;
}
i++;
}
}
BinQueue deleteMin(BinQueue h) {
if (isEmpty(h))
Error("EMPTY HEAP");
int minTree;
ElementType minElem;
int i, j;
for (i = 0, j = 1; j currentSize; i++, j *= 2) {
if (h->theTrees[i] != NULL) {
minElem = h->theTrees[i]->element;
minTree = i;
i++;
break;
}
}
for (; j currentSize; i++, j *= 2) {
if (h->theTrees[i] && h->theTrees[i]->element < minElem) {
minElem = h->theTrees[i]->element;
minTree = i;
}
}
BinQueue deleteQueue = initialize();
deleteQueue->currentSize = (1 leftChild;//高度从大到小
for (int i = minTree - 1; i >= 0; i--, p = p->nextSibling) {
deleteQueue->theTrees[i] = p;
}
free(h->theTrees[minTree]);
h->theTrees[minTree] = NULL;
h->currentSize -= (deleteQueue->currentSize + 1);
merge(h, deleteQueue);
free(deleteQueue);
return h;</p>
main.cpp
#include"binomialqueue.h"
#include
#include
#include"fatal.h"
int RandInt(int i, int j) {
int temp;
temp = (int)(i + (1.0*rand() / RAND_MAX)*(j - i));
return temp;
}
void getRandomInt(int *A, int n) {
for (int i = 0; i < n; i++) {
A[i] = i + 1;
}
for (int i = 1; i < n; i++) {
//std::swap(A[i], A[RandInt(0, i)]);
int randAdrr = RandInt(0, i);
int t = A[i];
A[i] = A[randAdrr];
A[randAdrr] = t;
}
}
int a[99999999];
int main() {
int n;
scanf("%d", &n);
//int *a = malloc(sizeof(int)*n);
//if (a == NULL)
// fprintf(stderr,"out of memory");
getRandomInt(a, n);
BinQueue h = initialize();
for (int i = 0; i < n; i++)
insert(a[i], h);
int cnt = 1;
for (int i = 0; i < n; i++) {
if (cnt == findMin(h))
cnt++;
h= deleteMin(h);
}
//destroy(h);
//free(a);
文章来源:https://blog.csdn.net/qq789045/article/details/51583771