二项堆Binomial Queues
程序员文章站
2022-06-02 20:29:53
...
二项堆的具体实现代码:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct BinNode *Position;
typedef struct BinNode *BinTree;
typedef struct Collection *BinQueue;
struct BinNode
{
int Element;
Position LeftChild;
Position Sibling;
}BINNODE;
struct Collection
{
int CurrentSize;
BinTree TheTrees[100];
}COLLECTION;
BinTree CombineTrees(BinTree T1,BinTree T2);
BinQueue Merge(BinQueue H1, BinQueue H2);
void print(BinTree T);
int main()
{
char initial[100];
BinQueue heap=NULL, temp=NULL;
int i=0,j=0;
int N=0;
scanf("%s",initial);
heap=(BinQueue)malloc(sizeof(COLLECTION));
heap->CurrentSize=1;
for(i=0;i<100;i++)
{
heap->TheTrees[i]=NULL;
}
heap->TheTrees[0] = (BinTree)malloc(sizeof(struct BinNode));//从第0个开始建树//
heap->TheTrees[0]->Element=initial[0]-'0';//放入第一个数据并自动转化成整数型//
heap->TheTrees[0]->LeftChild = NULL;
heap->TheTrees[0]->Sibling = NULL;
j=2;//因为第一个数放进去了,所以从第二个数开始//
while(initial[j]!=','&&initial[j]!='\n'&&initial[j]!='\0')
{
temp=(BinQueue)malloc(sizeof(COLLECTION));//临时建立另一个指针数组//
temp->CurrentSize=1;
for(i=0;i<99;i++)
{
temp->TheTrees[i]=NULL;//记得全部初始化否则在不同的运行环境下会出现不同的错误//
}
temp->TheTrees[0] = (BinTree)malloc(sizeof(struct BinNode));//分配内存//
temp->TheTrees[0]->Element=initial[j]-'0';//从第二个数开始//
temp->TheTrees[0]->LeftChild = NULL;
temp->TheTrees[0]->Sibling = NULL;
heap = Merge(heap,temp);//合并//
j=j+2;//在这里我们的测试数据都是个位数所以直接移动到后第二个即可//
}
scanf("%d",&N);
if(N>=heap->CurrentSize)
{
printf("0,");
}
else if (heap->TheTrees[N]==NULL)
{
printf("0,");
}
else
{
print(heap->TheTrees[N]);
}
}
void print(BinTree T)
{
if(T!=NULL)
{
printf("%d,",T->Element);
if(T->LeftChild!=NULL)
{
if(T->LeftChild->Sibling!=NULL)
{
printf("%d,",T->LeftChild->Sibling->Element);
}
print(T->LeftChild);
}
}
}
BinTree CombineTrees(BinTree T1,BinTree T2)
{
if(T1==NULL)
{
return T2;
}
if(T2==NULL)
{
return T1;
}
if(T1->Element>T2->Element)
{
return CombineTrees(T2,T1);
}
T2->Sibling = T1->LeftChild;
T1->LeftChild = T2;
return T1;
}
BinQueue Merge(BinQueue H1,BinQueue H2 )
{
BinTree T1, T2, Carry = NULL;
int i, j;
H1->CurrentSize += H2-> CurrentSize;
for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 )
{
T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; /*current trees */
switch( 4*!!Carry + 2*!!T2 + !!T1 )
{
case 0: /* 000 */
case 1: /* 001 */
{
break;
}
case 2: /* 010 */
{
H1->TheTrees[i] = T2;
H2->TheTrees[i] = NULL;
break;
}
case 3: /* 011 */
{
Carry = CombineTrees( T1, T2 );
H1->TheTrees[i] =NULL;
H2->TheTrees[i] = NULL;
break;
}
case 4: /* 100 */
{
H1->TheTrees[i] = Carry;
Carry = NULL;
break;
}
case 5: /* 101 */
{
Carry = CombineTrees( T1, Carry );
H1->TheTrees[i] = NULL;
break;
}
case 6: /* 110 */
{
Carry = CombineTrees( T2, Carry );
H2->TheTrees[i] = NULL;
break;
}
case 7: /* 111 */
{
H1->TheTrees[i] = Carry;
Carry = CombineTrees( T1, T2 );
H2->TheTrees[i] = NULL;
break;
}
}
}
return H1;
}
推荐阅读