guide.cpp

设计一个校园导游程序

#include<iostream.h>
#include<fstream.h>
#include<stdio.h>
#include<string.h>
#include<malloc.h>

#define MAXVTXNUM  20
#define INFINITY  300

typedef struct{
	char name[30];
	char info[200];
}VertexType;

typedef struct{
  int length;
  int ivex,jvex;
}EdgeType;

typedef struct EdgeNode{
  EdgeType elem;
  EdgeNode *ilink,*jlink;
  int tag;
}EdgeNode,*EdgePtr;

typedef struct{
  VertexType data;
  EdgePtr firstEdge;
}VNode;

typedef struct{
  VNode Adjmulist[MAXVTXNUM];
  int vexNum,edgeNum;
}Graph;

typedef struct{
  int vx,vy;
}Edge;

typedef struct{
  Edge edges[MAXVTXNUM];
  int len;
}PathType,Parray[MAXVTXNUM][MAXVTXNUM];

typedef struct{
  char vertices[MAXVTXNUM][30];
  int num;
}PType;

typedef struct{
  int a;
}Int,array[MAXVTXNUM][MAXVTXNUM];

Parray P;
array D;
PType ALLP[MAXVTXNUM][MAXVTXNUM];

void InitGraph(Graph&g);						//初始化图g
int LocateVex(Graph&g,char*uname);				//返回g中顶点名与uname相同的顶点序号
void GetVex(Graph g,int i,VertexType&v);		//用v返回g中顶点序号为i的顶点
EdgePtr FirstEdge(Graph g,int vi);				//返回g中序号为vi的顶点的第一条边的指针
void NextEdge(Graph g,int vi,EdgePtr p,EdgePtr&q);	
void InsertVex(Graph&g,VertexType v);
void InsertEdge(Graph&g,EdgeType e);
int CreateGraph(Graph&g,char*str);
void ShowVex(Graph g,int vi);
void ShowGraph(Graph&g);

void InitPath(PathType&pa)
{
  pa.len=0;
}//Initpath

void OutPath(Graph g,PathType pa,PType&vtxes)
{
  int m=0;
  VertexType vtx;
  for(int i=0;i<pa.len;i++)
  {
    GetVex(g,pa.edges[i].vx,vtx);
	strcpy(vtxes.vertices[m++],vtx.name);
  }
  GetVex(g,pa.edges[pa.len].vy,vtx);
  strcpy(vtxes.vertices[m],vtx.name);
  vtxes.num=m;
}//OutPath 存在问题

void ShortestPath(Graph g,Parray P,array D)
{
  EdgePtr e=NULL;
  int u,v,w,i,j;
  for( v=0;v<g.vexNum;++v)
    for( w=0;w<g.vexNum;++w)
	{
	  D[v][w].a=INFINITY;
	  for(EdgePtr e=FirstEdge(g,v);e;NextEdge(g,v,e,e))
		  if(v==w)D[v][w].a=0;
		  else if((e->elem.ivex==v&&e->elem.jvex==w)||(e->elem.ivex==w&&e->elem.jvex==v))
			  D[v][w].a=e->elem.length;
	  for( u=0;u<g.vexNum;++u)
		  if(D[v][w].a<INFINITY)
		  {
		    P[v][w].edges[P[v][w].len].vx=v;
			P[v][w].edges[P[v][w].len].vy=w;
			P[v][w].len=1;
		  }//if
	}//for
  for(u=0;u<g.vexNum;++u)
	  for(v=0;v<g.vexNum;++v)
		  for(w=0;w<g.vexNum;++w)
			  if(D[v][u].a+D[u][w].a<D[v][w].a)
			  {
				  D[v][w].a=D[v][u].a+D[u][w].a;
				  for( i=0;i<P[v][u].len;++i)
				      P[v][w].edges[i]=P[v][u].edges[i];
				  for( j=0;j<P[u][w].len;++j)
					  P[v][w].edges[i+j]=P[u][w].edges[j];
				  P[v][w].len=P[v][u].len+P[u][w].len;
			  }//if
}//ShortestPath 

void OutSP(Graph g)
{
  int m,n,i;
  char a;
  do{
      cout<<"\n请输入开始的景点序号：";
      cin>>m;
      cout<<"\n请输入最终的景点序号：";
	  cin>>n;
      for(i=0;i<=ALLP[m][n].num;i++)
	  {
	      if(i==0) cout<<"（起点）"<<g.Adjmulist[m].data.name<<"——";
	      else if(i==ALLP[m][n].num) cout<<g.Adjmulist[n].data.name<<"（终点）";
	      else cout<<ALLP[m][n].vertices[i]<<"——";
	  }
      cout<<endl<<"路径长度为："<<D[m][n].a<<endl ;
	  cout<<"请选择：结束查询——q		继续查询——c：";
	  cin>>a;
  }while(a!='q');
}//OutSP

