graphlnk.h

一个图的学习程序

//邻接表表示的图的类定义
#include "iostream"


;using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxWeight = 80;
const int DefaultVertices = 100;

//边结点的定义
template <class T, class E>
struct Edge
{
	int dest;                             //边的另一顶点位置
	E cost;
	Edge<T,E> *link;                      //下一条边的链指针
	Edge(){}
	Edge(int num, E weight):dest(num),cost(weight),link(NULL){}
	bool operator != (Edge<T,E> &R)const
	{
		return (dest != R.dest)?true:false;
	}
};

//结点的定义
template <class T,class E>
struct Vertex
{
	T data;                       //顶点的名字
	Edge<T,E> *adj;               //边链表的头指针
};

//图的类定义
template <class T,class E>
class Graphlnk
{
	template <class T,class E>
	friend std::istream &operator>>(std::istream &in, Graphlnk<T,E> &G);
	template <class T,class E>
	friend std::ostream &operator<<(std::ostream &out, Graphlnk<T,E> &G);
public:
	Graphlnk(int sz = DefaultVertices);
	~Graphlnk();
	T getValue(int i)
	{
		return(i>=0 && i<numVertices)? NodeTable[i].data:0;
	}
	E getWeight(int v1,int v2);
	bool insertVertex(const T &vertex);
	bool removeVertex(int v);
	E insertEdge(int v1,int v2,E cost);
	bool removeEdge(int v1,int v2);
	int getFirstNeighbor(int v);
	int getNextNeighbor(int v,int w);
	bool createVertices(int n);
	void output();
//private:
	Vertex<T,E> *NodeTable;
	int maxVertices;
	int numedges;
	int numVertices;
	int getVertexPos(const T vertex)
	{
		for(int i=0;i<numVertices;i++)
			if(NodeTable[i].data == vertex)return i;
		return -1;
	}
};

//构造函数：建立一个空的邻接表
template <class T,class E>
Graphlnk<T,E>::Graphlnk(int sz)
{
	maxVertices = sz;
	numVertices = 0;
	numedges = 0;
	NodeTable = new Vertex<T,E>[maxVertices];
	if(NodeTable == NULL)
	{
		cerr<<"存储分配错误！"<<endl;
		exit(1);
	}
	for(int i=0; i<maxVertices; i++)
		NodeTable[i].adj = NULL;
}

//析构函数：删除一个邻接表
template <class T,class E>
Graphlnk<T,E>::~Graphlnk()
{
	for(int i=0; i<numVertices; i++)               //删除各边链表中的结点
	{
		Edge<T,E> *p = NodeTable[i].adj;           //找到其对应边链表的首结点
		while(p != NULL)                           //不断地删除第一个结点
		{
			NodeTable[i].adj = p->link;
			while(p != NULL)
			{
				NodeTable[i].adj = p->link;
				delete p;
				p = NodeTable[i].adj;
			}
		}
	}
	delete []NodeTable;                                //删除顶点表数组
}

//给出定位位置为v的第一个邻接顶点的位置，如果找不到，则函数返回-1
template <class T,class E>
int Graphlnk<T,E>::getFirstNeighbor(int v)
{
	if(v != -1)
	{
		Edge<T,E> *p = NodeTable[v].adj;
		if(p != NULL) return p->dest;
	}
	return -1;
}

//给出顶点v的邻接顶点w的下一个邻接顶点的位置，若没有下一个邻接顶点，则函数返回-1
template <class T, class E>
int Graphlnk<T,E>::getNextNeighbor(int v, int w)
{
	if(v != -1)
	{
		Edge<T,E> *p = NodeTable[v].adj;
		while(p != NULL && p->dest != w)           //寻找顶点w
			p = p->link;
		if(p !=NULL && p->link != NULL)            //寻找下一个邻接顶点
			return p->link->dest;
	}
	return -1;
}

//函数返回边（v1，v2）上的权值，若该边不在图中，则函数返回权值0
template <class T, class E>
E Graphlnk<T,E>::getWeight(int v1, int v2)
{
	if(v1 != -1 && v2 != -1)
	{
		Edge<T,E> *p = NodeTable[v1].adj;
		while(p != NULL && p->dest != v2)
			p = p->link;
		if(p != NULL)
			return p->cost;
	}
	return 0;
}

