08.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

	    LinkedWGraph<T> & Delete(int i,int j);
	    int Degree(int i) const {return OutDegree(i);}
	    int InDegree(int i) const {return OutDegree(i);}
    protected:
	    LinkedWGraph<T> & AddNoCheck(int i,int j,const T&w);
}

template<class T> 
LinkedWGraph<T> & LinkedWGraph<T>::Add(int i,int j,const T&w)
{
	if(i<1||j<1||i>n||j>n||i==j||Exist(i,j)) out<<"wrong!";
	return AddNoCheck(i,j,w);
}

template<class T>
LinkedWGraph<T> & LinkedWGraph<T>::AddNoCheck(int i,int j,const T&w)
{
	GraphNode<T> x;
	x.vertex=j;
	x.weight=w;
	h[i].Insert(0,x);
	x.vertex=i;
	try {h[j].Insert(0,x);}
	catch(...) 
	{
		x.vertex=j;
		h[i].Delete(x);
	throw;}
	e++;
	return *this;
}
template<class T>
LinkedWGraph<T> & LinkedWGraph<T>::Delete(int i,int j)
{
	LinkedWGraph<T>::Delete(i,j);
	LinkedWGraph<T>::Delete(j,i);
	e++;
	return *this;
}

///////////////////////////////////////////////////////////
//8.6.1图的搜索游标
///////////////////////////////////////////////////////////
void InitializePos() { pos=new int [n+1];}
void DeactivatePos() { delete [] pos;}
template<class T>
int AdjacencyWDigraph<T>::Begin(int i)
{
	if(i<1||i>n) out<<"wrong!";
	for(int j=1;j<=n;j++)
		if(a[i][j]!=NoEdge)
		{
			pos[i]=j;
		    return j;
		}
	pos[i]=n+1;
	return 0;
}
template<class T>
int AdjacencyWDigraph<T>::NextVertex(int i)
{
	if(i<1||i>n) out<<"wrong!";
	for(int j=pos[i]+1;j<=n;j++)
		if(a[i][j]!=NoEdge)
		{
			pos[i]=j;
		    return j;
		}
	pos[i]=n+1;
	return 0;
}

void InitializePos() { pos=new Iterator<T> [n+1];}
void DeactivatePos() { delete [] pos;} 
private:
	Iterator<T> *pos;

int LinkedDigraph::Begin(int i)
{
	if(i<1||i>n) out<<"wrong!";
	int *x=pos[i].Init(h[i]);
	return (x) ? *x:0;
}

int LinkedDigraph::NextVertex(int i)
{
	if(i<1||i>n) out<<"wrong!";
	int *x=pos[i].Next();
	return (x) ? *x:0;
}

template<class T>
int LinkedWDigraph<T>::Begin(int i)
{
	if(i<1||i>n) out<<"wrong!";
	GraphNode<T> *x=pos[i].Init(h[i]);
	return (x) ? x->vertex:0;
}

template<class T>
int LinkedWDigraph<T>::NextVertex(int i)
{
	if(i<1||i>n) out<<"wrong!";
	GraphNode<T> *x=pos[i].Next();
	return (x) ? x->vertex:0;
}
///////////////////////////////////////////////////////////
//8.6.2广度优先搜索
///////////////////////////////////////////////////////////
template<class T>
void AdjacencyWDigraph<T>::BFS(int v,int reach[],int label)
{
    Queue<int> Q;
    reach[v]=label;
    Q.EnQueue(v);
    while(!Q.Empty())
	{
	    int w;
	    Q.DeQueue(w);
  	    for(int u=1;u<=n;u++)
		    if(a[w][u]!=NoEdge && !reach[u])
			{
			    Q.EnQueue(u);
			    reach[u]=label;
			}
	}
}

void LinkedWDigraph::BFS(int v,int reach[],int label)
{	
    Queue<int> Q;
    reach[v]=label;
    Q.EnQueue(v);
    while(!Q.Empty())
	{
	    int w;
	    Q.DeQueue(w);
		Node<int> *p;
		for(p=h[w].First();p;p=p->next)
		{
			int u=p->element;
			if(!reach[u])
			{
				Q.EnQueue(u);
				reach[u]=label;
			}
		}
	}
}

class Network
{
public:
	virtual int Begin(int i)=0;
	virtual int NextVertex(int i)=0;
	virtual void InitializePos()=0;
	virtual void DeactivatePos()=0;
	virtual int Vertices() const =0;
	virtual int Edges() const =0;
	void BFS(int v,int reach[],int label);
	void DFS(int v,int reach[],int label);
}

void Network::BFS(int v,int reach[],int label)
{
	Queue<int> Q;
	InitializePos();
    reach[v]=label;
    Q.EnQueue(v);
    while(!Q.Empty())
	{
	    int w;
	    Q.DeQueue(w);
		int u=Begin(w);
		while(u)
		{
			if(!reach[u])
			{
				Q.EnQueue(u);
				reach[u]=label;
			}
			u=NextVertex(w);
		}
	}
	DeactivatePos();
}
///////////////////////////////////////////////////////////
//8.6.3深度优先搜索
///////////////////////////////////////////////////////////
void NetWork::DFS(int v,int reach[],int label)
{
	InitializePos();
	dfs(v,reach,label);
	DeactivatePos();
}

