202728.cpp

数据结构（清华版）

#include<iostream.h>
#include<fstream.h>
const MaxVexNum=20;
const Infinty=-1;
typedef char VexType;
typedef int ArcType;
//创建结构体======================================================================================
typedef struct ArcNode
{
	int adjvex;ArcType info;ArcNode *nextarc;
}*ArcPtr;

struct VexNode
{ VexType data;ArcPtr firstarc;};

struct ALGraph
{VexNode vexs[MaxVexNum+1];
int kind,vexnum,arcnum;
};
//创建顶点查找函数==================================================================================
int LocateVex(ALGraph &G,VexType V)
{
	int i;
	for(i=G.vexnum;i>0 && G.vexs[i].data!=V;i--);
	return i;
}


//邻接表存储结构创建图=================================================================================
void CreateGraph(ALGraph &G,char fn[])
{
	int i,j;VexType c,u,v;
	ArcPtr p;ifstream f;ArcType w;
	f.open(fn,ios::nocreate);
	if(!f){G.vexnum=0;return;}
	f>>G.kind;i=0;
	while(true)
	{
		f>>c;if(c=='#') break;
		i++;G.vexs[i].data=c;
		G.vexs[i].firstarc=NULL;
	}
	G.vexnum=i;
	G.arcnum=0;
	while(true)
	{
		f>>u>>v; if(u=='#'||v=='#') break;
		i=LocateVex(G,u);
		if(i==0) continue;
		j=LocateVex(G,v);
		if(j==0||j==i) continue;
		if(G.kind==1||G.kind==3) w=1;
		else f>>w;
		G.arcnum++;p=new ArcNode;
		p->adjvex=j;p->info=w;
		p->nextarc=G.vexs[i].firstarc;
		G.vexs[i].firstarc=p;
		if(G.kind<=2) continue;
		G.arcnum++;p=new ArcNode;
		p->adjvex=i;p->info=w;
		p->nextarc=G.vexs[j].firstarc;
		G.vexs[j].firstarc=p;
	}
	
	f.close ();
}

//输出图函数==============================================================================================
void OutputGraph(ALGraph &G)  
{
	int i,j;ArcPtr p;
	if(G.vexnum ==0)   
	{cout<<"空图"<<endl;return;}
	cout<<"          "<<"顶点数="<<G.vexnum <<"   弧数="<<G.arcnum <<"    顶点:";  
	for(i=1;i<=G.vexnum ;i++)cout<<G.vexs [i].data<<',';
	cout<<endl<<"各顶点的出弧:"<<endl;
	for(i=1;i<=G.vexnum ;i++)
	{
		cout<<"      "<<"顶点"<<G.vexs[i].data<<endl;
		for(p=G.vexs [i].firstarc;p;p=p->nextarc )
			cout<<"      "<<"  <"<<G.vexs [i].data<<','<<G.vexs [p->adjvex].data<<">:"<<p->info <<endl;
	}
	cout<<"      "<<"各顶点的入弧:"<<endl;
	for(i=1;i<=G.vexnum ;i++)
	{
		cout<<"      "<<"顶点"<<G.vexs[i].data <<endl;
		for(j=1;j<=G.vexnum ;j++)
			for(p=G.vexs [j].firstarc;p;p=p->nextarc)
				if(G.vexs[p->adjvex].data ==G.vexs[i].data )
					cout<<"      "<<"  <"<<G.vexs [j].data <<','<<G.vexs [i].data <<">:"<<p->info <<endl;
	}
	
}
//创建函数求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度
int m=0;
void FindSimplePath(ALGraph G,int u,int v,int k,int  visited[],int path[])
{
	int l,i;ArcPtr p;
	path[k]=u; 
	visited[u]=1;
	if(u==v) 
	{
		m++;
		cout<<"找到地  "<<m<<" 一个路径";
		for(i=0;i<=k;i++) cout<<"  "<<G.vexs[path[i]].data; //输出
		cout<<endl;
	}
	else
		for(p=G.vexs[u].firstarc;p;p=p->nextarc)
		{
			l=p->adjvex;
			if(visited[l]==0) FindSimplePath(G,l,v,k+1,visited,path); //继续寻找
		}
	visited[u]=0;
	path[k]=0; 
}
void FindSimplePath(ALGraph G,VexType u,VexType v)
{
	int i ,j;int visited[MaxVexNum+1];int path[MaxVexNum+1];
	for(i=1;i<=G.vexnum ;i++)visited[i]=0;
	i=LocateVex(G,u);
	j=LocateVex(G,v);
	FindSimplePath( G,i,j,0, visited,path);
}
//主函数===================================================================================================
void main()
{
	ALGraph G;
	cout<<"邻接表形式存储的图结构："<<endl;
	CreateGraph(G,"728.txt");
	OutputGraph(G); 
	cout<<endl<<endl;
	FindSimplePath( G,'u','v');
	cout<<endl;
	
	
}