duidui分支限介未完成.cpp

用c++实现一个堆

#include <iostream.h>
class traveling
{ 
	friend void main(void);
public:
	int BBTSP();
private:
	int n;
	int a[100][100],
		noedge,
		cc,
		bestc;
};
template <class type> class minheap
{
 public:
	     minheap(int maxsize);
	     minheap(type arr[],int n);
    	~minheap(){delete [] heap;}
    	 const minheap <type> &operator=(const minheap &r);
    	int insert(const type &x);
    	int removemin(type &x);
    	int isempty() const{return currentsize==0;}
    	int isfull() const{return currentsize==maxheapsize;}
    	void makeempty(){current=0;}
		type *heap;
 private:
		enum{defaultsize=10};
		
		int currentsize;
		int maxheapsize;
		void filterdown(int i,int m);
		void filterup(int i);
};
class minheapnode
{
	friend traveling;
	friend minheap ;
public:
	int lcost;
private:
	int cc,
		rcost,
		s,
		*x;
};
template <class type> minheap<type>::minheap(int maxsize)
{
	maxheapsize=defaultsize<maxsize?maxsize:defaultsize;
	heap=new type [maxheapsize];
	currentsize=0;
}
template <class type>void minheap<type>::filterdown(const int start,const int endofheap)
{
   int i=start,j=2*i;type temp=heap[i];
   while(j<=endofheap)
   {
	   if(j<=endofheap)&&heap[j].lcost>heap[j+1].lcost) j++;
	   if(temp.lcost<=heap[j].lcost) break;
	   else{heap[i]=heap[j];i=j;j=2*j+1;}
   }
   heap[i]=temp;
}
template <class type> void minheap<type>::filterup(int start)
{
	int j=start,i=(j-1)/2; type temp=heap[j];
	while(j>0)
	{
		if(heap[i].lcost<=temp.lcost) break;
		else{ heap[j]=heap[i];j=i;i=(i-1)/2;}
	}
	heap[j]=temp;
}
template <class type> int minheap<type>::insert(const type &x)
{
	if(currentsize==maxheapsize){cerr<<"heap full"<<endl;return 0;}
	heap[currentsize]=x;filterup(currentsize);
	currentsize++;
	return 1;
}
template <class type> int minheap<type>::removemin(type &x)
{
	if(!current){cour<<"heap empty"<<endl;return 0;}
	x=heap[0];heap[0]=heap[currentsize-1];
	currentsize--;
	filterdown(0,currentsize-1);
	return 1;
}
template <class type> const minheap <type> & minheap<type>::operator=(const minheap &r)
{
	type key;
	key.lcost=r.lcost;
	key.cc=r.cc;
	key.rcost=r.rcost;
	key.s=r.s;
	key.x=r.x;
	return key;                        
}
traveling::BBTSP()
{
	minheap<minheapnode> h(1000);
	int *minout=new int[n+1];
	int minsum=0;
	for(int i=1;i<=n;i++)
	{
		int min=noedge;
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]!=noedge&&
				(a[i][j]<min||min==noedge))
				min=a[i][j];
		}
		if(min==noedge) return noedge;//无回路
		minout[i]=min;
		minsum+=min;
	}
//初始化
	minheapnode E;
	E.x =new int[n];
	for(int ii=0;ii<=n;ii++)
		E.x[ii]=ii+1;
	E.s=0;
	E.cc=0;
	E.rcost=minsum;
	int bestc=noedge;/////////////////
//搜索排列树空间
	while(E.s<n-1)
	{
		if(E.s==n-2)
		{
			if(a[E.x[n-2]][E.x[n-1]]!=noedge&&
				a[E.x[n-1]][1]!=noedge&&(E.cc+
				a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]
				<bestc||bestc==noedge))
			{
				bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1];
				E.cc=bestc;
				E.lcost=bestc;
				E.s++;
				h.insert(E);
			}
			else {cout<<E.x[0]<<E.x[1];delete[] E.x;}
		}
		else
		{
			for(int i=E.s+1;i<n;i++)
				if(a[E.x[E.s]][E.x[i]]!=noedge)
				{
					int cc=E.cc+a[E.x[E.s]][E.x[i]];
					int rcost=E.rcost-minout[E.x[E.s]];
					int b=cc+rcost;
					if(b<bestc||bestc==noedge)
					{
						minheapnode N;
						N.x=new int[n];
						for(int jj=0;jj<n;jj++)
							N.x[jj]=E.x[jj];
						N.x[E.s+1]=E.x[i];
						N.x[i]=E.x[E.s+1];
						N.cc=cc;
						N.s=E.s+1;
						N.lcost=b;
						N.rcost=rcost;
						h.insert(N);
					}
				}
				delete[] E.x;
		}
		E=h.heap[0];
	}
	if(bestc==noedge) return noedge;
	//for(int iii=0;iii<=n;iii++)
	//	v[iii+1]=E.x[iii];
	//{cout<<E.x[iii]<<"  ";}
	
//	while(true)
//	{
//		delete[] E.x;
//	}
	return bestc;
}
void main()
{
	traveling T;
	cout<<"plealse input relexe number!!"<<endl;
	cin>>T.n;cin>>T.noedge;cin>>T.cc;cin>>T.bestc;
	cout<<"请输入邻接距阵!!"<<endl;
	for(int i=1;i<=T.n;i++)
	{
		for(int j=1;j<=T.n;j++)
		{cin>>T.a[i][j];}
	}
	cout<<"输入邻接距阵成功!!"<<endl;
	T.BBTSP();
}