sx1.cpp

一个校园地图系统,用数据结构编的.新建一个文本文件输入地点和路径长度就可以啦

// sx1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <fstream.h>

#define MVNum 500                              //最大顶点数
#define Maxint 80000

enum boolean{FALSE,TRUE};

typedef  int   VRType;
typedef  char  InfoType;
typedef  char  VertexType;
typedef	 int   Status;
typedef  int   AdjMatrix;

int vexnum;                                     //顶点总数
int arcnum;                                     //弧（边）总数

typedef   struct  vnode{
	AdjMatrix number;
	VertexType name[50];
	InfoType  info[100];
}vnode;                                         //将顶点定义为结构体，查找时用number进行查找更方便

typedef struct{                                 //图的定义
	vnode V[MVNum];                             //顶点表，用一维向量即可
	AdjMatrix arcs[MVNum][MVNum];               //邻接矩阵                    
}Mgraph; 

void text(Mgraph *G)
{
    int i,j,k,w;
	ifstream inFile("vera.txt");
    if(!inFile)
		{ 
			cerr<<"cannot open vera.dat"<<endl;
			exit(1);
		}
    inFile>>vexnum>>arcnum;
	for(i=1;i<=9;i++)
		inFile>>G->V[i].number>>G->V[i].name>>G->V[i].info;
	for(i=1;i<=9;i++)                                           //初始化邻接矩阵	
		for(j=1;j<=9;j++)
			G->arcs[i][j]=Maxint;
	for(k=1;k<=10;k++)
	{	
		inFile>>i>>j>>w;
		G->arcs[i][j]=G->arcs[j][i]=w;
	}
}

void print(Mgraph *G)
{
	int i;
	for(i=1;i<=9;i++)
    {
		cout<<G->V[i].number<<G->V[i].name<<endl;
	}
}

void Dijkstra(Mgraph *G,int v1, int n)
{
	//用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径Path[v]及其距离Dist[v]
	//S[v]为真当且仅当v属于S,即已求得从vl到v的最短路径
	int Dist[MVNum],Path[MVNum];
	int i,w,min;
	int v,vt;
	enum boolean S[MVNum];
	for(v=1;v<=n;v++)
	{//初始化S和Dist
		S[v]=FALSE;                          //置空最短路径终点集
		Dist[v]=G->arcs[v1][v];	             //置初始的最短路径值
		if(Dist[v]<Maxint)  
			Path[v]=v1;                      //v1是v的前趋
		else Path[v]=0;                      //v无前趋
	}
	Dist[v1]=0;
	S[v1]=TRUE;                              //S集初始时只有源点、源点到源点的距离为0
	//开始循环、每次求得v1到某个v顶点的最短路径，并加v到S集中
	for(i=2;i<n;i++)
	{//其余n-1个顶点
		min=Maxint;
		for(w=1;w<=n;w++)
			if(!S[w]&&Dist[w]<min) 
				{v=w;min=Dist[w];}			      //w顶点离v1顶点更近
				S[v]=TRUE;
		for(w=1;w<=n;w++)                     //更新当前最短路径及距离
			if(!S[w]&&(Dist[v]+G->arcs[v][w]<Dist[w]))
			{//修改Dist[w]和Path[w],w属于V-S
				Dist[w]=Dist[v]+G->arcs[v][w];
				Path[w]=v;
			}
	}
	cout<<"请输入要查询的终点标号"<<endl;
	cin>>vt;
	cout<<"路径长度：路径为："<<endl;
	cout<<setw(5)<<Dist[vt];
	cout<<setw(5)<<endl;
	v=Path[vt];
	while(v!=0)
	{
		cout<<"<-"<<v;
		v=Path[v];
	}
		cout<<endl;
}

void main()
{
	int n1,n2;
	int v,i,j;	
	cout<<"         ##################欢迎来到XXXX！################"<<endl<<endl;
	cout<<"########################这是一个校园景点查询系统！###########################"<<endl<<endl;
	
	Mgraph *G;
	G=new Mgraph;
	ifstream inFile("vera.txt");
    if(!inFile)
		{ 
			cerr<<"cannot open vera.dat"<<endl;
			exit(1);
		}
    inFile>>n1>>n2;
	cout<<"**********XXXX共有"<<n1<<"个景点**********"<<endl<<endl;
	cout<<"**********各景点间有"<<n2<<"条路径**********"<<endl<<endl;
	cout<<"**********以下为各标号以及其对应的景点**********"<<endl<<endl;
	text(G);
	print(G);
	do
	{
		cout<<"要进行景点信息查询，请输入1"<<endl;
		cout<<"要进行景点之间路径查询，请输入2"<<endl;
		cout<<"要退出本系统，请输入0"<<endl<<endl;
		cin>>i;
		switch(i)
		{
		case 1:
			cout<<"请输入您要查询的景点的标号"<<endl;
			cin>>j;
			cout<<G->V[j].name<<G->V[i].info<<endl;
			break;
		case 2:
			cout<<"请输入要查询的源景点的标号v：";
			cin>>v;
			Dijkstra(G,v,n1);                         //调用迪杰斯特拉算法
			cout<<"最短路径已得出！"<<endl;
			break;
		case 0: 
			exit(0);
		}
	}while(i!=0);
}