1.cpp

校园导游图算法--数据结构中有关图的算法 按v求最短路径 按s求信息； 按q退出； 地图在map图像文件里

#include"graphic.h"
#include"path.h"
#include<iostream.h>
#include<stdlib.h>
#include<process.h>
#include<conio.h>
#include"window.h"
typedef int bool;
/*void CreatGraph(GraphType g,File *f)
{
	InitGraph(g);
	fscanf(f,g.vexNum,g.edgeNum);
	for(int i=0;i<g.vexNum;i++)
	{
		fscanf(f,v.name,v.info);
		InsertVex(g,v);
	}
	for(int k=0;k<g.edgeNum;k++)
	{
		fscanf(f,e.ivex,e.jvex,e.length);
		if(e.length) InsertEdge(g,e);
	}
}*/
void printsight(GraphType g,string sight)
{
	gotoxy(10,10);
	for(int i=0;i<g.vexNum;i++)
	{
		if(*sight==*g.Adjmulist[i].data.name) 
		{
			cout<<*sight<<" infomation's:"<<g.Adjmulist[i].data.info;
			return;
		}
		else continue;
	}
	cout<<"wrong!Please reload!";
}
void printpath(int pathlength,PType PathInfo)
{
	gotoxy(10,10);
	cout<<"from "<<PathInfo.vertices[0]<<" to "<<PathInfo.vertices[PathInfo.num]<<" 's the shortest path is:";
	for(int i=0;i<PathInfo.num;i++)
		cout<<PathInfo.vertices[i]<<"-->";
	cout<<PathInfo.vertices[PathInfo.num];
	gotoxy(10,11);
	cout<<"though "<<PathInfo.num<<" sights,you need walk length:"<<pathlength<<endl;;
	gotoxy(20,15);
}
void cancel()
{
	    gotoxy(10,8);
		cout<<"                                                           ";
		gotoxy(10,9);
		cout<<"                                                           ";
		gotoxy(10,10);
		cout<<"                                                          ";
		gotoxy(10,11);
		cout<<"                                                           ";
		gotoxy(10,12);
		cout<<"                                                           ";
		gotoxy(10,13);
		cout<<"                                                           ";
		gotoxy(10,14);
		cout<<"                                                           ";
		gotoxy(10,15);
		cout<<"                                                           ";
		gotoxy(10,15);
		gotoxy(10,16);
		cout<<"                                                           ";
		gotoxy(10,15);
		cprintf("Operation:");
		gotoxy(20,15);
} 
void creat(GraphType &g)
{
	InitGraph(g);
	static int v_num=4;
	static int e_num=5;
	VertexType v[4];
	v[0].info="this is our study building!";
	v[0].name="a";
	v[1].info="2";
	v[1].name="b";
	v[2].info="3";
	v[2].name="c";
	v[3].info="4";
	v[3].name="d";
	EdgeType e[5];
	e[0].ivex=0;
	e[0].jvex=1;
	e[0].length=10;
	e[1].ivex=0;
	e[1].jvex=3;
	e[1].length=100;
	e[2].ivex=1;
	e[2].jvex=2;
	e[2].length=20;
	e[3].ivex=0;
	e[3].jvex=2;
	e[3].length=80;
	e[4].ivex=2;
	e[4].jvex=3;
	e[4].length=30;
	for(int i=0;i<v_num;i++)
	{
		InsertVex(g,v[i]);
	}
	for(int k=0;k<e_num;k++)
	{
	    InsertEdge(g,e[k]);
	}
}
void PutInSet(int v,int ss[MAX])
{
	int i=0;
	for(i=0;i<=MAX;i++)
		if(ss[i]==0) break;
    ss[v]=1;
}
status InSet(int w,int ss[MAX])
{
	int i=0;
	for(i=0;i<=MAX;i++)
		if(ss[w]==1)
		{
			return TRUE;
		}
	return FALSE;
}
int minval(GraphType g,int ss[MAX],int dist[MAX])
{
	int min,u,n;
	int i=0;
	while(ss[i]==1) i++;
	min=dist[i];
	u=i;
	n=g.vexNum;
	while(i<n)
	{
		if(ss[i]==1) i++;
		else if(min>dist[i])
		{
			u=i;
			min=dist[i];
		}
		i++;
	}
	return u;
}
void ShortestPath(GraphType g,int st,int nd,int &pathLength,PType &PathInfo)
{
	int dist[MAX];
	PathType path[MAX];
	EdgePtr p,q;
	int adjvex,w;
	int maxint=100000;
	int ss[MAX];
	for(int i=0;i<g.vexNum;i++)
	{
		dist[i]=maxint;
		InitPath(path[i]);
	}
	p=FirstEdge(g,st);
	while(p)
	{
		NextEdge(st,p,adjvex,q);
		dist[adjvex]=p->elem.length;
		InsertPath(path[adjvex],st,adjvex);
		p=q;
	}
	bool found=FALSE;
    for(int k=0;k<=MAX;k++) ss[k]=0;
	ss[st]=1;
	dist[st]=0;
	while(!found)
	{
	    int min=minval(g,ss,dist);
		if(min==nd) found=TRUE;
		else{
			int v=min;
			PutInSet(v,ss);
			p=FirstEdge(g,v);
			while(p)
			{
				NextEdge(v,p,w,q);
				if(!InSet(w,ss)&&(dist[v]+p->elem.length)<dist[w])
				{
					dist[w]=dist[v]+p->elem.length;
					copyPath(path[w],path[v]);
					InsertPath(path[w],v,w);
				}
				p=q;
			}
		}
	}
	 pathLength=dist[nd];
	 OutPath(g,path[nd],PathInfo);
}
void GetShortestPath(GraphType g,string sname,string tname,int &pathLength,PType &PathInfo)
{
	int sv,tv;
	LocateVex(g,sname,sv);
    LocateVex(g,tname,tv);
	ShortestPath(g,sv,tv,pathLength,PathInfo);
}
void windows()
{
	int NUM;
	clrscr();
	DRAW_WIN();
	window(LEFT,TOP,RIGHT,BOTTOM);
	gotoxy(5,3);
	textcolor(WHITE);
	cprintf("**************** WELCOM TO THE GRAPHIC TEST PROGRA ****************");
	gotoxy(5,4);
	cprintf("*    Scenic Information-s       Visited Path-v         Quit-q     *");
	gotoxy(5,5);
	cprintf("*******************************************************************");
	gotoxy(5,20);
	cprintf("*******************************************************************");
	gotoxy(5,21);
	cprintf("*    Enter a operation code: s/S,v/V or q/Q    Help/H             *");
	gotoxy(5,22);
	textcolor(WHITE);
	cprintf("**************THANK YOU USING FOR USING THIS SYSTEM****************");
	gotoxy(10,15);
	cprintf("Operation:");
	gotoxy(20,15);
}
void main()
{
	GraphType g;
	InitGraph(g);
	creat(g);
	windows();
	char cmd;
	do{
	    cmd=getch();
	    string sight,sname,tname;
	    int pathlen;
	    PType spath;
	switch(cmd)
	{
	case 's':
		cancel();
		gotoxy(10,8);
		cprintf("please input the sight that you want to know:");
		gotoxy(55,8);
		cin>>sight;
		cout<<endl;
		gotoxy(10,9);
		printsight(g,sight);
		gotoxy(20,15);
		break;
	case 'v':
		cancel();
		gotoxy(10,8);
		cprintf("please input the shortest path that you want to know!");
		gotoxy(10,10);
		gotoxy(10,9);
		cout<<"from:";
		cin>>sname;
		gotoxy(20,9);
		cout<<"to:";
		cin>>tname;
		GetShortestPath(g,sname,tname,pathlen,spath);
		printpath(pathlen,spath);
		break;
	case 'h':
		gotoxy(10,8);
		cout<<"welcom to this graphic test program!         ";
		gotoxy(10,9);
		cout<<"From this program you can know our school.You can press";
		gotoxy(10,10);
		cout<<"'s'to view the sight and getting the infomation about it";
		gotoxy(10,11);
		cout<<"and you can press 'v' to get the shortest path from the ";
		gotoxy(10,12);
		cout<<"you input to the direction the endding.                 ";
		gotoxy(10,13);
		cout<<"The program's writter is Guanjibin(jackquen)            ";
		gotoxy(10,14);
		cout<<"The E-mail:[e-mail] qq:45899323"            ;
		gotoxy(10,15);
		cout<<"                  THAN YOU FOR USING!                   ";
		gotoxy(10,16);
		cout<<"               PRESS 's' or 'v' BACK                      ";
		break;
	}
	}while(cmd!='q'&&cmd!='Q');
}