校园导航系统(可用)

#include
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#define Max 32767
#define NUM 11
typedef struct ArcCell{
int adj; // 相邻接的景点之间的路程
char *info;
}ArcCell; // 定义边的类型
typedef struct VertexType{
int number; // 景点编号
char *sight; // 景点名称
char *description; // 景点描述
}VertexType; // 定义顶点的类型
typedef struct{
VertexType vex[NUM]; // 图中的顶点，即为景点
ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离
int vexnum,arcnum; // 顶点数，边数
}MGraph; // 定义图的类型
MGraph G; // 把图定义为全局变量
int P[NUM][NUM]; // //
long int D[NUM]; // 辅助变量存储最短路径长度
int x[13]={0};
void CreateUDN(int v,int a); // 创建图的函数
void pingmu(); //屏幕输出函数
void introduce();
void ShortestPath(int num); //最短路径函数
void output(int sight1,int sight2); //输出函数
void PrintMGraph();
char Menu(); // 主菜单
void search();
;// 查询景点信息
char SearchMenu(); // 查询子菜单
void HaMiTonian(int); // 哈密尔顿图的遍历
void NextValue(int);
void display(); // 显示遍历结果

void main() // 主函数
{ int v0,v1;
char ck;
system("color 3f");//背景颜色显示函数
CreateUDN(NUM,11);
do
{
ck=Menu();
switch(ck)
{

case'1':
introduce();//介绍函数
printf("\n\n\t\t\t%-25s\n\n",G.vex[0].description);
getchar();
getchar();
break;
case '2':
system("cls");
pingmu();
printf("\n\n\t\t\t请选择起点景点（1～10）：");
scanf("%d",&v0);
printf("\t\t\t请选择终点景点（1～10）：");
scanf("%d",&v1);
ShortestPath(v0); // 计算两个景点之间的最短路径
output(v0,v1); // 输出结果
printf("\n\n\t\t\t\t请按回车键继续...\n");
getchar();
getchar();
break;
case '3':search();
break;
case '4':
system("cls");
pingmu();//屏幕输出函数，输出操作界面
x[0]=1;
HaMiTonian(1);
printf("\n\n\t\t\t\t请按回车键继续...\n");
getchar();
getchar();
break;
case'5':
PrintMGraph();
printf("\n\n\t\t\t\t请按回车键继续...\n");
getchar();
getchar();
break;
};
}while(ck!='e');

}

