08.cpp

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

#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

///////////////////////////////////////////////////////////
//8.4.1用邻接矩阵实现赋权有向图
///////////////////////////////////////////////////////////

template<class T>
class AdjacencyWDigraph
{
	firend AdjacencyWGraph<T>;
	public:
		AdjacencyWDigraph(int Vertices=10,T noEdge=0);
		~AdjacencyWDigraph() { Delete2DArray(a,n+1);}
		bool Exist(int i,int j) const;
		int Edges() const {return e;}
		int Vertices() const {return n;}
		AdjacencyWDigraph<T>&Add(int i,int j,const T&w);
		AdjacencyWDigraph<T>&Delete(int i,int j);
		int OutDegree(int i) const;
		int InDegree(int i) const;
		void Output() const;
	private:
		T NoEdge;
		int n;
		int e;
		T **a;
};
template<class T>
AdjacencyWDigraph<T>::AdjacencyWDigraph(int Vertices,T noEdge)
{
	n=Vertices;
	e=0;
	NoEdge=noEdge;
	Make2DArray(a,n+1,n+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=NoEdge;
}
template<class T>
bool AdjacencyWDigraph<T>::Exist(int i,int j) const
{
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge) return false;
	return true;
}
template<class T>
AdjacencyWDigraph<T> & AdjacencyWDigraph<T>::Add(int i,int j,const T&w)
{
//	if(i<1||j<1||i>n||j>n||i==j||a[i][j]!=NoEdge) throw BadInput();
	a[i][j]=w;
	e++;
	return *this;
}
template<class T>
AdjacencyWDigraph<T> & AdjacencyWDigraph<T>::Delete(int i,int j)
{
	if(i<1||j<1||i>n||j>n||a[i][j]==NoEdge) throw BadInput();
	a[i][j]=NoEdge;
	e--;
	return *this;
}
template<class T>
int AdjacencyWDigraph<T>::OutDegree(int i) const
{
	if(i<1||i>n) throw BadInput();
	int sum=0;
	for(int j=1;j<=n;j++)
		if(a[i][j]!=NoEdge) sum++;
		return sum;
}
template<class T>
int AdjacencyWDigraph<T>::InDegree(int i) const
{
	if(i<1||i>n) throw BadInput();
	int sum=0;
	for(int j=1;j<=n;j++)
		if(a[j][i]!=NoEdge) sum++;
		return sum;
}
template<class T>
void AdjacencyWDigraph<T>::Output() const
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			out<<a[i][j]<<" ";
		out<<endl;
	}
}
///////////////////////////////////////////////////////////
//8.4.2用邻接矩阵实现赋权无向图
///////////////////////////////////////////////////////////
template<class T>
class AdjacencyWGraph:public AdjacencyWDigraph<T>
{
	public:
		AdjacencyWGraph(int Vertices=10,T noEdge=0)
		:AdjacencyWGraph<T>(Vertices,noEdge){}
		AdjacencyWGraph<T> & Add(int i,int j,const T &w)
		{
			AdjacencyWDigraph<T>::Add(i,j,w);
			a[i][j]=w;
			return *this;
		}
		AdjacencyWGraph<T> & Delete(int i,int j)
		{
			AdjacencyWDigraph<T>::Delete(i,j,w);
			a[j][i]=NoEdge;
			return *this;
		}
		int Degree(int i) const {return OutDegree(i);}
}
///////////////////////////////////////////////////////////
//8.4.3用邻接矩阵实现有向图
///////////////////////////////////////////////////////////
class AdjacencyDigraph:public AdjacencyWDigraph<int>
{
	public:
		AdjacencyDigraph(int Vertices=10)
		:AdjacencyWDigraph<int>(Vertices,0){}
		AdjacencyDigraph & Add(int i,int j)
		{
			AdjacencyWDigraph<int>::Add(i,j,1);
			return *this;
		}
		AdjacencyDigraph & Delete(int i,int j)
		{
			AdjacencyWDigraph<int>::Delete(i,j);
			return *this;
		}
}
///////////////////////////////////////////////////////////
//8.4.4用邻接矩阵实现无向图
///////////////////////////////////////////////////////////
class AdjacencyGraph:public AdjacencyWGraph<int>
{
	public:
		AdjacencyGraph(int Vertices=10)
		:AdjacencyWGraph<int>(Vertices,0){}
		AdjacencyGraph & Add(int i,int j)
		{
			AdjacencyWGraph<int>::Add(i,j,1);
			return *this;
		}
		AdjacencyWGraph<int> & Delete(int i,int j)
		{
			AdjacencyWGraph<int>::Delete(i,j);
			return *this;
		}
}
///////////////////////////////////////////////////////////
//8.5.1邻接表基类
///////////////////////////////////////////////////////////
template<class T>
List<T>&List<T>::Delete(T&x)
{
	Node<T> *current=first,
		    *trail=0;
	while(current && curretn->element!=x)
	{
		trail=current;
		current=current->next;
	}
	if(!current) out<<"wrong!";
	x=current->element;
	if(trail)  trail->next=current->next;
	else first=current->next;
	delete current;
	return *this;
}

