fibheader.h

应用斐波纳契堆和邻接表改进单源最短路径算法

#include<iostream.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<iomanip.h>


template<class Type>
struct Element
{
	Type key;
	Type id;
};

template<class Type>
class FibonacciHeap;

///////////////////////////////堆节点定义///////////////////////////////////

template<class Type>
class FibonacciNode
{
	friend class Graph;
	friend class FibonacciHeap<Type>;
	private:
		Element<Type> data;
		FibonacciNode<Type>*child,*leftlink,*rightlink;
		FibonacciNode<Type> *parent;
		FibonacciNode()
		{
			child=parent=leftlink=rightlink=0;
		}
		bool ChildCut;
		int degree;
};


//////////////////////////////////堆定义/////////////////////////////////
template<class Type>
class FibonacciHeap
{
	public:
		FibonacciHeap(FibonacciNode<Type>*init=0)
		{
			min=init;
			Size=0;
		
		}

		void Insert(const Element<Type>&x);//插入数据
		
		Element<Type> *DeleteMin(Element<Type>&);//删除最小元素结点

		FibonacciNode<Type>* MinCombine(FibonacciNode<Type>*,FibonacciNode<Type>*);//合并环链

		void Minus(FibonacciNode<Type>*,int minus);//key值减少

		Element<Type>*Delete(FibonacciNode<Type>*);//删除任意元素结点
		void display36(FibonacciNode<Type>* p,int n);

	private:
		void CastcadingCut(FibonacciNode<Type>*);//瀑布修剪

		FibonacciNode<Type>* JoinMinTree(FibonacciNode<Type> *p,FibonacciNode<Type> *q);

		void Move(FibonacciNode<Type> *b);   //将b变作根结点
		FibonacciNode<Type>*min;
		void Display(FibonacciNode<Type>* root);	

		int Size;                                 //所有结点的个数
		int MaxDegree;
	
};





//////////////////////////////////插入///////////////////////////////////


template<class Type>
void FibonacciHeap<Type>::Insert(const Element<Type>&x)
{   
	FibonacciNode<Type>*p=new FibonacciNode<Type>;   
	p->data.key=x.key;
	p->data.id=x.id;//新建一个结点，存储数据          
	p->child=0;                                                  //初始化
	p->parent=0;
	p->degree=0;
	p->ChildCut=false;
	
	if(min==0)
	{
		min=p;
		min->rightlink=min->leftlink=p;
	}
	else
	{
		p->leftlink=min;
		p->rightlink=min->rightlink;
		min->rightlink->leftlink=p;
		min->rightlink=p;
	}

	if(min->data.key>p->data.key)
	min=p;

	Size++ ;                                            //插入一个结点，结点个数加一           

}

////////////////////////环链合并///////////////////////////////////////////
/////////////////////执行时有问题//////////////////////////////////////////
/////////////////////为避免错误，本函数在程序中没有调用///////////////////
template<class Type>               
FibonacciNode<Type>* FibonacciHeap<Type>::MinCombine(FibonacciNode<Type>* s,FibonacciNode<Type>* f)
{                                  //
	f->parent=0;
	for(FibonacciNode<Type>* a=f->rightlink;a!=f;a=a->rightlink)
	{
		a->parent=0;
	} 
	f->rightlink->leftlink=s;
	s->rightlink->leftlink=f;
	FibonacciNode<Type>* kk=s->rightlink;
	f->rightlink=s->rightlink;
	s->rightlink=kk;
	return s;
}


/////////////////////////////////key值减少///////////////////////////////////////