char Menu() // 主菜单 //
{
char c;
int flag;
do{
flag=1;
system("cls");
pingmu();
introduce();
printf("\n\t\t┏━━━━━━━━━━━━━━━━━━━┑\n");
printf("\t\t┃ ┃\n");
printf("\t\t┃ 1.学校简介 ┃\n");
printf("\t\t┃ 2.查询景点路径 ┃\n");
printf("\t\t┃ 3.查询景点信息 ┃\n");
printf("\t\t┃ 4.查看参观路线 ┃\n");
printf("\t\t┃ 5.查询各景点之间的距离 ┃\n");
printf("\t\t┃ e.退出 ┃\n");
printf("\t\t┃ ┃\n");
printf("\t\t┗━━━━━━━━━━

━━━━━━━━━┛\n");
printf("\t\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e')
flag=0;
}while(flag);
return c;
}
char SearchMenu() // 查询子菜单
{
char c;
int flag;
do{
flag=1;
system("cls");
pingmu();
introduce();
printf("\n\t\t┏━━━━━━━━━━━━━━━━━━┑\n");
printf("\t\t┃ ┃\n");
printf("\t\t┃ 1、按照景点编号查询 ┃\n");
printf("\t\t┃ 2、按照景点名称查询 ┃\n");
printf("\t\t┃ e、返回 ┃\n");
printf("\t\t┃ ┃\n");
printf("\t\t┗━━━━━━━━━━━━━━━━━━┛\n");
printf("\t\t\t请输入您的选择：");
scanf("%c",&c);
if(c=='1'||c=='2'||c=='e')
flag=0;
}while(flag);
return c;
}
void search() // 查询景点信息
{
int num;
int i;
char c;
char name[20];
do
{
system("cls");
c=SearchMenu();
switch (c)
{
case '1':
system("cls");
introduce();
pingmu();
printf("\n\n\t\t请输入您要查找的景点编号：");
scanf("%d",&num);
for(i=0;i{
if(num==G.vex[i].number)
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按任回车返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到！");
printf("\n\n\t\t\t按回车键返回...");
getchar();
getchar();
}
break;
case '2':
system("cls");
pingmu();
introduce();
printf("\n\n\t\t请输入您要查找的景点名称：");
scanf("%s",name);
for(i=1;i{
if(!strcmp(name,
G.vex[i].sight))
{
printf("\n\n\t\t\t您要查找景点信息如下:");
printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
printf("\n\t\t\t按回车键返回...");
getchar();
getchar();
break;
}
}
if(i==NUM)
{
printf("\n\n\t\t\t没有找到！");
printf("\n\n\t\t\t按回车键返回...");
getchar();
getchar();
}
break;
}
}while(c!='e');
}

void CreateUDN(int v,int a) // 创建图的函数
{
int i,j;

G.vexnum=v; // 初始化结构中的景点数和边数
G.arcnum=a;
for(i=1;i// 初始化没一个景点名及其景点描述
G.vex[0].sight="学校简介";
G.vex[1].sight="前校门";
G.vex[2].sight="活动中心";
G.vex[3].sight="计算机楼";
G.vex[4].sight="科技大楼";
G.vex[5].sight="田径场";
G.vex[6].sight="普宿";
G.vex[7].sight="食堂";
G.vex[8].sight="公寓";
G.vex[9].sight="后校门";
G.vex[10].sight="图书馆和教学楼";

// 这里把所有的边假定为32767，含义是这两个景点之间是不可到达
for(i=1;i{
for(j=1;j{
G.arcs[i][j].adj=Max;
G.arcs[i][j].info=NULL;
}
}

//下边是可直接到达的景点间的距离，由于两个景

点间距离是互相的，
// 所以要对图中对称的边同时赋值。
G.arcs[1][4].adj=G.arcs[4][1].adj=100;
G.arcs[1][2].adj=G.arcs[2][1].adj=30;
G.arcs[1][3].adj=G.arcs[3][1].adj=100;
G.arcs[3][5].adj=G.arcs[5][3].adj=100;
G.arcs[4][5].adj=G.arcs[5][4].adj=100;
G.arcs[3][6].adj=G.arcs[6][3].adj=200;
G.arcs[3][4].adj=G.arcs[4][3].adj=50;
G.arcs[2][4].adj=G.arcs[4][2].adj=50;
G.arcs[5][7].adj=G.arcs[7][5].adj=100;
G.arcs[4][6].adj=G.arcs[6][4].adj=400;
G.arcs[6][7].adj=G.arcs[7][6].adj=100;
G.arcs[6][8].adj=G.arcs[8][6].adj=500;
G.arcs[7][8].adj=G.arcs[8][7].adj=200;
G.arcs[7][9].adj=G.arcs[9][7].adj=20;
G.arcs[6][9].adj=G.arcs[9][6].adj=120;
G.arcs[9][10].adj=G.arcs[10][9].adj=50;
}
// 打印出邻接矩阵
void PrintMGraph()
{
int i,j;
cout<<"\n ====================================================================\n\n ";
for(i=1;i{
cout<}
cout<for(i=1;i{
cout<<"\n\n"<for(j=1;j{
if(G.arcs[i][j].adj==Max)
cout<<" @ ";
else
cout<<" "<}
}
cout<<"\n\n\n\n==========================================================================================\n\n\n";
}

void introduce() // 介绍函数
{
int i;

for(i=1;i<=NUM;i++)
{
G.vex[0].description="湖南工业大学是一所具有50年办学历史的多科性大学!!\n 2008年被教育部评定为本科教学工作水平优秀高校\n\t2009年获得外国留学生招收资格.\n\t学校位于中部老工业基地、湖南工业重镇、“两型社会”建设实验区——株洲市\n\t是株洲惟一的多科性大学!!\n\t学校以包装教育为特色，是我国第一个被国际包装协会（IAPRI）接纳的会员单位\n\t是教育部全国普通高校包装工程专业教学指导分委员会、中国包装联合会包装教育 委员会的主任单位和中国包装技术培训中心所在地!";
G.vex[1].description="上了坡之后就可以看到著名的湖南工业大学工学院校区的前校门";
G.vex[2].description="学生活动中心,什么开学典礼,迎新晚会都在这举行";
G.vex[3].description="我们学院的老师办公和同学上机编程的地方";
G.vex[4].description="这是我们学校最高的楼了,能在这里办公的都是学校的领导,其实 也可以叫行政大楼";
G.vex[5].description="我们学校别的地方都很破,就这田径场还像样,各个校区都要到这 里来搞运动会";
G.vex[6].description="这是我们学校的宿舍,称为普宿就是因为很破^^^^^^^^^";
G.vex[7].description="食堂,同学们吃饭的地方,五楼,菜的种类很多\n\t 什么蒸菜啥的都有,就是不好吃";
G.vex[8].description="这是我住的地方,比普宿好多了,条件不错,就是有点贵,前面住男 生,后面住女生,所以女生可以自由出入男生寝室而男生就不能进女生

寝室了";
G.vex[9].description="学校的后校门,从这里出去,有很多餐馆,都还算便宜\n\t 一般周日都在这聚餐";
G.vex[10].description="教学楼和图书馆在一起,到是挺方便的,只是上课下课的时候有点 拥挤";
}
}
void pingmu() // 屏幕输出函数
{
int i;
printf("制作者：湖南工业大学-计算机与通信学院-计093班-任琛-学号：09408100314\n");
printf("\n\t\t%c%c%c%c%c%c%c%c%c%c%c欢迎来到湖南工业大学%c%c%c%c%c%c%c%c%c%c\n\n",6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6);
printf("\t\t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n",3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3);
printf("\t\t%c\t\t学校简介\t\t%c\n",1,1);
printf("\t\t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n",3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3);
printf("\t\t%c\t\t学校概况\t\t%c\n",6,6);
printf("\t\t%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c\n",3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3);
for(i=1;i{
printf("\t\t%c\t\t(%2d)%-20s%c\t\t\t",1,i,G.vex[i].sight,1); // 输出景点列表
}
printf("\t\t%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c%c\n\n",1,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,1);
}
void ShortestPath(int num) // 迪杰斯特拉算法最短路径函数 num为入口点的编号
{
int v,w,i,t; // i、w和v为计数变量
int final[NUM];
int min;
for(v=1;v{
final[v]=0; // 假设从顶点num到顶点v没有最短路径
D[v]=G.arcs[num][v].adj;// 将与之相关的权值放入D中存放
for(w=1;wP[v][w]=0;
if(D[v]<32767) // 存在路径
{
P[v][num]=1; // 存在标志置为一
P[v][v]=1; // 自身到自身
}
}
D[num]=0;
final[num]=1; // 初始化num顶点属于S集合
// 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合
for(i=1;i{
min=Max; // 当前所知离顶点num的最近距离
for(w=1;wif(!final[w]) // w顶点在v-s中
if(D[w]{
v=w;
min=D[w];
}
final[v]=1; // 离num顶点更近的v加入到s集合
for(w=1;wif(!final[w]&&((min+G.arcs[v][w].adj){
D[w]=min+G.arcs[v][w].adj;
for(t=0;tP[w][t]=P[v][t];
P[w][w]=1;
}
}
}
void output(int sight1,int sight2) // 输出函数
{
int a,b,c,d,q=0;
a=sight2; // 将景点二赋值给a
if(a!=sight1) // 如果景点二不和景点一输入重合，则进行...
{
printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);// 输出提示信息
printf("\t(最短距离为 %dm.)\n\n\t",D[a]); // 输出sight1到sight2的最短路径长度，存放在D[]

数组中
printf("\t%s",G.vex[sight1].sight); // 输出景点一的名称
d=sight1; // 将景点一的编号赋值给d
for(c=0;c{
gate:; // 标号，可以作为goto语句跳转的位置
P[a][sight1]=0;
for(b=0;b{
if(G.arcs[d][b].adj<32767&&P[a][b]) // 如果景点一和它的一个临界点之间存在路径且最短路径
{
printf("-->%s",G.vex[b].sight); // 输出此节点的名称
q=q+1; // 计数变量加一，满8控制输出时的换行
P[a][b]=0;
d=b; // 将b作为出发点进行下一次循环输出，如此反复
if(q%8==0) printf("\n");
goto gate;
}
}
}
}
}
void HaMiTonian(int m) // 哈密尔顿图的遍历
{
if(m>8) return;
L: NextValue(m);
if(x[m]==0)
return;
if(m==7&&G.arcs[1][x[8]-1].adj!=32767)
display();
else
HaMiTonian(m+1);
goto L;
}
void NextValue(int k) //
{
int j;
l:x[k]=(x[k]+1)%10;
if(x[k]==0)
return;
if(G.arcs[x[k-1]-1][x[k]-1].adj!=32767)
{
for(j=0;jif(x[j]==x[k])
goto l;
return;
}
else
goto l;
}
void display()
{
int i=1;
printf("\n\n\t");
for(i=1;i<8;i++)
printf("%s->",G.vex[x[i]-1].sight);
printf("出口");
printf("\n");
}