graph.cpp

—图数据类型的实现——问题描述：图是一种较线性表和树更为复杂的数据结构。在图形结构中

// graph.cpp : Defines the entry point for the console application.
//

#include"Graph.h"
#include<iostream.h>
//template<class NameType,class DistType>
Graph::Graph(int sz):numVertexs(0),maxNumVertexs(sz),numEdges(0)
{
	int n,e,j,k;
	NameType name;
	DistType weight;
	status=new int[maxNumVertexs];
	for(int i=0;i<maxNumVertexs;i++)
		status[i]=0;
	nodeTable=new Vertex[sz];
	
	cout<<"input the number of vertices you want to creat:";
	cin>>n;
	for( i=0;i<n;i++)
	{
		cout<<"the "<<i<<" vertices value:";
		cin>>name;
		InsertVertex(name);
	}
	cout<<"input the number of edges you want to creat:"<<endl;
	cin>>e;
	cout<<"the edge order is head  tail weight,such as 3 5 67:\n";
	for(i=0;i<e;)
	{
		cout<<"the "<<i<<" edge:";
		cin>>j>>k>>weight;
		if(j==k)
		{
			cout<<"input error! head=tail is forbidden!"<<endl;
			continue;
		}
		i++;
	}
}
void Graph::InsertVertex(const NameType &ver)
{
	if(numVertexs<maxNumVertexs)
	{
		(nodeTable[numVertexs]).data=ver;
		(nodeTable[numVertexs]).adj=NULL;
		numVertexs++;
	}
	else
	{
		cout<<"insert vertice error!it is full!"<<endl;
		return;
	}
}
void Graph::InsertEdge(int v1,int v2,DistType weight)
{
	Edge *ps=NULL;
	Edge *pEdge=new Edge(v1,weight);
	ps=nodeTable[v2].adj;
	if(ps==NULL)
		ps=pEdge;
	else
	{
		while( ps->link!=NULL)
			ps=ps->link;
		ps->link=pEdge;
	}
	pEdge=new Edge(v2,weight);
	ps=nodeTable[v1].adj;
	if(ps==NULL)
		ps=pEdge;
	else
	{
		while( ps->link!=NULL)
			ps=ps->link;
		ps->link=pEdge;
	}
}
void Graph::RemoveEdge(int v1,int v2)
{
	Edge *p1,*p2;
	p2=p1=nodeTable[v1].adj;
	while( p1!=NULL && p1->dest!=v2 )
	{
		p2=p1;
		p1=p1->link;
	}
	if(p1==nodeTable[v1].adj)
	{
		nodeTable[v1].adj=p1->link;
		delete p1;
	}
	else
	{
		if(p1->link!=NULL)
		{
			p2->link=p1->link;
			delete p1;
		}
		else
		{
			p2->link=NULL;
			delete p1;
		}
	}
	p2=p1=nodeTable[v2].adj;
	while( p1!=NULL && p1->dest!=v1 )
	{
		p2=p1;
		p1=p1->link;
	}
	if(p1==nodeTable[v2].adj)
	{
		nodeTable[v2].adj=p1->link;
		delete p1;
	}
	else
	{
		if(p1->link!=NULL)
		{
			p2->link=p1->link;
			delete p1;
		}
		else
		{
			p2->link=NULL;
			delete p1;
		}
	}
}
Graph::~Graph()
{
	Edge *p,*p1;
	for(int i=0;i<numVertexs;i++)
	{
		p=(nodeTable[i]).adj;
		while(p!=NULL)
		{
			p1=p;
			p=p->link;
			delete p1;
		}
		delete p;
	}
		delete []nodeTable;
}
void Graph::RemoveVertex(int v)
{
	Edge *p1;
	int dst;
	p1=(nodeTable[v]).adj;
	while(p1!=NULL)
	{
		dst=p1->dest;
		this->RemoveEdge(v,dst);
	}
	for(int i=v;i<numVertexs;i++)
		nodeTable[i]=nodeTable[i+1];

	numVertexs--;
}
DistType Graph::GetWeight(int v1,int v2)
{
	Edge *p;
	p=nodeTable[v1].adj;
	while(p!=NULL&&p->dest!=v2)
		p=p->link;
	if(p==NULL)
	{
		cout<<"no edge exist!";
		return 0;
	}
	return p->cost;
}
int Graph::GetNextNeighbor(int v1,int v2)
{
	Edge *p=nodeTable[v1].adj;
	while(p!=NULL&&p->dest!=v2)
		p=p->link;
	if(p==NULL)
	{
		cout<<"no next neighbor!";
		return -1;
	}
	else
	{
		if(p->link!=NULL)
			return p->link->dest;
		else
			return -1;
	}
}
int Graph::GetVertexPos(const NameType &ver)	
{
	for(int i=0;i<numVertexs;i++)
	{
		if(nodeTable[i].data==ver)
			return i;
	}
	return -1;
}
int Graph::GetFirstNeighbor(int v)
{
	if(nodeTable[v].adj!=NULL)
		return nodeTable[v].adj->dest;
	else return -1;
}                                     

/*ostream& operator<<(ostream &out,Graph &ref)
{
	for(int i=0;i<numVertexs;i++)
		out<<"vertices: "<<i<<"  value: "<<nodeTable[i].data;
	for( i=0;i<numVertexs;i++)
	{
		Edge *p=(nodeTable[i]).adj;
		while()
		out<<"edge:"<<i
		
			return out;

}*/
void Graph::DFS(int start)
{
	
	if( start<0 && start>=numVertexs ) 
	{
		cout<<"end!"<<endl;
		return;
	}
	cout<<nodeTable[start].data<<endl;
	int v1=this->GetFirstNeighbor(start);
	while(v1!=-1)
	{
		cout<<this->GetValue(v1)<<endl;
		DFS(v1);
		v1=this->GetNextNeighbor(start,v1);
		
	}
return;
}