校园导游系统.cpp

有很多数据结构的课设

// 校园导游系统.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#define vex 4
#define arc 4
#define max 100
#define INFINITY 45886946

struct view
{
	char name[50];
	char intro[200];
};

struct mgraph
{
	view vexs[vex];
	int arcs[vex][arc];
	int vexnum,arcnum;

};

typedef struct {
	int *base;
	int *top;
	int size;
}SqStack;
int initstack(SqStack &s)
{
	s.base=new int[max];
	if(!s.base) exit(1);
	s.top=s.base;
	s.size=max;
	return 1;
}

int push(SqStack &s,int x)
{
	if (s.top-s.base>=s.size)
		return 0;
	*s.top++=x;
	return 1;
}
int pop(SqStack &s,int &x)
{
	if (s.top==s.base)
		return 0;
	x=*--s.top;
	return 1;
}

int _tmain(int argc, _TCHAR* argv[])
{
	system("color 3e");                            //利用DOS命令设定背景，文字颜色
	mgraph G;
	//先对各景点信息进行初始化
	strcpy(G.vexs[0].name,"北苑大门");
	strcpy(G.vexs[0].intro,"中原工学院的北苑大门，在主大门建成之前，暂时是我校的主要大门");
	strcpy(G.vexs[1].name,"图书馆");
	strcpy(G.vexs[1].intro,"中原工学院图书馆是一个两座连体的6层建筑大楼，正对将来的主广场，雄伟壮观");
	strcpy(G.vexs[2].name,"北苑餐厅");
	strcpy(G.vexs[2].intro,"北苑餐厅是一个4层建筑，担负着北苑学生的吃饭重任");
	strcpy(G.vexs[3].name,"教学区");
	strcpy(G.vexs[3].intro,"在南苑有一个有多座建筑组成的大型建筑群，它就是中原工学院的教学区");
	G.vexnum=vex;
	G.arcnum=arc;

	G.arcs[0][1]=10;
	G.arcs[0][2]=2;
	G.arcs[0][3]=INFINITY;
	G.arcs[1][2]=3;
	G.arcs[1][3]=INFINITY;
	G.arcs[2][3]=4;
	for(int v=0;v<vex;v++)//图的邻接矩阵的对角线值为0；
		for(int w=0;w<arc;w++)
		{
			G.arcs[v][v]=0;
			G.arcs[w][v]=G.arcs[v][w];
		}
A:
	system("cls");
	cout<<endl<<"欢迎使用本校园景点导游系统"<<endl;
	cout<<endl<<"请选择你要进行的操作："<<endl;
	cout<<endl<<"1，景点浏览     2，旅游线路咨询    3，退出"<<endl;
	int opinion;
	cin>>opinion;
	if(opinion==1)
	{
		for(int i=0;i<vex;i++)
		{
			//cout<<G.vexs[1].intro;
			cout<<endl<<"景点 "<<i+1<<"："<<G.vexs[i].name<<endl<<G.vexs[i].intro;
		}
		for(int v=0;v<vex;v++)
			for(int w=0;w<arc;w++)
				if(G.arcs[v][w]!=INFINITY && v!=w &&w>v)
				{
					cout<<endl<<endl<<G.vexs[v].name<<"  到  "<<G.vexs[w].name<<"  "<<G.arcs[v][w]<<"  公里"<<endl;
				}
        goto B;
	}
	else if(opinion==2)
	{
		void shortestpath(mgraph G,int v0,int  p[][arc],int d[]);
		cout<<endl<<"请输入你的出发地点，以景点代号表示"<<endl;
		for(int i=0;i<vex;i++)
			cout<<i+1<<G.vexs[i].name<<"    ";
		int kk;
		cin>>kk;
		kk--;
		cout<<endl<<endl<<"请输入你的目的地："<<endl;
		int j;
		cin>>j;
		j--;
		

		void floydshortestpath(mgraph G,int **&d,int **&p);
		int **d,**p;
		floydshortestpath(G,d,p);
		SqStack S;
		initstack(S);
		int i=0,k;
		
		while(i<G.vexnum)
		{  
			if(i==kk)
			{
				if(p[i][j]==-1) 
					continue;
				else
				{
					k=j;
					while(p[i][k]!=i)
					{
						push(S,p[i][k]);
						k=p[i][k];
					}
					cout<<G.vexs[i].name<<"到"<<G.vexs[j].name<<"最短路径为：";
					cout<<G.vexs[i].name<<"--->";
					while(S.top!=S.base)
					{
						pop(S,k);
						cout<<G.vexs[k].name<<"-->";
					}
					cout<<G.vexs[j].name<<endl;
				}
				break;
			}
			else
				i++;
		}
		cout<<"其最短路径长度为:"<<d[kk][j];
		for(i=0;i<G.vexnum;i++)
		{
			delete[]d[i];
			delete[]p[i];
		}
		delete []p;
		delete []d;
		goto B;
	}
	else
		exit(1);
B:
	cout<<endl<<endl<<endl;
	cout<<"操作完毕，按任意键进入下一次操作！→"<<endl;
	while (!kbhit());                             //调用库函数，等待用户按键
	system("cls");
	goto A;
	return 0;
}

void floydshortestpath(mgraph G,int **&d,int **&p)
{


	int i,j,k;


	d=new int *[G.vexnum];
	p=new int *[G.vexnum];
	for(i=0;i<G.vexnum;i++)
	{
		d[i]=new int [G.vexnum];
		p[i]=new int [G.vexnum];
		for(j=0;j<G.vexnum;j++)
		{
			d[i][j]=G.arcs[i][j];
			if(i!=j&&G.arcs[i][j]<max)
				p[i][j]=i;
			else
				p[i][j]=-1;
		}
	}
	for(k=0;k<G.vexnum;k++)
		for(i=0;i<G.vexnum;i++)
			for(j=0;j<G.vexnum;j++)
				if(d[i][k]+d[k][j]<d[i][j])
				{
					d[i][j]=d[i][k]+d[k][j];
					p[i][j]=p[k][j];
				}
}