jichuti.cpp

这是一个关于数据结构的源程序

#include<iostream.h>
const int MAXV=10;
const int MAX=1000;
template<class NameType,class DistType>class Graph
{
	private:
		NameType*VList;
		int NumV;
		DistType Edge[MAXV][MAXV];
	public:
		Graph(int sz=MAXV);
		NameType GetValue(int i);
		int GetFN(int v);
		int GetNN(int v1,int v2);
		void CreatGraph();
		void dfs(int v,int*visited);
		void DFS();
};
template<class NameType,class DistType>
Graph<NameType,DistType>::Graph(int sz)
{
	NumV=sz;
	VList=new NameType[NumV];
	for(int i=0;i<sz;i++)
	{
		for(int j=0;j<sz;j++)
			Edge[i][j]=0;
	}
}
template<class NameType,class DistType>
NameType Graph<NameType,DistType>::GetValue(int i)
{
	return (i>=0&&i<NumV)?VList[i]:NULL;
}
template<class NameType,class DistType>
int Graph<NameType,DistType>::GetFN(int v)
{
	if(v!=-1)
	{
		for(int col=0;col<NumV;col++)
		{
			if(Edge[v][col]>0&&Edge[v][col]<MAX)
				return col;
		}
	}
	return -1;
}
template<class NameType,class DistType>
int Graph<NameType,DistType>::GetNN(int v1,int v2)
{
	if(v1!=-1&&v2!=-1)
	{
		for(int col=v2+1;col<NumV;col++)
			if(Edge[v1][col]>0&&Edge[v1][col]<MAX)return col;
	}
	return -1;
}
template<class NameType,class DistType>
void Graph<NameType,DistType>::CreatGraph()
{
	cout<<"输入结点的数据: ";
	for(int i=0;i<NumV;i++)
		cin>>VList[i];
	cout<<"输入邻接矩阵: "<<endl;
	for(int j=0;j<NumV;j++)
		for(int k=0;k<NumV;k++)
			cin>>Edge[j][k];
}
template<class NameType,class DistType>
void Graph<NameType,DistType>::dfs(int v,int*visited)
{
	cout<<GetValue(v)<<" ";
	visited[v]=1;
	int w=GetFN(v);
	while(w!=-1)
	{
		if(!visited[w])
			dfs(w,visited);
		w=GetNN(v,w);
	}
}
template<class NameType,class DistType>
void Graph<NameType,DistType>::DFS()
{
	int*visited=new int[NumV];
	for(int i=0;i<NumV;i++)
		visited[i]=0;
	dfs(0,visited);
	delete[] visited;
}
void main()
{
	int size,type;
	char flag;
	do
	{
		cout<<"输入要构建的图中结点的个数: ";
        cin>>size;
		cout<<"选择结点的数据类型: <1>整形<2>字符型<3>浮点型: ";
		cin>>type;
		switch(type)
		{
		case 2:{Graph<char,int> graph(size);
               graph.CreatGraph();
	           cout<<"图的深度优先遍历为: ";
			   graph.DFS(); break;}
		case 1:{Graph<int,int> graph(size);
               graph.CreatGraph();
	           cout<<"图的深度优先遍历为: ";
			   graph.DFS(); break;}
		case 3:{Graph<float,int> graph(size);
               graph.CreatGraph();
	           cout<<"图的深度优先遍历为: ";
			   graph.DFS(); break;}
		}
		cout<<endl<<"Try again?<Y/N>: ";
		cin>>flag;
	}while(flag=='Y'||flag=='y');
}