template<class T>
class LinkedBase
{
public:
	LinkedBase(int Vertices=10)
	{
		n=Vertices;
		e=0;
		h=new List<T>[n+1];
	}
	~LinkedBase() {delete [] h;}
	int Edges() const { return e;}
	int Vertices() const {return n;}
	int OutDegree(int i) const
	{
		if(i<1||i>n) out<<"wrong!";
		return h[i].LENGTH();
	}
private:
	int n;
	int e;
	List<T> *h;
}
///////////////////////////////////////////////////////////
//8.5.2用邻接表实现有向图
///////////////////////////////////////////////////////////
class LinkedDigraph : public LinkedBase<int>
{
public:
	LinkedDigraph(int Vertices=10)
		:LinkedBase<int> (Vertices){}
	bool Exist(int i,int j) const;
	LinkedDigraph & Add(int i,int j);
	LinkedDigraph & Delete(int i,int j);
	int InDegree(int i) const;
protected:
	LinkedDigraph & AddNoCheck(int i,int j);
}

bool LinkedDigraph::Exist(int i,int j)const
{
	if(i<1||i>n) out<<"wrong!";
	return (h[i].Locate(j)) ? true:false;
}

LinkedDigraph & LinkedDigraph::Add(int i,int j)
{
	if(i<1||j<1||i>n||j>n||i==j||Exist(i,j)) out<<"wrong!";
	return AddNoCheck(i,j);
}

LinkedDigraph & LinkedDigraph::AddNoCheck(int i,int j)
{
	h[i].Insert(0,j);
	e++;
	return *this;
}

LinkedDigraph & LinkedDigraph::Delete(int i,int j)
{
	if(i<1||i>n) out<<"wrong!";
	h[i].Delete(j);
	e--;
	return *this;
}

int LinkedDigraph::InDegree(int i) const
{
	if(i<1||i>n) out<<"wrong!";
	int sum=0;
	for(int j=1;j<=n;j++)
		if(h[j].Locate(i)) sum++;
	return sum;
}

///////////////////////////////////////////////////////////
//8.5.3用邻接表实现无向图
///////////////////////////////////////////////////////////
class LinkedGraph : public LinkedDigraph
{
public:
	LinkedGraph(int Vertices=10)
		:LinkedDigraph (Vertices){}
	LinkedGraph & Add(int i,int j);
	LinkedGraph & Delete(int i,int j);
	int Degree(int i) const {return OutDegree(i);}
	int InDegree(int i) const {return OutDegree(i);}
protected:
	LinkedGraph & AddNoCheck(int i,int j);
}
 
LinkedGraph & LinkedGraph::Add(int i,int j)
{
	if(i<1||j<1||i>n||j>n||i==j||Exist(i,j)) out<<"wrong!";
	return AddNoCheck(i,j);
}

LinkedGraph & LinkedGraph::AddNoCheck(int i,int j)
{
	h[i].Insert(0,j);
	try {h[j].Insert(0,j);}
	catch(...) {h[i].Delete(j);
	throw;}
	e++;
	return *this;
}

LinkedGraph & LinkedGraph::Delete(int i,int j)
{
	LinkedDigraph::Delete(i,j);
	e++;
	LinkedDigraph::Delete(j,i);
	return *this;
}

///////////////////////////////////////////////////////////
//8.5.4用邻接表实现赋权有向图
///////////////////////////////////////////////////////////
template<class T>
class GraphNode
{
	friend LinkedWDigraph<T>;
	friend LinkedWGraph<T>;
	friend List<T>;
public:
	int operator!=(GraphNode<T> y)const
	{
		return (vertex!=y.vertex);
	}
	void Output(ostream & out) const
	{
		out<<vertex<<" "<<weight<<" ";
	}
private:
	int vertex;
	T weight;
};
template<class T>
ostream & operator<<(ostream & out,GraphNode<T> x)
{
	x.Output(out) ;
	return out;
}


template<class T>
class LinkedWDigraph : public LinkedBase<GraphNode<T>>
{
public:
	LinkedWDigraph(int Vertices=10)
		:LinkedBase<GraphNode<T>> (Vertices){}
	bool Exist(int i,int j) const;
	LinkedWDigraph<T> & Add(int i,int j,const T&w);
	LinkedWDigraph<T> & Delete(int i,int j);
	int InDegree(int i) const ;
protected:
	LinkedWDigraph<T> & AddNoCheck(int i,int j,const T&w);
}
template<class T>
bool LinkedWDigraph<T>::Exist(int i,int j) const
{
	if(i<1||i>n) out<<"wrong!";
	GraphNode<T> x;
	x.vertex=j;
	return h[i].Locate(x);
}
template<class T>
LinkedWDigraph<T> & LinkedWDigraph<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>
LinkedWDigraph<T> & LinkedWDigraph<T>::AddNoCheck(int i,int j,const T&w)
{
	GraphNode<T> x;
	x.vertex=j;
	x.weight=w;
	h[i].Insert(0,x);
	e++;
	return *this;
}

template<class T>
LinkedWDigraph<T> & LinkedWDigraph<T>::Delete(int i,int j,const T&w)
{
	if(i<1||i>n) out<<"wrong!";
	GraphNode<T> x;
	x.vertex=j;
	h[i].Delete(x);
	e--;
	return *this;
}
template<class T>
int LinkedWDigraph<T>::InDegree(int i) const
{
	if(i<1||i>n) out<<"wrong!";
	int sum=0;
	GraphNode<T> x;
	x.vertex=i;
	for(int j=1;j<=n;j++)
		if(h[j].Locate(x)) sum++;
	return sum;
}
///////////////////////////////////////////////////////////
//8.5.5用邻接表实现赋权无向图
///////////////////////////////////////////////////////////
template<class T>
class LinkedWGraph : public LinkedWDigraph<T>
{
	public:
		LinkedWGraph(int Vertices=10)
		    :LinkedWDigraph<T> (Vertices){}
	    bool Exist(int i,int j) const;
	    LinkedWGraph<T> & Add(int i,int j,const T&w);