void main()
{
  char ch;
  char str[100];
  int c,i,j,m=0,n=0;
  cout<<"\n				校园导游咨询 \n";
  Graph g;
  InitGraph(g);
  cout<<"\n请输入校园景点数据的源文件路径：\n(例：e:\\校园景点路径.txt)：";
  cin>>str;
  CreateGraph(g,str);
  ShowGraph(g);
  for( i=0;i<MAXVTXNUM;i++)
	     for(j=0;j<MAXVTXNUM;j++)
		       InitPath(P[i][j]);
  ShortestPath(g,P,D);
  for( i=0;i<MAXVTXNUM;i++)
	     for( j=0;j<MAXVTXNUM;j++)
		       OutPath(g,P[i][j],ALLP[i][j]);
  do{
     cout<<"\n请选择：\nc——重建路径\nv——显示景点信息\np——查询最短路径\nq——退出系统\n你的选择为：";
     cin>>ch;
     switch(ch)
	 {
	 case 'c':  InitGraph(g);
                 cout<<"\n请输入校园景点数据的源文件路径：\n(例：e:\\校园景点路径.txt)：";
				cin>>str;
				if(CreateGraph(g,str))
				  ShowGraph(g);
				break;
	 case 'v':  cout<<"\n请输入景点的编号：";
		        cin>>c;
				ShowVex(g,c);
				break;
	 case 'p':  OutSP(g);
                break;
	 default:   cout<<"对不起，你的选择有错误！";
	 }
  }while(ch!='q'&&ch!='Q');
}

void InitGraph(Graph&g)
{
  g.vexNum=0;
  g.edgeNum=0;
  for(int i=0;i<MAXVTXNUM;i++)
  {
    g.Adjmulist[i].firstEdge=NULL;
  }
}

int LocateVex(Graph&g,char*uname)
{
  int i;
  for(i=0;i<g.vexNum;i++)
  {if(!(strcmp(uname,g.Adjmulist[i].data.name)))return --i;}
  return -1;
}

void GetVex(Graph g,int i,VertexType&v)
{
  v=g.Adjmulist[i].data;
}

EdgePtr FirstEdge(Graph g,int vi)
{
	//返回个中指向依附于顶点vi的第一条边的指针
  return g.Adjmulist[vi].firstEdge;
}//FirstEdge

void NextEdge(Graph g,int vi,EdgePtr p,EdgePtr&q)
{
	//以vj返回g中依附于顶点vi的一条边的另一端点
	//以q返回g中依附于顶点vi相对于p所指边的下一条边
	if(p->elem.ivex==vi){ q=p->ilink; }
	else {q=p->jlink; }
}//NextEdge

void InsertVex(Graph&g,VertexType v)
{
	//在图g的邻接多重表中添加一个顶点e
  g.Adjmulist[g.vexNum].data=v;
  g.Adjmulist[g.vexNum].firstEdge=NULL;
  g.vexNum++;
}//InsertVex

void InsertEdge(Graph&g,EdgeType e)
{
    //在图g的邻接多重表中添加一条边e
  EdgePtr p=(EdgePtr)malloc(sizeof(EdgeNode));
  p->elem=e;
  p->ilink=FirstEdge(g,e.ivex);
  p->jlink=FirstEdge(g,e.jvex);
  p->tag=0;
  g.Adjmulist[e.ivex].firstEdge=p;
  g.Adjmulist[e.jvex].firstEdge=p;
  g.edgeNum++;
}//InsertEdge

int CreateGraph(Graph&g,char*str)
{
	//建立图的多重邻接表
  ifstream fin(str);
  if(fin.fail()){cout<<"输入的文件名错误！";return 0;}
  int vn,en;
  fin>>vn>>en;
  VertexType v;
  EdgeType e;
  for(int i=0;i<vn;i++)
  {
    fin>>v.name>>v.info;
	InsertVex(g,v);
  }
  for(i=0;i<en;i++)
  {
    fin>>e.ivex>>e.jvex>>e.length;
	if(e.length)InsertEdge(g,e);
  }
  fin.close();
  return 1;
}//CreateGraph

void ShowVex(Graph g,int vi)
{
	if(vi>=g.vexNum){cout<<"\n此处景点是不存在的！"; return;}
    cout<<endl<<"此处景点名为："<<g.Adjmulist[vi].data.name<<endl<<"次处景点信息："<<g.Adjmulist[vi].data.info<<endl;
}//ShowVex

void ShowGraph(Graph&g)
{
  EdgePtr e=NULL,p=NULL;
  if(g.vexNum==0){cout<<"\n校园景点信息还没有创建！";return;}
  cout<<"\n已经创建好了的的校园景点以及其路径如下所示：\n";
  cout<<"\n景点的编号\t景点的名称\n";
  for(int i=0;i<g.vexNum;i++)
  { 
    cout<<i<<"\t\t"<<g.Adjmulist[i].data.name<<endl;
  }
  cout<<"\n路径（景点1编号，景点2编号）\t路径长度\n";
  for(i=0;i<g.vexNum;i++)
  {
	 e=FirstEdge(g,i);
     while(e!=NULL)
	 {   
		 if(e->tag==0)
		 {
			cout<<"\n（"<<e->elem.ivex<<","<<e->elem.jvex
		    	<<"）\t\t\t\t"<<e->elem.length ;
		 }
		 e->tag=1;
		 NextEdge(g,i,e,e);
	 }
  }
  cout<<endl;
}//ShowGraph