template<class Type>
void FibonacciHeap<Type>::Minus(FibonacciNode<Type>*b,int a)                    //将b的Key值减a
{
	b->data.key-=a;
	if(b->parent)                                 //b不是根结点,在进行移动操作时应将变作根结点的结点的parent置为0
	{
		if(b->data.key<b->parent->data.key)                  //b的Key值小于parent的key值 
		{
			Move(b);                                   //将b移到根链
			if(b->parent->ChildCut) //看是否要进行瀑布修剪，在瀑布修剪时再判断b->parent是否为根点
			{   
		       //b->parent->ChildCut=false;             //这时它将要变成根结点，ChildCut无意义，    
			   CastcadingCut(b->parent);               //b的父母是否为根结点在瀑布修剪时再进行判断
			}
			else
			{
				b->parent->ChildCut=true;               //原先为false
			}
		}
	}
	if(b->data.key<min->data.key)                       //最后对min进行赋值
	{
		min=b;
	}
}
/////////////////////////////////瀑布修剪/////////////////////////////////
template<class Type>
void FibonacciHeap<Type>::CastcadingCut(FibonacciNode<Type>*b)
{
	if(!b->parent)                             //为根结点,这样在前面执行Move时不需改变ChildCut
	{                                         
		return;
	}
    Move(b);                                   //将其移到根链 
	if(b->parent->ChildCut)
	{
		CastcadingCut(b->parent);                  //接着判断其父母 
	}
}

////////////////////////////////根节点归并////////////////////////////////////

template<class Type>
void FibonacciHeap<Type>::Move(FibonacciNode<Type> *b)                           //将b变作根结点
{
	if(!b->parent)                                  //先判断b是否为根结点，可省去
	{
		return;
	}
	b->leftlink->rightlink=b->rightlink;             //将其链接到根链
	b->rightlink->leftlink=b->leftlink;
	min->rightlink->leftlink=b;
	b->rightlink=min->rightlink;
	b->leftlink=min;
	min->rightlink=b;
	b->parent->degree--;                             //degree记录了结点的子女数 
	b->parent=0;                                     //这是必要的，通过这个可以判断其是否为根结点   
	return;
}
////////////////////////////////删除任意节点////////////////////////////////

template<class Type>
Element<Type>* FibonacciHeap<Type>::Delete(FibonacciNode<Type> *b)
{
	if(b==min)                                                 
	{
		Element<Type> x=b->data;
		return DeleteMin(x);
	}

	if(!b->parent)                        
	{
		b->leftlink->rightlink=b->rightlink;
	    b->rightlink->leftlink=b->leftlink;               
	}
	else
	{
		if(b==b->leftlink)                   //	b没有兄弟
		{
			b->parent->child=0;
		}
		else
		{
			if(b->parent->child==b)                 //使b的父母能链向其子女
			{
				b->parent->child=b->rightlink;
			}
			b->leftlink->rightlink=b->rightlink;           //将剩余的子女链起来
			b->rightlink->leftlink=b->leftlink; 
		}

		if(b->parent->ChildCut)                       //b->parent已经被删除一个子女,重复判断
		{
			CastcadingCut(b->parent);
		}
		else
		{
			b->parent->ChildCut=true;
		}
	}

     FibonacciNode<Type> *y=b->child;
	 if(y)
	 {
	/*	y->parent=0;                         //即MinCombine()
        for(FibonacciNode<Type>* a=y->rightlink;a!=y;a=a->rightlink)
		{
			a->parent=0;
		} 
		y->rightlink->leftlink=min;
		min->rightlink->leftlink=y;
		FibonacciNode<Type>* kk=min->rightlink;
		min->rightlink=y->rightlink;
		y->rightlink=kk ;*/
	 
	

min=MinCombine(min,y);                        //好像调用它min不变,MinCombine应该有返回值班室
	 }
	 Element<Type> r=b->data; 
	Size--;


	delete b;
	Element<Type>* rr=&r;
	return  rr;

}

//////////////////////////////////删除最小节点/////////////////////////////

