欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二项堆Binomial Queues

程序员文章站 2022-06-02 20:29:53
...

二项堆Binomial Queues
二项堆Binomial Queues

二项堆的具体实现代码:

#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;
}

相关标签: c#