list.h

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

/////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////CLASS LIST//////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////

template <class Type> class List;
class Node{
	friend class Graph;		
public:
	Node(){Id=Length=0;};
	Node(const int v,const int length){
		Id=v;
		Length=length;
	};
private:
	int Id;
	int Length;
};

///////////////////////////////////////////////////////////////////////////////////////////
///////////////////LISTNODEDEFINE//////////////////////////////////////////////////////////
template <class Type>
class ListNode{
	friend class List;
	friend class Graph;
private:
	Type Data;
public:
	ListNode *link;
	ListNode(){link=0;};
	ListNode(const int v,const int length):Data(v,length){link=0;};
};

//////////////////////////////////////////////////////////////////////////////////
////////////////////////////LISTDEFINE/////////////////////////////////////////////
template <class Type>
class List
{
	friend class Graph;
public:
	List(){
		first=0;
	first=NULL;
	};
	void Insert(const int v,const int length);
	~List();
private:
	ListNode<Type> *first;
};

////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////INSERT///////////////////////////////////////////////
template <class Type>
void List<Type>::Insert(const int v,const int length)
{
	ListNode<Type> *p=new ListNode<Type>(v,length);
	ListNode<Type> *ps=first;
	first=p;
	p->link=ps;
	p=ps=0;
}
/////////////////////////////////////////////////////////////////////////////////////
template <class Type>
List<Type>::~List()
{
	ListNode<Type> *ps=0;
	for(ListNode<Type> *p=first;p;p=ps)
	{   
		ps=p->link;
		delete p;
	}
}