template<class Type>
Element<Type>* FibonacciHeap<Type>::DeleteMin(Element<Type>&x)                   //删除最小结点
{

	if(!min)
	{
		cout<<"It's empty."<<endl;
		Size--;
		return 0;
	}

	x=min->data;
	FibonacciNode<Type> *d=min;
	FibonacciNode<Type> *y=min->child;
	FibonacciNode<Type> *s=y;
	FibonacciNode<Type> *xx=min->rightlink;
 	if(min==min->rightlink)    // don't have brothers
	{
		if(y)  //如果min有子女
		{
			min=y;
			do{
				y->parent=0;
				y=y->rightlink;
			}while(y!=s->leftlink);
			s->parent=0;
			delete d;
		}
		else
		{
			min=0;
			delete d;
		}
	}
	else                                           //have brothers
	{
		min->leftlink->rightlink=min->rightlink;                         
		min->rightlink->leftlink=min->leftlink;
		min=xx;

		if(y)               //如果min有子女
		{
			y->parent=0;
			for(FibonacciNode<Type>* a=y->rightlink;a!=y;a=a->rightlink)
			{
				a->parent=0;
			} 
			y->rightlink->leftlink=min;
			min->rightlink->leftlink=y;
			FibonacciNode<Type>* kk=min->rightlink;
			min->rightlink=y->rightlink; 
			y->rightlink=kk ;
		}
 		delete d;
	}
	
	Size--; 

	MaxDegree=int(log(Size)/log(1.618))+1;           

	FibonacciNode<Type>** Tree=new FibonacciNode<Type>*[MaxDegree];
    	 
	for(int v=0;v<MaxDegree;v++)
		Tree[v]=0;
    int d1=0;    
	//FibonacciNode<Type> *gt=min;
  	Tree[min->degree]=min;              //error

	FibonacciNode<Type> *ps=0;
	for(FibonacciNode<Type> *p=min->rightlink;p!=min;p=ps)//遍历每一个结点 
	{            ps=p->rightlink;
		for(d1=p->degree;Tree[d1];d1++)                       //若Tree[d]非空，则与p合并,然后将Tree[d]
		{                                               //清空，否则将p赋给Tree[d]
			p=JoinMinTree(p,Tree[d1]);
			Tree[d1]=0;
		}
        Tree[d1]=p;
	}
   	 

	int a=0;                                               //下面将数组链成链表 
	while(!Tree[a])
	{
		a++;
	}                                   

    FibonacciNode<Type>  *t1=Tree[a];
	min=Tree[a];					
	for(int i=a+1;i<MaxDegree;i++)                       
	{                                          
		if(Tree[i])
		{
			t1->rightlink=Tree[i];
			Tree[i]->leftlink=t1;
			if(min->data.key>Tree[i]->data.key)              //顺便确定最小结点
			{
				min=Tree[i];
			}              
	
		t1=Tree[i];  
		} 
	}

   	t1->rightlink=Tree[a];     
	Tree[a]->leftlink=t1;
	delete []Tree;
	
	return &x;
}

//////////////////////////////将两棵树合成一棵树/////////////////////////////
template<class Type>
FibonacciNode<Type>* FibonacciHeap<Type>::JoinMinTree(FibonacciNode<Type> *p,FibonacciNode<Type> *q)
{
	if(!q)                          //Tree[d1]可能为空，(若将上面的for循环改为while循环可以避免)
	{
		return p;
	}
    	if(p->data.key < q->data.key)     
	{
		if(!p->child)
		{		
			p->child=q;
			q->leftlink=q;
			q->rightlink=q;
		}
		else
		{
			if(p->degree==1)
			{			
				p->child->rightlink=q;
				p->child->leftlink=q;
				q->leftlink=p->child;
				q->rightlink=p->child;
			}
			else
			{
			    p->child->rightlink->leftlink=q;
			    q->rightlink=p->child->rightlink;
			    q->leftlink=p->child;
			    p->child->rightlink=q;
			}
		}
		p->parent=0;
		q->ChildCut=false;
		q->parent=p;                           //p成为q的父母，则p的子女个数加1
		p->degree++;			
	}
	else 
	{
		if(!q->child)
		{
			q->child=p;
			p->leftlink=p;
			p->rightlink=p;
		}
		else
		{
			if(q->degree==1)
			{		
				q->child->rightlink=p;
				q->child->leftlink=p;
				p->leftlink=q->child;
				p->rightlink=q->child;
			}
			else
			{				
		        q->child->rightlink->leftlink=p;
	        	p->rightlink=q->child->rightlink;
				p->leftlink=q->child;
		        q->child->rightlink=p;
			}
		}
		q->parent=0;
		p->ChildCut=false;
		p->parent=q;
		q->degree++;                          //q成为p的父母，则q的子女个数加1
	 	p=q;

	}
 	
      //Size--;                                 //两根结点合并，树的个数减1
	  return p;                         

}