void Network::dfs(int v,int reach[],int label)
{
	reach[v]=label;
	int u=Begin(v);
	while(u)
	{
		if(!reach[u]) dfs(u,reach,label);
		u=NextVertex(v);
	}
}

///////////////////////////////////////////////////////////
//8.7.1单源最短路径
///////////////////////////////////////////////////////////
template<class T>
void AdjacencyWDigraph<T>::Dijkstra(int s,T dist[],int prev[])
{
	if(s<1||s>n) out<<"wrong!";
	List<int> L;
	Iterator<int> I;
	for(int v=1;v<=n;v++)
	{
		dist[v]=a[s][v];
		if(dist[v]==NoEdge) prev[v]=0;
		else
		{
			prev[v]=s;
			L.Insert(0,v);
		}
	}

	while(!L.Empty())
	{
		int *v=I.Init(L);
		int *w=I.Next();
		while(w)
		{
			if(dist[*w]<dist[*v]) v=w;
			w=I.Next();
		}
		
		int i=*v;
		L.Delete(*v);
		for(int j=1;j<-n;j++)
		{
			if(a[i][j]!=NoEdge && (!prev[j]||dist[j]>dist[i]+a[i][j]))
			{
				dist[j]=dist[i]+a[i][j];
				if(!prev[j]) L.Insert(0,j);
				prev[j]=i;
			}
		}
	}
}
///////////////////////////////////////////////////////////
//8.7.2所有顶点对之间的最短路径
///////////////////////////////////////////////////////////
template<class T>
void AdjacencyWDigraph<T>::Floyed(T **c,int **path)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			c[i][j]=a[i][j];
			path[i][j]=0;
		}
    for(i=1;i<=n;i++)
		c[i][i]=0;
	for(int k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				T t1=c[i][k];
				T t2=c[k][j];
				T t3=c[i][j];
				if(t1 != NoEdge && t2 != NoEdge && (t3 == NoEdge || t1+t2<t3))
				{
					c[i][j]=t1+t2;
					path[i][j]=k;
				}
			}
}
///////////////////////////////////////////////////////////
//8.8.2 Prim算法
///////////////////////////////////////////////////////////
template<class T>
class EdgeNode
{
	friend ostream & operator<<(ostream &,EdgeNode<T>);
	friend UNetwork<T>;
	friend AdjacencyWGraph<T>;
	friend void main(void);
	public:
		operator T() const {return weight;}
	private:
		T weight;
		int u,v;
}

template<class T>
bool AdjacencyWGraph<T>::Prim(EdgeNode<T> *t)
{
  int i,j,k,kk=0;
  T *lowcost = new T [n+1];
  int *closest = new int [n+1];
  bool *s = new bool [n+1];
  s[1]=true;
  for (i = 2; i <= n; i++){
    lowcost[i] = a[i][1];
    closest[i]=1;
    s[i]=false;
    }
  for (i = 1; i < n; i++){
    T min=NoEdge;
    j=1;
    for (k = 2; k <= n; k++)
      if ((lowcost[k]<min)&&(!s[k])){
        min=lowcost[k];
        j=k;}
    if(min==NoEdge)return false;
    t[kk].weight = lowcost[j];
    t[kk].u = j;
    t[kk++].v = closest[j];
    s[j]=true;
    for (k = 2; k <= n; k++)
      if ((a[k][j]<lowcost[k])&&(!s[k])){
        lowcost[k]=a[k][j];
        closest[k]=j;
        }
    }
  return (kk == n-1);
}

///////////////////////////////////////////////////////////
//8.8.3Kruskal算法
///////////////////////////////////////////////////////////
template<class T>
bool UNetwork<T>::Kruskal(EdgeNode<T> t[])
{
	int n=Vertices();
	int e=Edges();
	InitializePos();
	EdgeNode<T> *E=new EdgeNode<T> [e+1];
	int k=0;
	for(int i=1;i<=n;i++)
	{
		int j;
		T c;
		First(i,j,c);
		while(j)
		{
			if(i<j)
			{
				E[++k].weight=c;
				E[k].u=i;
				E[k].v=j;
			}
		    Next(i,j,c);
		}
	}

	MinHeap<EdgeNode<T>> H(1);
	H.Initialize(E,e,e);
	UnionFind U(n);
	k=0;
	while(e && k<n-1)
	{
		EdgeNode<T> x;
		H.DeleteMin(x);
		e--;
		int a=U.Find(x,u);
		int b=U.Find(x,v);
		if(a!=b)
		{
			t[k++]=x;
			U.Union(a,b);
		}

	}
	DeactivatePos();
	H.Deactivate();
	return (k==n-1);
}