//在图的顶点表中插入一个新顶点vertex，成功则返回true，否则返回false
template <class T,class E>
bool Graphlnk<T,E>::insertVertex(const T &vertex)
{
	if(numVertices == maxVertices)
		return false;
	NodeTable[numVertices].data = vertex;
	numVertices++;
	return true;
}

//在图中删除一个指定顶点v，v是顶点号。若删除成功，函数返回true，否则返回false
template <class T,class E>
bool Graphlnk<T,E>::removeVertex(int v)
{
	if(numVertices == 1 || v<0 || v>=numVertices)return false;
	Edge<T,E> *p,*s,*t;
	int i,k;
	while(NodeTable[v].adj != NULL)
	{
		p = NodeTable[v].adj;
		k = p->dest;
		s = NodeTable[k].adj;
		t = NULL;
		while(s != NULL && s->dest !=v)
		{
			t = s;
			s = s->link;
		}
		if(s != NULL)
		{
			if(t == NULL)
				NodeTable[k].adj = s->link;
			else t->link = s->link;
			delete s;
		}
		NodeTable[v].adj = p->link;
		delete p;
		numedges--;
	}
	numVertices--;
	NodeTable[v].data = NodeTable[numVertices].data;
	p = NodeTable[v].adj = NodeTable[numVertices].adj;
	while(p != NULL)
	{
		s = NodeTable[p->dest].adj;
		while(s != NULL)
		{
			if(s->dest == numVertices)
			{
				s->dest = v;
				break;
			}
			else
				s = s->link;
		}
	}
	return true;
}


template <class T,class E>
E Graphlnk<T,E>::insertEdge(int v1, int v2, E cost)
{
	if(v1>=0 && v1<numVertices && v2>=0 && v2<numVertices)
	{
		Edge<T,E> *q,*p = NodeTable[v1].adj;
		while(p != NULL && p->dest != v2)
			p = p->link;
		if(p != NULL)return false;
		p = new Edge<T,E>;
		q = new Edge<T,E>;
		p->dest = v2;
		p->cost = cost;
		p->link = NodeTable[v1].adj;
		NodeTable[v1].adj = p;
		q->dest = v1;
		q->cost = cost;
		q->link = NodeTable[v2].adj;
		NodeTable[v2].adj = q;
		numedges++;
		//cout<<"<"<<NodeTable[v1].data<<","<<NodeTable[v2].data<<":"<<p->cost<<">"<<endl;
		return p->cost;
	}
	return 0;
}

template <class T,class E>
bool Graphlnk<T,E>::createVertices(int n)
{
	if(n<=maxVertices)
	{
		numVertices = n;
		for(int i=0; i<n; i++)
		{
			NodeTable[i].data = i+1;
		}
		for(int j=0; j<n; j++)
		{
			cout<<"NodeTable["<<j<<"].data="<<NodeTable[j].data<<endl;
		}
		return true;
	}
	else
		return false;
}

template <class T ,class E>
void Graphlnk<T,E>::output()
{
	cout<<"The number of vertices are:"<<numVertices<<endl;
	cout<<"The number of edges are:"<<numedges<<endl;
}

template <class T,class E>
bool Graphlnk<T,E>::removeEdge(int v1, int v2)
{
	if(v1 != -1 && v2 != -1)
	{
		Edge<T,E> *p = NodeTable[v1].adj, *q = NULL, *s = p;
		while(p != NULL && p->dest != v2)
		{
			q = p;
			p = p->link;
		}
		if(p != NULL)
		{
			if(p == s)
				NodeTable[v1].adj = p->link;
			else
				q->link = p->link;
			delete p;
		}
		else return false;
		p = NodeTable[v2].adj;
		q = NULL;
		s = p;
		while(p->dest != v1)
		{
			q = p;
			p = p->link;
		}
		if(p == s)
			NodeTable[v2].adj = p->link;
		else
			q->link = p->link;
		delete p;
		return true;
	}
	return false;
}